各種排序算法C語言實(shí)現(xiàn)(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上#include <stdio.h>#include <stdlib.h>#define Max 20 /最大頂點(diǎn)數(shù)/順序存儲方式使用的結(jié)構(gòu)體定義typedef struct vexTypechar data;int indegree;Vex;typedef struct Graphint vexnum; /頂點(diǎn)數(shù)量int arcnum; /邊數(shù)Vex vex_arrayMax; /存放頂點(diǎn)的數(shù)組int arc_arrayMaxMax; /存放鄰接矩陣的二維數(shù)組Graph; /圖的定義/鏈?zhǔn)酱鎯κ褂玫慕Y(jié)構(gòu)體定義typedef struct ar

2、cTypechar vex1,vex2; /邊所依附的兩點(diǎn)int arcVal; /邊的權(quán)值A(chǔ)rc; /邊的定義typedef struct LinkTypeint index; /在頂點(diǎn)表的下標(biāo)struct LinkType *nextarc; /指向下一個(gè)頂點(diǎn)結(jié)點(diǎn)LinkNode; /邊表定義typedef struct vexNodechar data;int add; /在頂點(diǎn)數(shù)組的下表位置LinkNode *firstarc; /指向邊表的第一個(gè)結(jié)點(diǎn)int indegree; /入度VexNode; /頂點(diǎn)邊定義typedef struct LGraphVexNode vex_arr

3、ayMax; /頂點(diǎn)數(shù)組 int vexnum; /圖中頂點(diǎn)數(shù)LGraph;/*函數(shù)功能：圖的創(chuàng)建 入口參數(shù)：圖G 返回值：無*/void Creat_G(Graph *G)char v;int i=0;int j=0;G->vexnum=0;printf("輸入說明。有權(quán)值請輸入權(quán)值，無權(quán)值請輸入1，無邊請輸入0n");printf("n請輸入所有頂點(diǎn)(不超過20個(gè)，按#結(jié)束輸入)：n");doprintf("輸入第 %d 個(gè)頂點(diǎn)：",G->vexnum+1);scanf(" %c",&v);

4、G->vex_arrayG->vexnum.data = v;G->vexnum+;while(v!='#');G->vexnum-;printf("輸入鄰接矩陣（%d * %d）：",G->vexnum,G->vexnum);for(i=0; i<G->vexnum; i+)printf("輸入 %c 到以下各點(diǎn)的權(quán)值：n",G->vex_arrayi.data);for(j=0; j<G->vexnum; j+)printf("<%c, %c>:

5、",G->vex_arrayi.data,G->vex_arrayj.data);scanf("%d",&G->arc_arrayij);printf("n構(gòu)建圖的頂點(diǎn)為：n");for(i=0; i<G->vexnum; i+)printf("%c ",G->vex_arrayi.data);printf("n構(gòu)建圖的鄰接矩陣為：n");for(i=0; i<G->vexnum; i+)for(j=0; j<G->vexnum; j+)

6、printf("%d ",G->arc_arrayij);printf("n");/*函數(shù)功能：統(tǒng)計(jì)各點(diǎn)的入度 入口參數(shù)：指向圖的指針*G 返回值：無*/void Count_indegree(Graph *G)int i;int j;for(j=0; j<G->vexnum; j+)G->vex_arrayj.indegree =0;for(i=0; i<G->vexnum; i+)if(G->arc_arrayij!=0)G->vex_arrayj.indegree+;/*函數(shù)功能：對鄰接矩陣進(jìn)行拓?fù)渑?/p>

7、序 入口參數(shù)：指向圖的指針*G 返回值：無*/void Topol_sort(Graph *G)int i,j;char topoMax; /存放拓?fù)渑判虻慕Y(jié)果int count=0; /記錄topo中的元素個(gè)數(shù)，便于與vexnum比較，判斷是有環(huán)圖還是無環(huán)圖char stackMax; /存放indegree=0的頂點(diǎn)所在vex_array中的下標(biāo)int top=0; /棧的指針int bool=1; /彈棧的標(biāo)準(zhǔn)int no; /接收stack棧中彈出的頂點(diǎn)下標(biāo)for(i=0; i<G->vexnum; i+)if(G->vex_arrayi.indegree=0)sta

8、cktop = i;top+;doif(top=-1)bool=0;elsetop-;no = stacktop;topocount = G->vex_arrayno.data;count+;for(j=0; j<G->vexnum; 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 < G->vexnum)printf("n結(jié)果：原圖中有環(huán)

9、，無法形成拓?fù)湫蛄?n");elseprintf("n結(jié)果：原圖的拓?fù)湫蛄袨椋簄");for(i=0; i<count; i+)printf("%c ",topoi);printf("n");/*函數(shù)功能：鄰接矩陣及相關(guān)操作 入口參數(shù)：指向圖的指針*G 返回值：無*/void LinJieJuZhen(Graph *G)int choice;printf("n1 圖的創(chuàng)建(針對有向圖)n2 拓?fù)渑判騨0 退出n請選擇：");scanf("%d",&choice);dosw

10、itch(choice)case 1:Creat_G(G);break;case 2:Count_indegree(G);Topol_sort(G);break;case 0:break;printf("請選擇：");scanf("%d",&choice);if(choice=0)break;while(choice!=0);/*函數(shù)功能：創(chuàng)建鄰接鏈表T 入口參數(shù)：指向連接鏈表的指針*T 返回值：無*/void Creat_LinkT(LGraph *T)char v;int i,j,k;char answer;int count;int f=1

11、; /標(biāo)志邊表的第一個(gè)結(jié)點(diǎn)LinkNode *p=NULL;LinkNode *q=NULL;T->vexnum = 0;printf("n輸入說明。有權(quán)值請輸入權(quán)值，無權(quán)值請輸入1，無邊請輸入0n");printf("n請輸入所有頂點(diǎn)(不超過20個(gè)，按#結(jié)束輸入)n");doprintf("輸入第 %d 個(gè)頂點(diǎn)：",T->vexnum+1);scanf(" %c",&v);T->vex_arrayT->vexnum.data = v;T->vex_arrayT->vex

12、num.firstarc = NULL;T->vexnum+;while(v!='#');T->vexnum-;for(i=0; i<T->vexnum; i+)f=1;printf("n以頂點(diǎn) %c 為始點(diǎn)是否有邊(Y / N): ",T->vex_arrayi);scanf(" %c",&answer);if(answer='Y')printf("輸入以 %c 為始點(diǎn)的所有終點(diǎn)個(gè)數(shù)：",T->vex_arrayi);scanf("%d"

13、,&count);for(j=0; j<count; j+)p = (LinkNode *)malloc(sizeof(LinkNode);p->nextarc=NULL;printf("輸入第 %d 個(gè)頂點(diǎn)：",j+1);scanf(" %c",&v);for(k=0; k<T->vexnum; k+)if(v=T->vex_arrayk.data)p->index = k; /找到該元素，并記錄下標(biāo)if(f=1) /是第一個(gè)結(jié)點(diǎn),放在T->vex_arrayi.firstarc上T->v

14、ex_arrayi.firstarc = p;q = p;f = 0;elseq->nextarc = p;q = p;printf("創(chuàng)建鏈表為:n");for(i=0; i<T->vexnum; 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

15、("NULLn");/*函數(shù)功能：統(tǒng)計(jì)各個(gè)點(diǎn)的入度 入口參數(shù)：指向圖的指針*T 返回值:無*/void Count_T_indegree(LGraph *T)int i;LinkNode *p=NULL;for(i=0; i<T->vexnum; i+)T->vex_arrayi.indegree = 0;for(i=0; i<T->vexnum; i+)p = T->vex_arrayi.firstarc;while(p!=NULL)T->vex_arrayp->index.indegree+;p=p->nextarc

16、;/*函數(shù)功能：拓?fù)渑判?入口參數(shù)：指向圖的指針*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; i<T->vexnum; i+)if(T->vex_arrayi.indegree=0)stacktop = i;top+;doif(top=0)bool=0;elsetop-;no = stacktop;topocount = T->vex_array

17、no.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 < T->vexnum)printf("原圖有環(huán)，無法形成拓?fù)渑判颍");elseprintf(&qu

18、ot;原圖的拓?fù)渑判驗(yàn)椋簄");for(i=0; i<count; i+)printf("%c ",topoi);/*函數(shù)功能：鄰接鏈表及拓?fù)渑判?入口參數(shù)：指向圖的指針*T 返回值：無*/void LinJieLianBiao(LGraph *T)int choice;printf("n1 圖的創(chuàng)建(針對有向圖)n2 拓?fù)渑判騨0 退出n");doprintf("n請選擇：");scanf("%d",&choice);switch(choice)case 1:Creat_LinkT(T);

19、printf("圖已創(chuàng)建完成！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、 圖的順序存儲-鄰接矩陣并進(jìn)行拓?fù)渑判騨2、 圖的連式存儲-鄰接鏈表并進(jìn)行拓?fù)渑判騨0、 退出n");doprintf("請選擇主菜單操作：

20、");scanf("%d",&choice);switch(choice)case 1:printf("n*圖的順序存儲-鄰接矩陣*n");LinJieJuZhen(&G);break;case 2:printf("n*圖的鏈?zhǔn)酱鎯?鄰接鏈表*n");LinJieLianBiao(&T);break;case 0:exit(0);default:printf("輸入錯誤！n");break;while(choice!=0);#include <stdio.h>#incl

21、ude <stdlib.h>#define Max 20typedef struct listint arrayMax;int length;List;/*數(shù)組復(fù)制*/void Copy(List *L,List *Lx)int i;Lx->length = L->length;for(i=1; i<=L->length; i+)Lx->arrayi = L->arrayi;/*創(chuàng)建順序表*/void Creat(List *L)int data=0;int i;L->length=1;printf("輸入數(shù)據(jù)，以-100為結(jié)束輸

22、入標(biāo)志n");while(data!=-100)printf("輸入第 %d 個(gè)元素值：",L->length);scanf("%d",&data);L->arrayL->length = data;L->length+;L->length = L->length-2;printf("輸入的元素值為：");for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n"

23、);/*直接插入排序*/void ZhiJieChaRu_sort(List *L)int i;int j;for(i=2; i<=L->length; i+)if(L->arrayi < L->arrayi-1)L->array0 = L->arrayi;L->arrayi = L->arrayi-1;for(j=i-2; L->array0 < L->arrayj; j-)L->arrayj+1 = L->arrayj;L->arrayj+1 = L->array0;printf("n

24、-直接插入法排序結(jié)果為-n");for(i=1; i<=L->length; 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; i<=L->length; i+)low = 1;high = i-1;L->array0 = L->arrayi;while(low <= high)mid = (low+high)

25、/2;if(L->array0 < L->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-二分法排序結(jié)果為-n");for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n");/一次增量下的希爾排序vo

26、id Shell_pass(List *L,int d)int i;int j;for(i=d+1; i<=L->length; i+)if(L->arrayi < L->arrayi-d)L->array0 = L->arrayi;L->arrayi = L->arrayi-d;for(j=i-2*d; j>0 && L->array0<L->arrayj; j-)L->arrayj = L->arrayj-d;L->arrayj+d = L->array0;/希爾排序voi

27、d Shell_sort(List *L,int d)int i;for(i=0; i<4; i+) /一次取出d中的增量值Shell_pass(L,di);printf("n-希爾排序結(jié)果為-n");for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n");/冒泡排序void MaoPao_sort(List *L)int i;int j;int flag=1; /問題：課件上顯示為已注銷的部分，但是無法排序（沒有交換=？=已經(jīng)排好了）for(

28、i=1; i<=L->length; i+) /控制趟數(shù)/flag=1;for(j=1; j<=L->length-i; j+) /一趟的循環(huán),第i趟結(jié)束后就篩選出第i個(gè)最小值，所以只需從前l(fā)ength-i個(gè)中冒出最小值if(L->arrayj+1 < L->arrayj)flag=0;L->array0 = L->arrayj+1;L->arrayj+1 = L->arrayj;L->arrayj = L->array0;/if(flag=1)/break;printf("n-冒泡排序結(jié)果為-n"

29、;);for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n");/快速排序的一次樞軸定位int KuaiSu_sort(List *L, int low, int high)int pivotkey; /樞軸L->array0 = L->arraylow; /每次排序序列的第一個(gè)值作為樞軸,即low作為樞軸pivotkey = L->arraylow;while(low < high)while(low<high && piv

30、otkey<=L->arrayhigh) /無論是哪種退出循環(huán)方式，都恰好是high的位置就是樞軸位置high-;if(low<high)L->arraylow = L->arrayhigh;low+;while(low<high && pivotkey>=L->arraylow)low+;if(low<high)L->arrayhigh = L->arraylow;high-;/整個(gè)循環(huán)退出就得到樞軸在真正序列中的位置為low（也是high）L->arraylow = L->array0;/*pri

31、ntf("n-分步排序結(jié)果為-n");for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n");*/return low;/完整快速排序void KuaiSuPaiXu_sort(List *L,int low,int high)int pivotloc; /接收一次樞軸定位的位置if(low < high)pivotloc = KuaiSu_sort(L,low,high); /也可寫為(L,low,pivotkey-1)KuaiSuPaiXu

32、_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; i<L->length; i+) /冒泡排序的最后一個(gè)值不用參與比較min = i;for(j=i+1; j<=L->length; j+)if(L->arrayj < L->arraymin)min = j;if(min!=i)L->array

33、0 = L->arraymin;L->arraymin = L->arrayi;L->arrayi = L->array0;printf("n-簡單選擇排序結(jié)果為-n");for(i=1; i<=L->length; i+)printf("%d ",L->arrayi);printf("n");/* 2路歸并排序一趟合并 函數(shù)功能：將Ls.m 和 Lm+1.t和并為Ts.t 入口參數(shù)：原列表L，合并后的列表T,起始值s,中間值m，終點(diǎn)值t 返回值：無void GuiBing_pass(L

34、ist *L,List *T,int s,int m,int t)int i;int j;int k=1;for(i=1,j=m+1; i<=m,j<=t; k+)if(L->arrayi < L->arrayj)T->arrayk = L->arrayi+;elseT->arrayk = L->arrayj+;while(i < m)T->arrayk+ = L->arrayi+;while(j<t)T->arrayk+ = L->arrayj+;2-歸并排序遞歸分解 函數(shù)功能：將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