数据结构查找排序实验报告

《数据结构查找排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、贵州大学实验报告学院：电子信息学院专业：通信工程班级：2012级1班姓名学号实验组实验时间2014.5.15指导教师成绩实验项目名称查找排序实验目的和要求1、掌握常用的查找、排序方法，及相应的算法实现。2、能实现并应用某一种查找算法。理解各种排序方法的特点，并能加以灵活应用。3、了解各种排序算法的时间复杂度分析。实验原理1、根据实验内容编程，上机调试、得出正确的运行程序。2、编译运行程序，观察运行情况和输出结果。实验仪器运行Visualc++的微机一台实验内容和步骤1、查找相关实验内容及步骤。①建立顺序存储结构，构建一个顺序表，实现顺序

2、查找算法。typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，号单元留空intlength;//表的长度}SSTable;②对顺序表先排序后，实现行二分法查找相关操作。③定义二叉树节点，根据节点的值进行查找，并且实现节点的插入，删除等操作。typedefstructBiTnode{//定义二叉树节点intdata;//节点的值structBiTnode*lchild,*rchild;}BiTnode,*BiTree;④定义哈希表以及要查找的节点元素，创建哈希表，实现其相关查找操作。ty

3、pedefstruct{intnum;}Elemtype;//定义查找的结点元素typedefstruct{Elemtype*elem;//数据元素存储基址intcount;//数据元素个数intsizeindex;}HashTable;//定义哈希表。2.排序相关实验内容及步骤。①定义记录类型。typedefstruct{intkey;//关键字项}RecType;②实现直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。③实现冒泡排序：设想被排序的记录数组R[1‥n]

4、垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。④实现快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。⑤实现直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R[1

5、‥i-1]和R[i‥n]（1≤i≤n-1），该趟排序则是从当前无序区中选择出关键字最小的记录R[k]，将它与无序区的的第一个记录R[i]交换，有序区增加一个记录，使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。⑥实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R[1‥n]看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R[1‥n]子中，将R看成是一棵二叉树，每个结点

6、表示一个记录，源文件的第一个记录R[1]作为二叉树的根，以下各记录R[2‥n]依次逐层从左到右排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]。⑦实现二路归并排序：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直到一个长度为n的有序序列为止。3、编写一个主函数，调试上述算法。4、完成实验报告。实验数据实验总结通过本次实验我掌握常用的查找、排序方法，及相应的算法实现指导教师

7、意见签名：年月日