数据结构课程设计各种排序算法的实现.docx
《数据结构课程设计各种排序算法的实现.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计各种排序算法的实现.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构课程设计各种排序算法的实现
数据结构课程设计（各种排序算法的实现）
数据结构
课程设计报告
题目：
专业：
班级：
学号：
姓名：
指导老师：
时间：
一、课程设计题目及所涉及知识点
设计题目：
排序算法实现
知识点：
malloc申请连续存储空间、冒泡排序、快速排序、直接插入排序的算法实现、结构体的定义与调用、函数的递归调用
二、课程设计思路及算法描述
设计思路：
1、确定程序要实现的功能即
（1）允许用户输入一组数据，任意多个。
（2）由用户选择对该组数据进行排序的方法：
直接插入排序、冒泡排序、快速排序。
并可以查看每趟排序的结果。
2、确定程序所需要的功能块，存储结构-结构体，malloc申请存储空间，各功能函数--冒泡排序功能块maopao（）；、直接插入排序功能块insertsort（）；、快速排序q_sort（）；、数据访问功能块traveres（）；、数据输出功能块liststring（）;主函数部分main（）；。
3、编写代码具体实现各项功能，并进行调试。
算法描述：
冒泡排序（BubbleSorting）的基本思想：
设待排序n个元素存放在数组a[n]中,无序区范围初始为（a（0）,a
（1）,a
（2）,...,a[n-1]）,冒泡排序方法是在当前无序区内,从最上面的元素a[0]开始,对每两个相邻的元素a[i+1]和
R[j+1]=R[j]；
R[j]=R[0]；
exchange=TRUE；//发生了交换，故将交换标志置为真
}
if（!
exchange）//本趟排序未发生交换，提前终止算法
return；
}//endfor（外循环）
}//BubbleSort
直接插入排序（StraightInsertionSorting）的基本思想：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:
先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j（0<=j<=i-1）,使得a[j]<=t或j为（-1）,把t赋值给a[j+1].
算法实现：
voidinsert_sort（ElemTypea[],intn）
//待排序元素用一个数组a表示，数组有n个元素
{inti,j;
ElemTypet;
for（i=1;i{t=a[i];//把待排序元素赋给t
j=i-1;
while（（j>=0）&&（ta[j+1]=a[j];j--;}//顺序比较和移动
a[j+1]=t;}
}
快速排序算法：
在R[low..high]中任选一个记录作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1）和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录（不妨记为pivot）的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置（pivotpos）上，它无须参加后续的排序。
算法实现：
voidQuickSort（SeqListR，intlow，inthigh）
{//对R[low..high]快速排序
intpivotpos；//划分后的基准记录的位置
if（lowpivotpos=Partition（R，low，high）；//对R[low..high]做划分
QuickSort（R，low，pivotpos-1）；//对左区间递归排序
QuickSort（R，pivotpos+1，high）；//对右区间递归排序
}
}//QuickSort
三、课程设计中遇到的难点及解决办法
问题：
如何实现对每趟排序结果的存储、访问？
解决方法：
设计一个并行的存储空间（结构体数组），存储每趟排序的结果，通过指针型参数传递存储空间的地址实现数据的实时存储。
问题：
如何实现结构体数组作为参数传递数据，并使数组中的数据可以真实的改变，实现类似于“&”（引用）应用的功能？
解决方法：
运用指针即将结构体数组的首地址作为一个结构体指针进行参数的传递，由于指针的特性从而实现数据的实时传递!
四、总结
课程设计是巩固所学知识理论，提高程序设计的重要环节，通过课程设计的训练，使我们能够综合应用数据结构的基础知识，加深了对于所学知识的理解，也更加懂得了实践的重要性，也明白了各种算法重要的是理解其原理，而不是死记硬背！
同时让我们更加了解自身不足和知识学习缺陷，从而不断完善自我，提高自己的学习水平。
在设计过程中我们真正实现了把所学知识运用于实践，逐渐培养自己的思维和逻辑能力以及实践能力，做到学以致用。
五、附录—主要源程序代码及运行结果
#include"stdio.h"
#include"malloc.h"
typedefintelemtype;
typedefstruct{//存储排序数据
elemtype*data;
intlength;
}list;
typedefstruct{//存储每趟排序数据
elemtype*sqdata;
}sqlist,*linklist;
/*
*设置一个标志位flag，将其初始值设置为非0，表示被排序的表是一个
*无序的表，在进行数据交换时，修改flag为0。
在新一轮排序开始时，检查
*此标志，若此标志为1，表示上一次没有做过交换数据，则结束排序；否则
*继续排序；
*/
intmaopao（list&l,linklistsql,intx）{//冒泡排序
intflag;
for（inti=1;i<=x;i++）{
flag=1;//标记是否有数据交换
for（intj=1;j<=x-i;j++）{
if（l.data[j]>l.data[j+1]）{
l.data[0]=l.data[j];
l.data[j]=l.data[j+1];
l.data[j+1]=l.data[0];
flag=0;
}
}
for（intm=1;m<=x;m++）//每趟排序结果的存储
sql[i-1].sqdata[m]=l.data[m];
if（1==flag）break;
}
returni-1;//返回排序趟数
}
//直接插入排序
intInsertsort（list&l,linklistsql,intx）{
for（inti=2;i<=x;i++）{
if（l.data[i]l.data[0]=l.data[i];
for（intj=i-1;l.data[0]l.data[j+1]=l.data[j];
l.data[j+1]=l.data[0];
}
for（intm=1;m<=x;m++）//每趟排序结果的存储
sql[i-2].sqdata[m]=l.data[m];
}
returni-2;//返回排序趟数
}
voidq_sort（list&l,intlow,inthigh）{//快速排序（递归）
intpivot;
intleft,right;
l.data[0]=l.data[low];
left=low;
right=high;
if（low<=high）{
while（lowwhile（（low=l.data[0]））
high--;
if（low!
=high）{
l.data[low]=l.data[high];
low++;
}
while（（lowlow++;
if（low!
=high）{
l.data[high]=l.data[low];
high--;
}
}
l.data[low]=l.data[0];
pivot=low;
if（leftq_sort（l,left,high-1）;//递归调用
if（right>pivot）
q_sort（l,high+1,right）;
}
else
printf（"未输入数据！
"）;
}
//访问一遍数据并输出最终排序结果
voidtraveres（listL,intx）{
printf（"最终排序结果：
"）;
for（inti=1;i<=x;i++）
printf（"%3d",L.data[i]）;
printf（"\n"）;
printf（"***************************************\n\n"）;
}
voidliststring（listl,linklistsql,intnum,intx）{
//输出每趟排序结果
intz;
printf（"共记录有%d趟排序结果,\n",num）;
traveres（l,x）;
printf（"要查看第几趟排序结果？
"）;
scanf（"%d",&z）;
printf（"\n"）;
printf（"***************************************\n\n"）;
printf（"第%d趟排序结果为：
",z）;
for（inta=1;a<=x;a++）
printf（"%5d",sql[z-1].sqdata[a]）;
printf（"\n\n"）;
}
voidmain（）{//主函数部分
listl;
intx;
inty;
intnum;
linklistsql;
printf（"请输入要排序的数据的个数：
"）;
scanf（"%d",&x）;
if（x==0）
printf（"数据个数不能为0！
\n"）;
else{
l.data=（elemtype*）malloc（x*sizeof（elemtype））;//申请存储空间
sql=（linklist）malloc（x*sizeof（linklist））;
for（intq=0;qsql[q].sqdata=（elemtype*）malloc（x*sizeof（elemtype））;//申请存储空间
printf（"请输入要排序的数据：
\n"）;
for（inti=1;i<=x;i++）{//接收数据
printf（"请输入第%d个数据：
",i）;
scanf（"%d",&l.data[i]）;
}
printf（"请输入要使用的排序方法：
1、冒泡2、直接插入排序、3、快速排序\n"）;
printf（"您的选择为：
"）;
scanf（"%d",&y）;
printf（"***************************************\n"）;
switch（y）{
case1:
printf（"您选择了“冒泡排序”\n"）;
num=maopao（l,sql,x）;
liststring（l,sql,num,x）;
printf（"***************************************\n"）;break;
case2:
printf（"您选择了“直接插入排序”\n"）;
num=Insertsort（l,sql,x）;
liststring（l,sql,num,x）;
printf（"***************************************\n"）;break;
case3:
printf（"您选择了“快速排序”\n"）;
q_sort（l,1,x）;
traveres（l,x）;
break;
default:
printf（"输入错误！
"）;
}
}
printf（"按任意键结束！
\n\n\n"）;
}
六、指导老师评语及成绩
升级会员 