[理學(xué)]數(shù)據(jù)結(jié)構(gòu)3第三章：棧和隊(duì)列ppt課件

1、棧和隊(duì)列棧和隊(duì)列 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造棧的定義棧Stack：是一種操作受限的線性表。它是線性表的一個(gè)重要特例。棧中元素的進(jìn)、出是按照后進(jìn)先出的原那么進(jìn)展的，這是棧構(gòu)造的重要特征。因此，棧又稱(chēng)后進(jìn)先出LIFOLast In First Out的線性表，簡(jiǎn)稱(chēng)為L(zhǎng)IFO表 有關(guān)術(shù)語(yǔ)棧頂、棧底、進(jìn)棧、出棧、空棧棧是限制僅在表的一端進(jìn)展插入和刪除運(yùn)算的線性表。允許插入和刪除的一端稱(chēng)為棧頂Top，即表尾。另一端稱(chēng)為棧底Bottom，即表頭。向棧里放入一個(gè)元素，稱(chēng)為“進(jìn)棧。從棧中取出一個(gè)元素，稱(chēng)為“出棧。當(dāng)棧中沒(méi)有元素時(shí)，稱(chēng)為“空棧。 棧的運(yùn)算棧的根本運(yùn)算：1置空棧SETNULLS2判棧空EMPTYS3進(jìn)棧PU

2、SHS，x4退棧POSS5取棧頂TOPs6 重置空棧CLEARS棧有順序存儲(chǔ)和鏈接存儲(chǔ)兩種方式。棧的示意圖棧的順序存儲(chǔ)構(gòu)造順序棧即棧的順序存儲(chǔ)構(gòu)造，是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素附設(shè)指針top指示棧頂元素在順序棧中的位置。top=0時(shí)，表示?？铡Ｃ慨?dāng)插入一個(gè)新的棧頂元素，top增1；每當(dāng)刪除棧頂元素時(shí)，top減1。 圖例順序棧的定義 / 棧的順序存儲(chǔ)表示 #define STACK_INIT_SIZE 10 / 存儲(chǔ)空間初始分配量 #define STACKINCREMENT 2 / 存儲(chǔ)空間分配增量 struct SqStack SElemType *base;

3、/ 在棧構(gòu)造之前和銷(xiāo)毀之后，base的值為NULL SElemType *top; / 棧頂指針 int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 ; / 順序棧順序棧存儲(chǔ)構(gòu)造順序棧的根本操作Status InitStackSqStack &S / 構(gòu)造一個(gè)空棧Sif!S.base=SElemType malloc S T A C K _ I N I T _ S I Z E * s i z e o fSElemType exitOVERFLOW; / 存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return O

4、K; 構(gòu)造空棧圖例順序棧的根本操作 Status DestroyStackSqStack &S / 銷(xiāo)毀棧S，S不再存在 freeS.base; S.base=NULL; S.top=NULL; S.stacksize=0; return OK; 銷(xiāo)毀順序棧圖例順序棧的根本操作Status ClearStackSqStack &S / 把S置為空棧 S.top=S.base; return OK; Status StackEmptySqStack S / 假設(shè)棧S為空棧，那么返回TRUE，否那么返FALSE ifS.top=S.base return TRUE; else re

5、turn FALSE; 順序棧的根本操作 int StackLengthSqStack S / 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 return S.top-S.base; Status GetTopSqStack S,SElemType &e / 假設(shè)棧不空，那么用e返回S的棧頂元素，并返回OK；否那么返回ERROR ifS.topS.base e=*S.top-1; return OK; else return ERROR; 順序棧的根本操作Status PushSqStack &S,SElemType e / 插入元素e為新的棧頂元素 ifS.top-S.base=S.stac

6、ksize/ 棧滿，追加存儲(chǔ)空間 S.base=SElemType *reallocS.base,S.stacksize+STACKINCREMENT*sizeofSElemType; if!S.base exitOVERFLOW; / 存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; 進(jìn)棧圖例順序棧的根本操作Status PopSqStack &S,SElemType &e / 假設(shè)棧不空，那么刪除S的棧頂元素，用e返回其值，并返回OK；否那么返回ERROR

7、ifS.top=S.base return ERROR; e=*-S.top; return OK; 出棧圖例棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造為什么使用鏈棧防止上溢錯(cuò)誤、棧實(shí)際所用的最大空間是很難估計(jì)的、各個(gè)棧的實(shí)際容量在使用期是可變的。鏈棧棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為鏈棧,它是運(yùn)算受限的單鏈表，它的插入和刪除僅限制在表頭位置上進(jìn)展。棧頂指針就是鏈表的頭指針，它唯一確定一個(gè)鏈棧。由于棧的操作是線性表操作的特例，故鏈棧的操作易于實(shí)現(xiàn) 鏈棧圖例鏈棧圖例鏈棧的根本操作 void pushnode *HS,int x / 在棧頂指針是HS的鏈棧中插入一個(gè)值為x的結(jié)點(diǎn) node *s s=node malloc sizeofn

8、ode； s-date=x； s-next=HS； HS=s； 鏈棧的根本操作 int popnode *HS / 在棧頂指針是HS的鏈棧中取出一個(gè)結(jié)點(diǎn) int x； node *p if HS= =NULL printf“向下溢出n； else x=HS-date； p=HS； HS=HS-next； freep； returnx； 鏈棧的根本操作 int semptnode *HS / 斷定棧頂指針是HS的鏈棧是否為空 if HS= =NULL return1； else return0； 棧的應(yīng)用舉例 void conversion / 算法3.1 / 對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，

9、打印輸出與其等值的八進(jìn)制數(shù) InitStacks; / 初始化棧scanf%d,&n; / 輸入非負(fù)十進(jìn)制整數(shù)n whilen / 當(dāng)n不等于0 Pushs,n%8; / 入棧n除以8的余數(shù)8進(jìn)制的低位 n=n/8; while!StackEmptys / 當(dāng)棧不空 Pops,e; / 彈出棧頂元素且賦值給e printf%d,e; / 輸出e 棧的應(yīng)用舉例void conversion / 對(duì)于輸入的任意一個(gè)非負(fù)10進(jìn)制整數(shù)，打印輸出與其等值的16進(jìn)制數(shù) InitStacks; / 初始化棧 scanf%u,&n; / 輸入非負(fù)十進(jìn)制整數(shù)n whilen / 當(dāng)n不等于0 P

10、ushs,n%16; / 入棧n除以16的余數(shù)16進(jìn)制的低位 n=n/16; while!StackEmptys / 當(dāng)棧不空 Pops,e; / 彈出棧頂元素且賦值給e ifenext=NULL; return OK; 空隊(duì)列圖例鏈隊(duì)列的根本操作 Status DestroyQueueLinkQueue &Q / 銷(xiāo)毀隊(duì)列Q無(wú)論空否均可 whileQ.front Q.rear=Q.front-next; freeQ.front; Q.front=Q.rear; return OK; 銷(xiāo)毀后的隊(duì)列隊(duì)列的根本操作 Status ClearQueueLinkQueue &Q / 將

11、Q清為空隊(duì)列Q.rear=Q.front; p=Q.front-next; Q.front-next=NULL; whilep q=p; p=p-next; freeq; return OK; 隊(duì)列的根本操作Status QueueEmptyLinkQueue Q / 假設(shè)Q為空隊(duì)列,那么返回TRUE,否那么返回FALSE ifQ.front=Q.rear return TRUE; else return FALSE; 鏈隊(duì)列的根本操作int QueueLengthLinkQueue Q / 求隊(duì)列的長(zhǎng)度 int i=0; QueuePtr p; p=Q.front; whileQ.rear!

12、=p i+; p=p-next; return i; 鏈隊(duì)列的根本操作 Status EnQueueLinkQueue &Q,QElemType e / 插入元素e為Q的新的隊(duì)尾元素 p=QueuePtrmallocsizeofQNode if!p exitOVERFLOW; / 存儲(chǔ)分配失敗 p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 鏈隊(duì)列的根本操作Status DeQueueLinkQueue &Q,QElemType &e / 假設(shè)隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值ifQ.front

13、=Q.rear return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; ifQ.rear=p Q.rear=Q.front; freep; return OK; 順序存儲(chǔ)構(gòu)造循環(huán)隊(duì)列順序隊(duì)列出現(xiàn)假溢出的問(wèn)題假如不考慮溢出，入隊(duì)列操作可描繪如下：q.rear=q.rear+1； q.dataq.rear=x 出隊(duì)運(yùn)算描繪為：q.front=q.front+1 顯然，當(dāng)q.front=q.rear時(shí)，假設(shè)作出隊(duì)操作，那么產(chǎn)生“下溢。當(dāng)q.rear-q.front=m時(shí)，隊(duì)滿，再作入隊(duì)操作也會(huì)引起“上溢。循環(huán)隊(duì)列:為了進(jìn)步運(yùn)算的效率，

14、我們用另一種方法表達(dá)數(shù)組中各單元的位置關(guān)系。設(shè)想數(shù)組Q中的m個(gè)單元不是排成一行，而是圍成一個(gè)圓環(huán)，即Q0接在Qm-1之后，形成一個(gè)閉合的環(huán)，這個(gè)意義下的隊(duì)列叫做循環(huán)隊(duì)列。 隊(duì)列的假溢出循環(huán)隊(duì)列示意圖循環(huán)隊(duì)列的定義 #define MAXQSIZE 5 / 最大隊(duì)列長(zhǎng)度對(duì)于循隊(duì)列，最大隊(duì)列長(zhǎng)度要減1 struct S ueue QElemType *base; / 初始化的動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針,假設(shè)隊(duì)列不空,指向隊(duì)列頭元素 int rear; / 尾指針,假設(shè)隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置 ; 隊(duì)列的順序存儲(chǔ)構(gòu)造循環(huán)隊(duì)列的根本操作Status InitQueu

15、eS ueue &Q / 構(gòu)造一個(gè)空隊(duì)列Q Q.base=QElemType*m a l l o c M A X Q S I Z E * s i z e o fQElemType; if!Q.base / 存儲(chǔ)分配失敗 exitOVERFLOW; Q.front=Q.rear=0; return OK; 空隊(duì)列圖例循環(huán)隊(duì)列的根本操作int QueueLengthS ueue Q / 返回Q的元素個(gè)數(shù),即隊(duì)列的長(zhǎng)度 returnQ.rear-Q.front+MAXQSIZE%MAXQSIZE; Status GetHeadS ueue Q,QElemType &e / 假設(shè)隊(duì)列不

16、空,那么用e返回Q的隊(duì)頭元素,并返回OK,否那么返回ERROR ifQ.front=Q.rear / 隊(duì)列空 return ERROR; e=*Q.base+Q.front; return OK; 循環(huán)隊(duì)列的根本操作Status EnQueueS ueue &Q,QElemType e / 插入元素e為Q的新的隊(duì)尾元素 ifQ.rear+1%MAXQSIZE=Q.front / 隊(duì)列滿 return ERROR; Q.baseQ.rear=e; Q.rear=Q.rear+1%MAXQSIZE; return OK; 入隊(duì)操作循環(huán)隊(duì)列的根本操作 Status DeQueueS ueue

17、 &Q,QElemType &e / 假設(shè)隊(duì)列不空,那么刪除Q的隊(duì)頭元素,用e返回其值,并返回OK;否那么返回ERROR ifQ.front=Q.rear / 隊(duì)列空 return ERROR; e=Q.baseQ.front; Q.front=Q.front+1%MAXQSIZE; return OK; 循環(huán)隊(duì)列出隊(duì)操作循環(huán)隊(duì)列的根本操作 Status DestroyQueueS ueue &Q / 銷(xiāo)毀隊(duì)列Q,Q不再存在 ifQ.base freeQ.base; Q.base=NULL; Q.front=Q.rear=0; return OK; 銷(xiāo)毀隊(duì)列圖例實(shí)習(xí)題一

18、 棧、隊(duì)列的算法設(shè)計(jì)本次實(shí)習(xí)的目的在于深化理解棧和隊(duì)列的特性，以便在實(shí)際問(wèn)題背景下靈敏運(yùn)用它們。 1.停車(chē)場(chǎng)管理 根本描繪 設(shè)停車(chē)場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在車(chē)場(chǎng)的最北端，假設(shè)車(chē)場(chǎng)內(nèi)已停滿n輛汽車(chē)，那么后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，那么排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某車(chē)開(kāi)出大門(mén)外，其它車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它分開(kāi)停車(chē)場(chǎng)時(shí)，必須按它停留的時(shí)間長(zhǎng)短繳納費(fèi)用，試為停車(chē)場(chǎng)編制按上述要求進(jìn)展管理的模擬程序。 根本要求 以棧模

19、擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的通道，按照從終端讀八的輸入數(shù)據(jù)序列進(jìn)展模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)的汽車(chē)“到達(dá)或“離去信息，汽車(chē)牌照碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)展操作后的輸出數(shù)據(jù)為：假設(shè)是車(chē)輛離去，那么輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用在便道上停留時(shí)間不收費(fèi)。棧以順序構(gòu)造實(shí)現(xiàn)，隊(duì)列以鏈表構(gòu)造實(shí)現(xiàn)。 測(cè)試數(shù)據(jù) 設(shè)n=2，輸入數(shù)據(jù)為： A,1,5, A,2,10, D,1,15, A,3,20, A,4,25, A,5,30, D,2,35,D,4,10,E,0,0, 其中，A表示到達(dá)，D表示，E表示輸入完畢。實(shí)習(xí)題二 2.車(chē)輛調(diào)度 問(wèn)題描繪 假設(shè)停在鐵路調(diào)度站，如課本3.1所示，入D處車(chē)廂序列的編號(hào)依次為1,2,3, n。設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長(zhǎng)度為