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

《数据结构查找算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、成形式1、设计报告；2、源程序四、系（部）审核意见指导教师：****发题日期：2015-01-05完成日期：2015-01-09一需求分析1.1问题描述查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对表做修改运算（插入或删除），则相应的表成为动态查找表，反之称为静态查找表。由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数

3、（也叫平均查找长度）作为一个查找算法效率优劣的标准。平均查找程度ASL定义为：ASL=∑PiCi（i从1到n）其中Pi代表查找第i个元素的概率，一般认为每个元素的查找概率相等，Ci代表找到第i个元素所需要比较的次数。查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找（又叫哈希查找），它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找则需

4、要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。1.2基本要求（1）输入的形式和输入值的范围；在设计查找算法性能分析的过程中，我们调用产生随机数函数：srand((int)time(0));产生N个随机数。注：折半查找中需要对产生的随机数进行排序，需要进行排序后再进行输入，N<50;（2）输出形式；查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找长度的公式：ASL=∑PiCi（i从1到n）输出各种查找算法的平均查找长度。注：平均查找长度=总的平均查找长度/N；（1）程序所能达

5、到的功能通过输出几种查找算法的ASL，我们很显然能得在数据量较小时（N<100）我们在实现静态查找时应该选择如何调用哪种查找算法。二概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。1、数据结构顺序查找：在进行顺序查找顺序表类型定时需要定义typedefintKeyType；顺序表类型为SeqList类型。typedefNodeTypeSeqList【MaxSize】；/它的基本思路是：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比

6、较，若当前扫描到的关键字与k相等，查找成功。折半查找：在进行顺序查找顺序表类型定时需要定义typedefintKeyType，并且需要调用排序函数对其进行排序。折半查找类型为SeqList类型。typedefNodeTypeSeqList【MaxSize】；折半查找又叫二分查找，效率较高，但折半查找要求被查找的表示顺序表，它的基本思路是：设R【low…..high】是当前的查找区间，首先确定该区间的中点位置mid=┖（low+high）/2┘，然后将待查的k值与R【mid】.key。①如果中点值的值是

7、k，返回该元素的逻辑符号；②如果中点值>k，则中点值之后的数都大于k，所以k值在该表的左边，所以确定一个新的查找区间；③如果中点值

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