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

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

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

3、的结点元素 typedef struct Elemtype *elem; /数据元素存储基址 int count; /数据元素个数 int sizeindex; HashTable;/定义哈希表。 2. 排序相关实验内容及步骤。 定义记录类型。 typedef struct int key; /关键字项 RecType; 实现直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。 实现冒泡排序：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（

4、交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。 实现快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。 实现直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的

5、有序区和新的无序区。如此反复进行，直到排序完毕。 实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。 实现二路归并排序：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直到一个长度为n的有序序列为止。 3、编写一个主函数，