数据结构课程设计各种排序算法的实现

数据结构

课程设计汇报

题目:

专业:

班级:

学号:

姓名:

指导老师:

时间:

一、课程设计题目及所波及知识点

设计题目：排序算法实现

知识点：malloc申请持续存储空间、冒泡排序、迅速排序、直/插入排序的算法实现、

造体FI勺定义与调用、函数的递归调用

二、课程设计思绪及算法描述

设计思绪：1.确定程序要实现的功能即(1)容许顾客输入一组数据，任意多种。

(2)由顾客选择对该组数据进行排序口勺措施：直接插入排序、冒泡排序、迅速排序。并可

以查看每趟排序的成果,

2、确定程序所需要的功能块，存储构造-构造体，malloc申请存储空间，各功能函数一

冒泡排序功能块maopaoO；、直接插入排序功能块insertsort()；、迅速排序q_sort()；、数

据访问功能块traveresO；、数据输出功能块liststringO;主函数部分main。；。

3.编写代码详细实现各项功能，并进行调试。

算法描述：冒泡排序(BubbleSorting)的基本思想：

设待排序n个元素寄存在数组a[n]中，无序区范围初始为(a(0),a(l),a(2)a[n-l])»W

泡排序措施是在目前无序区内，从最上面的元素a：0]开始，对每两个相邻的元素和

a[i](i=0,l,...,n-1)进行比较,且使值较小的元素换至值较大的元素之上(若a[i]>a[i+l],则

a[i]和勺值互换)，这样通过一趟冒泡排序后，假设最终下移II勺元素为a[k],则无序区中值

较大的几种元素抵达下端并从小到大依次寄存在a[kH],a[k+2],...a[n-l]中，这样无序区范围

变为在目前无序区内进行下一趟冒泡排序。这个过程一直到某一

趟排序中不出现元素互换的动作，排序结束。整个排序过程最多执行n-1遍。

算法实现:

voidBubblcSort(ScqListR)

〃R(L.n)是待排序的文献，采用自下向上扫描，对R做冒泡排序

inti,j；

Booleanexchange；〃互换标志

for(i=l;i<n;i++){〃最多做n-1趟排序

exchange二FALSE；〃本趟排序开始前，互换标志应为假

for(j=n-l;j>=i；j—)〃对目前无序区R[i..n]自下向上扫描

if(R[j+1].key<R[j].key){〃互换记录

R[O]=R[j+l]；〃R[0]不是哨兵，仅做暂存单元

K[j+l]=R[j];

R[j]=R[O]；

oxchange=TRUE;〃发生了互换，故将互换标志置为真

)

if(!exchange)〃本趟排序未发生互换，提前终止算法

return；

)〃endfor(外循环)

}//BubbleSort

直接插入排序(StraightInsertionSorting)的!基木思想：

把n个待排序的元素当作为一种有序表和一种无序表，开始时有序表中只包括一种元素，无

序表中包具有nT个元素，排序过程中每次从无序表中取出第一种元素，将它插入到有序表中的

合适位置，使之成为新时有序表，反复nT次可完毕排序过程。

把a[i]插入到a[()],a[l].....a[iT]之中的详细实行过程为:先把a[i]赋值给变量t,然后将t

依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一种位置,直到发现某个j(0<=j<=iT),

使得a[j]<=t或j为(T),把t赋值给a[j+l].

算法实现：

voidinsertsort(ElomTypca[],intn)

〃待排序元素用一种数组a表达，数组有n个元素

{inti,j;

ElemTypet;

for(i=l;i<n;i++)//i表达插入次数,共进行nT次插入

{〃把待排序元素赋给t

while((j>=0)&&(t<a[j])){

a[j+l]=a[j];j—;}//次序比较和移动

a[j+l]=t：}

)

迅速排序算法：

在R[low..high]中任选一种记录作为基准(Pivot),以此基准将目前无序区划分为左、右两

个较小口勺子区间R[low..pivotposT)和R[pivotpos+L.high],并使左边子区间中所有记录口勺关

键字均不不小于等于基准记录(不妨记为pivot)的关键字pivot,key,右边的子区间中所有记录

的关键字均不小于等于pivot,key,而基准记录pivot则位于对H勺曰勺位置(pivotpos)上，它不必

参与后续口勺排序。

算法实现：

voidQuicksort(SeqListR,intlow,inthigh)

{〃对R[low..high]迅速排序

intpivotpos；〃划分后的基准记录的位置

ifQow<high){〃仅当区间长度不小于1时才须排序

pivotpos=Partition(R,low,high)：〃对R[low..high]做划分

Quicksort(R,low,pivotpos-1)；〃对左区间递归排序

Quicksort(R,pivotpos+1,high)；〃对右区间递归排序

)

}//Quicksort

三、课程设计中碰到的难点及处理措施

问题：怎样实现对每趟排序成果口勺存储、访问？

处理措施：设计一种并行的存储空间(构造体数组)，存储每趟排序欧I成果，通过指针型参数

传递存储空间的地址实现数据的实时存储。

问题：怎样实现构造体数组作为参数传递数据，并使数组中的数据可以真实的变化，实现类似

于于"（引用）应用的功能?

处理措施：运用指针即将构造体数组的首地址作为一种构造体指针进行参数的传递，由于指针

H勺特性从而实现数据H勺实时传递！

四、总结

课程设计是巩固所学知识理论，提高程序设计H勺重要环节，通过课程设计H勺训练，使我们可以综合应用

数据构造II勺基础知识，加深了对于所学知识II勺理解，也愈加懂得了实践的重要性，也明白了多种算法重

要的是理解其原理，而不是死记硬背！同步让我们愈加理解自身局限性和知识学习缺陷，从而不停完善

自我，提高自己的学习水平。在设计过程中我们真正实现了把所学知识运用于实践，逐渐培养自己的思维

和逻辑能力以及实践能力，做到学以致用。

五、附录一重要源程序代码及运行成果

Sinclude"stdio.h"

#include"malloc.h"

typedefintelemtype;

typedefstruct{〃存储排序数据

elemtype*data;

intlength;

}list;

typedefstruct{〃存储每趟排序数据

elemtype*sqdata;

}sqlist,*linklist;

/*

*设置一种标志位flag,将其初始值设置为非0,表达被排序的表是一种

*无序日勺表，在进行数据互换时，修改flag为0。在新一轮排序开始时，检查

*此标志，若此标志为1,表达上一次没有做过互换数据，则结束排序；否则

*继续排序;

*/

intmaopao(list&1,linklistsql,intx){〃冒泡排序

intflag;

for(inti=l;i<=x;i++){

flag=l;〃标识与否有数据互换

for(intj=l;j<=x-i;j++){

if(1.data[j]>l.data[j+l]){

1.data[0]=l.data[j];

1.data[j]=l.data[j+l];

1.data[j+l]=l.data[0];

flag=0;

)

)

for(intm=l;m<=x;m++)〃每趟排序成果U勺存储

sql[i-l].sqdata[m]=l.data[m];

if(l==flag)break;

)

returni-l;〃返回排序趟数

)

〃直接插入排序

intInsertsort(1ist&1,1inklistsql,intx){

for(inti=2;i<=x;i++){

if(1.data[i]<l.data[i-l]){

1.data[0]=l.datedi];

for(intj=i-l;1.data[0]<l.data[j];j-)

1.data[j+l]=l.data[j];

1.data[j+l]=l.data[0];

}

for(intm=l;m<=x;m++)〃每趟排序成果日勺存储

sql[i-2].sqdata[m]=l.data[in];

)

returni-2;〃返回排序趟数

)

voidqsort(list&1,intlow,inthigh){〃迅速排序(递归)

intpivot;

intleft,right;

1.data[0]=l.data[low];

left=low;

right=high;

if(low<=high){

while(low<high){

while((low<high)&&(1.data[high]>=1.data[0]))

high—;

if(low!=high){

1.data[low]=l.data[high];

low++;

)

while((low<high)&&(1.data[low]<=l.data[0]))

low++;

if(low!=high)(

1.data[high]=l.data[low];

high一;

}

)

1.data[low]=l.data[O];

pivot=low;

if(left<pivot)

q_sort(1,left,high-1);〃递归调用

if(right>pivot)

q_sort(1,high+1,right);

)

else

printf（"未输入数据！”）；

)

〃访问一遍数据并输出最终排序成果

voidtraveresClistL,intx){

printf（"最终排序成果："）;

for(inti=l;i<=x;i++)

printf("%3d",L.data[i]);

prinlf("\n");

printf("***************************************\n\n");

)

voidliststringdist1,linklistsql,intnum,intx){

//输出每趟排序成果

intz;

printf（"共记录有机1趟排序成果，\n”,num）;

traveres(1,x);

printf（〃要查看第几趟排序成果？”)；

scanf(飞d",&z);

printf("An");

printf("***************************************\n\n");

printf("第%d趟排序成果为：”,z);

for(inta=l;a<=x;a++)

printf("%5d”,sql[z-1].sqdata[a]);

printf(/，\n\n，/);

}

voidmainO{〃主函数部分

list1;

intx;

inty;

intnum;

linklistsql;

printf("请输入要排序的数据H勺个数：〃)；

scanf(飞d",&x);

if(x==0)

printf("数据个数不能为0!\n");

else{

1.data=(elemtype*)malloc(x*sizeof(elemtype));〃申请存储空间

sql=(linklist)malloc(x*sizeof(Iinklist));

for(intq=0;q<x;q++)

sql[q].sqdata=(elemtype*)malloc(x*sizeof(elemtype));〃申请存储空间

山―请输入《排序的数据:\ir);

for(inti=l;i<=x;i++){//接受数据

printf("请输入第%d个数据："，i);

scanf(“先d”,&1.data[i]);

)

printf（〃请输入要使用的排序措施：1.冒泡2.直接插入排序、3.迅速排序\n〃）;

printf("您的选择为:〃）；

scanf&y);

printf("***************************************\n");

switch(y){

case1:

printf（"您选择了“冒泡排序”\n〃）；

num=niaopao(1,sql,x);

1iststringO,sql,num,x);

printf(〃***************************************\n");brea.<;

case2:

printf（"您选择了"直接插入排序”\n〃）;

num=Insertsort(1,sql,x);

liststring(l,sql,num,x);

printf("***************************************\n〃)；brea《；

case3:

printf（“您选择了“迅速排序”\n〃）;

qsort(1,1,x);

traveres(l,x);

break;

default:

printf（〃输入错误!〃）;

}

)

printf（"按任意键结束！\n\n\n/，）;

}

ED

青

今

簟

青

第

入

青

第

青

入

青

第

入

主

选

1

34

要查看第几趟排序结果？

2趟排序结果为：2134

安任意键结束!

军MgS

i人要使用的排序方法：工、冒泡2、直接插入排序、3、快速排序

弼逑号L二2

记录有

登

终排序：1234

查看第几趟排序结果？1

1趟排序结果为:3421

<1安任意键结束!

入

耙

要

:据4

，

一

后

数

入

^据

、

，

外

主

入E4

肩:

主

第

入e3

E0引:

主

第

入:E2

E04:

人

第

。E

■*:1

入>

科

序

方法

使^-

J、3、快速排序

选

刑3

二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

二二

-二二

选

“A

-

结

终