棧和隊(duì)列的基本操作實(shí)驗(yàn)報(bào)告

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

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

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

4、turn ERROR; /沒(méi)有申請(qǐng)到存，返回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); /棧滿了，重新申請(qǐng)存 if(!S.base) /判斷是否申請(qǐng)成功 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、初始化隊(duì)列 /* 函數(shù)功能：初始化隊(duì)列參數(shù)：隊(duì)列（LinkQueue &Q）成功返回1， 否則返回0 */int InitQueue(LinkQueue &Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);/申請(qǐng)結(jié)點(diǎn)的存 if(!Q.front) /判斷有無(wú)申請(qǐng)到空間 return ERROR; /沒(méi)有返回0 Q.front ->next = NULL; return OK;8.在隊(duì)列隊(duì)尾插入元素/* 函數(shù)功能：在隊(duì)列隊(duì)尾插入元素參數(shù)：隊(duì)列（LinkQueu

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

8、nkQueue &Q, QElemType &e) if(Q.front = Q.rear) /判斷隊(duì)列是否為空 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; /聲明一個(gè)棧LinkQueue Q; /聲明一個(gè)隊(duì)列char m,k,c; int n=0,i,j,t=0,z=0;while(

9、!t)cout << "請(qǐng)輸入你要判斷回文的字符串，輸入結(jié)束："InitQueue (Q);InitStack (S);while(c=getchar()!='')/對(duì)字符的判斷 不斷輸入字符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則說(shuō)明全部相等cout << "這個(gè)字符串不是回文字符串" << endl;elsecout &

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

11、否是回文數(shù)，并輸出判斷語(yǔ)句結(jié)束 2、程序清單#include<iostream>#include<malloc.h>using namespace std;/棧的表示和實(shí)現(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;/隊(duì)列的表示和實(shí)現(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)于隊(duì)列的函數(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 << "請(qǐng)輸入你要判斷回文的字符串：" << endl;InitQueue (Q);InitStack (S);while(c=getchar()!='')/對(duì)字符的判斷 不斷輸入字符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 << "這個(gè)字符串是回