chapter3：棧、隊(duì)列-文庫(kù)吧資料
2024-10-07 21:59本頁(yè)面
【正文】 ueue 二、鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) ? 用鏈表表示的隊(duì)列簡(jiǎn)稱(chēng)為鏈隊(duì)列。Q,amp。e) Q為非空隊(duì)列 ,用 e返回 Q的隊(duì)頭元素 ? EnQueue(amp。Q) 隊(duì)列 Q存在則銷(xiāo)毀 Q ? ClearQueue(amp。 ? ────────────── ? 出隊(duì) ← ○ ○ …… ○ ← ○進(jìn)隊(duì) ? ────────────── ? 隊(duì)頭 隊(duì)尾 Queue front rear enqueue dequeue A B C A queue is open at two ends. You can only add entry (enqueue) at the rear , and delete entry (dequeue) at the front. Note that you cannot add/extract entry in the middle of the queue. Firstin Firstout (FIFO) When we enqueue entries in the queue and then dequeue them one by one, we will get the entries in the same order. A B C A A B B C C The first one enqueued is the first one dequeued. (FIFO) 抽象數(shù)據(jù)類(lèi)型隊(duì)列 ? ADT Queue{ ? 數(shù)據(jù)對(duì)象 : D={ai| ai(ElemSet,i=1,2,...,n,n=0} ? 數(shù)據(jù)關(guān)系 : R1={ai1,ai | ai1,ai( D,i=2,...,n} ? 基本操作： ? InitQueue(amp。 現(xiàn)實(shí)世界中有許多問(wèn)題（關(guān)系）可用隊(duì)列描述，顧客服務(wù)部門(mén)的工作方式往往是排隊(duì)方式，這類(lèi)系統(tǒng)稱(chēng)作排隊(duì)系統(tǒng)。插入與刪除分別稱(chēng)為入隊(duì)與出隊(duì)。 隊(duì)列的邏輯結(jié)構(gòu) 一、基本概念 隊(duì)列是一種限定僅分別在表的兩端進(jìn)行插入與刪除的線性表。 printf(%d,e)。 ? while(!StackEmpty(*S)){ ? Pop(S,amp。 ? n=n/8。} ? if(!n) Push(S,0)。 ? if(n0) ? { printf(\nThe number must be over 0.)。 ? scanf(%d,amp。S)。 ? int n。先求得的余數(shù)在寫(xiě)出結(jié)果時(shí)最后寫(xiě)出，最后求出的余數(shù)最先寫(xiě)出，符合棧的先入后出性質(zhì)，故可用棧來(lái)實(shí)現(xiàn)數(shù)制轉(zhuǎn)換： ? void conversion() { ? pSqStack S。 } ? 鏈棧則沒(méi)有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動(dòng)的一頭自由地增加鏈環(huán) (結(jié)點(diǎn) )而不會(huì)溢出，鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要在頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。 =o } void pop() // remove most recent item { if s==Null {printf(“pop fails empty stack} else {a=。 ? }Lnode, *LinkList。 PHead Len 棧頂 棧底 Null 鏈?zhǔn)綏５慕Y(jié)點(diǎn)描述 ? Typedef struct Lnode{ ? ElemType data。它的主要數(shù)據(jù)項(xiàng)為指向棧頂元素的指針，另外可設(shè)一個(gè)存貯當(dāng)前長(zhǎng)度的量。所以棧采用鏈?zhǔn)酱尜A結(jié)構(gòu)主要目的是避免存貯區(qū)的預(yù)申請(qǐng)問(wèn)題。線性表采用鏈?zhǔn)酱尜A，主要有兩個(gè)目的：避免插入 /刪除操作帶來(lái)的移動(dòng)元素問(wèn)題與存貯區(qū)的預(yù)申請(qǐng)問(wèn)題。方法是將兩棧的棧底分別固定在存貯區(qū)的兩底，兩棧指針相向增長(zhǎng) 167。若系統(tǒng)中使用 n個(gè)棧， 每個(gè)棧的最大尺寸 ni (i=1,2,…,n) ， 則 n個(gè)棧要預(yù)分配的總存貯容量為 如果已知這 n個(gè)棧在任何時(shí)刻的總的存貯占用量均不會(huì)超過(guò)N， 且有 N 則可考慮令這 n個(gè)棧共享一塊大小為 N的存貯區(qū)，以節(jié)省存貯空間 。 下溢 本身可以表示棧為空棧 ,因此可以用它來(lái)作為控制轉(zhuǎn)移的條件。順序棧好比一個(gè)盒子，我們?cè)诶镱^放了一疊書(shū)，當(dāng)我們要用書(shū)的話只能從第一本開(kāi)始拿 ,那么當(dāng)我們把書(shū)本放到這個(gè)棧中超過(guò)盒子的頂部時(shí)就放不下了，這時(shí)就
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1