;
数据结构
课程设计报告
】
题目:
专业:
班级:
学号:
姓名:
指导老师:
时间:
~
一、课程设计题目及所涉及知识点
设计题目:排序算法实现
知识点: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)
n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
{
int i,j;
Boolean exchange; n]自下向上扫描
if(R[j+1].key 个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1]. 算法实现: void insert_sort(ElemType a[],int n) high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的 关键字均小于等于基准记录(不妨记为pivot)的关键字,右边的子区间中所有记录的关键字 均大于等于,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。 算法实现: void QuickSort(SeqList R,int low,int high) { high]快速排序 int pivotpos; high]做划分 QuickSort(R,low,pivotpos-1); qdata[m]=[m]; if(1==flag) break; } return i-1; qdata[m]=[m]; } return i-2; qdata[a]); printf("\n\n"); } void main(){ qdata=(elemtype *)malloc(x * sizeof(elemtype));//申请存储空间printf("请输入要排序的数据:\n"); for(int i=1;i<=x;i++){ //接收数据 printf("请输入第%d个数据:",i); scanf("%d",&[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"); } 六、指导老师评语及成绩<