。

由于“集合”中的数据元素之间存在着松散的关系#xff0c;因此查找表是一种应用灵便的结构。

查找表是由同一类型的数据元素或记录构成的集合。

由于“集合”中的数据元素之间存在着松散的关系因此查找表是一种应用灵便的结构。

问题什么查找——根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素或记录

主关键字

问题查找成功否——根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素或记录

查询某个

数据元素的各种属性在查找表中插入一个数据元素删除查找表中的某个数据元素。

问题查找表怎么分类

查找的方法取决于查找表的结构即表中数据元素是依何种关系组织在一起的。

由于对查找表来说在集合中查询或检索一个

数据元素时。

若无规律可循只能对集合中的元素——加以辨认直至找到为止。

“查询”

是任何计算机应用系统中使用频度都很高的操作因此设法提高查找表的查找效率是本章讨论问题的出发点。

为提高查找效率一个办法就是在构造查找表时在集合中的数据元素之间人为地加上某种确定的约束关系。

7.2.1顺序查找

ST;//定义顺序表ST在顺序表ST中查找值为key的数据元素从最后一个元素开始比较

int

key){for(iST.length;i1;--i)if(ST.R[i].key)

return

key){for(iST.length;ST.R[i].key!key;--i)if(i0)

break;if(i0)

key){for(iST.length;ST.R[i].key!keyi0;--i);if(i0)

return

}改进把待查找关键字key存入表头“哨兵”、“监视哨”从后往前逐个比较可免去查找过程中每一部都要检测是否查找完毕加快速度。

int

key){ST.R[0].keykey;for(iST.length;ST.R[i].key!key;--i);return

}当ST.length较大时此改进能使进行一次查找所需的平均时间几乎减少一半。

时间效率分析比较次数与key位置有关

mid分别指向待查元素所在区间的上界、下界和中点key为给定的要查找的值初始时令low1highnmid[lowhigh/2]让k与mid指向的记录比较

若keyR[mid].key查找成功若keyR[mid].key则highmid-1若keyR[mid].key则lowmid1

重复上述操作直至lowhigh时查找失败

key){low1;highST.length;//置区间初值while(lowhigh){mid(lowhigh)/2;if(ST.R[mid].keykey)

return

if(keyST.R[mid].key)//缩小查找区间highmid-1;//继续在前半区间进行查找else

0;//顺序表中不存在待查元素

0;//查找不到时返回0mid(lowhigh)/2;if(keyST.elem[mid].key)

return

if(keyST.elem[mid].key)......//递归在前半区间进行查找else

......//递归在后半区间进行查找

将表分成几块且表或者有序或者分块有序若ij则第j块中所有记录的关键字均大于第i块中的最大关键字。

建立“索引表”每个结点含有最大关键字域和指向本块第一个结点的指针且按关键字有序。

查找过程先确定待查记录所在快顺序或折半查找再在块内查找顺序查找。

分块查找缺点要增加一个索引表的存储空间并对初始索引表进行排序运算。

适用情况如果线性表既要快速查找又经常动态变化则可采用分块查找。

查找方法比较

顺序查找折半查找分块查找ASL最大最小中间表结构有序表、无序表有序表分块有序存储结构顺序表、线性链表顺序表顺序表、线性链表