数据结构排序课程设计 程序.docx
- 文档编号:10544921
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:14
- 大小:16.24KB
数据结构排序课程设计 程序.docx
《数据结构排序课程设计 程序.docx》由会员分享,可在线阅读,更多相关《数据结构排序课程设计 程序.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构排序课程设计程序
#include
#include
#defineN7//产生随机数的个数
//定义两个节点
structnode
{
intkey;
}table[20];
structrnode
{
intkey;
intnext;
};
//打印随机数
voidprint(structnodea[20],intn)
{
inti;
for(i=0;i printf("%8d",a[i].key); printf("\n"); } //创建随机数 intCreat_rand(void) { intn; srand(0); randomize();//对随机数发生器进行初始化 for(n=0;n table[n].key=random(1000);//产生随机数 return(n); } ////////////////////快速排序/////////////////////////// inthoare(structnodea[20],intl,inth) //分区处理函数 { inti,j; structnodex; i=l; j=h; x.key=a[i].key; do { while((i j--; if(i { a[i].key=a[j].key; i++; } while((i i++; if(i { a[j].key=a[i].key; j--; } }while(i a[i].key=x.key; return(i); } voidKuai_Su(structnodea[20],intn) //快速排序 { inti,l,h,tag,top; ints[20][2]; l=0;h=n-1;tag=1;top=0; do { while(l { i=hoare(a,l,h); top++; s[top][0]=i+1; s[top][1]=h; h=h-1; } if(top==0) tag=0; else { l=s[top][0]; h=s[top][1]; top--; } }while(tag==1); printf("输出快速排序结果: \n"); } ////////////////////快速排序结束//////////////////////// ////////////////////堆排序函数////////////////////////// voidHeap_Change(structnodea[20],inti,intm) //调整堆的函数 { structnodex; intj; x.key=a[i].key; j=2*i; while(j<=m) { if(j if(a[j].key>a[j+1].key) j++; if(a[j].key { a[i].key=a[j].key; i=j; j=2*i; } else j=m+1; } a[i].key=x.key; } voidDui(structnodea[20],intn) //堆排序的主体部分调用函数 { inti,v; structnodex; for(i=n;i>0;i--) a[i].key=a[i-1].key; for(i=n/2;i>=1;i--) Heap_Change(a,i,n); printf("输出堆排序结果: \n"); for(v=n;v>=2;v--) { printf("%8d",a[1].key); x.key=a[1].key; a[1].key=a[v].key; a[v].key=x.key; Heap_Change(a,1,v-1); } printf("%8d",a[1].key); for(i=0;i a[i].key=a[i+1].key; } /////////////////堆排序函数结束/////////////////// //////////////////归并函数//////////////////////// voidmerges(structnodea[20],structnodea2[20],inth1,intmid,inth2) //归并排序的核心算法 { inti,j,k; i=h1;j=mid+1;k=h1-1; while((i<=mid)&&(j<=h2)) { k=k+1; if(a[i].key<=a[j].key) { a2[k].key=a[i].key; i++; } else { a2[k].key=a[j].key; j++; } } while(i<=mid) { k++; a2[k].key=a[i].key; i++; } while(j<=h2) { k++; a2[k].key=a[j].key; i++; } } voidmergepass(structnodea[20],structnodea2[20],intl,intn) //一趟归并 { intj,i,h1,mid,h2; i=0; while((n-i)>=2*l) { h1=i; mid=h1+l-1; h2=i+2*l-1; merges(a,a2,h1,mid,h2); i=i+2*l; } if((n-i)<=l) for(j=i;j<=n;j++) a2[j].key=a[j].key; else { h1=i; mid=h1+l-1; h2=n-1; merges(a,a2,h1,mid,h2); } } voidMerger(structnodea[20],intn) { intl; structnodea2[20]; l=1; while(l { mergepass(a,a2,l,n); l=2*l; mergepass(a2,a,l,n); l=2*l; } printf("输出归并排序的结果: \n"); } ///////////////归并函数结束/////////////// ///////////////基数排序/////////////////// intyx(intm,inti)//分离关键字倒数第i位有效数字的算法 { intx; switch(i) { case1: x=m%10;break; case2: x=(m%100)/10;break; case3: x=(m%1000)/100;break; case4: x=(m%10000)/1000;break; } return(x); }//yxend intradixsort(structrnodea[20],intn) { intf[11],e[11],i,j,k,l,p,d,t; for(i=1;i<=n;i++) { a[i].key=table[i-1].key; a[i].next=i+1; } a[n].next=0; p=1; printf("输出关键字有效位数d\n"); scanf("%d",&d); printf("输出基数排序的结果: \n"); for(i=1;i<=d;i++) { for(j=0;j<=10;j++) { f[j]=0; e[j]=0; } while(p! =0) { k=yx(a[p].key,i); if(f[k]==0) { f[k]=p; e[k]=p; } else { l=e[k]; a[l].next=p; e[k]=p; } p=a[p].next; } j=0; while(f[j]==0) j++; p=f[j]; t=e[j]; while(j<10) { j++; while((j<10)&&(f[j]==0)) j++; if(f[j]! =0) { a[t].next=f[j]; t=e[j]; } } a[t].next=0; t=p; while(t! =0) { printf("%5d",a[t].key); t=a[t].next; } printf("\n"); } return(p); } //希尔排序 voidshell(structnodea[20],intn) { inti,j,k; for(i=n;i>=1;i--) a[i].key=a[i-1].key; k=n/2; while(k>=1) { for(i=k+1;i<=n;i++) { a[0].key=a[i].key; j=i-k; while((a[j].key>a[0].key)&&(j>=0)) { a[j+k].key=a[j].key; j=j-k; } a[j+k]=a[0]; } k=k/2; } for(i=0;i a[i].key=a[i+1].key; printf("输出希尔排序的结果: \n"); } voidmain(void) { intnum,c; structrnodes[20]; c=1; printf("\n\t\t1、产生7个随机数"); printf("\n\t\t2、快速排序"); printf("\n\t\t3、希尔排序"); printf("\n\t\t4、堆排序"); printf("\n\t\t5、基数排序"); printf("\n\t\t6、归并排序"); printf("\n\t\t(提示先按数字1,产生随机数)"); printf("\n\t\t输入选择<1--6>: "); while(c! =0)//接受字符 { //开始输入数字 scanf("%d",&c); switch(c) { case1: num=Creat_rand(); print(table,num); break; case2: Kuai_Su(table,num); print(table,num); ;break; case3: shell(table,num); print(table,num); break; case4: Dui(table,num); break; case5: Merger(table,num); print(table,num); break; case6: radixsort(s,num); } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构排序课程设计 程序 数据结构 排序 课程设计