静态表的查找操作实验

实验B06: 静态表的查找操作实验

欧阳学文

一、实验名称和性质 所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 静态表的查找操作 2 □验证□综合√设计 √必做□选做 二、实验目的

1．掌握顺序查找操作的算法实现。

2．掌握二分查找操作的算法实现及实现该查找的前提。 3．掌握索引查找操作的算法实现。 三、实验内容

1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。

2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。

3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。

四、实验的软硬件环境要求

硬件环境要求： PC机（单机）

使用的软件名称、版本号以及模块：

Windows环境下的TurboC2.0以上或VC++ 五、知识准备

前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。 六、验证性实验 1．实验要求

编程实现如下功能：

欧阳学文创作

欧阳学文创作

（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。

（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。

（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。 2. 实验相关原理：

查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。

静态查找表采用顺序存储结构的数据描述为： #define MAXSIZE 100 /*顺序查找表的最大长度*/ typedefintkeytype; typedefstruct {keytype key; }redtype; typedefstruct

{redtypeelem[MAXSIZE]; int length;

}Sstable;

【核心算法提示】

查找操作是根据给定的某个值，在查找表中确定一个其

欧阳学文创作

欧阳学文创作

关键字等于给定值的数据元素或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。

（1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。

（2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。

【核心算法描述】

intsxsearch(SstableST, keytypekey)

/*在顺序查找表ST中，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */

欧阳学文创作

欧阳学文创作

{ ST.elem[0].key=key; /*在表头设置监视哨*/

for(i=ST.length;ST.elem[i].key!=key;i); /*从后往前顺序查找*/

return i; }

intbinsearch(SstableST,keytypekey)

/*在按关键字从小到大的有序顺序表ST中，用二分查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */ { low=1;high=ST.length; /*置查找区间的初值*/ while(low<=high) { mid=(low+high)/2;

if (key==ST.elem[mid].key)

return mid;/*找到匹配记录*/

else if (keyhigh=mid1;/*继续对左半部分进行二分查

找*/

else low=mid+1；/*继续对右半部分进行二分查找*/

欧阳学文创作

欧阳学文创作

}

return 0; /*找不到匹配记录*/ }

3．源程序代码参考

#define MAXSIZE 100 typedefintkeytype; typedefstruct { keytype key; }redtype;

typedefstruct

{ redtypeelem[MAXSIZE]; int length; }Sstable;

intsxsearch(SstableST,keytype Key)/*顺序查找函数*/ { int i;

ST.elem[0].key=Key;

for(i=ST.length;ST.elem[i].key!=Key;i); return i; }

intbinsearch(SstableST,keytype Key)/*二分法查找函数*/ { intlow,mid,high;

low=1;high=ST.length; while(low<=high)

{ mid=(low+high)/2;

if (Key==ST.elem[mid].key) return mid;

else if (Keyelse low=mid+1; }

欧阳学文创作

欧阳学文创作

return 0; }

main()/*主函数*/ {Sstable ST; inti,pos,x,key; pos=0; while(1)

{ printf(\"\\n 1Sxserach\\n\"); printf(\" 2Binserach\\n\"); printf(\" 3Exit\\n\");

printf(\"please input choose(13):\"); scanf(\"%d\ switch(x) { case 1:

printf(\"please input table length n:\");/*请求输入顺序表表长*/

scanf(\"%d\

printf(\"please input n data:\\n\");/*请求输入n个关键字值*/ for(i=1;i<=ST.length;i++) scanf(\"%d\

printf(\"please input key:\");/*请求输入待查找的记录关键字值*/

scanf(\"%d\

pos=sxsearch(ST,key); /*调用顺序查找函数*/ break; case 2:

printf(\"please input table length n:\");/*请求输入顺序表表长*/

scanf(\"%d\

printf(\"please input n data(sort):\\n\");/*请求输入n个关键字值（必须升序排列）*/ for(i=1;i<=ST.length;i++)

欧阳学文创作

欧阳学文创作

scanf(\"%d\

printf(\"please input key:\");/*请求输入待查找的记录关键字值*/

scanf(\"%d\

pos=binsearch(ST,key);/*调用二分法查找函数*/ break;

case 3: return;

default: printf(\"choose error\\n\"); }

if(pos==0)

printf(\"\\nthe data is not found.\\n\"); /*若找不到，提示信息*/ else

printf(\"\\nthe data is at position %d\\n\若找到，输出位置*/ }

4．运行结果参考如图61所示 图61 验证性实验运行结果

欧阳学文创作

欧阳学文创作

七、设计性实验 1．实验要求

编程实现如下功能： （1）建立索引查找表

（2）利用索引查找确定给定记录在索引查找表中的块号和在块中的位置。 2．核心算法分析

索引查找表有索引表和块表两部分所构成，其中索引表存储的是各块记录中的最大关键字值和各块的起始存储地址，用顺序存储结构，各块的起始存储地址的初始值置为空指针；而块表中存储的是查找表中的所有记录并且按块有序，用链式存储或顺序存储结构，在此用链式存储结构。则索引查找表的存储结构图如62所示：

欧阳学文创作

欧阳学文创作

ST ST. Length 3 ST. r

r[0] r[1] r[2] r[3]

12 23 47 …… 最大关键字块链头指针

3 15 31 6 23 45 12 14 37 9 21 47 ^ 4 ^ 13 ^ 图62 索引查找表的存储结构示意图

将如图62所示的存储结构描述为： #define MAXSIZE 100

typedefintkeytype;

typedefstructbnode /*块链中的结点类型*/ { keytype key; /*存储块中记录的关键字值*/

structbnode *next; /*指向块链中下一记录结点的指针*/ } Bnode;

typedefstructsnode /*索引表中元素的类型*/

{ keytypeMaxkey; /*存储各块记录中的最大关键字值*/ Bnode *head; /*块链的头指针*/ }Snode;

typedefstruct /*索引查找表的结构类型*/

欧阳学文创作

欧阳学文创作

{ Snode r[MAXSIZE]; /*索引顺序表*/

int length; /*索引顺序表中存储数据的个数*/ }Stable;

由于在索引查找表中，索引表是按关键字从小到大排列的有序顺序表，块链是一个无序链表，所有索引表的查找过程可归纳为：

（1）在索引表中用二分查找确定待查找的记录所在的块号；

（2）沿着块链指针用顺序查找的方法确定待查找的记录在块链中的存储位置。

如果查找成功，则输出待查找记录在索引表中的块号和在块链中的存储地址；如果查找失败，则输出“没有找到”的信息。

3．核心算法描述

intfindblock(Stable ST, keytype key)

/*用二分查找法在索引查找表ST的索引表中确定关键字值为key的待查找记录所在的块号,函数并返回值其块号值*/

{ intlow,high,mid;

low=1;high=ST.length; while(low<=high)

{ mid=(low+high)/2;

if (keylow=mid+1; }

return high+1; }

Blink findrec(Stable ST,keytype key)

/*用顺序查找法在索引查找表的块链中确定关键字值为key的待查找记录的存储位置，如查找成功则函数返回其

欧阳学文创作

欧阳学文创作

地址值，否则返回空指针*/ { Blink p; intBno;

Bno=findblock(ST,key); /*调用函数，确定待查记录所在块号*/

p=ST.r[Bno].head; /*取到待查记录所在块链的头指针*/ while (p&&p>key!=key) /*顺着链指针依次查找*/ p=p>next;

return p; /*返回查找结果*/ }

欧阳学文创作