lvjing数据结构课程设计

学校：工程师范(高职部)

班级：计用052

姓名：吕静

完成时间：7月10日。

学号：数据结构课程设计—排序。

班级：计用052 姓名：吕静

一．内容简介。

我此次设计的内容是关于排序的有关知识的设计，根据所学知识和平时的实践完成了此次的设计内容，虽不完美，但在实际应用极为广泛。

设计内容主要是关于插入排序、交换排序、选择排序、归并排序、、、的应用，我此次设计主要用到的语句包括：for、while、if、 do…while、 case…….

首先，先是对排序的主程序的概括，即所应用到的有关语句。

其次，是对主程序的调用，通过排列顺序选择恰当的语句完成所对应的程序。

然后，确立关键字及由一组记录组成的文件，而记录则由若干个数据项(或域)组成，其中有一项可用来标识一个记录，称为一个关键字项，该数据项的值成为关键字(可以是字类型的也可是字符类型的，根据问题的要求而定).

最后，通过所学将语句贯穿起来，实现函数的正确调用。

学习c语言最初应该知道怎样运用一些关键字来编写程序，类的关键字中专时代有所了解，但并不深入。进入大学后对此类的运用就比较广了。因此，学好运用好是致关重要的。

所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。排序是是数据处理中经常运用的一种重要运算。由于排序在计算机中占有重要地位，所以必须熟悉内部排序的排序过程，记住各种算法的时间复杂度，以便实际应用。

排序：插入排序：1）直接插入排序 2）希尔排序。

选择排序：1）直接选择排序 2）堆排序。

交换排序：1）起泡排序 2）快速排序。

归并排序：、、

二流程图 case1 case2 case3 case4 case5 case6

三．程序**及分析。

以下是我对排序的设计及难懂的问题：

#define n 8

typedef struct /定义记录为结构类型/

int key关键字域/

rectype;

rectype r[nr为记录类型的数组/

此段程序设计在每个程序的开始，必不可缺）

起泡排序：bubblesort (r) /从下往上扫描的起泡排序/

rectype r[ ]

int i,j,noswap,w;

rectype temp;

for(i=0;i

if(noswap==0)

if(noswap) break; /本趟排序中未发生交换，则终止算法/

bubblesort/

注意：每一趟排序都使有序区增加了一个气泡，再经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中的气泡的重量总是大于等于有序区中的气泡的重量，所以，整个起泡排序过程至少需要n-1趟排序。

直接选择排序：

selectsort(r) /对r[0]到r[n-1]进行直接选择排序/

rectype r;

int i,j,k;

rectype temp;

for (i=0;i

insertsort /

注意：算法的辅助空间是一个监视哨，故空间复杂度s（n）=o（1）;直接插入排序是稳定的排序方法。+

快速排序：int partition(r,l,h返回划分或被定位的基准记录的位置/

rectype r对无序区r[l]到r[h]做划分/

int l,h;

int i,j,w;

rectype temp;

i=l;j=h; temp=r[i初始化，temp为基准/

doelse break; /调整完毕，退出循环/

r[i]=temp; /最初被调整结点放入正确位置/

sift/堆栈排序的算法）：

heapsort (r对r[1]到r[n]进行堆排序/

rectype r;

int i,k;

rectype temp;

for(i=n/2;i>=1;i建初始堆/

sift(r,i,n);

for(i=n;i>=1;i进行n-1趟堆排序/

{ temp=r[1当前堆顶记录和最后一个记录的交换/

lvjing数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了