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

第四章串學(xué)習(xí)要點

1了解串的基本操作，了解利用這些基本操作實現(xiàn)串的其它操作的方法；

2掌握在串的堆分配存儲結(jié)構(gòu)下，串的基本操作算法；

3掌握串的模式匹配算法；串也叫字符串，它是由零個或多個字符組成的字符序列。基本內(nèi)容

1串的有關(guān)概念串的基本操作

2串的定長順序存儲結(jié)構(gòu)，堆分配存儲結(jié)構(gòu)；

3串的基本操作算法；

4串的模式匹配算法;5串操作的應(yīng)用。

第四章串4.1串的基本概念4.2串存儲和實現(xiàn)4.3串的匹配算法4.4串操作應(yīng)用舉例第四章串4.1串的基本概念4.2串存儲和實現(xiàn)4.3串的匹配算法4.4串操作應(yīng)用舉例第四章串4.1串的基本概念4.2串存儲和實現(xiàn)4.3串的匹配算法4.4串操作應(yīng)用舉例第四章串4.1串的基本概念4.2串存儲和實現(xiàn)4.3串的匹配算法4.4串操作應(yīng)用舉例一、串的定義

1什么是串串是一種特殊的線性表，它是由零個或多個字符組成的有限序列，一般記作s=‘a(chǎn)1,a2,a3,...an’其中s----串名，a1,a2,a3,...an----串值串的應(yīng)用非常廣泛，許多高級語言中都把串作為基本數(shù)據(jù)類型。在事務(wù)處理程序中，顧客的姓名、地址；貨物的名稱、產(chǎn)地?？勺鳛樽址幚恚谋疚募械拿恳恍凶址纫部勺鳛樽址幚?。4.1串類型的定義下面是一些串的例子：

（1）a=‘LIMING’

（2）b=‘NANJINGUNIVERSITYOFSCIENCE&TECHNOLOGY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

說明：1)串中包含的字符個數(shù)，稱為串的長度。

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

2）串中所包含的字符可以是字母、數(shù)字或其他字符，這依賴于具體計算機所允許的字符集。2串的有關(guān)術(shù)語1）子串

串中任意連續(xù)的字符組成的子序列稱為該串的子串

例：c=‘DATASTRUCTURE’，f=‘DATA’f是c的子串2）子串的位置子串T在主串S中的位置是指主串S中第一個與T相同的子串的首字母在主串中的位置。例：S=‘a(chǎn)babcabcac’,T=‘a(chǎn)bc’子串T在主串S中的位置為33）串相等兩個串相等，當(dāng)且僅當(dāng)兩個串長度相同，并且各個對應(yīng)位置的字符都相同；3串的基本操作

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

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

功能：由串變量S復(fù)制得到串變量T；3）判空操作StrEmpty(S)

功能：若為空串，則返回TRUE，否則返回FALSE

4）串比較操作

StrCompare(S,T)

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

ClearString(&S)

功能：將S清為空串6）求串長操作StrLenght(&S)

7）串連接操作Concat(&T,S1,S2)

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

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

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

為子串；

9）求子串位置操作Index(S,T,pos)

功能：返回S中第pos個字符之后與T相同的子串的位置，若不存在返回010)串插入操作StrInsert(&S,pos,T)

功能：將串T插入到串S的第pos字符之前11）串刪除操作StrDelete(&S,pos,len)

功能：從串S中刪除第pos個字符起長度

為len子串12）串替換操作replace(&S,T,V)

功能：用V替換主串S中出現(xiàn)的所有與T相等的不重疊子串；4.2串的表示和實現(xiàn)一、串的存儲1定長順序存儲結(jié)構(gòu)定長順序存儲結(jié)構(gòu)類似于C語言的字符數(shù)組，以一組地址連續(xù)的存儲單元存放串值字符序列，其類型說明如下：#defineMAXSTRLEN255

TypedefunsignedcharSString[MAXSTRLEN+1]

2、堆分配存儲

堆分配存儲類似于線性表的順序存儲結(jié)構(gòu)，以一組地址連續(xù)的存儲單元存放串值字符序列，其存儲空間是在程序執(zhí)行過程中動態(tài)分配的。在C語言中，存在一個稱之為“堆”的自由存儲區(qū)，并由C語言的動態(tài)分配函數(shù)管理。利用函數(shù)malloc()為每個新產(chǎn)生的串分配一塊實際串長所需的存儲空間，若分配成功，則返回一個指向起始地址的指針，作為串的基址，同時，為了以后處理方便，將串長也作為存儲結(jié)構(gòu)的一部分。串的這種存儲結(jié)構(gòu)本教材中稱為堆分配存儲。

堆分配存儲的類型說明Typedef

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

intlength;//整型域：存放串長}Hstring;

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

以上兩種存儲表示通常為高級程序設(shè)計語言所采用。由于堆分配存儲結(jié)構(gòu)的串既有順序存儲結(jié)構(gòu)的特點，處理方便，操作中對串長又沒有任何限制，更顯靈活，因此在串處理的應(yīng)用程序中常被采用。以下我們給出在堆分配存儲結(jié)構(gòu)下，串的部分基本操作算法。二串基本操作算法串賦值算法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串常量根據(jù)串常量的長度動態(tài)分配存儲空間a1a2anchars01n-1傳遞數(shù)據(jù)T.chT.length01n-1a1a2an串賦值操作圖示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

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

串連接算法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

s1.ch01n1-1s1.lengthn1s2.ch01n2-1s2.lengthn2串s1串s2進行串的合并s.ch01n1-1n1n1+n2-1

s.lengthn1+n2串連接圖示求子串算法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{//復(fù)制子串

Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];

Sub.length=len;}returnOK;}SubStringlen動態(tài)分配存儲空間01n-1pos-1S.lengthS.chn01Sub.chLen-1Sub.length01Sub.chLen-1Sub.lengthlen串插入算法StrInsert(HString&S,intpos,HStringT){//為串S重新分配大小等于串S和串T長度之和的存儲空間，//將S和T串值復(fù)制到新分配存儲空間中;if(pos<1||pos>S.length+1)returnERROR;//參數(shù)不合法if(T.lenght){//若T非空，為串S重新分配存儲空間,并插入Tif(!(S.ch=(char*)realloc((S.ch,S.length+T.length)*sizeof(char))));

exit(OVERFLOW);

for(i=S.length-1;i>=pos-1;--i)

S.ch[i+T.length]=S.ch[i];//將S的第pos個字符及后面的字符后移，為插入T騰出位置S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入T

S.length+=T.length;}returnOK;}SubStringS.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1為串S重新分配存儲空間,并將S復(fù)制到新空間將S的第pos個字符及后面的字符后移，為插入T騰出位置插入T修改串長串替換算法Replace(HString&S,HStringT,HStringV){//V.length==T.lengthpos=1;while(pos<S.length){

i=pos;j=1;

while(i<S.length&&j<T.length){

if(S.ch[i]==T.ch[j]){++i;++j}

else{i=i-j+2;j=1}}//whileif(j>T.length)S.ch[i-T.length..i-1]=V[0..V.length-1];pos=i;}//whilereturnOK;}//Replace3.串的鏈?zhǔn)酱鎯?/p>

串也可以用鏈?zhǔn)酱鎯ΓY(jié)點中的每個數(shù)據(jù)元素是一個字符。每個結(jié)點可以放一個字符，也可以放多個字符。XDBAHnGABCD三串的其它操作

可以利用串的基本操作實現(xiàn)串的其它操作。例：用求串長、求子串等操作實現(xiàn)定位函數(shù)Index(S,T,pos)。

算法的基本思想：在主串S中第i(初值為pos)個字符開始，長度和T的長度相等的子串和T串進行比較，若相等，求得函數(shù)值i。否則i加1繼續(xù)比較。直到S中不存在和T相等的子串為止。

intindex(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;elsereturni;}//while}//ifReturnok}//index4.3串的模式匹配算法

求子串位置的定位函數(shù)

子串的定位操作通常稱作串的模式匹配（其中T被稱為模式串），是各種串處理系統(tǒng)中最重要的操作之一。下面給出一種模式匹配算法，在本算法中，串采用定長順序存儲結(jié)構(gòu)，其類型說明如下：#defineMAXSTRLEN255

TypedefunsignedcharSstring[MAXSTRLEN+1]

本算法中，分別利用計數(shù)指針i和j指示主串S和模式串T中當(dāng)前正待比較的字符位置。算法的基本思想是：從主串S的第一個字符起和模式的第一個字符比較之，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從主串的下一個字符起再重新和模式的字符比較之。依次類推，直至模式T中的每個字符依次和主串S中的一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)值為模式T中第一個字符在主串S中的序號，否則稱匹配不成功，函數(shù)值為零。圖4.3展示了模式和主串S的匹配過程。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后退(至當(dāng)前匹配起始位置的//下一位置）重新開始匹配}if(j>T[0])returni-T[0];//匹配成功，返回子串T的位置elsereturn0;}//Index例S=‘a(chǎn)babcabcac’T=‘a(chǎn)bc’pos=4index(S,T,pos)返回值為6第一趟匹配ababcabcacbabi=3

abcj=3第二趟匹配ababcabcacbabi=2

aj=1第三趟匹配ababcabcacbabi=7

abcacj=5第四趟匹配ababcabcacbabi=4

aj=1第五趟匹配ababcabcacbabi=5

aj=1第六趟匹配ababcabcacbabi=11

abcacj=6匹配成功4.4串操作應(yīng)用舉例文本編輯程序

文本編輯程序是一個面向用戶的系統(tǒng)服務(wù)程序。它的基本操作包括串的插入、刪除、查找。

在緩沖區(qū)中順序存放文本文件，但是文本編輯程序要經(jīng)常的插入、刪除字符。這兩種操作都會引起文件內(nèi)所有字符的移動。要全部順序存儲，處理速度就會非常低。通常的方法是建立兩張表：行表（行號、首地址、長度）和頁表（頁號、首行號）。

1）在讀入文件過程中建立行表和頁表換行符：登記當(dāng)前行長度、準(zhǔn)備新行號及記錄首地址。換頁符：除了做換行符要做的工作外，還要建立新的頁記錄。2）刪除字符：修改行表中對應(yīng)記錄的長度字段。3）插入字符：檢查插入行有無空間來插入字符有：修改行表中長度字段，插入字符。無：將該行移到適當(dāng)位置，并修改行表中對應(yīng)記錄的行首地址、長度字段，插入字符。

4）插入行：修改行表中涉及到的行號，行表中插入新記錄。5）刪除行：刪除行表中對應(yīng)記錄修改所涉及到的行號。插入行和刪除行的操作有可能需要修改頁號。

以上只是粗略的框架，實現(xiàn)文本編輯程序時需要考慮諸多細節(jié)問題。

建立詞索引表

信息檢索是計算機應(yīng)用的重要領(lǐng)域之一，提高信息檢索的效率是信息檢索要解決的重要問題，解決效率問題的方法通常是建立索引。例如圖書館書目檢索系統(tǒng)，我們可以按書名、作者名和分類號建立索