【正文】 下面的程序給出了棧的連續(xù)存貯結(jié)構(gòu)下的基本操作的實(shí)現(xiàn)。 len=0。 //分配 m個(gè)元素的空間 if (room==NULL) throw TExcepComm(4)。 TStackSquTElem::Push(TElem amp。 //elem進(jìn)棧 len++。 //?？諘r(shí)觸發(fā)異常 len。 TStackSquTElem::GetTop(void) {//返回棧頂元素 return room[len1]。 x=room[0]。 room[len1]=x。 if (kn1) k=n1。 //復(fù)制 return k。 pE= new TElem[newSize]。 //刪除原空間 room = pE。 167。所以棧采用鏈?zhǔn)酱尜A結(jié)構(gòu)主要目的是避免存貯區(qū)的預(yù)申請(qǐng)問題。它的主要數(shù)據(jù)項(xiàng)為指向棧頂元素的指針。 an1 a1 ^ top len an 圖 4 0鏈?zhǔn)綏；拘问? 棧頭 TStackLink 鏈結(jié)點(diǎn)，棧頂 TLinkNode (二 )面向?qū)ο竺枋? 我們這里將首結(jié)點(diǎn)的地址和鏈表中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)等有關(guān) 鏈表的信息，看做一個(gè)類中的數(shù)據(jù)成員，并針對(duì)其設(shè)置 有關(guān)操作，構(gòu)成一個(gè)類 TStackLink。 類 TStackLink從抽象類 TStack0繼承而來，其定義如 下： template class TElem class TStackLink : public TStack0TElem { protected: TLinkNodeTElem *top。 virtual TElemamp。 Pop(void)。 RollDown()。 //Newly added functions virtualTLinkNodeTElem*PushNode(TLinkNodeTElem *pNode)。 }。這些操作實(shí)質(zhì)上是很直接的、很基本 的，是實(shí)現(xiàn)其他操作的重要基礎(chǔ)，另一方面，由于 鏈表本身的特殊性，也直接需要將這些有關(guān)鏈的操 作作為基本操作。 (三 ) 基本操作實(shí)現(xiàn) 1．初始化： 通過構(gòu)造函數(shù)實(shí)現(xiàn)，只簡單地將 top置為 空，表示無結(jié)點(diǎn)存在。 //成員函數(shù) Clear()的功能是釋放鏈中所有結(jié)點(diǎn) } 2．進(jìn)棧 Push(TElem amp。elem ) { TLinkNodeTElem *pNode。//TElem must support ―=‖ PushNode(pNode)。 TStackLinkTElem::Pop(void) { TLinkNodeTElem *pNode。 } 4．讀棧 GetTop()： 返回棧頂元素的內(nèi)容 的引用。 template class TElemTLinkNode TElem* TStackLinkTElem::PushNode (TLinkNodeTElem*pNode) { pNodenext = top。 } PopNode(void)： 將棧頂結(jié)點(diǎn) 摘下并返回其地址。 //TElem must support ―=‖ pNode = top。 } 7．讀棧頂結(jié)點(diǎn) GetTopNode(void)：將棧頂結(jié)點(diǎn)地址返回。 //p指向第一個(gè)結(jié)點(diǎn) while (p!=NULL) { q=p。 //所有結(jié)點(diǎn)都已釋放，故應(yīng)置 top為空 len=0。 關(guān)于 MoveStack的算法，是多棧共享存貯空間問題中的關(guān)鍵。 由于 n棧共享存貯區(qū)，且它們的棧底位置不固定，所以需有 n個(gè)棧頂指針和 n個(gè)棧底指針，下面給出這種結(jié)構(gòu)的 C++語言描述（假定 n個(gè)棧的元素類型均相同）。 //棧空間，動(dòng)態(tài)空間，做一維數(shù)組用 long *top, //棧頂指針數(shù)組 *bot 。 我們將這 n個(gè)棧（序號(hào)為 0~numStacks1）按固定次序（即相對(duì)位置固定）分配在一維數(shù)組 room中。 1．初始化棧 Init(s) { for(i=0。 } 2．進(jìn)棧 設(shè) s為 TStacks的一個(gè)實(shí)例的指針，將元素 x放到 i號(hào)棧中的過程為 Push ( i, x) { if (stop[i]+1 == sbot[i+1]) { ret = MoveStacks(s, i,1)。 x = sroom[s→top[i]]。下面是它的一種實(shí)現(xiàn)算法。 3) [r與 l是否存在？ ] 若 ls+rsm，則表明總存貯區(qū)中已無法滿足要求的空閑區(qū)，不能移出空位，失敗返回，否則 , 轉(zhuǎn)下面操作。 6) [左移 ] 將序號(hào)為 sbot[l+1] ~ stop[i]的數(shù)組元素依次向左移 m位置，并修改相應(yīng)的棧頂與棧底指針，轉(zhuǎn) 9。 9)[結(jié)束 ] （成功）返回。 隊(duì)列 167。見圖 40。 出隊(duì) ← ○ ○ ○ …… ← ○ ○ 進(jìn)隊(duì) 隊(duì)尾 隊(duì)頭 圖 4 0隊(duì)列示意圖 (二 ) 隊(duì)列抽象模型 這里討論隊(duì)列的面向?qū)ο蟪橄竽Ｐ汀? template class TElem class TQueue0 { protected: long len。 }。 virtual TElemamp。 virtual TElemamp。 virtual void Clear()=0。 u GetLen(void)： 返回隊(duì)長度（元素個(gè)數(shù)）。 u QPush(TElem amp。 u QPop()： 出隊(duì)。 u RollDown()： 將隊(duì)中元素循環(huán)向下（隊(duì)尾底方向） 推一個(gè)位置，隊(duì)尾元素到達(dá)隊(duì)頭。同樣用一維數(shù)組做為隊(duì)元素存貯空間。為了方便，令 front指向隊(duì)頭元素的前一個(gè)位置（空位）。 這里，由于我們不循環(huán)使用隊(duì)空間，故將這種情況的隊(duì)列稱為非循環(huán)隊(duì)列。 3．出隊(duì) 出隊(duì)是將當(dāng)前隊(duì)中頭元素摘取并返回其： if (隊(duì)空 ) 觸發(fā)異常 ； Qfront++。 ? 分析上面的進(jìn)隊(duì)與出隊(duì)算法，由于進(jìn)隊(duì)時(shí) rear增加，但出隊(duì)時(shí) rear也不會(huì)減小，所以，當(dāng)進(jìn)過 N1個(gè)元素 (設(shè)N為隊(duì)空間大小 )后，不論此前是否出過隊(duì)， rear也會(huì)越界。 這種問題的根源是出隊(duì)操作所騰出的空位不能重復(fù)利用。但這種方法效率差； n 循環(huán)隊(duì)列法。 下面考慮循環(huán)隊(duì)列的實(shí)現(xiàn)。 為了處理方便，我們?nèi)匀患俣ǎ? ? 隊(duì)頭指示器 front：指向隊(duì)中第 1個(gè)元素的前一個(gè)位置。 如果設(shè)置隊(duì)長度 len，隊(duì)滿和空的判別，可直接使用len， : 循環(huán)隊(duì) 的具體的存儲(chǔ)用類 TQueueSqu描述如下。 //隊(duì)空間的大小 long CopyRoom(TElem *objRoom, long n1, TElem * srcRoom, long n2)。 ~TQueueSqu()。 virtual TElemamp。 virtual TElemamp。 virtual void Clear()。注意，我們這里用隊(duì)長度判別隊(duì)空與滿。 size=0。 rear=0。 } template class TElem TElemamp。 } rear++。 return room[rear]。 len。 }。 隊(duì)列的鏈?zhǔn)酱尜A結(jié)構(gòu) (一 ) 存儲(chǔ)方法 與棧類似，若隊(duì)中元素個(gè)數(shù)變化范圍很大，則可采用鏈?zhǔn)浇Y(jié)構(gòu)（動(dòng)態(tài)式）。 a2 an ^ front rear len a1 圖 40 鏈?zhǔn)疥?duì)列基本形式 隊(duì)結(jié)點(diǎn) TStackLink 鏈結(jié)點(diǎn) ,隊(duì)頭TLinkNode 隊(duì)尾結(jié)點(diǎn) (二 ) 面向?qū)ο竺枋? 設(shè)立一個(gè)類 TQueueLink，其從 TQueue0派生而來。 TLinkNode *next。 public: TQueueLink()。elem)。 GetHead(void)。 RollUp()。 virtual const TLinkNodeTElem* GetHeadNode (void)。 template class TElem TQueueLinkTElem::TQueueLink() {//構(gòu)造函數(shù)，實(shí)現(xiàn)初始化 front = NULL。 } template class TElem TElemamp。 pNode = new(nothrow) TLinkNodeTElem。 //調(diào)用 QPushNode, 將新生成的鏈結(jié)點(diǎn)推 入隊(duì) return pNodeinfo。注意，在下次調(diào)用該函數(shù)前要將返回值復(fù)制。 //TElem must support ―=‖ delete pNode。 return frontinfo。 //隊(duì)不空時(shí)，新結(jié)點(diǎn)插入到最后一個(gè)結(jié)點(diǎn)的后面 else front = pNode。 //返回隊(duì)頭結(jié)點(diǎn) } template class TElem TLinkNodeTElem *TQueueLinkTElem::QPopNode(void) {//結(jié)點(diǎn)出隊(duì)。 //TElem must support ―=‖ pNode = front。 return pNode。 串 現(xiàn)實(shí)世界中的實(shí)體有多種形式，如數(shù)值、文字符號(hào)序列、圖形、圖象、聲音等。在計(jì)算機(jī)中，串被認(rèn)為是一種特殊線性表 ──元素為文字符號(hào)的線性表，由于現(xiàn)實(shí)問題中經(jīng)常使用串，所以對(duì)串應(yīng)提供靈活多樣的基本操作，選擇合適的存貯結(jié)構(gòu)。串值中字符個(gè)數(shù)（即 n）稱為 串長 ，長度為 0的串稱為 空串 。那么，串之間的大小關(guān)系是如何定義的呢？首先應(yīng)定義單個(gè)字符間的大小關(guān)系。例如，字符 A與 B的 ASCII碼分別為 65與 66（十進(jìn)制），則說 39。 ? ASCII(American Standard code for Information Interchange)是美國信息交換標(biāo)準(zhǔn)編碼，長度為 8位二進(jìn)制符號(hào)，所以最多能編 28=256個(gè)不同的字符。漢字的編碼也有幾種，如大陸用的國標(biāo)碼 (GB2312)，臺(tái)灣地區(qū)用的 Big5等。 ? 要在一個(gè)系統(tǒng)中能混合所用多種文字，則需要一種統(tǒng)一的編碼系統(tǒng)，它將各種文字的基本字符在同一空間內(nèi)編碼。 下面給出幾個(gè)例子說明此定義。 n (long idx)： 返回 s中序號(hào)為 idx的字符。 n (s1, maxNum)： 連接函數(shù)。設(shè)字符 ch可能在 s中出現(xiàn)若干次，則該函數(shù)返回 ch的第 sn次出現(xiàn)的位置（序號(hào)）。 n ? mode同前。 sn的含義同上。 sn省缺值為 1. ? 18