数据结构第9章查找

数据结构

第四十三讲

顺序查找与折半查找

主讲：刘立嘉

1、 查找的基本概念

查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素

若表中存在这样一个记录，则称“查找成功”。查找结果给出整

个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。

n

对含有n个记录的表，ASL=∑pici 查找方法评价

i=1

n 查找速度其中：pi为查找表中第i个元素的概率，∑pi=1

i=1 占用存储空间多少ci为找到表中第i个元素所需比较次数

算法本身复杂程度

平均查找长度ASL(Average Search Length)：为确定记录

在表中的位置，需和给定值进行比较的关键字的个数的

期望值叫查找算法的~

关键字——是数据元素中某个数据项的值，它可以标识一个数据元素若此关键字可以唯一的标识一个记录，则称此关键字为“主关键字”。若此关键字能识别若干记录，则称之“次关键字”。

高考成绩表准考证号姓名各科成绩总分政治语文外语 85 78 82 86 75 80 88 90 80 259 243 242

…..

主关键字

179325 179326 179327

陈红陆华张平

Key=179326

…..

Key=179238

查找表可分为两类:

静态查找表仅作查询和检索操作的查找表。动态查找表

有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。

2、 静态查找表

StaticSearchTable {ADT ADT StaticSearchTableStaticSearchTable {

数据对象D：D是具有相同特性的数据元素的集合。每个数据元素

含有类型相同、可唯一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作 P： Create(&ST, n);

Destroy(&ST);

Search(ST, key);

Traverse(ST, Visit());

StaticSearchTable} ADT } ADT StaticSearchTable

3、顺序表的查找：顺序查找

以顺序表或线性链表表示静态查找表

静态查找表的顺序存储结构

struct {typedeftypedef structstruct {

ElemType *elem;

//数据元素存储空间基址，建表时

//按实际长度分配，0号单元留空 //

int length; //表的长度 intint

SSTable;} } SSTableSSTable;

顺序查找的查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。

顺序查找ST.elem 0 1当i不为0时，查找成功

i7 8

i

64 21 37 88 19 92 05 64 56 80 75 132 3 4 5 6 9 10 11 ST.Length

key=64 iST.elem当i为0时，查找不成功

i

60 21 37 88 19 92 05 64 56 80 75 130 1 2 3 4 5 6 7 8 9 10 11 ST.Length

key=60

Search_Seq(SSTable ST, intint Search_Seq(SSTable ST,

KeyType key) { KeyTypeKeyType key) {

// 在顺序表ST中顺序查找其关键字等于// key的数据元素。若找到，则函数值为 // key

// 该元素在表中的位置，否则为0。 //

ST.elem[0].key = key; // “哨兵”// “

for (i=ST.length; !EQ(ST.elem[i].key,key); --i); i=ST.length; !EQ(ST.elem[i].key,keyEQ(ST.elem[i].key,key); --i// 从后往前找

return i; // 找不到时，i为0

} // Search_Seq} // Search_Seq

分析顺序查找的时间性能

查找算法中的基本操作是将记录的关键字和给定值进行比较，因此，常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。

定义：查找成功时的平均查找长度

(Average Search Length)

为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值

ASL=∑PiCi

i=1n其中: n 为表长，Pi 为查找表中第i个记录的概n 率，且 ∑　Pi=1，Ci为找到该记录时，曾和给定

i=1值进行过比较的关键字个数。

对顺序表而言，Ci= n-i+1

ASL= nP1+(n-1)P2+…+2Pn-1+Pn

1在等概率查找的情况下，Pi= n顺序查找的平均查找长度为：1 n+1 ASLss=∑ (n i+ 1 )= n i=1 2n

在不等概率查找的情况下，ASLss 在

Pn≥Pn-1≥···≥P2≥P1时取极小值

若查找概率预先无法测定，为提高查找概率，在每个记录中附设一个访问频度域，并使记录始终按访问频度非递减有序的次序排列，使得查找概率大的记录在查找过程中不断往后移，以便在以后的逐次查找中减少比较次数。 或者在每次查找之后将刚查找到的记录直接移至表尾。

思考题：

1、问：对顺序结构如何线性查找？

答：利用顺序表

2、问：对单链表结构如何线性查找？

答：从头指针始 “顺藤摸瓜”

3、问：对非线性（树结构）如何顺序查找?

答：借助各种二叉树遍历操作！

4、有序表的查找：折半查找

上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。

若以有序表表示静态查找表，则查找过程可用折半查找进行。

折半查找

查找过程：每次将待查记录所在区间缩小一半适用条件：采用 …… 此处隐藏：544字，全部文档内容请下载后查看。喜欢就下载吧 ……