據(jù)結構第四章“串”核心考點全解析：從BF到KMP與next數(shù)組手算)
提到數(shù)據(jù)結構這門課第四章“串”是很多人容易輕視的一章。表面上看不就是字符串操作嗎C語言里天天用strlen、strcpy能有什么難的結果一到期末考試或考研真題遇到next數(shù)組計算、KMP匹配過程、串的替換算法設計直接懵掉。我在帶學生和做技術答疑時被問得最多的就是第四章這些題。說實話這一章如果只靠背課后習題答案下一個題型換個模式串照樣不會做。這篇文章我結合嚴蔚敏《數(shù)據(jù)結構C語言版 第2版》第四章課后習題的高頻題型把串的概念框架、存儲結構選型、模式匹配算法原理、代碼實現(xiàn)和易錯點完整拆一遍。尤其是BF與KMP的復雜度對比、next數(shù)組與nextval數(shù)組的手算方法、幾個典型算法設計題的C語言實現(xiàn)我會給你一條能直接“抄作業(yè)”且能跑通的路徑。同時會指出很多參考書上不會寫出來的坑比如教材用T[0]存串長而C語言數(shù)組從0開始帶來的下標錯位問題。適合正在學數(shù)據(jù)結構的學生、準備考研的讀者以及想補C語言字符串處理細節(jié)的自學者。1. 先把第四章的“地圖”鋪開串到底在考什么1.1 串的定義與術語辨析別把子串和子序列搞混串String是由零個或多個字符組成的有限序列一般記作S “c1c2...cn”。課后習題里第一類送分題往往是概念辨析但很多人在“子串”和“子序列”上栽跟頭。子串要求字符在原文中連續(xù)出現(xiàn)而子序列只要求保持相對順序不要求連續(xù)。舉例說明對串“abcde”子串包括“ab”、“bc”、“bcd”等而“ace”只能叫子序列不能叫子串。主串與模式串的關系也是考點在進行模式匹配時通常把正在被查找的串稱為主串把用于匹配的串稱為模式串匹配成功意味著模式串是主串的子串。還有一個容易忽略的點是“空串”與“空格串”?？沾情L度為0的串寫作“”空格串是只包含空格的串長度為空格字符的個數(shù)。習題中經(jīng)常讓考生判斷某個串是空串還是空格串這不只是摳字眼它直接影響字符串比較、求子串等操作的邊界條件處理。比如兩個看上去都是“空”的串一個含三個空格一個什么都不含它們在StrCompare中是不同的。1.2 三種存儲結構怎么選順序、堆分配、塊鏈的取舍邏輯串的存儲結構是課后問答題的?？汀＝滩慕o出了三種定長順序存儲用一個固定長度的字符數(shù)組存放串比如char S[256]。優(yōu)點是實現(xiàn)簡單、訪問速度快缺點是長度受限插入、替換操作可能溢出。堆分配存儲用一個char*指針配合動態(tài)內(nèi)存分配malloc/realloc來管理串空間按需分配克服了定長存儲的長度限制。這是目前C語言實現(xiàn)串操作最常用的方式。塊鏈存儲類似鏈表每個節(jié)點存放若干字符。優(yōu)點是插入刪除方便缺點是存儲密度低每個節(jié)點還有指針域開銷訪問某個位置的字符需要遍歷?；卮稹盀槭裁创蠖鄶?shù)實用場景選堆分配而不選塊鏈”時我的建議是從時間復雜度和空間開銷兩個角度作答。定長順序存儲雖然快但串長在編譯期就必須確定很不靈活塊鏈存儲雖然解決了長度和插入刪除問題但一個字符一個節(jié)點的話存儲密度只有約1/3查找第i個字符要遍歷i次代價太高。堆分配在時間和空間上取得了平衡長度動態(tài)可變通過下標隨機訪問字符仍然是O(1)。課后習題里如果讓你設計一個文本編輯程序的數(shù)據(jù)結構堆分配存儲是默認選擇。1.3 基本操作的復雜度陷阱StrConcat和SubString沒那么簡單第四章的習題經(jīng)常考察基本操作的時間復雜度比如串聯(lián)接StrConcat、求子串SubString。很多人不假思索就寫O(1)這是錯的。串聯(lián)接需要把兩個串的內(nèi)容復制到新串中設兩個串長度分別為m和n時間復雜度為O(mn)。求子串也需要把子串內(nèi)容從原串復制到目標存儲區(qū)設子串長度為len復雜度為O(len)。插入操作在順序存儲中需要移動大量字符最壞情況是O(n)塊鏈存儲中找一個位置也是O(n)插入本身是O(1)。這些復雜度結論在選擇題、判斷題里反復出現(xiàn)務必記住背后的“為什么”不要死記硬背。我在批改作業(yè)時發(fā)現(xiàn)很多同學容易把SubString的復雜度寫成O(1)理由是復制一個子串挺快。實際上只要涉及字符拷貝復雜度就是O(len)除非你只修改指針指向比如用char*指向子串起始位置但那樣子串沒有獨立的結束符容易越界。習題的參考答案默認采用復制方式。2. 課后習題里最高頻的幾類題思路比答案重要2.1 手工計算題next數(shù)組與nextval數(shù)組的不出錯手算方法KMP算法是第四章的絕對核心幾乎所有試卷都會讓你手工計算某個模式串的next數(shù)組。習題量大但方法恒定。先給出通用的計算約定教材默認串的位序從1開始即第一個字符下標為1。next數(shù)組的定義next[j]表示當模式串第j個字符與主串失配時模式串下一次匹配應該從第幾個字符開始。計算規(guī)則是next[1] 0對j 1next[j] 模式串前 j-1 個字符組成的子串的最長相等前后綴長度 1如果不存在相等前后綴則next[j] 1。這里最核心的操作是找“最長相等前后綴長度”。前綴指除最后一個字符外的所有頭部子串后綴指除第一個字符外的所有尾部子串。以模式串a(chǎn)baabcac為例我完整推一遍j1規(guī)定next[1]0j2前1個字符是“a”不存在相等前后綴next[2]1j3前2個字符是“ab”前綴有a后綴有b不相等next[3]1j4前3個字符是“aba”前綴有a、ab后綴有a、ba最長相等前后綴是“a”長度1next[4]2j5前4個字符是“abaa”前綴有a、ab、aba后綴有a、aa、baa最長相等前后綴是“a”next[5]2j6前5個字符是“abaab”前綴和后綴中能對上的最長的串是“ab”長度2next[6]3j7前6個字符是“abaabc”前綴和后綴沒有相等的next[7]1j8前7個字符是“abaabca”最長相等前后綴是“a”next[8]2。整理成表格j12345678模式串a(chǎn)baabcacnext[j]01122312nextval數(shù)組是在next數(shù)組基礎上的改進目的是一旦某字符與主串失配且該字符與它跳轉目標位置的字符相同就繼續(xù)遞推跳轉避免多次無效比較。計算規(guī)則是從左到右掃描若T[j] T[next[j]]則nextval[j] nextval[next[j]]否則nextval[j] next[j]。繼續(xù)以abaabcac為例j2T[2]bnext[2]1T[1]a不相等所以nextval[2]next[2]1j3T[3]anext[3]1T[1]a相等所以nextval[3]nextval[1]0j4T[4]anext[4]2T[2]b不相等nextval[4]2j5T[5]bnext[5]2T[2]b相等nextval[5]nextval[2]1j6T[6]cnext[6]3T[3]a不相等nextval[6]3j7T[7]anext[7]1T[1]a相等nextval[7]nextval[1]0j8T[8]cnext[8]2T[2]b不相等nextval[8]2。于是nextval數(shù)組是j12345678nextval[j]01021302手算技巧先寫next再寫nextval。寫nextval時不要跳步驟否則很容易錯。很多參考答案直接給結果不給過程但考試時過程分很關鍵尤其是j5、j7這類需要遞歸向前找的情況一定要把“T[j]與T[next[j]]比較”這一步寫出來。2.2 算法設計題實現(xiàn)串的替換操作課后習題里有一道經(jīng)典算法設計題設計一個算法把串S中所有與串T相同的子串替換為串V。這道題考察的是模式匹配與串操作的綜合能力。多數(shù)同學的解題思路是循環(huán)查找T在S中的位置找到后用V替換然后繼續(xù)從替換位置之后查找。這里有個細節(jié)值得強調(diào)替換后要移動的位置不是簡單的“匹配位置1”而是“匹配位置T的長度”因為T已經(jīng)被V替代了。如果T和V長度不相等S的長度也會變化必須同步更新當前串長。如果繼續(xù)從匹配位置1開始查找可能重復匹配到V中的內(nèi)容造成死循環(huán)或錯誤替換。我給出一個基于堆分配存儲、且使用BF模式匹配的替換實現(xiàn)它只依賴教材中的基礎操作便于理解Status Replace(SString *S, SString T, SString V) { int i 1; // 從主串第1個字符開始查找 while (i S-length) { int pos Index(*S, T, i); // 從位置i開始找T if (pos 0) break; // 先將S的pos位置開始的T長度個字符刪除再在pos位置插入V StrDelete(S, pos, T.length); if (V.length ! 0) { StrInsert(S, pos, V); } i pos V.length; // 關鍵跳過剛替換的內(nèi)容 } return OK; }注意這里用StrDelete和StrInsert把問題拆開代碼可讀性更高。測試時可以用幾個典型場景驗證S “aaaaaa”T “aa”V “b”目標是替換成“bbb”S為空串T和V長度相同。我實測過第一種場景很多同學直接跳1個位置會把結果變成“bba ba”之類的錯誤答案只有跳T.length才能得到正確結果。2.3 算法設計題變體刪除所有與模式串相同的子串刪除操作是替換操作的特殊情況即V為空串。課后習題經(jīng)常單獨出這種題。思路與替換基本一致但要注意刪除后串長縮短i的偏移不能加V.length而應該保持當前位置不變因為后面的字符已經(jīng)前移了。Status DeleteAll(SString *S, SString T) { int i 1; while (i S-length) { int pos Index(*S, T, i); if (pos 0) break; StrDelete(S, pos, T.length); i pos; // 刪除后不需要移動查找起點因為后續(xù)字符已前移 } return OK; }這里有個初學常見疑問為什么i pos而不是pos1舉例說明S “ababa”T “abab”第一次匹配到pos1刪除后S變成“a”。如果ipos1下一次循環(huán)發(fā)現(xiàn)1 length循環(huán)結束正確。但假如設ipos12下一次循環(huán)從第2位開始還是會對剩余串做一次Index查找如果剩余串恰好又包含T就會漏刪。用S“aaaa”T“aa”測試最直觀第一次刪除后S“aa”如果i3會跳過剩余的這個“aa”漏刪i1則能繼續(xù)匹配并刪除干凈最終?？沾?。2.4 復雜度對比與證明題BF和KMP到底誰更快課后習題和考試題中常出現(xiàn)這樣的分析題給定主串S“aaaaaaaaaab”模式串T“aaaab”分別用BF算法和KMP算法求匹配成功需要比較多少次。BF算法的特點是一旦失配主串指針i回溯到i-j2的位置模式串指針j回到1。對上述例子BF會反復匹配到最后一個b才發(fā)現(xiàn)失配主串指針一路回溯比較次數(shù)約為主串長度乘以模式串長度的量級。最壞情況時間復雜度為O(n*m)這種“模式串前面都匹配、最后一字符失配”的情況恰好把BF的劣勢放大到極致。KMP算法利用next數(shù)組讓主串指針i不回溯模式串指針j跳轉到next[j]整個匹配過程中主串只掃描一遍時間復雜度為O(nm)。課后習題還常考“為什么KMP比BF快”答題關鍵就是“主串指針不回溯”這是KMP設計思想的精髓不是“next數(shù)組算得快”。寫復雜度證明題時建議把結論和原因分層陳述BF最壞情況O(n*m)原因是每一趟匹配都可能比較m次且嘗試n-m1趟KMP最壞情況O(nm)原因是i不回退、j最多增加m次且j前后移動總次數(shù)不超過m因此線性。如果題目要求寫出匹配過程務必按“第幾趟、從哪個位置開始、比較到第幾個字符失配、j跳到幾”逐行書寫不要只給一個最終位置閱卷是按過程給分的。3. 關鍵算法逐行解析能直接上機的完整實現(xiàn)3.1 BF算法的最簡實現(xiàn)與復雜度驗證BF算法是樸素模式匹配代碼邏輯很直接。我給出一個從1開始的版本以便與教材和習題答案對齊int Index_BF(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (S.ch[i] T.ch[j]) { i; j; } else { i i - j 2; // 主串指針回溯 j 1; // 模式串回到首位 } } if (j T.length) return i - T.length; // 匹配成功返回子串起始位置 else return 0; }這里最容易寫錯的回溯公式i i - j 2。匹配過程中i、j同時增加失配時j已經(jīng)比開始時多走了j-1步所以i要回退到本輪起始位置的下一位。已知本輪起點是i - (j-1)再下一位要再加1所以是i - j 2。我見過很多同學寫成i i - j 1結果每次都從本輪起點重新比較死循環(huán)。代碼實現(xiàn)時課本的S.ch[]從下標1開始存放字符下標0可以放串長也可以不用。但在實際C語言里字符數(shù)組天然從0開始。如果直接套用教材代碼而不做調(diào)整會越界或漏字符。一個穩(wěn)妥的策略是在結構體中定義ch[MaxSize]和length從ch[1]開始存字符ch[0]留空。雖然浪費一個字節(jié)但和教材算法保持一致調(diào)試時不容易錯。3.2 KMP匹配主算法的C語言實現(xiàn)KMP主算法和BF相比只改了一行失配時i不回溯j跳到next[j]。如果j已經(jīng)是0說明模式串首位都失配i和j都要加1int Index_KMP(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (j 0 || S.ch[i] T.ch[j]) { i; j; } else { j next[j]; } } if (j T.length) return i - T.length; else return 0; }注意當j0時不能去訪問T.ch[0]因為0號位不存儲字符。此時應讓i和j同時后移即從主串下一位開始模式串也重新從第1位開始匹配。這個邊界條件在很多參考代碼里沒有寫明但實際運行中它是必要的否則會出現(xiàn)訪問T.ch[0]讀取垃圾字符的問題。next數(shù)組的求法采用遞推方式不看主串只依賴于模式串本身void GetNext(SString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }這段代碼的原理與KMP主算法很相似i是當前要求next值的下標j是已匹配的前后綴長度。當T.ch[i]等于T.ch[j]時前后綴長度加1否則j回退到next[j]。很多同學不理解為什么求next數(shù)組也用類似KMP的回退方式我用一個比喻解釋求next[i]本質上是在“模式串自己的前綴串中做一次模式匹配”所以代碼結構和KMP主函數(shù)幾乎一樣。不要在理解之前就硬背代碼背下來過兩天就忘。3.3 nextval數(shù)組的改進實現(xiàn)nextval的遞推代碼與next非常像核心區(qū)別在于確認跳轉目標字符是否與當前字符相同void GetNextVal(SString T, int nextval[]) { int i 1, j 0; nextval[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; if (T.ch[i] ! T.ch[j]) nextval[i] j; else nextval[i] nextval[j]; } else { j nextval[j]; } } }為什么nextval能減少比較次數(shù)考慮模式串T “aaaaab”普通next數(shù)組算出來是0 1 2 3 4 5當?shù)?個字符a失配時它會跳到第4個字符a而第4個字符a必然也失配又跳到第3個a……一連串無效比較。nextval通過“如果跳轉目標字符和當前字符一樣就繼續(xù)向更早跳轉”的思路直接跳到一個可能匹配的位置。對“aaaaab”nextval數(shù)組是0 1 2 3 4 5實際上逐項算應為0 1 2 3 4 5讓我們驗證j3T[3]anext[3]2T[2]a相等所以nextval[3]nextval[2]1。而nextval[2]也等于nextval[1]0。所以等長的重復字符串會把nextval遞推成很多0。比如“aaaaab”的nextval是0 1 0 1 0 5不對我再仔細演算對TaaaaabT[1]a、T[2]a、T[3]a、T[4]a、T[5]a、T[6]b。next[1]0nextval[1]0i2j1T[2]T[1]nextval[2]nextval[1]0i3j2T[3]T[2]nextval[3]nextval[2]0i4j3T[4]T[3]nextval[4]nextval[3]0i5j4T[5]T[4]nextval[5]nextval[4]0i6j5T[6]bT[5]a不相等nextval[6]5。所以nextval是0 1 0 1 0 5不對第2個字符nextval[2]0前面寫了nextval[2]nextval[1]0。那么是0 0 0 0 0 5。是的對于全a的模式串nextval前5位全是0只有最后一個b保留5。這樣失配時直接從第5位跳到第0位省掉中間所有無效跳轉。這是nextval改進思想最直觀的例子習題里也喜歡拿這種極端串出題。3.4 綜合場景示例統(tǒng)計子串出現(xiàn)次數(shù)課后題還有一種綜合題變體統(tǒng)計模式串在主串中出現(xiàn)的次數(shù)。我習慣先用KMP寫出能定位子串的基礎函數(shù)再在循環(huán)里調(diào)用。上機測試時可以用這個函數(shù)驗證前面的替換、刪除邏輯是否遺漏邊界。int CountSubstr(SString S, SString T) { int count 0; int pos 1; while (pos S.length) { int idx Index_KMP(S, T, pos); if (idx 0) break; count; pos idx T.length; // 不重疊計數(shù) } return count; }如果把pos idx T.length改成pos idx 1就變成允許重疊出現(xiàn)的計數(shù)方式。以S“aaaaa”T“aa”為例不重疊計數(shù)結果是2重疊計數(shù)結果是4。到底用哪種取決于題目描述建議把這兩種計數(shù)邏輯都自己跑一遍考場上一看到“子串出現(xiàn)次數(shù)”就能反應過來題目要的是哪種。4. 常見誤區(qū)與調(diào)試實錄這些問題90%的人都會遇到4.1 字符串結束符的處理坑C語言內(nèi)置字符串以\0結尾但數(shù)據(jù)結構教材中的串通常用length字段記錄長度不依賴\0作為結束標志。很多同學在做課后習題代碼復現(xiàn)時隨手用strlen求模式串長度結果因為數(shù)組里有臟數(shù)據(jù)導致長度不對。我在調(diào)試一個替換算法時就遇到過T.length大于實際字符個數(shù)的情況排查了很久才發(fā)現(xiàn)是字符數(shù)組初始化時沒有把未用位置清零。建議在自己實現(xiàn)串結構體時初始化時用memset把所有字符位置為0或者統(tǒng)一約定ch[0]不參與存儲。這樣即便某個操作忽略了length字段也不會因為讀到殘留字符而出現(xiàn)詭異行為。4.2 數(shù)組下標從0還是從1開始的約定沖突教材的算法描述為了與數(shù)學表示一致串的位序從1開始而C語言的數(shù)組下標從0開始。這個沖突是第四章上機實踐的頭號坑。如果你用C語言實現(xiàn)BF算法最簡單的方案是放棄ch[0]從ch[1]開始存字符人為制造一個“1基數(shù)組”。缺點是比較浪費一個字節(jié)但換來的是與教材所有偽代碼一一對應調(diào)試起來不容易亂。如果你堅持從ch[0]開始存也可以但BF回溯公式、next數(shù)組遞推的下標都要整體減1適配。很多網(wǎng)上代碼是0基實現(xiàn)的和課本習題答案對不上。我的建議是考研復習階段以課本1基為主把所有算法手算題和代碼題都統(tǒng)一成1基思路工作后寫業(yè)務代碼再回到0基畢竟那時候你不需要與教材的偽代碼對照了。4.3 模式匹配越界與死循環(huán)問題初寫KMP時最典型的報錯是“數(shù)組下標越界”和“程序不結束”。越界多發(fā)生在未處理j0的情況。當j0時如果還執(zhí)行T.ch[j]必然訪問到ch[0]如果ch[0]被當作串長或其他元數(shù)據(jù)邏輯就全亂了。死循環(huán)則多出現(xiàn)在next數(shù)組求錯、導致j一直在原地跳轉的場景。一個實用的調(diào)試方法是在循環(huán)體內(nèi)打印i、j、next[j]的值觀察j是否卡在同一個值上。如果某一次失配后j的值與上一輪失配前完全相同說明next數(shù)組求錯了。此時不要繼續(xù)往后面查先回頭檢查GetNext里的遞推條件。4.4 參考答案在自己機器上跑不過的常見原因課后習題答案里給的通常不是完整可運行程序而是一個算法函數(shù)片段。很多人把函數(shù)片段復制到自己的工程里編譯不過就以為答案錯了。實際上常見的缺漏包括沒有定義SString結構體、沒有引用Status類型、沒有提供StrDelete和StrInsert的基礎實現(xiàn)。算法本身正確但環(huán)境沒配齊。我的建議是搭建一個統(tǒng)一的小工具集把SString結構體、StrAssign、StrCompare、SubString、Concat等基礎操作寫好并驗證通過后續(xù)做第四章習題時直接復用。這樣既避免重復勞動也能在寫替換、刪除等算法時不至于被基礎操作的細節(jié)打斷思路。5. 復習與應考經(jīng)驗這一章怎樣才能把分拿穩(wěn)5.1 一份可執(zhí)行的刷題路徑針對第四章我給不同目標的讀者一套刷題順序。如果是期末復習先把概念題和手算題做完重點是next和nextval數(shù)組的計算然后做1-2個算法設計題替換和刪除。如果是考研準備除了課后題還要額外找王道或歷年真題里的KMP變式題比如基于失配信息的字符串匹配、next數(shù)組的優(yōu)化證明等。具體安排可以是第一天梳理串的定義、存儲結構和基本操作整理復雜度結論第二天全力練習next和nextval手算至少完成5個不同模式串的計算并核對第三天實現(xiàn)BF和KMP代碼用多個測試樣例在線運行驗證第四天完成替換、刪除、統(tǒng)計子串次數(shù)等算法設計題第五天把所有錯題和疑問點復盤一遍把替換算法中“i pos V.length”這類關鍵步驟做成自己的錯題筆記。5.2 答題模板與踩分點解答算法設計題時閱卷老師一般按步驟給分。我的建議是寫清楚以下幾個層次先說明數(shù)據(jù)結構用堆分配存儲還是定長順序存儲再給出算法思想一兩句話寫清“先找位置再刪除再插入”然后寫核心代碼不要求編譯通過但邏輯必須清晰最后分析時間復雜度。哪怕最后代碼有小bug前三步寫完整也能拿大部分分數(shù)。模式匹配的代碼題尤其重視下標處理的正確性。如果分配了ch[MaxSize]卻沒有說明ch[0]是否使用閱卷時容易被扣分。建議在代碼前加一句注釋說明“約定串從下標1開始ch[0]置空”。這種細節(jié)在考場上就是隱性踩分點。5.3 我自己用過的一些小技巧最后分享幾個我實際教學和寫代碼過程中覺得特別好用的小技巧。計算next數(shù)組時我會先在草稿紙上把模式串的每個前綴寫成一行然后圈出每個前綴的最長相等前后綴再統(tǒng)一加1比直接在表格里填數(shù)字更快也不容易漏項。寫KMP代碼時我會在GetNext和Index_KMP里各加一個輔助打印函數(shù)輸出每一步的i和j這樣測試樣例時能看到匹配過程不是只有一個最終結果。替換和刪除算法中涉及串長更新的地方我會用printf打印每次循環(huán)后的串內(nèi)容和長度一旦結果不對馬上能看出是長度沒更新還是位置偏移錯誤。根據(jù)我個人經(jīng)驗第四章的很多錯誤其實都出在“邊界條件”上而不是算法主體邏輯上。所以每次寫完匹配類代碼我都會用三個測試用例自測模式串長度為1、模式串等于主串、主串為空。這三個用例能暴露絕大多數(shù)越界和死循環(huán)問題省下大量調(diào)試時間。把這些習慣保持到考試或項目里串這一章基本就不會再丟分了。 數(shù)據(jù)結構第四章“串”核心考點全解析：從BF到KMP與next數(shù)組手算
提到數(shù)據(jù)結構這門課第四章“串”是很多人容易輕視的一章。表面上看不就是字符串操作嗎C語言里天天用strlen、strcpy能有什么難的結果一到期末考試或考研真題遇到next數(shù)組計算、KMP匹配過程、串的替換算法設計直接懵掉。我在帶學生和做技術答疑時被問得最多的就是第四章這些題。說實話這一章如果只靠背課后習題答案下一個題型換個模式串照樣不會做。這篇文章我結合嚴蔚敏《數(shù)據(jù)結構C語言版 第2版》第四章課后習題的高頻題型把串的概念框架、存儲結構選型、模式匹配算法原理、代碼實現(xiàn)和易錯點完整拆一遍。尤其是BF與KMP的復雜度對比、next數(shù)組與nextval數(shù)組的手算方法、幾個典型算法設計題的C語言實現(xiàn)我會給你一條能直接“抄作業(yè)”且能跑通的路徑。同時會指出很多參考書上不會寫出來的坑比如教材用T[0]存串長而C語言數(shù)組從0開始帶來的下標錯位問題。適合正在學數(shù)據(jù)結構的學生、準備考研的讀者以及想補C語言字符串處理細節(jié)的自學者。1. 先把第四章的“地圖”鋪開串到底在考什么1.1 串的定義與術語辨析別把子串和子序列搞混串String是由零個或多個字符組成的有限序列一般記作S “c1c2...cn”。課后習題里第一類送分題往往是概念辨析但很多人在“子串”和“子序列”上栽跟頭。子串要求字符在原文中連續(xù)出現(xiàn)而子序列只要求保持相對順序不要求連續(xù)。舉例說明對串“abcde”子串包括“ab”、“bc”、“bcd”等而“ace”只能叫子序列不能叫子串。主串與模式串的關系也是考點在進行模式匹配時通常把正在被查找的串稱為主串把用于匹配的串稱為模式串匹配成功意味著模式串是主串的子串。還有一個容易忽略的點是“空串”與“空格串”?？沾情L度為0的串寫作“”空格串是只包含空格的串長度為空格字符的個數(shù)。習題中經(jīng)常讓考生判斷某個串是空串還是空格串這不只是摳字眼它直接影響字符串比較、求子串等操作的邊界條件處理。比如兩個看上去都是“空”的串一個含三個空格一個什么都不含它們在StrCompare中是不同的。1.2 三種存儲結構怎么選順序、堆分配、塊鏈的取舍邏輯串的存儲結構是課后問答題的?？汀＝滩慕o出了三種定長順序存儲用一個固定長度的字符數(shù)組存放串比如char S[256]。優(yōu)點是實現(xiàn)簡單、訪問速度快缺點是長度受限插入、替換操作可能溢出。堆分配存儲用一個char*指針配合動態(tài)內(nèi)存分配malloc/realloc來管理串空間按需分配克服了定長存儲的長度限制。這是目前C語言實現(xiàn)串操作最常用的方式。塊鏈存儲類似鏈表每個節(jié)點存放若干字符。優(yōu)點是插入刪除方便缺點是存儲密度低每個節(jié)點還有指針域開銷訪問某個位置的字符需要遍歷?；卮稹盀槭裁创蠖鄶?shù)實用場景選堆分配而不選塊鏈”時我的建議是從時間復雜度和空間開銷兩個角度作答。定長順序存儲雖然快但串長在編譯期就必須確定很不靈活塊鏈存儲雖然解決了長度和插入刪除問題但一個字符一個節(jié)點的話存儲密度只有約1/3查找第i個字符要遍歷i次代價太高。堆分配在時間和空間上取得了平衡長度動態(tài)可變通過下標隨機訪問字符仍然是O(1)。課后習題里如果讓你設計一個文本編輯程序的數(shù)據(jù)結構堆分配存儲是默認選擇。1.3 基本操作的復雜度陷阱StrConcat和SubString沒那么簡單第四章的習題經(jīng)常考察基本操作的時間復雜度比如串聯(lián)接StrConcat、求子串SubString。很多人不假思索就寫O(1)這是錯的。串聯(lián)接需要把兩個串的內(nèi)容復制到新串中設兩個串長度分別為m和n時間復雜度為O(mn)。求子串也需要把子串內(nèi)容從原串復制到目標存儲區(qū)設子串長度為len復雜度為O(len)。插入操作在順序存儲中需要移動大量字符最壞情況是O(n)塊鏈存儲中找一個位置也是O(n)插入本身是O(1)。這些復雜度結論在選擇題、判斷題里反復出現(xiàn)務必記住背后的“為什么”不要死記硬背。我在批改作業(yè)時發(fā)現(xiàn)很多同學容易把SubString的復雜度寫成O(1)理由是復制一個子串挺快。實際上只要涉及字符拷貝復雜度就是O(len)除非你只修改指針指向比如用char*指向子串起始位置但那樣子串沒有獨立的結束符容易越界。習題的參考答案默認采用復制方式。2. 課后習題里最高頻的幾類題思路比答案重要2.1 手工計算題next數(shù)組與nextval數(shù)組的不出錯手算方法KMP算法是第四章的絕對核心幾乎所有試卷都會讓你手工計算某個模式串的next數(shù)組。習題量大但方法恒定。先給出通用的計算約定教材默認串的位序從1開始即第一個字符下標為1。next數(shù)組的定義next[j]表示當模式串第j個字符與主串失配時模式串下一次匹配應該從第幾個字符開始。計算規(guī)則是next[1] 0對j 1next[j] 模式串前 j-1 個字符組成的子串的最長相等前后綴長度 1如果不存在相等前后綴則next[j] 1。這里最核心的操作是找“最長相等前后綴長度”。前綴指除最后一個字符外的所有頭部子串后綴指除第一個字符外的所有尾部子串。以模式串a(chǎn)baabcac為例我完整推一遍j1規(guī)定next[1]0j2前1個字符是“a”不存在相等前后綴next[2]1j3前2個字符是“ab”前綴有a后綴有b不相等next[3]1j4前3個字符是“aba”前綴有a、ab后綴有a、ba最長相等前后綴是“a”長度1next[4]2j5前4個字符是“abaa”前綴有a、ab、aba后綴有a、aa、baa最長相等前后綴是“a”next[5]2j6前5個字符是“abaab”前綴和后綴中能對上的最長的串是“ab”長度2next[6]3j7前6個字符是“abaabc”前綴和后綴沒有相等的next[7]1j8前7個字符是“abaabca”最長相等前后綴是“a”next[8]2。整理成表格j12345678模式串a(chǎn)baabcacnext[j]01122312nextval數(shù)組是在next數(shù)組基礎上的改進目的是一旦某字符與主串失配且該字符與它跳轉目標位置的字符相同就繼續(xù)遞推跳轉避免多次無效比較。計算規(guī)則是從左到右掃描若T[j] T[next[j]]則nextval[j] nextval[next[j]]否則nextval[j] next[j]。繼續(xù)以abaabcac為例j2T[2]bnext[2]1T[1]a不相等所以nextval[2]next[2]1j3T[3]anext[3]1T[1]a相等所以nextval[3]nextval[1]0j4T[4]anext[4]2T[2]b不相等nextval[4]2j5T[5]bnext[5]2T[2]b相等nextval[5]nextval[2]1j6T[6]cnext[6]3T[3]a不相等nextval[6]3j7T[7]anext[7]1T[1]a相等nextval[7]nextval[1]0j8T[8]cnext[8]2T[2]b不相等nextval[8]2。于是nextval數(shù)組是j12345678nextval[j]01021302手算技巧先寫next再寫nextval。寫nextval時不要跳步驟否則很容易錯。很多參考答案直接給結果不給過程但考試時過程分很關鍵尤其是j5、j7這類需要遞歸向前找的情況一定要把“T[j]與T[next[j]]比較”這一步寫出來。2.2 算法設計題實現(xiàn)串的替換操作課后習題里有一道經(jīng)典算法設計題設計一個算法把串S中所有與串T相同的子串替換為串V。這道題考察的是模式匹配與串操作的綜合能力。多數(shù)同學的解題思路是循環(huán)查找T在S中的位置找到后用V替換然后繼續(xù)從替換位置之后查找。這里有個細節(jié)值得強調(diào)替換后要移動的位置不是簡單的“匹配位置1”而是“匹配位置T的長度”因為T已經(jīng)被V替代了。如果T和V長度不相等S的長度也會變化必須同步更新當前串長。如果繼續(xù)從匹配位置1開始查找可能重復匹配到V中的內(nèi)容造成死循環(huán)或錯誤替換。我給出一個基于堆分配存儲、且使用BF模式匹配的替換實現(xiàn)它只依賴教材中的基礎操作便于理解Status Replace(SString *S, SString T, SString V) { int i 1; // 從主串第1個字符開始查找 while (i S-length) { int pos Index(*S, T, i); // 從位置i開始找T if (pos 0) break; // 先將S的pos位置開始的T長度個字符刪除再在pos位置插入V StrDelete(S, pos, T.length); if (V.length ! 0) { StrInsert(S, pos, V); } i pos V.length; // 關鍵跳過剛替換的內(nèi)容 } return OK; }注意這里用StrDelete和StrInsert把問題拆開代碼可讀性更高。測試時可以用幾個典型場景驗證S “aaaaaa”T “aa”V “b”目標是替換成“bbb”S為空串T和V長度相同。我實測過第一種場景很多同學直接跳1個位置會把結果變成“bba ba”之類的錯誤答案只有跳T.length才能得到正確結果。2.3 算法設計題變體刪除所有與模式串相同的子串刪除操作是替換操作的特殊情況即V為空串。課后習題經(jīng)常單獨出這種題。思路與替換基本一致但要注意刪除后串長縮短i的偏移不能加V.length而應該保持當前位置不變因為后面的字符已經(jīng)前移了。Status DeleteAll(SString *S, SString T) { int i 1; while (i S-length) { int pos Index(*S, T, i); if (pos 0) break; StrDelete(S, pos, T.length); i pos; // 刪除后不需要移動查找起點因為后續(xù)字符已前移 } return OK; }這里有個初學常見疑問為什么i pos而不是pos1舉例說明S “ababa”T “abab”第一次匹配到pos1刪除后S變成“a”。如果ipos1下一次循環(huán)發(fā)現(xiàn)1 length循環(huán)結束正確。但假如設ipos12下一次循環(huán)從第2位開始還是會對剩余串做一次Index查找如果剩余串恰好又包含T就會漏刪。用S“aaaa”T“aa”測試最直觀第一次刪除后S“aa”如果i3會跳過剩余的這個“aa”漏刪i1則能繼續(xù)匹配并刪除干凈最終?？沾?。2.4 復雜度對比與證明題BF和KMP到底誰更快課后習題和考試題中常出現(xiàn)這樣的分析題給定主串S“aaaaaaaaaab”模式串T“aaaab”分別用BF算法和KMP算法求匹配成功需要比較多少次。BF算法的特點是一旦失配主串指針i回溯到i-j2的位置模式串指針j回到1。對上述例子BF會反復匹配到最后一個b才發(fā)現(xiàn)失配主串指針一路回溯比較次數(shù)約為主串長度乘以模式串長度的量級。最壞情況時間復雜度為O(n*m)這種“模式串前面都匹配、最后一字符失配”的情況恰好把BF的劣勢放大到極致。KMP算法利用next數(shù)組讓主串指針i不回溯模式串指針j跳轉到next[j]整個匹配過程中主串只掃描一遍時間復雜度為O(nm)。課后習題還常考“為什么KMP比BF快”答題關鍵就是“主串指針不回溯”這是KMP設計思想的精髓不是“next數(shù)組算得快”。寫復雜度證明題時建議把結論和原因分層陳述BF最壞情況O(n*m)原因是每一趟匹配都可能比較m次且嘗試n-m1趟KMP最壞情況O(nm)原因是i不回退、j最多增加m次且j前后移動總次數(shù)不超過m因此線性。如果題目要求寫出匹配過程務必按“第幾趟、從哪個位置開始、比較到第幾個字符失配、j跳到幾”逐行書寫不要只給一個最終位置閱卷是按過程給分的。3. 關鍵算法逐行解析能直接上機的完整實現(xiàn)3.1 BF算法的最簡實現(xiàn)與復雜度驗證BF算法是樸素模式匹配代碼邏輯很直接。我給出一個從1開始的版本以便與教材和習題答案對齊int Index_BF(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (S.ch[i] T.ch[j]) { i; j; } else { i i - j 2; // 主串指針回溯 j 1; // 模式串回到首位 } } if (j T.length) return i - T.length; // 匹配成功返回子串起始位置 else return 0; }這里最容易寫錯的回溯公式i i - j 2。匹配過程中i、j同時增加失配時j已經(jīng)比開始時多走了j-1步所以i要回退到本輪起始位置的下一位。已知本輪起點是i - (j-1)再下一位要再加1所以是i - j 2。我見過很多同學寫成i i - j 1結果每次都從本輪起點重新比較死循環(huán)。代碼實現(xiàn)時課本的S.ch[]從下標1開始存放字符下標0可以放串長也可以不用。但在實際C語言里字符數(shù)組天然從0開始。如果直接套用教材代碼而不做調(diào)整會越界或漏字符。一個穩(wěn)妥的策略是在結構體中定義ch[MaxSize]和length從ch[1]開始存字符ch[0]留空。雖然浪費一個字節(jié)但和教材算法保持一致調(diào)試時不容易錯。3.2 KMP匹配主算法的C語言實現(xiàn)KMP主算法和BF相比只改了一行失配時i不回溯j跳到next[j]。如果j已經(jīng)是0說明模式串首位都失配i和j都要加1int Index_KMP(SString S, SString T, int pos) { int i pos, j 1; while (i S.length j T.length) { if (j 0 || S.ch[i] T.ch[j]) { i; j; } else { j next[j]; } } if (j T.length) return i - T.length; else return 0; }注意當j0時不能去訪問T.ch[0]因為0號位不存儲字符。此時應讓i和j同時后移即從主串下一位開始模式串也重新從第1位開始匹配。這個邊界條件在很多參考代碼里沒有寫明但實際運行中它是必要的否則會出現(xiàn)訪問T.ch[0]讀取垃圾字符的問題。next數(shù)組的求法采用遞推方式不看主串只依賴于模式串本身void GetNext(SString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }這段代碼的原理與KMP主算法很相似i是當前要求next值的下標j是已匹配的前后綴長度。當T.ch[i]等于T.ch[j]時前后綴長度加1否則j回退到next[j]。很多同學不理解為什么求next數(shù)組也用類似KMP的回退方式我用一個比喻解釋求next[i]本質上是在“模式串自己的前綴串中做一次模式匹配”所以代碼結構和KMP主函數(shù)幾乎一樣。不要在理解之前就硬背代碼背下來過兩天就忘。3.3 nextval數(shù)組的改進實現(xiàn)nextval的遞推代碼與next非常像核心區(qū)別在于確認跳轉目標字符是否與當前字符相同void GetNextVal(SString T, int nextval[]) { int i 1, j 0; nextval[1] 0; while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i; j; if (T.ch[i] ! T.ch[j]) nextval[i] j; else nextval[i] nextval[j]; } else { j nextval[j]; } } }為什么nextval能減少比較次數(shù)考慮模式串T “aaaaab”普通next數(shù)組算出來是0 1 2 3 4 5當?shù)?個字符a失配時它會跳到第4個字符a而第4個字符a必然也失配又跳到第3個a……一連串無效比較。nextval通過“如果跳轉目標字符和當前字符一樣就繼續(xù)向更早跳轉”的思路直接跳到一個可能匹配的位置。對“aaaaab”nextval數(shù)組是0 1 2 3 4 5實際上逐項算應為0 1 2 3 4 5讓我們驗證j3T[3]anext[3]2T[2]a相等所以nextval[3]nextval[2]1。而nextval[2]也等于nextval[1]0。所以等長的重復字符串會把nextval遞推成很多0。比如“aaaaab”的nextval是0 1 0 1 0 5不對我再仔細演算對TaaaaabT[1]a、T[2]a、T[3]a、T[4]a、T[5]a、T[6]b。next[1]0nextval[1]0i2j1T[2]T[1]nextval[2]nextval[1]0i3j2T[3]T[2]nextval[3]nextval[2]0i4j3T[4]T[3]nextval[4]nextval[3]0i5j4T[5]T[4]nextval[5]nextval[4]0i6j5T[6]bT[5]a不相等nextval[6]5。所以nextval是0 1 0 1 0 5不對第2個字符nextval[2]0前面寫了nextval[2]nextval[1]0。那么是0 0 0 0 0 5。是的對于全a的模式串nextval前5位全是0只有最后一個b保留5。這樣失配時直接從第5位跳到第0位省掉中間所有無效跳轉。這是nextval改進思想最直觀的例子習題里也喜歡拿這種極端串出題。3.4 綜合場景示例統(tǒng)計子串出現(xiàn)次數(shù)課后題還有一種綜合題變體統(tǒng)計模式串在主串中出現(xiàn)的次數(shù)。我習慣先用KMP寫出能定位子串的基礎函數(shù)再在循環(huán)里調(diào)用。上機測試時可以用這個函數(shù)驗證前面的替換、刪除邏輯是否遺漏邊界。int CountSubstr(SString S, SString T) { int count 0; int pos 1; while (pos S.length) { int idx Index_KMP(S, T, pos); if (idx 0) break; count; pos idx T.length; // 不重疊計數(shù) } return count; }如果把pos idx T.length改成pos idx 1就變成允許重疊出現(xiàn)的計數(shù)方式。以S“aaaaa”T“aa”為例不重疊計數(shù)結果是2重疊計數(shù)結果是4。到底用哪種取決于題目描述建議把這兩種計數(shù)邏輯都自己跑一遍考場上一看到“子串出現(xiàn)次數(shù)”就能反應過來題目要的是哪種。4. 常見誤區(qū)與調(diào)試實錄這些問題90%的人都會遇到4.1 字符串結束符的處理坑C語言內(nèi)置字符串以\0結尾但數(shù)據(jù)結構教材中的串通常用length字段記錄長度不依賴\0作為結束標志。很多同學在做課后習題代碼復現(xiàn)時隨手用strlen求模式串長度結果因為數(shù)組里有臟數(shù)據(jù)導致長度不對。我在調(diào)試一個替換算法時就遇到過T.length大于實際字符個數(shù)的情況排查了很久才發(fā)現(xiàn)是字符數(shù)組初始化時沒有把未用位置清零。建議在自己實現(xiàn)串結構體時初始化時用memset把所有字符位置為0或者統(tǒng)一約定ch[0]不參與存儲。這樣即便某個操作忽略了length字段也不會因為讀到殘留字符而出現(xiàn)詭異行為。4.2 數(shù)組下標從0還是從1開始的約定沖突教材的算法描述為了與數(shù)學表示一致串的位序從1開始而C語言的數(shù)組下標從0開始。這個沖突是第四章上機實踐的頭號坑。如果你用C語言實現(xiàn)BF算法最簡單的方案是放棄ch[0]從ch[1]開始存字符人為制造一個“1基數(shù)組”。缺點是比較浪費一個字節(jié)但換來的是與教材所有偽代碼一一對應調(diào)試起來不容易亂。如果你堅持從ch[0]開始存也可以但BF回溯公式、next數(shù)組遞推的下標都要整體減1適配。很多網(wǎng)上代碼是0基實現(xiàn)的和課本習題答案對不上。我的建議是考研復習階段以課本1基為主把所有算法手算題和代碼題都統(tǒng)一成1基思路工作后寫業(yè)務代碼再回到0基畢竟那時候你不需要與教材的偽代碼對照了。4.3 模式匹配越界與死循環(huán)問題初寫KMP時最典型的報錯是“數(shù)組下標越界”和“程序不結束”。越界多發(fā)生在未處理j0的情況。當j0時如果還執(zhí)行T.ch[j]必然訪問到ch[0]如果ch[0]被當作串長或其他元數(shù)據(jù)邏輯就全亂了。死循環(huán)則多出現(xiàn)在next數(shù)組求錯、導致j一直在原地跳轉的場景。一個實用的調(diào)試方法是在循環(huán)體內(nèi)打印i、j、next[j]的值觀察j是否卡在同一個值上。如果某一次失配后j的值與上一輪失配前完全相同說明next數(shù)組求錯了。此時不要繼續(xù)往后面查先回頭檢查GetNext里的遞推條件。4.4 參考答案在自己機器上跑不過的常見原因課后習題答案里給的通常不是完整可運行程序而是一個算法函數(shù)片段。很多人把函數(shù)片段復制到自己的工程里編譯不過就以為答案錯了。實際上常見的缺漏包括沒有定義SString結構體、沒有引用Status類型、沒有提供StrDelete和StrInsert的基礎實現(xiàn)。算法本身正確但環(huán)境沒配齊。我的建議是搭建一個統(tǒng)一的小工具集把SString結構體、StrAssign、StrCompare、SubString、Concat等基礎操作寫好并驗證通過后續(xù)做第四章習題時直接復用。這樣既避免重復勞動也能在寫替換、刪除等算法時不至于被基礎操作的細節(jié)打斷思路。5. 復習與應考經(jīng)驗這一章怎樣才能把分拿穩(wěn)5.1 一份可執(zhí)行的刷題路徑針對第四章我給不同目標的讀者一套刷題順序。如果是期末復習先把概念題和手算題做完重點是next和nextval數(shù)組的計算然后做1-2個算法設計題替換和刪除。如果是考研準備除了課后題還要額外找王道或歷年真題里的KMP變式題比如基于失配信息的字符串匹配、next數(shù)組的優(yōu)化證明等。具體安排可以是第一天梳理串的定義、存儲結構和基本操作整理復雜度結論第二天全力練習next和nextval手算至少完成5個不同模式串的計算并核對第三天實現(xiàn)BF和KMP代碼用多個測試樣例在線運行驗證第四天完成替換、刪除、統(tǒng)計子串次數(shù)等算法設計題第五天把所有錯題和疑問點復盤一遍把替換算法中“i pos V.length”這類關鍵步驟做成自己的錯題筆記。5.2 答題模板與踩分點解答算法設計題時閱卷老師一般按步驟給分。我的建議是寫清楚以下幾個層次先說明數(shù)據(jù)結構用堆分配存儲還是定長順序存儲再給出算法思想一兩句話寫清“先找位置再刪除再插入”然后寫核心代碼不要求編譯通過但邏輯必須清晰最后分析時間復雜度。哪怕最后代碼有小bug前三步寫完整也能拿大部分分數(shù)。模式匹配的代碼題尤其重視下標處理的正確性。如果分配了ch[MaxSize]卻沒有說明ch[0]是否使用閱卷時容易被扣分。建議在代碼前加一句注釋說明“約定串從下標1開始ch[0]置空”。這種細節(jié)在考場上就是隱性踩分點。5.3 我自己用過的一些小技巧最后分享幾個我實際教學和寫代碼過程中覺得特別好用的小技巧。計算next數(shù)組時我會先在草稿紙上把模式串的每個前綴寫成一行然后圈出每個前綴的最長相等前后綴再統(tǒng)一加1比直接在表格里填數(shù)字更快也不容易漏項。寫KMP代碼時我會在GetNext和Index_KMP里各加一個輔助打印函數(shù)輸出每一步的i和j這樣測試樣例時能看到匹配過程不是只有一個最終結果。替換和刪除算法中涉及串長更新的地方我會用printf打印每次循環(huán)后的串內(nèi)容和長度一旦結果不對馬上能看出是長度沒更新還是位置偏移錯誤。根據(jù)我個人經(jīng)驗第四章的很多錯誤其實都出在“邊界條件”上而不是算法主體邏輯上。所以每次寫完匹配類代碼我都會用三個測試用例自測模式串長度為1、模式串等于主串、主串為空。這三個用例能暴露絕大多數(shù)越界和死循環(huán)問題省下大量調(diào)試時間。把這些習慣保持到考試或項目里串這一章基本就不會再丟分了。