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

数 据 结 构

课程设计报告

题 目：
专 业：
班 级：
学 号：
姓 名：
指导老师：
时 间：

8

一、课程设计题目及所涉及知识点
设计题目：排序算法实现
知识点：malloc申请连续存储空间、冒泡排序、快速排序、直接插入排序的算法实现、 结构体的定义与调用、函数的递归调用
二、课程设计思路及算法描述
设计思路：1、确定程序要实现的功能即（1）允许用户输入一组数据，任意多个。
（2）由用户选择对该组数据进行排序的方法：直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的结果。
2、确定程序所需要的功能块，存储结构-结构体，malloc申请存储空间，各功能函数--冒泡排序功能块maopao()；、直接插入排序功能块insertsort()；、快速排序q_sort(）；、数据访问功能块traveres()；、数据输出功能块liststring();主函数部分main()；。
3、编写代码具体实现各项功能，并进行调试。
算法描述： 冒泡排序（Bubble Sorting）的基本思想：
设待排序n个元素存放在数组a[n]中,无序区范围初始为(a(0),a(1),a(2),...,a[n-1]),冒泡排序方法是在当前无序区内,从最上面的元素a[0]开始,对每两个相邻的元素a[i+1]和a[i](i=0,1,...,n-1)进行比较,且使值较小的元素换至值较大的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],...a[n-1]中,这样无序区范围变为(a[0],a[1],a[2],...,a[k])。在当前无序区内进行下一趟冒泡排序。这个过程一直到某一趟排序中不出现元素交换的动作，排序结束。整个排序过程最多执行n-1遍。
算法实现：
void BubbleSort(SeqList R)
//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
{
int i，j；
Boolean exchange； //交换标志
for(i=1;i<n;i++){ //最多做n-1趟排序
exchange=FALSE； //本趟排序开始前，交换标志应为假
for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描
if(R[j+1].key<R[j].key){//交换记录
R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元
R[j+1]=R[j]；
R[j]=R[0]；
exchange=TRUE； //发生了交换，故将交换标志置为真
}
if(!exchange) //本趟排序未发生交换，提前终止算法
return；
} //endfor(外循环)
} //BubbleSort
直接插入排序（Straight Insertion Sorting）的基本思想：
把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].
算法实现：
void insert_sort(ElemType a[],int n)
//待排序元素用一个数组a表示，数组有n个元素
{ int i,j;
ElemType t;
for ( i=1; i<n; i++) //i表示插入次数，共进行n-1次插入
{ t=a[i]; //把待排序元素赋给t
j=i-1;
while ((j>=0)&& (t<a[j])){
a[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)上，它无须参加后续的排序。
算法实现：
void QuickSort(SeqList R，int low，int high)
{ //对R[low..high]快速排序
int pivotpos； //划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R，low，high)； //对R[low..high]做划分
QuickSort(R，low，pivotpos-1)； //对左区间递归排序
QuickSort(R，pivotpos+1，high)； //对右区间递归排序
}
} //QuickSort
三、课程设计中遇到的难点及解决办法
问题：如何实现对每趟排序结果的存储、访问？
解决方法：设计一个并行的存储空间（结构体数组），存储每趟排序的结果，通过指针型参数 传递存储空间的地址实现数据的实时存储。
问题：如何实现结构体数组作为参数传递数据，并使数组中的数据可以真实的改变，实现类 似于“&”(引用)应用的功能？
解决方法：运用指针即将结构体数组的首地址作为一个结构体指针进行参数的传递，由于指 针的特性从而实现数据的实时传递!
四、总结
课程设计是巩固所学知识理论，提高程序设计的重要环节，通过课程设计的训练，使我们能够综合应用数据结构的基础知识，加深了对于所学知识的理解，也更加懂得了实践的重要性，也明白了各种算法重要的是理解其原理，而不是死记硬背！同时让我们更加了解自身不足和知识学习缺陷，从而不断完善自我，提高自己的学习水平。在设计过程中我们真正实现了把所学知识运用于实践，逐渐培养自己的思维和逻辑能力以及实践能力，做到学以致用。

五、附录—主要源程序代码及运行结果
#include "stdio.h"
#include "malloc.h"
typedef int elemtype;

typedef struct { //存储排序数据
elemtype *data;
int length;
}list;
typedef struct{ //存储每趟排序数据
elemtype *sqdata;
}sqlist,*linklist;
/*
* 设置一个标志位flag，将其初始值设置为非0，表示被排序的表是一个
*无序的表，在进行数据交换时，修改flag为0。在新一轮排序开始时，检查
*此标志，若此标志为1，表示上一次没有做过交换数据，则结束排序；否则
*继续排序；
*/
int maopao(list &l,linklist sql,int x){ //冒泡排序
int flag;
for(int i=1;i<=x;i++){
flag=1; //标记是否有数据交换
for(int j=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(int m=1;m<=x;m++) //每趟排序结果的存储
sql[i-1].sqdata[m]=l.data[m];
if(1==flag) break;
}
return i-1; //返回排序趟数
}
//直接插入排序
int Insertsort(list &l,linklist sql,int x){
for(int i=2;i<=x;i++){
if(l.data[i]<l.data[i-1]){
l.data[0]=l.data[i];
for(int j=i-1;l.data[0]<l.data[j];j--)
l.data[j+1]=l.data[j];
l.data[j+1]=l.data[0];
}
for(int m=1;m<=x;m++) //每趟排序结果的存储
sql[i-2].sqdata[m]=l.data[m];
}
return i-2; //返回排序趟数
}
void q_sort(list &l,int low,int high){ //快速排序（递归）
int pivot;
int left,right;
l.data[0]=l.data[low];
left=low;
right=high;
if(low<=high){
while(low<high){
while((low<high) && (l.data[high]>=l.data[0]))
high--;
if(low!=high){
l.data[low]=l.data[high];
low++;
}
while((low<high) && (l.data[low]<=l.data[0]))
low++;
if(low!=high){
l.data[high]=l.data[low];
high--;
}
}
l.data[low]=l.data[0];
pivot=low;
if(left<pivot)
q_sort(l,left,high-1); //递归调用
if(right>pivot)
q_sort(l,high+1,right);
}
else
printf("未输入数据！");
}
//访问一遍数据并输出最终排序结果
void traveres(list L,int x){
printf("最终排序结果：");
for(int i=1;i<=x;i++)
printf("%3d",L.data[i]);
printf("\n");
printf("***************************************\n\n");
}
void liststring(list l,linklist sql,int num,int x){
//输出每趟排序结果
int z;
printf("共记录有%d趟排序结果,\n",num);
traveres(l,x);
printf("要查看第几趟排序结果？ ");
scanf("%d",&z);
printf("\n");
printf("***************************************\n\n");
printf("第%d趟排序结果为：",z);
for(int a=1;a<=x;a++)
printf("%5d",sql[z-1].sqdata[a]);
printf("\n\n");
}
void main(){ //主函数部分
list l;
int x;
int y;
int num;
linklist sql;
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(int q=0;q<x;q++)
sql[q].sqdata=(elemtype *)malloc(x * sizeof(elemtype));//申请存储空间
printf("请输入要排序的数据：\n");
for(int i=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){
case 1:
printf("您选择了“冒泡排序”\n");
num=maopao(l,sql,x);
liststring(l,sql,num,x);
printf("***************************************\n"); break;
case 2:
printf("您选择了“直接插入排序”\n");
num=Insertsort(l,sql,x);
liststring(l,sql,num,x);
printf("***************************************\n"); break;
case 3:
printf("您选择了“快速排序”\n");
q_sort(l,1,x);
traveres(l,x);
break;
default:
printf("输入错误！");
}
}
printf("按任意键结束！\n\n\n");
}

六、指导老师评语及成绩