數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第4章ppt課件.ppt

第四章串 課前思考 從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來(lái)說 串是一種特殊的線性表 但就數(shù)據(jù)類型而言 串不是線性表 希望你帶著這個(gè)問題開始這一章的學(xué)習(xí) 并能在學(xué)完這一章的內(nèi)容之后能得出正確的結(jié)論 學(xué)習(xí)目標(biāo) 1 理解 串 類型定義中各基本操作的特點(diǎn) 并能正確利用它們進(jìn)行串的其它操作 2 理解串類型的各種存儲(chǔ)表示方法 3 理解串匹配的各種算法 重點(diǎn)和難點(diǎn) 相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言 本章非整個(gè)課程的重點(diǎn) 鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型 因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法 并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作 本章的難點(diǎn)是理解實(shí)現(xiàn)串匹配的KMP算法的思想 但它不屬本章學(xué)習(xí)的基本要求 更不是重點(diǎn)學(xué)習(xí)內(nèi)容 知識(shí)點(diǎn) 串的類型定義 串的存儲(chǔ)表示 串匹配 KMP算法 學(xué)習(xí)指南 雖然目前各常用的高級(jí)語(yǔ)言中都已經(jīng)實(shí)現(xiàn)了串類型 但由于它是通過軟件實(shí)現(xiàn)的 因此作為一個(gè)軟件工作者還是應(yīng)該了解串的實(shí)現(xiàn)方法 本章沒有必須完成的算法設(shè)計(jì)題 如果有興趣可以試試以下幾個(gè)題 4 10 4 11 4 13 4 17 4 18 4 23 4 28 4 30 其中前6個(gè)是練習(xí)串的基本操作的應(yīng)用 后2個(gè)是和KMP算法相關(guān)的練習(xí) 4 1串類型的定義 4 2串的表示和實(shí)現(xiàn) 4 3串的模式匹配算法 4 1串的類型定義 一 基本概念 1 串的定義串 string 是由零個(gè)或多個(gè)字符組成的有限序列 記作s a1a2 an 其中s為串的名字 用成對(duì)的單引號(hào)括起來(lái)的字符序列為串的值 但兩邊的引號(hào)不算串值 不包含在串中 ai 1 i n 可以是字母 數(shù)字或其它字符 n為串中字符的個(gè)數(shù) 稱為串的長(zhǎng)度 2 空串不含任何字符的串稱為空串 它的長(zhǎng)度n 0 記為s 3 空格串含有一個(gè)或多個(gè)空格的串 稱為空格串 它的長(zhǎng)度n為空格的個(gè)數(shù) 一般用符號(hào) 表示空串 串是有限長(zhǎng)的字符序列 由一對(duì)單引號(hào)相括 如 astring 4 子串 主串通常將字符在串中的序號(hào)稱為該字符在串中的位置 子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示 若一個(gè)串是另一個(gè)串中連續(xù)的一段 則這個(gè)串稱為另一個(gè)串的子串 而另一個(gè)串相對(duì)于該串稱為主串 例如 串s1 abcdefg s2 fabcdefghxyz 則s1為s2的子串 s2相對(duì)于s1為主串 另外 空串是任意串的子串 任意串是自身的子串 若一個(gè)串的長(zhǎng)度為n 則它的子串?dāng)?shù)目為 1 真子串個(gè)數(shù)為 除串本身以外的子串都稱為真子串 當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí) 稱這兩個(gè)串是相等的 即只有當(dāng)兩個(gè)串的長(zhǎng)度相等 并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等 二 串的抽象數(shù)據(jù)類型的定義如下 ADTString 數(shù)據(jù)對(duì)象 D ai ai CharacterSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R1 ai 1 ai D i 2 n 基本操作 StrAssign T chars StrCopy T S DestroyString S StrEmpty S StrCompare S T StrLength S Concat T S1 S2 SubString Sub S pos len Index S T pos Replace S T V StrInsert S pos T StrDelete S pos len ClearString S ADTString StrAssign T chars 初始條件 chars是字符串常量 操作結(jié)果 把chars賦為T的值 StrCopy T S 初始條件 串S存在 操作結(jié)果 由串S復(fù)制得串T DestroyString S 初始條件 串S存在 操作結(jié)果 串S被銷毀 StrEmpty S 初始條件 串S存在 操作結(jié)果 若S為空串 則返回TRUE 否則返回FALSE 表示空串 空串的長(zhǎng)度為零 StrCompare S T 初始條件 串S和T存在 操作結(jié)果 若S T 則返回值 0 若S T 則返回值 0 若S T 則返回值 0 例如 StrCompare data state 0 StrLength S 初始條件 串S存在 操作結(jié)果 返回S的元素個(gè)數(shù) 稱為串的長(zhǎng)度 Concat T S1 S2 初始條件 串S1和S2存在 操作結(jié)果 用T返回由S1和S2聯(lián)接而成的新串 例如 Concate T man kind 求得T mankind SubString Sub S pos len 初始條件 串S存在 1 pos StrLength S 且0 len StrLength S pos 1 操作結(jié)果 用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串 例如 SubString sub commander 4 3 求得sub man SubString sub commander 1 9 求得sub commander SubString sub commander 9 1 求得sub r 子串為 串 中的一個(gè)字符子序列 SubString sub commander 4 7 sub SubString sub beijing 7 2 sub SubString student 5 0 起始位置和子串長(zhǎng)度之間存在約束關(guān)系 長(zhǎng)度為0的子串為 合法 串 Index S T pos 初始條件 串S和T存在 T是非空串 1 pos StrLength S 操作結(jié)果 若主串S中存在和串T值相同的子串 則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置 否則函數(shù)值為0 假設(shè)S abcaabcaaabc T bca Index S T 1 2 Index S T 2 6 Index S T 8 0 子串在主串中的位置 意指子串中的第一個(gè)字符在主串中的位序 Replace S T V 初始條件 串S T和V均已存在 且T是非空串 操作結(jié)果 用V替換主串S中出現(xiàn)的所有與 模式串 T相等的不重疊的子串 例如 假設(shè)S abcaabcaaabca T bca 若V x 則經(jīng)置換后得到S axaxaax 若V bc 則經(jīng)置換后得到S abcabcaabc StrInsert S pos T 初始條件 串S和T存在 1 pos StrLength S 1 操作結(jié)果 在串S的第pos個(gè)字符之前插入串T 例如 S chater T rac 則執(zhí)行StrInsert S 4 T 之后得到S character StrDelete S pos len 初始條件 串S存在1 pos StrLength S len 1 操作結(jié)果 從串S中刪除第pos個(gè)字符起長(zhǎng)度為len的子串 ClearString S 初始條件 串S存在 操作結(jié)果 將S清為空串 對(duì)于串的基本操作集可以有不同的定義方法 在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類型時(shí) 應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn) gets str 輸入一個(gè)串 puts str 輸出一個(gè)串 strcat str1 str2 串聯(lián)接函數(shù) strcpy str1 str2 k 串復(fù)制函數(shù) strcmp str1 str2 串比較函數(shù) strlen str 求串長(zhǎng)函數(shù) 例如 C語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù) 在上述抽象數(shù)據(jù)類型定義的13種操作中 串賦值StrAssign 串復(fù)制Strcopy 串比較StrCompare 求串長(zhǎng)StrLength 串聯(lián)接Concat以及求子串SubString等六種操作構(gòu)成串類型的最小操作子集 即 這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn) 反之 其他串操作 除串清除ClearString和串銷毀DestroyString外 可在這個(gè)最小操作子集上實(shí)現(xiàn) 例如 可利用串比較 求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index S T pos StrCompare SubString S i StrLength T T 0 S串 T串 T串 i pos n m 1 算法的基本思想為 intIndex StringS StringT intpos T為非空串 若主串S中第pos個(gè)字符之后存在與T相等的子串 則返回第一個(gè)這樣的子串在S中的位置 否則返回0if pos 0 n StrLength S m StrLength T i pos while i n m 1 SubString sub S i m if StrCompare sub T 0 i elsereturni while ifreturn0 S中不存在與T相等的子串 Index 又如串的置換函數(shù) Replace S T V S串 T串 V串 V串 pos pos sub i news串 sub 串的邏輯結(jié)構(gòu)和線性表極為相似 區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集 串的基本操作和線性表有很大差別 在線性表的基本操作中 大多以 單個(gè)元素 作為操作對(duì)象 在串的基本操作中 通常以 串的整體 作為操作對(duì)象 在程序設(shè)計(jì)語(yǔ)言中 串只是作為輸入或輸出的常量出現(xiàn) 則只需存儲(chǔ)此串的串值 即字符序列即可 但在多數(shù)非數(shù)值處理的程序中 串也以變量的形式出現(xiàn) 4 2串的表示和實(shí)現(xiàn) 一 串的定長(zhǎng)順序存儲(chǔ)表示 二 串的堆分配存儲(chǔ)表示 三 串的塊鏈存儲(chǔ)表示 一 串的定長(zhǎng)順序存儲(chǔ)表示 與前面所講的線性表的順序存儲(chǔ)結(jié)構(gòu)類似 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列 常常將定長(zhǎng)順序串設(shè)計(jì)成一種結(jié)構(gòu)類型 串的存儲(chǔ)分配是在編譯時(shí)完成的 defineMAXSTRLEN255 用戶可在255以內(nèi)定義最大串長(zhǎng)typedefunsignedcharSstring MAXSTRLEN 1 0號(hào)單元存放串的長(zhǎng)度 或 typedefstruct 串結(jié)構(gòu)定義 charch MAXLEN intlen SString 按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí) 其基本操作為 字符序列的復(fù)制 串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定 超過予定義長(zhǎng)度的串值則被舍去 稱之為 截?cái)?特點(diǎn) StatusConcat SStringS1 SStringS2 SString Concat 例如 串的聯(lián)接算法中需分三種情況處理 T 1 S1 0 S1 1 S1 0 T S1 0 1 S1 0 S2 0 S2 1 S2 0 T 0 S1 0 S2 0 uncut TRUE if S1 0 S2 0 MAXSTRLEN 未截?cái)?elseif S1 0 MAXSTRSIZE 截?cái)?else 截?cái)?僅取S1 T 1 S1 0 S1 1 S1 0 T S1 0 1 MAXSTRLEN S2 1 MAXSTRLEN S1 0 T 0 MAXSTRLEN uncut FALSE T 0 MAXSTRLEN S1 0 MAXSTRLEN T 0 S1 0 MAXSTRLENuncut FALSE 1 串插入函數(shù) StrInsert s pos t 在串s中序號(hào)為pos的字符之前插入串t SString s t intpos inti if poss len return 0 插入位置不合法 if s len t lenlen t len 1 i t len pos i s ch i s ch i t len for i 0 ich i pos t ch i s len s len t len 定長(zhǎng)順序存儲(chǔ)的操作實(shí)施 算法串插入函數(shù) elseif pos t lenMAXLEN 但串t的字符序列可以全部插入 for i MAXSTRLEN 1 i t len pos 1 i s ch i s ch i t len for i 0 ich i pos t ch i s len MAXLEN else 串t的部分字符序列要舍棄 for i 0 ich i pos t ch i s len MAXSTRLEN return 1 2 串刪除函數(shù) StrDelete s pos len 在串s中刪除從序號(hào)pos起len個(gè)字符 SString s intpos len inti if pos s len len return 0 for i pos len ilen i s ch i len s ch i s len s len len return 1 算法串刪除函數(shù) 3 串復(fù)制函數(shù) StrCopy s t 將串t的值復(fù)制到串s中 SString s t inti for i 0 ich i t ch i s len t len 算法串復(fù)制函數(shù) 4 判空函數(shù) StrEmpty s 若串s為空 即串長(zhǎng)為0 則返回1 否則返回0 SStrings if s len 0 return 1 elsereturn 0 算法判空函數(shù) 5 串比較函數(shù) StrCompare s t 若串s和t相等 則返回0 若s t 則返回1 若s t 則返回 1 SStrings t inti for i 0 i s len 算法串比較函數(shù) 6 求串長(zhǎng)函數(shù) StrLength s 返回串s的長(zhǎng)度 SStrings return s len 算法求串長(zhǎng)函數(shù) 7 清空函數(shù) StrClear s 將串s置為空串 SString s s len 0 return 1 算法清空函數(shù) 8 連接函數(shù) Concat s t 將串t連接在串s的后面 SString s t inti flag if s len t lenlen ilen t len i s ch i t ch i s len s len t len flag 1 elseif s lenlen ich i t ch i s len s len MAXSTRLEN flag 0 elseflag 0 串s的長(zhǎng)度等于MAXLEN 串t不被連接 return flag 算法連接函數(shù) 9 求子串函數(shù) SubString sub s pos len 將串s中序號(hào)pos起len個(gè)字符復(fù)制到sub中 SString sub s intpos len inti if poss len lens len pos sub len 0 return 0 else for i 0 ich i s ch i pos sub len len return 1 算法求子串函數(shù) 10 定位函數(shù) StrIndex s pos t 求串t在串s中的位置 SStrings t intpos inti j if t len 0 return 0 i pos j 0 while i t len return i t len elsereturn 0 算法定位函數(shù) typedefstruct char ch 若是非空串 則按串長(zhǎng)分配存儲(chǔ)區(qū) 否則ch為NULLintlength 串長(zhǎng)度 HString 二 串的堆分配存儲(chǔ)表示 特點(diǎn) 仍用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列 但其存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得 通常 C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的 系統(tǒng)利用函數(shù)malloc 和free 進(jìn)行串值空間的動(dòng)態(tài)管理 為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū) 稱串值共享的存儲(chǔ)空間為 堆 C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符 串長(zhǎng)是一個(gè)隱含值 這類串操作實(shí)現(xiàn)的算法為 先為新生成的串分配一個(gè)存儲(chǔ)空間 然后進(jìn)行串值的復(fù)制 StatusConcat HString Concat StatusSubString HString SubString Sub ch char malloc len sizeof char Sub ch 0 len 1 S pos 1 pos len 2 Sub length len 三 串的塊鏈存儲(chǔ)表示 也可用鏈表來(lái)存儲(chǔ)串值 由于串的數(shù)據(jù)元素是一個(gè)字符 它只有8位二進(jìn)制數(shù) 因此用鏈表存儲(chǔ)時(shí) 通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符 而是一個(gè)子串 存儲(chǔ)密度 數(shù)據(jù)元素所占存儲(chǔ)位 實(shí)際分配的存儲(chǔ)位 defineCHUNKSIZE80 可由用戶定義的塊大小typedefstructChunk 結(jié)點(diǎn)結(jié)構(gòu)charch CHUNKSIZE structChunk next Chunk typedefstruct 串的鏈表結(jié)構(gòu)Chunk head tail 串的頭和尾指針intcurlen 串的當(dāng)前長(zhǎng)度 LString 例如 在編輯系統(tǒng)中 整個(gè)文本編輯區(qū)可以看成是一個(gè)串 每一行是一個(gè)子串 構(gòu)成一個(gè)結(jié)點(diǎn) 即 同一行的串用定長(zhǎng)結(jié)構(gòu) 80個(gè)字符 行和行之間用指針相聯(lián)接 實(shí)際應(yīng)用時(shí) 可以根據(jù)問題所需來(lái)設(shè)置結(jié)點(diǎn)的大小 這是串的一種重要操作 很多軟件 若有 編輯 菜單項(xiàng)的話 則其中必有 查找 子菜單項(xiàng) 4 3串的模式匹配算法 子串的定位操作通常稱為串的模式匹配 是各種串處理系統(tǒng)中最重要的操作之一 初始條件 串S和T存在 T是非空串 1 pos StrLength S 操作結(jié)果 若主串S中存在和串T值相同的子串返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置 否則函數(shù)值為0 首先 回憶一下串匹配 查找 的定義 INDEX S T pos 下面討論以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的幾種算法 一 簡(jiǎn)單算法 二 首尾匹配算法 三 KMP D E Knuth V R Pratt J H Morris 算法 一 簡(jiǎn)單算法Brute Force算法 例如 設(shè)目標(biāo)串s cddcdc 模式串t cdc s的長(zhǎng)度為n n 6 t的長(zhǎng)度為m m 3 用指針i指示目標(biāo)串s的當(dāng)前比較字符位置 用指針j指示模式串t的當(dāng)前比較字符位置 BF模式匹配過程如下所示 這個(gè)算法簡(jiǎn)單 易于理解 但效率不高 主要原因是 主串指針i在若干個(gè)字符序列比較相等后 若有一個(gè)字符比較不相等 仍需回溯 即i i j 1 該算法在最好情況下的時(shí)間復(fù)雜度為O m 即主串的前m個(gè)字符正好等于模式串的m個(gè)字符 在最壞情況下的時(shí)間復(fù)雜度為O n m intindex SqStrings SqStringt inti 0 j 0 k while i t len k i t len 返回匹配的第一個(gè)字符的下標(biāo) elsek 1 模式匹配不成功 returnk 先比較模式串的第一個(gè)字符 再比較模式串的最后一個(gè)字符 最后比較模式串中從第二個(gè)到第n 1個(gè)字符 二 首尾匹配算法 intIndex FL SStringS SStringT intpos sLength S 0 tLength T 0 i pos patStartChar T 1 patEndChar T tLength while i sLength tLength 1 if S i patStartChar i 重新查找匹配起始點(diǎn)elseif S i tLength 1 patEndChar i 模式串的 尾字符 不匹配else return0 檢查中間字符的匹配情況 k 1 j 2 while j tLength 重新開始下一次的匹配檢測(cè) 三 模式匹配的改進(jìn)算法 KMP算法 此方法由克努特 D E Knuth 莫里斯 J H Morris 普拉特 V R Pratt 同時(shí)發(fā)現(xiàn) 1 基本思想 每當(dāng)一趟匹配過程中出現(xiàn)字符不等時(shí) 不需回溯i指針 而是利用已得到的部分匹配結(jié)果 將模式串向右滑動(dòng)盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較 避免多余的 不必要的比較 從而提高算法性能 算法總在0 n m 的時(shí)間數(shù)量級(jí)上完成匹配操作 2 KMP算法匹配實(shí)例 1 模式串t中沒有真子串真子串是指模式串t存在某個(gè)k 0 k j 使得 t0t1 tk tj ktj k 1 tj 成立 例如t cdc 就是這樣的模式串 在圖4 6中的第一次回溯 當(dāng)s0 t0 s1 t1 s2 t2時(shí) 算法中取i 1 j 0 使主串指針回溯一個(gè)位置 比較s1和t0 因t0 t1 所以一定有s1 t0 另外 因有t0 t2 s0 t0 s2 t2 則一定可推出s2 t0 所以也不必取i 2 j 0去比較s2和t0 可直接在第二次比較時(shí)取i 3 j 0 比較s3和t0 這樣 模式匹配過程主串指針i就可不必回溯 2 模式串中存在真子串例如t abab 由于 t0t1 t2t3 這里k 1 j 3 則存在真子串 設(shè)s abacabab t abab 第一次匹配過程如下所示 此時(shí)不必從i 1 i i j 1 1 j 0重新開始第二次匹配 因t0 t1 s1 t1 必有s1 t0 又因t0 t2 s2 t2 所以必有s2 t0 因此 第二次匹配可直接從i 3 j 1開始 現(xiàn)在我們討論一般情況 設(shè)s s0s1 sn 1 t t0t1 tm 1 當(dāng)si tj 0 i n m 0 j m 時(shí) 存在 t0t1 tj 1 si jsi j 1 si 1 4 1 若模式串中存在的真子串滿足 t0t1 tk tj ktj k 1 tj 0 k j 4 2 由 4 1 式說明模式串中的子串 t0t1 tk 1 已和主串 si ksi k 1 si 1 匹配 下一次可直接比較si和tk 若不存在 4 2 式 則結(jié)合 4 1 式說明在 t0t1 tj 1 中不存在任何以t0為首字符子串與 si j 1si j 2 si 1 中以si 1為末字符的匹配子串 下一次可直接比較si和t0 為此 定義next j 函數(shù)如下 max k 0 k j 且 t0t1 tk 1 tj ktj k 1 tj 1 當(dāng)此集合非空時(shí) 1當(dāng)j 0時(shí)0其他情況 next j t abab 對(duì)應(yīng)的next數(shù)組如下 由模式串t求出next值的算法如下 voidGetNext SqStringt intnext intj k j 0 k 1 next 0 1 while j t len 1 if k 1 t ch j t ch k k為 1或比較的字符相等時(shí) j k next j k elsek next k intKMPIndex SqStrings SqStringt KMP算法 intnext MaxSize i 0 j 0 v GetNext t next while i t len v i t len 返回匹配模式串的首字符下標(biāo) elsev 1 返回不匹配標(biāo)志 returnv 設(shè)主串s的長(zhǎng)度為n 子串t長(zhǎng)度為m 在KMP算法中求next數(shù)組的時(shí)間復(fù)雜度為O m 在后面的匹配中因主串s的下標(biāo)不減即不回溯 比較次數(shù)可記為n 所以KMP算法總的時(shí)間復(fù)雜度為O n m 例如 設(shè)目標(biāo)串s aaabaaaab 模式串t aaaab s的長(zhǎng)度為n n 9 t的長(zhǎng)度為m m 5 用指針i指示目標(biāo)串s的當(dāng)前比較字符位置 用指針j指示模式串t的當(dāng)前比較字符位置 KMP模式匹配過程如下所示 上述定義的next 在某些情況下尚有缺陷 例如 模式 aaaab 在和主串 aaabaaaab 匹配時(shí) 當(dāng)i 3 j 3時(shí) s ch 3 t ch 3 由next j 的指示還需進(jìn)行i 3 j 2 i 3 j 1 i 3 j 0等三次比較 實(shí)際上 因?yàn)槟Ｊ街械牡? 2 3個(gè)字符和第4個(gè)字符都相等 因此 不需要再和主串中第4個(gè)字符相比較 而可以將模式一次向右滑動(dòng)4個(gè)字符的位置直接進(jìn)行i 4 j 0時(shí)的字符比較 KMP算法的改進(jìn) 這就是說 若按上述定義得到next j k 而模式中pj pk 則為主串中字符si和pj比較不等時(shí) 不需要再和pk進(jìn)行比較 而直接和pnext k 進(jìn)行比較 換句話說 此時(shí)的next j 應(yīng)和next k 相同 為此將next j 修正為nextval j 由模式串t求出nextval值 voidGetNextval SqStringt intnextval intj 0 k 1 nextval 0 1 while j t len if k 1 t ch j t ch k j k if t ch j t ch k nextval j k elsenextval j nextval k elsek nextval k 本章小結(jié) 在這一章介紹了串類型的定義及其實(shí)現(xiàn)方法 并重點(diǎn)討論了串操作中最常用的 串定位操作 又稱模式匹配 的兩個(gè)算法 串的兩個(gè)顯著特點(diǎn)是 其一 它的數(shù)據(jù)元素都