數(shù)據(jù)結(jié)構(gòu)與算法基本程序

1、數(shù)據(jù)結(jié)構(gòu)與算法基本程序目錄一、線性表及其操作1、尾插法建立一個(gè)單鏈表，并按順序輸出2、單鏈表的元素查找，按內(nèi)容查找3、元素插入操作4、按內(nèi)容元素刪除操作5、按位置刪除元素6、建立雙向鏈表7、單鏈表就地逆置8、約瑟夫環(huán)問(wèn)題二、棧及其操作1、建立堆棧2、進(jìn)棧與出棧3、棧的應(yīng)用，括號(hào)匹配三、隊(duì)及其操作1、鏈隊(duì)列的建立2、入隊(duì)和出隊(duì)3、循環(huán)隊(duì)列建立4、循環(huán)隊(duì)列的入隊(duì)和出隊(duì)操作四、串及其操作1、串的樸素匹配五、樹(shù)（二叉樹(shù)）及其操作1、二叉排序樹(shù)2、哈夫曼編碼六、排序1、冒泡排序2、直接選擇排序法一、線性表及其操作/All copyright are preserved by cobby/*尾插法建立一個(gè)

2、單鏈表，并按順序輸出*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本結(jié)構(gòu)體類(lèi)型*/*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,q;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;l=(L)malloc(sizeof(L);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)

3、點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();/此語(yǔ)句用來(lái)吸收鍵盤(pán)輸入的回車(chē)符，沒(méi)有其它含義while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(L);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭

4、，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/All copyright are preserved bycobby/*單鏈表的元素查找，按內(nèi)容查找*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本

5、結(jié)構(gòu)體類(lèi)型*/*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,q;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;int n;l=(L)malloc(sizeof(L);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(L);/*為

6、新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)

7、元素重復(fù)輸出操作*/*-以上為建立一個(gè)單鏈表-*/printf(nInput a character you wanna findn);scanf(%c,&ch);printf(nthe character you wanna find is %cn,ch);q=l-next;/*q移至頭結(jié)點(diǎn)的后一個(gè)元素，即實(shí)際第一個(gè)數(shù)據(jù)點(diǎn)*/n=1;/位置計(jì)數(shù)器while(q!=NULL)/*若q不為空，即該結(jié)點(diǎn)存在*/if(q-c=ch)/*字符匹配*/printf(character found in position %dn,n);q=q-next;/*移至下一個(gè)元素繼續(xù)查找*/n+;/All cop

8、yright are preserved bycobby/*元素插入操作*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本結(jié)構(gòu)體類(lèi)型*/Node,*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,q;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/

9、l-next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(Node);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar(

10、);q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/*以上為建立一個(gè)單鏈表*/printf(Input the character and its position, such as s,3nn);scanf(%c,%d,&ch,&pos);q=l;n=1;while(n!=pos&q-next!=NULL)/*未找

11、到插入位置，且后面還有元素*/q=q-next;n+;/*退出循環(huán)后，要么找到插入位置，要么表已到最后，輸入的插入位置過(guò)大*/if(nc=ch;p-next=q-next;q-next=p;/*操作完成，然后輸出新表*/q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/All copyright are preserv

12、ed bycobby/*按內(nèi)容元素刪除操作*/#include#include#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/ char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本結(jié)構(gòu)體類(lèi)型*/Node,*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,q;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;int n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-

13、next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(Node);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();

14、q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/*以上為建立單鏈表*/printf(input the character you wanna deletenn);scanf(%c,&ch);printf(the element you wanna delete is %cnn,ch);q=l-next;p=l;n=

15、1;while(q!=NULL&q-c!=ch)p=q;q=q-next;n+;/*退出循環(huán)時(shí)可能找到指定元素，也可能表讀完，需要進(jìn)一步判斷*/if(q=NULL)printf(element not found, delete failednn);elsep-next=q-next;q=l-next;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操

16、作*/All copyright are preserved bycobby/*按位置刪除元素*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本結(jié)構(gòu)體類(lèi)型*/Node,*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,q;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的

17、數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(Node);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&c

18、h);getchar();q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/*以上為建立單鏈表*/printf(Input the positionn);scanf(%d,&pos);p=l;n=1;while(p-next!=NULL&n!=pos)p=p-next;n+;/*退出循環(huán)后，可能找到刪除的元素位置，可能

19、表讀完，需要進(jìn)一步判斷*/if(n=pos)/*刪除位置找到，刪除該位置上的元素*/p-next=p-next-next;/free(p);elseprintf(incorrect position, delete failedn);q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/建立雙向鏈表#include#inc

20、lude#include#define NULL 0typedef struct dlnodechar ch;struct dlnode *pri,*next;dnode,*dl;main()dl l,p,q;char c;l=(dl)malloc(sizeof(dnode);l-ch=0;l-next=NULL;l-pri=NULL;q=l;printf(輸入字符建立雙向鏈表n);scanf(%c,&c);getchar();while(c!=!)p=(dl)malloc(sizeof(dnode);p-ch=c;p-pri=q;p-next=NULL;q-next=p;q=p;scanf(

21、%c,&c);getchar();q=l;while(q-next!=NULL)q=q-next;printf(%c-,q-ch);printf(n);while(q-pri!=NULL)printf(%c-,q-ch);q=q-pri;printf(n);/單鏈表就地逆置#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類(lèi)型為字符型*/struct node *next;/*指針域，類(lèi)型為本結(jié)構(gòu)體類(lèi)型*/Node,*L;/*類(lèi)型重定義，即Node和*L和struct node等價(jià)*/main()L l,p,

22、q,r;/*用指針類(lèi)型定義三個(gè)結(jié)點(diǎn)類(lèi)型的指針*/char ch;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存在*/q=l;/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(Node);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后

23、面沒(méi)有其它元素*/q-next=p;/*q用于將上一個(gè)元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個(gè)元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/printf(n);/以上完成了單鏈表的創(chuàng)建q=l-next;p=q-next;r=

24、p-next;q-next=NULL;while(r!=NULL)p-next=q;q=p;p=r;if(r-next!=NULL)/r后面還有結(jié)點(diǎn)，則逆置繼續(xù)r=r-next;elsebreak;r-next=q;l-next=r;/頭結(jié)點(diǎn)指向最后一個(gè)結(jié)點(diǎn)q=l;/*輸入整個(gè)鏈表前，先將q移到鏈表頭，l一般不動(dòng)*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個(gè)元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個(gè)元素重復(fù)輸出操作*/printf

25、(n);/約瑟夫環(huán)問(wèn)題#include#includetypedef struct lnodeint num;struct lnode *next;node,*L;main()int amount,start,circle,n,c;L p,l,q;printf(一共有幾個(gè)人圍成一圈？n);scanf(%d,&amount);getchar();printf(從第幾個(gè)開(kāi)始計(jì)數(shù)？n);scanf(%d,&start);getchar();printf(每幾人一次循環(huán)？n);scanf(%d,&circle);getchar();l=(L)malloc(sizeof(node);/頭結(jié)點(diǎn)l-next

26、=NULL;l-num=0;q=l;n=0;while(n+next=NULL;p-num=n;q-next=p;q=p;q-next=l-next;/形成循環(huán)鏈表/以上完成了單向循環(huán)鏈表的建立p=l-next;q=l;n=1;while(n+next;q=q-next;/退出循環(huán)時(shí)p,q分別位于指定位置/接下去進(jìn)行周期性結(jié)點(diǎn)刪除，直到鏈表只余一個(gè)結(jié)點(diǎn)為止n=1;/n計(jì)算被刪除的結(jié)點(diǎn)的數(shù)量，當(dāng)n=amount-1時(shí)刪除結(jié)束while(n+amount)c=1;/c作為循環(huán)臨時(shí)變量while(c+next;q=q-next;/刪除當(dāng)前p指向的結(jié)點(diǎn)printf(刪除結(jié)點(diǎn)%dt,p-num);q-n

27、ext=p-next;p=p-next;printf(n最后剩下%dn,p-num);二、棧及其操作/All copyright are preserved bycobby/*建立堆棧*/#include#include#define NULL 0typedef struct nodechar ch;struct node *next;Snode,*stack;main()stack s,top,p;char ch;s=(stack)malloc(sizeof(Snode);s-ch=0;s-next=NULL;/*建立棧底指針*/top=s;scanf(%c,&ch);getchar();w

28、hile(ch!=!)p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;scanf(%c,&ch);getchar();while(top-next!=NULL)printf(%c-,top-ch);top=top-next;printf(n);/All copyright are preserved bycobby/*進(jìn)棧與出棧*/#include#include#define NULL 0typedef struct nodechar ch;struct node *next;Snode,*stack;main()stack s,

29、top,p;char ch;int choice;s=(stack)malloc(sizeof(Snode);s-ch=!;s-next=NULL;/*建立棧底指針*/top=s;scanf(%c,&ch);getchar();while(ch!=!)p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;scanf(%c,&ch);getchar();while(p-next!=NULL)/此處p可用top代替printf(%c-,p-ch);p=p-next;printf(n);/*以上建立了一個(gè)堆棧*/printf(進(jìn)?；虺鰲?？輸入“

30、1”為進(jìn)棧，輸入“2”為出棧，其它則退出程序n);scanf(%d,&choice);getchar();while(choice=1|choice=2)/若不是輸入1或2，則不做任何操作if(choice=1)/*進(jìn)棧*/printf(n輸入要入棧的元素n);scanf(%c,&ch);getchar();p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;else if(choice=2)if(top-next!=NULL)top=top-next;elseprintf(棧已清空n);exit();/*出棧*/printf(%c-,

31、top-ch);p=top;while(p-next!=NULL)printf(%c-,p-ch);p=p-next;printf(n);printf(進(jìn)?；虺鰲?？輸入“1”為進(jìn)棧，輸入“2”為出棧，其它則退出程序n);scanf(%d,&choice);getchar();/All copyright are preserved bycobby/棧的應(yīng)用，括號(hào)匹配#include#include#define NULL 0typedef struct nodechar ch;struct node *next;snode,*stack;main()stack s,top,p;char *st

32、ring,ch100=;s=(stack)malloc(sizeof(snode);/建立棧底元素s-ch=0;s-next=NULL;top=s;printf(輸入一個(gè)含括號(hào)的四則運(yùn)算表達(dá)式：n);scanf(%s,ch);string=ch;while(*string!=0)if(*string=(|*string=|*string=)/遇到左括號(hào)，入棧p=(stack)malloc(sizeof(snode);p-ch=*string;p-next=top;top=p;else if(*string=)|*string=|*string=)/遇到右括號(hào)if(*string=)if(top

33、-ch=()/括號(hào)匹配top=top-next;elseprintf(小括號(hào)不匹配);exit(0);else if(*string=)if(top-ch=)/括號(hào)匹配top=top-next;elseprintf(中括號(hào)不匹配);exit(0);elseif(top-ch=)/括號(hào)匹配top=top-next;elseprintf(大括號(hào)不匹配);exit(0);string+;if(top-ch!=0)printf(多出左括號(hào)%cn,top-ch); HYPERLINK /Article/kfyy/sjjg/200710/6629.html 三、隊(duì)及其操作/All copyright ar

34、e preserved bycobby/鏈隊(duì)列的建立#include#include#include#define NULL 0typedef struct node/隊(duì)列結(jié)點(diǎn)的基本數(shù)據(jù)結(jié)構(gòu)，即隊(duì)列中每個(gè)結(jié)點(diǎn)的類(lèi)型char c;struct node *next;qnode,*basic_node;typedef struct/隊(duì)列實(shí)際上由頭、尾兩個(gè)結(jié)點(diǎn)指針構(gòu)成，即頭指針和尾指針唯一確定時(shí)，隊(duì)列也被唯一確定qnode *head;qnode *rear;queue,*Q;main()Q q;/定義隊(duì)列，結(jié)構(gòu)體變量q中含有頭指針head和尾指針rear，所以q是一個(gè)完整的隊(duì)列（只不過(guò)隊(duì)列為空）/

35、事實(shí)上，任何由Q定義的結(jié)構(gòu)體變量都是一個(gè)獨(dú)立完整的隊(duì)列basic_node p,l;/basic_node是基本結(jié)點(diǎn)類(lèi)型，即是獨(dú)立的結(jié)點(diǎn)，它是組成隊(duì)列的基本元素。/基本結(jié)點(diǎn)p,l和隊(duì)列q的關(guān)系可由下圖表示：/(q-head)-p-l-p-l-p-l-(q-rear)char ch;q=(Q)malloc(sizeof(queue);q-head=NULL;/初始化時(shí)隊(duì)列為空q-rear=NULL;printf(輸入隊(duì)列元素:n);scanf(%c,&ch);getchar();while(ch!=!)p=(qnode*)malloc(sizeof(qnode);p-c=ch;p-next=NU

36、LL;/新來(lái)的元素一定在隊(duì)列的最后，它的后面沒(méi)有其它元素if(q-head=NULL)q-head=p;/第一個(gè)元素入隊(duì)時(shí)，隊(duì)頭指針指向它l=q-head;/l指向第一個(gè)元素l-next=p;/使前一個(gè)元素指向當(dāng)前入隊(duì)的新元素l=p;/l移動(dòng)到當(dāng)前新元素，以備用下次入隊(duì)操作q-rear=p;/修改隊(duì)尾指針，使其總是指向當(dāng)前最后一個(gè)隊(duì)列元素scanf(%c,&ch);getchar();l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(頭指針指向元素為%ct尾指針指向元素為%cn,q-head-c,q-rear-c );/A

37、ll copyright are preserved bycobby/入隊(duì)和出隊(duì)#include#include#include#define NULL 0typedef struct node/隊(duì)列結(jié)點(diǎn)的基本數(shù)據(jù)結(jié)構(gòu)，即隊(duì)列中每個(gè)結(jié)點(diǎn)的類(lèi)型char c;struct node *next;qnode,*basic_node;typedef struct/隊(duì)列實(shí)際上由頭、尾兩個(gè)結(jié)點(diǎn)指針構(gòu)成，即頭指針和尾指針唯一確定時(shí)，隊(duì)列也被唯一確定qnode *head;qnode *rear;queue,*Q;main()Q q;/定義隊(duì)列，結(jié)構(gòu)體變量q中含有頭指針head和尾指針rear，所以q是一個(gè)完

38、整的隊(duì)列（只不過(guò)隊(duì)列為空）/事實(shí)上，任何由Q定義的結(jié)構(gòu)體變量都是一個(gè)獨(dú)立完整的隊(duì)列basic_node p,l;/basic_node是基本結(jié)點(diǎn)類(lèi)型，即是獨(dú)立的結(jié)點(diǎn)，它是組成隊(duì)列的基本元素。/基本結(jié)點(diǎn)p,l和隊(duì)列q的關(guān)系可由下圖表示：/(q-head)-p-l-p-l-p-l-(q-rear)char ch;int choice;q=(Q)malloc(sizeof(queue);q-head=NULL;/初始化時(shí)隊(duì)列為空q-rear=NULL;printf(輸入隊(duì)列元素:n);scanf(%c,&ch);getchar();while(ch!=!)p=(qnode*)malloc(sizeo

39、f(qnode);p-c=ch;p-next=NULL;/新來(lái)的元素一定在隊(duì)列的最后，它的后面沒(méi)有其它元素if(q-head=NULL)q-head=p;/第一個(gè)元素入隊(duì)時(shí)，隊(duì)頭指針指向它l=q-head;/l指向第一個(gè)元素l-next=p;/使前一個(gè)元素指向當(dāng)前入隊(duì)的新元素l=p;/l移動(dòng)到當(dāng)前新元素，以備用下次入隊(duì)操作q-rear=p;/修改隊(duì)尾指針，使其總是指向當(dāng)前最后一個(gè)隊(duì)列元素scanf(%c,&ch);getchar();l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(頭指針指向元素為%ct尾指針指向元素為%

40、cn,q-head-c,q-rear-c );/以上建立了一個(gè)隊(duì)列printf(輸入1進(jìn)行入隊(duì)，輸入2進(jìn)行出隊(duì):n);scanf(%d,&choice);getchar();if(choice=1)printf(n輸入要入隊(duì)的元素:n);scanf(%c,&ch);getchar();p=(qnode*)malloc(sizeof(qnode);/給新入隊(duì)的元素分配內(nèi)存空間p-c=ch;p-next=NULL;/新元素為最后一個(gè)元素q-rear-next=p;/原來(lái)最后一個(gè)元素指向新入隊(duì)的元素q-rear=p;/修改隊(duì)尾指針，使其指向當(dāng)前最后一個(gè)元素else if(choice=2)q-hea

41、d=q-head-next;elseexit(0);l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(頭指針指向元素為%ct尾指針指向元素為%cn,q-head-c,q-rear-c );/All copyright are preserved bycobby/循環(huán)隊(duì)列建立#include#include#define MAX 8typedef structchar cMAX;/循環(huán)隊(duì)列是順序隊(duì)列的一種，它的核心就是一個(gè)數(shù)組int front;/整形變量，作為頭指針用int rear;/整形變量，作為尾指針用queue;m

42、ain()queue *q;char ch;int i;q=(queue*)malloc(sizeof(queue);/生成一個(gè)空循環(huán)隊(duì)列for(i=0;ici=0;q-front=0;q-rear=0;printf(輸入要入隊(duì)的元素:n);scanf(%c,&ch);getchar();while(ch!=!)if(q-rear+1)%MAX=q-front)/若隊(duì)列已滿(mǎn)printf(隊(duì)列已滿(mǎn)，無(wú)法入隊(duì)n);break;elseq-cq-rear=ch;/rear指向當(dāng)前可入隊(duì)的數(shù)組元素位置q-rear=(q-rear+1)%MAX;/修改尾指針，向后移動(dòng)一個(gè)位置/注意，不能簡(jiǎn)單使用q-re

43、ar+，不然會(huì)導(dǎo)致隊(duì)列溢出scanf(%c,&ch);getchar();for(i=q-front;irear;i=(i+1)%MAX)/能夠用for循環(huán)，說(shuō)明了順序隊(duì)列和鏈?zhǔn)疥?duì)列的區(qū)別printf(%cci);printf(n);/All copyright are preserved bycobby/循環(huán)隊(duì)列的入隊(duì)和出隊(duì)操作#include#include#define MAX 8typedef structdchar cMAX;/循環(huán)隊(duì)列是順序隊(duì)列的一種，它的核心就是一個(gè)數(shù)組int front;/整形變量，作為頭指針用int rear;/整形變量，作為尾指針用queue;main()q

44、ueue *q;char ch;int i,choice;q=(queue*)malloc(sizeof(queue);/生成一個(gè)空循環(huán)隊(duì)列for(i=0;ici=0;q-front=0;q-rear=0;printf(輸入要入隊(duì)的元素:n);scanf(%c,&ch);getchar();while(ch!=!)if(q-rear+1)%MAX=q-front)/若隊(duì)列已滿(mǎn)printf(隊(duì)列已滿(mǎn)，無(wú)法入隊(duì)n);break;elseq-cq-rear=ch;/rear指向當(dāng)前可入隊(duì)的數(shù)組元素位置q-rear=(q-rear+1)%MAX;/修改尾指針，向后移動(dòng)一個(gè)位置/注意，不能簡(jiǎn)單使用q-r

45、ear+，不然會(huì)導(dǎo)致隊(duì)列溢出scanf(%c,&ch);getchar();printf(頭指針指向元素為%dt尾指針指向元素為%dn,q-front,q-rear);for(i=q-front;irear;i=(i+1)%MAX)/能夠用for循環(huán)，說(shuō)明了順序隊(duì)列和鏈?zhǔn)疥?duì)列的區(qū)別printf(%c-,q-ci);printf(n);/以上建立了一個(gè)循環(huán)隊(duì)列printf(輸入1入隊(duì)，輸入2出隊(duì):n);scanf(%d,&choice);getchar();while(choice=1|choice=2)if(choice=1)printf(輸入要入隊(duì)的元素n);scanf(%c,&ch);ge

46、tchar();if(q-rear+1)%MAX=q-front)/若隊(duì)列已滿(mǎn)printf(隊(duì)列已滿(mǎn)，無(wú)法入隊(duì)n);break;elseq-cq-rear=ch;/rear指向當(dāng)前可入隊(duì)的數(shù)組元素位置q-rear=(q-rear+1)%MAX;/修改尾指針，向后移動(dòng)一個(gè)位置/注意，不能簡(jiǎn)單使用q-rear+，不然會(huì)導(dǎo)致隊(duì)列溢出else if(choice=2)if(q-front+1)%MAX!=q-rear)/隊(duì)非空q-cq-front=0;/刪除元素q-front=(q-front+1)%MAX;/修改隊(duì)頭指針elseprintf(隊(duì)已清空n);break;if(q-rearq-front

47、)/尾指針在頭指針的右邊f(xié)or(i=q-front;irear;i=(i+1)%MAX)/能夠用for循環(huán)，說(shuō)明了順序隊(duì)列和鏈?zhǔn)疥?duì)列的區(qū)別printf(%cci);printf(n);else/尾指針在頭指針的左邊f(xié)or(i=q-front;irear+MAX);i+)/能夠用for循環(huán)，說(shuō)明了順序隊(duì)列和鏈?zhǔn)疥?duì)列的區(qū)別printf(%cci%MAX);printf(n);printf(頭指針指向元素為%dt尾指針指向元素為%dn,q-front,q-rear);printf(輸入1入隊(duì)，輸入2出隊(duì):n);scanf(%d,&choice);getchar();四、串及其操作/串的樸素匹配#in

48、cludemain()char str1100,str2100,*p;int i=0,j=0,len_str1=0,len_str2=0,num=0;printf(輸入母串:n);scanf(%s,str1);getchar();printf(%輸入子串:n);scanf(%s,str2);getchar();p=str1;while(*p!=0)/獲取母串長(zhǎng)度len_str1+;p+;p=str2;/獲取子串長(zhǎng)度while(*p!=0)len_str2+;p+;for(i=0;ilen_str1;i+)/i為母串下標(biāo)for(j=0;jlen_str2;j+)/j為子串下標(biāo)num+;if(st

49、r1i+j!=str2j)break;/若當(dāng)前字符不匹配，則指針向母串下一個(gè)字符移動(dòng)if(j=len_str2)printf(子串在母串中的位置為%dn,i+1);/break;/若子串在母串中多次出現(xiàn)，則全部找到其位置。若恢復(fù)break語(yǔ)句則只找出最前的一個(gè)匹配子串printf(母串長(zhǎng)度為%d,子串長(zhǎng)度為%dn核心語(yǔ)句執(zhí)行次數(shù)為%dn,len_str1,len_str2,num);五、樹(shù)（二叉樹(shù)）及其操作/二叉排序樹(shù)#include#includetypedef struct tnodeint num;struct tnode *Lchild,*Rchild;Tnode,*Btree;typ

50、edef struct snodeint num;Btree r;struct snode *next;Snode,*stack;Btree root;void describe_tree()/交互式顯示哈夫曼樹(shù)Btree t;stack s,top,temp;int choice;s=(stack)malloc(sizeof(Snode);s-num=0;s-next=NULL;s-r=NULL;top=s;t=root;/t指向哈夫曼樹(shù)的根結(jié)點(diǎn)temp=(stack)malloc(sizeof(Snode);/分配新棧結(jié)點(diǎn)temp-num=t-num;temp-next=top;/結(jié)點(diǎn)入棧

51、temp-r=t;/將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)top=temp;/修改棧頂指針printf(輸入1往左子樹(shù)，輸入2往右子樹(shù)，輸入3返回父結(jié)點(diǎn)，其它輸入退出程序n);scanf(%d,&choice);getchar();while(choice=1|choice=2|choice=3)if(choice=1)/往左子樹(shù)if(t-Lchild!=NULL)t=t-Lchild;temp=(stack)malloc(sizeof(Snode);/分配新棧結(jié)點(diǎn)/新結(jié)點(diǎn)入棧temp-num=t-num;temp-next=top;/結(jié)點(diǎn)入棧temp-r=t;/將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)top=

52、temp;/修改棧頂指針printf(值為%dn,t-num);else/左子樹(shù)不存在，當(dāng)前結(jié)點(diǎn)已經(jīng)是葉子結(jié)點(diǎn)printf(無(wú)左孩子！n);else if(choice=2)/往右子樹(shù)if(t-Rchild!=NULL)t=t-Rchild;temp=(stack)malloc(sizeof(Snode);/分配新棧結(jié)點(diǎn)/新結(jié)點(diǎn)入棧temp-num=t-num;temp-next=top;/結(jié)點(diǎn)入棧temp-r=t;/將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)top=temp;/修改棧頂指針printf(值為%dn,t-num);else/右子樹(shù)不存在，當(dāng)前結(jié)點(diǎn)已經(jīng)是葉子結(jié)點(diǎn)printf(無(wú)右孩子！n);

53、else if(choice=3)/返回父結(jié)點(diǎn)if(top-next!=s)/棧非空top=top-next;t=top-r;printf(值為%dn,t-num);elseprintf(已經(jīng)在根結(jié)點(diǎn)了！n);scanf(%d,&choice);getchar();void inorder(Btree r)/中序遞歸遍歷if(r!=NULL)inorder(r-Lchild);printf( %d num);inorder(r-Rchild);main()int array100,n=0,i,choice;Btree p,q;for(i=0;inum=arrayn;root-Lchild=NU

54、LL;root-Rchild=NULL;n+;elseexit(0);while(arrayn!=0)p=(Btree)malloc(sizeof(Tnode);/依次給每個(gè)整數(shù)分配結(jié)點(diǎn)p-num=arrayn;p-Lchild=NULL;p-Rchild=NULL;/分配完結(jié)點(diǎn)后，要插入到二叉樹(shù)中合適的位置q=root;/q初始化到根結(jié)點(diǎn)while(q!=NULL)if(q-numnum)/若新結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值，則往右子樹(shù)if(q-Rchild!=NULL)/當(dāng)前結(jié)點(diǎn)有右孩子，則指針移向右孩子繼續(xù)比較q=q-Rchild;else/當(dāng)前結(jié)點(diǎn)沒(méi)有右孩子，則新結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)的右孩子q-Rc

55、hild=p;break;elseif(q-Lchild!=NULL)/當(dāng)前結(jié)點(diǎn)有左孩子，則指針移向左孩子繼續(xù)比較q=q-Lchild;else/當(dāng)前結(jié)點(diǎn)沒(méi)有左孩子，則新結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)的左孩子q-Lchild=p;break;n+;/建立二叉排序樹(shù)完畢/對(duì)其進(jìn)行中序遍歷printf(n哈夫曼樹(shù)構(gòu)造完成，是否查看哈夫曼樹(shù)，輸入1查看，其它輸入跳過(guò));scanf(%d,&choice);getchar();if(choice=1)describe_tree();inorder(root);printf(n);哈夫曼算法程序太大，一個(gè)貼放不下，下面兩個(gè)貼均為哈夫曼編碼程序./2005/4/28/Al

56、l Copyright Are Reserved By cobby/哈夫曼編碼#include#include#include#define NULL 0typedef struct huff_code_node/存儲(chǔ)編碼的鏈表char ch;/編碼對(duì)應(yīng)的字符char code100;/字符對(duì)應(yīng)的哈夫曼碼struct huff_code_node *next;hnode,*huff;typedef struct tree_Node/二叉樹(shù)結(jié)點(diǎn)char ch;/字符內(nèi)容int amount;/字符在字符串中出現(xiàn)的次數(shù)struct tree_Node *left,*right;/指向左子樹(shù)與右子樹(shù)

57、tnode,*bt;typedef struct list_node/鏈表結(jié)點(diǎn)char ch;/存儲(chǔ)字符串中的字符int amount;/字符在字符串中出現(xiàn)的次數(shù)tnode *son;/鏈表結(jié)點(diǎn)帶有二叉子樹(shù)的根結(jié)點(diǎn)指針struct list_node *next;/指向鏈表中下一個(gè)結(jié)點(diǎn)Node,*L;typedef struct stack_nodechar ch;/存儲(chǔ)字符int amount;/出現(xiàn)次數(shù)bt son;/指向二叉樹(shù)的某結(jié)點(diǎn)struct stack_node *next;snode,*stack;char t200,*str,*c;/用于存儲(chǔ)和處理輸入的字符串bt root=N

58、ULL;/哈夫曼樹(shù)L l,p,q,new_node;/鏈表結(jié)點(diǎn)huff hlist;/計(jì)算得到的編碼表int char_num;/輸入的不同字符數(shù)量int char_amount;/輸入的所有字符數(shù)量int code_sum;/哈夫曼編碼總長(zhǎng)void initial()/初始化操作l=(Node*)malloc(sizeof(Node);/建立空鏈表l-ch=0;l-amount=0;l-son=NULL;l-next=NULL;str=t;/將字符串指針指向字符串的第一個(gè)位置/鍵盤(pán)輸入字符串printf(輸入字符串進(jìn)行哈夫曼編碼:n);scanf(%s,str);getchar();void

59、 pull_in_list()int exist;/表示當(dāng)前字符是否存在于鏈表中，0為不存在，1為已存在int n;/計(jì)算輸入不同字符的數(shù)量，計(jì)算后賦值給全局變量char_numint m;/計(jì)算輸入所有字符的數(shù)量，計(jì)算后賦值給全局變量char_amountc=str;/c指向第一個(gè)字符while(*c!=0)/若字符串未讀完exist=0;p=l;/p指向鏈表頭結(jié)點(diǎn)/尋找該字符是否已經(jīng)在鏈表中while(p-next!=NULL)/若鏈表非空p=p-next;if(p-ch=*c)/若當(dāng)前字符已經(jīng)在鏈表中exist=1;p-amount+;/字符出現(xiàn)次數(shù)加1break;if(exist=0)

60、/若當(dāng)前字符不存在于鏈表中，則分配一個(gè)結(jié)點(diǎn)入表new_node=(Node*)malloc(sizeof(Node);new_node-ch=*c;new_node-amount=1;new_node-next=NULL;new_node-son=NULL;p-next=new_node;p=new_node;c+;/讀下一個(gè)字符printf(統(tǒng)計(jì)結(jié)果:n);p=l;n=0;m=0;while(p-next!=NULL)n+;p=p-next;m+=p-amount;printf(%c%dn,p-ch,p-amount);char_num=n;char_amount=m;printf(一共有%