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

1、（1）理解棧和隊(duì)列的特征以及它們之間的差異，知道在何時(shí)使用那種數(shù)據(jù)結(jié)構(gòu)。重點(diǎn)掌握在順序棧上和鏈棧上實(shí)現(xiàn)棧的基本運(yùn)算算法，注意棧滿和?？盏臈l件。（3）重點(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)方法：（一）綜合運(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 xp Visual C+三、實(shí)驗(yàn)內(nèi)容及過程描述實(shí)驗(yàn)步驟： 進(jìn)入Visual C+集成環(huán)境。

2、輸入自己編好的程序。 檢查一遍已輸入的程序是否有錯(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è)程序，實(shí)現(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完 成如下功能：（1）初始化棧s；（2）判斷棧s是否非空；（3）依次進(jìn)棧元素a,b,c,d,e；（

3、4）判斷棧s是否非空；（5）輸出出棧序列：（6）判斷棧s是否非空；（7）釋放棧。圖Proj3_l工程組成本工程Proj3_l的組成結(jié)構(gòu)如圖所示。本工程的模塊結(jié)構(gòu)如圖所示。圖中方框表示函 數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。圖 其中包含如下函數(shù)：InitStack(SqStack *&s) DestroyStack(SqStack *&s) StackEmpty(SqStack *s)Push(SqStack *&s, ElemType e)Pop (SqStack *&s, ElemType &e)Proj3_l工程的程序結(jié)構(gòu)圖初始化棧S

4、銷毀棧s判斷枝空進(jìn)棧出棧取棧頂元索GetTop(SqStack *s, ElemType &e)對應(yīng)的程序如下:文件名：include <> include <> #define MaxSize 100 typedef char ElemType; typedef structElemType data.MaxSize;int top:/棧頂指針? SqStack;void InitStack(SqStack *&s)初始化棧 S s=(SqStack *)malloc(sizeof(SqStack);s->top=-l;/棧頂指針置為-1)voi

5、d DestroyStack (SqStack *&s) 銷毀棧 sfree(s);)bool StackEmpty (SqStack *s) 判斷?？誶eturn(s-top=_l);)bool Push (SqStack *&s, ElemType e) 進(jìn)棧 if (s->top=MaXSize-l) 棧滿的情況，即棧上溢出 return false;s->top+;棧頂指針增1s->datas->top =e;元素e放在棧頂指針處return true;)bool Pop(SqStack *&s, ElemType &e) 出枝

6、if (s->top=-l)棧為空的情況，即棧下溢出return false;e=s->datas->top; 取棧頂指針元素的元素s->top;棧頂指針減1return true; bool GetTop (SqStack *s, ElemType &e) 取校頂元素 if (s->top=-l)棧為空的情況，即棧下溢出return false;e=s->datas->top; 取棧頂指針元素的元素 return true;)設(shè)計(jì)程序如下文件名:trinclude include #define MaxSize 100typedef char

7、 ElemType;typedef structElemType dataMaxSize;int top; SqStack;棧頂指針externexternexternexternexternexternvoid void bool bool bool boolInitStack(SqStack *&s);DestroyStack(SqStack *&s);StackEmpty(SqStack *s);Push (SqStack *&s,ElemType e);Pop(SqStack *&s, ElemType &e);GetTop(SqStack *s

8、» ElemType &e);void mainOElemType e;SqStack *s;printf ("棧s的基本運(yùn)算如下:n");printf (" (1)初始化棧 sn");InitStack(s);printf(" printf(" Push(s,' a Push(s, * b Push(s, ' c Push(s, * d Push(s,' e printf(" printf("(2)棧為%sn”, (StackEmpty(s)?"空":

9、"非空");(3)依次進(jìn)棧元素a, b,c,d,erT););););););(4)棧為%sn", (StackEmpty(s)?"空":"非空");(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）、

10、編寫一個(gè)程序，實(shí)現(xiàn)鏈枝的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完成如下功能:(1)初始化鏈棧S：(2)判斷鏈棧S是否非空:(3)依次進(jìn)棧a, b, c, d, e（4）判斷鏈棧s是否非空：（5）輸出鏈棧長度；（6）輸出從校底到校頂元索：（7）輸出出隊(duì)序列；（8）判斷鏈棧s是否非空；圖Proj3_2工程組成（9）釋放隊(duì)列。本工程Proj3_2的組成結(jié)構(gòu)如圖所示。本工程的模塊結(jié)構(gòu)如圖所示。圖中方框表示函 數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。圖Proj3_2工程的程序結(jié)構(gòu)圖其中包含如卜函數(shù)：InitStack(LiStack *&s) 初始化棧 sDestroyStack

11、 (LiStack *&s)/銷毀棧StackEmpty(LiStack *s)判斷棧是否為空Push (LiStack *&s, ElemType e) 進(jìn)棧Pop(LiStack *&s, ElemType &e)出棧GetTop (LiStack *5, ElemType &e) 取棧頂元素對應(yīng)的程序如下：/'文件名：-include <>include <>typedef char ElemType;typedef struct linknodeElemType data;/數(shù)據(jù)域struct linknode *

12、next;/指針,域? LiStack;void Ini t St ack (LiSt ack *&s) 初始化棧 s s=(LiStack *)malloc(sizeof(LiStack);s->next=NULL;)void DestroyStack(LiStack *&s) 銷毀棧 LiStack *p=s, *q=s->next;while (q!=NULL) free(p);p=q;q=p->next;)free(p);此時(shí)p指向尾節(jié)點(diǎn),釋放其空間Jbool StackEmpty (LiStack *s) /判斷棧是否為空return (s*>

13、next=NULL);)void Push(LiStack *&s, ElemType e) /進(jìn)棧 LiStack *p;p=(LiStack )malloc(sizeof(LiStack);p->data=e;新建元素e對應(yīng)的節(jié)點(diǎn)*pp->next=s->next;插入*p節(jié)點(diǎn)作為開始節(jié)點(diǎn)s->next=p;)bool Pop (LiStack *&s, ElemType &e) 出棧 LiStack *p;if (s->next=NULL) return false;p=s->next;e=p-z data;s->next

14、=p->next;free(p);return true;?？盏那闆rp指向開始節(jié)點(diǎn)刪除*p節(jié)點(diǎn)釋放*p節(jié)點(diǎn))bool GetTop (LiStack *s, ElemType &e) /取棧頂元素 if (s->next=NULL)棧空的情況return false;e=s； next 一data;return true;)設(shè)計(jì)主程序文件名：#include <>include <>typedef char ElemType;typedef struct linknodeElemType data; struct linknode *next; Li

15、Stack;/數(shù)據(jù)域指針域externexternexternexternexternvoid void bool void boolexternboolInitStack(LiStack *&s);DestroyStack(LiStack *&s);StackEmpty(LiStack *s);Push(LiStack *&s, ElemType e);Pop(LiStack *&s,ElemType &e);GetTop(LiStack *s, ElemType &e);void mainOElemType e;LiStack *s;prin

16、tf ("棧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, c*);Push(s,'d');Push (s, ' c');printf (* (4)棧為sn

17、”, (StackEmpty (s)?"空"："非空")；printf (" (5)出棧序列：”)；while (!StackEmpty(s)Pop(s, e);printf (飛c ”, e)；)printf C*n*);printf (* (6)棧為sn”, (StackEmpty (s)?"空"："非空")；printf (" (7)釋放棧n");DestroyStack (s);程序運(yùn)行結(jié)果如下:3）、編寫一個(gè)程序，實(shí)現(xiàn)順序環(huán)形隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序并完

18、成如 下功能：（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)如圖所示。本工程的模塊結(jié)構(gòu)如圖所示。圖中方框表示函 數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系。圖 Proj3_3工程的程序結(jié)構(gòu)圖其中包含如卜函數(shù)：InitQueue (SqQueue *&q) 初始化隊(duì)列DestroyQueue(SqQueue *&q)銷毀隊(duì)列Qu

19、eueEmpty(SqQueue *q) 判斷隊(duì)列空enQueue (SqQueue *&q, ElemType e) 進(jìn)隊(duì)deQueue(SqQueue *&q, ElemType &e)出隊(duì)對應(yīng)的程序如F：/文件名：#include include <>#define MaxSize 5typedef char ElemType;typedef structElemType dataMaxSize;int front, rear; 隊(duì)首和隊(duì)尾指針) SqQueue;void InitQueue(SqQueue *&q) 初始化隊(duì)列 q=(SqQu

20、eue *)malloc (sizeof(SqQueue);q- front=q- rear=0;)void DestroyQueue (SqQueue *&q) 銷毀隊(duì)列free(q);)bool QueueEmpty (SqQueue *q) 判斷隊(duì)列空return(q->front=q->rear);)bool enQueue (SqQueue *&q, ElemType e) 進(jìn)隊(duì)if (q->rear+l) %MaxSize=q->front) 隊(duì)滿上溢出 return false;q->rear=(q->rear+l)MaxSiz

21、e;q- dataq->rear=e;return true;)bool deQueue (SqQueue *&q, ElemType &e) 出隊(duì)if (q->front=q->rear) /隊(duì)空下溢出return false;q->front= (q->front+l)%NfaxSize;e=q>dataq->front;return true;)設(shè)計(jì)主程序include <>include <>#define MaxSize 5typedef char ElemType; typedef structEle

22、mType elemtMaxSize-;int front, rear;隊(duì)首和隊(duì)尾指針 SqQueue;externexternexternexternexternvoid void bool bool boolInitQueue(SqQueue *&q);DestroyQueue(SqQueue *&q);QueueEmpty(SqQueue *q);enQueue(SqQueue *&q, ElemType e);deQueue(SqQueue *&q, ElemType &e);void mainOElemType 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ì)滿，不能進(jìn)隊(duì)if (