棧和隊列的基本操作實現(xiàn)及其應(yīng)用_第1頁
棧和隊列的基本操作實現(xiàn)及其應(yīng)用_第2頁
棧和隊列的基本操作實現(xiàn)及其應(yīng)用_第3頁
棧和隊列的基本操作實現(xiàn)及其應(yīng)用_第4頁
棧和隊列的基本操作實現(xiàn)及其應(yīng)用_第5頁
已閱讀5頁,還剩20頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、;實驗 二 棧和隊列的基本操作實現(xiàn)及其應(yīng)用一_一、實驗?zāi)康?、熟練掌握棧和隊列的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)。一_二、實驗內(nèi)容題目一、試寫一個算法,判斷依次讀入的一個以為結(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;

2、SqStack;設(shè)計相關(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è)計描述1、初始化棧/* 函數(shù)功能:對棧進行初始化 。參數(shù):棧(SqStack S)。成功初始化返回0,否則返回-1 */int InitStack(SqStack &S) S.base=(SElemType *)malloc(10*sizeof(SElemType);i

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

4、入返回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ù)功能:在棧中刪除元素。參數(shù);棧(SqStack S),元素(SElemty

5、pe 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)。是回文時返回1,否則返回0*/int IsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) return 0;return 1;一_四、函數(shù)的調(diào)用主函數(shù)主要設(shè)計:int lpp;char ch;SqStack p

6、;InitStack(p);cout請輸入字符:;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;else cout此字符串是回文。endl;一_五、實驗總結(jié)通過這次試驗我熟悉了對棧的基本操作,對基本的棧操作有了很好的掌握,知道自己容易在什么地方出錯,。一_六、程序清單#includeusing namespace std;#define STACK_INIT_SIZE 100#

7、define 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=(SElemType *)malloc(10*sizeof(SElemType);if(!S.base) return -1;S.top=S.base;S.stacksize=STACK_INI

8、T_SIZE;S.base=new SElemType;return 0;int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;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+=STAC

9、KINCREMENT;*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) return 0;return 1;int main()int lpp;char ch;SqStack p;InitStack(p);cout請輸入字符:;while(ch=cin.get()&ch!=)Push(p,ch);bj=ch;j+

10、;if (StackEmpty(p)=-1) cout此為空棧endl;return 0;lpp=IsReverse(p);if(lpp=0) cout此字符串不是回文。endl;else cout此字符串是回文。next=NULL;return 0;2、入隊列int EnQueue(LinkQueue &Q,QElemType e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);if(!lpp) return -1;lpp-data=e; lpp-next=NULL; if(Q.front=NULL)Q.front-next=lpp;Q.rea

11、r=lpp; else Q.rear-next=lpp;Q.rear=lpp; return 0;3、出隊列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.front;delete lpp;return 0;4、統(tǒng)計隊列的長度int QueueLength(LinkQueue Q)QueuePtr lpp=Q.front;int i=0;

12、while(lpp!=Q.rear)i+;lpp=lpp-next;return i;5、查找隊列的某個元素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、遍歷隊列int QueueTraverse(LinkQueue Q)QueuePtr p; p=Q.front-next;while(p) coutdatanext;coutendl;return 0;7、主界面函數(shù)void zhujiemian()couten

13、dl;cout【tt 數(shù)據(jù)結(jié)構(gòu)實驗二 】endl;cout【tt-】endl;cout【tt 1 隊列初始化 】endl; cout【tt 2 出隊列 】endl;cout【tt 3 入隊列 】endl; cout【tt 4 隊列長度 】endl;cout【tt 5 在隊列中查找元素 】endl;cout【tt 6 遍歷隊列 】endl;cout【tt 其他鍵退出 】endl;cout【tt-】endl;couta;while(a!=1) couta;coutendl;doswitch(a)case 1:if(InitQueue(Q)=0)cout初始化成功!endl;elsecout初始化失

14、??!endl;break;case 2:if(QueueLength(Q)=0)cout隊列為空無法出隊!endl;break;if(DeQueue(Q,c)=0)cout刪除成功!endl;elsecout刪除失??!endl;break;case 3:cout輸入你要入隊元素c;if(EnQueue(Q,c) =0)cout入隊成功!endl;elsecout入隊失?。ndl;break;case 4:b=QueueLength(Q);cout隊列的長度為:bendl;break;case 5:coutb;if(QueueFind(Q,b)=1)cout恭喜您,隊列中有您要找的元素bend

15、l;elsecout不好意思,隊列中沒有您要找的元素ba;cout0&a=6);說明:通過調(diào)用序列號不同的函數(shù)進行各種操作。函數(shù)根據(jù)每次輸入的數(shù)進行判斷不在16內(nèi)的函數(shù)將結(jié)束,否則將繼續(xù)進行。二_五、程序調(diào)試及運行結(jié)果分析 程序第一步必須執(zhí)行初始化,否則程序不能運行。 在程序第一步必須執(zhí)行初始化后,程序完美運行,在進行任何函數(shù)操作程序都是正常運行,而且本程序?qū)Σ迦牒蛣h除時進行錯誤檢測如有的地方不可以插入,有點地方不能刪除,如果隊列為空時則程序會輸出隊列為空,并繼續(xù)進行其他操作,大大減少了程序的bug。二_六、程序清單#includeusing namespace std;typedef int

16、 QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode, *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,QElemTy

17、pe e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);if(!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.fron

18、t-next=lpp-next;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) coutdatanext;coutnext;while(p)if(p-data=e) return 1;p=p-next;return 0; void zhujiemian()coutendl;cout【tt 數(shù)據(jù)結(jié)構(gòu)實驗二 】endl;cout【tt-】endl;cout【

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論