1、2022-4-10第四章 串1第四章 串4.1 串類型的定義4.2 串的表示和實現 4.2.1 定長順序存儲表示 4.2.2 堆分配存儲表示 4.2.3 串的塊鏈存儲表示4.3 串的模式匹配算法4.4 串操作應用舉例文本編輯2022-4-10第四章 串24.1 串類型的定義基本概念 串(String)是由零個或多個字符組成的有限序列。一般記作S=a1a2a3an，其中S 是串名，單引號括起來的字符序列是串值；ai(1in)可以是字母、數字或其它字符；串中所包含的字符個數稱為該串的長度。 空串(Empty String)：長度為零的串。它不包含任何字符。 空格串(Blank String)： 由

2、一個或多個空格組成的串。 注意：空串和空格串的不同。2022-4-10第四章 串3基本概念（續）子串：串中任意個連續字符組成的子序列。主串：包含子串的串。通常將子串在主串中首次出現時的該子串的首字符對應的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設A和B分別為 A=“This is a string” B=“is” 則B是A的子串，A為主串。B在A中出現了兩次，其中首次出現所對應的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。2022-4-10第四章 串4基本概念（續） 通常在程序中使用的串可分為兩種：串變量和串常量。串常量

3、和整常數、實常數一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示的，例如語句Error(“overflow”)中“overflow”是直接量。但有的語言允許對串常量命名，以使程序易讀、易寫。如C+中，可定義 const char path=“dir/bin/appl”; 這里path是一個串常量，對它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。2022-4-10第四章 串5串的抽象數據類型定義 串的抽象數據類型定義見教材P71 串的基本操作(13個)：StrAssign, Strcopy, StrEmpty, StrCompare, St

4、rLength, ClearString, Concat, SubString, Index, Replace, StrInsert, StrDelete, DestroyString 許多高級語言均提供了串基本操作相應的運算或標準庫函數來實現。下面僅介紹幾種在C語言中常用的串運算，其它的串操作見教材及參考書。2022-4-10第四章 串6 串變量及基本操作： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;(1)求串長(length) int strlen(char s); /求串的長度 例如：couts

5、trlen(s1); 輸出132022-4-10第四章 串7基本操作（續）（2）串復制(copy) char *strcopy(char to,char from); 該函數將串from復制到串to中，并且返回一個指向串to的開始處的指針。 例如：strcopy(s3,s1); /s3=“dirtreeformat”(3)聯接(concatenation) char concat(char to,char from) 該函數將串from復制到串to的末尾，并且返回一個指向串to的開始處的指針。2022-4-10第四章 串8基本操作（續）例如：concat(s3,”/”) concat(s3,s

6、2); /s3=“dirtreeformat/file.mem”(4)串比較（compare) int strcompare(chars1,char s2); 該函數比較串s1和串s2的大小，當返回值小于0，等于0或大于0時分別表示s1s2 例如： result= strcompare (“baker”,”Baker”) result0 result= strcompare (“12”,”12”); result=0 result= strcompare (“Joe”,”Joseph”); result02022-4-10第四章 串9基本操作（續）（5）字符定位(index) char str

7、chr(char s,char c); 該函數是找c在字符串中第一次出現的位置，若找到則返回該位置，否則返回NULL。 例如：p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,”.cpp”); s2=“file.cpp”最小操作子集：串賦值StrAssign、串比較Strcompare、求串長StrLength、串聯接concat和求子串SubString。串的其余操作可由這些基本操作組合而成。2022-4-10第四章 串104.2 串的表示和實現 因為串是特殊的線性表，故其存儲結構與線性表的存儲結構類似。只不過由于組成串的結點是單個字符。串有三

8、種機內表示方法，下面分別介紹。1 定長順序存儲表示 定長順序存儲表示,也稱為靜態存儲分配的順序表。它是用一組連續的存儲單元來存放串中的字符序列。所謂定長順序存儲結構，是直接使用定長的字符數組來定義，數組的上界預先給出： #define maxstrlen 255 typedef char sstringmaxstrlen+1; sstring s; /s是一個可容納255個字符的順序串。2022-4-10第四章 串11串的結束標記 一般可使用一個不會出現在串中的特殊字符在串值的尾部來表示串的結束。例如，C語言中以字符 0表示串值的終結，這就是為什么在上述定義中，串空間最大值maxstrlen為

9、256，但最多只能存放255個字符的原因，因為必須留一個字節來存放 0字符。若不設終結符，可用一個整數來表示串的長度，那么該長度減1的位置就是串值的最后一個字符的位置。2022-4-10第四章 串12順序串的類型定義順序串的類型定義和順序表類似： typedef struct char chmaxstrlen; int length; sstring; /其優點是涉及到串長操作時速度快。2022-4-10第四章 串13順序存儲時串操作的實現 串聯接Concat(T,S1,S2) 求子串SubString(sub,s,pos,len) 注：串聯接操作可能出現“截斷”現象2022-4-10第四章

10、串142 堆分配存儲表示 這種存儲表示的特點是，仍以一組地址連續的存儲單元存放串值字符序列，但它們的存儲空間是在程序執行過程中動態分配而得。所以也稱為動態存儲分配的順序表。在C語言中，利用動態存儲管理函數，來根據實際需要動態分配和釋放字符數組空間。 typedef struct char *ch; /若是非空串，則按串長分配存儲區，否則ch為null int length; /串長度 hsring;2022-4-10第四章 串153 串的鏈式存儲結構 順序串上的插入和刪除操作不方便，需要移動大量的字符。因此，我們可用單鏈表方式來存儲串值，串的這種鏈式存儲結構簡稱為鏈串。 typedef str

11、uct node char data; struct node *next; lstring; 一個鏈串由頭指針唯一確定。 這種結構便于進行插入和刪除運算，但存儲空間利用率太低。2022-4-10第四章 串16結點的大小 由于串結構的特殊性，可使每個結點存放多個字符。通常將結點數據域存放的字符個數定義為結點的大小，顯然，當結點大小大于 1時，串的長度不一定正好是結點的整數倍，因此要用特殊字符來填充最后一個結點，以表示串的終結。headABCIB C DE F G HI # # #headA2022-4-10第四章 串17 塊鏈結構（設頭、尾指針） 對于結點大小不為1的鏈串，其類型定義只需對上述

12、的結點類型做簡單的修改即可。 #define nodesize 80 typedef struct node char datanodesize; struct node *next; node; typedef struct lstring node *head,*tail; int curlen; lstring;2022-4-10第四章 串18存儲密度的概念 存儲密度小，運算處理方便，存儲占用量大；存儲密度大，情況則相反。 串的鏈式存儲結構隊某些串操作（如聯接等）有一定的方便，但總的說來不如另外兩種存儲結構靈活。存儲密度 =串值所占的存儲位實際分配的存儲位2022-4-10第四章 串19

13、4.3 串的模式匹配算法子串定位運算又稱為模式匹配(Pattern Matching)或串匹配(String Matching)，此運算的應用非常廣泛。在文本編輯程序中，我們經常要查找某一特定單詞在文本中出現的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應性能。在串匹配中，一般將主串稱為目標串，子串稱之為模式串。2022-4-10第四章 串20模式匹配（續） 設S為目標串，T為模式串，且不妨設： S=“s0s1s2sn-1” T=“t0t1tm-1” 串的匹配實際上是對于合法的位置0in-m依次將目標串中的子串si.i+m-1和模式串t0.m-1進行比較，若si.i+m-1=t0

14、.m-1，則稱從位置i開始的匹配成功，亦稱模式t在目標s中出現.2022-4-10第四章 串21模式匹配（續）若si.i+m-1 t0.m-1，則稱從位置i開始的匹配失敗。上述的位置i又稱為位移，當si.i+m-1=t0.m-1時，i稱為有效位移；當si.i+m-1 t0.m-1時，i稱為無效位移。這樣，串匹配問題可簡化為是找出某給定模式T在一給定目標T中首次出現的有效位移。 2022-4-10第四章 串22模式匹配算法串匹配的算法很多，這里我們只討論一種最簡單的稱為樸素的串匹配算法。其基本思想是用一個循環來依次檢查n-m+1個合法的位移i(0I n-m)是否為有效位移，其算法段為： for(

15、i=0;i=n-m;i+) if(Si.i+m-1=T0.m-1) return i; 2022-4-10第四章 串23模式匹配算法匹配過程設目標串為a b a b c a b c a c b a b，模式串為a b c a c第一趟 a b a b c a b c a c b a b a b c第二趟 a b a b c a b c a c b a b a第三趟 a b a b c a b c a c b a b a b c a c第四趟 a b a b c a b c a c b a b a第五趟 a b a b c a b c a c b a b a第六趟 a b a b c a b c

16、 a c b a b a b c a c2022-4-10第四章 串24KMP算法模式匹配的改進算法算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同時發現，因而得名。改進在于：利用已經得到的部分匹配結果將模式向右“滑動”盡可能遠的一段距離。算法可以在O(n+m)的時間數量級上完成。第一趟 a b a b c a b c a c b a b a b c第二趟 a b a b c a b c a c b a b a b c a c第三趟 a b a b c a b c a c b a b a b c a c 2022-4-10第四章 串25線性結構復習線性表n個數據元素的有限序列 抽象數據類型定義（12個基本操作） 存儲結構：順序存儲順序表；鏈式存儲線性鏈表，循環鏈表和雙向鏈表；其它。棧和隊列操作受限的線性表 抽象數據類型定義（分別為9個操作） 存儲結構：順序存儲順序棧和循環隊列；鏈式存儲鏈棧和鏈隊列串由零個或多個字符組成的有限序列 抽象數據類型定義（13個基本操作） 存儲結構：定長順序存儲；堆分配存儲和塊鏈存儲2022-4-10第四章 串26作業題1 (P27 4.3)設s=I AM A STUDENT, t=GOOD, q=WORKER. 求：strlenth(s),strleng