数据结构课程设计报告

《数据结构》

课程设计报告。

计算机与信息工程系。

二零一四年十二月四日。

目录。1设计内容及要求 1

1.1 需求分析 1

1.2 要求 1

2概要设计 1

3设计过程或程序** 2

一）定义结构体数组： 2

二）直接排序 2

三）冒泡排序： 3

四）堆排序： 4

五）希尔排序 5

六）快速排序： 5

七）电脑随机取数： 6

八）用户自行输入 7

九）主函数调用： 8

3设计结果与分析 10

时间的估算 11

4参考文献 11

排序算法演示系统。

1设计内容及要求。

1.1 需求分析。

排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，快速排序，希尔排序，堆排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。

比较的结果用一个直方图表示。

利用随机函数产生n个随机整数（n=1000，1500，2000，2500，…,30000），利用直接插入排序、希尔排序、起泡排序、快速排序、堆排序五种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。

1.2 要求。

（1）用户输入任意个数，产生相应的随机数。

(2)用户可以自己选择排序方式（直接插入排序、希尔排序、起泡排序、快速排序、堆排序）的一种。

(3)程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。

2概要设计。

1)直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。

2)希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。

先在各组内进行直接插人排序；然后，取第二个增量d2（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第n-1和第n个记录的关键字进行过比较为止。

上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1个记录进行同样操作。一共要进行n-1趟起泡排序。

4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。

5）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。

3设计过程或程序**。

（一）定义结构体数组：

typedefstruct

intkey;

datatype;

datatyper[maxnum];/定义结构体数组。

二）直接排序。

voidd_insertsort(datatyper,intn)//直接排序。

inti,j;

for(i=2;i<=n;i++)

cn[0]++

if(r[i].key

r[0]=r[i];mn[0]++

for(j=i-1;r[0].keyr[j+1]=r[j];

r[j+1]=r[0];

mn[0]+=2;

三）冒泡排序：

voidbubble_sort(datatyper,intn)//冒泡排序。

inti,j;

intswap;

for(i=1;i

六）快速排序：

voidquick_sort(datatyper,ints,intt)//快速排序。

inti;if(s;

a:printf("请输入你要输入的个数：")

scanf("%d",&n);

if(n>25)

printf("超出范围重新输入！n");

gotoa;

addlist(r,n);

printf("排序前元素顺序为：")

for(i=1;iprintf("%d",r[i].key);

printf("");

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了