《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第3章

第3章棧和隊(duì)列3.1棧3.2隊(duì)列

3.1棧

棧(Stack)是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表。我們把表尾稱為棧頂(Top)；表頭稱為棧底(Bottom)。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)稱為空棧。圖3-1棧的示意圖3.1.1棧的順序存儲(chǔ)表示——順序棧

1.棧的順序存儲(chǔ)結(jié)構(gòu)

棧是一種特殊的線性表，因此可以用線性表的方法來(lái)存儲(chǔ)棧。最簡(jiǎn)單的方法是用一維數(shù)組來(lái)存儲(chǔ)。由于棧底是固定不變的，而棧頂是隨進(jìn)棧出棧操作動(dòng)態(tài)變化的，因此為了實(shí)現(xiàn)對(duì)棧的操作，必須記住棧頂?shù)漠?dāng)前位置。另外，對(duì)于棧來(lái)說(shuō)，是有容量限制的。鑒于以上考慮，把棧的順序存儲(chǔ)結(jié)構(gòu)定義為圖3-2棧的狀態(tài)變化

(1)置空棧。對(duì)棧進(jìn)行初始化，即將棧頂指針Top初始化為-1。

(2)判斷棧是否為空。在進(jìn)行出棧操作時(shí)，必須先判斷棧不為空；否則會(huì)出錯(cuò)。

(3)進(jìn)棧。將數(shù)據(jù)元素e插入棧頂。

(4)出棧。首先判斷棧是否為空，若為空則表示下溢；否則刪除棧頂數(shù)據(jù)元素。

(5)取棧頂元素。只把棧頂元素的值取出，而不調(diào)整棧頂指針Top的值。

2.多個(gè)棧共享存儲(chǔ)空間

上面討論了單個(gè)棧在順序存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)和運(yùn)算，它能有效地控制先進(jìn)后出順序的數(shù)據(jù)處理。但是，當(dāng)一個(gè)程序中同時(shí)使用多個(gè)順序棧時(shí)，應(yīng)如何處理呢？

為了防止上溢錯(cuò)誤，需要為每個(gè)棧分配一個(gè)較大的空間，但在某一個(gè)棧發(fā)生上溢的同時(shí)，可能其余棧未用的空間還很多，如果將這多個(gè)棧安排在同一個(gè)向量中，即讓多個(gè)棧共享存儲(chǔ)空間，既節(jié)約了存儲(chǔ)空間，又降低了上溢發(fā)生的概率。圖3-3兩個(gè)棧共享存儲(chǔ)空間圖3-4多個(gè)棧共享存儲(chǔ)空間3.1.2棧的鏈?zhǔn)酱鎯?chǔ)表示——鏈棧

對(duì)于順序棧來(lái)說(shuō)，其最大缺點(diǎn)是：當(dāng)棧的容量不固定時(shí)，必須設(shè)置棧，使其可容納最多的數(shù)據(jù)元素，這樣就會(huì)浪費(fèi)很多存儲(chǔ)容間，也可能產(chǎn)生上溢現(xiàn)象。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就不會(huì)產(chǎn)生類似的問(wèn)題。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。它是運(yùn)算受限的單鏈表，其插入和刪除操作僅在表頭進(jìn)行。圖3-5是鏈棧的示意圖。圖3-5鏈棧的示意圖棧頂是top指針，它唯一地確定一個(gè)鏈棧。當(dāng)top等于NULL時(shí)，該鏈棧為空棧。鏈棧的定義如下：3.1.3棧的應(yīng)用

棧的應(yīng)用非常廣泛，只要問(wèn)題滿足LIFO原則，均可使用棧做數(shù)據(jù)結(jié)構(gòu)。棧的典型應(yīng)用有：

(1)過(guò)程遞歸調(diào)用。

(2)“回溯”問(wèn)題的求解。

(3)表達(dá)式求值。

下面通過(guò)舉例來(lái)說(shuō)明。

1．遞歸調(diào)用

遞歸調(diào)用是指一個(gè)過(guò)程(函數(shù))通過(guò)調(diào)用語(yǔ)句直接或間接調(diào)用自身的過(guò)程。遞歸是程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具，有很多數(shù)學(xué)函數(shù)就是遞歸定義的，如大家熟悉的階乘函數(shù)；在有的數(shù)據(jù)結(jié)構(gòu)中，如二叉樹、廣義表等。由于結(jié)構(gòu)本身固有的遞歸特性，使其操作也可用遞歸函數(shù)來(lái)描述。下面以計(jì)算Fibonacci序列為例來(lái)說(shuō)明棧在遞歸調(diào)用中的作用。

Fibonacci序列定義為圖3-6遞歸執(zhí)行過(guò)程圖3-7遞歸調(diào)用過(guò)程中棧的變化

2．地圖染色問(wèn)題

1)問(wèn)題描述及分析

地圖染色問(wèn)題，可以根據(jù)四色定理來(lái)解決。四色定理是指可以用不多于四種顏色對(duì)地圖著色，使相鄰的行政區(qū)域不重色。下面應(yīng)用這個(gè)定理的結(jié)論，用回溯算法對(duì)一幅給定的地圖染色。

2)數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)上實(shí)現(xiàn)上述算法時(shí)，用一個(gè)關(guān)系矩陣R[n][n]來(lái)描述各行政區(qū)域間的相鄰關(guān)系，如下所示：

除關(guān)系矩陣R之外，還需要設(shè)置一個(gè)棧S，用來(lái)記錄行政區(qū)域的所染顏色的序號(hào)：

S[i]?=?k根據(jù)以上說(shuō)明，類型說(shuō)明如下：

intR[n][n];

intS[n];

圖3-8所示行政區(qū)域的關(guān)系矩陣R如圖3-9所示。圖3-8行政區(qū)域地圖及染色結(jié)果

圖3-9關(guān)系矩陣R[7][7]

3)算法設(shè)計(jì)

上述算法的C語(yǔ)言實(shí)現(xiàn)如下：圖3-10運(yùn)行過(guò)程中棧S的變化過(guò)程

3．表達(dá)式求值

1)問(wèn)題描述及分析

任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、操作符(operator)和界限符(delimiter)組成的。在實(shí)際應(yīng)用中，操作數(shù)可以是任何合法的變量名和常數(shù)；操作符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符等；界限符有左右括號(hào)和表達(dá)式結(jié)束符等。在這里僅討論簡(jiǎn)單算術(shù)表達(dá)式的求值問(wèn)題。這種表達(dá)式只含加、減、乘、除四種運(yùn)算符，其運(yùn)算規(guī)則與四則運(yùn)算相同。

2)數(shù)據(jù)結(jié)構(gòu)

為了實(shí)現(xiàn)算符優(yōu)先法，我們?cè)O(shè)置兩個(gè)棧，一個(gè)稱做OPTR，用來(lái)存放運(yùn)算符；另一個(gè)稱做OPND，用以存放操作數(shù)或運(yùn)算結(jié)果。這兩個(gè)棧既可均采用順序存儲(chǔ)，也可采用鏈?zhǔn)酱鎯?chǔ)。

3)算法設(shè)計(jì)

算法的基本思想：

(1)置操作數(shù)棧OPND為空棧，表達(dá)式起始符#為運(yùn)算符棧OPTR的棧底元素。

(2)依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧；若是運(yùn)算符，則在和棧OPTR的棧頂元素比較優(yōu)先權(quán)后做相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢為止。

3.2隊(duì)列

隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭(Front)；允許插入的另一端稱為隊(duì)尾(Rear)。

隊(duì)列同現(xiàn)實(shí)生活中排隊(duì)相仿，新來(lái)的成員總是加入隊(duì)尾(即不允許“加塞”)，每次離開的成員總是隊(duì)列頭上的(不允許中途離隊(duì))，即當(dāng)前“最老的”成員離隊(duì)。換言之，先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。因此隊(duì)列亦稱做先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱為FIFO表。圖3-11隊(duì)列示意圖隊(duì)列抽象數(shù)據(jù)類型的定義如下：3.2.1隊(duì)列的存儲(chǔ)結(jié)構(gòu)

1．順序隊(duì)列

順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣，順序隊(duì)列也必須用一個(gè)數(shù)組來(lái)存放當(dāng)前隊(duì)列中的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置均是變化的，因而需要設(shè)置兩個(gè)指針，分別指示當(dāng)前隊(duì)頭元素和隊(duì)尾元素在數(shù)組中的位置。對(duì)順序隊(duì)列的類型sequeue和一個(gè)實(shí)際的順序隊(duì)列指針sq的說(shuō)明如下：為方便起見，我們規(guī)定頭指針front總是指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針rear指向當(dāng)前隊(duì)尾元素的位置。一開始，隊(duì)列的頭、尾指針指向向量空間下界的前一個(gè)位置，在此設(shè)置為-1。若不考慮溢出，則入隊(duì)運(yùn)算可描述為

sq->rear++; //尾指針加1

sq->data[sq->rear]=x; //x入隊(duì)

出隊(duì)運(yùn)算可描述為

sq->front++;

//頭指針加1

*temp=sq->data[sq->front]; //讀出隊(duì)頭元素圖3-12順序隊(duì)列運(yùn)算時(shí)的頭、尾指針變化情況顯然，當(dāng)前隊(duì)列中的元素個(gè)數(shù)(即隊(duì)列的長(zhǎng)度)是(sq->rear)-(sq->front)。若sq->front=sq->rear，則隊(duì)列長(zhǎng)度為0，即當(dāng)前隊(duì)列是空隊(duì)列，圖3-12(a)和(c)均表示空隊(duì)列?？贞?duì)列時(shí)再做出隊(duì)操作便會(huì)產(chǎn)生“下溢”。隊(duì)滿的條件是當(dāng)前隊(duì)列長(zhǎng)度等于向量空間的大小，即

(sq->rear)-(sq->front)==MAXSIZE克服假上溢通常采用的方法是：設(shè)想向量sq->data

[MAXSIZE]是一個(gè)首尾相接的圓環(huán)，即sq->data[0]接在sq->data[MAXSIZE-1]之后，我們將這種意義下的隊(duì)列稱為循環(huán)隊(duì)列，如圖3-13所示。圖3-13循環(huán)隊(duì)列示意圖若當(dāng)前尾指針等于數(shù)組的上界，則再做入隊(duì)操作時(shí)，令尾指針等于數(shù)組的下界，這樣就能利用到已被刪除的元素空間，克服了假上溢。因此入隊(duì)操作時(shí)，在循環(huán)意義下的尾指針加1操作可描述為

?if(sq->rear+1>=MAXSIZE)sq->rear=0;

elsesq->rear++;

如果利用“?！边\(yùn)算，上述循環(huán)意義下的尾指針加1操作可以更簡(jiǎn)潔地描述為

sq->rear=(sq->rear+1)%MAXSIZE同樣，出隊(duì)操作時(shí)，在循環(huán)意義下的頭指針加1操作，也可利用“?！边\(yùn)算來(lái)實(shí)現(xiàn)，即

sq->front=(sq->frout+1)%MAXSIZE

因?yàn)槌鲫?duì)和入隊(duì)分別要將頭指針和尾指針在循環(huán)意義下加1，所以某個(gè)元素出隊(duì)后，若頭指針已從后面追上尾指針，即

sq->front==sq->rear則當(dāng)前隊(duì)列為空；若某個(gè)元素入隊(duì)后，尾指針已從后面追上頭指針，即

sq->rear==sq->front

則當(dāng)前隊(duì)列為滿。因此，僅憑關(guān)系式sq->front==sq->rear是無(wú)法區(qū)別循環(huán)隊(duì)列是空還是滿的。對(duì)此，有兩種解決的辦法：一種是引入一個(gè)標(biāo)志變量以區(qū)別是空隊(duì)列還是滿隊(duì)；另一種更為簡(jiǎn)單的辦法是入隊(duì)前測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為是隊(duì)滿，即判別隊(duì)滿的條件是：

(sq->rear+1)%MAXSIZE==sq->front

從而保證了sq->rear==sq->front是隊(duì)空的判別條件。在循環(huán)隊(duì)列上實(shí)現(xiàn)的五種基本運(yùn)算如下：

(1)置空隊(duì)列。

(2)判隊(duì)空。

(3)取隊(duì)頭元素。

(4)入隊(duì)。

(5)出隊(duì)。

2．鏈隊(duì)列

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾插入操作，為此再增加一個(gè)尾指針，指向鏈表上的最后一個(gè)結(jié)點(diǎn)。于是，一個(gè)鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一地確定。和順序隊(duì)列類似，我們也是將這兩個(gè)指針?lè)庋b在一起，將鏈隊(duì)列的類型linkqueue定義為一個(gè)結(jié)構(gòu)體類型，如下所示：

typedefstruct{

linklist*front,*rear;

}linkqueue;

linkqueue

q;圖3-14鏈隊(duì)列示意圖在鏈隊(duì)列上實(shí)現(xiàn)的五種基本運(yùn)算如下：

(1)置空隊(duì)。

(2)判隊(duì)空。

(3)取隊(duì)頭結(jié)點(diǎn)數(shù)據(jù)。

(4)入隊(duì)。

(5)出隊(duì)。3.2.2隊(duì)列的應(yīng)用

1．劃分子集問(wèn)題

1)問(wèn)題描述與分析

已知集合A?=?{a1，a2，…，an}，并已知集合上的關(guān)系R?=?{(ai，aj)|ai，aj屬于A，i不等于j}，其中(ai，aj)表示ai與aj之間的沖突關(guān)系。現(xiàn)要求將集合A劃分成互不相交的子集A1，A2…Am(m≤n)，使任何子集上的元素均無(wú)沖突關(guān)系，同時(shí)要求劃分的子集個(gè)數(shù)較少。

2)數(shù)據(jù)結(jié)構(gòu)

采用循環(huán)篩選法。從集合A中的第一個(gè)元素開始，凡與第一個(gè)元素?zé)o沖突且與該組中的其他元素也無(wú)沖突的元素劃歸一組，作為一個(gè)子集A1；再將A中剩余元素按同樣的方法找出互不沖突的元素劃歸第二組，即子集A2；依次類推，直到A中所有元素都劃歸不同的組(子集)為止。

在計(jì)算機(jī)實(shí)現(xiàn)時(shí)，首先要將集合中元素的沖突關(guān)系設(shè)置一個(gè)沖突關(guān)系矩陣，用一個(gè)二維數(shù)組R[n][n]表示，若第i個(gè)元素與第j個(gè)元素有沖突則R[i][j]?=?1；否則R[i][j]?=?0。對(duì)應(yīng)上述問(wèn)題的關(guān)系矩陣R見圖3-15。圖3-15關(guān)系矩陣R[q][q]另外，還要設(shè)置以下數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列cq[n]，用來(lái)存放集合A的元素；數(shù)組result[n]用來(lái)存放每個(gè)元素的分組號(hào)；newr[n]為工作數(shù)組。其類型定義如下：

intR[n][n];

intcq[n],result[n],newr[n];

3)算法思想

初始狀態(tài)：集合A中的元素放入cq中，result和newr置0，設(shè)組號(hào)group?=?1。如圖8-16(a)所示。圖3-16劃分子集的篩選過(guò)程

4)算法實(shí)現(xiàn)

2．離散事件仿真

1)問(wèn)題描述及分析

假設(shè)服務(wù)系統(tǒng)有四個(gè)窗口對(duì)外接待客戶，在營(yíng)業(yè)時(shí)間內(nèi)不斷有客戶進(jìn)入并要求服務(wù)。由于每個(gè)窗口只能接待一個(gè)客戶，因此進(jìn)入該服務(wù)系統(tǒng)的客戶須在某一個(gè)窗口前排隊(duì)。如果窗口的服務(wù)員忙則進(jìn)入的客戶排隊(duì)等待；閑則可立即服務(wù)。服務(wù)結(jié)束則從隊(duì)列中撤離，并計(jì)算一天內(nèi)進(jìn)入服務(wù)系統(tǒng)的客戶的平均逗留時(shí)間。影響系統(tǒng)隊(duì)列變化的原因有兩種：

(1)新客戶進(jìn)入服務(wù)系統(tǒng)，該客戶加入到隊(duì)列最短的窗口隊(duì)列中。

(2)四個(gè)隊(duì)列中有客戶服務(wù)完畢而撤離。

2)算法思想

假設(shè)事件表中最早發(fā)生的是新客戶到達(dá)，則隨之應(yīng)得到兩個(gè)時(shí)間：一是本客戶處理業(yè)務(wù)所需時(shí)間；二是下一個(gè)客戶到達(dá)服務(wù)系統(tǒng)的時(shí)間間隔。此時(shí)模擬程序應(yīng)做的工作如下：

(1)比較四個(gè)隊(duì)列中的客戶數(shù)，