2022年曉莊-數據結構實驗報告 .pdf

《2022年曉莊-數據結構實驗報告 .pdf》由會員分享，可在線閱讀，更多相關《2022年曉莊-數據結構實驗報告 .pdf（31頁珍藏版）》請在得力文庫 - 分享文檔賺錢的網站上搜索。

1、數據結構 (C 語言版 ) 實驗報告學院信息工程學院班級15 計科 2 班學號15131019 姓名張旭指導教師曹晨名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 1 頁，共 31 頁 - - - - - - - - - 實驗一線性表基本操作和簡單程序1 實驗目的（1）復習 Visual C+ 6.0上機調試程序的基本方法及C 語言編程；（2）掌握線性表的基本操作：初始化、插入、刪除、取數據元素等運算在鏈表存儲結構上的程序設計方法。2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材

2、內容。（2） 分別以頭插法和尾插法建立兩個數據域定義為整型的升序單鏈表，再將這兩個有序鏈表合并成一個新的無重復元素的有序鏈表，最后可以根據輸入的數據，先找到相應的結點，后刪除之。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#include #include typedef struct node int data; struct node *next; node; node * qbuild(node *first) int i,n,a100; node *s; printf(輸入 n:); scanf(%d,&n); first=(node*)m

3、alloc(sizeof(node); first-next=NULL; for(i=0;idata=ai; s-next=first-next; first-next=s; return first; node * hbuild(node *first) int i,n,a100; struct node *s,*r; printf(輸入 n:); scanf(%d,&n); first=(node*)malloc(sizeof(node); r=first; for(i=0;idata=ai; r-next=s; r=s; r-next=NULL; return first; node *

4、 hebing(node *La,node *Lb) node *pa,*pb,*pc,*Lc; pa=La-next; pb=Lb-next; Lc=pc=La; while(pa & pb) if(pa-data data) pc-next =pa; pc=pa; pa=pa-next ; 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 3 頁，共 31 頁 - - - - - - - - - else if(pa-data pb-data) pc-next =pb; pc=pb

5、; pb=pb-next; else pc-next =pa; pc=pa; pa=pa-next ; pb=pb-next ; pc-next =pa?pa:pb; free(Lb); return Lc; node * shanchu(node *first,int i) node *p,*q; p=first-next; while(p) if(p-next )-data=i) q=p-next ; p-next =q-next; free(q); break; p=p-next; return first; void display(node *first) struct node *

6、p; p=first-next; while(p!=NULL) 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 4 頁，共 31 頁 - - - - - - - - - printf(%d ,p-data); p=p-next; printf(n); int main() int m; struct node *a,*b,*c; a=qbuild(a); printf(打印鏈表a：); display(a); b=hbuild(b); printf(打印鏈表b：); display(

7、b); c=hebing(a,b); printf(打印鏈表c：); display(c); printf(輸入刪除的數m:); scanf(%d,&m); c=shanchu(c,m); printf(打印刪除后的鏈表c:); display(c); return 0; 4 實驗結果輸入 n:5 輸入 a0:9 輸入 a1:5 輸入 a2:4 輸入 a3:3 輸入 a4:1 打印鏈表a：1 3 4 5 9 輸入 n:5 輸入 a0:1 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第

8、 5 頁，共 31 頁 - - - - - - - - - 輸入 a1:3 輸入 a2:4 輸入 a3:6 輸入 a4:8 打印鏈表b：1 3 4 6 8 打印鏈表c：1 3 4 5 6 8 9 輸入刪除的數m:5 打印刪除后的鏈表c:1 3 4 6 8 9 - Process exited after 32.78 seconds with return value 0 請按任意鍵繼續. . . 5 心得體會本次實驗是以后實驗的基礎，是數據結構中最基本的東西。通過本次試驗，我對之前所學習的C 語言知識要點有了進一步實踐，加深了我對C 語言的認識。名師資料總結 - - -精品資料歡迎下載 - -

9、 - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 6 頁，共 31 頁 - - - - - - - - - 實驗二利用棧和隊列判斷字符串是否是回文1 實驗目的（1）深入了解棧和循環隊列的特性、棧和遞歸程序設計的關系。（2）要求能靈活運用兩種結構來解決有關的應用問題。y2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容。（2） 假設正讀和反讀都相同的字符序列為“回文”，例如，abba和 abcba是回文，abcde 和 ababab則不是回文。試寫一個算法判別讀入的一個以為結束符的字符序列是否是“回文”。（3） 上機運行程序。（

10、4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#include #include #define m 100 typedef struct /定義棧 char datam; int top; zhan; void cshz(zhan *s) /初始化棧 s-top=0; int pdzk(zhan *s) /判斷棧是否為空 if(s-top=0) return 0; else 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 7 頁，共 31 頁 - - - - -

11、 - - - - return 1; void ruzhan(zhan *s,char x) /入棧 if(s-top=m) printf(?？?n); else s-data+s-top=x; char chuzhan(zhan *s) /出棧 char y; if(s-top=0) printf(?？?n); return 0; else y=s-datas-top; s-top=s-top-1; return y; typedef struct /定義隊列 char datam; int front; int rear; dui; void cshdl(dui *q) /初始化隊列 q-

12、front=q-rear=0; 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 8 頁，共 31 頁 - - - - - - - - - void rudui(dui *q,char e) /入隊 if(q-rear+1)%m=q-front) printf(隊列為空 n); else q-dataq-rear=e; q-rear=(q-rear+1); char chudui(dui *q) /出對 char f; if(q-front=q-rear) printf(隊列為空 n)

13、; return 0; else f=q-dataq-front; q-front=(q-front+1); return f; int main() char c; int y=0; zhan *s=(zhan *)malloc(sizeof(zhan); dui *q=(dui *)malloc(sizeof(dui); cshz(s); cshdl(q); printf(輸入一個字符串:n); while(c=getchar()!=) ruzhan(s,c); rudui(q,c); 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - -

14、 - - 名師精心整理 - - - - - - - 第 9 頁，共 31 頁 - - - - - - - - - while(pdzk(s) if(chuzhan(s)=chudui(q) y=1; continue; else y=0; break; if(y=1) printf(此字符串為回文n); else printf(此字符串不是回文n); return 0; 4 實驗結果輸入輸出示例：1. 輸入一個字符串: abbabba 此字符串為回文- Process exited after 8.796 seconds with return value 0 請按任意鍵繼續. . . 2.

15、輸入一個字符串: abbabb 此字符串不是回文- Process exited after 7.968 seconds with return value 0 請按任意鍵繼續. . 5 心得體會名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 10 頁，共 31 頁 - - - - - - - - - 利用棧和隊列進行對回文數的檢測，看似簡單的問題，卻變得更加復雜，但是卻給了我們一個深入了解棧和隊列的機會，對于其中的知識也相對掌握了。這也說明了實踐對課堂上學到的知識有著鞏固和加深的作

16、用，想要學好數據結構，不能怕麻煩。名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 11 頁，共 31 頁 - - - - - - - - - 實驗三三元組表的轉置1 實驗目的（1）掌握稀疏矩陣的存儲方法和基本運算。（2）掌握三元組表轉置的程序設計方法。2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容。（2） 輸入一個三元組表，先輸出其矩陣形態，然后對其進行轉置并輸出轉置后的矩陣。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#inc

17、lude #define MAXSIZE 100 typedef struct /定義三元組 int hang,lie; int zhi; SAN; typedef struct SAN dataMAXSIZE; int mu,nu,tu; SANYUAN; void zhuanzhi(SANYUAN M,SANYUAN *T) /對三元組進行轉置 int col,p,q,t; int numMAXSIZE,cpotMAXSIZE; T-mu=M.nu;T-nu=M.mu;T-tu=M.tu; if(T-tu) 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - -

18、- - - - - - - - 名師精心整理 - - - - - - - 第 12 頁，共 31 頁 - - - - - - - - - for(col=1;col=M.nu;+col) numcol=0; for(t=1;t=M.tu;+t) +numM.datat.lie; cpot1=1; for(col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;pdataq.hang=M.datap.lie; T-dataq.lie=M.datap.hang; T-dataq.zhi=M.datap.zhi; +cpotcol; void

19、 output(SANYUAN *M) /輸出三元組 int i,j; int t=1; for(i=1;imu;i+) for(j=1;jnu;j+) if(M-datat.hang=i&M-datat.lie=j) printf(%d ,M-datat.zhi); t+; else printf(0 ); printf(n); int main() SANYUAN A,T;int k; printf(輸入矩陣大小n); printf(行： );scanf(%d,&A.mu); printf(列： );scanf(%d,&A.nu); 名師資料總結 - - -精品資料歡迎下載 - - - -

20、 - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 13 頁，共 31 頁 - - - - - - - - - printf(非零元素個數:);scanf(%d,&A.tu); printf(輸入三元組表:n); /順序輸入三元組 for(k=1;k=A.tu;k+) scanf(%d %d %d,&A.datak.hang,&A.datak.lie,&A.datak.zhi); printf(原矩陣 n); output(&A); zhuanzhi(A,&T); printf(轉置后的矩陣：n); output(&T); return 0;

21、 4 實驗結果輸入矩陣大小行： 8 列： 8 非零元素個數:5 輸入三元組表: 1 2 3 2 3 4 3 4 5 5 6 7 7 8 9 原矩陣0 3 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 轉置后的矩陣：0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0

22、0 0 0 0 0 0 0 0 0 0 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 14 頁，共 31 頁 - - - - - - - - - 0 0 0 0 0 0 9 0 - Process exited after 24.57 seconds with return value 0 請按任意鍵繼續. . . 5 心得體會本次試驗相對簡單一點，容易理解，只要掌握了三元組表的知識，就完全可以解決。名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - -

23、- - - - - - - - 名師精心整理 - - - - - - - 第 15 頁，共 31 頁 - - - - - - - - - 實驗四二叉樹的遍歷1 實驗目的（1） 進一步掌握指針變量的用途和程序設計方法。（2） 掌握二叉樹的結構特征，以及鏈式存儲結構的特點及程序設計方法。（3） 掌握構造二叉樹的基本方法。（4） 掌握二叉樹遍歷算法的設計方法。2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容。（2） 利用二叉鏈表建立一棵二叉樹，分別采用先序、中序和后序遍歷該二叉樹，并輸出遍歷的序列。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#i

24、nclude #include #define MAX 100 typedef struct BiTNode / 定義二叉樹 char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; void CreateBiTree(BiTree *T) char data; /按先序次序輸入二叉樹中結點的值（一個字符），#表示空樹 scanf(%c,&data); if(data = #) *T = NULL; else *T = (BiTree)malloc(sizeof(BiTNode); 名師資料總結 - - -精品資料歡迎下載 - -

25、- - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 16 頁，共 31 頁 - - - - - - - - - / 生成根結點 (*T)-data = data; / 構造左子樹 CreateBiTree(&(*T)-lchild); / 構造右子樹 CreateBiTree(&(*T)-rchild); void Visit(BiTree T) / 輸出 if(T-data != #) printf(%c ,T-data); void PreOrder(BiTree T) / 先序遍歷 if(T != NULL) / 訪問根節點 Vi

26、sit(T); / 訪問左子結點 PreOrder(T-lchild); / 訪問右子結點 PreOrder(T-rchild); void InOrder(BiTree T) / 中序遍歷 if(T != NULL) / 訪問左子結點 InOrder(T-lchild); / 訪問根節點 Visit(T); / 訪問右子結點 InOrder(T-rchild); 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 17 頁，共 31 頁 - - - - - - - - - void P

27、ostOrder(BiTree T) /后序遍歷 if(T != NULL) / 訪問左子結點 PostOrder(T-lchild); / 訪問右子結點 PostOrder(T-rchild); / 訪問根節點 Visit(T); int main() BiTree T; printf(以 #代表空先序遍歷n 輸入二叉樹：); CreateBiTree(&T); printf(先序遍歷： n); PreOrder(T); printf(n); printf(中序遍歷： n); InOrder(T); printf(n); printf(后序遍歷： n); PostOrder(T); retu

28、rn 0; 4 實驗結果以#代表空先序遍歷輸入二叉樹：ab#c# 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 18 頁，共 31 頁 - - - - - - - - - 先序遍歷：a b c 中序遍歷：b a c 后序遍歷：b c a - Process exited after 10.89 seconds with return value 0 請按任意鍵繼續. . . 5 心得體會這次的試驗讓我對二叉樹有了更進一步的理解，對二叉樹的操作也更加熟悉。本次試驗是對二叉樹進行建立，

29、并掌握先序遍歷，中序遍歷和后續遍歷，雖然用的是遞歸的方法相對簡單一點， 但是理解起來還是有點困難。二叉樹是數據結構中很重要的一部分知識，也是數據結構的重難點，我相信在以后的學習中還會遇到，而我更要進行更深入的學習。名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 19 頁，共 31 頁 - - - - - - - - - 實驗五圖的遍歷1 實驗目的（1）加深理解圖的非線性結構特點，靈活運用圖的存儲結構、圖的深度優先搜索和廣度優先搜索來解決有關應用問題。（2）加深遞歸程序設計的訓練。（3

30、）注重提高關于模型選擇、算法設計和分析方面的能力。2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容。（2） 利用鄰接矩陣或鄰接表存儲一張圖，分別采用圖的深度優先搜索和廣度優先搜索遍歷該圖，并輸出遍歷結果。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#include #include #define MAXVEX 100 /最大頂點數#define INFINITY 65535 /用 65535 來代表無窮大int visitedMAXVEX=0; typedef struct char vexsMAXVEX; / 頂點表 int arcMA

31、XVEXMAXVEX; /鄰接矩陣，可看作邊 int numVertexes, numEdges; / 圖中當前的頂點數和邊數Graph; 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 20 頁，共 31 頁 - - - - - - - - - void CreateGraph(Graph *g) int i,j,k,w,t; printf(輸入頂點數，邊數和t （中間用空格）:); scanf(%d %d %d, &(g-numVertexes), &(g-numEdges),&

32、t); printf(n); for(i=1;inumVertexes;i+) getchar(); printf(輸 入 第 %d 頂 點 信 息vexs%d=,i,i); scanf(%c,&(g-vexsi); printf(n); for(i=1;inumVertexes;i+) for(j=1;jnumVertexes;j+) if (t2) g-arcij = INFINITY; else g-arcij=0; for(k=1;knumEdges;k+) printf(輸入 i j（中間用空格）:); scanf(%d %d,&i,&j); if(ig-numVertexes |j

33、g-numVertexes) exit(0); if(t2) printf(輸入 w:); scanf(%d,&w); g-arcij=w; if(t=3) g-arcji=w; else g-arcij=1; if (t=1) g-arcji=1; printf(n); printf(輸出鄰接矩陣 :n); for(i=1;inumVertexes ;i+) for(j=1;jnumVertexes ;j+) printf(%8d,g-arcij); if(t2&g-arcij=65535) g-arcij=0; else if(t2&g-arcij!=65535) 名師資料總結 - - -

34、精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 21 頁，共 31 頁 - - - - - - - - - g-arcij=1; printf(n); void dfs (Graph g,int i) /廣度優先搜索，從頂點i 開始遍歷 int j; printf(%d-,i); /輸出訪問頂點 visitedi=1; / 全局數組訪問標記置1 表示已經訪問 for(j=1; j,i); visitedi=1 ; r+; qr=i ; while (fr) f+; i=qf ; for (j=1; j,j)

35、; ; visitedj=1 ; r+; qr=j ; int main() Graph g; int i; printf(t為 14, 分別表示無向圖、有向圖、帶權無向圖、帶權有向圖n); CreateGraph(&g); 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 22 頁，共 31 頁 - - - - - - - - - printf(n輸入 i:); scanf(%d,&i); printf(n深度優先搜索遍歷：); dfs (g,i); printf(NULLn); p

36、rintf(廣度優先搜索遍歷：); bfs (g,i); printf(NULLn); return 0; 4 實驗結果1. 無向圖t 為 14, 分別表示無向圖、有向圖、帶權無向圖、帶權有向圖輸入頂點數，邊數和t （中間用空格）:8 10 1 輸入第 1 頂點信息vexs1=1 輸入第 2 頂點信息vexs2=2 輸入第 3 頂點信息vexs3=3 輸入第 4 頂點信息vexs4=4 輸入第 5 頂點信息vexs5=5 輸入第 6 頂點信息vexs6=6 輸入第 7 頂點信息vexs7=7 輸入第 8 頂點信息vexs8=8 輸入 i j（中間用空格）:1 2 輸入 i j（中間用空格）:1

37、 3 輸入 i j（中間用空格）:2 4 輸入 i j（中間用空格）:2 5 輸入 i j（中間用空格）:3 6 輸入 i j（中間用空格）:3 7 輸入 i j（中間用空格）:4 8 輸入 i j（中間用空格）:5 8 輸入 i j（中間用空格）:6 8 輸入 i j（中間用空格）:7 8 輸出鄰接矩陣: 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 2

38、3 頁，共 31 頁 - - - - - - - - - 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 輸入 i:1 深度優先搜索遍歷：1-2-4-8-5-6-3-7-NULL 廣度優先搜索遍歷：1-2-3-4-5-6-7-8-NULL - Process exited after 74.92 seconds with return value 0 請按任意鍵繼續. . . 2. 帶權無向圖t 為 14, 分別表示無向圖、有向圖、帶權無向圖、帶權有向圖輸入頂點數，邊數和t （中間用空格）:5 8 3 輸入第 1

39、頂點信息 vexs1=1 輸入第 2 頂點信息vexs2=2 輸入第 3 頂點信息vexs3=3 輸入第 4 頂點信息vexs4=4 輸入第 5 頂點信息vexs5=5 輸入 i j（中間用空格）:1 2 輸入 w:6 輸入 i j（中間用空格）:1 3 輸入 w:1 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 24 頁，共 31 頁 - - - - - - - - - 輸入 i j（中間用空格）:1 5 輸入 w:3 輸入 i j（中間用空格）:2 5 輸入 w:9 輸入 i

40、j（中間用空格）:2 4 輸入 w:8 輸入 i j（中間用空格）:4 5 輸入 w:7 輸入 i j（中間用空格）:4 3 輸入 w:2 輸入 i j（中間用空格）:3 5 輸入 w:4 輸出鄰接矩陣: 65535 6 1 65535 3 6 65535 65535 8 9 1 65535 65535 2 4 65535 8 2 65535 7 3 9 4 7 65535 輸入 i:3 深度優先搜索遍歷：3-1-2-4-5-NULL 廣度優先搜索遍歷：3-1-4-5-2-NULL - Process exited after 42.63 seconds with return value 0

41、 請按任意鍵繼續. . . 5 心得體會圖在數據結構中也是一個重要的知識點，是一種較線性表和樹更加復雜的數據結構。本次試驗相對來說比較有難度，也是寫了很長時間才寫完，掌握了對各種圖的構建和遍歷。雖然也做出了結果，但掌握的還不夠充分，不能很好的理解和掌握。概念性的東西非常多，還得加名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 25 頁，共 31 頁 - - - - - - - - - 緊學習名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - -

42、- - - - - 名師精心整理 - - - - - - - 第 26 頁，共 31 頁 - - - - - - - - - 實驗六查找和排序1 實驗目的（1）提高關于查找、排序算法的運用、比較與分析能力。（2）順序查找與二分查找的比較，ASL 的分析。（3）直接插入排序、冒泡排序、選擇排序（三選一）與快速排序的分析比較。2 實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容。（2） 自舉一個數列，對其進行排序和查找，分析算法的優缺點。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3 程序代碼#include #define MAXSIZE 20 /* 一個用

43、作示例的小順序表的最大長度 */ #define N 10 typedef struct int key; /* 關鍵字項 */ RedType; /* 記錄類型 */ typedef struct RedType rMAXSIZE+1; /* r0閑置或用作哨兵單元 */ int length; /* 順序表長度 */ SqList; /* 順序表類型 */ void InsertSort(SqList *L) /* 對順序表 L 作直接插入排序。算法10.1 */ int i,j; for(i=2;i=(*L).length;+i) if (*L).ri.key(*L).ri-1.key)

44、 /* ,需將 L.ri插入有序子表 */ (*L).r0=(*L).ri; /* 復制為哨兵 */ for(j=i-1;(*L).r0.key(*L).rj.key);-j) (*L).rj+1=(*L).rj; /* 記錄后移 */ 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 27 頁，共 31 頁 - - - - - - - - - (*L).rj+1=(*L).r0; /* 插入到正確位置 */ int SelectMinKey(SqList L,int i) /* 返回

45、在 L.ri.L.length中 key 最小的記錄的序號 */ int min; int j,k; k=i; /* 設第 i 個為最小 */ min=L.ri.key; for(j=i+1;j=L.length;j+) if(L.rj.keymin) /* 找到更小的 */ k=j; min=L.rj.key; return k; void SelectSort(SqList *L) /* 對順序表 L 作簡單選擇排序。算法10.9 */ int i,j; RedType t; for(i=1;i0)&(flag=1) flag=0; for(j=1;j(*L).rj+1.key) 名師資料

46、總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 28 頁，共 31 頁 - - - - - - - - - flag=1; x=(*L).rj; (*L).rj=(*L).rj+1; (*L).rj+1=x; m-; int Partition(SqList *L,int low,int high) /* 交換順序表L 中子表 L.rlow.high的記錄，使樞軸記錄到位， */ /* 并返回其所在位置，此時在它之前 ( 后) 的記錄均不大 ( 小) 于它。算法 10.6(a) */ Red

47、Type t; int pivotkey; pivotkey=(*L).rlow.key; /* 用子表的第一個記錄作樞軸記錄 */ while(lowhigh) /* 從表的兩端交替地向中間掃描 */ while(low=pivotkey) -high; t=(*L).rlow; /* 將比樞軸記錄小的記錄交換到低端 */ (*L).rlow=(*L).rhigh; (*L).rhigh=t; while(lowhigh&(*L).rlow.key=pivotkey) +low; t=(*L).rlow; /* 將比樞軸記錄大的記錄交換到高端 */ (*L).rlow=(*L).rhigh;

48、 (*L).rhigh=t; return low; /* 返回樞軸所在位置 */ void QSort(SqList *L,int low,int high) /* 對順序表 L 中的子序列L.rlow.high作快速排序。算法10.7 */ int pivotloc; if(lowhigh) /* 長度大于 1 */ pivotloc=Partition(L,low,high); /* 將 L.rlow.high一分為二 */ QSort(L,low,pivotloc-1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */ QSort(L,pivotloc+1,high); /*

49、 對高子表遞歸排序 */ void QuickSort(SqList *L) 名師資料總結 - - -精品資料歡迎下載 - - - - - - - - - - - - - - - - - - 名師精心整理 - - - - - - - 第 29 頁，共 31 頁 - - - - - - - - - /* 對順序表 L 作快速排序。算法10.8 */ QSort(L,1,(*L).length); void print(SqList L) int i; for(i=1;i=L.length;i+) printf(%d ,L.ri.key); printf(n); int main() printf

50、(輸入%d個數n,N); RedType dN=0; SqList L1,L2,L3,L4; int i; for(i=0;iN;i+) /* 給 l1.r賦值 */ printf(輸入 d%d=,i); scanf(%d,&di); L1.ri+1=di; L1.length=N; L4=L3=L2=L1; printf(排序前 :n); print(L1); InsertSort(&L1); printf(直接插入排序后 :n); print(L1); printf(簡單選擇排序后 :n); SelectSort(&L2); print(L2); printf(冒泡排序后 :n); bub