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