c希尔排序和堆排序-课程设计报告

《c希尔排序和堆排序-课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号16082202032016-2017学年第二学期《C语言程序设计》课程设计报告希尔排序和堆排序专业:网络工程班级：16级网工（3）班姓名：代应豪指导教师：代美丽成绩:计算机学院2017年4月24日目录1需求分析13•152概要设计15•173详细设计18•254调试结果26•295课程设计总结29•30参考书冃:30希尔排序算法例子：#includevoidStraightlnsertionSort(intk[]zintn){intij.temp;intgap=n;do{gap=gap/3+1;for(i=gap;ivn;

2、i++){if(k[i]temp;j-=gap){k[j+gap]二k[j];}k[j+gap]二temp;}}}while(gap>l);inti,a[10]={2,3,4,5,1,4,2,4,5,61;StraightlnsertionSort(a,10);printf(n排序后为！n);for(i=0;i<10;i++){printf(“％cTa[i]);}printf("H);return0;}输入输出结果：•3•OAttmOebugXJmaff.exe*

3、-□X1223444556essanykeytocontinue2:堆排序算法例子:/*2017年4月24日16:48:33描述：堆排序输岀结果:请输入创建链表的长度（长度小于20））length=9请输入数据第1个元素:50请输入数据第2个元素:10请输入数据第3个元素:90请输入数据第4个元素:30请输入数据第5个元素:70请输入数据第6个元素:40请输入数据第7个元素:80请输入数据第8个元素:60请输入数据第9个元素:20原始链表输出:501090307040806020堆排序后输出链表，由小到大输出:102030405060708090

4、*/#include#defineMAXSiZE20typedefstruct{inta[MAXSiZE];intlength;}Sqlist,*pSqlist;〃函数声明intCreatList(Sqlist*L);intShowList(Sqlist*L);voidswap(Sqlist*L,inti,intj);voidHeapSort(Sqlist*L);〃堆排序函数声明voidHeapAdjust(Sqlist*L,ints,intm);〃堆调整函数声明intmain(){SqlistL;〃创建并显小链表CreatLi

5、st(&L);printf(”原始链表输出:H)；ShowList(&L);〃堆排序HeapSort(&L);printf(H堆排序后输出链表,由小到大输出:H)；ShowList(&L);return0;〃创建链表intCreatList(Sqlist*L){inti;//SqListL;intlength;printf(n请输入创建链表的长度(长度小于20))length=H);scanf("%d,,/&length);for(i=1;i<=length;i++){printf(”请输入数据第%d个元素:",i);//scanf("%

6、dH/&list.data[i]);scanf(H%dH,&L->a[i]);L->length=length;return0;〃输出链表intShowList(Sqlist*L){inti;for(i=1;i<=L->length;i++){printfC1%d,,/L->a[i]);}printf(Hn);return0;}〃数据交换voidswap(Sqlist*L,inti,intj)inttemp=0;temp=L->a[i];L->a[i]=L->a[j];L->a[j]=temp;}〃对调整函数，调整成为一个大顶堆voidHea

7、pAdjust(Sqlist*LZints,intm){inttemp,j;temp=L->a[s];for(j=2*s;j<=m;j*=2)〃沿关键字较大的孩子节点向下筛选{if(ja[j]a[j+l]){++j；〃j为关键字中较大的记录下标}if(temp>=L->a[j])break;L->a[s]=L->a[j]；s=j；}L->a[s]=temp;〃插入}〃对顺序表进行堆排序voidHeapSort(Sqlist*L){inti;for(i=L->length/2;i>0;i・・)〃把链表中的a中数据构成一个大顶堆

8、HeapAdjust(L,i,L->length);for(i=L->1ength;i>l;i-)swap(L,1,i);〃将堆顶记录和