數(shù)據(jù)結(jié)構(gòu)偽代碼轉(zhuǎn)化成為可執(zhí)行源代碼.docx

數(shù)據(jù)結(jié)構(gòu)偽代碼轉(zhuǎn)化為源代碼尊重原作者的勞動，我只是個學(xué)習(xí)者，見此文章，感覺很有用，愿與大家一起分享 -百度文庫：桔紫藍(lán)*/ -*/ 出自： 編程中國*/ 作者： cobbyE-mail：QQ：51160333*/ 時間： 2007-10-26編程論壇首發(fā)*/ 聲明： 尊重作者勞動，轉(zhuǎn)載請保留本段文字*/ -前言：這些是前幾年我在大專教書時，數(shù)據(jù)結(jié)構(gòu)課程中給學(xué)生寫的學(xué)習(xí)例程，對于初學(xué)者有一定幫助。在此收集到一起，當(dāng)個共享貼貢獻(xiàn)給廣大網(wǎng)友和編程愛好者。一般程序都不難也不大，并且所有例程均有較詳細(xì)注釋，適合自學(xué)。中間有一個“哈夫曼編碼”，程序較大，希望能給大家一點(diǎn)啟示。以下所有程序均在VC+6.0開發(fā)環(huán)境中調(diào)試通過，運(yùn)行正常。有任何疑問可以“另外”發(fā)貼討論。更多內(nèi)容請訪問我的博客。自認(rèn)為本貼內(nèi)容充實，對網(wǎng)友會所很大幫助，請版主或者管理員置頂加精，謝謝。數(shù)據(jù)結(jié)構(gòu)與算法基本程序目錄一、線性表及其操作1、尾插法建立一個單鏈表，并按順序輸出2、單鏈表的元素查找，按內(nèi)容查找3、元素插入操作4、按內(nèi)容元素刪除操作5、按位置刪除元素6、建立雙向鏈表7、單鏈表就地逆置8、約瑟夫環(huán)問題二、棧及其操作1、建立堆棧2、進(jìn)棧與出棧3、棧的應(yīng)用，括號匹配三、隊及其操作1、鏈隊列的建立2、入隊和出隊3、循環(huán)隊列建立4、循環(huán)隊列的入隊和出隊操作四、串及其操作1、串的樸素匹配五、樹（二叉樹）及其操作1、二叉排序樹2、哈夫曼編碼六、排序1、冒泡排序2、直接選擇排序法一、線性表及其操作/All copyright are preserved by cobby/*尾插法建立一個單鏈表，并按順序輸出*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;l=(L)malloc(sizeof(L);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();/此語句用來吸收鍵盤輸入的回車符，沒有其它含義while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(L);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/All copyright are preserved bycobby/*單鏈表的元素查找，按內(nèi)容查找*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;int n;l=(L)malloc(sizeof(L);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(jié)點(diǎn)的連結(jié)要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*輸入!表示輸入結(jié)束*/p=(L)malloc(sizeof(L);/*為新輸入的數(shù)據(jù)分配內(nèi)存空間*/p-c=ch;p-next=NULL;/*新輸入的結(jié)點(diǎn)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/*-以上為建立一個單鏈表-*/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)的后一個元素，即實際第一個數(shù)據(jù)點(diǎn)*/n=1;/位置計數(shù)器while(q!=NULL)/*若q不為空，即該結(jié)點(diǎn)存在*/if(q-c=ch)/*字符匹配*/printf(character found in position %dn,n);q=q-next;/*移至下一個元素繼續(xù)查找*/n+;/All copyright are preserved bycobby/*元素插入操作*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/Node,*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(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)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/*以上為建立一個單鏈表*/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)/*未找到插入位置，且后面還有元素*/q=q-next;n+;/*退出循環(huán)后，要么找到插入位置，要么表已到最后，輸入的插入位置過大*/if(nc=ch;p-next=q-next;q-next=p;/*操作完成，然后輸出新表*/q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/All copyright are preserved bycobby/*按內(nèi)容元素刪除操作*/#include#include#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/Node,*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;int n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(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)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(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=1;while(q!=NULL&q-c!=ch)p=q;q=q-next;n+;/*退出循環(huán)時可能找到指定元素，也可能表讀完，需要進(jìn)一步判斷*/if(q=NULL)printf(element not found, delete failednn);elsep-next=q-next;q=l-next;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/All copyright are preserved bycobby/*按位置刪除元素*/#define NULL 0/*宏定義*/typedef struct node/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/Node,*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(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)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/*以上為建立單鏈表*/printf(Input the positionn);scanf(%d,&pos);p=l;n=1;while(p-next!=NULL&n!=pos)p=p-next;n+;/*退出循環(huán)后，可能找到刪除的元素位置，可能表讀完，需要進(jìn)一步判斷*/if(n=pos)/*刪除位置找到，刪除該位置上的元素*/p-next=p-next-next;/free(p);elseprintf(incorrect position, delete failedn);q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/建立雙向鏈表#include#include#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(%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)類型的數(shù)據(jù)結(jié)構(gòu)*/char c;/*數(shù)據(jù)域，類型為字符型*/struct node *next;/*指針域，類型為本結(jié)構(gòu)體類型*/Node,*L;/*類型重定義，即Node和*L和struct node等價*/main()L l,p,q,r;/*用指針類型定義三個結(jié)點(diǎn)類型的指針*/char ch;l=(L)malloc(sizeof(Node);/*分配內(nèi)存空間*/l-c=0;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為空*/l-next=NULL;/*指明下一個結(jié)點(diǎn)目前不存在*/q=l;/*q為游動指針，鏈表結(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)在鏈表的最后，即它的后面沒有其它元素*/q-next=p;/*q用于將上一個元素鏈接至當(dāng)前新元素*/q=p;/*q自己移到當(dāng)前最后一個元素，以備繼續(xù)鏈接所用*/scanf(%c,&ch);getchar();q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/printf(n);/以上完成了單鏈表的創(chuàng)建q=l-next;p=q-next;r=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)指向最后一個結(jié)點(diǎn)q=l;/*輸入整個鏈表前，先將q移到鏈表頭，l一般不動*/while(q-next!=NULL)/*若q所指向的元素后面還有其它元素，則將該元素的數(shù)據(jù)輸出*/printf(%c-,q-next-c);/*q-next-c表示q所指向的下一個元素的數(shù)據(jù)*/q=q-next;/*完成該元素的輸出后，q移至下一個元素重復(fù)輸出操作*/printf(n);/約瑟夫環(huán)問題#include#includetypedef struct lnodeint num;struct lnode *next;node,*L;main()int amount,start,circle,n,c;L p,l,q;printf(一共有幾個人圍成一圈？n);scanf(%d,&amount);getchar();printf(從第幾個開始計數(shù)？n);scanf(%d,&start);getchar();printf(每幾人一次循環(huán)？n);scanf(%d,&circle);getchar();l=(L)malloc(sizeof(node);/頭結(jié)點(diǎn)l-next=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)時p,q分別位于指定位置/接下去進(jìn)行周期性結(jié)點(diǎn)刪除，直到鏈表只余一個結(jié)點(diǎn)為止n=1;/n計算被刪除的結(jié)點(diǎn)的數(shù)量，當(dāng)n=amount-1時刪除結(jié)束while(n+amount)c=1;/c作為循環(huán)臨時變量while(c+next;q=q-next;/刪除當(dāng)前p指向的結(jié)點(diǎn)printf(刪除結(jié)點(diǎn)%dt,p-num);q-next=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();while(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,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);/*以上建立了一個堆棧*/printf(進(jìn)棧或出棧？輸入“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-,top-ch);p=top;while(p-next!=NULL)printf(%c-,p-ch);p=p-next;printf(n);printf(進(jìn)?；虺鰲＃枯斎搿?”為進(jìn)棧，輸入“2”為出棧，其它則退出程序n);scanf(%d,&choice);getchar();/All copyright are preserved bycobby/棧的應(yīng)用，括號匹配#include#include#define NULL 0typedef struct nodechar ch;struct node *next;snode,*stack;main()stack s,top,p;char *string,ch100=;s=(stack)malloc(sizeof(snode);/建立棧底元素s-ch=0;s-next=NULL;top=s;printf(輸入一個含括號的四則運(yùn)算表達(dá)式：n);scanf(%s,ch);string=ch;while(*string!=0)if(*string=(|*string=|*string=)/遇到左括號，入棧p=(stack)malloc(sizeof(snode);p-ch=*string;p-next=top;top=p;else if(*string=)|*string=|*string=)/遇到右括號if(*string=)if(top-ch=()/括號匹配top=top-next;elseprintf(小括號不匹配);exit(0);else if(*string=)if(top-ch=)/括號匹配top=top-next;elseprintf(中括號不匹配);exit(0);elseif(top-ch=)/括號匹配top=top-next;elseprintf(大括號不匹配);exit(0);string+;if(top-ch!=0)printf(多出左括號%cn,top-ch);三、隊及其操作/All copyright are preserved bycobby/鏈隊列的建立#include#include#include#define NULL 0typedef struct node/隊列結(jié)點(diǎn)的基本數(shù)據(jù)結(jié)構(gòu)，即隊列中每個結(jié)點(diǎn)的類型char c;struct node *next;qnode,*basic_node;typedef struct/隊列實際上由頭、尾兩個結(jié)點(diǎn)指針構(gòu)成，即頭指針和尾指針唯一確定時，隊列也被唯一確定qnode *head;qnode *rear;queue,*Q;main()Q q;/定義隊列，結(jié)構(gòu)體變量q中含有頭指針head和尾指針rear，所以q是一個完整的隊列（只不過隊列為空）/事實上，任何由Q定義的結(jié)構(gòu)體變量都是一個獨(dú)立完整的隊列basic_node p,l;/basic_node是基本結(jié)點(diǎn)類型，即是獨(dú)立的結(jié)點(diǎn)，它是組成隊列的基本元素。/基本結(jié)點(diǎn)p,l和隊列q的關(guān)系可由下圖表示：/(q-head)-p-l-p-l-p-l-(q-rear)char ch;q=(Q)malloc(sizeof(queue);q-head=NULL;/初始化時隊列為空q-rear=NULL;printf(輸入隊列元素:n);scanf(%c,&ch);getchar();whil