數(shù)據(jù)結(jié)構(gòu)課件：串

第四章串第四章串內(nèi)容提要：理解串的邏輯結(jié)構(gòu)及定義理解串的存儲結(jié)構(gòu)及操作的虛擬實現(xiàn)理解串的模式匹配算法第四章串本章學習另一種特殊的線性表，它特殊在：

1．數(shù)據(jù)元素都是來自字符集！

2．由于數(shù)據(jù)元素特殊，它的操作有些不同與一般線性表，例如：操作的對象一般是對子串（即一組數(shù)據(jù)元素）,而不是單個數(shù)據(jù)元素!有些高級語言已經(jīng)把串ADT物理實現(xiàn)了，所以，我們這里只是簡單討論一下串的邏輯特性、存儲結(jié)構(gòu)及一些操作的實現(xiàn)。§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)1、串（String）：簡單說，它是有限字符集中的零個或多個字符組成的有限序列。按數(shù)據(jù)結(jié)構(gòu)來定義：它是一種特殊的線性表（數(shù)據(jù)元素之間的關系是線性關系），特殊在其數(shù)據(jù)元素來自于字符集這個數(shù)據(jù)對象。定義為：

String＝(D,R)

D={ci|ci∈DODO=CHARACTERi=1，2,…nn>=0}R＝{N}

N={<ci-1,ci>|ci-1,ci∈D0i=2，3,…，n}

§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)一個串一般記作：S=‘c1c2…cn’

2、串結(jié)構(gòu)的特點：數(shù)據(jù)元索都是字符，它的操作的對象一般不再是單個數(shù)據(jù)元素，而是一組數(shù)據(jù)元索。3、串的一些術語：空串：長度為零的字符串，n=O空格串：數(shù)據(jù)元素都是空格的字符串；子串：串中連續(xù)的任意個字符組成的子序列，稱為該串的子串；主串：包含子串的串；c=‘DATASTRUCTURE’，f=‘DATA’f是c的子串下面是一些串的例子：(1)a=‘LIMING’

(2)b=‘BEJINGUNIUERCITY’

(3)c=‘DATASTRUCTURE’

(4)d=‘’

(5)e=‘’

說明：1)串中包含的字符個數(shù)，稱為串的長度。長度為0的串稱為空串，它不包括任何字符，上面（4）中的串d是空串,，(5)中的e是包含一個空格符的空格串；

2）串中所包含的字符可以是字母、數(shù)字或其他字符，這依賴于具體計算機所允許的字符集。§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)字符在串中的位置：字符在串中的序號（即第幾個數(shù)據(jù)元素）;子串在串中的位置：子串的第一個字符在主串中的位置；串相等：兩個串的長度相等，且各對應位置處的字符都相等；S=‘a(chǎn)babcabcac’,T=‘a(chǎn)bc’子串T在主串S中的位置為3例如:a,b,c,d

四個字符串為a=‘BEI’,b=‘JING’c=‘BEIJING’,d=‘BEIJING’它們的長度分別為3,4,7,8a和b都是c和d的子串a(chǎn)在c和d中的位置都是1b在c中的位置是4,而b在d中的位置是5注意:單引號是為字符串區(qū)別于變量名而設,它不是字符串的內(nèi)容4串的基本操作

串的邏輯結(jié)構(gòu)與線性表一樣，都是線性結(jié)構(gòu)。但由于串的應用與線性表不同，串的基本操作與線性表有很大差別。1）串賦值操作StrAssign(&T,chars)

功能：將串常量chars的值賦給串變量T；2）復制串操作StrCopy(&T,S)

功能：由串變量S復制得到串變量T；§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)

3）判空操作StrEmpty(S)功能：若為空串，則返回TRUE，否則返回FALSE4）串比較操作

StrCompare(S,T)功能:若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<05）串置空操作

ClearString(&S)

功能：將S清為空串6）求串長操作

StrLenght(&S)

功能：返回S的元素個數(shù),成為串的長度;7）串連接操作Concat(&T,S1,S2)

功能：由S1和S2連接組成的新串，用T返回新串；

8）求子串操作SubString(&Sub,S,pos,len)

功能：用Sub返回串S的第pos個字符起長度len

為

子串；

§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)

§4.1串的邏輯結(jié)構(gòu)及定義

一串的邏輯結(jié)構(gòu)9）求子串位置操作Index(S,T,pos)

功能：返回S中第pos個字符之后與T相同的子串的位置，若不存在返回010)串插入操作StrInsert(&S,pos,T)功能：將串T插入到串S的第pos字符之前11）串刪除操作StrDelete(&S,pos,len)功能：從串S中刪除第pos個字符起長度len

為子串可以看出:串的操作有一個特點,即對一組數(shù)據(jù)元素進行操作!!

§4.1串的邏輯結(jié)構(gòu)及定義

二串的ADT描述StrAssign(&T,chars)StrCopy(&T,S)StrEmpty(S)StrCompare(S,T)ClearString(&S)StrLenght(&S)Concat(&T,S1,S2)Index(S,T,pos)等

§4.1串的邏輯結(jié)構(gòu)及定義

二串的ADT應用舉例上述11種基本操作中,下面5種操作構(gòu)成最小操作子集:串賦值StrAssign;串比較StrCompare;求串長StrLength;串聯(lián)結(jié)Concat;求子串Substring;

其它操作可以用其實現(xiàn)§4.1串的邏輯結(jié)構(gòu)及定義

二串的ADT應用舉例例1:利用判斷串相等,求串長度,求子串操作實現(xiàn)定位操作.§4.1串的邏輯結(jié)構(gòu)及定義

二串的ADT應用舉例§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)一、串的順序存儲結(jié)構(gòu)（串的靜態(tài)存儲結(jié)構(gòu)）1、存儲方式：同一般線性表的順序存儲結(jié)構(gòu)完全相同。用一組地址連續(xù)的存儲單元存儲串的字符序列，據(jù)預定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)．2、特點：簡單、方便，但空間效率低，插入、刪除要移動字符，時間效率低。§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)3虛擬實現(xiàn)注意:1定義了最大串長，則當實際串長超過預定義長度時，多余部分被舍去，稱為截斷．

2下標為0的數(shù)組分量存放串的實際長度，便于某些操作．PASCAL語言用此方式．§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)此外，還可以用另一種方式表示串長，即以‘\0’字符作為串的結(jié)束標志．串長隱含其中（C語言的字符串是以這種方式實現(xiàn)）.實際的串值存放在下標為O--MAXSTRLEN-1的單元中，而下標為MAXSTRLEN的單元存放‘\O’字符．§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)4串的連接操作Concat(&T,S1,S2)的算法示意圖S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN時S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN時截斷部分§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)5取子串有兩種求法：其一：已知子串起點和長度；其二：已知子串起點和終點；SSub1poslen§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)6、子串定位模式匹配：在一個主串中，查找子串是否存在，存在返回子串的位置；不存在返回O。子串稱為模式。這個操作用的非常多，如：字處理軟件中的“查找”/“替換”實現(xiàn)它的方法也很多，我們介紹思想最簡單的一種―模式匹配的BF算法基本思想：從主串的第i個位置開始，與子串的每個字符逐個比較，若均相等，則找到；否則，即出現(xiàn)了不等，則說明從該起點不是模式串，換下一個起點，重新開始！第一趟匹配

ab

a

bcabcacbabi=3

ab

cj=3第二趟匹配

ab

abcabcacbabi=2

a

j=1第三趟匹配

ababca

b

cacbabi=7

abca

cj=5例S=‘a(chǎn)babcabcac’T=‘a(chǎn)bc’pos=1index(S,T,pos)返回值為6§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)第四趟匹配

aba

b

cabcacbabi=4

a

j=1第五趟匹配

abab

c

abcacbabi=5

aj=1第六趟匹配

ababcabcacb

abi=11

abcacj=6匹配成功BF算法若不匹配時,主串回到上一次起始的下一位置,模式串回到起始的第一個字符!§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)int

Index(SStringS,SStringT,intpos){//返回在主串S第pos個字符后子串T的位置。若不存在，則函數(shù)值為0。其中，T非空，1≤pos≤StLength(S)。i=pos;j=1;//i=pos,主串匹配的起始位置while(i<=S[0]&&j<=T[0]){

if(S[i]=T(j){++i;++j;)}//繼續(xù)比較后繼字符

else{i=i-j+2;j=1;}//指針i后退(至當前匹配起始位置的//下一位置）重新開始匹配}

if(j>T[0])returni-T[0];//匹配成功，返回子串T的位置elsereturn0;}//Index§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)算法效率：設主串長度為m，模式串長度為n;

找到模式串(無回溯):最好：開始就是模式串，O(n)

aaaaabbbbbb

aaa最壞：最后是模式串，O(m)

cbbbcbcbaaa

aaa找不到模式串(無回溯):O(m)

aaaaaaaaaaaaxyz§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)找到模式串(有回溯):最好：回溯很少，或沒回溯O(m+n)

abcabcabcaab

aab

最壞：回溯很多，或每次都有回溯O(m*n)

aaaaaaaaaaab

aaab

找不到模式串(有回溯)：O(m*n)aaaaaaaaaaaa

aaac§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)a、時間復雜性最壞為（m*n)，但一般情況下為O(m+n)，所以還是一個常用算法。b、由于有回溯，所以主串輸入后必須保存。BF算法的特點:§4.2串的表示及實現(xiàn)

§4.2.2串的鏈式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)一、串的鏈存儲結(jié)構(gòu)（塊鏈式）

1、存儲方式：同一般線性表的單鏈存儲結(jié)構(gòu)完全相同。但是，一個結(jié)點存儲幾個數(shù)據(jù)元素有差異！由于串結(jié)構(gòu)中每個數(shù)據(jù)元素為一個字符，所以最直接的鏈式存儲結(jié)構(gòu)是每個結(jié)點的數(shù)據(jù)域存放一個字符。舉例：string^S

2.優(yōu)點是操作方便；不足之處是存儲密度較低。所謂存儲密度為：

若要將多個字符存放在一個結(jié)點中，就可以緩解這個問題。舉例：Sstring####^§4.2串的表示及實現(xiàn)

§4.2.2串的鏈式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)說明:

(1)

由于串中的字符個數(shù)不一定是每個結(jié)點存放字符個數(shù)的整倍數(shù)，所以，需要在最后一個結(jié)點的空缺位置上填充特殊的字符。(2)這種存儲形式優(yōu)點是存儲密度高于結(jié)點大小為1的存儲形式；不足之處是做插入、刪除字符的操作時，可能會引起結(jié)點之間字符的移動，算法實現(xiàn)起來比較復雜。

(3)存儲密度小,運算處理方便,但占用存儲量大;存儲密度大,運算處理困難,但占用存儲量小.§4.2串的表示及實現(xiàn)

§4.2.1串的順序存儲結(jié)構(gòu)及操作虛擬實現(xiàn)§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)一串的堆分配存儲

堆分配存儲類似于線性表的順序存儲結(jié)構(gòu)，以一組地址連續(xù)的存儲單元存放串值字符序列，其存儲空間是在程序執(zhí)行過程中動態(tài)分配的。maxlen§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)例如：有3個字符串

s='ComputerScience'

t='Datastructuresisimportant!’u=’seats:rocking-chair,stool,armchair…’在這種存儲結(jié)構(gòu)下，串操作仍是基于“字符序列的復制”進行的。例如，如串插入操作StrInsert(S,pos,T)（將串T插入到串S的第pos字符之前）的算法是，為串S重新分配大小等于串S和串T長度之和的存儲空間，然后進行將S和T串值復制到新分配存儲空間中。

Typedef

struct

{char*ch;//指針域，指向存放串值的存儲空間基址

intlength;//整型域：存放串長}Hstring;§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)堆分配存儲的虛擬實現(xiàn)串賦值算法StatusStrAssign(HString&T,char*chars){//生成一個其值等于串常量chars的串Tif(T.ch)free(T.ch);//若T.ch非空，釋放T.ch所指向的存儲空間for(i=0,c=chars;c;++i,++c);//求chars的長度iif(!i){T.ch=NULL;T.length=0;}//若i=0,生成空串Telse{if(!(T.ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}//StrAssign§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)串常量根據(jù)串常量的長度動態(tài)分配存儲空間a1a2anchars01n-1傳遞數(shù)據(jù)T.chT.length01n-1a1a2an串賦值操作圖示n§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)int

StrCompare(HStringS,HStringT){//若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}//StrCompare

串比較算法§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)StatusClearString(HString&S){

//將S清為空串。if(S.ch){free(S.ch);S.ch=NULL;}//若S.ch非空，釋放S.ch所指向的存儲空間，S.ch=nullS.length=0;returnOK;}//ClearString

串置空算法

§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)StatusConcat(HString&T,HstringS1,HStringS2){

//用T返回由S1和S2連接而成的新串。if(T.ch)free(T.ch);//若T.ch非空，釋放T.ch所指向的存儲空間if(!(T.ch=(char*)malloc((S1.Length+S2.length）*sizeof(char))))exit(OVERFLOW);T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];returnOK;}//Concat

串連接算法

§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)s1.ch01n1-1s1.lengthn1s2.ch01n2-1s2.lengthn2串s1串s2進行串的合并s.ch01n1-1n1n1+n2-1

s.lengthn1+n2串連接圖示

§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)求子串算法StatusSubString(HString&Sub,HStringS,intpos,int

len){

//用Sub返回串S的第pos個字符起長度為len的子串。其中，//1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;//參數(shù)不合法if(Sub.ch)free(Sub.ch);//若Sub.ch非空，釋放Sub.ch所指向存儲空間if(!len){Sub.ch=NULL;Sub.length=0;}//若len=0,Sub為空子串else{//復制子串

Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2];Sub.length=len;}returnOK;}SubString01Sub.chLen-1Sub.lengthlen動態(tài)分配存儲空間01pos-1n-1S.lengthnS.ch01Sub.chLen-1Sub.lengthlen

§4.2串的表示及實現(xiàn)

§4.2.3串的堆式存儲結(jié)構(gòu)及操作虛擬實現(xiàn)串插入算法StrInsert(HString&S,intpos,HStringT){//為串S重新分配大小等于串S和串T長度之和的存儲空間，將S和T串值復制到新分配存儲空間中;if(pos<1||pos>S.length+1)returnERROR;//參數(shù)不合法if(T.length){//若T非空，為串S重新分配存儲空間,并插入Tif(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);

//將S的第pos個字符及后面的字符后移，為插入T騰出位置for(i=S.length-1;i>=pos-1;--i)

S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入TS.length+=T.length;}returnOK;}SubStringS.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1為串S重新分配存儲空間,并將S復制到新空間將S的第pos個字符及后面的字符后移，為插入T騰