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