《數(shù)據(jù)結(jié)構(gòu)》部分理論實踐源代碼集(C實現(xiàn))

1、數(shù)據(jù)結(jié)構(gòu)部分理論實踐源代碼集/*線性表順序存儲的基本操作*/.2/*線性表鏈式存儲-單鏈表的基本操作*/.5/*雙鏈表的基本操作*/.9/*順序表應用*/.13/*單鏈表的應用*/.14/*順序棧的基本操作*/.16/*鏈式棧的基本操作*/.18/*棧的應用:求表達式值*/.20/*順序隊的基本操作*/.23/*循環(huán)隊的基本操作*/.25/*鏈式隊的基本操作*/.27/*隊列應用-求迷宮問題*/30/*隊列排序(習題3.6)*/.32/*只有一個指針rear的鏈式隊的基本操作(習題3.7)*/.34/*順序串的基本操作*/.37/*鏈式串基本操作*/.41/*矩陣的基本操作*/.47/*三元組

2、稀疏矩陣的基本操作*/.49/*鏈式稀疏矩陣的基本操作*/.53/*二叉樹基本操作*/.56/*二叉樹遍歷*/.60/*二叉排序樹基本操作*/.62/*構(gòu)造哈夫曼樹*/.66/*有向圖的鄰接矩陣生成和顯示*/.68/*無向圖的鄰接表生成和顯示*/.70/*無向圖的深度優(yōu)先搜索*/.72/*無向圖的寬度優(yōu)先搜索*/.74/*普里姆算法構(gòu)造最小生成樹*/.77/*克魯斯卡爾算法構(gòu)造最小生成樹*/.79/*Dijkstra算法求最短路徑*/.81/*Floyd算法求最短路徑*/.83/*直接插入排序算法*/.85/*希爾排序算法*/.86/*直接選擇排序算法*/.88/*冒泡排序算法*/.89/*冒

3、泡排序算法*/.90/*歸并排序算法*/.92/*哈希表：開放地址法解決沖突*/.94/*哈希表：拉鏈法解決沖突*/.96/*鏈表的應用-求兩個一元多項式之和*/.98/*棧的應用-判斷一個數(shù)是否是回文數(shù)*/102/*采用順序結(jié)構(gòu)存儲串,編寫一個函數(shù),求串s和串t的一個最長公共子串*/104/*二叉樹的應用-設計一個表示家譜的二叉樹*/.106/*快速排序的設計*/.110 /*哈希表查找設計*/.113/*線性表順序存儲的基本操作*/ #include #define MaxSize 50 typedef char ElemType; struct List ElemType listMax

4、Size; int size; ; void setnull(struct List *p) p-size=0; int length(struct List *p) return(p-size); int get(struct List *p,int i) if (ip-size) return(-1); else return(p-listi-1); int locate(struct List *p,ElemType x) int i=0; while (isize & p-listi!=x) i+; if (i=p-size) return(-1); else return(i+1);

5、 void insert(struct List *p,ElemType x,int i) int j; if (ip-size+1) printf(位置參數(shù)不正確,不能進行插入操作!n); else p-size+;for (j=p-size-1;j=i;j-) /*結(jié)點向后移動,騰出一個位置*/ p-listj=p-listj-1;p-listj=x; void delete(struct List *p,int i) int j; if (ip-size | i1)printf(位置參數(shù)不正確,不能進行刪除操作!n); else for (j=i-1;jsize-1;j+) /*結(jié)點向前

6、移動,覆蓋該刪除的結(jié)點*/ p-listj=p-listj+1;p-size-; display(struct List *p) int j; if (p-size=0) printf(該線性表為空,不能顯示!n); else printf(線性表:); if (p-size=1) /*只有一個結(jié)點的情況*/ printf(%c,p-listp-size); else /*有一個以上結(jié)點的情況*/ for (j=0;jsize-1;j+) printf(%c,p-listj); printf(%c,p-listj); /*顯示最后一個結(jié)點*/ printf(n); main() struct

7、List L; setnull(&L); insert(&L,a,1); insert(&L,b,2); insert(&L,a,1); insert(&L,c,2); insert(&L,d,1); insert(&L,e,2); display(&L); printf(值:%c 位置:%dn,a,locate(&L,a); printf(位置:%d 值:%cn,4,get(&L,4); printf(刪除第2個結(jié)點后); delete(&L,2); display(&L); printf(刪除第2個結(jié)點后); delete(&L,2); display(&L); printf(刪除第1個結(jié)

8、點后); delete(&L,1); display(&L); printf(刪除第1個結(jié)點后); delete(&L,1); display(&L); /*線性表鏈式存儲-單鏈表的基本操作*/ #include #include typedef char ElemType; struct LNode ElemType data; struct LNode *next; setnull(struct LNode *p) *p=NULL; int length(struct LNode *p) int n=0; struct LNode *q=*p; while (q!=NULL) n+;q=q

9、-next; return(n); ElemType get(struct LNode *p,int i) int j=1; struct LNode *q=*p; while (jnext;j+; if (q!=NULL) /*找到了第i個結(jié)點*/ return(q-data); else printf(位置參數(shù)不正確!n); int locate(struct LNode *p,ElemType x) int n=0; struct LNode *q=*p; while (q!=NULL & q-data!=x) /*查找data域為x的第一個結(jié)點*/ q=q-next;n+; if (q

10、=NULL) /*未找到data域等于x的結(jié)點*/ return(-1); else /*找到data域等于x的結(jié)點*/ return(n+1); void insert(struct LNode *p,ElemType x,int i) int j=1; struct LNode *s,*q; s=(struct LNode *)malloc(sizeof(struct LNode); /*建立要插入的結(jié)點s*/ s-data=x; q=*p; if (i=1) /*插入的結(jié)點作為頭結(jié)點*/ s-next=q; *p=s; else while (jnext!=NULL) /*查找第i-1個

11、結(jié)點*/ q=q-next;j+; if (j=i-1) /*找到了第i-1個結(jié)點,由q指向它*/ s-next=q-next; /*將結(jié)點s插入到q結(jié)點之后*/ q-next=s; else printf(位置參數(shù)不正確!n); void delete(struct LNode *p,int i) int j=1; struct LNode *q=*p,*t; if (i=1) /*刪除鏈表的頭結(jié)點*/ t=q;*p=q-next; else while (jnext!=NULL) /*查找第i-1個結(jié)點*/ q=q-next;j+; if (q-next!=NULL & j=i-1) /*

12、找到第i-1個結(jié)點,由q指向它*/ t=q-next; /*t指向要刪除的結(jié)點*/ q-next=t-next; /*將q之后的結(jié)點刪除*/ else printf(位置參數(shù)不正確!n); if (t!=NULL) /*在t不為空時釋放該結(jié)點*/ free(t); void display(struct LNode *p) struct LNode *q; q=*p; printf(單鏈表顯示:); if (q=NULL) /*鏈表為空時*/ printf(鏈表為空!); else if (q-next=NULL) /*鏈表只有一個結(jié)點時*/ printf(%cn,q-data); else

13、/*鏈表存在一個以上的結(jié)點時*/ while (q-next!=NULL) /*顯示前面的結(jié)點*/ printf(%c,q-data);q=q-next; printf(%c,q-data); /*顯示最后一個結(jié)點*/ printf(n); main() struct LNode *head; setnull(&head); insert(&head,a,1); insert(&head,b,2); insert(&head,a,2); insert(&head,c,4); insert(&head,d,3); insert(&head,e,1); display(&head); printf

14、(單鏈表長度=%dn,length(&head); printf(位置:%d 值:%cn,3,get(&head,3); printf(值:%c 位置:%dn,a,locate(&head,a); printf(刪除第1個結(jié)點:); delete(&head,1); display(&head); printf(刪除第5個結(jié)點:); delete(&head,5); display(&head); printf(刪除開頭3個結(jié)點:); delete(&head,3); delete(&head,2); delete(&head,1); display(&head); /*雙鏈表的基本操作*/

15、#include #include typedef char ElemType; struct DNode ElemType data; struct DNode *left,*right; setnull(struct DNode *p) *p=NULL; int length(struct DNode *p) int n=0; struct DNode *q=*p; while (q!=NULL) n+;q=q-right; return(n); ElemType get(struct DNode *p,int i) int j=1; struct DNode *q=*p; while (

16、jright;j+; if (q!=NULL) /*找到了第i個結(jié)點*/ return(q-data); else printf(位置參數(shù)不正確!n); int locate(struct DNode *p,ElemType x) int n=0; struct DNode *q=*p; while (q!=NULL & q-data!=x) /*查找data域為x的第一個結(jié)點*/ q=q-right;n+; if (q=NULL) /*未找到data域等于x的結(jié)點*/ return(-1); else /*找到data域等于x的結(jié)點*/ return(n+1); void insert(st

17、ruct DNode *p,ElemType x,int i) int j=1; struct DNode *s,*q; s=(struct DNode *)malloc(sizeof(struct DNode); /*建立要插入的結(jié)點s*/ s-data=x; s-left=s-right=NULL; q=*p; if (i=1) /*插入的結(jié)點作為表頭結(jié)點*/ s-right=q; if (q!=NULL) /*原來的雙鏈表不為空*/ q-left=s; *p=s; else while (jright!=NULL) /*查找第i-1個結(jié)點*/ q=q-right;j+; if (j=i-

18、1) /*找到了第i-1個結(jié)點,由q指向它*/ if (q-right!=NULL) /*q不是最后一個結(jié)點*/ s-right=q-right; /*將結(jié)點s插入到q結(jié)點和之后結(jié)點q-right之間*/ q-right-left=s; s-left=q; q-right=s; else /*q是最后一個結(jié)點*/ s-left=q; /*將s作為表尾結(jié)點*/ q-right=s; else printf(位置參數(shù)不正確!n); void delete(struct DNode *p,int i) int j=1; struct DNode *q=*p,*t; if (i=1) /*刪除鏈表的頭

19、結(jié)點*/ t=q;q=q-right;if (q!=NULL) /*當雙鏈表不只一個結(jié)點時*/ q-left=NULL;*p=q; else while (jright!=NULL) /*查找第i-1個結(jié)點*/ q=q-right;j+; if (q-right!=NULL & j=i-1) /*找到第i-1個結(jié)點,由q指向它*/ t=q-right; /*t指向要刪除的結(jié)點*/ if (t-right!=NULL) /*刪除的結(jié)點不是最后結(jié)點*/ q-right=t-right; /*將q之后的結(jié)點刪除*/ q-right-left=q; else /*刪除的結(jié)點是最后結(jié)點*/ q-righ

20、t=NULL; else printf(位置參數(shù)不正確!n); if (t!=NULL) /*在t不為空時釋放該結(jié)點*/ free(t); void display(struct DNode *p) struct DNode *q; q=*p; printf(雙鏈表顯示:); if (q=NULL) /*鏈表為空時*/ printf(鏈表為空!); else if (q-right=NULL) /*鏈表只有一個結(jié)點時*/ printf(%cn,q-data); else /*鏈表存在一個以上的結(jié)點時*/ while (q-right!=NULL) /*顯示前面的結(jié)點*/ printf(%c,q

21、-data);q=q-right; printf(%c,q-data); /*顯示最后一個結(jié)點*/ printf(n); main() struct DNode *dhead; setnull(&dhead); insert(&dhead,a,1); insert(&dhead,b,2); insert(&dhead,a,2); insert(&dhead,c,4); insert(&dhead,d,3); insert(&dhead,e,1); display(&dhead); printf(雙鏈表長度=%dn,length(&dhead); printf(位置:%d 值:%cn,3,get

22、(&dhead,3); printf(值:%c 位置:%dn,a,locate(&dhead,a); printf(刪除第1個結(jié)點:); delete(&dhead,1); display(&dhead); printf(刪除第5個結(jié)點:); delete(&dhead,5); display(&dhead); printf(刪除開頭3個結(jié)點:); delete(&dhead,3); delete(&dhead,2); delete(&dhead,1); display(&dhead); /*順序表應用*/ #include #define MaxSize 50 main() int m,n,

23、d,i,count; int AMaxSize; printf(輸入猴子個數(shù)n,m號:); scanf(%d,%d,&n,&m); for (i=0;in;i+) Ai=i+1; printf(出隊前:); for (i=0;in;i+) printf(%d ,Ai); printf(n); printf(出隊后:); count=0; d=0; /*d記錄退出圈外的猴子個數(shù)*/ while (dn) for (i=0;in;i+) if (Ai!=0) count+; if (count=m) /*第i個猴子退出*/ printf(%d ,Ai); Ai=0; /*元素值清0*/ count

24、=0; /*計數(shù)器重置為0*/ d+; /*單鏈表的應用*/ #include #include struct Node int data; struct Node *next; main() struct Node *head,*s,*q,*t; int n,m,count=0,i; printf(輸入猴子個數(shù)n,m號:); scanf(%d,%d,&n,&m); for (i=1;idata=i; s-next=NULL; if (i=1) /*建立表頭結(jié)點*/ head=s,q=head; /*head作為表頭結(jié)點,q總是指向鏈表的最后一個結(jié)點*/ else /*建立其他結(jié)點*/ q-n

25、ext=s; q=q-next; q-next=head; /*建立循環(huán)單鏈表*/ printf(出隊前:); q=head; /*q先指向表頭結(jié)點*/ while (q-next!=head) /*顯示出隊前的順序*/ printf(%d ,q-data);q=q-next; printf(%dn,q-data); printf(出隊后:); q=head; /*q先指向表頭結(jié)點*/ do count+; /*計數(shù)器增1*/ if (count=m-1) /*第i個猴子退出*/ t=q-next; /*t指向要刪除的結(jié)點*/ q-next=t-next; /*刪除結(jié)點t*/ count=0;

26、 /*計數(shù)器重置0*/ printf(%d ,t-data);q=q-next; while (q-next!=q); /*循環(huán)直到只剩一個結(jié)點*/ printf(%dn,q-data); /*顯示最后的一個結(jié)點值*/ /*順序棧的基本操作*/ #include #define MaxSize 100 typedef char ElemType; typedef struct char stackMaxSize; int top; stacktype; void initstack(stacktype *S) S-top=-1; void push(stacktype *S,ElemType

27、x) if (S-top=MaxSize) printf(棧上溢出!n); else S-top+; S-stackS-top=x; void pop(stacktype *S) if (S-top=-1) printf(棧下溢出!n); else S-top-; ElemType gettop(stacktype *S) if (S-top=-1) printf(棧空!n); else return(S-stackS-top); int empty(stacktype *S) if (S-top=-1) return(1); else return(0); void display(stac

28、ktype *S) int i; printf(棧中元素:); for (i=S-top;i=0;i-) printf(%c ,S-stacki); printf(n); main() stacktype *st; printf(建立一空棧n); initstack(st); printf(棧空:%dn,empty(st); printf(依次插入a,b,c,d元素n); push(st,a); push(st,b); push(st,c); push(st,d); display(st); printf(退一次棧n); pop(st); printf(棧頂元素:%cn,gettop(st);

29、 printf(退一次棧n); pop(st); display(st); /*鏈式棧的基本操作*/ #include typedef char ElemType; typedef struct linknode ElemType data; struct linknode *next; linkstack; void initstack(linkstack *S) *S=NULL; void push(linkstack *S,ElemType x) linkstack *q; q=(linkstack *)malloc(sizeof(linkstack); q-data=x; q-next

30、=*S; *S=q; void pop(linkstack *S) linkstack *t; if (*S=NULL) printf(棧下溢出!n); else t=*S; *S=t-next; free(t); ElemType gettop(linkstack *S) if (*S=NULL) return(-1); else return(*S)-data); int empty(linkstack *S) if (*S=NULL) return(1); else return(0); void display(linkstack *S) linkstack *q; printf(棧中

31、元素:); q=*S; while (q!=NULL) printf(%c ,q-data); q=q-next; printf(n); main() linkstack *stack; printf(建立一空棧n); initstack(&stack); printf(?？?%dn,empty(&stack); printf(依次插入a,b,c,d元素n); push(&stack,a); push(&stack,b); push(&stack,c); push(&stack,d); display(&stack); printf(退一次棧n); pop(&stack); printf(棧頂

32、元素:%cn,gettop(&stack); printf(退一次棧n); pop(&stack); display(&stack); /*棧的應用:求表達式值*/ #include #define MAX 100 char expMAX; /*存儲轉(zhuǎn)換成的后綴表達式*/ void trans() /*將算術(shù)表達式轉(zhuǎn)換成后綴表達式*/ char strMAX; /*存儲原算術(shù)表達式*/ char stackMAX; /*作為棧使用*/ char ch; int sum,i,j,t,top=0; /*t作為exp的下標,top作為stack的下標,i作為str的下標*/ printf(*n);

33、printf(* 輸入一個求值的表達式,以#結(jié)束。只能包含+,-,*,/運算符和正整數(shù) *n); printf(*n); printf(算術(shù)表達式:); i=0; /*獲取用戶輸入的表達式*/ do i+; scanf(%c,&stri); while (stri!=# & i!=MAX); sum=i; /*記錄輸入表達式總的字符個數(shù)*/ t=1;i=1; ch=stri;i+; while (ch!=#) switch(ch) case (: /*判定為左括號*/ top+;stacktop=ch; break; case ): /*判定為右括號*/ while (stacktop!=() expt=stacktop;top-;t+; top-; break; case +: /*判定為加減號*/ case -: while (top!=0 & stacktop!=() expt=stacktop;top-;t+; top+;stacktop=ch; break; case *: /*判定為*或/號*/ case /: while (stacktop=* | stacktop=/) expt=stacktop;