《各种排序算法C语言实现(共21页).docx》由会员分享，可在线阅读，更多相关《各种排序算法C语言实现(共21页).docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上#include #include #define Max 20 /最大顶点数/顺序存储方式使用的结构体定义typedef struct vexTypechar data;int indegree;Vex;typedef struct Graphint vexnum; /顶点数量int arcnum; /边数Vex vex_arrayMax; /存放顶点的数组int arc_arrayMaxMax; /存放邻接矩阵的二维数组Graph; /图的定义/链式存储使用的结构体定义typedef struct arcTypechar vex1,vex2; /边所依附的两点in
2、t arcVal; /边的权值Arc; /边的定义typedef struct LinkTypeint index; /在顶点表的下标struct LinkType *nextarc; /指向下一个顶点结点LinkNode; /边表定义typedef struct vexNodechar data;int add; /在顶点数组的下表位置LinkNode *firstarc; /指向边表的第一个结点int indegree; /入度VexNode; /顶点边定义typedef struct LGraphVexNode vex_arrayMax; /顶点数组 int vexnum; /图中顶点数
3、LGraph;/*函数功能：图的创建 入口参数：图G 返回值：无*/void Creat_G(Graph *G)char v;int i=0;int j=0;G-vexnum=0;printf(输入说明。有权值请输入权值，无权值请输入1，无边请输入0n);printf(n请输入所有顶点(不超过20个，按#结束输入)：n);doprintf(输入第 %d 个顶点：,G-vexnum+1);scanf( %c,&v);G-vex_arrayG-vexnum.data = v;G-vexnum+;while(v!=#);G-vexnum-;printf(输入邻接矩阵（%d * %d）：,G-vexn
4、um,G-vexnum);for(i=0; ivexnum; i+)printf(输入 %c 到以下各点的权值：n,G-vex_arrayi.data);for(j=0; jvexnum; j+)printf(: ,G-vex_arrayi.data,G-vex_arrayj.data);scanf(%d,&G-arc_arrayij);printf(n构建图的顶点为：n);for(i=0; ivexnum; i+)printf(%c ,G-vex_arrayi.data);printf(n构建图的邻接矩阵为：n);for(i=0; ivexnum; i+)for(j=0; jvexnum;
5、j+)printf(%d ,G-arc_arrayij);printf(n);/*函数功能：统计各点的入度 入口参数：指向图的指针*G 返回值：无*/void Count_indegree(Graph *G)int i;int j;for(j=0; jvexnum; j+)G-vex_arrayj.indegree =0;for(i=0; ivexnum; i+)if(G-arc_arrayij!=0)G-vex_arrayj.indegree+;/*函数功能：对邻接矩阵进行拓扑排序 入口参数：指向图的指针*G 返回值：无*/void Topol_sort(Graph *G)int i,j;c
6、har topoMax; /存放拓扑排序的结果int count=0; /记录topo中的元素个数，便于与vexnum比较，判断是有环图还是无环图char stackMax; /存放indegree=0的顶点所在vex_array中的下标int top=0; /栈的指针int bool=1; /弹栈的标准int no; /接收stack栈中弹出的顶点下标for(i=0; ivexnum; i+)if(G-vex_arrayi.indegree=0)stacktop = i;top+;doif(top=-1)bool=0;elsetop-;no = stacktop;topocount = G-
7、vex_arrayno.data;count+;for(j=0; jvexnum; j+)if(G-arc_arrayij!=0)G-vex_arrayj.indegree-;if(G-vex_arrayj.indegree=0)stacktop = j;top+;while(bool=1);count-;if(count vexnum)printf(n结果：原图中有环，无法形成拓扑序列!n);elseprintf(n结果：原图的拓扑序列为：n);for(i=0; ivexnum = 0;printf(n输入说明。有权值请输入权值，无权值请输入1，无边请输入0n);printf(n请输入所有顶
8、点(不超过20个，按#结束输入)n);doprintf(输入第 %d 个顶点：,T-vexnum+1);scanf( %c,&v);T-vex_arrayT-vexnum.data = v;T-vex_arrayT-vexnum.firstarc = NULL;T-vexnum+;while(v!=#);T-vexnum-;for(i=0; ivexnum; i+)f=1;printf(n以顶点 %c 为始点是否有边(Y / N): ,T-vex_arrayi);scanf( %c,&answer);if(answer=Y)printf(输入以 %c 为始点的所有终点个数：,T-vex_arr
9、ayi);scanf(%d,&count);for(j=0; jnextarc=NULL;printf(输入第 %d 个顶点：,j+1);scanf( %c,&v);for(k=0; kvexnum; k+)if(v=T-vex_arrayk.data)p-index = k; /找到该元素，并记录下标if(f=1) /是第一个结点,放在T-vex_arrayi.firstarc上T-vex_arrayi.firstarc = p;q = p;f = 0;elseq-nextarc = p;q = p;printf(创建链表为:n);for(i=0; ivexnum; i+)printf(%c
10、 -,T-vex_arrayi.data);p = T-vex_arrayi.firstarc;while(p!=NULL)printf(%c -,T-vex_arrayp-index.data);p=p-nextarc;printf(NULLn);/*函数功能：统计各个点的入度 入口参数：指向图的指针*T 返回值:无*/void Count_T_indegree(LGraph *T)int i;LinkNode *p=NULL;for(i=0; ivexnum; i+)T-vex_arrayi.indegree = 0;for(i=0; ivexnum; i+)p = T-vex_array
11、i.firstarc;while(p!=NULL)T-vex_arrayp-index.indegree+;p=p-nextarc;/*函数功能：拓扑排序 入口参数：指向图的指针*T 返回值：无*/void L_Topol_sort(LGraph *T)int i,j;int no;int stackMax;int top=0;int topoMax;int count=0;int bool=1;LinkNode *p=NULL;for(i=0; ivexnum; i+)if(T-vex_arrayi.indegree=0)stacktop = i;top+;doif(top=0)bool=0
12、;elsetop-;no = stacktop;topocount = T-vex_arrayno.data;count+;p = T-vex_arrayno.firstarc;while(p!=NULL)T-vex_arrayp-index.indegree-;if(T-vex_arrayp-index.indegree=0)stacktop = p-index;top+;p = p-nextarc;while(bool=1);/printf(检测n);if(count vexnum)printf(原图有环，无法形成拓扑排序！n);elseprintf(原图的拓扑排序为：n);for(i=0
13、; icount; i+)printf(%c ,topoi);/*函数功能：邻接链表及拓扑排序 入口参数：指向图的指针*T 返回值：无*/void LinJieLianBiao(LGraph *T)int choice;printf(n1 图的创建(针对有向图)n2 拓扑排序n0 退出n);doprintf(n请选择：);scanf(%d,&choice);switch(choice)case 1:Creat_LinkT(T);printf(图已创建完成！n);break;case 2:Count_T_indegree(T);L_Topol_sort(T);break;case 0:break
14、;if(choice=0)break;while(choice!=0);void main()int choice;/邻接矩阵中的变量 Graph G;LGraph T;printf(-nn);printf(1、 图的顺序存储-邻接矩阵并进行拓扑排序n2、 图的连式存储-邻接链表并进行拓扑排序n0、 退出n);doprintf(请选择主菜单操作：);scanf(%d,&choice);switch(choice)case 1:printf(n*图的顺序存储-邻接矩阵*n);LinJieJuZhen(&G);break;case 2:printf(n*图的链式存储-邻接链表*n);LinJieL
15、ianBiao(&T);break;case 0:exit(0);default:printf(输入错误！n);break;while(choice!=0);#include #include #define Max 20typedef struct listint arrayMax;int length;List;/*数组复制*/void Copy(List *L,List *Lx)int i;Lx-length = L-length;for(i=1; ilength; i+)Lx-arrayi = L-arrayi;/*创建顺序表*/void Creat(List *L)int data=
16、0;int i;L-length=1;printf(输入数据，以-100为结束输入标志n);while(data!=-100)printf(输入第 %d 个元素值：,L-length);scanf(%d,&data);L-arrayL-length = data;L-length+;L-length = L-length-2;printf(输入的元素值为：);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/*直接插入排序*/void ZhiJieChaRu_sort(List *L)int i;int j;for(i=2; ilengt
17、h; i+)if(L-arrayi arrayi-1)L-array0 = L-arrayi;L-arrayi = L-arrayi-1;for(j=i-2; L-array0 arrayj; j-)L-arrayj+1 = L-arrayj;L-arrayj+1 = L-array0;printf(n-直接插入法排序结果为-n);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/*二分法排序*/void ErFenFa_sort(List *L)int i;int j;int low;int high;int mid;for(i=2;
18、ilength; i+)low = 1;high = i-1;L-array0 = L-arrayi;while(low array0 arraymid)high = mid - 1;elselow = mid + 1;for(j=i-1; j=high+1; j-)L-arrayj+1 = L-arrayj;L-arrayhigh+1 = L-array0;printf(n-二分法排序结果为-n);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/一次增量下的希尔排序void Shell_pass(List *L,int d)int i
19、;int j;for(i=d+1; ilength; i+)if(L-arrayi arrayi-d)L-array0 = L-arrayi;L-arrayi = L-arrayi-d;for(j=i-2*d; j0 & L-array0arrayj; j-)L-arrayj = L-arrayj-d;L-arrayj+d = L-array0;/希尔排序void Shell_sort(List *L,int d)int i;for(i=0; i4; i+) /一次取出d中的增量值Shell_pass(L,di);printf(n-希尔排序结果为-n);for(i=1; ilength; i+
20、)printf(%d ,L-arrayi);printf(n);/冒泡排序void MaoPao_sort(List *L)int i;int j;int flag=1; /问题：课件上显示为已注销的部分，但是无法排序（没有交换=？=已经排好了）for(i=1; ilength; i+) /控制趟数/flag=1;for(j=1; jlength-i; j+) /一趟的循环,第i趟结束后就筛选出第i个最小值，所以只需从前length-i个中冒出最小值if(L-arrayj+1 arrayj)flag=0;L-array0 = L-arrayj+1;L-arrayj+1 = L-arrayj;L
21、-arrayj = L-array0;/if(flag=1)/break;printf(n-冒泡排序结果为-n);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/快速排序的一次枢轴定位int KuaiSu_sort(List *L, int low, int high)int pivotkey; /枢轴L-array0 = L-arraylow; /每次排序序列的第一个值作为枢轴,即low作为枢轴pivotkey = L-arraylow;while(low high)while(lowhigh & pivotkeyarrayhigh)
22、 /无论是哪种退出循环方式，都恰好是high的位置就是枢轴位置high-;if(lowarraylow = L-arrayhigh;low+;while(low=L-arraylow)low+;if(lowarrayhigh = L-arraylow;high-;/整个循环退出就得到枢轴在真正序列中的位置为low（也是high）L-arraylow = L-array0;/*printf(n-分步排序结果为-n);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);*/return low;/完整快速排序void KuaiSuPaiXu_so
23、rt(List *L,int low,int high)int pivotloc; /接收一次枢轴定位的位置if(low high)pivotloc = KuaiSu_sort(L,low,high); /也可写为(L,low,pivotkey-1)KuaiSuPaiXu_sort(L,low,pivotloc-1);KuaiSuPaiXu_sort(L,pivotloc+1,high); /也可写为(L,high,pivotkey-1)/简单选择排序void JianDanXuanZe_sort(List *L)int i;int j;int min;for(i=1; ilength; i+
24、) /冒泡排序的最后一个值不用参与比较min = i;for(j=i+1; jlength; j+)if(L-arrayj arraymin)min = j;if(min!=i)L-array0 = L-arraymin;L-arraymin = L-arrayi;L-arrayi = L-array0;printf(n-简单选择排序结果为-n);for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/* 2路归并排序一趟合并 函数功能：将Ls.m 和 Lm+1.t和并为Ts.t 入口参数：原列表L，合并后的列表T,起始值s,中间值m，终点值t
25、 返回值：无void GuiBing_pass(List *L,List *T,int s,int m,int t)int i;int j;int k=1;for(i=1,j=m+1; i=m,jarrayi arrayj)T-arrayk = L-arrayi+;elseT-arrayk = L-arrayj+;while(i arrayk+ = L-arrayi+;while(jarrayk+ = L-arrayj+;2-归并排序递归分解 函数功能：将Ls.t归并为T2s.t,再将T2s.t归并为T1s.tvoid GuiBing_sort(List *L,List *T1,int s,i
26、nt t)int m;List Tx;List *T2 = &Tx;Tx.length = 6;if(s=t)L-arrays = T2-arrays;elsem = (s+t)/2;GuiBing_sort(L,T2,s,m);GuiBing_sort(L,T2,m+1,t);GuiBing_pass(T2,T1,s,m,t);*/void main()int choice;int i;int d4 = 7,5,3,1; /希尔排序的增量数组List L;List Lx; /每次使用一中排序后就会对数组改变，所以复制下来检测每一种排序方法List T; /存放2路归并排序的结果T.lengt
27、h = 6;printf(1 创建顺序表n2 直接插入排序n3 二分法插入排序n4 希尔排序n5 冒泡排序n6 快速排序n7 简单选择排序n0 退出n);doprintf(请选择：);scanf(%d,&choice);switch(choice)case 1:Creat(&L);break;case 2:Copy(&L,&Lx);ZhiJieChaRu_sort(&Lx);break;case 3:Copy(&L,&Lx);ErFenFa_sort(&Lx);break;case 4:Copy(&L,&Lx);Shell_sort(&Lx,d);break;case 5:Copy(&L,&L
28、x);MaoPao_sort(&Lx);break;case 6:Copy(&L,&Lx);KuaiSuPaiXu_sort(&Lx,1,Lx.length);printf(n-快速排序结果为-n);for(i=1; i=Lx.length; i+)printf(%d ,Lx.arrayi);printf(n);break;case 7:Copy(&L,&Lx);JianDanXuanZe_sort(&Lx);break;/*case 8:Copy(&L,&Lx);GuiBing_sort(&Lx,&T,1,Lx.length);printf(n-2-路排序结果为-n);for(i=1; i=Lx.length; i+)printf(%d ,T.arrayi);printf(n);break;*/case 0:printf(退出操作!n);exit(0);break;default :printf(输入错误);break;while(choice!=0);专心-专注-专业