当前位置:文档之家› 查找排序实验报告

查找排序实验报告

《编程实训》实验报告书专业:计算机科学与技术班级: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 782 概要设计(如果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) //大根堆调整函数void MergePass(SeqList R,int length) //归并排序4 实现和调试4.1 主要的算法查找:①建立顺序存储结构,构建一个顺序表,实现顺序查找算法。

typedef struct {ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空int length; //表的长度} SSTable;②对顺序表先排序后,实现行二分法查找相关操作。

③定义二叉树节点,根据节点的值进行查找,并且实现节点的插入,删除等操作。

typedef struct BiTnode { //定义二叉树节点int data; //节点的值struct BiTnode *lchild,*rchild;}BiTnode,*BiTree;④定义哈希表以及要查找的节点元素,创建哈希表,实现其相关查找操作。

typedef struct {int num;} Elemtype; //定义查找的结点元素typedef struct {Elemtype *elem; //数据元素存储基址int count; //数据元素个数int sizeindex;}HashTable;//定义哈希表排序:2. 排序相关实验内容及步骤。

①定义记录类型。

typedef struct{int key; //关键字项}RecType;②实现直接插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已排序好的子文件中的适当位置,直到全部记录插入完成为止。

③实现冒泡排序:设想被排序的记录数组R[1‥n]垂直排序。

根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上“漂浮”(交换),如此反复进行,直到最后任意两个气泡都是轻者在上,重者在下为止。

④实现快速排序:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录作为支点(又称基准记录)(pivot),将所有关键字比它小的记录放置在它的位置之前,将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。

之后对所分的两部分分别重复上述过程,直到每部分只有一个记录为止。

⑤实现直接选择排序:第i趟排序开始时,当前有序区和无序区分别为R[1‥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看成是一棵二叉树,每个结点表示一个记录,源文件的第一个记录R[1]作为二叉树的根,以下各记录R[2‥n]依次逐层从左到右排列,构成一棵完全二叉树,任意结点R[i]的左孩子是R[2i],右孩子是R[2i+1],双亲是R[i/2]。

⑦实现二路归并排序:假设初始序列n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并,……,如此重复,直到一个长度为n的有序序列为止。

4.2 主要问题及解决在实验前对于各种查找和排序的算法不是很熟悉,所以花了一些时间去复习。

有些代码反复测试还是找不出错误,最后也是翻阅了书本并仔细思考才改进了算法并成功测试出了结果。

这次试验大大提升了我对排序算法及查找算法的熟练程度。

4.3 测试执行及结果查找算法:任意输入若干正整数并测试如下:排序算法:任意输入数字并测试如下:5 改进根据提示的代码,经过一系列调试后最终出了结果。

在一开始运行时总是出错,特别是二叉树的测试,代码有些小错误导致测试的时候程序总是出错。

最后改动了一下提高了程序的稳定性并成功运行出了结果。

6 附录【附录1----查找源程序】#include"iostream"#include"stdlib.h"#include"stdio.h"#include "malloc.h"#define MAX 11using namespace std;typedef int ElemType ;//顺序存储结构typedef struct{ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空int length; //表的长度}SSTable;void Create(SSTable *table, int length);void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem));void Create(SSTable **table, int length) // 构建顺序表{SSTable *t = (SSTable*) malloc(sizeof(SSTable));//分配空间t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));t->length=length;*table=t;}void FillTable(SSTable *table) // 无序表的输入{ElemType *t=table->elem;for(int i=0; i<table->length; i++) //for循环,输入各个元素{t++;scanf("%d", t); //输入元素getchar();}}void Destroy(SSTable *table) // 销毁表{free(table->elem);//释放元素空间free(table);//释放表的空间}void PrintTable(SSTable *table) // 打印查找表{int i; //定义变量ElemType *t=table->elem;for(i=0; i<table->length; i++) //进入循环,依次打印表中元素{t++;printf("%d ", *t); //打印输出}printf("\n");}int Search_Seq(SSTable *table, ElemType key) //哨兵查找算法{table->elem[0]=key; //设置哨兵int result=0; // 找不到时,返回int i;for (i=table->length; i>=1;i--){if (table->elem[i]==key){result=i;break;}}return result; //返回结果}void printSeq(){SSTable *table; //先设置几个变量int r;int n;ElemType key;printf("请输入元素个数:");scanf("%d",&n); //输入元素个数Create(&table, n); //建立表printf("请输入");cout<<n;printf("个值:");FillTable(table); //输入无序表的值printf("您输入的%d 个值是:\n",n);PrintTable(table); //打印无序表printf("请输入关键字的值:");scanf("%d",&key);printf("\n");printf("顺序查找法运行结果如下:\n\n ");Search_Seq(table,key); //哨兵查找算法r=Search_Seq(table,key);if(r>0){printf(" 关键字%d 在表中的位置是:%d\n",key, r);//打印关键字在表中的位置printf("\n");}else //查找失败{printf ("查找失败,表中无此数据。

相关主题