棧和隊(duì)列的基本操作實(shí)現(xiàn)及其應(yīng)用參考模板

1、實(shí)驗(yàn) 二 棧和隊(duì)列的基本操作實(shí)現(xiàn)及其應(yīng)用一_一、實(shí)驗(yàn)?zāi)康?、熟練掌握棧和隊(duì)列的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。一_二、實(shí)驗(yàn)內(nèi)容題目一、試寫(xiě)一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字符序列，是否為回文。所謂“回文“是指正向讀和反向讀都一樣的一字符串,如“321123”或“ableelba”。相關(guān)常量及結(jié)構(gòu)定義：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef struct SqStack SElemType *base; SElemType *top; int stacksize;S

2、qStack;設(shè)計(jì)相關(guān)函數(shù)聲明：判斷函數(shù)：int IsReverse()棧：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s)一_三、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、初始化棧/* 函數(shù)功能：對(duì)棧進(jìn)行初始化 。參數(shù)：棧(SqStack S)。成功初始化返回0,否則返回-1 */int InitStack(SqStack &S)1 / 19 S.base=(SElemType *)mall

3、oc(10*sizeof(SElemType);if(!S.base) /判斷有無(wú)申請(qǐng)到空間 return -1; /沒(méi)有申請(qǐng)到內(nèi)存,參數(shù)失敗返回-1S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType;return 0;2、判斷棧是否是空/*函數(shù)功能:判斷棧是否為空。參數(shù); 棧(SqStack S)。棧為空時(shí)返回-1,不為空返回0*/int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;3、入棧/*函數(shù)功能:向棧中插入元素。參數(shù); 棧(SqSta

4、ck S),元素(SElemtype e)。成功插入返回0,否則返回-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、出棧/*函數(shù)功能:在

5、棧中刪除元素。參數(shù);棧(SqStack S),元素(SElemtype e)。成功刪除返回0,否則返回-1 */int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return -1;e=*-S.top; /刪除操作return 0;5、判斷是否為回文/*函數(shù)功能:判斷棧中的字符串是否為回文。參數(shù); 棧(SqStack S)。是回文時(shí)返回1,否則返回0*/int IsReverse(SqStack &S)int i;char a;for(i=0;i<j;i+)Pop(S,a);if(a!=bi) return 0;re

6、turn 1;一_四、函數(shù)的調(diào)用主函數(shù)主要設(shè)計(jì)：int lpp;char ch;SqStack p;InitStack(p);cout<<"請(qǐng)輸入字符："while(ch=cin.get()&&ch!='')Push(p,ch);bj=ch;j+;if (StackEmpty(p)=-1) cout<<"此為空棧"<<endl;return 0;lpp=IsReverse(p);if(lpp=0) cout<<"此字符串不是回文。"<<endl

7、;else cout<<"此字符串是回文。"<<endl;一_五、實(shí)驗(yàn)總結(jié)通過(guò)這次試驗(yàn)我熟悉了對(duì)棧的基本操作，對(duì)基本的棧操作有了很好的掌握，知道自己容易在什么地方出錯(cuò)，。一_六、程序清單#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10char bSTACK_INIT_SIZE+STACKINCREMENT;int j=0;typedef char SElemType;typedef struct SqStac

8、k SElemType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) S.base=(SElemType *)malloc(10*sizeof(SElemType);if(!S.base) return -1;S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType;return 0;int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;int Pu

9、sh(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;int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return -1;e=*-

10、S.top;return 0;int IsReverse(SqStack &S)int i;char a;for(i=0;i<j;i+)Pop(S,a);if(a!=bi) return 0;return 1;int main()int lpp;char ch;SqStack p;InitStack(p);cout<<"請(qǐng)輸入字符："while(ch=cin.get()&&ch!='')Push(p,ch);bj=ch;j+;if (StackEmpty(p)=-1) cout<<"此為空棧&q

11、uot;<<endl;return 0;lpp=IsReverse(p);if(lpp=0) cout<<"此字符串不是回文。"<<endl;else cout<<"此字符串是回文。"<<endl;return 0;二_一、實(shí)驗(yàn)?zāi)康?、會(huì)用棧和隊(duì)列解決簡(jiǎn)單的實(shí)際問(wèn)題。二_二、實(shí)驗(yàn)內(nèi)容題目二、編程模擬隊(duì)列的管理，主要包括：出隊(duì)列、入隊(duì)、統(tǒng)計(jì)隊(duì)列的長(zhǎng)度、查找隊(duì)列某個(gè)元素e、及輸出隊(duì)列中元素。相關(guān)常量及結(jié)構(gòu)定義：typedef int QElemType;typedef struct QNodeQEl

12、emType data; struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; int count;LinkQueue;設(shè)計(jì)相關(guān)函數(shù)聲明：InitQueue(LinkQueue &Q)EnQueue(LinkQueue &Q,QElemType e)DeQueue(LinkQueue &Q,QElemType &e)QueueLength(LinkQueue Q)QueueTraverse(LinkQueue Q)QueueFind(LinkQueue

13、Q,QElemType e)二_三、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、初始化隊(duì)列int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) return -1;Q.front->next=NULL;return 0;2、入隊(duì)列int EnQueue(LinkQueue &Q,QElemType e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);if(!lpp) return -1;lpp->data=e; l

14、pp->next=NULL; if(Q.front=NULL)Q.front->next=lpp;Q.rear=lpp; else Q.rear->next=lpp;Q.rear=lpp; return 0;3、出隊(duì)列int DeQueue(LinkQueue &Q,QElemType &e)QueuePtr lpp;if(Q.front=Q.rear) return -1;lpp=Q.front->next;e=lpp->data;Q.front->next=lpp->next;if(Q.rear=lpp) Q.rear=Q.fron

15、t;delete lpp;return 0;4、統(tǒng)計(jì)隊(duì)列的長(zhǎng)度int QueueLength(LinkQueue Q)QueuePtr lpp=Q.front;int i=0;while(lpp!=Q.rear)i+;lpp=lpp->next;return i;5、查找隊(duì)列的某個(gè)元素int QueueFind(LinkQueue Q,QElemType e)QueuePtr p;p=Q.front->next;while(p)if(p->data=e) return 1;p=p->next;return 0; 6、遍歷隊(duì)列int QueueTraverse(LinkQ

16、ueue Q)QueuePtr p; p=Q.front->next;while(p) cout<<p->data<<'t' p=p->next;cout<<endl;return 0;7、主界面函數(shù)void zhujiemian()cout<<endl;cout<<"【tt 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二 】"<<endl;cout<<"【tt-】"<<endl;cout<<"【tt 1 隊(duì)列初始化 】"&l

17、t;<endl; cout<<"【tt 2 出隊(duì)列 】"<<endl;cout<<"【tt 3 入隊(duì)列 】"<<endl; cout<<"【tt 4 隊(duì)列長(zhǎng)度 】"<<endl;cout<<"【tt 5 在隊(duì)列中查找元素 】"<<endl;cout<<"【tt 6 遍歷隊(duì)列 】"<<endl;cout<<"【tt 其他鍵退出 】"<&

18、lt;endl;cout<<"【tt-】"<<endl;cout<<"【tt 請(qǐng)選擇要進(jìn)行操作的序號(hào)（1-6） 】:"二_四、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)主函數(shù)主要涉及：LinkQueue Q;int a,b,c;zhujiemian();cin>>a;while(a!=1) cout<<"輸入錯(cuò)誤，必須先初始化，請(qǐng)重新輸入："cin>>a;cout<<endl;doswitch(a)case 1:if(InitQueue(Q)=0)cout<<&

19、quot;初始化成功！"<<endl;elsecout<<"初始化失??！"<<endl;break;case 2:if(QueueLength(Q)=0)cout<<"隊(duì)列為空無(wú)法出隊(duì)！"<<endl;break;if(DeQueue(Q,c)=0)cout<<"刪除成功！"<<endl;elsecout<<"刪除失?。?quot;<<endl;break;case 3:cout<<"輸

20、入你要入隊(duì)元素"<<endl;cin>>c;if(EnQueue(Q,c) =0)cout<<"入隊(duì)成功！"<<endl;elsecout<<"入隊(duì)失?。?quot;<<endl;break;case 4:b=QueueLength(Q);cout<<"隊(duì)列的長(zhǎng)度為："<<b<<endl;break;case 5:cout<<"您要查找的元素："cin>>b;if(QueueFind(

21、Q,b)=1)cout<<"恭喜您，隊(duì)列中有您要找的元素"<<b<<endl;elsecout<<"不好意思，隊(duì)列中沒(méi)有您要找的元素"<<b<<endl;break;case 6:QueueTraverse(Q);break;default:break; zhujiemian();cin>>a;cout<<endl;while(a>0&&a<=6);說(shuō)明：通過(guò)調(diào)用序列號(hào)不同的函數(shù)進(jìn)行各種操作。函數(shù)根據(jù)每次輸入的數(shù)進(jìn)行判斷不在16內(nèi)的

22、函數(shù)將結(jié)束，否則將繼續(xù)進(jìn)行。二_五、程序調(diào)試及運(yùn)行結(jié)果分析 程序第一步必須執(zhí)行初始化，否則程序不能運(yùn)行。 在程序第一步必須執(zhí)行初始化后，程序完美運(yùn)行，在進(jìn)行任何函數(shù)操作程序都是正常運(yùn)行，而且本程序?qū)Σ迦牒蛣h除時(shí)進(jìn)行錯(cuò)誤檢測(cè)如有的地方不可以插入，有點(diǎn)地方不能刪除，如果隊(duì)列為空時(shí)則程序會(huì)輸出隊(duì)列為空，并繼續(xù)進(jìn)行其他操作，大大減少了程序的bug。二_六、程序清單#include<iostream>using namespace std;typedef int QElemType;typedef struct QNodeQElemType data;struct QNode *next;Q

23、Node, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;int count;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) return -1;Q.front->next=NULL;return 0;int EnQueue(LinkQueue &Q,QElemType e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);i

24、f(!lpp) return -1;lpp->data=e; lpp->next=NULL; if(Q.front=NULL)Q.front->next=lpp;Q.rear=lpp; else Q.rear->next=lpp;Q.rear=lpp; return 0;int DeQueue(LinkQueue &Q,QElemType &e)QueuePtr lpp;if(Q.front=Q.rear) return -1;lpp=Q.front->next;e=lpp->data;Q.front->next=lpp->nex

25、t;if(Q.rear=lpp) Q.rear=Q.front;delete lpp;return 0;int QueueLength(LinkQueue Q)QueuePtr lpp=Q.front;int i=0;while(lpp!=Q.rear)i+;lpp=lpp->next;return i;int QueueTraverse(LinkQueue Q)QueuePtr p; p=Q.front->next;while(p) cout<<p->data<<'t' p=p->next;cout<<endl;re

26、turn 0; int QueueFind(LinkQueue Q,QElemType e)QueuePtr p;p=Q.front->next;while(p)if(p->data=e) return 1;p=p->next;return 0; void zhujiemian()cout<<endl;cout<<"【tt 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二 】"<<endl;cout<<"【tt-】"<<endl;cout<<"【tt 1 隊(duì)列初始化 】"<

27、<endl; cout<<"【tt 2 出隊(duì)列 】"<<endl;cout<<"【tt 3 入隊(duì)列 】"<<endl; cout<<"【tt 4 隊(duì)列長(zhǎng)度 】"<<endl;cout<<"【tt 5 在隊(duì)列中查找元素 】"<<endl;cout<<"【tt 6 遍歷隊(duì)列 】"<<endl;cout<<"【tt 其他鍵退出 】"<<endl;cout<<"【tt-】"<<endl;cout<<"【tt 請(qǐng)選擇要進(jìn)行操作的序號(hào)（1-6） 】:"int main()LinkQueue Q;int a,b,c;zhujiemian();cin>>a;while(a!=1) cout<<"輸入錯(cuò)誤，必須先初始化，請(qǐng)重新輸入："cin>>a;cout<&