查找与内排序试验五

本文格式为Word版，下载可任意编辑——查找与内排序试验五甘肃政法学院

本科生试验报告

（五）

姓名:学院:专业:班级:

试验课程名称:数据结构试验日期:2023年12月17日指导教师及职称:金涛试验成绩:

开课时间：2023-2023学年第一学期

甘肃政法学院试验管理中心印制

试验题查找、内排序目姓名班级小组合否作学号一、试验目的理解查找的基本概念,包括静态查找表和动态查找表、内查找和外查找之间的差异；重点把握线性表上各种查找算法,包括顺序查找、二分查找和分块查找的基本思路、算法实现和查找效率等；把握各种树表的查找算法,包括二叉排序树、AVL树和B-树的基本思路、算法实现和查找效率等；把握哈希表查找技术以及哈希表与其他表的本质区别。理解内排序的基本概念；重点把握插入排序算法,包括直接插入排序和希尔排序的过程和算法实现；重点把握交换排序算法,包括冒泡排序和快速排序的过程和算法实现；重点把握选择排序算法,包括直接选择排序和堆排序的过程和算法实现；把握归并排序的过程和算法实现；握基数排序的过程和算法实现；活运用各种排序算法解决一些综合应用问题。二．试验环境一台装有MicrosoftVisualC++6.0的计算机。三、试验内容与步骤一、查找：查找是给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相关的指示信息。若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。2.①顺序查找：它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描终止后,仍未找到关键字等于k的记录,则查找失败。②二分查找：二分查找也称为折半查找要求线性表中的结点必需己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。试验步骤及截图如下：运行结果如下：③分块查找：分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将表R[0..n-1]均分为b块,前b-1块中记录个数为s=?n/b?,最终一块即第b块的记录数小于等于s；每一块中的关键字不一定有序,但前一块中的最大关键字必需小于后一块中的最小关键字,即要求表是“分块有序〞的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0..b-1],即IDX[i](0≤i≤b-1)中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。运行结果如下：3.若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1,即平衡因子取值为1、0或-1,则该二叉树称为平衡二叉树（AVL）。运行结果如下：二叉排序树：

运行结果如下：4.B-树又称为多路平衡查找树,是一种组织和维护外存文件系统十分有效的数据结构。运行结果如下：5.哈希表(HashTable)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为n,设置一个长度为m(m≥n)的连续内存单元,以线性表中每个对象的关键字ki(0≤i≤n-1)为自变量,通过一个称为哈希函数的函数h(ki),把ki映射为内存单元的地址(或称下标)h(ki),并把该对象存储在这个内存单元中。h(ki)也称为哈希地址(又称散列地址)。把如此构造的线性表存储结构称为哈希表。

运行结果如下：5．快速排序基本思想是：在待排序的n个记录中任取一个记录(寻常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。运行结果如下：6.直接选择排序的基本思想是：第i趟排序开始时,当前有序区和无序区分别为R[0..i-1]和R[i..n-1](0≤i＜n-1),该趟排序则是从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。运行结果如下：7.堆排序是一树形选择排序,它的特点是,在排序过程中,将R[1..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。8.归并排序是屡屡将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

}}2.希尔排序：voidShellSort(RecTypeR[],intn)/*希尔排序算法*/{inti,j,d;RecTypetemp;d=n/2;/*d取初值n/2*/while(d>0){for(i=d;i=0/*R[j]与R[j+d]交换*/R[j]=R[j+d];R[j+d]=temp;j=j-d;}}d=d/2;/*递减增量d*/}}3.冒泡排序：voidBubbleSort(RecTypeR[],intn){inti,j,exchange;RecTypetemp;for(i=0;ii;j--)/*比较,找出最小关键字的记录*/if(R[j].keyiif(i=1;i--)/*循环建立初始堆*/sift(R,i,n);for(i=n;i>=2;i--)/*进行n-1次循环,完成推排序*/{temp=R[1];/*将第一个元素同当前区间内R[1]对换*/R[1]=R[i];R[i]=temp;sift(R,1,i-1);/*筛选R[1]结点,得到i-1个结点的堆*/}}7.二路归并排序算法如下：voidMergeSort(RecTypeR[],intn)/*自底向上的二路归并算法*/{intlength;for(length=1;length=0;i--)/*从低位到高位做d趟排序*//*123以“321〞存储*/{for(j=0;jdata[i]-'0';/*找第k个链队*/if(head[k]==NULL)/*进行分派,即采用尾插法建立单链表*/{head[k]=p;tail[k]=p;}else{tail[k]->next=p;tail[k]=p;}p=p->next;/*取下一个待排序的元素*/}p=NULL;for(j=0;jnext=head[j];t=tail[j];}}t->next=NULL;/*最终一个结点的next域置NULL*/}}五、试验总结本次试验是有关查找和内排序的试验，在整个试验过程中由于操作不熟练和源代码理解不透彻问题导致了一些错误；但通过本次试验还是或多或少的把握了有关查找和内排序的相关知识点儿。通过本次查找和排序的练习，初步把握了其基本概念和操作查找的基本概念查找表:是由同一类型的数据元素（或记录）构成的集合。查找表的操作：查询某个“特定的〞数据元素是否在查找表中；检索某个“特定的〞数据元素的各种属性；在查找表中插入一个元素；从查找表中删去某个数据元素。排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。在以后的试验和学习过程中，我会更加重视理论知识与实践相结合的方法；更好的学习该课程。

运行结果如下：9.基数排序是通过“分派〞和“收集〞过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。运行结果如下：四、试验过程与分析本次试验是有关查找与内排序的试验，在整个试验过程中我们应当注意一下一些问题：1.由于查找运算的主要运算是关键字的比较,所以寻常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(AverageSearchLength)定义为：其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数。2.①顺序查找：顺序查找的算法如下(在顺序表R[0..n-1]中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1)：intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(i=n)return-1;elsereturni;}②二分查找：算法如下(在有序表R[0..n-1]中进行二分查找,成功时返回记录的位置,失败时返回-1)：intBinSearch(SeqListR,intn,KeyTypek){intlow=0,high=n-1,mid;while(lowk)/*继续在R[low..mid-1]中查找*/high=mid-1;elselow=mid+1;/*继续在R[mid+1..high]中查找*/}return-1;}③分块查找：采用二分查找索引表的分块查找算法如下(索引表I的长度为m)：intIdxSearch(IDXI,intm,SeqListR,intn,KeyTypek){intlow=0,high=m-1,mid,i;intb=n/m;/*b为每块的记录个数*/while(low=k)high=mid-1;elselow=mid+1;}if(lowkey==k)/*递归终结条件*/returnbt;if(kkey)returnSearchBST(bt->lchild,k);/*在左子树中递归查找*/elsereturnSearchBST(bt->rchild,k);/*在右子树中递归查找*/}4.在一棵B-树上顺序查找关键字为k的方法为：将k与根结点中的key[i]进行比较：(1)若k=key[i],则查找成功；(2)若k＜key[1],则沿着指针ptr[0]所指的子树继续查找；(3)若key[i]＜k＜key[i+1],则沿着指针ptr[i]所指的子树继续查找；(4)若k＞key[n],则沿着指针ptr[n]