实验八 查找和排序算法的实现

《实验八 查找和排序算法的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、XXXXXX实验报告班级学号姓名实验组别实验日期室温报告日期成绩一报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：查找与排序算法的实现和应用实验目的：1.掌握顺序表上查找的实现及监视哨的作用。2.掌握折半查找所需的条件、折半查找的过程和实现方法。3.掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。4.掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法。5.掌握直接插入排序、希尔排序、快速排序算法的实现。实验环境：Windows2000,VisualC++6.0实验内容：1.通过具体

2、算法程序，进一步加深对各种查找方法的掌握，以及对实际应用中问题解决方法的掌握。各查找算法的输入序列为：265371611159154819。输出要求：查找关键字37，给出查找结果。2.对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。各排序算法输入的无序序列为：265371611159154819.实验要求：1.顺序查找首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。2编程实现插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。

3、实验原理：1查找概念及其特点用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。①顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点，表示查找失败。顺序查找过程:从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录;反之，若直到第一个记录，其关键字和给定值比较都

4、不相等，则表明表中没有所查的记录，查找失败。算法描述为19附页intSearch(intd,inta[],intn){/*在数组a[]中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/inti;/*从后往前查找*/for(i=n-1;a!=d;--i)returni;/*如果找不到，则i为0*/}②折半查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功;若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，

5、直到查找到或查找结束发现表中没有这样的结点。折半查找又称为二分查找，它是一种效率较高的查找方法。【二分查找要求】:1.必须采用顺序存储结构2.必须按关键字大小有序排列。【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以

6、上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。【算法复杂度】假设其数组长度为n，其算法复杂度为o(log(n))下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-desthenmax=mid-1elsemin=mid+1returnmax19附页折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x

7、，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。③哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点(1≤i≤n)，keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有:addr(Ri)=H(keyi)，addr(Ri)为哈希函数。哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。设插入的

8、元素的关键字为x，A为存储的数组。初始化比较容易，例如constempty=maxlongint;//用非常大的整数代表这