武汉理工数据结构课设

1、1问题描述 2设计2. 1存储结构设计2. 2主要算法设计2. 3测试用例设计 3调试报告3. 1调试过程中遇到的问题的解决3. 2对设计和编码的讨论和分析 4经验和体会4.1收获4. 2对算法改进的设想 5附源程序清单和运行结果5. 1源程序代码125. 2运行结果与分析参考文献索引顺序查找1问题描述这个课程设计的题目是“索引顺序查找”，其实就是分块查找是介于顺序查 找和折半查找之间的查找方法。将数据分别放入几个块中，其中块之间是有序的，即前边的最大数小于后边的最小数，块内数据可以是无序的。编写出一个 能进行索引顺序查找的程序，要求能自动建立索引表；对任意待查找的关键字, 若查找成功，给出其

2、关键字比较次数；测试用例自己设计。我的设计思想是建立一个数组用来存放数据，所存放的数据之间是按块有 序的，所以设计之前要想好自己怎样分块。每个数据都只有自己的地址address,每块内都有一个最大值max。比较关键字key时先比较最大值，符合条件后再 进入块内比较。不管所比较的关键字在比较关键字时是不是恰好和最大值相等, 都要进入块再重新比较，并且从相应块的首地址开始比较，然后向后依次比较。 从比较一开始，就会有一个计数关键字count开始计数。因此，分块查找过程需分两步进行。先确定待查记录所在的块（子表），然后在块 中顺序查找。假设给定值key=38,则先将key依次和索引表中各最大关键字进

3、行 比较，因为22<key<48,则关键字为38的记录若存在，必定在第二个子表中， 由于同一索引项中的指针指示第二个子表中的第一个记录是表中第7个记录，则 自第7个记录起进行顺序查找，直到l.data10=key为止。假如此子表中没有关键 字等于key的记录（例如：key=29时自第7个记录起至第12个记录的关键字和key 比较都不等），则查找不成功。索引顺序查找的性能分析：分块查找的平均查找长度为:其中，d为查找索引表确定所在块的平均查找长度zir为在块中查找元素的平均查找长度。若用顺序查找的方法确定所在的块，贝!hv jsbi o ihi£a & o若用折半查

4、找确定所在的块，贝!has%= £»+ =+丄办=扇叫a些罟s u2£2设计2.1存储结构设计这个程序首先用到了2个结构体，typedef struct datatype datamaxsize; int length; list;> typedef structf datatype max;int address;index> 分另u表 示定义索引表、定义块表。其中key表示待查找的索引值；max表示块内索引的 最大值，即为最大关键字，address为块内第一个索引的地址；datasize表示数组所能容纳的最多元素，length表示表内元素的个数。在

5、创建块表时，int intput (list *l, index *index),定义了l为list的引用， index为index的数据成员。先将表的长度l-length定义为0,每输入一个数，表长 度随之加1,然后输入要建的块数，并且输入每个块的首地址。指明每个块的最大 值，以便在下一个函数indexsearch中直接将key与最大值进行比较。在查找时，我定义了 函数int indexsearch(list ljndex index9int lendatatypekey),现将关键字key与每一块的最大<indexi.key进行比较，从第一块开始，依次向 后比较，当计数器i超过块的个

6、数时，返回1;当符合条件ivlen&&key>indeximax时, 进入块进行比较。从当前块的首地址元素开始依次向后比较。无论是比较最大值还是比 较块中元素，比较次数计数器count直在计数。当存在块中元素与关键字相等时，输 出关键字的比较次数conn併且返回当前元素的地址addresso若当前块中没有元素与关 键字相等，返回12.2主要算法设计为了体现程序的简单与高效，我将程序最终到造成了只用两个函数就完成了 主要功能的实现，在函数index中输入所有数据元素与地址和要分的块数，以及 每一块的最大值。在函数indexsearch中实现了关键字的比较，其中包括关键字 与

7、最大元素的比较和响应块中每个元素的比较，直到找到相应元素为止。而且 比较次数与相应元素的地址也在这个函数中体现出来。根据索引顺序査找的原理，得知分块查找需两步进行，要先确定待查所在的 块(子表)，然后在块中顺序查找，所以至少需要两个查找函数。查找块函数可 用折半查找或者顺序查找。一般情况下进行分块查找，可以将长度为n的表均匀地分成b块，每块含有 s个记录，即b= rn/s ；假定表中每个记录的查找概率相等，则每块查找的概率 为1/b,块中每个记录的查找概率为1/so若用顺序查找确定所在块，则分块查找的平均查找长度为aslbs=l/2(n/s+s)+lo可见，此时的平均查找长度不仅和表 长n有关

8、，而且和每一块中的记录个数s有关。在给定n的前提下，s是可以选择的。容易证明，当s取徧时，ass取小值奶+ 1。这个值比顺序查找有了很大改进，但远不及折半查找。若用折半查找确定所在块，则分块查找的平均 查找长度 aslbs 约为 log2(n/s+l)+s/2o虽然通过平均查找长度的比较，对块的查找用折半查找较先进，但我这里的 int indexsearch()函数还是用的一般人较易理解的顺序查找。这里用到的是顺序 查找，若key值小于或等于第一块的最大关键字indexl.max,则key值可能在 第一块中；若key值大于最后一块的最大关键字indexlen.max,则key值必定 不在任何一

9、个块中，查找失败；若key值大于前一块的最大关键字，小于或等 于后一块的最大关键字，则key值肯能在后一块中。这样就能确定key值所在 的块了。通过我的思考，我觉得顺序查找较简单些，所以在程序中就用了顺序 查找。再者是在块中查找关键字用到的int indexsearch ()函数，由于块中的元素是 无序排列，所以只能用顺序查找。l->data是通过所查到的块中的元素建立的 数组，再通过把每个块中的元素依次和key值做比较，就可查到是否存在key 这个元素。若从该块的第一个元素查到最后一个元素都没有找到与key相等的 值，则查找失败，这个是根据该块的长度(块中元素的个数)控制的。若找到 与

10、kty相等的值，就返回该元素所在的位置。2.3测试用例设计1 对创建表的函数int input(),通过手动输入所有元素(按块有序进行输入，以0 为结束输入的标志)和块数，如输入一些简单易操作的数32 16549870 2然后输入每块的首地址以及每块的最大值，这样就将块确定了下来。如：输入要建立的3个块表，每个块表的最大关键字和首地址分别是：3, 0； 6, 3； 9, 6。得到的结果为:index0.max=3 indexleinax=6 index2<max=9index o.address=o index l.address=3 index 2>address=63 对查找关

11、字所在的块以及对比找到确切位置的函数int indexsearch()通过对要查找的key值分别与每一块的最大关键字进行比较，得出key值可 能位于哪一块中。如i：当key=5时，先与第一块最大关键字进行比较，key>index0.max=3, 再与第二块最头关键字进行比较，key<index2.max=6,所以5可能在第二块中, 返回第二块的首地址；然后比较key<l.datao,所以再与下一个元素比较，有 key=l.datal,所以可以确定在第二块第二个位置，比较次数为4次。当key=12时，先与第一块最大关键字进行比较，key>index0.max=3；再 进行

12、比较，key>index2.max=9,所以12不可能位于这些块表中，查找失败, 则不再需要进入块中进行比较。与第二块最大关键字进行比较,key>indexl.max=6；再与第三块最大关键字3调试报告3.1调试过程中遇到的问题的解决1 对存放元素的数组的大小定义一开始过小，导致我后来存放的元素超出了数组 空间，产生溢出，于是我将数组大小改为100,问题得以解决2对创建索引顺序表的函数int input()这个函数还算简单，在此函数中我同时实现了表中元素的输入，每块的首地 址以及块内最大值，当时设计的时候没有使表的首地址和块的首地址做到统一, 在建立完函数时我将它们的首地址统一设置

13、成0,这样元素的名义地址为i,实 际地址为i+1.3对于搜索函数indexsearch出现的错误虽然不多，但是很严重，而且在当时按 我当的初设计思路来改很难改。从一开始设计搜索函数时，我考虑的太多，想 实现这个函数的“智能化”：在比较最大值时，我考虑了 key是不是恰好是某一 块的最大值，这样将不再进入块中进行比较，而且考虑到这一点我在块中搜索 时，是从后往前搜索的，即搜索的初值我设计为j=indexi+l.address-l,h这样 当key在最后一块时，上边的这一公式却不能再用，只能另外处理。而且在当 初计算比较次数时由于这样设计的比较繁琐，我忘记了对比较块最后一个值时 对计数器加1。由于

14、对搜索函数的数次盲目改动都以失败告终，我最后用了一种简单的思 路进行比较，即先比较每块的最大值，如果没有直接返回1,不再进入块；若有 符合条件得块，则直接进入此块，并且不管最大值是否就是key,都从首地址再 次重新进行比较。这样计数器在查找块时和在块内查找时都在计数。在计数时由于程序自身的缺陷，在比较找到符合条件的块以及在块中寻找 都符合条件的元素时，计数器都不会对最后一次的比较加1,因为在比较时我使 用的是while循环语句，这样当条件符合时，就不会再进入下边的结构对计数器 加1 所以我在当每次查找成功后都会再对计数器加1 这样就保证了计数器的值 就是真正的比较的次数。现在想想我当初设计搜索

15、函数时之所以出现那种负责的比较，只是因为我 在潜意识里将块的最大值和块的最后一个值给混淆了，这也是为什么我当初按 大小顺序输入元素得到的比较次数并没有错的原因。而当我按照混乱的顺序输 入元素时就出错了。4对主函数main()在最初自己电脑上调试时没有出现错误，但是到了实验室里出现了跳屏现 象，即结果输出来的时候窗口随之就关闭了，在老师加入两个getcharo后，问 题得到解决。3.2对设计和编码的讨论和分析我觉得我的程序非常简便，绝对体现了程序的高效性和简单性，我看过其他 类似的程序但都显得过分冗杂，程序非常长，看起来很复杂，但是最终实现的 主要的还是那两个函数，我的函数之所以只有两个，是因为

16、我的操作都隐含在 这两个函数中了，函数虽少，功能不少，充分借助了函数内的数据，这让我可 以从一开始的冗杂到现在的简单。4经验和体会4.1收获通过这次课程设计，我对索引顺序查找有了更加深入的了解，我基本学会了 用索引顺序查找来解决类似的查找问题。虽然在程序的编译过程中遇到了不少 问题，但是我通过查资料，跟同学讨论等方式，把问题都逐步的解决了。所以, 在这次的实践中，我也学到了不少解决问题的方法，让我获益匪浅。我希望以 后老师能多给我们安排一些类似的课程设计，我认为通过我们的自主设计，自 主思考，不仅能提高我们的专业技能，而且能提高我们自主解决问题的能力， 使我们获得了更多在平时学不到的知识。这同

17、时也是一种经验，为以后的工作 奠定了一定的基础。4.2对算法改进的设想我的搜索函数indexsearch无论怎么改都有自身的局限性，这也我我本身的设计 思路有关，而且关键问题在while循环上，我在查找块成功进入块内查找时，对 于前几个块的查找都没问题只是到了最后一个，因为我的while循环语句是wh订e(j<=(indexi+l.address)&&key!=l.data|jj),这样导致若关字在最后一块时，产生错误，因为没有indexi+l.addresso这样我不得不将语改为(j<=(indexi.address+2)&&key!=l.data

18、j),这样改是因为我一开始测试时所使用的块 长是3,虽然这样该解决了最后一块的问题，但是也就产生了局限性，使每块的个数被固定了。这也有解决办法，就是设将 indexi.address+2 改为indexi.address+x,这样每块的个数就可以随意变动了。由于时间关系，我并未将其改动，但我相信改动后一定会产生期望的效果的。5附源程序清单和运行结果5.1源程序代码#include nstdio.hn#define maxsize 100 typedef int datatype;typedef structdatatype datafmaxsize; int length;list;typed

19、ef structdatatype max;int address;index;int intpul(list *l,index * index)datatype x,y;int i,j;l->length=o;printf("输入表，以'o'结束nnh);scanf(“d”,&x);while(x!=0)l->datal->length=x;l->length+; scanf(h%dh,&x);printf(nn输入块的长度:”);scanf(” d”,&y);printf(nn输入每一块的地址：”)； for(i=0

20、;i<y;i+)scanf(”d”,&x); indexij.address=x;printf("n输入每一块的最大值:”);for(j=0;j<y;j+)scanf(”d”,&x); indexj.max=x;return y;int indexsearch(list l,index indexjnt len,datatype key) int i=0,count=0,j;while(i<le n&&key>indexi.max) i4-+;count+; if(i>=len)returnelsecount+;while

21、(j<=indexi.address+2&&key!=l.dataj)j+;count+;if(j>indexi.address+2)return -1;else count+; printf(nn 搜索次数是:%dh,count); return j;int main()list l;index indexmaxsizej;int x,y,m;intlen;len=intput(&l，index); printf(mn输入关键字:”); scanf(,'n%d",&x);y=indexsearch(l,index jen,x);if(y=-l)printf(,n 没有 %du,x); else printf("n地址:%d",y+l );printf(nn是否还要继续？若是，请按1： h); scanf(,n%d",&m);while(m=l)printf(nn输入关键字