查找——顺序表的查找和有序表的查找

本文主要讲关于静态查找的顺序表查找和有序表的查找

1.顺序存储结构

Typedef struct {

ElemType*elem;(数据元素存储空间基址，0 号单元留空)

int length;(表长度)

}SSTable;

1.1 顺序表查找

顺序表的查找适用于顺序存储和链表存储的记录表。从表的任一端开始逐个与给定值相比较，若相等，则查找成功。返回值为该记录在表中的位置序号;若超出界限，则查找失败。返回值为零。适用于顺序存储与链表存储。

1.1.1 顺式存储的顺序查找

• 从尾部查找

Int Search-Seq(SSTableST,keyTypekey){

ST.elem[0].key=key;

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

return i;

} Search-seq

• 从头部查找

int Search_seq(SSTable ST,keytype key)

int i= 1;

{

while(i <= ST.length &&ST.elem[i].key!= key)

i++;

if(i>ST.length) return FALSE; //没找到

else return i; //找到了

}

• 从头部查找比从尾部查找效率低，建议用尾部查找法

1.1.2 链式存储的顺序查找

status getelement(link head,keytype key){

(for(p=head;p!=NULL&&p->key!=key;p=p->next);

return p;

}

1.2 有序表的查找

1.2.1 折半查找

折半查找(Binary Search)的过程是: 首先计算被查表的中间位置; 然后将中间位置记录的关键字与给定值相比较:若相等则查找成功;若中间位置记录的关键字小于给定值， 则下次从后半个表继续查找; 若中间位置记录的关键字大于给定值， 则下次从前半个表继续查找。

例如：查找 21 需要比较 3 次。

• 算法

Int Search-Bin(SSTable ST,keyType key) {

low = 1; high = ST.length; While( low<=high ) {

mid =(low +high)/2;

if EQ(key,ST.elemmid].key) return mid;

else if LTkey,ST.elem[mid].key) high= mid-1; else low =mid +1 ;

}

return 0;

}

折半查找的过程可以用下面的判定树表示:

从下图可见，查找 21 的过程恰好是走过一条从根 21 到结点 4 的路径,和给定关键字进行比较的关键字个数为该路径上的结点数或结点 4 在判定树上的层数。其他结点也类似。因此，折半查找在查找成功时进行比较的关键字个数不超过树的深度，而具有 n 个结点的判定树的深度为 [log₂n] +1，所以折半查找在查找成功时和给定值进行比较的关键字个数最多为 [log₂n] +1。