数据结构查找算法课程设计.docx
- 文档编号:11266036
- 上传时间:2023-05-30
- 格式:DOCX
- 页数:18
- 大小:52.41KB
数据结构查找算法课程设计.docx
《数据结构查找算法课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构查找算法课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构查找算法课程设计
西安********
课程设计说明书
设计题目:
查找算法性能分析
系别:
计算机学院
专业:
计算机科学
班级:
计科***
姓名:
王***
(共页)
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个随机数。
注:
折半查找中需要对产生的随机数进行排序,需要进行排序后再进行输入,N<50;
(2)输出形式;
查找算法分析过程中,只要对查找算法稍作修改就可以利用平均查找长度的公式:
ASL=∑PiCi(i从1到n)
输出各种查找算法的平均查找长度。
注:
平均查找长度=总的平均查找长度/N;
(3)程序所能达到的功能
通过输出几种查找算法的ASL,我们很显然能得在数据量较小时(N<100)我们在实现静态查找时应该选择如何调用哪种查找算法。
二概要设计
说明本程序中用到的所有抽象数据类型的定义。
主程序的流程以及各程序模块之间的层次(调用)关系。
1、数据结构
顺序查找:
在进行顺序查找顺序表类型定时需要定义typedefintKeyType;
顺序表类型为SeqList类型。
typedefNodeTypeSeqList【MaxSize】;/
它的基本思路是:
从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,查找成功。
折半查找:
在进行顺序查找顺序表类型定时需要定义typedefintKeyType,并且需要调用排序函数对其进行排序。
折半查找类型为SeqList类型。
typedefNodeTypeSeqList【MaxSize】;
折半查找又叫二分查找,效率较高,但折半查找要求被查找的表示顺序表,它的基本思路是:
设R【low…..high】是当前的查找区间,首先确定该区间的中点位置mid=┖(low+high)/2┘,然后将待查的k值与R【mid】.key。
1如果中点值的值是k,返回该元素的逻辑符号;
2如果中点值>k,则中点值之后的数都大于k,所以k值在该表的左边,所以确定一个新的查找区间;
3如果中点值 4依次循环。 索引查找: /索引存储结构是在存储数据的同时还建立附加的索引表,索引表包括关键字和地址。 索引表的数据类型KeyTypekey、intlink,link代表对应块的起始下标。 typedefIdxTypeIDX[MaxSize] ink找到起始地址15,从该地址开始在R【15…19】中进行查找,直到找到关R【8】.key=k为止,如果查找不成功说明不存在关键字k=80。 二叉树查找: 线性表可以有三种查找法,其中折半查找的效率最高,但是折半查找要求元素时顺序表,而且不能用链式存储结构,因此有表的插入或删除操作时,需要移动大量元素,这时候二叉树查找的优势就体现出来了。 即动态查找时就需要用到链式存储结构。 二叉排序树(BST)又称二叉查找树,其定义为: 二叉排序树或者是空树,或者是满足如下性质的二叉树: 1若它的左孩子非空,则左子树上的所有元素的值均小于根元素的值; 2若它的右孩子非空,则左子树上的所有元素的值均大于根元素的值; 3左右子树本身是一颗二叉树。 重要性质: 中序遍历二叉排序树所得到中序序列是以一个递增有序序列。 二叉排序树算法思想: 它可以看做是一个有序表,所以在二叉树上查找,和折半查找类似,也是一个逐步缩小查找范围的过程,运用递归查找算法SearchBST()。 哈希表查找: 在用哈希表查找时先建立一个哈希表,哈希表主要用于快速查找,哈希表的查找过程和建表过程类似。 它的算法是: 1设给定的值为k,根据建表时设定的散列函数h(k)计算哈希地址; 2存储的个数为n,设置一个长度为M(M>n)的连续内存单元,以线性表中的每个对象Ki为自变量,通过h(k)把Ki映射为内存单元的地址,并把该对象存储字这个内存单元中。 哈希函数的构造有直接定址法、除留余数法和数字分析法,常用的是除留余数法,它是用关键字k除以某个不大于哈希表长度m的数p,将所得到的余数作为哈希地址。 除留余数法的哈希函数h(k): H(k)=KmodP(mod为取余运算,p<=m) 2、程序模块 顺序查找: intSeqSearch(SeqListR,intn,KeyTypek)/*函数的返回值是整型,有三个参数分别是顺序表SeqList、元素个数n和需要查找的关键字k*/ { inti=0; while(i =k)/*从表头开始找*/ i++; if(i>=n)/*未找到返回0/* return0; else returni+1;/*找到时返回逻辑符号i+1*/ } 折半查找: intBinSearch(SeqListR,intn,KeyTypek)/*函数的返回值是整型,有三个参数分别是顺序表SeqList、元素个数n和需要查找的关键字*/ { intlow=0,high=n-1,mid; intcount=0; while(low<=high)/*当前区域存在元素时循环*/ { count++;/*每循环一次count++*/ mid=(low+high)/2; if(R[mid].key==k)/*如果查找成功返回其逻辑序号mid+1*/ returnmid+1; if(R[mid].key>k)/*继续在R【low…mid-1】中查找*/ high=mid-1; else/*继续在R【mid+1…high】中查找*/ returncount+1;/*返回的是总的平均查找长度*/ } } 索引查找: intIdxSearch(IDXI,intb,SeqListR,intn,KeyTypek)/*索引查找函数值返回的是整型,函数有五个参数,分别是索引表I、分的块数b、顺序表R、关键字个数和关键字*/ { intlow=0,high=b-1,mid,i,count=0; ints=n/b;/*s为每块的元素个数,应为n/b的向上取整*/ while(low<=high)/*索引表中进行折半查找、找到的位置为high+1*/ { count++; mid=(low+high)/2; if(I[mid].key>=k) high=mid-1; else low=mid+1; } /*应在索引表的high+1中,再在对应的线性表中进行顺序查找*/ i=I[high+1].link; while(i<=I[high+1].link+s-1&&R[i].key! =k) if(i<=I[high+1].link+s-1)/*查找成功*/ { i++; count++; } returncount+1; } intSearchBST(BSTNode*bt,KeyTypek)/*二叉排序树查找函数的返回值是BSTNode类型,函数有两个参数分别是二叉排序树bt和关键字k*/ {if(bt==NULL||bt->key==k)/*递归的终结条件*/ return1; if(k {returnSearchBST(bt->lchild,k)+1;/*在左子树中的递归查找*/ } else {returnSearchBST(bt->rchild,k)+1;/*在右子树中的递归查找*/ }} intSearchHT(HashTableha,intp,KeyTypek)/*哈希查找的返回值是整型有三个参数,分别是哈希表ha、小于哈希表长度的最小素数p和关键字k*/ { inti=0,adr=0; intm=50; adr=k%p; while(ha[adr].key! =NULLKEY&&ha[adr].key! =k)/*采用线性探查法查找下一个地址*/ { i++; adr=(adr+1)%m;/*adr=(adr+1)modm*/ } if(ha[adr].key==k) returni+1;/*查找成功*/ else return-1;/*查找失败*/ } 3、各模块之间的调用关系以及算法设计 函数的调用关系图: Main SeqSearch BinSearch IdxSearch SearchHT SearchBST CreateHT InsertHT CreateBST InsertBST 在主函数中需要定义一个SeqListR的顺序表;HashTableha哈希表;索引表IDXI。 用srand函数(产生随机数)随机产生50个1到100的整数并输出,因为折半查找需要的是顺序表,所以再对产生的50个随机数再进行排序。 调用SeqSearch、BinSearch、IdxSearch、SearchHT、SearchBST(CreateBST)。 依次进行输出。 注意: 每次都要给sum重新赋值为零。 三详细设计 #include<> #include<> #include<> #defineMAXL100 #defineMAXI100 #defineNULLKEY-1 #defineDELKEY-2 typedefintKeyType; typedefintInfoType; typedefstruct { KeyTypekey; intlink; }IdxType; typedefIdxTypeIDX[MAXI]; typedefstruct { KeyTypekey; InfoTypedata; }NodeType; typedefNodeTypeSeqList[MAXL]; typedefstructnode { KeyTypekey; InfoTypedata; structnode*lchild,*rchild; }BSTNode; typedefstruct {KeyTypekey; InfoTypedata; intcount; }HashTable[MAXL]; intSeqSearch(SeqListR,intn,KeyTypek)ey! =k) {i++; } returni+1; } intBinSearch(SeqListR,intn,KeyTypek)ey==k) returncount+1; if(R[mid].key>k) high=mid-1; else low=mid+1; } return0; } intIdxSearch(IDXI,intb,SeqListR,intn,KeyTypek)ey>=k) high=mid-1; else low=mid+1; } i=I[high+1].link; while(i<=I[high+1].link+s-1&&R[i].key! =k) { count++; i++; } if(i<=I[high+1].link+s-1) returncount+1; else return0; } intSearchHT(HashTableha,intp,KeyTypek)ey! =NULLKEY&&ha[adr].key! =k) { i++; adr=(adr+1)%m; } if(ha[adr].key==k) returni+1; else return-1; } voidInsertHT(HashTableha,int&n,KeyTypek,intp)ey==NULLKEY||ha[adr].key==DELKEY) { ha[adr].key=k; ha[adr].count=1; } else { i=1; do { adr=(adr+1)%p; i++; }while(ha[adr].key! =NULLKEY&&ha[adr].key! =DELKEY); ha[adr].key=k; ha[adr].count=i; } n++; } voidCreateHT(HashTableha,KeyTypex[],intn,intm,intp)ey=NULLKEY; ha[i].count=0; } for(i=0;i InsertHT(ha,n1,x[i],p); } intInsertBST(BSTNode*&p,KeyTypek)ey=1+(int)*rand()/(RAND_MAX+); printf("%d\t",R[i].key); } printf("***************************************************************************\n"); for(i=0;i<50;i++) for(a=i+1;a<50;a++) if(R[i].key>R[a].key) { e=R[i].key; R[i].key=R[a].key; R[a].key=e; } for(i=0;i<50;i++) T[i]=R[i].key; for(i=0;i<50;i++) { sum=sum+SeqSearch(R,50,R[i].key); } printf("顺序查找平均查找长度: %\n",sum/; sum=0; for(i=0;i<50;i++) { sum=sum+BinSearch(R,50,R[i].key); } printf("折半查找平均查找长度: %\n",sum/; sum=0; for(i=0;i<5;i++) { I[i].link=i*10; I[i].key=R[i*10+9].key; } for(i=0;i<50;i++) { sum=sum+IdxSearch(I,5,R,50,R[i].key); } printf("索引查找平均查找长度: %\n",sum/; sum=0; CreateHT(ha,b,50,53,53); for(i=0;i<50;i++) { sum=sum+SearchHT(ha,53,ha[i].key); } printf("哈希表查找平均查找长度: %\n",sum/; sum=0; for(i=0;i<50;i++) { sum=sum+SearchBST(CreateBST(b,50),b[i]);; } printf("二叉树查找平均查找长度: %\n",sum/; } 四测试与分析 输出结果: 结果分析: 由结果显然可以看出,在线性表存储结构中折半查找的效率最高,顺序查找的效率最低,索引查找介于两者之间。 在顺序表存储结构、链式存储结构、索引表存储结构和哈希表存储结构中效率最高的是哈希表。 还有一种在动态查找时很高效的一种存储结构——树表。 几种查找的效率依次是: 五总结 数据结构总结: 为期一周的数据结构课程设计已经过去了,在这次课程设计中我学习到了很多知识,对编程也有了一定的认识。 譬如在结构体的使用在大一下学期的C语言课程中我学的不是很清楚,很多问题都没有搞懂,但在数据结构这门课程中我对结构体这一部分有了新的认识;此外还有函数的调用以及函数的参数这方面我也弥补了在大一上学期拉下的课程。 当然这学期的数据结构主要讨论的是算法问题,算法的优劣对效率的影响很大,记得以前在数据结构贴吧里看到这一句话“好的算法可能需要不到一分钟就可以跑完,而不合适的算法100年也不一定能跑完”,在这次课程设计中我也深深的体会到了这句话的含义。 我课程设计的题目是《查找性能的分析》,的确,不同的查找方法差异很大。 当然我也遇到了很多问题: ①如何生成50个随机数时需要用到的“srand”函数; ②每种查找算法之后sum(总的平均查找长度)要重新赋值为0; ③哈希查找是需要先建立哈希表,二叉树排序树查找需要先建立二叉树; 在大二第一学期我们开设了一门数据结构课程,听学长说这门课程很重要当然也很难,我也在很积极努力的学习这门课程。 石老师是一个很负责人的老师,经常给我强调编程的重要性,讲课风格别具一格,思路清晰,举例形象生动。 在课程设计中我的编程水平很是不行,半天编不出一个程序,我也在寻找问题的根源,归根到底我还是练习的太少,投入太少,像查找算法这部分就比其余部分认识较为深刻,当石老师说哈夫曼编码就是文件压缩的原理时,我渐渐的感觉到数据结构这门课程是非常重要的也是非常使用的,其它算法的用途是什么的可以解决什么问题呢,我想这应该是我们在以后这两年中值得去思考的问题。 最后很感谢石老师的指导,在数据结构这门课程的学习中,石老师教我们如何看懂程序帮助很大,万分感谢,我会在以后的道路中谨记老师教导,勤动手、勤动脑。 还要感谢在课程设计中帮我调试程序的同学们。 学生: 王旭 2015年1月10日11: 30: 45
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 查找 算法 课程设计
文档标签
- 应用算法数据结构课程设计
- 数据结构课程设计计算器
- 数据结构算法课程设计题目
- 数据结构与算法课程设计数据结构算法课程设计
- 数据结构实验查找算法
- 问题数据结构算法课程设计
- 算法与数据结构课程设计报告算法数据结构
- 数据结构查找算法实验
- 数据结构算法设计课程设计
- 查找算法设计实现
- 数据结构查找课程设计
- 数据结构算法课程设计
- 数据结构与算法数据结构算法课程设计
- 算法数据结构查找
- 算法数据结构程序设计中的
- 数据结构查找算法
- 数据结构算法课程设计指导书
- 算法与数据结构课程设计算法数据结构课程设计
- 棋盘数据结构算法课程设计
- 数据结构课程设计说明书应用
- 数据结构与算法分析课程设计《数据结构与算法分析课程设计》任务书数据结构算法
- 计数器的设计与应用终结版计数器设计