1、#include #inelude 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 arcTypecharvexl,vex2; 邊所依附的兩點i nt a rcVa I;邊的權值Arc; 邊

2、的定義typedef struct LinkTypeint index; 在頂點表的下標struct LinkType * nextarc;指向卞一個頂點結點LinkNode; 邊表定義typedef struct vexNodechar data;int add;在頂點數組的下表位置LinkNode *firstarc; 指向邊表的第一個結點int indegree; 入度VexNode; 頂點邊定義typedef struct LGraphVexNode vex_arrayMax; 頂點數組 i nt vexn um;圖中頂點數LGraph;廠函數功能：圖的創建入口參數：圖G返回值：無*/

3、void Creat_G(Graph *G)char v;int i=0;int j=0;G-vex num=0;printf(輸入說明。有權值請輸入權值，無權值請輸入1,無邊請輸入0n”); printf(n請輸入所有頂點(不超過20個,按#結束輸入)：n“)；doprintf(輸入第 %d 個頂點：jGvexnum+l);scanf(H %c,&v);G-vex_arrayG-vexnum.data = v;G-vexnum+;while(v!=#)；G-vex num；printf(”輸入鄰接矩陣(d * %d)： ”，Gvexnum,Gvexnum);for(i=0; ivexnum;

4、 i+)printf(輸入 %c 到以下各點的權值：n,G-vex_arrayi.data);for(j=0; jvex nu m; j+)printf(: ,G-vex_arrayi.data/G-vex_arrayj.data); scanf(%cT：&Garc_aiTayij);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; j+)printf(%d ”,G-arc_arr

5、ayij);printf(”n”)；/*函數功能：統計各點的入度入II參數：指向圖的指針*G返回值：無*/void Count_indegree(Graph *G)int i;int j;for(j=0; jvex num; j+)G-vex_arrayj.indegree =0; for(i=0; i vex num; i+) if(G-arc_arrayij!=O)G vex_airayji ndegree+;廠函數功能：對鄰接矩陣進行拓撲排序 入口參數：指向圖的指針*G 返回值：無*/ void Topol_sort(Graph *G)int ij;chartopoMax; 存放拓撲排序

6、的結果int count=0; 記錄topo口中的元素個數，便于與vexnum比較，判斷是有環圖還是無 環圖char stackMax; 存放 indegree=O 的頂點所在 vex_array沖的下標int top=0; 棧的指針int bool=l; 彈棧的標準int no; 接收stack棧中彈出的頂點下標for(i=0; ivexnum; i+)if(G-vex_arrayi.indegree=O)stacktop = i;top+;doif(top=-l)bool=0;elsetop-；no 二 stacktop;topoco unt = G-vex_arrayno.data;co

7、un t+;for(j=0; jvex num; j+)if(G-arc_arrayi j!=0)Gove x_arrayj.i ndegree 一;if(G-vex_arrayj.indegree=O) stacktop = j; top+;while(bool=l);cou nt；if(count vexnum)printf(n結果：原圖中有環,無法形成拓撲序列!n); elseprintf(n結果：原圖的拓撲序列為:n”)；for(i=0; ivex num = 0;printf（n輸入說明。有權值請輸入權值，無權值請輸入1，無邊請輸入0n“）;printf（Hn請輸入所有頂點（不超過2

8、0個，按#結束輸入）寸）；doprintf(輸入第 d 個頂點:Jvexnum+l); scanf( %c,&v);T- vex_a r ray T- vexn u m . d at a = v;T- vex_a r ray T- vexn u m .f i rsta rc = NULL;T-vex nu m+;while(v!=,#1)；T-vex num；for(i=0; ivexnum; i+)f=l;printf(n 以頂點 %c 為始點是否有邊(Y/N): ”,T-vex_arrayi);scanf(H %c：&answer);if(answer=,Y,)printfC輸入以%c為始

9、點的所有終點個數：zT-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_a rray k .data)p-index = k; 找到該元素，并記錄下標if(f=l) 是第一個結點，放在 T-vex_arrayi.firstarc 上 T-vex_arrayi.firstarc = p;q = p;f = 0;elseqn extarc = p;q = p;phntfC創建鏈表為:nj;for(

10、i=0; ivexnum; i+)printf(%c ,I/T-vex_a rray i .d ata);p = T- vex_a r ray i .f i rst a rc;while(p!=NULL)printf( %c 一一,T-vex_arrayp-in dex.data); p=p-n extarc;printf(,NULLnH)；廠函數功能：統計各個點的入度入II參數：指向圖的指針*T返回值:無*/void Count_T_indegree(LGraph *T)int i;LinkNode *p=NULL;for(i=0; ivexnum; i+)T-vex_arrayi.i nd

11、egree = 0;for(i=0; ivexnum; i+)p = T- vex_a r ray i .f i rst a rc; while(p!=NULL)T-vex_arrayp-index.i ndegree+; p=p-n extarc;/*函數功能：拓撲排序入I I參數：指向圖的指針*T返回值：無*/void L_Topol_sort(LGraph *T)int i,j；int no;int stackMax;int top=0;int topoMax;int count=O;int bool=l;LinkNode *p=NULL;for(i=0; ivexnum; i+)if(

12、T-vex_arrayi.indegree=O)stacktop = i;top+;doif(top=0) bool=0;elsetop-；no 二 stacktop;topoco unt = T-vex_arrayno.data; coun t+;p = T-vex_arrayno.firstarc; while(p!=NULL)T-vex_arrayp-i ndex.indegree-;if(T-vex_arrayp-i ndexindegree=O) stacktop = pin dex;top+;p = pn extarc;while(bool=l);/printfC 檢測n“);if

13、(cou nt vex num)printf(原圖有環,無法形成拓撲排序! n)； elseprintf(”原圖的拓撲排序為:n“);for(i=0; iarrayj+l = L-arrayj;L-arrayj+l = L-arrayj;Lx-arrayi = L-arrayi;default:printf(輸入錯誤！ n)； break;while(choice=0);/include #include #define Max 20typedef struct listint arrayMax;int length;List;廠數組復制*7void Copy(Ust *L,List *Lx)

14、int i;Lx-length = L-le ngth;for(i=l; ilength; i+)廠創建順序表拿/void Creat(List *L)int data=O;int i;L-length=l;printf(輸入數據，以100為結束輸入標志n”);while(data!=-100)printf(輸入第%d個元素值：丄-length); scanf(,%d,&data);L-arrayL-le ngth = data;L-le ngth+;L-length = L-length-2;printf(輸入的元素值為:)；for(i=l; ilength; i+)printf(%d Xa

15、rrayfi);printfCXn11)；/*直接插入排序*/void ZhiJieChaRu_sort(List *L)int i;int j;for(i=2; ilength; i+)if(L-arrayi arrayi-l)L-arrayO = L-arrayi;L-arrayi = L-arrayi-l;for(j=i-2; L-arrayO arrayj; j-) L-arrayj+l = L-arrayO;printf(*n直接插入法排序結果為n)；for(i=l; ilength; i+)printf(%d丄airayi);printf (”n“);/*二分法排序*/void E

16、rFenFa_sort(List *L)int i;int j;int low;int high;int mid;for(i=2; ilength; i+)low = 1;high = i-1;L-arrayO = L-arrayi;while(low arrayO arraymid)high = mid -1;elselow = mid + 1;for(j=i-l; j=high+l; j_)L-arrayj+l = L-arrayj;L-arrayhigh+l = L-arrayO;printf(Hn二分法排序結果為nH)；for(i=l; ilength; i+) printf(%d丄-

17、airayi);printfCV);一次增量下的希爾排序void Shell_pass(List *LJnt d)int i;int j;for(i=d+l; ilength; i+)if(L-arrayi arrayi-d)L-arrayO = 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 *LJnt d)int i;for(i=0; i4; i+) 一次取出d中的增

18、量值 Shell_pass(L,di);printf(n希爾排序結果為n)；for(i=l; ilength; i+) printf(%d丄-airayi);printf(,nM)；冒泡排序void MaoPao_sort(List *L)int i;int j;int flag=l; 問題：課件上顯示為已注銷的部分，但是無法排序(沒有交換二？二已經 排好了)for(i=l; ilength; i+) 控制趟數/ flag=l;for(j=l; jlength-i; j+)一趟的循環，第i趟結束后就篩選出第i個最小值，所以只需從前length-i個中冒岀最小值if(L-arrayj+l arr

19、ayj)flag=O;L-array0 = L-arrayj+l;L-arrayj+l = L-arrayj; L-arrayj = L-arrayO;/ if(flag=l)/break;printf(n冒泡排序結果為n)；for(i=l; ilength; i+)printf(%d丄-arrayi);printf(“n“)；快速排序的一次樞軸定位int KuaiSu_sort(List *L, int low, int high) int pivotkey; 樞軸L-arrayO = L-arraylow;每次排序序列的第一個值作為樞軸，即low作為樞軸pivotkey = L-array

20、low;while(low high)while(lowhigh & pivotkeyarrayhigh) 無論是哪種退岀循壞方式，都恰好是high的位置就是樞軸位置high-;if (lowarraylow = L-arrayhigh;low+;while(low=L-arraylow)low+;if (lowarrayhigh = L-arraylow;high-;整個循環退出就得到樞軸在真正序列中的位置為low (也是high)L-arraylow = L-arrayO;/* printf(n分步排序結果為n)；for(i=l; ilength; i+)printf(n%d丄-airay

21、i);prin 廿(An);*/return low;完整快速排序void KuaiSuPaiXu_sort(List *LJnt lowjnt high)int pivotloc; 接收一次樞軸定位的位置if(low high)pivotloc = KuaiSu_sort(LJow,high); /也可寫為(Ljow,pivotkey-1) KuaiSuPaiXu_sort(L,low;pivotloc-l);KuaiSuPaiXu_sort(L，pivotloc+l，high); 也可寫為(Lhigpivotkey-l) 簡單選擇排序void JianDanXuanZe_sort(List

22、 *L)int i;int j;int min;for(i=l; ilength; i+)冒泡排序的最后一個值不用參與比較min = i;for(j=i+l; jlength; j+)if(L-arrayj arraymin)min = j;if(min!=i)L-arrayO = L-arraymin;L-arraymin = L-arrayi;L-arrayi = L-arrayO;printf(n簡單選擇排序結果為n)；for(i=l; ilength; i+)printf(%d zL-arrayi);printfCXn);2路歸并排序一趟合并函數功能：將Ls.m和Lm+l.t和并為Ts

23、.t入II參數：原列表L,合并后的列表T,起始值s,中間值終點值t返回值：無void GuiBing_pass(List *L,List *TJnt s,int m,int t)int i;int j;int k=l;for(i=l,j=m+l; i=mjarrayi 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歸并為Tls.tvoid GuiBing_sort(List *L,List *TlJnt sjnt t)int m;List Tx;List *T2 = &Tx;Txength = 6;if(s=t)L-arrays = T2-arrays;elsem = (s+t)/2;GuiBing_sort(L/T2/s/m);GuiBing_sort(L,T2/m+l,t);GuiBing_pass(T2,Tl/s/m/t);*/void main()int choice;int i;int d4 = 7,5,3,1;希爾排序的增量數組List L;List Lx;