湖州师范学院数据结构DS大作业_数据结构课内大作业

湖州师范学院数据结构DS大作业由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课内大作业”。

求真学院

数据结构课程设计大作业

20142832班

题

目： 专

业： 学生姓名： 学

号 指导教师 完成日期：

排序效率的比较 计算机科学与技术

邵

斌

湖州师院求真学院信息工程系

目录一、二、三、四、五、六、七、实验内容概述...............................................................................................................................1 实验目的概述...............................................................................................................................1 解题思路的描述...........................................................................................................................1 源程序清单...................................................................................................................................1 程序调试及测试结果...................................................................................................................8 结论...............................................................................................................................................9 参考文献.....................................................................................................................................10

I

此处写大作业题目（宋体三号，居中）

【内容摘要】

200至300字左右，楷体BG2312五号

【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。

关键字：排序 逻辑运算 数据结构 时间复杂度

【Abstract】

中文摘要的翻译，五号，Times New Roman

【Key words】XXXXX，XXXXX，XXXXX，XXXXX Data structure is the way of computer storage and organization data.A data structure is a data element and a set of data elements that have one or more specific relationships between each other.Typically, carefully selected data structures can be brought to a higher running or storage efficiency, proceing a variety of problems.The program is written in C language, it fully reflects the concept of data structure and algorithm charm.The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achieve the same effect, is the so-called “all roads lead to Rome”.And, the program also collects the running time of each algorithm, through the time of the comparison, for the user to pick out two kinds of optimization of the sorting method.Keywords: sorting logic operation data structure time complexity

一、实验内容概述

对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。

要求：（１）被排序的对象由计算机随机生成，长度分别取２０，１００，５００三种。

（２）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。

（３）对课设的结果做比较分析

二、实验目的概述

1.巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力；

2.通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作；

3.锻炼学生的动手能力与培养其独立思考的能力。

三、解题思路的描述

这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。

对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。

取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete()来释放申请排序对象的指针，避免程序出现内存耗尽的情况。

四、源程序清单

主要包括： #include #include #include int a[501],b[501];int len;//数组长度

void number(){ srand(time(0));int i,t;printf(“随机数长度：n”);printf(“ 1.长度为20n”);printf(“ 2.长度为100n”);printf(“ 3.长度为500n”);printf(“输入序号选择长度:”);scanf(“%d”,&t);switch(t){ case 1: n=20;for(i=1;i

}break;case 2: n=100;for(i=1;i

}RecordNode;//排序结点类型 typedef struct{ RecordNode *record;int n;//排序对象的大小 //srand函数是初始化随机数的种子 }ElemType;//排序对象的类型 直接排序

void InsertSort(ElemType A[], int n){ int i, j;ElemType x;for(i=1;i

x = A[i];//准备插入第i个元素 for(j=i-1;j>=0;j--){ //从第i-1个开始往前找插入点 if(x.stn

void SelectSort(ElemType A[], int n){ int i, j, k;ElemType x;for(i=0;i

for(i=1;i

void BubbleSort(ElemType A[], int n){ int i, j, flag;//flag为交换标记 ElemType x;for(i=1;i=i;j--)//第i 趟 if(A[j].stn

x=A[j];A[j]=A[j-1];A[j-1]=x;} if(flag==0)return;} for(i=1;i

void ShellSort(ElemType A[ ], int n,int dk)

{

int i,j,temp;ElemType x;

for(i=dk;i=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行 A[j+dk]= A[j];if(j!=i-dk)A[j+dk]=temp;//插入 } for(i=1;i

快速排序

void QuickSort(ElemType A[ ], int s, int t){ //递归算法，对区间 A[s] ～A[t] 进行快速排序 int i=s+1, j=t;ElemType temp, x = A[s];//第一个为基准元素 while(i= x.stn)j--;//从右到左 if(i

printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } if(s!=j){ //交换基准元素 A[s]=A[j];A[j]=x;} if(s

void CreatHeap(ElemType A[], int n){ int i;for(i =(n–2)/2;i >= 0;i--)Sift(A, n, i);//调整A[i..n-1]使之为一个堆 } void Sift(ElemType A[], int n, int i){ // 调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）ElemType x=A[i];int j = 2 * i + 1;// j为i的左孩子 while(j

if(x.stn

CreatHeap(A, n);// 把A建成一个堆for(i = n-1;i >= 1;i--){ x = A[0];//第0个元素与第i个元素交换 A[0] = A[i];A[i] = x;Sift(A, i, 0);//调整A[0..i-1]使之为一个堆 } for(i=1;i>A[j];cout

cout

算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？ 插入排序：稳定，时间复杂度 O(n^2)O(n2)选择排序：不稳定，时间复杂度 O(n^2)O(n2)冒泡排序：稳定，时间复杂度 O(n^2)O(n2)希尔排序：不稳定，时间复杂度 平均时间 O(nlogn)最差时间O(n^s)1

程序调试及测试结果

主要包括：

选择长度为20的随机数，六种方法排序的结果。

从比较次数和移动次数可大致看出各排序方法的效率高低，后三种明显优于前三种

六、结论

主要包括：

随机数产生方法：srand(time(0))就是给这个算法一个启动种子，也就是算法的随机种子数，有这个数以后才可以产生随机数,用1970.1.1至今的秒数，初始化随机数种子。Srand是种下随机种子数，你每回种下的种子不一样，用Rand得到的随机数就不一样。为了每回种下一个不一样的种子，所以就选用Time(0)，Time(0)是得到当前时时间值（因为每时每刻时间是不一样的了）。

进行函数的参数传递时，如果传入一个地址，比传入一个struct效率要高，因为少了一个拷贝过程。待改进的地方：很多步骤有重复用到，如把数组b赋值给a，定义Ccnt，Rcnt等，可以做个初始化的函数调用，省去重复的代码。可以增加其他排序方法进行效率比较。

七、参考文献

[1] 唐国民, 王国钧.数据结构 [M].北京:清华大学出版社, 2013: 213-238 [2] 张乃孝.算法与数据结构——C语言描述[M].北京: 高等教育出版社, 2002 [3] 唐国民，王智群.C语言程序设计[M].北京:清华大学出版社, 2009:107-115 [4] 唐国民, 王国钧.数据结构实验教程 [M].北京:清华大学出版社, 2013: 195-207 说明：

标为M的是书籍 标为D的为学位论文 标为J的为期刊 标为C的为会议论文

指导教师：邵

斌 日期：2016/6/5 实验成绩：