十一期間,項目比較緊,讓各位久等了
一.串的定義
串:是由零個或多個字符組成的有限序列,又名叫字符串
一般記為s = "a1,a2,a3......an",其中s是串的名字,用雙引號(有的書中也用單引號)括起來的字符序列是串的值.ai(1<= i <= n)可以是字母,數(shù)字或其他字符,i是該字符在串中的位置.串中的字符數(shù)目n稱為串的長度*
零個字符串稱為空串,它的長度為零,,可以直接用兩雙引號' " " '表示
序列:說明串的相鄰字符之間具有前驅和后繼的關系
空格串:只包含空格的串.它和空串是有區(qū)別的,空格串是有內(nèi)容長度的,而且不止一個空格
子串與主串:串中任意個數(shù)的連續(xù)字符組成的子序列稱為該串的子串,相應地,包含子串的串稱為主串
子串在主串中的位置就是子串的第一個字符在主串的序號
二.串的比較
數(shù)字很容易比較大小.字符串的大小比較取決于他們每個字母的前后順序和字符串的長度
字符串比較總結:
-
1.字符串相等
必須他們串的長度以及他們各個對應位置的字符都相等時,才算相等.即給定兩個串:s = "a1, a2, a3 ......an", t = "b1, b2 , b3 ....bm",當且僅當n = m,且a1= b1,a2 = b2,a3 = b3......an = bm都滿足時.我們認為s = t -
2.字符串不相等
給定兩個串:s = "a1, a2, a3......an", t = "b1,b2,b3......bm",當滿足以下條件任意一個,s < t
1)n < m,且a1 = b1 (i = 1,2,......,n),比如圖字符串比較四
2)存在某個k <= min(m, n),使得ai = bi(i = 1, 2 .......k -1),ak < bk,如字符串比較圖1,2
三.串的抽象數(shù)據(jù)類型
串的邏輯結構和線性表很相似.不同之處在于串針對的是字符集,也就是串中的元素都是字符,比如"123""2010-10-10",這也只能理解為長度為3和長度為10的字符串,每個元素都是字符
線性表關注的是單個元素的操作,比如查找一個元素,插入或刪除一個元素
串中更多的是查找子串位置,得到指定位置子串,替換子串等操作
ADT 串(string)
Data
串中元素僅由一個字符組成,相鄰元素具有前驅和后繼關系
Operation
StrAssign(T,*chars):生成一個其值等于字符串常量chars的串T
StrCopy(T,S):若S存在,由串S賦值得串T
ClearString(S):若串存在,將串清空
StringEmpty(S):若串S為空,返回true,否則返回false
StrLength(S):返回串S的元素個數(shù),即串的長度
StrCompare(S,T):若S > T,返回值 > 0,若S = T,返回0,若 S < T,返回值 <0
Concat(T,S1,S2):用T返回由S1和S2連接而成的新串
SubString(Sub,S,pos,len):串S存在,1 <= pos <= StrLength(S),且0<= len <= StrLength(s) - post +1,用Sub返回串S的第post個字符起長度為len的子串
Index(S,T,pos):串S和T存在,T是非空串,1 <= post <= StrLength(s).若主串S中存在和串T值相同的子串,則返回它在主串S中第post個字符之后第一次出現(xiàn)的位置,否則返回0
Replace (S,T,V):串S,T,V存在,T是非空串.用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串
StrInsert(S,pos,T):串S和T存在,1<= pos <= StrLength(S) + 1.在串S的第pos個字符之前插入串T
StrDelete(S,post,len):串S存在,1<=pos <= Strlength(S) - len + 1.從串S中刪除第pos個字符起長度為len的子串
endADT
實現(xiàn)算法
//T為非空串,若主串S中第pos個字符之后存在與T相等的子串
//則返回第一個這樣的子串在S中的位置,否則返回0
int Index (String S , String T, int pos){
int n ,m ,i;
String sub;
if (pos > 0)[
n = StrLength(S);//得到主串S的長度
m = StrLength(T);//得到子串T的長度
i = pos;
while (i <= n - m + 1){
SubString(sub, S,i,m);//取主串第i個位置,長度與T相等的子串給sub
if (StrCompare (sub,T) != 0)//如果兩串不相等
++i;
else
return i ; //如果兩串相等返回i值
}
}
return 0; //若無子串與T相等,返回0
}
四.串的存儲結構
1.串的順序存儲結構
串的順序存儲結構是用一組地址連續(xù)的存儲單元來存儲串中的字符序列.按照預定義的大小,為每個定義的串變量分配一個固定長度的存儲單元.一般用定義長數(shù)組來定義
它規(guī)定在串值后面加一個不計入串長度的結束標記字符,比如"\0"來表示串值的終結
串的順序存儲長度的缺點:串的長度超過數(shù)組的長度MaxSize,超出部分就不在顯示
2.串的鏈式存儲
串的鏈式存儲結構,與線性表是相似的,結構中的每個元素數(shù)據(jù)都是一個字符,如果一個結點對應一個字符,就會存在很大的空間浪費.因此,一個結點可以存放一個字符,也可以存放多個字符,最后一個結點未被占滿時,可以用"#"或其他串值字符補全
五.樸素的模式匹配算法
子串的定位操作通常稱作串的模式匹配,應該算是串中最重要的操作之一
假設我們要從下面的主串S = "goodgoogle"中,找到T="google"這個子串的位置,我們需要下面的步驟
1.從主串的第一位開始,此次與T進行匹配.S與T的前三個字母都匹配成功,但是S的第四個字母是d,T的第四個字母是g,第一位匹配失敗.豎直連線表示相等,??表示不等
2.主串S的第二位開始,主串S的首字母是o,要匹配的T首字母是g,匹配失敗
3.主串S的第三位開始,主串S的首字母是o,要匹配的T首字母是g,匹配失敗
4.主串S的第四位開始,主串S的首字母是d,要匹配的T首字母是g,匹配失敗
5.主串S的第五位開始,S與T,6個字母全匹配成功,終于成功了..此處應該有掌聲~??????
思路:
1.對主串進行大循環(huán)
-
2.對子串進行小循環(huán)
//主串S和子串T的長度存在S[0]和T[0]中 //返回子串T在主串S中pos個字符之后的位置,若不存在,則函數(shù)返回值為0 //T非空,1 <= pos <= StrLength(S) int Index (String S , String T, int pos){ int i = pos;//i用于主串中當前位置下標,若pos不為1,則從pos位置開始匹配 int j = 1; //j用于子串T當前位置下標值 while(i <= S[0] && j<= T[0]){//若i小于S長度且j小于T的長度時循環(huán) if (S[i] == T[j])//兩字母相等則繼續(xù) { ++i; ++j; }else{ //指針后退重新開始匹配 i = i - j + 2;//i返回到上次匹配首位的下一位 j = 1; //j返回到子串T的首位 } } if (j > T[0]) return i - T[0]; esle return 0; }
最好情況: 一次就成功 ,時間復雜度為O(1)
稍差一點:就想剛才例子中,第二,三,四位一樣,每次都首字母就不匹配,那么對T串的循環(huán)就不必進行,比如"abcdefgoole"中,去找"goole",那么時間復雜度為O(n + m) ,其中n為主串長度,m為子串長度 ........這里始終認為是O(n -m + 1),坐等大神解釋
最壞情況:每次不成功的匹配都發(fā)生在串T的最后一個字符.舉個很極端的例子,主串S = "0000000000000000000000000000000000000000000000000001",而要匹配的子串為T ="0000000001",前者有49個"0"和1個"1"的主串,后者是9個"0"和1個"1"的子串,在匹配是.每次都將T中的字符循環(huán)到最后一位才發(fā)現(xiàn):他們不匹配.這樣等于T串需要在S串的前40個位置都需要判斷10次,并得出不匹配的結論
直到最后41個位置,因為全部匹配相等,所以不需要再繼續(xù)進行下去.如果最終沒有可匹配的子串,比如T = "0000000002",到第41位置判斷不匹配后同樣不需要在進行對比下去了.因此最壞情況的時間復雜度為O(n - m + 1) * m
KMP模式匹配算法看的不是很理解,以后會專門補上單獨的一章
