山大《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)03棧與隊(duì)列

1、實(shí)驗(yàn)三 棧與隊(duì)列一 實(shí)驗(yàn)任務(wù)1）棧的應(yīng)用2）隊(duì)列的表示與實(shí)現(xiàn)二 實(shí)驗(yàn)?zāi)康?）了解棧與隊(duì)列的特性2）掌握棧的順序、鏈?zhǔn)酱鎯Ρ硎炯皩?shí)現(xiàn)3）掌握隊(duì)列的順序、鏈?zhǔn)酱鎯Ρ硎炯皩?shí)現(xiàn)4）掌握棧與隊(duì)列在實(shí)際問題中的應(yīng)用三 實(shí)驗(yàn)原理1棧的特性棧（Stack）又稱堆棧，是一種特殊的線性表，可定義為插入、刪除和訪問只能在某一端進(jìn)行的線性數(shù)據(jù)結(jié)構(gòu)。堆棧允許插入、刪除和訪問的一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧頂?shù)牡谝粋€(gè)元素被稱為棧頂元素。堆棧的性質(zhì)決定它的數(shù)據(jù)是按“先進(jìn)后出”的順序被訪問，即最先存儲的元素最后被訪問、刪除，最后存儲的元素最先被訪問、刪除，所以棧也稱為“LIFO”（Last_In,

2、 First_Out）。棧的抽象數(shù)據(jù)類型定義如下：ADT Stack數(shù)據(jù)對象：D=ai | ai ElemSet, i = 1,2,n, n0數(shù)據(jù)關(guān)系：R = | ai-1, ai D, i = 2, n 約定an端為棧頂，a1端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。Push(&S, e )初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S, &e) 初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。GetTop(S, &e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。StackEmpty(S)初始條件：

3、棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長度。StackTraverse(S，visit( )初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit ( ) 。一旦visit ( ) 失敗，則操作失敗。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀 。 ADT Stack2棧的順序表示棧的順序存儲結(jié)構(gòu)，即順序棧，是利用一組連續(xù)的存儲單元依次存放自

4、棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)通過指針top指示棧頂元素在順序棧中的位置。由于很難估計(jì)棧在使用過程中所需要的最大空間的大小，所以通常利用C語言中動態(tài)分配的一組連續(xù)的存儲單元作為順序棧所需要的存儲空間。順序棧所需要的具體數(shù)據(jù)類型描述如下：#define MAXLEN 100#define STACK_INCREASE 10 /順序棧存儲空間的動態(tài)分配增量typedef structElemType *base; /棧的存儲空間的基地址，即棧底指針ElemType *top; /棧頂指針int maxsize; /棧當(dāng)前分配的存儲容量SqStack;其中，maxsize指示棧當(dāng)前可使用的最大容量；ba

5、se為棧底指針，在順序棧中，它始終指向棧底的位置，若base=NULL，則表明棧結(jié)構(gòu)不存在；top為棧頂指針，起初值為棧底指針值，即top=base，這也可作為?？盏臉?biāo)記。棧插入新元素時(shí)，將新元素插入到棧頂指針?biāo)赶虻奈恢?，同時(shí)指針top增1，刪除棧頂元素時(shí)，指針top減1。3棧的鏈?zhǔn)酱鎯Ρ硎緱５逆準(zhǔn)酱鎯Y(jié)構(gòu)，即鏈棧，與線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，是通過由結(jié)點(diǎn)構(gòu)成的單鏈表實(shí)現(xiàn)的，但每個(gè)結(jié)點(diǎn)的指針指向其前驅(qū)結(jié)點(diǎn)（在其之前進(jìn)棧的結(jié)點(diǎn)）。此時(shí)，表頭指針稱為棧頂指針，其指向的結(jié)點(diǎn)即為棧頂結(jié)點(diǎn)。所需要的具體數(shù)據(jù)類型描述如下：typedef struct SNodeElemType data;struct

6、SNode *prior; /prior將指向其前一次入棧的元素SNode, *SLink;4隊(duì)列的特性隊(duì)列（Queue）簡稱隊(duì)，也是一種特殊的線性表，可定義為只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性結(jié)構(gòu)。隊(duì)列允許插入的一端稱為隊(duì)尾（Rear），允許刪除的一端稱為隊(duì)首（Front）。由于隊(duì)列的插入和刪除分別在不同的兩端進(jìn)行，因而先插入者自然先從另一端刪除，所以隊(duì)列具有“先進(jìn)先出”的特點(diǎn)，簡稱為FIFO（First-In, First-Out）。隊(duì)列的抽象數(shù)據(jù)類型定義如下：ADT Queue 數(shù)據(jù)對象：D=ai | ai ElemSet, i = 1,2,n, n0數(shù)據(jù)關(guān)系：R1=

7、 | ai-1, ai D, i = 2, n 約定其中a1端為隊(duì)首，an端為隊(duì)尾。基本操作：InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。QueueEmpty(Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則FALSE。QueueLength(Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。EnQueue(&Q, e) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q, &e) 初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)首元素，并用e返回其值。GetHead(Q, &e) 初始條件：Q為非

8、空隊(duì)列。 操作結(jié)果：用e返回Q的隊(duì)首元素。QueueTraverse(Q, visit( ) ) 初始條件：Q已存在且非空。 操作結(jié)果：從隊(duì)首到隊(duì)尾，依次對Q 的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗。ClearQueue(&Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：將Q清為空隊(duì)列。DestroyQueue(&Q) 初始條件：隊(duì)列Q已存在。 操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ADT Queue5隊(duì)列的順序表示隊(duì)列的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元依次存放從隊(duì)首到隊(duì)尾的元素，同時(shí)附設(shè)兩個(gè)指針front和rear分別指示隊(duì)首元素及隊(duì)尾元素的位置。循環(huán)隊(duì)列所

9、需要的具體數(shù)據(jù)類型描述如下：#define MAXQSIZE 100 /最大隊(duì)列長度typedef struct ElemType * base; /初始化的動態(tài)分配存儲空間 int front; /頭指針，若隊(duì)列不空，指向隊(duì)首元素 int rear; /尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一個(gè)位置SqQueue;6隊(duì)列的鏈?zhǔn)酱鎯Ρ硎娟?duì)列的鏈接存儲結(jié)構(gòu)，簡稱鏈隊(duì)列。鏈隊(duì)列所需要的具體數(shù)據(jù)類型描述如下：typedef struct QNode ElemType data; /值域 struct QNode * next; /鏈接指針域QNode, * QueuePtr;typedef struc

10、t QueuePtr front; /頭指針 QueuePtr rear; /尾指針LinkQueue;四 實(shí)驗(yàn)設(shè)備、儀器、工具與材料 微機(jī)、VC五 實(shí)驗(yàn)內(nèi)容（1）實(shí)驗(yàn)任務(wù)1：棧的應(yīng)用迷宮求解編制C程序完成迷宮問題。程序基本要求：用戶輸入迷宮數(shù)據(jù)初始化迷宮；利用棧的順序表示以及入棧、出棧等基本操作，實(shí)現(xiàn)迷宮路徑的求解；輸出求解得到的完整路徑（或提示迷宮無通路）。（2）實(shí)驗(yàn)任務(wù)2：隊(duì)列的表示與實(shí)現(xiàn)編寫一個(gè)C程序?qū)崿F(xiàn)順序隊(duì)列的各種基本操作，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：1）建立循環(huán)隊(duì)列2）入隊(duì)列3）出隊(duì)列4）判斷隊(duì)列是否為空5）遍歷隊(duì)列6）取隊(duì)首元素六 實(shí)驗(yàn)步驟（1）實(shí)驗(yàn)預(yù)習(xí)1）預(yù)習(xí)本

11、實(shí)驗(yàn)原理中關(guān)于棧與隊(duì)列的定義、順序存儲表示。2）分析掌握教材4850頁中的算法3-13-4，為完成實(shí)驗(yàn)任務(wù)1做好準(zhǔn)備。3）分析掌握教材5760頁中迷宮問題及求解算法3-13，為完成實(shí)驗(yàn)任務(wù)1做好準(zhǔn)備。4）分析掌握教材7073頁中的算法3-153-20，為完成實(shí)驗(yàn)任務(wù)2做好準(zhǔn)備。（2）實(shí)驗(yàn)步驟1）問題分析。充分地分析和理解此實(shí)驗(yàn)任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個(gè)子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計(jì)。3）詳細(xì)設(shè)計(jì)。詳細(xì)設(shè)計(jì)的目的是對子程序（過程或函數(shù)）的進(jìn)一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細(xì)節(jié)。4）編碼。在詳細(xì)設(shè)計(jì)的基礎(chǔ)上，對詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實(shí)驗(yàn)報(bào)告要求實(shí)驗(yàn)報(bào)告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概