串和數(shù)組精選課件

第5章串和數(shù)組串也可以看作是一種線性表，只是其操作通常是按成組的元素來進(jìn)行的。數(shù)組可以認(rèn)為是線性表在維數(shù)上的一種拓展。串和數(shù)組依然屬于線性結(jié)構(gòu)，但在存儲結(jié)構(gòu)的實(shí)現(xiàn)方面較線性表為復(fù)雜。值得注意的是，串和數(shù)組是在高級語言層面已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，在數(shù)據(jù)結(jié)構(gòu)中再討論它們是為了深入理解實(shí)現(xiàn)它們的基礎(chǔ)技術(shù)。講授本章課程大約需4課時。1第5章串和數(shù)組串也可以看作是一種線性表，只是其操作通

5.1串的定義和操作5.2串的表示和實(shí)現(xiàn)

5.3正文模式匹配5.4正文編輯━串操作應(yīng)用舉例25.1串的定義和操作25.1串的定義和操作35.1串的定義和操作3串的定義：

串（String），或稱字符串是由零個或多個字符組成的有限序列。記作：S=a0a1…ai…an-1

（n≥0）

其中，ai屬于字符集，n為串的長度，當(dāng)n=0時串為空串。例如:

astring、a+b、

4串的定義：串（String），或稱字符串是由零個或串的基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)5串的基本操作：StrAssign(&T,chars)SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)

ClearString(&S)6SubString(&Sub,S,pos,len)

StrAssign(&T,chars)

初始條件：chars是字符串常量。

操作結(jié)果：把chars賦為T的值。

7StrAssign(&T,chars)7

StrCopy(&T,S)

初始條件：串S存在。

操作結(jié)果：由串S復(fù)制得串T。8

StrCopy(&T,SDestroyString(&S)

初始條件：串S存在。

操作結(jié)果：串S被銷毀。9DestroyString(&S)9

表示空串，空串的長度為零

StrEmpty(S)

初始條件：串S存在。

操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。

表示空格，長度為1的字符串10表示空串，空串的長度

StrCompare(S,T)

初始條件：串S和T存在。

操作結(jié)果：若ST，則返回值0；

若ST，則返回值0；

若ST，則返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>011StrCompare(

StrLength(S)

初始條件：串S存在。

操作結(jié)果：返回S的元素個數(shù)，

稱為串的長度。12StrLength(S)

Concat(&T,S1,S2)

初始條件：串S1和S2存在。

操作結(jié)果：用T返回由S1和S2

聯(lián)接而成的新串。例如：Concate(T,man,kind)

求得T=mankind13Concat(&T,S1,S2)

初

SubString(&Sub,S,pos,len)初始條件：

串S存在，0≤pos<StrLength(S)且0≤len≤StrLength(S)-pos。操作結(jié)果：

用Sub返回串S的位置為pos起長度為len的子串。14

SubString(&Sub,S,pos,例如：

SubString(sub,commander,3,3)

求得sub=man；SubString(sub,commander,0,9)求得sub=commander；SubString(sub,commander,8,1)求得sub=r；子串為“串”中的一個字符子序列15例如：子串為“串”中的一個字符子序列15SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串長度之間存在約束關(guān)系長度為0的子串為“合法”串16SubString(sub,commander,

Index(S,T,pos)

初始條件：串S和T存在，T是非空串，

0≤pos≤StrLength(S)-1。

操作結(jié)果：

若主串S中存在和串T值相同

的子串,則返回它在主串S中第pos個

字符之后第一次出現(xiàn)的位置；

否則函數(shù)值為-1。

17Index(S,T,假設(shè)S=abcaabcaaabca,T=bca

Index(S,T,1)=1；Index(S,T,3)=5；Index(S,T,11)=-1；

“子串在主串中的位置”意指子串中的第一個字符在主串中的位序。18假設(shè)S=abcaabcaaabca,T=

Replace(&S,T,V)

初始條件：串S,T和V均已存在，

且T是非空串。

操作結(jié)果：

用V替換主串S中出現(xiàn)

的所有與（模式串）T

相等的不重疊的子串。19

Replace(&S,T,V例如：假設(shè)S=abcaabcaaabca，T=bca若V=

x，則經(jīng)置換后得到S=axaxaax若V=bc，則經(jīng)置換后得到S=abcabcaabc20例如：假設(shè)S=abcaabcaaabca，T

StrInsert(&S,pos,T)

初始條件：串S和T存在，1≤pos≤StrLength(S)。

操作結(jié)果：在串S的第pos個字符之前插入串T。例如：S=chater，T=rac，則執(zhí)行StrInsert(S,4,T)之后得到S=character21StrInsert(&S,pos,T)

StrDelete(&S,pos,len)

初始條件：串S存在

1≤pos≤StrLength(S)-len。

操作結(jié)果：從串S中刪除位置pos

起長度為len的子串。

22StrDelete(&S,pos,lenClearString(&S)

初始條件：串S存在。

操作結(jié)果：將S清為空串。

23ClearString(&S)

初始條件：

對于串的基本操作集可以有不同的定義方法，在使用高級程序設(shè)計語言中的串類型時，應(yīng)以該語言的參考手冊為準(zhǔn)。

gets(str)輸入一個串；

puts(str)

輸出一個串；

strcat(str1,str2)串聯(lián)接函數(shù)；

strcpy(str1,str2)

串復(fù)制函數(shù)；

strcmp(str1,str2)串比較函數(shù)；

strlen(str)求串長函數(shù)；

char*strstr(char*s,char*sub)

如果找到子串，返回該位置的指針。如果找不到，則返回空指針。-C語言程序設(shè)計-附錄C例如：C語言函數(shù)庫中提供下列串處理函數(shù)：24對于串的基本操作集可以有不同的定義方法，在使用高級在上述串類型定義的13種操作中，串賦值StrAssign、串復(fù)制Strcopy、串比較StrCompare、求串長StrLength、串聯(lián)接Concat以及求子串SubString等六種操作構(gòu)成串類型的最小操作子集。

即：這些操作不可能利用其他串操作來實(shí)現(xiàn)，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個最小操作子集上實(shí)現(xiàn)。25在上述串類型定義的13種操作中，25例如，可利用串比較、求串長和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。pos<=i<=n-mSubString(sub,S,i,StrLength(T))StrCompare(sub,T)

?

0

S串T串

T串iposn-m算法的基本思想為：26例如，可利用串比較、求串長和求子串等操作實(shí)現(xiàn)定位函數(shù)int

Index(StringS,StringT,intpos){

//T為非空串。若主串S中第pos個字符之后存在與T相等的子串，則返回第一個這樣的子串在S中的位置，否則返回0

if(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;

else

returni;//S中的第一個與T相等子串的位置

}

//while

}

//if

return

-1;//S中不存在與T相等的子串}//Index27intIndex(StringS,StringT串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。

串的基本操作和線性表有很大差別。

在線性表的基本操作中，大多以“單個元素”作為操作對象；在串的基本操作中，通常以“串的整體”作為操作對象。28串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別串的基本操5.2串的表示和實(shí)現(xiàn)295.2串的表示和實(shí)現(xiàn)29在程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。30在程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則一、串的定長順序存儲表示二、串的堆分配存儲表示三、串的塊鏈存儲表示（在存儲結(jié)構(gòu)的層面討論串的操作）31一、串的定長順序存儲表示二、串的堆分配存儲表示三、串的塊鏈存一、串的定長順序存儲表示

如果利用C語言的串類型描述算法，可用一組連續(xù)的存儲單元存放串的字符序列，并以‘\0’為結(jié)束標(biāo)志。使用C語言的字符數(shù)組來存儲字符串。如，chars[]="abc";//字符串的長度為3chara[10];//字符串最大串長為9

32一、串的定長順序存儲表示如果利用C語言的串類型描述算法

按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時，其基本操作為“字符序列的復(fù)制”串的實(shí)際長度可在這個預(yù)定義長度的范圍內(nèi)隨意設(shè)定，超過預(yù)定義長度的串值則被舍去，稱之為“截斷”串的定長順序存儲操作特點(diǎn):33按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時，其基本操作為“字符序void

concat_sq(char

s1[],char

s2[],char

t[

])

{

int

j=0,k=0;

while(s1[j]!='\0')

t[k++]=s1[j++];//復(fù)制S1

j=0;

while(s2[j]!=‘\0’)t[k++]=s2[j++];

//接著復(fù)制S2

t[k]='\0';//增加結(jié)束符}例如：串的聯(lián)接操作concat34voidconcat_sq(chars1[],charvoidmain(){

char

s1[]="china";

char

s2[]="beijing";

char

t1[13];

//順序分配定長空間

concat(s1,s2,t1); cout<<t1<<endl;}定長分配體現(xiàn)在調(diào)用程序35voidmain(){定長分配體現(xiàn)在調(diào)用程序35typedefstruct{char*ch;

//若是非空串，則按串長分配存儲區(qū)，//否則ch為NULL

int

length;//串長度

}

HString;二、串的堆分配存儲表示如果完全用偽碼描述算法，可進(jìn)行類型定義：36typedefstruct{二、串的堆分配存儲表示如果直接用C語言描述算法，可通過函數(shù)new和delete為用戶進(jìn)行串值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。

本書采用這種方式。

這類串操作實(shí)現(xiàn)的常用思路：先為新生成的串分配一個存儲空間，然后進(jìn)行串值的復(fù)制。37如果直接用C語言描述算法，可通過函數(shù)new和deleconcat

操作substring

操作串的堆分配存儲表示實(shí)現(xiàn)38concat操作substring操作串的堆分配存儲表示void

concat(char*s1,char*s2,char*&t){

inti=0,j=0;

t=new

char[strlen(s1)+strlen(s2)+1];//為t分配堆空間

while((t[i]=s1[i])!='\0')i++;

while((t[i]=s2[j])!='\0'){i++;j++;

}

}39voidconcat(char*s1,char*s2voidmain()

{

char*s1="china";

char*s2="beijing";

char*t1;//僅說明類型而不申請空間concat(s1,s2,t1);

cout<<t1<<endl;}調(diào)用程序無需預(yù)先申請空間40voidmain(){調(diào)用程序無需預(yù)先申請空間40

void

substring(char*&sub,char*s,intpos,intlen){char*p;

intk,slen=strlength(s);

if(pos<0||pos>slen-1||len<0||len>slen-pos)

ERRORMESSAGE(“參數(shù)不合法”);sub=new

char[len+1];//為sub分配堆空間p=s+pos-1;k=len;

while(k){*sub++=*p++;k--;

}*sub='\0';sub=sub-len;}41voidsubstring(char*&sub,c5.3正文模式匹配425.3正文模式匹配42先前，曾介紹過串匹配(查找)的操作INDEX(S,T,pos)在實(shí)際應(yīng)用中，串的匹配查找操作使用的機(jī)會很多，現(xiàn)專門討論該算法。使用串的有關(guān)操作實(shí)現(xiàn)了INDEX，但在效率上仍有改進(jìn)的余地。43先前，曾介紹過串匹配(查找)的操作INDEX(S,T

簡單算法（簡單的正文模式匹配算法）

以定長順序結(jié)構(gòu)表示串a(chǎn)baacababaacbcaababaacbaabaacabaacST演示模型：匹配成功！44簡單算法（簡單的正文模式匹配算法）abaacababaacint

Index_BF(charS[],charT[],intpos){

//返回子串T在主串S中第pos個字符之后的位置。若不存在，//則函數(shù)值為-1。其中，T非空，0≤pos≤StrLength(S)-1。i=pos;j=0;

while(S[i+j]!=‘\0’&&T[j]!=‘\0’)

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

else

{i++;j=0;}

//重新開始新一輪的匹配

if(T[j]!=‘\0’)returni;

elsereturn-1;}//Index_BF45intIndex_BF(charS[],charT[若找到S中所有和模式串T匹配的子串，只需多次調(diào)用Index_BF(charS[],charT[],intpos)匹配成功后,下一次的匹配起始位置為i+Strlength(T)Index_BF不是最精巧的模式匹配算法，但比較好理解，適合于一般的使用。46若找到S中所有和模式串T匹配的子串，只需多次調(diào)用Inde5.4正文編輯

━串操作應(yīng)用舉例47