查找排序实验报告.doc

《编程实训》 实验报告书 专 业：计算机科学与技术 班 级：151班 学 号： 姓 名： 指导教师： 日 期：2016年6月30日 目录 一、需求分析…………………………………………………………………………………3 1.任务要求……………………………………………………………………………………3 2.软件功能分析………………………………………………………………………………3 3.数据准备……………………………………………………………………………………3 二、概要设计…………………………………………………………………………………3 1.功能模块图………………………………………………………………………………4 2.模块间调用关系…………………………………………………………………………4 3.主程序模块………………………………………………………………………………5 4.抽象数据类型描述…………………………………………………………………………5 三、详细设计…………………………………………………………………………………6 1.存储结构定义………………………………………………………………………………6 2.各功能模块的详细设计……………………………………………………………………7 四、实现和调试………………………………………………………………………………7 1.主要的算法………………………………………………………………………………7 2.主要问题及解决…………………………………………………………………………8 3.测试执行及结果……………………………………………………………………………8 五、改进………………………………………………………………………………………9 六、附录……………………………………………………………………………………9 1.查找源程序………………………………………………………………………………9 2.排序源程序………………………………………………………………………………9 目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实 现；以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下： 12 23 45 56 78 2 概要设计（如果2，3合并可以省略2.4） 2.1 功能模块图（注：含功能说明） 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。 数据类型（data type）是一个"值"的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找： typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; //表的长度 }SSTable; 排序： typedef struct { //定义记录类型 int key; //关键字项 }RecType; typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵 3.2 各功能模块的详细设计 查找： void Create(SSTable *table, int length); // 构建顺序表 void FillTable(SSTable *table) // 无序表的输入 int Search_Seq(SSTable *table, ElemType key); //哨兵查找算法 void Sort(SSTable *table ) // 排序算法 int Search_Bin(SSTable *table, ElemType key) // 二分法查找（非递归） 排序： void InsertSort(SeqList R) //对顺序表R中的记录R[1 n]按递增序进行插入排序 void BubbleSort(SeqList R) //自下向上扫描对R做冒泡排序 int Partition(SeqList R,int i,int j)//对R[i j]做一次划分，并返回基准记录的位置 void QuickSort(SeqList R,int low,int high) //R[low..high]快速排序 void SelectSort(SeqList R) //直接选择排序 void Heapify(SeqList R,int low,int high) //大根堆调整函数 v