數據結構C語言版棧和隊列的應用編程

1、實驗目的:掌握棧的順序存儲結構的定義及順序棧中的各種基本操作。設計完成棧的綜合應用包括1.數制轉換2.判斷回文3.括號匹配實驗功能:本次實驗棧和隊列的應用，我對數制轉換、判斷回文和括號匹配進行了算法編程；主要采用棧的順序存儲結構和隊列的單鏈存儲，對棧的構造空棧、判空、入棧、出棧和隊列的構造空隊列、入隊、出隊基本操作分別進行了定義,建立了int型的數制轉換順序棧和char型的括號匹配順序棧，同時用棧和隊列判斷字符串是否回文。由于數制轉換（int）和括號匹配（char）的數據類型不同，分別對它們定義了進棧和出棧子函數，另外,我還將數制轉換分為了七個子函數，分別進行不同進制之間的轉換,我覺得這樣安排

2、對使用者來說更簡單快捷.我還將九個完整的函數塊放在一個主函數main里，形成一個完整的、可以實現九個子函數功能的主函數。再通過編寫選擇語句switchcase，實現子函數功能的選擇，循環(huán)while語句實現子函數菜單功能的重復執(zhí)行，break語句跳出循環(huán)，結束子函數功能。主函數里通過對子函數的調用實現整體函數功能。流程圖：預定義棧的存儲空間和增量存儲空間,Include頭文件主函數mainWhile主菜單switchcase選擇分支實驗過程（完整源程序）:typedefintSElemType;/定義棧元素類型為整型#include#include#includemalloc.h/malloc(

3、)等#include#includeprocess.h/exit()#includemath.h#includestdlib.h#defineSTACK_INIT_SIZE100/存儲空間初始分配量#defineSTACKINCREMENT2/存儲空間分配增量#defineMAX20structSqStack/棧的順序存儲表示SElemType*base;/在棧構造之前和銷毀之后，base的值為NULLSElemType*top;/棧頂指針intstacksize;/當前已分配的存儲空間，以元素為單位;typedefstructchar*base;/定義括號匹配的結構體char*top;cha

4、rsize;Stack;typedefstructQNode/隊列的鏈式存儲結構intdata;structQNode*next;QNode,*QueuePtr;typedefstructLinkQueueQueuePtrfront;/對頭指針QueuePtrrear;/隊尾指針LinkQueue;/單鏈隊列intInitStack(SqStack&S)/構造一個空棧Sif(!(S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)exit(0);/存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return

5、1;voidcreatstack(Stack&W)/括號匹配順序棧的建立W.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/系統(tǒng)自動生成一結點W.top=W.base;W.size=STACK_INIT_SIZE;printf(括號匹配空棧已成功創(chuàng)建!n);intStackEmpty(SqStackS)/若棧S為空棧，則返回1,否則返回0if(S.base=S.top)return1;elsereturn0;intPush(SqStack&S,inte)/入棧插入元素e為新的棧頂元素if(S.top-S.base=S.stacksize)/棧滿

6、，追加存儲空間S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)exit(0);/存儲分配失敗S.top=S.base+STACKINCREMENT;*(S.top)+=e;return1;voidPush(Stack&W,chare)/括號匹配進棧if(W.top-W.base)=W.size)W.base=(char*)realloc(W.base,(W.size+STACK_INIT_SIZE)*sizeof(char);W.top=W.base+W.size;W.size+=S

7、TACK_INIT_SIZE;*(W.top+)=e;intPop(SqStack&S,int&e)/出棧/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0if(S.top=S.base)return0;e=*-S.top;return1;voidPop(Stack&W,char&e)/括號匹配出棧if(W.top=W.base)printf(ERROR!n);e=*(-W.top);intInitQueue(LinkQueue&Q)/構造一個空隊列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(0)

8、;/存儲分配失敗Q.front-next=NULL;return1;intEnQueue(LinkQueue&Q,inte)/插入元素e為Q的新的隊尾元素QueuePtrp;if(!(p=(QueuePtr)malloc(sizeof(QNode)/存儲分配失敗exit(0);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;intQueueEmpty(LinkQueueQ)/若Q為空隊列,則返回1,否則返回0if(Q.front=Q.rear)return1;elsereturn0;intDeQueue(LinkQueue&Q,int&e

9、)/若隊列不空，刪除Q的隊頭元素，用e返回其值,并返回1,否則返回0QueuePtrP;if(Q.front=Q.rear)return0;P=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear=P)Q.rear=Q.front;free(P);return1;voidconversionA()/對于輸入的任意一個非負十進制整數，打印輸出與其等值的二進制數SqStacks;unsignedn;/非負整數SElemTypee;InitStack(s);/初始化棧printf(請輸入一個非負十進制整數n:);printf(n=);scanf(%u

10、,&n);/輸入非負十進制整數nprintf(轉換的二進制為：)；while(n)/當n不等于0Push(s,n%2);/入棧n除以2的余數(2進制的低位)n=n/2;while(!StackEmpty(s)/當棧不空Pop(s,e);/彈出棧頂元素且賦值給eprintf(%d,e);/輸出eprintf(n);voidconversionB()/對于輸入的任意一個非負10進制整數，打印輸出與其等值的8進制數SqStacks;unsignedn;/非負整數SElemTypee;InitStack(s);/初始化棧printf(請輸入一個非負十進制整數n:);printf(n=);scanf(%

11、u,&n);/輸入非負十進制整數nprintf(轉換的八進制為：)；while(n)/當n不等于0Push(s,n%8);/入棧n除以八的余數(八進制的低位)n=n/8;while(!StackEmpty(s)/當棧不空Pop(s,e);/彈出棧頂元素且賦值給eprintf(%d,e);/輸出eprintf(n);voidconversionC()/對于輸入的任意一個非負10進制整數，打印輸出與其等值的16進制數SqStacks;unsignedn;/非負整數SElemTypee;InitStack(s);/初始化棧printf(請輸入一個非負十進制整數n:);printf(n=);scanf

12、(%u,&n);/輸入非負十進制整數nprintf(轉換的十六進制為：)；while(n)/當n不等于0Push(s,n%16);/入棧n除以16的余數(16進制的低位)n=n/16;while(!StackEmpty(s)/當棧不空Pop(s,e);/彈出棧頂元素且賦值給eif(e=9)printf(%d,e);elseprintf(%c,e+55);printf(n);voidconversionD()/對于輸入的任意一個2進制整數，打印輸出與其等值的10進制數LinkQueues;unsignedn;/非負二進制整數inte;inti=0;intk=0;InitQueue(s);/初始化

13、隊列printf(請輸入一個非負二進制整數n:);printf(n=);scanf(%u,&n);/輸入非負二進制整數nprintf(轉換的十進制為：)；while(n)/當n不等于0EnQueue(s,n%10);/入隊列n除以10的余數n=n/10;while(!QueueEmpty(s)/當隊列不空DeQueue(s,e);/彈出隊頂元素且賦值給ek=k+e*pow(2,i+);printf(%d,k);printf(n);voidconversionE()/對于輸入的任意一個8進制整數，打印輸出與其等值的10進制數LinkQueues;unsignedn;/非負8進制整數inte;in

14、ti=0;intk=0;InitQueue(s);/初始化隊列printf(請輸入一個非負八進制整數n:);printf(n=);scanf(%u,&n);/輸入非負8進制整數nprintf(轉換的十進制為：)；while(n)/當n不等于0EnQueue(s,n%10);/入隊列n除以10的余數n=n/10;while(!QueueEmpty(s)/當隊列不空DeQueue(s,e);/彈出隊頂元素且賦值給e*/k=k+e*pow(8,i+);printf(%d,k);printf(n);voidconversionF()/對于輸入的任意一個16進制整數，打印輸出與其等值的10進制數char

15、n30;/存取輸入的16進制數intlen,i,j=0,dec=0;printf(請輸入一個非負十六進制整數n:);printf(n=);scanf(%s,n);printf(轉換的十進制為：)；len=strlen(n);for(i=0;i=48&ni=65&ni=97&ni=0;i-,j+)if(ni=57)dec=dec+(ni-0)*pow(16,j);elseif(ni=70)dec=dec+(ni-55)*pow(16,j);elsedec=dec+(ni-87)*pow(16,j);printf(%dn,dec);voidfactorA()/數制轉換絕對值小于1的十進制小數轉換為

16、二進制inti,j=O,chMAX;/*i為每位上的二進制數，ch為存放二進制數的數組*/floatnum;printf(請輸入一個絕對值小于1的十進制小數n:);printf(n=);scanf(%f,&num);/*輸入要轉換的十進制數小數*/printf(轉換的二進制為：)；doi=(int)(num*2);num=num*2-i;chj+=i;while(num);printf(0.);for(i=0;ij;i+)printf(%d,chi);voidfactorB()/數制轉換絕對值小于1的十進制小數轉換為八進制inti,j=O,chMAX;/*i為每位上的八進制數，ch為存放八進制

17、數的數組*/floatnum;printf(請輸入一個絕對值小于1的十進制小數n:);printf(n=);scanf(%f,&num);/*輸入要轉換的十進制數小數*/printf(轉換的八進制為：)；doi=(int)(num*8);num=num*8-i;chj+=i;while(num);printf(0.);for(i=0;ij;i+)printf(%d,chi);voidBracket(Stack&W,char*str)/括號匹配inti=0,flag1=0;chare;while(stri!=0)switch(stri)case:Push(W,);break;case:Push(

18、W,);break;case(:Push(W,();break;case:Pop(W,e);if(e!=)flag1=1;break;case:Pop(W,e);if(e!=)flag1=1;break;case):Pop(W,e);if(e!=()flag1=1;break;default:break;if(flag1)break;i+;if(!flag1&(W.top=W.base)printf(括號匹配！n);elseprintf(括號不匹配！n);voidfit(Stack&W)/括號匹配函數的實現creatstack(W);charstr200;printf(請輸入字符串:);sca

19、nf(%s,&str);Bracket(W,str);intPalindrome_Test()/判別輸入的字符串是否回文序列SqStackS;LinkQueueQ;InitStack(S);InitQueue(Q);/inti;/記錄次數的變量charV;SElemTypeV1,V2;while(V=getchar()!=)/獲取一個字符Push(S,V);/將數據插入棧EnQueue(Q,V);/插入隊列同時使用棧和隊列兩種結構while(S.top！=S.base)Pop(S,V1);/出棧DeQueue(Q,V2);/出隊列if(V1！=V2)return0;return1;/Palin

20、drome_Testintmain()intmenu;StackW;while(1)printf(n);printf(棧和隊列的應用n）；printf(printf(*1、10-2進制整數轉換*n)printf(*2、10-8進制整數轉換*n)printf(*3、10-16進制整數轉換*n)printf(*4、2-10進制整數轉換*n)printf(*5、8-10進制整數轉換*n)printf(*6、16-10進制整數轉換*n)printf(*7、10-2進制小數轉換*n)printf(*8、括號匹配*n)printf(*9、回文判斷*n)printf(*0、退出*n)printf(printf(n請選擇相應操作n);/選擇菜單scanf(%d,&menu);switch(menu)case1:conversionA();/10-2進制整數轉換break;case2:conversionB();/10-8進制整數轉換break;case3:con