【正文】 template class TElem TQueueLinkTElem::TQueueLink() {//構(gòu)造函數(shù)，實(shí)現(xiàn)初始化 front = NULL。 rear = NULL。 len = 0。 } template class TElem TQueueLinkTElem::~TQueueLink() {//析構(gòu)函數(shù)，調(diào)用 Clear()釋放鏈中所有元素結(jié)點(diǎn) Clear()。 } template class TElem TElemamp。 TQueueLinkTElem::QPush(TElem amp。elem) {//進(jìn)隊(duì)。元素值 elem進(jìn)隊(duì)，并返回它在隊(duì)中的值的引用 TLinkNodeTElem *pNode。 pNode = new(nothrow) TLinkNodeTElem。 //申請(qǐng)鏈結(jié)點(diǎn) if (pNode==NULL) throw TExcepComm(4)。 pNodeinfo = elem 。//TElem must support ―=‖ QPushNode(pNode)。 //調(diào)用 QPushNode, 將新生成的鏈結(jié)點(diǎn)推 入隊(duì) return pNodeinfo。 } template class TElem TElemamp。 TQueueLinkTElem::QPop(void) {//出隊(duì)。返回隊(duì)頭元素值的引用。注意，在下次調(diào)用該函數(shù)前要將返回值復(fù)制。 TLinkNodeTElem *pNode。 pNode = QPopNode()。 //調(diào)用 QPopNode，將隊(duì)頭元素摘下 elemBuff = pNode info。 //TElem must support ―=‖ delete pNode。 return elemBuff。 //返回隊(duì)頭元素值的引用 } template class TElem TElemamp。 TQueueLinkTElem::GetHead(void) {//返回隊(duì)頭元素的值的引用 if (front==NULL) throw TExcepComm(2)。 return frontinfo。 } template class TElem TLinkNodeTElem* TQueueLinkTElem ::QPushNode(TLinkNodeTElem *pNode) {//結(jié)點(diǎn)進(jìn)隊(duì)。將 pNode所指結(jié)點(diǎn)進(jìn)到隊(duì)尾 pNodenext = NULL。 if (rear!=NULL) rearnext = pNode。 //隊(duì)不空時(shí)，新結(jié)點(diǎn)插入到最后一個(gè)結(jié)點(diǎn)的后面 else front = pNode。 //隊(duì)空時(shí)，新結(jié)點(diǎn)作為隊(duì)中第一個(gè)結(jié)點(diǎn) rear = pNode。 //令 rear指向新的隊(duì)尾 len++。 return front。 //返回隊(duì)頭結(jié)點(diǎn) } template class TElem TLinkNodeTElem *TQueueLinkTElem::QPopNode(void) {//結(jié)點(diǎn)出隊(duì)。將隊(duì)頭結(jié)點(diǎn)摘除并返回其指針 TLinkNodeTElem *pNode。 if (front==NULL) throw TExcepComm(5)。 //隊(duì)空時(shí)拋擲異常 elemBuff = frontinfo。 //TElem must support ―=‖ pNode = front。 front = frontnext。 //將隊(duì)頭元素摘下 if (front==NULL) rear=NULL。 //出隊(duì)后，若隊(duì)變空，則 rear也要置為空 len。 return pNode。 //返回所摘下的元素 } template class TElem const TLinkNodeTElem* TQueueLinkTElem::GetHeadNode(void) {//返回隊(duì)頭元素指針 return front。 } ? 在 QPushNode()中 ， 在新結(jié)點(diǎn)進(jìn)隊(duì)前 ， 要特別注意隊(duì)是否為空 ！ 為空時(shí)相當(dāng)于在空鏈中插入結(jié)點(diǎn) ， 要特殊處理 ！ 類似地 ， 在 QPopNode()中 ， 出隊(duì)后要特別注意隊(duì)是否已變空 ， 若已變空 ， 則 rear指針要置為空 。 167。 串 現(xiàn)實(shí)世界中的實(shí)體有多種形式，如數(shù)值、文字符號(hào)序列、圖形、圖象、聲音等。其中，文字（符號(hào)）序列稱為字符串，簡稱串。串在現(xiàn)實(shí)世界中是屢見不鮮的。如人名、產(chǎn)品名、事物名稱、車牌號(hào)、文獻(xiàn)、源程序等。在計(jì)算機(jī)中，串被認(rèn)為是一種特殊線性表 ──元素為文字符號(hào)的線性表，由于現(xiàn)實(shí)問題中經(jīng)常使用串，所以對(duì)串應(yīng)提供靈活多樣的基本操作，選擇合適的存貯結(jié)構(gòu)。 167。 串的邏 輯結(jié)構(gòu) (一 ) 基本概念 串 是由零個(gè)或多個(gè)字符構(gòu)成的有限序列，一般記為 s = ―a1a2… an‖ (n≥ 0) 其中， s代表 串的名稱 ，用雙引號(hào)括起來的部分（不含該雙引號(hào)本身）為 串值 （即字符序列），每個(gè) ai為一個(gè)字符。字符是計(jì)算機(jī)可識(shí)別的任意符號(hào)（字母、數(shù)字及其它符號(hào)）。串值中字符個(gè)數(shù)（即 n）稱為 串長 ，長度為 0的串稱為 空串 。 串中任意個(gè)連續(xù)字符構(gòu)成的部分稱為該串的 子串 ，包含子串的串相對(duì)該子串稱為 主串 。串中某字符在串中出現(xiàn)的序號(hào)為該字符在串中的 字符位置 ，子串中第 1個(gè)字符在串中的序號(hào)稱為該子串在該串中的 位置 。 下面是幾個(gè)例子： s1=“ab123” //長度為 5的串 s2=“100” //長度為 3的串 s3=“ ” //含兩個(gè)空格字符的串，長度為 2 s4=“” //空串，長度為 0 顯然，若某串的長度為 n，則在該串中，長度為 1的子串的個(gè)數(shù)為 n個(gè)，長度為 2的子串的個(gè)數(shù)為 n1個(gè)， … ，長度為 i的子串的個(gè)數(shù)為 n(i1)個(gè)，即 ni+1個(gè)，所以，長度為 n的串中子串總數(shù)（包括空串與自身）為 1+ = 1+ ????niin1)1( 2 )1( ?nn (二 ) 串的比較運(yùn)算的定義 在實(shí)際應(yīng)用中，常需要論及串之間的大小關(guān)系。那么，串之間的大小關(guān)系是如何定義的呢？首先應(yīng)定義單個(gè)字符間的大小關(guān)系。 1．字符的大小 在計(jì)算機(jī)中，每個(gè)字符都有一個(gè)唯一的數(shù)值表示 ── 字符編碼（字符內(nèi)碼），字符間的大小關(guān)系就定義為它們的代碼之間的大小關(guān)系。字符編碼可有多種，對(duì)英文字母和符號(hào)， ASCII碼是最常見的一種。本教程就用字符的 ASCII碼之間的大小關(guān)系代表相應(yīng)字符的大小關(guān)系。例如，字符 A與 B的 ASCII碼分別為 65與 66（十進(jìn)制），則說 39。A39。39。B39。 ? ASCII(American Standard code for Information Interchange)是美國信息交換標(biāo)準(zhǔn)編碼，長度為 8位二進(jìn)制符號(hào)，所以最多能編 28=256個(gè)不同的字符。但 ASCII中規(guī)定，最高位為 1的碼代表一些特殊的字符（或命令），所以， ASCII有效的字符編碼為 128個(gè)，其包括英文大小寫字母，數(shù)字 0~9及其他一些常用符號(hào)（計(jì)算機(jī)鍵盤上的字符鍵）。在字符和數(shù)字中，空格編碼最小， 其次是數(shù)字（按 09的次序）、大寫字母（按 AZ的次序）、小寫字母（按 az的次序）等。 對(duì)漢字，它們的大小關(guān)系也按編碼大小確定。漢字的編碼也有幾種，如大陸用的國標(biāo)碼 (GB2312)，臺(tái)灣地區(qū)用的 Big5等。 ? GB2312（國標(biāo)碼）是針對(duì)漢字的 16位二進(jìn)制編碼，所以最多能編 216=65536個(gè)不同的碼，則足以代表新華字典中的所有漢字。 GB2312將漢字分為兩級(jí)編碼，分別稱一級(jí)字庫和二級(jí)字庫。一級(jí)字庫包括了日常用的大多數(shù)漢字，它中的漢字的國標(biāo)碼之間的大小關(guān)系，與對(duì)應(yīng)的漢語拼音構(gòu)成的串的大小關(guān)系一致（新華字典中，排在較前面的字，它的國標(biāo)碼也較?。?jí)字庫中的漢字碼之間的大小關(guān)系，與對(duì)應(yīng)漢字的筆劃數(shù)目的大小關(guān)系一致。 ? 要在一個(gè)系統(tǒng)中能混合所用多種文字，則需要一種統(tǒng)一的編碼系統(tǒng)，它將各種文字的基本字符在同一空間內(nèi)編碼。 UniCode就是這樣一種編碼。 2．字符串間的大小關(guān)系 有了字符大小的定義，就可以考慮串的小關(guān) 系了。設(shè) X與 Y是兩個(gè)串： X=―x1x2… xm‖ Y=―y1y2… yn― 則它們之間的大小關(guān)系定義如下： ①當(dāng) m=n且 x1=y1, … , xm=yn，則稱 X=Y. ② 當(dāng)下列條件之一成立時(shí)，稱 XY： i) mn，且 xi=yi， i=1,2, … , m ii)存在某一個(gè) k≤MIN(m,n) ，使得 xi=yi,i=1,2,… ，k1， xkyk ③ 不屬于情況①與②時(shí)，稱 XY. 這種方法定義的串的大小關(guān)系，也稱字典序。 下面給出幾個(gè)例子說明此定義。 ” abac‖與 “ abac‖：相等 (=) we與 web：前者小于后者 (情況 i) mouth與 move：前者小于后者（情況 ii） (三 ) 串的基本操作 在實(shí)際應(yīng)用中，對(duì)串的操作是多種多樣的，所以，為了處理方便，為串引入的基本操作也應(yīng)很多。下面介紹幾種常見的。這里，用 s,s1, … 表示串對(duì)象。 n (long idx)： 返回 s中序號(hào)為 idx的字符。 n (maxNum)： 將 s的值復(fù)制一份，返回其引用（或地址）， maxNum表示最多復(fù)制的字符數(shù)目省缺時(shí)表示 “ 全部 ” 。 n (s1, mode)： 串比較函數(shù)，比較 s與 s1之間的大小關(guān)系，若 ss1，返回負(fù)數(shù)；若 s==s1則返回 0；若 ss1則返回正數(shù)。 mode為比較 /匹配模式，為下列兩種之一： 大小寫敏感方式 (Sensitive)、大小寫不敏感方式 (NonSensitive). mode省缺值為 “ 大小寫敏感 ” （下同）。 n ()： 長度函數(shù)。返回值為 s的長度。 n (s1, maxNum)： 連接函數(shù)。將 s1的值連的尾部，使 s的值變?yōu)樵?s與 s1首尾相接的結(jié)果。 maxNum 表示最多復(fù)制的字符數(shù)目，省缺時(shí)表示 “ 全部 ” n (ch, mode,sn)： 字符位置函數(shù)。設(shè)字符 ch可能在 s中出現(xiàn)若干次，則該函數(shù)返回 ch的第 sn次出現(xiàn)的位置（序號(hào)）。 sn為正數(shù)時(shí)表示 “ 正向數(shù) ” （ sn=1表示第一個(gè)字符）； sn為負(fù)數(shù)時(shí)表示 “ 倒數(shù) ” （ sn=1表示最后字符）。 mode為針對(duì) ch的比較 /匹配模式。 sn缺省值為 1。 n (s1, mode, sn)： 子串位置函數(shù)。返回子串s1在 s中第 sn次出現(xiàn)的出現(xiàn)位置（序號(hào)）。 sn含義同上， Mode同前，是針對(duì)在 s中查找 s1的比較 /匹配的模式。 ? (s1, mode, sn,sn2)： 搜索子串函數(shù)。在 s中按 mode 方式，從 s中的第 sn起查找 s1的第 sn2個(gè)出現(xiàn)，返回出現(xiàn)位置。這里， sn的含義與前面的 sn類似，當(dāng) sn0時(shí)搜索從左到右，否則從右到左。 mode同前。 ? (sn, num)：求子串函數(shù)。返回 s中第 sn字符的 num個(gè)字符構(gòu)成的子串的引用（或地址）。 sn的含義同上。 num0時(shí)表示從 “ 左向右 ” 截取， num 0表示“ 從右向左 ” 截取。 num=0時(shí)表示從 sn起的 “ 全部 ” ，此時(shí)，若 sn0則 num相當(dāng)于正 0(+0)（從左向右的全部），否則相當(dāng)負(fù) 0（ 0）。 num省缺值為 +0或 0(根據(jù) sn的正負(fù)決定 )。 sn省缺值為 1. ? (s1,s2, mode, sn, num)： 子串替換函數(shù)。在 s中，用 s2的值替 s1的從第 sn個(gè)出現(xiàn)起的 num個(gè)出現(xiàn)。返回實(shí)際替