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

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

2、： 進(jìn)入Visual C+ 6.0 集成環(huán)境。 輸入自己編好的程序。 檢查一遍已輸入的程序是否有錯(cuò)（包括輸入時(shí)輸錯(cuò)的和編程中的錯(cuò)誤），如發(fā)現(xiàn)有錯(cuò)，及時(shí)改正。 進(jìn)行編譯和連接。如果在編譯和連接過程中發(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)、編寫一個(gè)程序algo3-1.cpp，實(shí)現(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)個(gè)主程序并完成如下功能：(1) 初始化棧s

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

4、;s,ElemType e) / 進(jìn)棧Pop(SqStack *& s,ElemType &e) /出棧/取棧頂元素GetTop(SqStack *s,ElemType &e)對(duì)應(yīng)的程序如下文件名：algo3-1.cpp #in clude <stdio.h> #include <malloc.h> #defi ne MaxSize 100 typedef char ElemType; typedef struct ElemType dataMaxSize;int top;棧頂指針 SqStack;void InitStack(SqStack *

5、&s)/初始化棧 S s=(SqStack *)malloc(sizeof(SqStack);s->top=-1;/棧頂指針置為-1void DestroyStack(SqStack *&s)/銷毀棧 sfree(s);bool StackEmpty(SqStack *s)/ 判斷?？誶eturn(s->top=-1);bool Push(SqStack *&s,ElemType e)進(jìn)棧 if (s->top=MaxSize-1) II棧滿的情況，即棧上溢出 return false;s->top+;II棧頂指針增1s->datas-&g

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

7、t;top; II取棧頂指針元素的元素 return true;設(shè)計(jì)exp3-1.cpp程序如下/文件名:exp3-1.cpp#in elude <stdio.h>#include <malloc.h>#defi ne MaxSize 100typedef char ElemType;typedef structElemType dataMaxSize;int top;棧頂指針 SqStack;extern void In itStack(SqStack *&；s);extern void DestroyStack(SqStack *& s);exter

8、n bool StackEmpty(SqStack *s);exter n bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType & e);extern bool GetTop(SqStack *s,ElemType & e);void mai n()ElemType e;SqStack *s;printf("棧s的基本運(yùn)算如下:n”);printf("(1)初始化棧 sn");In itStack(s);printf("(2)棧為 %

9、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("棧為 %sn",(StackEmpty(s)?"空":"非空");printf(" (5)出棧序列:");whil

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

11、e；(4) 判斷鏈棧s是否非空；(5) 輸出鏈棧長度；(6) 輸出從棧底到棧頂元素；(7) 輸出出隊(duì)序列；(8) 判斷鏈棧s是否非空；® Workspace ,Proj3_2,: 1 projectfs H 1 Proj32Jiles -3"圍 algo3-2.cpp' Source Files園 exp3-2.cppI Header Files1 Resource Files 鯊Wew 冒 FileViEw圖3.3Proj3_2工程組成(9)釋放隊(duì)列。本工程Proj3_2的組成結(jié)構(gòu)如圖3.3所示。本工程的模塊結(jié)構(gòu)如圖3.4所示。圖中方框表示函數(shù)，方框中指出函數(shù)名，

12、箭頭方向表示函數(shù)間的調(diào)用關(guān)系。圖3.4 Proj3_2工程的程序結(jié)構(gòu)圖其中包含如下函數(shù)：InitStack(LiStack *&s)/ 初始化棧 sDestroyStack(LiStack *&s)/ 銷毀棧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#in clude &l

13、t;stdio.h>#include <malloc.h>typedef char ElemType;typedef struct li nknodeElemType data;數(shù)據(jù)域ElemType data;數(shù)據(jù)域struct linknode *n ext;指針域 LiStack;void InitStack(LiStack *&s)/初始化棧 s s=(LiStack *)malloc(sizeof(LiStack);s-> next=NULL;void DestroyStack(LiStack *&s)/ 銷毀棧LiStack *p=s,*q=

14、s->n ext;while (q!=NULL) free(p);p=q;q=p->n ext;free(p); II此時(shí)p指向尾節(jié)點(diǎn)，釋放其空間bool StackEmpty(LiStack *s) II 判斷棧是否為空retur n(s->n ext=NULL);void Push(LiStack *& s,ElemType e)進(jìn)棧 LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p->data=e;II新建元素e對(duì)應(yīng)的節(jié)點(diǎn)*pp->next=s->next;II插入*p節(jié)點(diǎn)作為開始節(jié)點(diǎn)s_>

15、n ext=p;bool Pop(LiStack *&s,ElemType &e)II 出棧LiStack *p;if (s-> next=NULL)II?？盏那闆rreturn false;p=s->n ext;IIp指向開始節(jié)點(diǎn)e=p->data;s->n ext=p->n ext;II刪除*p節(jié)點(diǎn)free(p);II釋放*p節(jié)點(diǎn)return true;bool GetTop(LiStack *s,ElemType &e) II 取棧頂元素 if (s-> next=NULL)?？盏那闆rreturn false;e=s->n

16、ext->data; return true;設(shè)計(jì)exp3-2.cpp主程序/ 文件名:exp3-2.cpp#in elude <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct li nknodeElemType data;數(shù)據(jù)域struct linknode *n ext;指針域 LiStack;extern void In itStack(LiStack *&；s);extern void DestroyStack(LiStack *&s);exter n bool

17、 StackEmpty(LiStack *s);extern void Push(LiStack *& s,ElemType e);exter n bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType & e);void mai n()ElemType e;LiStack *s;printf("棧s的基本運(yùn)算如下:n”);printf("(1)初始化棧 sn");In itStack(s);printf(" (2)棧為 %sn&qu

18、ot;,(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("棧為 %sn",(StackEmpty(s)?"空":"非空");printf(" (5)出棧序列:");while (!

19、StackEmpty(s)Pop(s,e);prin tf("%c ",e);prin tf("n");printf(" (6)棧為 %sn",(StackEmpty(s)?"空":"非空");printf(" (7)釋放棧 n");DestroyStack(s);程序運(yùn)行結(jié)果如下：下nS運(yùn)化空進(jìn)非序宀工桟k 本勢(shì)次翼轂ny S> > > > > > > 吾 1234567 s5 <<<<<<<

20、; ea. j. h j.c j. d,c b acontinue3)、編寫一個(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 ；(7) 輸出隊(duì)列q的元素個(gè)數(shù)；(8) 輸出出隊(duì)序列；(9) 釋放隊(duì)列。11 Workspace31： 1 proiectfs-®IProj3_3 filesSource Files_l Header Files f Resou

21、rce Files j ClassView £ FileView圖3-5 Proj3_3的工程組成本工程Proj3_3的組成結(jié)構(gòu)如圖3.5所示。本工程的模塊結(jié)構(gòu)如圖3.6所示。圖中方框表示函數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系圖3.6 Proj3_3工程的程序結(jié)構(gòu)圖其中包含如下函數(shù)InitQueue(SqQueue *&q)/ 初始化隊(duì)列DestroyQueue(SqQueue *&q)/ 銷毀隊(duì)列QueueEmpty(SqQueue *q)/判斷隊(duì)列空enQueue(SqQueue *&q,ElemType e)/ 進(jìn)隊(duì)deQueue(SqQu

22、eue *&q,ElemType &e)/ 出隊(duì)對(duì)應(yīng)的程序如下：/文件名：algo3-3.cpp#in elude <stdio.h>#include <malloc.h>#defi ne MaxSize 5typedef char ElemType;typedef structElemType dataMaxSize;int fron t,rear;/隊(duì)首和隊(duì)尾指針 SqQueue;void Ini tQueue(SqQueue *&q)/ 初始化隊(duì)列 q=(SqQueue *)malloc (sizeof(SqQueue);q_>fro

23、n t=q->rear=0;void DestroyQueue(SqQueue *&q)/ 銷毀隊(duì)列free(q);bool QueueEmpty(SqQueue *q)/ 判斷隊(duì)列空return(q->fr on t=q->rear);bool en Queue(SqQueue *&q,ElemType e) / 進(jìn)隊(duì)if (q->rear+1)%MaxSize=q->fro nt)/ 隊(duì)滿上溢出return false;q->rear=(q->rear+1)%MaxSize;q_>dataq_>rear=e;return

24、 true;bool deQueue(SqQueue *&q,ElemType &e) / 出隊(duì)if (q->fro nt=q->rear)/ 隊(duì)空下溢出return false;q->fro nt=(q->fro nt+1)%MaxSize;e=q->dataq->fr on t;return true;設(shè)計(jì)exp3-3.cpp主程序#in clude <stdio.h>#include <malloc.h>#defi ne MaxSize 5typedef char ElemType;typedef structE

25、lemType elemMaxSize;int fron t,rear;/隊(duì)首和隊(duì)尾指針 SqQueue;exter n void In itQueue(SqQueue *&q);exter n void DestroyQueue(SqQueue *&q);exter n bool QueueEmpty(SqQueue *q);extern bool en Queue(SqQueue *& q,ElemType e); extern bool deQueue(SqQueue *& q,ElemType & e); void mai n()ElemType e;SqQueue *q;printf("環(huán)形隊(duì)列基本運(yùn)算如下:n");printf("(1)初始化隊(duì)列 qn");In itQueue(q);prin tf("(2)依次進(jìn)隊(duì)列元素 a,b,c n");if (!enQueue(q,'a') printf("t 提示:隊(duì)滿，不能進(jìn)隊(duì) n"); if (!en