【文章內(nèi)容簡介】 鏈中所有結(jié)點(diǎn) template class TElemvoid TStackLinkTElem::Clear() { TLinkNodeTElem *p, *q。 p=top。 //p指向第一個(gè)結(jié)點(diǎn) while (p!=NULL) { q=p。 p=pnext。 //令 p指向下一個(gè)結(jié)點(diǎn) delete q。 //釋放原 p所指結(jié)點(diǎn) } top = NULL。 //所有結(jié)點(diǎn)都已釋放，故應(yīng)置 top為空 len=0。 } ? 注意，“ delete p‖并不自動將 p置為空，所以，若在上面的程序中， 沒有“ top=NULL‖，則如果再次所用對應(yīng)的對象，會發(fā)生錯誤！ 167。 多棧共享存貯空間 * (一 ) 存儲方法 棧采用連續(xù)存貯結(jié)構(gòu)時(shí)，要預(yù)分配足夠大的存貯空間。若系統(tǒng)中使用 n個(gè)棧，每個(gè)棧的最大尺寸為 ni(i=1,2, …, n) ，則 n個(gè)棧要預(yù)分配的總存貯容量為 如果已知這 n個(gè)棧 在任何時(shí)刻的總的存貯 ??niin1 占用量均不會超過 N，且有 N 則可考慮令 這 n個(gè)棧共享一塊大小為 N的存貯區(qū)，以節(jié)省存貯空間(圖 40) 棧 1 棧 2 … … 棧 n 棧 1底 棧 2底 棧 3底 棧 n底 圖 4 0n棧共享存貯空間 ??niin1 在這種情況下，除第一個(gè)棧外，其它棧的棧底位置均不固定，當(dāng)某棧溢出時(shí)（即棧頂與下一個(gè)棧的棧底重疊時(shí)），應(yīng)該移動若干個(gè)棧，為該棧讓出一些空間，這個(gè)過程稱為棧移動過程 MoveStack。 關(guān)于 MoveStack的算法，是多棧共享存貯空間問題中的關(guān)鍵。它的設(shè)計(jì)目標(biāo)應(yīng)能使系統(tǒng)運(yùn)行期間內(nèi)的總的平均元素移動量最小。最直觀的目標(biāo)是，使一次MoveStack的執(zhí)行所引起的移動量最小。然而，由于各個(gè)棧在獨(dú)立工作，它們的進(jìn)棧出棧操作是隨機(jī)的，所以某次 MoverStack的移動量最小并不能保證總的平均移動量最小。 由于 n棧共享存貯區(qū)，且它們的棧底位置不固定，所以需有 n個(gè)棧頂指針和 n個(gè)棧底指針，下面給出這種結(jié)構(gòu)的 C++語言描述（假定 n個(gè)棧的元素類型均相同）。 template class TElem //設(shè)棧元素類型為可變類型Telem class Tstacks { long numStacks。 //棧的個(gè)數(shù) long totSize。 // 總?？臻g尺寸 TElem *room。 //?？臻g，動態(tài)空間，做一維數(shù)組用 long *top, //棧頂指針數(shù)組 *bot 。 //棧底指針數(shù)組 public: TStacks(long mNumStacks, long mTotSize)。 ~TStacks()。 //下面是其他成員函數(shù)，此略 }。 我們將這 n個(gè)棧（序號為 0~numStacks1）按固定次序（即相對位置固定）分配在一維數(shù)組 room中。 初始時(shí)，令它們各占有 個(gè)元素的空間（最后一個(gè)棧要多占有一些）， 即令 top[i]=bot[i]= * i 這里， i=0, 1, … , numStacks1。 為處理方便，我們增設(shè)一個(gè)虛棧，它的序號為 numStacks，它的底指針定義為 bot[numStacks1]=totSize 這種分配可用圖 40所示。 ??????n um S tac k sto tSi z e??????n um S t ac k st o t Si z e 棧 1 棧 2 … … 棧 n top[0] bot[0] top[1] bot[1] top[2] bot[2] top[n1] bot[n1] 圖 40 n棧共享存貯空間初始空間分配 top[n] bot[n] （二）算法考慮 下面用偽碼給出 n棧共享空間的主要算法。 1．初始化棧 Init(s) { for(i=0。 inumStacks。 i++) stop[i] = sbot[i] =i*totSize/numStacks。 sbot[numStacks]=totSize。 } 2．進(jìn)棧 設(shè) s為 TStacks的一個(gè)實(shí)例的指針，將元素 x放到 i號棧中的過程為 Push ( i, x) { if (stop[i]+1 == sbot[i+1]) { ret = MoveStacks(s, i,1)。 //i號棧滿 ,調(diào)用MoveStacks為 I號棧讓出 1個(gè)位置 if (ret 0) 觸發(fā)異常； //棧真滿，無空閑空間可利用 } stop[i]++。 sroom[stop[i]] = x。 //進(jìn)棧 } 3．出棧 設(shè) s為 TSstacks的一個(gè)實(shí)例的指針，將 i號棧頂?shù)脑貜棾龇祷氐倪^程為 Pop(i) { if (stop[i]==sbot[i]) 觸發(fā)?？债惓?。 x = sroom[s→top[i]]。 s→top[i] 。 return x。 } 4．棧移動 相比這下，棧移動過程 MoveStack(s, i, m)較復(fù)雜，它的功能是為 i號棧騰出 m個(gè)空位。下面是它的一種實(shí)現(xiàn)算法。 這里，用 n表示 numStacks. 為了使讀者了解另外一種算法描述 方法，這里采用自然語言流程描述法。 1) [向右搜索空閑區(qū) ] 對 r=i+1, i+2, …, n 1，計(jì)算各棧的空閑空間，并累計(jì)到 rs中，一旦 rs=m，則停止搜索 ,并記下當(dāng)前 r值。 2) [向左搜索空閑區(qū) ] 對 l=i1, i2, …, 0 ，計(jì)算各棧的空閑空間，并累計(jì)到 ls 中，一旦 ls=m，則停止搜索，并記下當(dāng)前 l值。 3) [r與 l是否存在？ ] 若 ls+rsm，則表明總存貯區(qū)中已無法滿足要求的空閑區(qū)，不能移出空位，失敗返回，否則 , 轉(zhuǎn)下面操作。 4)[確定移量量 ] 若 rs=m（ r存在），計(jì)算在 i棧右方讓出空位 的元素移動量 rm=stop[r] – stop[i]否則 (r不存在 )令 rm=0。若 ls=m，計(jì)算在 I棧左邊讓出空位的元素移動量 lm=s top[i] – sbot[l+1]否則令 lm==0。 5)[確定移動方向 ] 若 rm與 lm均為 0，則應(yīng)兩邊移，轉(zhuǎn) 8；若 lm=0，或 lm=0但 lmrm，則表明應(yīng)向右移，轉(zhuǎn) 7，（否 則應(yīng)向左移，下滑到 6）。 6) [左移 ] 將序號為 sbot[l+1] ~ stop[i]的數(shù)組元素依次向左移 m位置，并修改相應(yīng)的棧頂與棧底指針，轉(zhuǎn) 9。 7) [右移 ] 將序號為 stop[r] ~ stop[i]+1的數(shù)組元素依次向右移 m位置，并修改相應(yīng)的棧頂與棧底指針。轉(zhuǎn) 9。 8) [兩邊移 ] 根據(jù)均衡原則，分頭向左右兩移動若干元素（總量為 m個(gè)）。 9)[結(jié)束 ] （成功）返回。 (三 ) 兩棧共享存貯空間 對于兩棧共享存貯空間，可以特殊處理，以避免移動元素。方法是將兩棧的棧底分別固定在存貯區(qū)的兩端，兩棧指針相向增長（見圖 40）。 棧 1 棧 2 圖 40 兩棧共享存貯空間 167。 隊(duì)列 167。 隊(duì)列的邏輯結(jié)構(gòu) (一 ) 基本概念 隊(duì)列 (Queue)，簡稱為隊(duì)，是一種限定僅分別在表的兩端進(jìn)行插入與刪除的線性表。允許插入的一端稱隊(duì)尾，允許刪除的一端稱隊(duì)頭。插入與刪除操作分別稱為入隊(duì)與出隊(duì)。見圖 40。 隊(duì)是一種先進(jìn)先出 FIFO（ First In First Out）的結(jié)構(gòu)，元素出隊(duì)的次序與進(jìn)隊(duì)次序相同。 現(xiàn)實(shí)世界中有許多問題（關(guān)系）可用隊(duì)列描述，例如，對顧客服務(wù)的部門的工作往往是按排隊(duì)方式進(jìn)行的，這類系統(tǒng)稱作排隊(duì)系統(tǒng)。在計(jì)算機(jī)算法實(shí)現(xiàn)中，也經(jīng)常使用隊(duì)列記錄需按 FIFO方式處理的數(shù)據(jù)。 出隊(duì) ← ○ ○ ○ …… ← ○ ○ 進(jìn)隊(duì) 隊(duì)尾 隊(duì)頭 圖 4 0隊(duì)列示意圖 (二 ) 隊(duì)列抽象模型 這里討論隊(duì)列的面向?qū)ο蟪橄竽Ｐ?。抽象模型主要通過基本操作定義。隊(duì)列的基本操作主要包括進(jìn)隊(duì)、出隊(duì)。下面是描述隊(duì)列的抽象模型的類 TQueue0，它規(guī)定了通用操作接口（基本操作），是各種存儲結(jié)構(gòu)的隊(duì)列的基礎(chǔ)。 template class TElem class TQueue0 { protected: long len。 public: long GetLen(void) {return len。 }。 char IsEmpty() {return (len=0)? 1:0。 }。 virtual TElemamp。 QPush(TElem amp。elem)=0。 virtual TElemamp。 QPop(void)=0。 virtual TElemamp。 GetHead(void)=0。 virtual TElemamp。 RollDown()=0。 virtual TElemamp。 RollUp()=0。 virtual void Clear()=0。 }。 下面對該類中主要部分進(jìn)行說明。 u len： 私有數(shù)據(jù)成員，表示隊(duì)中當(dāng)前元素個(gè)數(shù)。 u GetLen(void)： 返回隊(duì)長度（元素個(gè)數(shù)）。該函數(shù)可直接在此實(shí)現(xiàn)。 u IsEmpty()： 檢查隊(duì)是否為空，空時(shí)返回邏輯 True， 否則返回 False。該函數(shù)可直接在此實(shí)現(xiàn)。 u QPush(TElem amp。elem)： 進(jìn)隊(duì)。將元素 elem加入隊(duì)中，返回其在隊(duì)中值的引用。溢出時(shí)觸發(fā)異常。 u QPop()： 出隊(duì)。將隊(duì)頭元素摘下，并返回其值的引用。下溢（隊(duì)空）時(shí)觸發(fā)異常。 u GetHead(void)： 與 QPop()類似，只是不摘下元素。 u RollDown()： 將隊(duì)中元素循環(huán)向下（隊(duì)尾底方向） 推一個(gè)位置，隊(duì)尾元素到達(dá)隊(duì)頭。 u