数据结构课程设计(各种排序算法的实现).pdf
；数数据据结结构构课程设计报告课程设计报告】题目：专业：班级：学号：姓名：指导老师：时间：一、课程设计题目及所涉及知识点一、课程设计题目及所涉及知识点设计题目：排序算法实现知识点：malloc 申请连续存储空间、冒泡排序、快速排序、直接插入排序的算法实现、结构体的定义与调用、函数的递归调用二、课程设计思路及算法描述二、课程设计思路及算法描述设计思路：设计思路：1、确定程序要实现的功能即（1）允许用户输入一组数据，任意多个。（2）由用户选择对该组数据进行排序的方法：直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的结果。2、确定程序所需要的功能块，存储结构-结构体，malloc 申请存储空间，各功能函数-冒泡排序功能块 maopao()；、直接插入排序功能块insertsort()；、快速排序q_sort(）；、数据访问功能块 traveres()；、数据输出功能块 liststring();主函数部分 main()；。3、编写代码具体实现各项功能，并进行调试。算法描述：算法描述：冒泡排序（冒泡排序（Bubble SortingBubble Sorting）的基本思想：）的基本思想：设待排序n个元素存放在数组an中,无序区范围初始为(a(0),a(1),a(2),.,an-1),冒泡排序方法是在当前无序区内,从最上面的元素 a0开始,对每两个相邻的元素 ai+1和ai(i=0,1,.,n-1)进行比较,且使值较小的元素换至值较大的元素之上(若 aiai+1,则 ai和 ai+1的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为 ak,则无序区中值较大的几个元素到达下端并从小到大依次存放在 ak+1,ak+2,.an-1中,这样无序区范围变为(a0,a1,a2,.,ak)。在当前无序区内进行下一趟冒泡排序。这个过程一直到某一趟排序中不出现元素交换的动作，排序结束。整个排序过程最多执行n-1 遍。算法实现：算法实现：void BubbleSort(SeqList R)n)是待排序的文件，采用自下向上扫描，对R 做冒泡排序int i，j；Boolean exchange；n自下向上扫描if(Rj+1.keyRj.key).,ai-1之中的具体实施过程为:先把 ai赋值给变量 t,然后将 t 依次与 ai-1,ai-2,.进行比较,将比 t 大的元素右移一个位置,直到发现某个 j(0=j=i-1),使得 aj=t 或 j 为(-1),把 t 赋值给 aj+1.算法实现：算法实现：void insert_sort(ElemType a,int n)high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间 Rlow.pivotpos-1)和 Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为 pivot)的关键字，右边的子区间中所有记录的关键字均大于等于，而基准记录pivot 则位于正确的位置(pivotpos)上，它无须参加后续的排序。算法实现：算法实现：void QuickSort(SeqList R，int low，int high)high快速排序int pivotpos；high做划分QuickSort(R，low，pivotpos-1)；qdatam=m;if(1=flag)break;return i-1;qdatam=m;return i-2;qdataa);printf(nn);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(按任意键结束！nnn);六、指导老师评语及成绩六、指导老师评语及成绩
