索引顺序查找

《索引顺序查找》由会员分享，可在线阅读，更多相关《索引顺序查找（9页珍藏版）》请在装配图网上搜索。

1、课程设计：索引顺序查找1问题描述试编写索引顺序查找的程序。（1）要求能自动建立索引表；（2）对任意待查找的关键字，若查找成功，给出其关键字比较次数。2 设计1、 33 66 990 5 101018332883850606642705983997801234567891011121314 索引顺序查找的索引存储表示的图例2、态查找的典型关键字类型说明过程： Typedef float KeyType;/实型Typedef int KeyType ; /整型Typedef char *keytype;/字符串型数据元素定义为：typedef structkeytype key; /关键字域 /其

2、他域ElemType;3.抽象数据类型静态查找表的定义为：ADT StaticSearchTable数据对象 D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系：数据元素问题同属一个集合。基本操作p： Create(&T,n); 操作结果：构造一个含有n个数据元素的静态查找表ST。 Destroy(&ST): 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search(ST,key); 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。 操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的

3、的位置，否则为“空”。 Traverse(ST,Visit(); 初始条件：在静态查找ST存在，Visit是对元素操作的应用函数。 操作结果：按某种次序对ST的每个元素调用函数visit（）一次且仅一次。一旦visit（）失败，则操作失败。ADT StaticSearchTable4、索引表的数据类型定义：#define MaxIndex /根据实际情况而定 typedef structKeyType key;Int link;IdxType5、主程序：main()初始化；for 接受命令； 处理命令；6、各模块之间的调用关系如下：主程序模块 随机函数模块 索引顺序查找模块7、详细算法设计：（

4、1）、随机数算法如下：void init() int i,k,m,j,m1; len=(int)sqrt(n); n1=n-len*(len-1); cout系统将自动产生n60)&(m70) a00=m; break; for(j=1;jlen;j+) m1=m-abs(rand()%60); a0j=m1; m=m+40+abs(rand()%80); for(i=1;ilen-1;i+) ai0=m; for(j=1;jlen;j+) m1=m-abs(rand()%60); aij=m1; m=m+40+abs(rand()%80); alen-10=m; for(j=1;jn1;j+

5、) m1=m-abs(rand()%60); alen-1j=m1; print(); (2)、查找算法如下：#define MaxIndex /应根据实际确定typedef structKeyType key;Int link;IdxType;int IdxSearch(Seqlist A,Index,int b,keyType K,int n) /分块查找关键字为k的记录，索引表为index0.b-1int low=0,high=b-1,mid,I;int s=n/b;while(low=high) /在索引表中查找mid=(low+high)/2;if(indexmid.keyk) lo

6、w=mid+!Else high=mid-1;if (lowb) /在顺序表中查找for(I=indexlow.link;I=indexlow.link+s-1 & In;I+)if(AI.key=k) return I;return 1;return 1:8、程序基本操作说明：int IdxSearch(Seqlist A,Index,int b,keyType K,int n)/索引顺序查找关键字K的记录，索引表为Index0b-1void Bubble_Sort(RecType R,int n)/用来实现冒泡排序void CreateIndexList(MainList&A,IndexL

7、ist&B,int n,int m) /根据从键盘输入的数据建立索引存储的主表和索引表，每个子表采用静态链接存储，n和m分别给出主表和索引表的最大长度3 调试报告调试过程中，随机函数不能正确产生随机数字，运行的时候运行两次就会产生编译错误，要运行一次就要编译一次，第一次运行的时候出现一个警告，再编译一次就会提示没错误通过，D:学习软件程序epandaypanda.cpp(22) : error C2065: n : undeclared identifierD:学习软件程序epandaypanda.cpp(22) : error C2448: : function-style initiali

8、zer appears to be a function definitionD:学习软件程序epandaypanda.cpp(90) : error C2065: init : undeclared identifier执行 cl.exe 时出错.4结束语， 这次实验让我深刻体会到编写程序的痛苦啊！编译错误让我无从下手去改正，想来想去总找不到最合适的方法，程序中稍微又点考虑不周就会再运行中出现错误出现死循环甚至死机，在这次课程设计中我设计的程序大多时候是处于死机状态，在朋友的帮助下我完成了这个艰难的任务，但是现在这个程序还是又很多缺陷。想随机数字的产生至今仍没得到解决， 程序查找数的时间过长

9、等等一系列等待解决的问题需要去探讨解决。在函数调用过程中也出现很多麻烦。经过这次课程实验设计让我明白了几点：1、 程序编写过程中，要及时加商注释，在这次程序中我没又很好的做到这点，致使我今天写的程序明天就看不懂了。2、 程序已经改动注释也要改动否则注释只会起到反作用。3、 程序编写要有自己简单实用的风格，便于自己阅读和检查。 附录F1 源代码#include#include#include int n,len,n1,count,kk; int a10100;typedef structKeyType key;Int link;IdxType; void print() int i,j; cou

10、t系统自动生成的索引表如下n; for(i=0;ilen-1;i+) for(j=0;jlen;j+) coutaij ; coutendl; for(j=0;jn1;j+) coutalen-1j ; coutendl; void init() int i,k,m,j,m1; len=(int)sqrt(n); n1=n-len*(len-1); cout系统将自动产生n60)&(m70) a00=m; break; for(j=1;jlen;j+) m1=m-abs(rand()%60); a0j=m1; m=m+40+abs(rand()%80); for(i=1;ilen-1;i+)

11、ai0=m; for(j=1;jlen;j+) m1=m-abs(rand()%60); aij=m1; m=m+40+abs(rand()%80); alen-10=m; for(j=1;jn1;j+) m1=m-abs(rand()%60); alen-1j=m1; print(); int IdxSearch(Seqlist A,Index,int b,keyType K,int n) int low=0,high=b-1,mid,I;int s=n/b;while(low=high) mid=(low+high)/2;if(indexmid.keyk) low=mid+!Else hi

12、gh=mid-1;if (lowb) for(I=indexlow.link;I=indexlow.link+s-1 & In;I+)if(AI.key=k) return I;return 1;return 1: void sort(int i) int j; if (ilen-1) for(j=0;jlen;j+) if (aij=kk) count+; cout次数countendl; exit(0); else count+; if (i=len-1) for(j=0;in1;i+) if (aij=kk) cout次数countendl;exit(0);else count+; cout没有找到!; void find() int i,j; coutkk; coutendl; count=0; for (i=0;ilen-1;i+)if (ai0kk) count+; sort(i+1); else count+; void main() coutn; init(); find();F2 运行结果：表中找不的结果：查找倒的结果：