数据结构内部排序算法比较.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：1.38M 资料格式：doc 举报版权申诉

blue1922-4003436-4744300845199097463.doc.pdf-第1页.png

第1页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第2页.png

第2页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第3页.png

第3页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第4页.png

第4页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第5页.png

第5页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第6页.png

第6页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第7页.png

第7页 / 共56页

blue1922-4003436-4744300845199097463.doc.pdf-第8页.png

第8页 / 共56页

文本预览

实习报告题目：内部排序算法比较班级：4 班姓名：张文芳学号：409417080429 完成日期：2011-6-27 一、需求分析 1、在本程序中，待排序表的表长不小于 1005 其中的数据要用伪随机数产生程序产生：至少要用 5 组不同的输入数据作比较：比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为 3 次移动)。用 6 种常用的内部排序算法进行比较 z 起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、演示程序以用户与计算机交互方式执行，即在计算机终端上显示"提示信息"之后，由随机数产生器生成的输入数据即待排序表。 3、程序执行的命令包括： (1)构造随机数产生一列数(2)构造起泡排序；(3)构造直接插入排序；(4)构造简单选择排序；(5)构造快速排序；(6)构造希尔排序；(7) 构造堆排序；(8)构造比较关键字的比较次数和移动次数的大小；(9) 结束。构造 6 种内部插入排序时，待排序表由随机数产生器生成。每一个内部插入排序不仅实现排序功能，而且记录关键字的比较次数和移动次数。 4、测试数据由随机数产生器生成二、概要设计 1、关于 6 种排序算法的描述顺序表的存储结构 typedef struct { int elem[MAX]; int length; int a,b; }SqList; void Initbiao(SqList &L); 操作结果：构造了一个顺序表,表的长度不小于 1005，且表中数据均由随机数产生器生成。

void Bubblesort(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行起泡排序，并记录关键字的比较次数 x 和移动次数 y void Insertsort(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行直接插入排序，并记录关键字的比较次数 x 和移动次数 y void Selectsort(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行简单选择排序，并记录关键字的比较次数 x 和移动次数 y void Quicksort(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行快速排序，并记录关键字的比较次数 x 和移动次数 y void Shellinsert(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行希尔排序，并记录关键字的比较次数 x 和移动次数 y void Heapsort(SqList L,int &x,int &y) 初始条件：顺序表 L 已存在操作结果：将顺序表 L 进行堆排序，并记录关键字的比较次数 x 和移动次数 y void compare(int x1,int x2,int x3,int x4,int x5,int x6) 操作结果：将 6 种排序方法的比较次数和移动次数分别进行比较 2.本程序包含九个模块 1)主程序模块 void main() { 初始化; 函数调用； } 2)随机产生一列数的模块

3)起泡排序模块 4)直接插入排序模块 5)简单选择排序模块 6)快速排序模块 7)希尔排序模块 8)堆排序模块 9)比较大小的模块三、详细设计 1、顺序表的顺序存储结构 typedef struct { //顺序表的值即随机产生的一列数 int elem[MAX]; int length; int a,b; //顺序表的长度 //记录排序的比较次数和移动次数 }SqList; 2、void Initbiao(SqList &L); 操作结果：构造了一个顺序表,表的长度不小于 1005，且表中数据均由随机数产生器生成。 void Initbiao(SqList &L)//随机数产生器生成 { int i,n; a: printf("请输入你要输入的个数:"); //i 是顺序表的长度范围，n 是要输入的个数 scanf("%d",&n); if(n<1005) { printf("不在范围内重新输入!!!\n"); //要输入的个数<1005 时，返回 a goto a; } if(n>2000) { printf("超出范围重新输入!!!\n"); goto a; //要输入的个数>2000 时，返回 a } for(i=1;i<2000;i++)

//顺序表的初始化 L.elem[i]=0; if(!L.elem)exit(0); L.length=0; for(i=1;i100)goto b; //给顺序表赋值，当数大于 100，返回 b，重新赋值 ++L.length; } for(i=1;i

开始输入 L N iL.el em[j+1] Y 比较次数 +1 将两个数进行交换，移动次数+3 i++ 输出 L、比较次数和移动次输出 L、比较次数和移动次数数结束

void bubblesort(SqList L,int &x,int &y)//起泡排序的每一趟都将一列数的最小值向上漂浮，最大值沉底，反复进行操作直至结束 //&x、&y 是引用参数，不仅给操作提供输入值，还将返回操作结果 //x、y 分别是比较次数和移动次数 { int i,j; L.a=0; L.b=0; for(i=1;iL.elem[j+1]) { L.elem[0]=L.elem[j]; L.elem[j]=L.elem[j+1]; L.elem[j+1]=L.elem[0]; L.b+=3; } } } x=L.a; y=L.b; for(i=1;i

开始输入 L i<=L.length N Y L.elem[i]

void InsertSort(SqList L,int &x,int &y)//直接插入排序是先将序列中的第一个纪录看成是一个有序的子序列，然后从第二个记录起逐个插入，直至整个序列变成按关键字非递减有序序列为止。 //&x、&y 是引用参数，不仅给操作提供输入值，还将返回操作结果 //x、y 分别是比较次数和移动次数 { int i,j; L.a=0; L.b=0; for(i=2;i<=L.length;i++) { L.a++; if(L.elem[i]

分享到：

赞收藏

资料库

数据结构内部排序算法比较.doc

相关推荐

课程资源

热门标签

最新资料