各种排序算法C语言实现

1、各种排序算法 C 语言实现#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; /

2、 边所依附的两点int 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; / 顶点数

3、组 int vexnum; / 图中顶点数LGraph;/* 函数功能：图的创建 入口参数：图 G 返回值：无*/void Creat_G(Graph *G)char v;int i=0;int j=0;G-vexnum=0;0n);printf( 输入说明。有权值请输入权值，无权值请输入 1，无边请输入 printf(n 请输入所有顶点 ( 不超过 20 个，按 #结束输入 )： n); doprintf( 输入第 %d 个顶点： ,G-vexnum+1); scanf( %c,&v);G-vex_arrayG-vexnum.data = v;G-vexnum+;while(v!=#);G-

4、vexnum-;printf( 输入邻接矩阵( %d * %d)： ,G-vexnum,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);17 / 21printf(n 构建图的顶点为： n);for(i=0; ivexnum; i+)printf(%c ,G-vex_arrayi.data);print

5、f(n 构建图的邻接矩阵为： n); for(i=0; ivexnum; i+)for(j=0; jvexnum; 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+; /* 函数功能：对邻

6、接矩阵进行拓扑排序 入口参数：指向图的指针 *G 返回值：无*/void Topol_sort(Graph *G)int i,j;char 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.in

7、degree=0) stacktop = i; top+;doif(top=-1) bool=0;else top-; no = stacktop;topocount = G-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);elsepr

8、intf(n 结果：原图的拓扑序列为： n);for(i=0; ivexnum = 0;0n);printf(n 输入说明。有权值请输入权值，无权值请输入1，无边请输入printf(n 请输入所有顶点 ( 不超过 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;pri

9、ntf(n 以顶点 %c 为始点是否有边 (Y / N): ,T-vex_arrayi); scanf( %c,&answer);if(answer=Y)printf( 输入以 %c 为始点的所有终点个数： ,T-vex_arrayi); 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_a

10、rrayi.firstarc 上 T-vex_arrayi.firstarc = p;q = p;f = 0;elseq-nextarc = p;q = p;printf( 创建链表为 :n);for(i=0; ivexnum; i+)printf(%c ,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 Coun

11、t_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_arrayi.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;i

12、nt 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;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.indegre

13、e=0)stacktop = p-index; top+;p = p-nextarc;while(bool=1);/printf( 检测 n);if(count vexnum)printf( 原图有环，无法形成拓扑排序！ n);elseprintf( 原图的拓扑排序为： n);for(i=0; icount; i+)printf(%c ,topoi);/* 函数功能：邻接链表及拓扑排序入口参数：指向图的指针 *T返回值：无*/void LinJieLianBiao(LGraph *T)int choice;printf(n1 图的创建 (针对有向图 )n2 拓扑排序 n0 退出 n);dopr

14、intf(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;if(choice=0) break;while(choice!=0);void main()int choice;/ 邻接矩阵中的变量Graph G;LGraph T;printf(nn);-邻接链表并printf(1 、 图的顺序存储 -邻接矩阵并进行拓扑排序 n2 、 图的连式存

15、储 进行拓扑排序 n0 、 退出 n);doprintf( 请选择主菜单操作： ); scanf(%d,&choice);switch(choice)case 1: printf(n* 图的顺序存储 - 邻接矩阵 *n); LinJieJuZhen(&G);break;case 2: printf(n* 图的链式存储 -邻接链表 *n); LinJieLianBiao(&T);break;case 0: exit(0);default:printf( 输入错误！ n); break;while(choice!=0);#include #include #define Max 20typedef

16、 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=0;int i;L-length=1;printf( 输入数据，以 -100 为结束输入标志 n); while(data!=-100)printf( 输入第 %d 个元素值： ,L-length); scanf(%d,&

17、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; ilength; i+)if(L-arrayi arrayi-1)L-array0 = L-arrayi;L-arrayi = L-arrayi-1;for(j=i-2; L-array0 arrayj;

18、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; ilength; i+)low = 1;high = i-1;L-array0 = L-arrayi;while(low array0 arraymid) high = mid - 1

19、;elselow = mid + 1;for(j=i-1; j=high+1; j-)L-arrayj+1 = L-arrayj; L-arrayhigh+1 = L-array0;n);printf(n 二分法排序结果为 for(i=1; ilength; i+)printf(%d ,L-arrayi);printf(n);/ 一次增量下的希尔排序void Shell_pass(List *L,int d)int i;int j;for(i=d+1; ilength; i+)if(L-arrayi arrayi-d)L-array0 = L-arrayi;L-arrayi = L-array

20、i-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 希尔排序结果为 nfor(i=1; ilength; i+) printf(%d ,L-arrayi);printf(n);/ 冒泡排序void MaoPao_sort(List *L)int i;int j;int flag=1

21、; / 问题：课件上显示为已注销的部分，但是无法排序(没有交换=？ =已经排好了)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-arrayj = L-array0;/ if(flag=1)/ break;printf(n 冒泡排序结果为 n);for(i=1;

22、 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) / 无论是哪种退出循环方式，都恰好 是 high 的位置就是枢轴位置high-; if(lowarraylow

23、= 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_sort(List *L,int low,int high) int pivotloc;

24、/ 接收一次枢轴定位的位置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+) / 冒泡排序的最后一个值不用参与比较 min = i;for(j

25、=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返回值：无void GuiBing_pass(Lis

26、t *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,int 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 cho