資源描述：
《串的定義及基本運算》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、4.1串的定義及基本運算4.2串的存儲結(jié)構(gòu)4.3模式匹配算法的實現(xiàn)4.4小結(jié)與習題第四章串1串（字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個字符組成，計算機非數(shù)值處理的對象經(jīng)常是字符串數(shù)據(jù)，在事物處理程序中，一般也是作為字符串處理的。4.1串的定義及基本運算一、串和基本概念串(String)是零個或多個字符組成的有限序列。一般記作：S=“a1a2a3…an”其中S是串名，雙引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符。2通常將僅由一個或多個空格組成的串稱為
2、空白串(BlankString)。注意：空串和空白串的不同。二、串的術(shù)語1.主串和子串：串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時的該子串的首字符對應(yīng)的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設(shè)A和B分別為A=“Thisisastring”B=“is”則B是A的子串，A為主串。32.子串的位置：子串的第一個字符在主串中的序號稱為子串的位置。B在A中出現(xiàn)了兩次，首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。3.串相等：稱兩個串是相等的，是指兩個
3、串的長度相等且對應(yīng)字符都相等。4三、串的基本運算1.求串長StrLength(s)：操作條件：串s存在；操作結(jié)果：求出串s的長度。2.串賦值StrAssign(s1,s2)操作條件：s1是一個串變量，s2或者是一個串常量，或者是一個串變量（通常s2是一個串常量時稱為串賦值，是一個串變量稱為串拷貝）。操作結(jié)果：將s2的串值賦值給s1，s1原來的值被覆蓋掉。53.連接操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：兩個串的聯(lián)接就是將一個串的串值緊接著放在另一個串的后面，連接成一個串。前者是產(chǎn)生新串s，s1和s2不改變;后者是在
4、s1的后面聯(lián)接s2的串值，s1改變，s2不改變。4.求子串SubStr(s,i,len)：操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：返回從串s的第i個字符開始的長度為len的子串。len=0得到的是空串。65.串比較StrCmp(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：若s1==s2，操作返回值為0；若s1s2,返回值>0。6.子串定位StrIndex(s,t)：找子串t在主串s中首次出現(xiàn)的位置操作條件：串s,t存在。操作結(jié)果：若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回值為
5、-1。78.串刪除StrDelete(s,i,len)操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：刪除串s中從第i個字符開始的長度為len的子串，s的串值改變。7.插入StrInsert(s,i,t)操作條件：串s,t存在，1≤i≤StrLength(s)+1。操作結(jié)果：將串t插入到串s的第i個字符位置上。9.串替換StrRep(s,t,r)操作條件：串s,t,r存在，t不為空。操作結(jié)果：用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。84.2串的存儲結(jié)構(gòu)4.2.1串的定長順序存儲類似于順序表，用一組地址
6、連續(xù)的存儲單元存儲串值中的字符序列，所謂定長是指按預定義的大小，為每一個串變量分配一個固定長度的存儲區(qū)，如：1.類似順序表，用一個指針來指向最后一個字符，這樣表示的串描述如下：typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;9nedutSMAXSIZE-1…543210s.datas.curlen2.在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。比如C語言中處理定長串的方法就是這樣的，它是用＇
