《數(shù)據(jù)結構-C語言描述》課件第5章

第5章字符串和廣義表5.1字符串5.2*廣義表習題55.1字符串5.1.1字符串ADT

字符串(string，簡稱為串)是由n(n≥0)個字符組成的有限序列，記為s="a0a1…an－1"其中，s是串名，雙引號括起來的字符序列是串s的值，n是串中字符的個數(shù)，又稱為串長度。n=0的串稱為空串。要注意區(qū)分空串和空白串：空串不包括任何字符，空白串包括空格符。

串中任意連續(xù)個字符組成的子序列稱為該串的子串(substring)，包含子串的串稱為主串。通常以子串的首字符在主串中的位置作為子串在主串中的位置。與數(shù)組的情況類似，許多程序設計語言引入了串的概念，在不同程度上提供了字符串的處理能力。FORTRAN語言中的串是直接量，標準PASCAL、C/C++語言中是將字符串作為字符數(shù)組來處理的。但是許多語言的編譯器通過庫函數(shù)的方式，向用戶提供了豐富的字符串函數(shù)。C語言也在string.h中提供了許多字符串處理函數(shù)。SNOBOL語言是一種專門面向字符串處理的程序設計語言，它有豐富的串運算函數(shù)。因此，我們可以認為字符串是許多程序設計語言已經(jīng)實現(xiàn)的數(shù)據(jù)結構。作為一種數(shù)據(jù)結構，字符串是一種線性數(shù)據(jù)結構，但它不同于線性表，因為組成字符串的元素是字符，在存儲表示上有其特殊性。線性表上的運算大都是針對單個元素的，而字符串運算往往是以子串為單位進行的(見ADT5－1)，因此，將字符串作為單獨的數(shù)據(jù)結構進行研究是有必要的。我們同樣可以將字符串定義為一個抽象數(shù)據(jù)類型。ADT5－1中定義了一組常用的字符串運算，當然，我們還可以定義其他運算，以提供更多的字符串操作功能。ADT5－1String{數(shù)據(jù)：零個或多個字符的有限序列，其最大允許長度為MaxString。運算：

voidCreateString(String*s,intmaxsize);

后置條件:構造一個空串。

intLength(Strings)

后置條件:函數(shù)值返回字符串s的長度。

voidClear(String*s)

后置條件:字符串*s成為空串。

voidCopy(Stringp，String*s)

后置條件:字符串*s有串p的值。

BOOLInsert(String*s,Stringp,intpos)

后置條件：若0≤pos≤Length(*s)，且Length(*s)+Length(p)≤maxsize，則串*s為在位置pos－1和pos之間插入串p后得到的串，其長度為Length(*s)+Length(p)，并且函數(shù)返回TRUE，否則函數(shù)返回FALSE。

BOOLRemove(String*s,intpos，intlen)

后置條件：若0≤pos<Length(*s)，且Length(*s)-pos>len，則串*s為從位置pos開始刪除了長度為len的子串后所得到的串，其長度為Length(*s)-len，并且函數(shù)返回TRUE，否則函數(shù)返回FALSE。

StringSubString(Strings,intpos，intlen)

后置條件：若0≤pos<Length(*s)，且Length(*s)-pos>len，則返回串*s中從位置pos開始，長度為len的子串，否則返回空串。

intIndex(Strings,Stringp,intpos)

后置條件：若0≤pos<Length(*s)，則函數(shù)值是大于等于pos的最小整數(shù)k，使得串p與串s中從位置k開始，長度為Length(p)的子串相等，并且函數(shù)返回k，否則函數(shù)返回－1。

}5.1.2字符串的存儲表示

1.串的順序表示串的順序表示是指把串中的字符順序地存儲在一片連續(xù)的空間中。在按字節(jié)編址的機器中，每個字符占一個字節(jié)。在按字編址的機器中，可采用壓縮形式來存放。所謂壓縮形式，就是根據(jù)各機器字的長度，盡可能將多個字符存放在一個字中。而非壓縮形式則是不論機器字的長短，每個字只放一個字符。顯然壓縮形式節(jié)省了空間，但卻不易實現(xiàn)字符串運算，非壓縮形式的特點正相反。

一般來講，字符串有定義長度，這是該字符串運算中的最大允許長度。一個字符串還有它當前的實際長度。指示一個串的實際長度可以有不同的做法。PASCAL語言在字符數(shù)組的位置為0的字節(jié)中直接存放該字符串的長度，C語言則以“\0”指示字符串結束，見圖5－1。圖5－1字符串的順序表示(字節(jié)編址)(a)PASCAL字符串存儲方式；(b)C語言字符串存儲方式

2.串的鏈接表示串也可以用單鏈表存儲，每個結點可以存放一個字符，見圖5－2(a)。這種方法處理簡便，但存儲空間利用率不高。每個結點也可存放多個字符，見圖5－2(b)(@作為字符串的結束標志)，這種做法可以提高空間利用率，但實現(xiàn)字符串操作的難度加大了。圖5－2字符串的鏈接表示

(a)每個結點存1個字符；(b)每個結點存4個字符

由于字符串是許多程序設計語言已實現(xiàn)的數(shù)據(jù)類型，如C語言在string.h中提供了許多字符串處理函數(shù)，此外，有了前幾章學習線性數(shù)據(jù)結構的基礎，無論字符串采用鏈接表示還是順序表示，實現(xiàn)ADT5－1中定義的大多數(shù)字符串操作都不會很困難，所以下面我們只討論串的模式匹配算法。5.1.3簡單模式匹配算法

設有兩個字符串s和p，稱在串s中找串p的過程為模式匹配(patternmatching)。這里，s為主串，p為子串，又稱為模式(pattern)。模式匹配最普遍的應用是在文本編輯器中查找子串。如WORD中的查找(Find)、替換(Replace)和定位(Locate)等命令都涉及到模式匹配問題。實現(xiàn)模式匹配最方便的方法是使用C語言在string.h中提供的函數(shù)strstr。看下面的例子。【程序5－1】C語言的strstr函數(shù)。#include<stdio.h>#include<string.h>voidmain(){ charp[10]="abc",s[10]="cdabcde",*t; if(t=strstr(s,p))printf("Thestringfromstrstris:%s\n",t); elseprintf("Thepatternwasnotfoundwithstrstr\n");}

程序5－1完成的功能是：如果模式串p在串s中，則指針t指向串p在串s中的第一個字符，并打印串s中從t指向的字符開始的字符串a(chǎn)bcde。雖然C語言的函數(shù)strstr可以實現(xiàn)模式匹配，但并非所有的語言都提供這樣的函數(shù)，也并非C語言的所有編譯器都提供這樣的函數(shù)。此外，模式匹配可有不同的方法，不同的方法有不同的效率。所以討論字符串的模式算法，仍然是很有意義的。

模式匹配的最簡單的做法是從主串s中位于pos的字符開始，與模式串p的位置為0的字符開始比較。如果兩字符相等，則繼續(xù)比較下一個字符；如果在逐次比較中，串s的當前字符與串p的當前字符不相等，則該趟匹配失敗。下一趟比較中，串s從位置pos+1的字符開始，串p從起始字符開始，繼續(xù)下一趟匹配。如果匹配再次失敗，比較從串s中位置為pos+2的字符，串p仍回到起始字符，進行下一趟匹配。依此類推，直到或者匹配成功，或者匹配失敗為止。如果匹配成功，函數(shù)返回串p在串s中的起始字符的位置，否則函數(shù)返回－1。這種模式匹配方法稱為簡單匹配算法。圖5－3和圖5－4分別為簡單匹配算法的匹配成功和匹配失敗的例子。圖5－3簡單匹配算法舉例(匹配成功)(a)第一趟；(b)第二趟；(c)第三趟；(c)匹配成功圖5－4簡單匹配算法舉例(匹配失敗)(a)第一趟；(b)第二趟；(c)以后的匹配都失?。?c)匹配失敗

程序5－2實現(xiàn)了簡單匹配算法。該程序是在如下描述的字符串順序表示下實現(xiàn)的。#defineMaxSize256typedefstructstring{charchs[MaxSize];intLength,MaxString;}String;【程序5－2】簡單匹配算法。intIndex(Strings,Stringp,intpos){ inti=pos; char*ps=s.chs+i,*pp=p.chs;if(pos<0||pos>=s.Length){ printf("Outofbounds!");return-1;}while(*pp!='\x0'&&s.Length-i+1>=p.Length)if(*ps++!=*pp++){ps=s.chs+(++i);pp=p.chs; }if(*pp=='\x0')returni;return-1;}

程序5－2中，定義了兩個字符指針ps和pp，ps指向串s中當前比較的字符，pp指向串p中當前比較的字符。在某趟比較中，串s中起始比較的字符的位置保存在變量i中，如在圖5－3(d)中，第四趟比較是從串s中位置為I=3的字符開始的。由于字符串以字符數(shù)組形式存儲，所以串s和串p的起始地址分別為s.chs和p.chs。ps=s.chs＋i，I=pos和pp=p.chs分別指向兩串中起始比較的兩字符。當條件*pp=='\x0'或s.Length－i＋1<p.Length成立時，結束while循環(huán)。前一個條件成立意味著匹配成功，返回i；后一個條件成立意味著匹配失敗。在while循環(huán)中，表達式(*ps++!=*pp++)比較ps和pp所指向的兩字符是否相等，并使指針ps和pp分別進一。如果兩字符相等，則繼續(xù)進行以后的比較；若不相等，則下一趟將是串s中位置為++i的字符(即ps=s.chs+(++i))與串p的首字符(即pp=p.chs)進行比較。

設主串和模式串的長度分別為n和m，while循環(huán)最多進行n－m+1趟，每趟最多比較m次，這樣總的比較次數(shù)最多是(n－m+1)×m。由于(n－m+1)×m≤n×m，因此簡單模式匹配算法在最壞情況下的時間復雜度是O(n×m)。例如：n=14,m=4,設s＝"aaaaaaaaaaaaab"，p="aaab"，while循環(huán)執(zhí)行14－4+1趟，每趟比較4次。5.1.4*模式匹配的KMP算法我們看到在簡單匹配算法中，當主串和子串的字符比較不相等時，主串的字符指針ps需返回本趟開始處的下一個字符，而子串的指針pp則回到子串的起始字符，這種回溯顯然是費時的。如果仔細觀察，可以發(fā)現(xiàn)這樣的回溯常常不是必須的。由D.E.Knuth、J.H.Morris和V.R.Pratt三人提出的KMP算法，盡可能地避免不必要的回溯，實現(xiàn)字符串的高效的模式匹配。在KMP算法中，主串指針ps始終無須回溯，子串指針pp返回到前面的什么位置，視情況而定。請看圖5－5所示的例子。圖5－5考察簡單匹配算法簡單匹配算法；(b)第一趟比較失配；(c)考察模式串p；(d)下一趟比較的起始位置

圖5－5(a)表示按照簡單匹配算法進行模式匹配的過程。圖5－5(b)表明了第一趟比較在s6失配，但前6個字符是兩兩相等的。圖5－5(c)考察子串p的子串“p0p1...p5”=“abaaba”，我們發(fā)現(xiàn)子串①和②不相等，③和④不相等，但⑤和⑥相等，所以，圖5－5(a)的簡單匹配算法的第二、三趟比較是注定會失配的，因而是多余的。從圖5－5(d)中我們可以看到，子串⑤、⑥和⑦三者相等，所以，很顯然圖5－5(a)的第四趟比較可以不必從p0開始，而直接從p3開始與s6比較。也就是說，如果對于子串p有：①(②，③(④且⑤=⑥，則第二趟比較就可以從p3與s6的比較開始。這也意味著主串指針ps無須回溯，而子串指針pp回溯到什么位置取決于串p自身的特性。

現(xiàn)在來看一般情況。設主串s="s0s1…sn－1"，模式串p="p0p1…pm－1"，并設字符比較在si≠pj處失配。如果考察p串，發(fā)現(xiàn)p0p1…pk－1=pj－kpj－k+1…pj－1

p0p1…pj－1的前綴子串，pj－kpj－k+1…pj－1

是p0p1…pj－1的后綴子串。由于匹配在si≠pj處失敗，所以必有pj－k…pj－2pj－1=si－k…si－2si－1因此

p0…pk－2pk－1=si－k…si－2si－1那么，下一趟比較可以從si和pk處開始。

1.失敗函數(shù)的定義

失敗函數(shù)f(j)的值指示當比較在pj處失配時，下一趟比較應從子串p的哪個字符處開始。定義5－1

設有長度為m的模式串p=p0p1…pm－1，失敗函數(shù)f定義為：

－1(當j=0時)f(j)=max{k|0＜k＜j且p0p1…pk－1=pj－kpj－k+1…pj－1}存在

0(其他情況)(5－1)

設比較在si、pj處失敗，f(j)≥0表示下一趟比較從si與pf(j)處開始；f(j)=－1表示p0

si,下一趟比較應從p0與si＋1開始。表5－1是失敗函數(shù)的例子。表中，f(7)=4表示在子串p0p1...p6中，最長的且相等的前綴子串和后綴子串的長度是4。如果比較在p7失敗，那么下趟比較從p4開始。表5－1失敗函數(shù)的例子j012345678910Pabcabcabbacf(j)－10001234501

2.KMP算法的C程序如果模式串p的失敗函數(shù)的值已經(jīng)計算出來，那么實現(xiàn)KMP算法就很簡單。與簡單匹配算法相似，當si

pj時，KMP算法接著比較si與pf(j)，即先令j=f(j)，再比較si與pj。有一種特殊的情況需單獨處理，那就是當f(j)=－1時，應令si與p0比較，也就是說，應使i=i+1,j=0(即實施運算i++，j++)，如程序5－3所示?！境绦?－3】KMP算法的C程序。intIndex_KMP(Strings,Stringp,intpos){inti=pos,j=0;intn=s.Length,m=p.Length;while(i<n&&j<m) if(j==-1||s.chs[i]==p.chs[j]){ i++;j++; }

elsej=f[j];return((j==m)?i－m:－1);}圖5－6KMP模式匹配舉例

(a)主串s和模式串p；(b)在j=7處失配；(c)比較從j=f(7)=4處開始

(d)比較從j=f(4)=1開始；(e)匹配成功

現(xiàn)在分析Index_KMP算法。該算法中，if(j==－1||s.chs[i]==p.chs[j])語句的執(zhí)行次數(shù)最多，我們以它的執(zhí)行次數(shù)來計算算法的時間復雜度。if語句有兩個分支：(1)i++;j++;；(2)j=f[j];。

if語句的執(zhí)行次數(shù)是這兩個分支執(zhí)行次數(shù)的和。

分支(1)中，i的初值為pos(pos≥0)，因i<n，因此，分支(1)最多執(zhí)行n次。分支(2)中，j的初值為0，執(zhí)行語句j=f[j]后，由于f[j]<j，j在分支(2)中只減不增，只在分支(1)中增1，并只當j≥0時，才會執(zhí)行分支(2)，因此分支(2)的執(zhí)行次數(shù)不會超過分支(1)。所以if語句的執(zhí)行次數(shù)不會超過2n，KMP算法的時間復雜度為O(n)。

3.計算失敗函數(shù)下面討論失敗函數(shù)的計算方法。計算f(j)就是對子串p0p1…pj－1求最長的且相等的前綴子串和后綴子串的長度。如果這種計算是費時的，則KMP算法不會給我們帶來節(jié)省時間的好處。幸運的是我們能夠設計出快速計算f(j)的算法。我們知道，總有f(0)=－1。如果已經(jīng)計算出f(j)(0≤j＜m－1)，如何計算f(j+1)呢?

為了求f(j+1)，根據(jù)定義，我們需要求得p0p1…pj的最長的且相等的前綴子串和后綴子串的長度k，即max{k|0＜k≤j且p0p1…pk－1=pj－k+1pj－k+2…pj}。

設f(j)=h，我們有p0p1…ph－1=pj-hpj-h+1…pj－1。

(1)若ph＝pj，則表明p0p1…ph=pj－h(huán)pj－h(huán)+1…pj，并且不可能有h'>h，使得p0p1…ph'=pj－h(huán)'

pj－h(huán)'+1…pj，所以，有f(j+1)=h+1。

(2)若ph

pj，則表明p0p1…ph'

pj－h(huán)pj－h(huán)+1…pj。設f(h)=g，考察pg

是否與pj相等，如果相等，則意味著p0p1…pg=pj－gpj－g+1…pj，有f(j+1)=g+1，依此類推。這一過程可看成是主串和模式串都是串p的模式匹配過程。

由此我們可得到計算失敗函數(shù)f(j)的遞推公式：其中，f1(j)=f(j),fm(j)=f(fm－1(j))。根據(jù)上述分析，我們得到程序5－4的計算失敗函數(shù)值的C程序。

【程序5－4】失敗函數(shù)的C程序。voidFail(Stringp,int*f){

intj=0,k=-1; f[0]=－1; while(j<p.Length) if(k==-1||p.chs[j]==p.chs[k]){ j++;k++; f[j]=k; }elsek=f[k];}

4.改進的失敗函數(shù)的C程序失敗函數(shù)可以通過改進，進一步提高效率。從圖5－6可以看出，在第1趟匹配到達失配點時，s7='a'，p7='b'，s7≠p7，取j=f(j)=4，即下一趟從p4開始與s7繼續(xù)比較。由于p4=p7='b'，因此p4≠s7，此趟回溯到j=4仍然是多余的；同理回溯到j=1也是多余的，可以直接回溯到j=0。這就是說，如果在求得f(j)為k值后，若有pk

pj，可令f(j)=k，否則令f(j)=f(k)。改進的失敗函數(shù)的例子見表5－2。改進的失敗函數(shù)的C程序見程序5－5。表5－2改進的失敗函數(shù)的例子j012345678910Pabcabcabbacf(j)－100－100－105－11【程序5－5】改進的失敗函數(shù)的C程序。voidFail2(Stringp,int*f){intj=0,k=－1;f[0]=－1;while(j<p.Length) if(k==－1||p.chs[j]==p.chs[k]){ j++;k++;if(p.chs[j]==p.chs[k])f[j]=f[k];elsef[j]=k; }elsek=f[k];}5.2*廣義表5.2.1廣義表的概念

廣義表(generalizedlists)又稱為列表(lists，這里用復數(shù)形式以示與一般線性表的區(qū)別)，是零個或多個元素的有序序列。廣義表的元素或者為原子(atom)，或者為廣義表。廣義表記作LS=(x0,x1,…,xn－1)，其中，xi稱為表元素。

原子可以是任何在結構上不可分割的數(shù)據(jù)元素。作為廣義表中元素的廣義表稱為子表。表結構被廣泛用于人工智能等領域。表處理語言LISP把廣義表作為基本數(shù)據(jù)結構，就連程序也表示成一系列的廣義表。顯然，上面給出的廣義表的定義是一個遞歸的定義。通常用圓括號將廣義表括起來，用逗號分隔表中元素。為了區(qū)分原子和子表，在下面書寫中，我們約定：用大寫字母表示表(或子表)，用小寫字母表示原子。例如：E=()G=(E)=(())L=(a，b)A=(x，L)=(x，(a，b))B=(A，y)=((x,(a，b))，y)C=(A，B)=((x，(a，b))，((x，(a，b))，y))D=(z，D)=(z，(z，(z，(…))))F=((r，s，t))H=(A，B，C，D)

一個廣義表中所包含的元素(包括原子和子表)的個數(shù)稱為該廣義表的長度。長度為零的表是空表。例如，上面例子中表E是空表，它不包含任何元素，但注意表G不是空表，它有一個空表作為其惟一的元素，所以其長度為1。表L、A、B、C的長度都是2，但F的長度是1，它包含一個子表，該子表的長度是3。從廣義表的定義和給出的例子可以得到廣義表的下列重要性質(zhì)：

(1)廣義表的元素可以是原子，也可以是子表，而子表的元素還可以是子表……。因此，廣義表是一種多層次的數(shù)據(jù)結構。當用圓括號表示廣義表時，一個表的深度是指表中所包含的括號的層數(shù)。例如表L的深度是1，而表A的深度是2?？毡硪彩菑V義表，其深度為1。(2)廣義表可以是遞歸的表。廣義表的定義并沒有限制元素的遞歸，即廣義表也可以是其自身的子表。例如表D就是一個遞歸的表。

(3)廣義表可以為其他表所共享。例如表A和表B是表C的共享子表。在C中可以不必列出子表的值，而用子表的名稱來引用。廣義表可以看成是線性表的推廣，而線性表是廣義表的特例，即深度為1的廣義表，但廣義表與線性表還有著重要的差別。

如果規(guī)定任何表都是有名的表，則為了既標明每個表的名字，又說明它的組成，可以將表的名字寫在本表對應的括號前，于是上面的廣義表可以分別寫成：E()G(E())L(a，b)A(x，L(a，b))B(A(x,L(a，b))，y)C(A(x，L(a，b))，B(A(x，L(a，b))，y))D(z,D(z，D(…)))……5.2.2廣義表ADT

一個廣義表的第一個元素稱為頭部(head)，其余元素組成尾部(tail)。求表的頭部和尾部是廣義表的兩個最基本的操作。此外，在廣義表上可以定義與線性表類似的一些操作，如建立、插入、刪除、拆開、連接，以及復制、遍歷、嵌套信息的輸入和輸出等。ADT5－2列出了部分廣義表的運算。LISP語言提供了豐富的廣義表函數(shù)。ADT5－2Lists{數(shù)據(jù)：是零個或多個元素的原子或子表所組成的有序序列，n是表長。運算：

voidCreateLists(Lists*lst);

根據(jù)廣義表的書寫形式創(chuàng)建一個廣義表。

BOOLIsEmpty(Listslst)

若廣義表為空，則返回TRUE，否則返回FALSE。

intSize(Listslst)

返回廣義表的長度。intDepth(Listslst)

返回廣義表的深度。

ListsHead(Listslst)

返回廣義表的頭部。

ListsTail(Listslst)

返回廣義表的尾部。

voidClear(Lists*lst);

移去所有元素，廣義表成為空表。}5.2.3廣義表的存儲表示由于廣義表的數(shù)據(jù)元素可以是原子，也可以是廣義表，因此它難以用順序存儲結構表示，通常都采用鏈接存儲結構表示。一種做法是將結點分成兩類：原子結點和子表結點，每類結點都有三個域，其中有一個標志域Tag，Tag=0表示該結點是原子結點，否則是子表結點。原子結點包括：Tag、Atom和Tp。子表結點包括：Tag、Hp和Tp。域Tp是原子結點和子表結點共有的，它是指向廣義表的尾部的指針。原子結點的域Atom中存放原子的值，子表結點的域Hp指示子表的頭部。圖5－7為一種可能的廣義表的存儲結構。圖5－7廣義表的鏈接存儲表示廣義表結點類型GLNode的定義如下：typedefstructglnode{intTag;structglnode*Tp;union{charAtom;structglnode*Hp;};}GLNode;typedefstructLists{GLNode*first;}Lists;5.2.4廣義表的算法這里，我們只給出求廣義表深度的遞歸算法，并且約定所討論的廣義表是非遞歸表且無共享子表。設非空廣義表為：L=(a0,a1,…,an－1)，其中ai(i=0,1,…,n－1)或者為原子，或者為子表，則求表L的深度可分解為分別求表L中各數(shù)據(jù)元素的深度，若ai是原子，則其深度為0，否則求子表ai的深度?？毡淼纳疃葹?。這樣非空的廣義表L的深度是各子表深度的最大值加1。