棧和隊列的基本操作實驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告一軟件1321徐蜀實驗二 棧和隊列的基本操作及其應(yīng)用一、實驗?zāi)康?、掌握棧和隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實際中靈活應(yīng)用。2、掌握棧和隊列的特點，即后進先出和先進先出的原則。3、掌握棧和隊列的基本運算，如：入棧與出棧，入隊與出隊等運算在順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。二、實驗容 1回文判斷三、實驗要求1、按照數(shù)據(jù)結(jié)構(gòu)實驗任務(wù)書，提前做好實驗預(yù)習與準備工作。2、加“*”題目必做，其他題目任選；多選者并且保質(zhì)保量完成適當加分。3、嚴格按照數(shù)據(jù)結(jié)構(gòu)實驗報告模板和規(guī)，及時完成實驗報告。 四、實驗步驟（說明：依據(jù)實驗容分別說明實驗程序中用到的數(shù)據(jù)類型的定義、主程序的流程以及

2、每個操作（函數(shù)）的偽碼算法、函數(shù)實現(xiàn)、程序編碼、調(diào)試與分析。 附流程圖與主要代碼）、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述（程序中每個模塊或函數(shù)應(yīng)加注釋，說明函數(shù)功能、入口及出口參數(shù)）1、棧的初始長度與需要再增加的長度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;/定義SElemType為char型 2、棧的順序存儲表示typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;3、隊列的鏈式表示方法typedef s

3、truct QNode SElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;4、初始化棧/* 函數(shù)功能：對棧進行初始化 參數(shù)：棧（SqStack &S）成功返回1，否則返回0 */int InitStack(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);/申請存 if(!S.base) /判斷有無申請到空間 re

4、turn ERROR; /沒有申請到存，返回0 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;5、入棧操作/* 函數(shù)功能：將元素入棧 參數(shù)：棧（SqStack &S）,插入元素e 插入成功返回1，否則返回0 */int Push(SqStack &S, SElemType e) if(S.top - S.base >= S.stacksize) /判斷棧頂與棧底的差是否大于棧的/容量 S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINC

5、REMENT) * sizeof(SElemType); /棧滿了，重新申請存 if(!S.base) /判斷是否申請成功 return ERROR; /不成功返回0 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;6、出棧操作/* 函數(shù)功能：將棧中的元素彈出參數(shù)：棧(SqStack &S),記錄元素e */int Pop(SqStack &S, SElemType &e) if(S.top = S.base) /判斷棧是否為空 return ERRO

6、R; e = *(-S.top) ; return OK;7、初始化隊列 /* 函數(shù)功能：初始化隊列參數(shù)：隊列（LinkQueue &Q）成功返回1， 否則返回0 */int InitQueue(LinkQueue &Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);/申請結(jié)點的存 if(!Q.front) /判斷有無申請到空間 return ERROR; /沒有返回0 Q.front ->next = NULL; return OK;8.在隊列隊尾插入元素/* 函數(shù)功能：在隊列隊尾插入元素參數(shù)：隊列（LinkQueu

7、e &Q），插入元素e成功返回1， 否則返回0 */int EnQueue(LinkQueue &Q, QElemType e) p = (QueuePtr)malloc(sizeof(QNode); /申請新的結(jié)點 if(!p) return ERROR; p -> data = e; p -> next = NULL; Q.rear -> next = P; Q.rear = p; return OK;9.刪除隊頭元素/* 函數(shù)功能：刪除對頭元素參數(shù)：隊列（LinkQueue &Q），記錄值e成功返回1，否則返回0 */int DeQueue(Li

8、nkQueue &Q, QElemType &e) if(Q.front = Q.rear) /判斷隊列是否為空 return ERROR; p = Q.front -> next; e = p -> data; Q.front -> next = p -> next; if(Q.rear = p) Q.rear = Q.front; free(p); return OK;10、主函數(shù)int main() SqStack S; /聲明一個棧LinkQueue Q; /聲明一個隊列char m,k,c; int n=0,i,j,t=0,z=0;while(

9、!t)cout << "請輸入你要判斷回文的字符串，輸入結(jié)束："InitQueue (Q);InitStack (S);while(c=getchar()!='')/對字符的判斷 不斷輸入字符EnQueue (Q,c);Push (S,c);n+;for( j=1;j<=n;j+)OutQueue (Q,m);Pop (S,k);if(m!=k) break;if(j>n) /如果j > n則說明全部相等cout << "這個字符串不是回文字符串" << endl;elsecout &

10、lt;< "這個字符串是回文字符串" << endl; return 0;說明：通過調(diào)用序列號不同的函數(shù)進行各種操作。函數(shù)根據(jù)每次輸入的數(shù)進行判斷不在110的函數(shù)將結(jié)束，否則將繼續(xù)進行。 程序調(diào)試及運行結(jié)果分析(應(yīng)包含多組測試數(shù)據(jù)) 五、實驗總結(jié)通過這次試驗，我知道自己還有很多不足，還會犯一些細節(jié)上的錯誤，但是也因此對棧和隊列的操作有了很好的認識附錄 1開始、程序流程圖執(zhí)行主函數(shù)main 聲明一個棧S和隊列Q！t N (c=getchar()!='' Y N Y入棧入隊列j=1;j<=n;j+ N出棧出隊列，并判斷值是否想等 Y判斷是

11、否是回文數(shù)，并輸出判斷語句結(jié)束 2、程序清單#include<iostream>#include<malloc.h>using namespace std;/棧的表示和實現(xiàn)#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef char SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;/隊列的表示和實現(xiàn)typedef struct QNode

12、SElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;/關(guān)于棧的函數(shù)int InitStack(SqStack &S) S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S.base) return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;int Pu

13、sh(SqStack &S, SElemType e) if(S.top - S.base >= S.stacksize) S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType); if(!S.base) return ERROR; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;int Pop(SqStack &S, SElemTy

14、pe &e) if(S.top = S.base) return ERROR; e = *(-S.top) ; return OK;/關(guān)于隊列的函數(shù)int InitQueue(LinkQueue &Q) Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front ->next = NULL; return OK;int EnQueue(LinkQueue &Q, SElemType e) QueuePtr p = (QueuePtr)malloc(siz

15、eof(QNode); if(!p) return ERROR; p -> data = e; p -> next = NULL; Q.rear -> next = p; Q.rear = p; return OK;int DeQueue(LinkQueue &Q, SElemType &e) if(Q.front = Q.rear) return ERROR; QueuePtr p = Q.front -> next; e = p -> data; Q.front -> next = p -> next; if(Q.rear = p)

16、 Q.rear = Q.front; free(p); return OK;/主函數(shù)int main() SqStack S;LinkQueue Q;char m,k,c;int n=0,i,j,t=0,z=0;while(!t)cout << "請輸入你要判斷回文的字符串：" << endl;InitQueue (Q);InitStack (S);while(c=getchar()!='')/對字符的判斷 不斷輸入字符EnQueue (Q,c);Push (S,c);n+;for( j=1;j<=n;j+)DeQueue (Q,m);Pop (S,k);if(m!=k) break;if(j>n)cout << "這個字符串是回