【正文】 ? 入口為 [1][1]，出口為 [m][n]。 表示： ? 二維數(shù)組 maze[i][j]（ 1≤i≤m, 1≤j≤n）。與棧的情況類似， QueueFull( )和 QueueEmpty( )的實現(xiàn)也依賴于具體的應用。x。 x = queue[++front % = MaxSize]。 return 0。 } JYP 126 template class Type Type* QueueType::Delete( Typeamp。 if (front == k) QueueFull( )。 JYP 125 通過整數(shù)模運算 （ %） 可實現(xiàn) front和 rear沿著順時針方向移動一個位置 ， 從而得到環(huán)狀隊列 Add和Delete操作的實現(xiàn)算法： template class Type void QueueType::Add(const Typeamp。 ? 隊列為空時的 front == rear是由于刪除操作使front ―追?上 rear所致；而隊列滿的時候， front == rear是由于加入操作使 rear ―追?上 front所致。 } JYP 122 如下所示， IsFull( ) == TRUE并不一定表示隊列中有 MaxSize個元素： JYP 123 因此，將數(shù)組 queue[MaxSize]視為環(huán)狀隊列，如下所示： JYP 124 ? 判斷隊列是否為空的條件仍然是 front == rear。 return amp。}。 x) { if (IsEmpty( )) { QueueEmpty( )。 else queue[++rear] = x。 } Add的實現(xiàn)： template class Type void QueueType::Add(const Typeamp。 } JYP 120 IsEmpty( )的實現(xiàn)： template class Type inline Boolean QueueType::IsEmpty( ) { if (front== rear) return TRUE。 } IsFull( )的實現(xiàn)： template class Type inline Boolean QueueType::IsFull( ) { if (rear==MaxSize1) return TRUE。 JYP 119 Queue的構(gòu)造函數(shù)： template class Type QueueType::Queue(int MaxQueueSize): MaxSize(MaxQueueSize) { queue = new Type[MaxSize]。 Type* queue。為了便于判斷隊列是否為空， front指向隊列第一個元素所在位置的前一個， rear指向隊列最后一個元素所在位置。 }。 Type* Delete( Typeamp。 item)。 Boolean IsFull( )。 ? 隊列 S = ( a0, …, a n1)， a0是前端元素， an1是尾端元素， ai在 ai1之后（ 0 i n）。 } StackFull( )和 StackEmpty( )的實現(xiàn)依賴于具體的應用。 return amp。}。 x) { if (IsEmpty( )) { StackEmpty( )。 else stack[++top] = x。 } Add的實現(xiàn)： template class Type void StackType::Add(const Typeamp。 } JYP 114 IsEmpty( )的實現(xiàn)： template class Type inline Boolean StackType::IsFull( ) { if (top == 1) return TRUE。 } IsFull( )的實現(xiàn)： template class Type inline Boolean StackType::IsFull( ) { if (top == MaxSize1) return TRUE。 JYP 113 Stack的構(gòu)造函數(shù)： template class Type StackType::Stack(int MaxStackSize):MaxSize(MaxStackSize) { stack = new Type[MaxSize]。 Type* stack。 top = –1表示?？?。為確保該指針所指的數(shù)據(jù)在 Delete函數(shù)結(jié)束仍然 JYP 112 存在，采用一個引用參數(shù)，將被刪除元素復制到該引用參數(shù)，并返回該參數(shù)的指針。 }。 Type* Delete( Typeamp。 item)。 Boolean IsFull( )。 ? 棧 S = ( a0, …, a n1)， a0是棧底元素， an1是棧頂元素， ai在 ai1之上（ 0 i n）。 整個模式匹配問題可用 O(LengthP + LengthS)的時間完成。 while循環(huán)中的語句在整個算法中最多執(zhí)行 LengthP–1次。由于第 4行共執(zhí)行 LengthP–1次， i的總增加值最多為 LengthP–1。 // 找不到滿足條件的 m 8 } // for 結(jié)束 9 } // fail 結(jié)束 對 fail的分析： ? 由于 f(i) i， while循環(huán)每迭代一次 i至少減少 1。 //尋找 m 6 if ( *(str+j) == *(str+i+1)) f[j] = i+1。amp。 j++) { // 計算 f[j] 4 int i = f[j1]。 3 for (int j = 1。 JYP 107 1 void String::fail ( ) { // 計算模式 p ( *this)的失敗函數(shù) 2 int LengthP= Length( )。 ? 假設已有 f(j–1)，則可通過以下觀察計 算 f(j)： 若 a = b，則 f(j) = f(j1)+1，否則（標記 f1(j) = f(j)，fm(j) = f( fm1(j))） JYP 105 若 a = c，則 f(j) = f2(j1)+1，否則可以繼續(xù)計算下去，直至找到某個 m，使第 fm(j–1)+1個位置的字符與 a相等，或 fm(j–1) = –1且第 0位置的字符仍不等于 a。 因此， FastFind的總計算時間是 O( LengthS)。 ? j最多可增加至 LengthS（第 7行）。 13 else return i LengthP 。 11 else j = [j1] + 1。 i++。amp。 4 int LengthP = ( ), LengthS = Length( )。 由此可得以下算法 FastFind。 ? y也是其本身兩頭匹配的最大子字符串，但 y不能作為 x用，否則比較將陷入無窮循環(huán)。否則，有兩種情況需要處理： JYP 98 （ 1） j = 0，只需繼續(xù)比較 si+1與 p0即可，如下圖所示： JYP 99 （ 2） j 0，設 y=p0, …, p j1， x是 y的兩頭匹配的最大真子字符串，且 x=p0, …, p k，則由于已有匹配的結(jié)果， sik1, …, s i1=pjk1, …, p j1=x，從而 sik1, …, si1 = p0, …, p k，因此 si 可與 pk+1繼續(xù)比較。 設 s = s0, …, s m1， pat = p0, …, p n1，當前正在比較 si與 pj是否相等。Knuth， Morris和 Pratt提出的算法（ KMP算法）就是基于這種思想，并達到了線性時間復雜性。 ? 要有根本改進，應避免回溯掃描。 JYP 96 字符串模式匹配的 KMP算法 ? 能否用 O(LengthP+LengthS)的時間求解字符串模式匹配問題呢？ ? 這樣的算法一定是最佳的，因為在最壞情況下求解此問題必須至少掃描 s和 pat一遍。 // pat 為空字符串，或不出現(xiàn)在 s中 } // Find結(jié)束 JYP 95 對于 s的每一個被考察的位置，都可能在匹配 pat的最后字符時失敗，因此 Find的時間復雜性是O(LengthP?LengthS)。 p = 。 // 找到匹配 } else { // 不匹配，考察 i的下一個位置，重新尋找匹配 i++。amp。 int i = 0。順序考察 s的第 i個位置，判定其是否為一個匹配的起點，直至首次成功匹配，如下圖所示： 設字符串由類型為 char*的私有數(shù)據(jù)成員 str表示，函數(shù) Find實現(xiàn)了上述策略。 // 返回 *this和 x的最長公共子序 // 列的長度 }。 // 返回由字符串 *this 的第 i個位 // 置及其后共計 j個字符構(gòu)成的子字符串 int Find ( String pat )。 String Concat (String t)。 int operator ! ( )。 class String { // 對象 : n≥0個字符構(gòu)成的線性序列 public: String (const char *init, int m)。若 n = 0，則 S為 空串 。這體現(xiàn)了時間與空間的權衡。 21} JYP 89 對圖 (a)的稀疏矩陣應用算法 FastTranspose，執(zhí)行完第 10行后 ， RowSize和 RowStart的值為： FastTranspose的四個循環(huán)分別迭代 Cols、 Terms、Cols1和 Terms次，總時間復雜性是 O(Cols + Terms)。 delete [ ] rowStart。 16 RowStart[smArray[i].col]++。 14 [j].col = smArray[i].row。 i++ ) { // 從 a 向 b復制 12 int j = RowStart[smArray[i].col]。 JYP 88 11 for ( i = 0。i Cols。 9 RowStart[0] = 0。 i Terms。 i++) rowSize[i] = 0。 6 if ( Terms 0 ) { // 計算 b中第 i行的非零項個數(shù) 7 for (int i = 0。 = Rows。 4 SparseMatrix b。由此得算法 FastTranspose： 1 SparseMatrix SparseMatrix::FastTranspose ( ) { // 快速轉(zhuǎn)置 2 int *rowSize = new int[Cols]。這樣，可以再次掃描 a，逐項將 a中元素置入 b的正確位置。如果先掃描一遍矩陣 a，獲得其中各列的元素個數(shù)，就可知道矩陣 b各行的元素個數(shù)。算法的總時間復雜性是 O(Cols?Terms)，需要 O(1)輔助空間。第 11， 12， 13和 14行執(zhí)行Terms次。 15 } 16 } // if ( Terms 0 )結(jié)束 17 return b。 JYP 85 13 [CurrentB].value= smArray[i].value。 i++ ) 10 if (smArray[i].col == c ) { // 找到第 c列的元素 11 [CurrentB].row = c。 c++ ) // 按照列轉(zhuǎn)置 9 for ( int i = 0。 // 當前位置指針 8 for ( int c = 0。 // b的列數(shù) = a的行數(shù) 5 = Terms。 3 = Cols。 改進方法 ： 按原矩陣的列構(gòu)建新矩陣的行，對 j = 0, …, Cols 1 順序掃描原矩陣，找到第 j列元素 i, j, value，將其轉(zhuǎn)變?yōu)樾戮仃嚨牡?j行元素 j, i, value存入三元組數(shù)組的當前位置。 // MaxTerms是常數(shù) JYP 81 前面的稀疏矩陣用三元組表示為： JYP 82 稀疏矩陣