1、棧和隊列的基本操作實現及其應用精品資料實驗 二 棧和隊列的基本操作實現及其應用一 _一、實驗目的1、熟練掌握棧和隊列的基本操作在兩種存儲結構上的實現。一 _二、實驗內容題目一、試寫一個算法，判斷依次讀入的一個以為結束符的字符序列，是否為回文。所謂“回文是指正向讀和反向讀都一樣的一字符串，女口 “321123或“ableelba。”相關常量及結構定義：#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10 typedef int SElemType;typedef struct SqStack SElemType *base;SElemTyp

2、e *top;int stacksize;SqStack;設計相關函數聲明：判斷函數：int lsReverse() 棧：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e ) int Pop(SqStack & S,SEIemType &e) int StackEmpty(s)三、數據結構與核心算法的設計描述1、初始化棧/*函數功能：對棧進行初始化。參數：棧(SqStack S)。成功初始化返回 0,否則返回-1 */int InitStack(SqStack &S)僅供學習與交流，如有侵權請聯系網站刪除謝謝2S.base=(

3、SEIemType *)malloc(10*sizeof(SEIemType); if(!S.base) /判斷有無申請到空間return -1;/沒有申請到內存，參數失敗返回-1S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType; return 0;2、判斷棧是否是空/*函數功能：判斷棧是否為空。參數；棧(SqStack S)。棧為空時返回-1,不為空返回0*/int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;3、入棧0,否/*函數功能：向

4、棧中插入元素。參數；棧(SqStack S),元素(SElemtype e)。成功插入返回 則返回-1 */int Push(SqStack & S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType);/重新分配空間if(!S.base) return -1;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;插入操作return 0;4、出棧僅供學習與

5、交流，如有侵權請聯系網站刪除 謝謝3/*函數功能：在棧中刪除元素。參數;棧(SqStack S),元素(SEIemtype e)。成功刪除返回 0,否則 返回-1 */int Pop(SqStack & S,SEIemType &e)if(S.top=S.base) return -1;e=*-S.top;刪除操作return 0;5、判斷是否為回文/*函數功能：判斷棧中的字符串是否為回文。參數；棧(SqStack S)。是回文時返回1,否則返回0*/int lsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) r

6、eturn 0;return 1;一四、函數的調用主函數主要設計：in t lpp;char ch;SqStack p;In itStack(p);coutvv請輸入字符：;while(ch=ci n. get()&ch!=)Push(p,ch);bj=ch; j+;僅供學習與交流，如有侵權請聯系網站刪除謝謝4if (StackEmpty(p)=-1)cout此為空棧endl;return 0; lpp=lsReverse(p);if(lpp=O) cout此字符串不是回文。endl;else cout此字符串是回文。e ndl;一 _五、實驗總結通過這次試驗我熟悉了對棧的基本操作，對基本的棧

7、操作有了很好的掌握，知道自 己容易在什么地方出錯，。一 _六、程序清單#in cludeusing n amespace std;#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10char bSTACK_INIT_SIZE+STACKINCREMENT;int j=0;typedef char SElemType;typedef struct SqStack SElemType *base;SElemType *top;int stacksize;SqStack;int InitStack(SqStack &S)S.base=(SEle

8、mType *)malloc(10*sizeof(SEIemType); if(!S.base) return -1;S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType;return 0;int StackEmpty(SqStack S)僅供學習與交流，如有侵權請聯系網站刪除 謝謝5if(S.top=S.base) return -1;else return 0;int Push(SqStack & S,SEIemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType *)

9、realloc(S.base,(S.stacksize+1) sizeof(SElemType);if(!S.base) return -1;S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 0;int Pop(SqStack & S,SElemType &e)if(S.top=S.base) return -1;e=*-S.top;return 0;int IsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) retu

10、rn 0;return 1;int main()int lpp;char ch;SqStack p;僅供學習與交流，如有侵權請聯系網站刪除謝謝6In itStack(p);coutvv請輸入字符：；while(ch=ci n. get()&ch!=)Push(p,ch);bj=ch;j+；if (StackEmpty(p)=-1)cout此為空棧endl;return 0;lpp=IsReverse(p);if(lpp=0) cout此字符串不是回文。endl;else coutvv此字符串是回文。 next=NULL;return 0;2、入隊列int En Queue(L in kQueu

11、e & Q,QElemType e)QueuePtr lpp; lpp=(QueuePtr)malloc(sizeof(QNode);if(!lpp) return -1;lpp-data=e; lpp-n ext=NULL;if(Q.fro nt=NULL)Q.front-n ext=lpp;僅供學習與交流，如有侵權請聯系網站刪除 謝謝8精品資料僅供學習與交流，如有侵權請聯系網站刪除 謝謝 Q.rear=lpp;elseQ.rear- n ext=lpp;Q.rear=lpp;return 0;3、出隊列int DeQueue(L in kQueue & Q,QEIemType &e) Qu

12、euePtr lpp;if(Q.fr on t=Q.rear) return -1;lpp=Q.fr ont-n ext;e=lpp-data;Q.front-n ext=lpp-n ext; if(Q.rear=lpp) Q.rear=Q.fro nt; delete lpp;return 0;4、統計隊列的長度int QueueLe ngth(L in kQueue Q)QueuePtr lpp=Q.fr ont;int i=0;while(lpp!=Q.rear)i+;lpp=lpp-n ext;return i;5、查找隊列的某個元素int QueueF in d(L in kQueu

13、e Q,QElemType e)QueuePtr p;p=Q.fr ont-n ext;while(p) if(p_data=e)return 1; p=p-n ext;return 0;6、遍歷隊列int QueueTraverse(L in kQueue Q) QueuePtr p;p=Q.fr ont-n ext;while(p)coutdatan ext;coute ndl;return 0;7、主界面函數void zhujiemia n()coute ndl;cout【tt數據結構實驗二】endl;cout【ttcout【tt 1隊列初始化】endl;cout【tt 2出隊列】end

14、l;cout【tt 3入隊列】endl;cout【tt 4隊列長度】endl;cout【tt 5在隊列中查找兀素】endl;cout【tt 6遍歷隊列】endl;cout【tt其他鍵退出】endl;cout【tt】endl;】endl;精品資料cout a;while(a!=1)cout a;coute ndl;doswitch(a)case 1:if(lni tQueue(Q)=0)cout初始化成功！endl;elsecout初始化失敗！endl;break;case 2:if(QueueLe ngth(Q)=0)cout隊列為空無法出隊！endl;break; if(DeQueue(Q,

15、c)=0) cout刪除成功！endl;elsecout刪除失敗！endl;break;case 3: cout輸入你要入隊元素 c;僅供學習與交流，如有侵權請聯系網站刪除謝謝11精品資料僅供學習與交流，如有侵權請聯系網站刪除 謝謝 if(E nQueue(Q,c) =0)cout入隊成功！ e ndl;elsecout入隊失敗！ e ndl;break;case 4:b=QueueLe ngth(Q);cout隊列的長度為：bendl;break;case 5:cout b;if(QueueF in d(Q,b)=1)cout恭喜您，隊列中有您要找的元素be ndl;elsecout不好意思

16、，隊列中沒有您要找的元素b a;cout0&a=6);說明：通過調用序列號不同的函數進行各種操作。函數根據每次輸入的數進行判斷不在1 6內的函數將結束，否則將繼續進行。二_五、程序調試及運行結果分析程序第一步必須執行初始化，否則程序不能運行。在程序第一步必須執行初始化后，程序完美運行，在進行任何函數操作程序都是正常運 行，而且本程序對插入和刪除時進行錯誤檢測如有的地方不可以插入，有點地方不能刪 除，如果隊列為空時則程序會輸出隊列為空，并繼續進行其他操作，大大減少了程序的bug。二_六、程序清單#in cludeusing n amespace std;typedef int QEIemType

17、;typedef struct QNodeQElemType data;struct QNode *n ext;QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;int count;Lin kQueue;int Ini tQueue(L in kQueue &Q)Q.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.fro nt) return -1;Q.fro nt- next=NULL;return 0;int En Queue(L in kQueue & Q,QEl

18、emType e)QueuePtr lpp; lpp=(QueuePtr)malloc(sizeof(QNode); if(!lpp) return -1;lpp-data=e; lpp-n ext=NULL;if(Q.fro nt=NULL)Q.front-n ext=lpp;Q.rear=lpp;elseQ.rear- n ext=lpp;Q.rear=lpp;精品資料return 0;int DeQueue(L in kQueue & Q,QEIemType &e) QueuePtr lpp;if(Q.front=Q.rear) return -1; lpp=Q.fr ont-n ext

19、;e=lpp_data;Q.front-n ext=lpp-n ext; if(Q.rear=lpp) Q.rear=Q.fro nt; delete lpp;return 0;int QueueLe ngth(L in kQueue Q)QueuePtr lpp=Q.fr ont;int i=0;while(lpp!=Q.rear)i+;lpp=lpp-n ext;return i;int QueueTraverse(L in kQueue Q)QueuePtr p;p=Q.fr ont-n ext;while(p)coutdatan ext;coutn ext;while(p)if(p_data=e)return 1; p=p-n ext;return 0;void zhujiemia n()coute ndl;cout【tt數據結構實驗二】endl;cout【ttcout【tt 1隊列