查找算法实现与性能分析 (数据结构课程设计)

存档编号：西安********课程设计说明书设计题目：查找算法性能分析系别：计算机学院专业：计算机科学班级：计科***姓名：王***（共页）2015年01月07 日*****计算机科学专业课程设计任务书姓名：*** 班级：计科**** 学号：****指导教师：**** 发题日期：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）输出各种查找算法的平均查找长度。

一、实验目的1. 理解并掌握几种常见查找算法的基本原理和实现方法。

2. 比较不同查找算法的时间复杂度和空间复杂度。

3. 通过实验验证查找算法的效率和适用场景。

二、实验内容本次实验主要涉及以下查找算法：1. 顺序查找法2. 二分查找法3. 散列查找法三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 实现顺序查找法2. 实现二分查找法3. 实现散列查找法4. 编写测试程序，分别对三种查找算法进行测试5. 比较三种查找算法的性能五、实验结果与分析1. 顺序查找法（1）实现代码```pythondef sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```（2）测试程序```pythonarr = [5, 3, 8, 6, 2, 7, 4, 9, 1]target = 6print("顺序查找结果：", sequential_search(arr, target))```（3）分析顺序查找法的时间复杂度为O(n)，空间复杂度为O(1)。

当数据量较大时，查找效率较低。

2. 二分查找法（1）实现代码```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1```（2）测试程序```pythonarr = [1, 2, 3, 4, 5, 6, 7, 8, 9]target = 6print("二分查找结果：", binary_search(arr, target))```（3）分析二分查找法的时间复杂度为O(log2n)，空间复杂度为O(1)。

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称查找算法指导教师教师评语教师签名：年月日一.实验内容：查找算法,其中线性表的查找包括顺序查找，二分查找，分块查找；树表的查找包括二叉排序树等；还有散列表的查找等等。

二.实验目的：1.掌握各种查找算法理解和实现；2.增强上机编程调试能力；三.主要程序代码分析：typedef struct{int Key; //关键项}ElemType;int Search_Seq(SSTable ST,int Key) //顺序查找{int i;ST.elem[0].Key=Key; //设置监视哨for(i=ST.length;ST.elem[i].Key!=Key;i--);return i;}int Search_Bin(SSTable ST,int Key) //在有序表中进行二分查找{int low=1;int high=ST.length; //置查找区间的上、下届初值int mid;count=0;while(low<=high) //当前查找区间非空{count++;mid=(low+high)/2;if(ST.elem[mid].Key==Key)return mid; //查找成功，返回else if(Key<ST.elem[mid].Key)high=mid-1; //缩小查找区间为左子表elselow=mid+1; //缩小查找区间为右子表}return (-1); //查找失败}四.程序运行结果：五.实验总结：查找又称检索，它也是数据处理中经常使用的一种重要的运算，在线性表上的查找方法有顺序查找，二分查找和分块查找。

顺序查找是一种最简单的查找方法。

它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后仍未找到关键字等于K的结点，则查找失败。

存档编号：********课程设计说明书设计题目：查找算法性能分析系别：计算机学院专业：计算机科学班级：计科***：王***（共页）2015年01月07 日*****计算机科学专业课程设计任务书：*** 班级：学号：指导教师：**** 发题日期：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）输出各种查找算法的平均查找长度。