数据结构查找算法课程设计.doc

存档编号： 西安*课程设计说明书设计题目：查找算法性能分析系别：计算机学院专业：计算机科学班级：计科*姓名：王*（共 页）2015年 01月07 日* 计算机科学 专业课程设计任务书姓名：*班级：计科*学号：*一、设计或实践题目查找算法性能分析二、内容及要求设计程序，对比分析顺序查找、折半查找、索引查找、二叉排序树查找和散列查找五种查找算法的性能1、测试数据的个数不少于50个；2、对每一种查找算法设计实现适应的存储结构；3、输出每种查找算法的查找成功时的平均长度三、完成形式1、设计报告；2、源程序四、系（部）审核意见指导教师：*发题日期：2015-01-05完成日期：2015-01-09一 需求分析1. 1问题描述查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对表做修改运算（插入或删除），则相应的表成为动态查找表，反之称为静态查找表。由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（也叫平均查找长度）作为一个查找算法效率优劣的标准。平均查找程度ASL定义为： ASL=PiCi（i从1到n）其中Pi代表查找第i个元素的概率，一般认为每个元素的查找概率相等，Ci代表找到第i个元素所需要比较的次数。查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找（又叫哈希查找），它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找则需要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。1. 2基本要求（1） 输入的形式和输入值的范围；在设计查找算法性能分析的过程中，我们调用产生随机数函数： srand(int)time(0);产生N个随机数。注：折半查找中需要对产生的随机数进行排序，需要进行排序后再进行输入，N50;（2） 输出形式；查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找长度的公式： ASL=PiCi（i从1到n）输出各种查找算法的平均查找长度。注：平均查找长度=总的平均查找长度/N；（3） 程序所能达到的功能通过输出几种查找算法的ASL，我们很显然能得在数据量较小时（Nk，则中点值之后的数都大于k，所以k值在该表的左边，所以确定一个新的查找区间； 如果中点值n）的连续内存单元，以线性表中的每个对象Ki为自变量，通过h（k）把Ki映射为内存单元的地址，并把该对象存储字这个内存单元中。哈希函数的构造有直接定址法、除留余数法和数字分析法，常用的是除留余数法，它是用关键字k除以某个不大于哈希表长度m的数p，将所得到的余数作为哈希地址。除留余数法的哈希函数h（k）： H（k）=K mod P（mod为取余运算，p=m）2、 程序模块顺序查找：int SeqSearch(SeqList R,int n,KeyType k) /*函数的返回值是整型，有三个参数分别是顺序表SeqList、元素个数n和需要查找的关键字k*/int i=0;while (i=n) /*未找到返回0/*return 0;elsereturn i+1; /*找到时返回逻辑符号i+1*/折半查找：int BinSearch(SeqList R,int n,KeyType k)/*函数的返回值是整型，有三个参数分别是顺序表SeqList、元素个数n和需要查找的关键字*/int low=0,high=n-1,mid;int count=0;while(lowk) /*继续在R【lowmid-1】中查找*/high=mid-1;else /* 继续在R【mid+1high】中查找*/return count+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=k)high=mid-1;elselow=mid+1;/* 应在索引表的high+1中，再在对应的线性表中进行顺序查找*/i=Ihigh+1.link;while(i=Ihigh+1.link+s-1&Ri.key!=k)if(ikey=k) /*递归的终结条件*/return 1;if(k key) return SearchBST(bt-lchild ,k) + 1; /*在左子树中的递归查找*/elsereturn SearchBST(bt-rchild ,k) + 1; /*在右子树中的递归查找*/int SearchHT(HashTable ha,int p,KeyType k) /*哈希查找的返回值是整型有三个参数，分别是哈希表ha、小于哈希表长度的最小素数p和关键字k*/ int i=0,adr=0;int m=50;adr =k%p;while (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、 各模块之间的调用关系以及算法设计函数的调用关系图：MainSeqSearchBinSearchIdxSearchSearchHTSearchBSTCreateHTInsertHTCreateBSTInsertBST在主函数中需要定义一个SeqList R的顺序表；HashTable ha 哈希表；索引表IDX I。用srand函数（产生随机数）随机产生50个1到100的整数并输出，因为折半查找需要的是顺序表，所以再对产生的50个随机数再进行排序。调用SeqSearch、BinSearch、IdxSearch、SearchHT、SearchBST（CreateBST）。依次进行输出。注意：每次都要给sum重新赋值为零。三 详细设计#include#include#include#define MAXL 100#define MAXI 100#define NULLKEY -1#define DELKEY -2typedef int KeyType;typedef int InfoType;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;typedef structKeyType key;InfoType data;int count;HashTableMAXL;int SeqSearch(SeqList R,int n,KeyType k) /顺序查找int i=0;while(in & Ri.key!=k)i+;return i+1;int BinSearch(SeqList R,int n,KeyType k) /折半查找int low=0,high=n-1,mid,count=0;while(lowk)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=k)high=mid-1;elselow=mid+1;i=Ihigh+1.link;while(i=Ihigh+1.link+s-1&Ri.key!=k)count+;i+;if(i=Ihigh+1.link+s-1)return count+1;else return 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 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;i+;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=0;im;i+)hai.key=NULLKEY;hai.count=0;for(i=0;ikey=k;p-lchild=p-rchild=NULL;return 1;else if(k=p-key)return 0;else if(kkey)return InsertBST(p-lchild,k);elsereturn InsertBST(p-rchild,k);BSTNode *CreateBST(KeyType a,int n) /二叉排序树的创建BSTNode *bt=NULL;int i=0;while (ikey=k)return 1;if(k key) return SearchBST(bt-lchild ,k) + 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;i50;i+)Ri.key=1+(int)(50.0*rand()/(RAND_MAX+1.0);printf(%dt,Ri.key);printf(*n);for(i=0;i50;i+) for(a=i+1;aRa.key)e=Ri.key;Ri.key=Ra.key;Ra.key=e;for(i=0;i50;i+)Ti=Ri.key;for(i=0;i50;i+)sum=sum+SeqSearch(R,50,Ri.key);printf(顺序查找平均查找长度：%6.2fn,sum/50.0);sum=0;for(i=0;i50;i+)sum=sum+BinSearch(R,50,Ri.key);printf(折半查找平均查找长度：%6.2fn,sum/50.0);sum=0;for(i=0;i5;i+)Ii.link=i*10;Ii.key=Ri*10+9.key;for(i=0;i50;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;i50;i+)sum=sum+SearchHT(ha,53,hai.key);printf(哈希表查找平均查找长度：%6.2fn,sum/50.0);sum=0;for(i=0;i50;i+)sum=sum+SearchBST(CreateBST(b,50),bi);printf(二叉树查找平均查找长度：%6.2fn,sum/50.0);四 测试与分析输出结果：结果分析： 由结果显然可以看出，在线性表存储结构中折半查找的效率最高，顺序查找的效率最低，索引查找介于两者之间。在顺序表存储结构、链式存储结构、索引表存储结构和哈希表存储结构中效率最高的是哈希表。还有一种在动态查找时很高效的一种存储结构树表。几种查找的效率依次是：五 总结数据结构总结：为期一周的数据结构课程设计已经过去了，在这次课程设计中我学习到了很多知识，对编程也有了一定的认识。譬如在结构体的使用在大一下学期的C语言课程中我学的不是很清楚，很多问题都没有搞懂，但在数据结构这门课程中我对结构体这一部分有了新的认识；此外还有函数的调用以及函数的参数这方面我也弥补了在大一上学期拉下的课程。当然这学期的数据结构主要讨论的是算法问