数据结构查找算法课程设计报告书

1、|西安 *课程设计说明书设计题目：查找算法性能分析系别：计算机学院专业：计算机科学班级：计科*姓名：王*（共页）2015年01月07日*计算机科学 专业课程设计任务书姓名： *班级： 计科*学号： *一、设计或实践题目查找算法性能分析二、内容及要求设计程序，对比分析顺序查找、折半查找、索引查找、二叉排序树查找和散列查找 五种查找算法的性能1、测试数据的个数不少于 50个；2、对每一种查找算法设计实现适应的存储结构；3、输出每种查找算法的查找成功时的平均长度三、完成形式1、设计报告;2、源程序四、系（部）审核意见指导教师： *发题日期： 2015-01-05完成日期： 2015-01-09需求分

2、析1. 1 问题描述查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是 一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行 称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对 表做修改运算(插入或删除) ，则相应的表成为动态查找表，反之称为静态查找 表。由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键 字的平均比较次数(也叫平均查找长度)作为一个查找算法效率优劣的标准。 平均查找程度 ASL 定义为：ASL=刀 PiCi (i 从 1 到 n)其中 Pi 代表查找第 i 个元素的概率，一般认为每个元素的查找概率相等， Ci 代表

3、找到第 i 个元素所需要比较的次数。查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找(又叫哈 希查找)，它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中 对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折 半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找 则需要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。1. 2 基本要求(1) 输入的形式和输入值的范围；在设计查找算法性能分析的过程中，我们调用产生随机数函数： srand(int)time(0);产生N个随机数。注：折半查找中需要对产生的随机数进行排序，

4、需要进行排序后再进行输入， N<50;( 2 ) 输出形式；查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找 长度的公式：ASL= 刀 PiCi (i 从 1 到 n) 输出各种查找算法的平均查找长度。注：平均查找长度 =总的平均查找长度 /N ；(3) 程序所能达到的功能通过输出几种查找算法的 ASL,我们很显然能得在数据量较小时(N100)我们在实现静态查找时应该选择如何调用哪种查找算法。二 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间 的层次(调用 )关系。1、数据结构顺序查找 ：在进行顺序查找顺序表类型定时需要定义 typedef

5、 int KeyType ； 顺序表类型为 SeqList 类型。 typedef NodeType SeqList【MaxSize】；/它的基本思路是：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，查找成功。折半查找：在进行顺序查找顺序表类型定时需要定义typedef int KeyType，并且需要调用排序函数对其进行排序。折半查找类型为 SeqList 类型。 typedef NodeType SeqList【MaxSize】；折半查找又叫二分查找，效率较高，但折半查找要求被查找的表示顺序表，它的基本思路是：设 R【low.high】

6、是当前的查找区间，首先确定该区间的中 点位置mid= L (low+high ) /2，然后将待查的 k值与R【mid】.key。 如果中点值的值是 k,返回该元素的逻辑符号； 如果中点值k，则中点值之后的数都大于k，所以k值在该表的左边，所以确定一个新的查找区间； 如果中点值k，则中点值之后的数都小于k, k值在该表的右边，再在 依次循环。索引查找：/索引存储结构是在存储数据的同时还建立附加的索引表，索引表包括关键字和地址。索引表的数据类型 KeyType key、int link ，link 代表对应 块的起始下标。typedef IdxType IDXMaxSize /索引表的类型分块查

7、找又称索引顺序查找，它的性能介于顺序查找和折半查找之间的一种算法，它的分块的思想是： 将表均分成b块，前b-1块中的关键字个数为 s=厂n/b n； 每一块的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字； 取各块中最大的关键字及该块在R中的起始位置。注：索引表是一个递增有序表分块查找的基本思路是： 首先查找索引表，因为索引表是有序表，所以可以采用折半查找或者 顺序查找，来确定待查元素在哪一块； 再已确定的块中进行顺序查找（因为块内元素无序，所以只能用顺序 查找）列：设有一个线性表采用顺序存储，有20个元素，将其分成 4 （b=4）部分，每部分有5个元素（s=5）,该索引

8、表的存储结构如下图所示：I08114I2639014410r>>53452210666341585718Li nkKey81993110401138125413661446157116781780188519100在如图所示的存储结构中， 查找关键字k=80时，首先将k和索引表中个关键字比较， 直到找到大于等于 k的值，因此若关键字 k=80存在则必定在第四块中，由IDX3ink找到起始地址15,从该地址开始在 R【1519】中进行查找，直到找到关R【8 .key=k为止，如果查找不成功说明不存在关键字k=80。二叉树查找：线性表可以有三种查找法，其中折半查找的效率最高，但是折半查

9、找要求元素 时顺序表，而且不能用链式存储结构，因此有表的插入或删除操作时，需要移动大 量元素，这时候二叉树查找的优势就体现出来了。即动态查找时就需要用到链式存 储结构。二叉排序树（BST又称二叉查找树，其定义为：二叉排序树或者是空树，或者是满 足如下性质的二叉树： 若它的左孩子非空，则左子树上的所有元素的值均小于根元素的值； 若它的右孩子非空，则左子树上的所有元素的值均大于根元素的值； 左右子树本身是一颗二叉树。重要性质：中序遍历二叉排序树所得到中序序列是以一个递增有序序列。 二叉排序树算法思想：它可以看做是一个有序表，所以在二叉树上查找，和折半查 找类似，也是一个逐步缩小查找范围的过程，运用

10、递归查找算法SearchBST()。哈希表查找：在用哈希表查找时先建立一个哈希表，哈希表主要用于快速查找，哈希表的查 找过程和建表过程类似。它的算法是： 设给定的值为k，根据建表时设定的散列函数h (k)计算哈希地址； 存储的个数为 n,设置一个长度为M( M>r)的连续内存单元，以线性表中的每个对象 Ki为自变量，通过 h(k)把Ki映射为内存单元的地址，并把 该对象存储字这个内存单元中。哈希函数的构造有直接定址法、除留余数法和数字分析法,常用的是除留余数法，它是用关键字 k除以某个不大于哈希表长度m的数p，将所得到的余数作为哈希地址。除留余数法的哈希函数 h(k)：H( k)=K m

11、od P ( mod为取余运算，p<=m)2、程序模块顺序查找：int SeqSearch(SeqList R,int n,KeyType k) /*函数的返回值是整型，有三个参数分别是顺序表 SeqList 、元素个数 n 和需要查找的关键字 k*/int i=0;while (i<n && Ri.key!=k) /*从表头开始找 */i+;if(i>=n) /* 未找到返回 0/*return 0;elsereturn i+1; /* 找到时返回逻辑符号 i+1*/折半查找 ：int BinSearch(SeqList R,int n,KeyType k)

12、/*函数的返回值是整型，有三个参数分别是顺序表 SeqList 、元素个数 n 和需要查找的关键字 */int low=0,high=n-1,mid;int count=0;while(low<=high) /*当前区域存在元素时循环 */count+; /*每循环一次 count+*/mid=(low+high)/2;if(Rmid.key=k)/*如果查找成功返回其逻辑序号 mid+1*/return mid+1;if(Rmid.key>k) /*继续在R【lowmid-1】中查找*/elsehigh=mid-1;/*继续在R【mid+1high】中查找*/return cou

13、nt+1; /*返回的是总的平均查找长度 */索引查找 ：int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /*索引查找函数值返回的是整型，函数有五个参数，分别是索引表 I、分的块数b、顺序表R、 关键字个数和关键字 */int low=0,high=b-1,mid,i,count=0;int s=n/b; /*s为每块的元素个数，应为 n/b 的向上取整 */while(low<=high) /* 索引表中进行折半查找、找到的位置为 high+1*/count+;mid=(low+high)/2;if(Imid.key>=k

14、) high=mid-1;elselow=mid+1;/* 应在索引表的 high+1 中，再在对应的线性表中进行顺序查找 */ i=Ihigh+1.link;while(i<=Ihigh+1.link+s-1&&Ri.key!=k)if(i<=Ihigh+1.link+s-1) /* 查找成功 */i+; count+;return count+1;int SearchBST(BSTNode *bt,KeyType k) /* 二叉排序树查找函数的返回值是BSTNode类型，函数有两个参数分别是二叉排序树bt和关键字k*/ if(bt=NULL|bt->ke

15、y=k) /* 递归的终结条件 */return 1;if(k < bt->key) return SearchBST(bt->lchild ,k) + 1; /*在左子树中的递归查找*/在右子树中的递归查elsereturn SearchBST(bt->rchild ,k) + 1;/*找*/int SearchHT(HashTable ha,i nt p,KeyType k) /*哈希查找的返回值是整型有三个参数，分别是哈希表 ha、小于哈希表长度的最小素数p和关键字k*/int i=O,adr=O;int m=50;adr =k%p;采用线性探查法查while (

16、haadr.key!=NULLKEY && haadr.key!=k) /*找下一个地址*/i+;adr =(adr+1)%m; /*adr=( adr+1) mod m*/if(haadr.key=k)return i+1;/*查找成功 */elsereturn -1;/*查找失败 */3、各模块之间的调用关系以及算法设计函数的调用关系图:Mai nV V V V VSeqSearchBin SearchIdxSearchSearchHTSearchBST*CreateHTInsertHTCreateBSTInsertBST在主函数中需要定义一个SeqList R的顺序表；H

17、ashTable ha 哈希表；索引表IDXI。用srand函数(产生随机数)随机产生50个1到100的整数并输出，因为折半查找需要的是顺序表，所以再对产生的50个随机数再进行排序。调用SeqSearch、Bin Search、IdxSearch、SearchHT、SearchBST( CreateBST )。依次进行输出。注意：每次都要给 sum重新赋值为零。三详细设计#in clude<stdlib.h>#in clude<stdio.h>#in clude<time.h>#defi ne MAXL 100#defi ne MAXI 100#defi n

18、e NULLKEY -1#defi ne DELKEY -2 typedef int KeyType; typedef int In foType;typedef structKeyType key;int link;IdxType;typedef IdxType IDXMAXI;typedef structKeyType key;InfoType data;NodeType;typedef NodeType SeqListMAXL;typedef struct nodeKeyType key;InfoType data;struct node *lchild,*rchild;BSTNode;

19、typedef struct KeyType key;InfoType data;int count;HashTableMAXL;顺序查找int SeqSearch(SeqList R,int n,KeyType k) / int i=0;while(i<n && Ri.key!=k)折半查找索引查找return i+1;int BinSearch(SeqList R,int n,KeyType k) /int low=0,high=n-1,mid,count=0;while(low<=high)count+;mid=(low+high)/2;if(Rmid.key

20、=k)return count+1;if(Rmid.key>k)high=mid-1;elselow=mid+1;return 0;int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /int low=0,high=b-1,mid,i;int count=0;int s=n/b;while(low<=high)count+;mid=(low+high)/2;if(Imid.key>=k)high=mid-1;elselow=mid+1;i=Ihigh+1.link;while(i<=Ihigh+1.link+s-1&

21、amp;&Ri.key!=k)count+;i+;if(i<=Ihigh+1.link+s-1)return count+1;elsereturn 0;散列查找int SearchHT(HashTable ha,int p,KeyType k) /int i=0,adr=0;int m=50;adr =k%p;while (haadr.key!=NULLKEY && haadr.key!=k)i+;adr =(adr+1)%m;if(haadr.key=k)return i+1;elsereturn -1;哈希表的插入void InsertHT(HashTable

22、 ha,int &n,KeyType k,int p) /int i,adr;adr=k%p;if(haadr.key=NULLKEY|haadr.key=DELKEY)haadr.key=k;haadr.count=1;elsei=1;doadr=(adr+1)%p;while(haadr.key!=NULLKEY&&haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;哈希表的创void CreateHT(HashTable ha,KeyType x,int n,int m,int p) /建int i,n1=0;for(i

23、=0;i<m;i+)hai.key=NULLKEY;hai.count=0;for(i=0;i<n;i+)InsertHT(ha,n1,xi,p);int InsertBST(BSTNode * &p,KeyType k) / 二叉排序树的插入if(p=NULL)p=(BSTNode *)malloc(sizeof(BSTNode);p->key=k;二叉排序树的创建二叉排序树查找p->lchild=p->rchild=NULL;return 1;else if(k=p->key)return 0;else if(k<p->key)ret

24、urn InsertBST(p->lchild,k);elsereturn InsertBST(p->rchild,k);BSTNode *CreateBST(KeyType a,int n) /BSTNode *bt=NULL;int i=0;while (i<n)InsertBST(bt,ai);i+;return bt;int SearchBST(BSTNode *bt,KeyType k) /if(bt=NULL|bt->key=k) return 1;if(k < bt->key)return SearchBST(bt->lchild ,k)

25、 + 1;elsereturn SearchBST(bt->rchild ,k) + 1;void main()SeqList R;int i;int e;int a;int b;HashTable ha;int T50;IDX I;double j,k,m,n,sum=0;srand(int)time(0);for(i=0;i<50;i+)Ri.key=1+(int)(50.0*rand()/(RAND_MAX+1.0);printf("%dt",Ri.key);*n");for(i=0;i<50;i+) for(a=i+1;a<50;a

26、+) if(Ri.key>Ra.key) e=Ri.key;Ri.key=Ra.key;Ra.key=e;for(i=0;i<50;i+)Ti=Ri.key;for(i=0;i<50;i+)sum=sum+SeqSearch(R,50,Ri.key);printf(" 顺序查找平均查找长度： %6.2fn",sum/50.0); sum=0;for(i=0;i<50;i+)sum=sum+BinSearch(R,50,Ri.key);printf(" 折半查找平均查找长度： %6.2fn",sum/50.0);sum=0;for(

27、i=0;i<5;i+)Ii.link=i*10;Ii.key=Ri*10+9.key;for(i=0;i<50;i+)sum=sum+IdxSearch(I,5,R,50,Ri.key);printf(" 索引查找平均查找长度： %6.2fn",sum/50.0);sum=0;CreateHT(ha,b,50,53,53);for(i=0;i<50;i+)sum=sum+SearchHT(ha,53,hai.key);printf(" 哈希表查找平均查找长度： %6.2fn",sum/50.0); sum=0;for(i=0;i<50;i+)sum=sum+SearchBST(CreateBST(b,50),bi);printf（" 二叉树查找平均查找长度： %6.2fn",sum/50.0）;四 测试与分析输出结果： 结果分析：由结果显然可以看出，在线性表存储结构中折半查找的效率最高，顺序查找的 效率最低，索引查找介于两者之间