數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列實(shí)驗(yàn)報(bào)告

1、一、實(shí)驗(yàn)?zāi)康暮鸵?1)理解棧和隊(duì)列的特征以及它們之間的差異，知道在何時(shí)使用那種數(shù)據(jù)結(jié)構(gòu)。(2)重點(diǎn)掌握在順序棧上和鏈棧上實(shí)現(xiàn)棧的基本運(yùn)算算法，注意棧滿(mǎn)和?？盏臈l件。(3)重點(diǎn)掌握在順序隊(duì)上和鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法，注意循環(huán)隊(duì)隊(duì)列滿(mǎn)和隊(duì)空的條件。(4)靈活運(yùn)用棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問(wèn)題。二、實(shí)驗(yàn)環(huán)境和方法實(shí)驗(yàn)方法：（一）綜合運(yùn)用課本所學(xué)的知識(shí)，用不同的算法實(shí)現(xiàn)在不同的程序功能。（二）結(jié)合指導(dǎo)老師的指導(dǎo)，解決程序中的問(wèn)題，正確解決實(shí)際中存在的異常情況，逐步改善功能。（三）根據(jù)實(shí)驗(yàn)內(nèi)容，編譯程序。實(shí)驗(yàn)環(huán)境：Windows xp Visual C+6.0三、實(shí)驗(yàn)內(nèi)容及過(guò)程描述實(shí)

2、驗(yàn)步驟： 進(jìn)入Visual C+ 6.0集成環(huán)境。 輸入自己編好的程序。 檢查一遍已輸入的程序是否有錯(cuò)（包括輸入時(shí)輸錯(cuò)的和編程中的錯(cuò)誤），如發(fā)現(xiàn)有錯(cuò)，及時(shí)改正。 進(jìn)行編譯和連接。如果在編譯和連接過(guò)程中發(fā)現(xiàn)錯(cuò)誤，頻幕上會(huì)出現(xiàn)“報(bào)錯(cuò)信息”，根據(jù)提示找到出錯(cuò)位置和原因，加以改正。再進(jìn)行編譯，如此反復(fù)直到不出錯(cuò)為止。 運(yùn)行程序并分析運(yùn)行結(jié)果是否合理。在運(yùn)行是要注意當(dāng)輸入不同的數(shù)據(jù)時(shí)所得結(jié)果是否正確，應(yīng)運(yùn)行多次，分別檢查在不同情況下結(jié)果是否正確。實(shí)驗(yàn)內(nèi)容：編譯以下題目的程序并調(diào)試運(yùn)行。1）、編寫(xiě)一個(gè)程序algo3-1.cpp，實(shí)現(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完成如下功能：（1）初始

3、化棧s；（2）判斷棧s是否非空；（3）依次進(jìn)棧元素a,b,c,d,e；（4）判斷棧s是否非空；（5）輸出出棧序列；（6）判斷棧s是否非空； （7）釋放棧。 圖3.1 Proj3_1 工程組成本工程Proj3_1的組成結(jié)構(gòu)如圖3.1所示。本工程的模塊結(jié)構(gòu)如圖3.2所示。圖中方框表示函數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。mainInitStackDestroyStackStackEmptyPushPopGetTop圖3.2 Proj3_1工程的程序結(jié)構(gòu)圖其中包含如下函數(shù)：InitStack(SqStack *&s)/初始化棧SDestroyStack(SqStack *&a

4、mp;s)/銷(xiāo)毀棧sStackEmpty(SqStack *s)/判斷?？誔ush(SqStack *&s,ElemType e)/進(jìn)棧Pop(SqStack *&s,ElemType &e)/出棧GetTop(SqStack *s,ElemType &e)/取棧頂元素 對(duì)應(yīng)的程序如下： /文件名:algo3-1.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSi

5、ze;int top;/棧頂指針 SqStack;void InitStack(SqStack *&s)/初始化棧Ss=(SqStack *)malloc(sizeof(SqStack);s->top=-1;/棧頂指針置為-1void DestroyStack(SqStack *&s)/銷(xiāo)毀棧sfree(s);bool StackEmpty(SqStack *s)/判斷?？誶eturn(s->top=-1);bool Push(SqStack *&s,ElemType e)/進(jìn)棧if (s->top=MaxSize-1)/棧滿(mǎn)的情況，即棧上溢出retu

6、rn false;s->top+;/棧頂指針增1s->datas->top=e;/元素e放在棧頂指針處return true;bool Pop(SqStack *&s,ElemType &e)/出棧if (s->top=-1)/棧為空的情況，即棧下溢出return false;e=s->datas->top;/取棧頂指針元素的元素s->top-;/棧頂指針減1return true; bool GetTop(SqStack *s,ElemType &e)/取棧頂元素if (s->top=-1)/棧為空的情況，即棧下溢出re

7、turn false;e=s->datas->top;/取棧頂指針元素的元素return true;設(shè)計(jì)exp3-1.cpp程序如下/文件名:exp3-1.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/棧頂指針 SqStack;extern void InitStack(SqStack *&s);extern void DestroyStack(S

8、qStack *&s);extern bool StackEmpty(SqStack *s);extern bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType &e);extern bool GetTop(SqStack *s,ElemType &e);void main()ElemType e;SqStack *s;printf("棧s的基本運(yùn)算如下:n");printf(" (1)初始化棧sn");InitStack(s)

9、;printf(" (2)棧為%sn",(StackEmpty(s)?"空":"非空");printf(" (3)依次進(jìn)棧元素a,b,c,d,en");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf(" (4)棧為%sn",(StackEmpty(s)?"空":"非空");printf(&qu

10、ot; (5)出棧序列:");while (!StackEmpty(s)Pop(s,e);printf("%c ",e);printf("n");printf(" (6)棧為%sn",(StackEmpty(s)?"空":"非空");printf(" (7)釋放棧n");DestroyStack(s);運(yùn)行結(jié)果如下：2）、編寫(xiě)一個(gè)程序algo3-2.cpp，實(shí)現(xiàn)鏈棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完成如下功能：（1）初始化鏈棧s；（2）判斷鏈棧s是否非空

11、；（3）依次進(jìn)棧a，b，c，d，e；（4）判斷鏈棧s是否非空；（5）輸出鏈棧長(zhǎng)度；（6）輸出從棧底到棧頂元素；（7）輸出出隊(duì)序列；（8）判斷鏈棧s是否非空； 圖3.3 Proj3_2工程組成（9）釋放隊(duì)列。本工程Proj3_2的組成結(jié)構(gòu)如圖3.3所示。本工程的模塊結(jié)構(gòu)如圖3.4所示。圖中方框表示函數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。mainInitStackDestroyStackStackEmptyPushPopGetTop 圖3.4 Proj3_2工程的程序結(jié)構(gòu)圖其中包含如下函數(shù)：InitStack(LiStack *&s)/初始化棧s DestroyStack(L

12、iStack *&s)/銷(xiāo)毀棧StackEmpty(LiStack *s)/判斷棧是否為空Push(LiStack *&s,ElemType e)/進(jìn)棧Pop(LiStack *&s,ElemType &e)/出棧GetTop(LiStack *s,ElemType &e)/取棧頂元素對(duì)應(yīng)的程序如下：/文件名:algo3-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknodeElemType data;/數(shù)據(jù)域E

13、lemType data;/數(shù)據(jù)域struct linknode *next;/指針域 LiStack;void InitStack(LiStack *&s)/初始化棧ss=(LiStack *)malloc(sizeof(LiStack);s->next=NULL;void DestroyStack(LiStack *&s)/銷(xiāo)毀棧LiStack *p=s,*q=s->next;while (q!=NULL)free(p);p=q;q=p->next;free(p);/此時(shí)p指向尾節(jié)點(diǎn),釋放其空間bool StackEmpty(LiStack *s)/判斷棧

14、是否為空return(s->next=NULL);void Push(LiStack *&s,ElemType e)/進(jìn)棧LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p->data=e;/新建元素e對(duì)應(yīng)的節(jié)點(diǎn)*pp->next=s->next;/插入*p節(jié)點(diǎn)作為開(kāi)始節(jié)點(diǎn)s->next=p;bool Pop(LiStack *&s,ElemType &e)/出棧LiStack *p;if (s->next=NULL)/?？盏那闆rreturn false;p=s->next;/p指向

15、開(kāi)始節(jié)點(diǎn)e=p->data;s->next=p->next;/刪除*p節(jié)點(diǎn)free(p);/釋放*p節(jié)點(diǎn)return true;bool GetTop(LiStack *s,ElemType &e)/取棧頂元素if (s->next=NULL)/?？盏那闆rreturn false;e=s->next->data;return true;設(shè)計(jì) exp3-2.cpp 主程序/文件名:exp3-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typede

16、f struct linknodeElemType data;/數(shù)據(jù)域struct linknode *next;/指針域 LiStack;extern void InitStack(LiStack *&s);extern void DestroyStack(LiStack *&s);extern bool StackEmpty(LiStack *s);extern void Push(LiStack *&s,ElemType e);extern bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(L

17、iStack *s,ElemType &e);void main()ElemType e;LiStack *s;printf("棧s的基本運(yùn)算如下:n");printf(" (1)初始化棧sn");InitStack(s);printf(" (2)棧為%sn",(StackEmpty(s)?"空":"非空");printf(" (3)依次進(jìn)棧元素a,b,c,d,en");Push(s,'a');Push(s,'b');Push(s,&#

18、39;c');Push(s,'d');Push(s,'e');printf(" (4)棧為%sn",(StackEmpty(s)?"空":"非空");printf(" (5)出棧序列:");while (!StackEmpty(s)Pop(s,e);printf("%c ",e);printf("n");printf(" (6)棧為%sn",(StackEmpty(s)?"空":"非空&

19、quot;);printf(" (7)釋放棧n");DestroyStack(s);程序運(yùn)行結(jié)果如下：3）、編寫(xiě)一個(gè)程序algo3-3.cpp，實(shí)現(xiàn)順序環(huán)形隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完成如下功能：（1）初始化隊(duì)列q；（2）判斷隊(duì)列q是否非空；（3）依次進(jìn)隊(duì)列a,b,c；（4）出隊(duì)一個(gè)元素，輸出該元素；（5）輸出隊(duì)列q的元素個(gè)數(shù)；（6）依次進(jìn)隊(duì)列元素d,e,f； 圖3-5 Proj3_3的工程組成（7）輸出隊(duì)列q的元素個(gè)數(shù)；（8）輸出出隊(duì)序列；（9）釋放隊(duì)列。本工程Proj3_3的組成結(jié)構(gòu)如圖3.5所示。本工程的模塊結(jié)構(gòu)如圖3.6所示。圖中方框表示函數(shù)，

20、方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。mainInitStackDestroyStackStackEmptyPushPopGetTop圖3.6 Proj3_3工程的程序結(jié)構(gòu)圖其中包含如下函數(shù)：InitQueue(SqQueue *&q)/初始化隊(duì)列DestroyQueue(SqQueue *&q)/銷(xiāo)毀隊(duì)列QueueEmpty(SqQueue *q)/判斷隊(duì)列空enQueue(SqQueue *&q,ElemType e)/進(jìn)隊(duì)deQueue(SqQueue *&q,ElemType &e)/出隊(duì)對(duì)應(yīng)的程序如下：/文件名:algo3-3.cpp

21、#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct ElemType dataMaxSize;int front,rear;/隊(duì)首和隊(duì)尾指針 SqQueue;void InitQueue(SqQueue *&q)/初始化隊(duì)列q=(SqQueue *)malloc (sizeof(SqQueue);q->front=q->rear=0;void DestroyQueue(SqQueue *&q)/銷(xiāo)毀隊(duì)列free(q

22、);bool QueueEmpty(SqQueue *q)/判斷隊(duì)列空return(q->front=q->rear);bool enQueue(SqQueue *&q,ElemType e)/進(jìn)隊(duì)if (q->rear+1)%MaxSize=q->front)/隊(duì)滿(mǎn)上溢出return false;q->rear=(q->rear+1)%MaxSize;q->dataq->rear=e;return true;bool deQueue(SqQueue *&q,ElemType &e)/出隊(duì)if (q->front=q

23、->rear)/隊(duì)空下溢出return false;q->front=(q->front+1)%MaxSize;e=q->dataq->front;return true;設(shè)計(jì) exp3-3.cpp 主程序#include <stdio.h>#include <malloc.h>#define MaxSize 5 typedef char ElemType;typedef struct ElemType elemMaxSize;int front,rear;/隊(duì)首和隊(duì)尾指針 SqQueue;extern void InitQueue(SqQ

24、ueue *&q);extern void DestroyQueue(SqQueue *&q);extern bool QueueEmpty(SqQueue *q);extern bool enQueue(SqQueue *&q,ElemType e);extern bool deQueue(SqQueue *&q,ElemType &e);void main()ElemType e;SqQueue *q;printf("環(huán)形隊(duì)列基本運(yùn)算如下:n");printf(" (1)初始化隊(duì)列qn");InitQueue(q);printf(" (2)依次進(jìn)隊(duì)列元素a,b,cn");if (!enQueue(q,'a') printf("t提示:隊(duì)滿(mǎn),不能進(jìn)隊(duì)n&qu