《軟件技術(shù)基礎(chǔ)》課件第5章

5.1串及其運(yùn)算5.2串的存儲(chǔ)結(jié)構(gòu)5.3串的模式匹配算法5.4多維數(shù)組5.5矩陣的壓縮存儲(chǔ)習(xí)題5第5章串和數(shù)組5.1.1串的概念

串(String)是由多個(gè)或零個(gè)字符組成的有限序列，記做S="c1c2c3…cn"(n≥0)。其中，S是串名；由雙引號(hào)括起來的字符序列稱為串值，但雙引號(hào)本身不屬于串；ci(1≤i≤n)是串中字符，i是字符在串中的位置序號(hào)；n是串的長度，表示串中字符的個(gè)數(shù)，不包含任何字符的串稱為空串，例如""是長度為0的空串。5.1串?及?其?運(yùn)?算串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。子串在主串中的序號(hào)定義為子串在主串中首次出現(xiàn)的位置序號(hào)。例如，設(shè)S1和S2分別為

S1=“Thisisastring”S2=“is”

則S2是S1的子串，S1是S2的主串。S2在S1中出現(xiàn)了兩次，首次出現(xiàn)在主串的第3個(gè)位置上，因此S2在S1中的序號(hào)是3。

特別需要一提的是，空串是任意串的子串，任意串是其自身的子串。通常，串可以分為串變量和串常量。正如我們所知道的，在程序中常量只能被引用而不能改變其值，但變量的值可以被改變。在C++語言中，串變量可以用字符型數(shù)組來表示，串常量可以用雙引號(hào)括起來的字符序列直接表示或者用符號(hào)常量來表示，例如有如下定義：

charstr[]="string";constcharstr_const[]="string";

str是串變量，而str_const是串符號(hào)常量。5.1.2串的基本運(yùn)算

串的基本運(yùn)算和線性表有很大的差別。線性表的插入、刪除等運(yùn)算都是以“單個(gè)元素”作為操作對象；而對串的運(yùn)算，通常是把串作為一個(gè)整體進(jìn)行操作，如串的復(fù)制、串的比較、插入和刪除子串等。

很多高級語言都提供了字符串操作的函數(shù)庫，下面結(jié)合串的基本運(yùn)算給出C語言有關(guān)字符串操作函數(shù)的例子。我們先定義幾個(gè)相關(guān)的變量：

chars1[80]=“d:\\user\\wang\\”,s2[40]=“file.txt”,s3[80];//字符串中含有轉(zhuǎn)義字符‘\\‘

intresult;

說明：字符串從字符數(shù)組下標(biāo)為0的元素開始存放。例如：result=strcmp(“good”,“Good”); //result>0

result=strcmp(“15”,“15”); //result=0

result=strcmp(“That”,“The”); //result<0

(4)?StrCat(&T,S)——串聯(lián)接，將串S聯(lián)接到串T的末尾，返回指向串S的指針。

例如：printf(“%s”,strcat(s1,s2));

//輸出：d:\\user\\wang\\file.txt

(5)?StrStr(S,Sub)——子串定位，查找串Sub在串S中第一次出現(xiàn)的位置，若查找到，則返回該位置信息，否則返回NULL。

例如：printf("%d\n",strstr(s1,"user")-s1+1);//輸出4

(6)?StrChr(S,C)——字符定位，查找字符C在串S中第一次出現(xiàn)的位置，若查找到，則返回該位置信息，否則返回NULL。

例如：result=strchr(s2,‘t’)-s2+1;//result的值是6

上述操作是最基本的串運(yùn)算，其余的串運(yùn)算一般可以由這些基本運(yùn)算組合而成。

voidsubstr(char*sub,char*s,intpos,intlen)

{

if(pos<1||pos>strlen(s)||len<0)printf(“parametererror!\n”);

else{

strncpy(sub,s+pos-1,len); //復(fù)制子串字符

strcpy(sub+len,“\0”); //添加子串的串結(jié)束符

}

}

上述程序是C語言的完整程序。不同的語言對串運(yùn)算會(huì)有差異，因此應(yīng)以該語言的參考手冊為準(zhǔn)。5.2.1串的順序存儲(chǔ)

串的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序串。與順序表類似，順序串是用字符向量來存儲(chǔ)，并且在串的末尾用一個(gè)特定的字符作為串結(jié)束符，例如C語言中以轉(zhuǎn)義字符‘\0’作為串結(jié)束符。為了具有一般性，我們?nèi)匀话汛念愋投x為一個(gè)結(jié)構(gòu)類型，其中用一個(gè)一維字符型數(shù)組存放串值，并用一個(gè)整型量表示串的長度。串的類型定義如下：

#definemaxsize256

typedefstruct

{charch[maxsize];

intlength;

}SeqString;5.2串的存儲(chǔ)結(jié)構(gòu)

【例5.2】

編寫一個(gè)算法voidstrdelete(SeqString*S,intpos,intlen)，若滿足1≤pos≤S->length-len+1，則從串S中刪除第pos個(gè)字符開始長度為len的子串；否則不刪除。

voidstrdelete(SeqString*S,intpos,intlen)

{

chartemp[maxsize];

if(pos>=1&&pos<=S->length-len+1){

strncpy(temp,S->ch,pos-1);

strcpy(temp+pos-1,S->ch+pos+len-1);

strcpy(S->str,temp);

S->length=S->length-len;

}

}5.2.2串的鏈?zhǔn)酱鎯?chǔ)

和順序表類似，在順序串上不方便進(jìn)行插入、刪除操作，需要移動(dòng)大量的元素。采用鏈表存儲(chǔ)串值可以提高插入、刪除的效率，串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈串。鏈串中的每個(gè)結(jié)點(diǎn)可以存放一個(gè)字符，若結(jié)點(diǎn)的指針域占4個(gè)字節(jié)，那么鏈串的存儲(chǔ)密度只有20%。如果每個(gè)結(jié)點(diǎn)存放多個(gè)字符，例如4個(gè)字符，則存儲(chǔ)密度可以達(dá)到50%，從而有效地提高了存儲(chǔ)空間的利用率。通常將每個(gè)結(jié)點(diǎn)存放字符的個(gè)數(shù)定義為結(jié)點(diǎn)大小，圖5.1(a)和(b)中的每個(gè)結(jié)點(diǎn)大小分別是1和4。一個(gè)結(jié)點(diǎn)可存放多個(gè)字符，而串長度不一定是結(jié)點(diǎn)大小的倍數(shù)，因此鏈表中最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域有可能沒有被串值占滿，可以用特殊的字符(例如'\0')來填充。圖5.1鏈串的示意圖鏈串結(jié)點(diǎn)的類型定義如下：

(1)結(jié)點(diǎn)大小為1。

typedefstructnode

{chardata;

structnode*next;

}LinkString;

(2)結(jié)點(diǎn)大小為4。

typedefstructnode

{chardata[4];

structnode*next;

}LinkString;子串定位又稱為串的模式匹配(PatternMatching)，是串運(yùn)算中最重要的操作之一。所謂模式匹配，就是在文本中查找是否存在給定的單詞及出現(xiàn)的位置，例如實(shí)現(xiàn)文本編輯程序中的查找功能。C語言函數(shù)庫中的子串定位函數(shù)strstr可以實(shí)現(xiàn)串的模式匹配操作，串的模式匹配算法分樸素的模式匹配和改進(jìn)的模式匹配兩種。5.3串的模式匹配算法5.3.1順序串上的模式匹配

樸素的模式匹配算法又稱為窮舉的模式匹配算法，假設(shè)S為目標(biāo)串(主串)，T為模式串(子串)，

S="s1,s2,…,sn"T="t1,t2,…,tm"其中0＜m≤n

在實(shí)際應(yīng)用中，模式串長度m通常遠(yuǎn)遠(yuǎn)小于目標(biāo)串長度n，即m<<n。下面給出不依賴其他串操作運(yùn)算的模式匹配算法。分別利用計(jì)數(shù)指針i和j指示目標(biāo)串S和模式串T中當(dāng)前比較的字符位序。算法的基本思想是：從目標(biāo)串S的第pos個(gè)字符開始與模式串T的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較后面的字符；否則，從目標(biāo)串的下一個(gè)字符開始與模式串的第一個(gè)字符進(jìn)行下一趟比較。重復(fù)此過程，直至模式串中的每個(gè)字符依次與目標(biāo)串中的一個(gè)連續(xù)的字符序列相等，則匹配成功，函數(shù)值為與模式串中第一個(gè)字符相等的字符在目標(biāo)串中的位序；如果各趟比較均不相等，則匹配不成功，函數(shù)值為0。從圖5.2可以看出模式串T="abc"與目標(biāo)串S="abbabca"?的匹配過程(pos=1)。圖5.2樸素的模式匹配過程現(xiàn)在分析算法的時(shí)間復(fù)雜度。在最壞情況下，假設(shè)每一趟都比較了m次才能夠確定對應(yīng)的字符是否均相等，共匹配了n-m+1趟，比較字符的總次數(shù)為m(n-m+1)，由于n>>m，因此時(shí)間復(fù)雜度是O(m*n)。樸素的模式匹配算法雖簡單，但效率較低，這是因?yàn)樵谝惶似ヅ渲心繕?biāo)串內(nèi)可能存在多個(gè)和模式串“部分匹配”的子串，而引起計(jì)數(shù)指針i的多次回溯。一種改進(jìn)的模式匹配算法的時(shí)間復(fù)雜度為O(m+n)。其改進(jìn)在于：每當(dāng)一趟過程中出現(xiàn)字符比較不等時(shí)，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的距離，再繼續(xù)進(jìn)行比較。具體算法讀者可參閱有關(guān)資料。5.3.2鏈串上的模式匹配

我們以結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)串，實(shí)現(xiàn)樸素的模式匹配算法。在算法中使用指針shift指向每一趟在目標(biāo)串中比較的起始位置，若一趟比較中出現(xiàn)不相等的字符，指針shift右移指向下一個(gè)結(jié)點(diǎn)，繼續(xù)下一趟的比較。若匹配成功，則返回shift所指向的結(jié)點(diǎn)地址；若匹配不成功，則返回空地址值。具體算法如下：矩陣廣泛用于科學(xué)計(jì)算與工程應(yīng)用中，在用高級語言編寫程序時(shí)，常常采用二維數(shù)組存儲(chǔ)矩陣。采用這種存儲(chǔ)方法時(shí)，不僅使矩陣運(yùn)算簡單，而且存儲(chǔ)密度高。但是，如果階數(shù)很高的矩陣中非零元素的分布具有一定的規(guī)律或者矩陣中有大量的零元素，則為了節(jié)省存儲(chǔ)空間，可以對這類矩陣進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)，就是為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不分配存儲(chǔ)空間。5.5矩陣的壓縮存儲(chǔ)5.5.1特殊矩陣

特殊矩陣是指n階方陣中非零元素或零元素的分布具有一定的規(guī)律。下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。

1．三角矩陣

在n階方陣中，以主對角線劃分，如果矩陣的下三角(不包括主對角線)中的元素均為值相同的常數(shù)，則稱為上三角矩陣，反之稱為下三角矩陣。在多數(shù)情況下，三角矩陣的常數(shù)為零。兩種三角矩陣如圖5.3所示。圖5.3三角矩陣圖5.4一個(gè)4階對稱方陣圖5.5一個(gè)4階對稱方陣的壓縮存儲(chǔ)

3．對角矩陣

所謂對角矩陣，是指方陣中的所有非零元素集中在以主對角線為中心的帶狀區(qū)域內(nèi)，帶狀區(qū)域之外的元素值均為零。帶寬為3的對角矩陣又稱為三對角矩陣，如圖5.6所示。圖5.6三對角矩陣將稀疏矩陣中的非零元素的行號(hào)、列號(hào)和元素值作為一個(gè)三元組(i，j，aij)，所有非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，則得到一個(gè)其結(jié)點(diǎn)均是三元組的線性表。我們將該線性表的順序存儲(chǔ)結(jié)構(gòu)稱為三元組表。在下面的討論中，三元組均以按行優(yōu)先的順序進(jìn)行排列。

在三元組表中除了要表示非零元素之外，還需表示矩陣的行數(shù)、列數(shù)及非零元素的總數(shù)。三元組表的結(jié)構(gòu)類型定義描述為設(shè)a為spmattrix型指針變量，圖5.7(a)所示的稀疏矩陣A的三元組表如圖5.7(b)所示。

下面以矩陣的轉(zhuǎn)置為例，說明采用三元組表的形式存儲(chǔ)稀疏矩陣時(shí)，如何實(shí)現(xiàn)矩陣的運(yùn)算。

一個(gè)m×n的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)n×m的矩陣，且A[i][j]=B[j][i]，0≤i≤m-1，0≤j≤n，即A的行是B的列，A的列是B的行。例如，圖5.7(a)中的A和圖5.8(a)中的B互為轉(zhuǎn)置矩陣。圖5.7稀疏矩陣A和它的三元素表?*a圖5.8稀疏矩陣B和它的三元素表?*b為了敘述方便，下面將三元組表*a中的成員a->data簡稱為三元組表，因?yàn)橄鄬τ谄渌蓡T而言，它是主要的。

將A轉(zhuǎn)置為B，就是將A的三元組表a->data置換為B的三元組表b->data，如果只是互換a->data中i和j的內(nèi)容，那么所得到的b->data是按列存放的矩陣B的三元組表，還必須重新排列b->data中各結(jié)點(diǎn)的順序。由于A的列是B的行，故按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->data必定是按行優(yōu)先的順序存放。算法的基本思想是：對a->data按列掃描n趟，在第col趟掃描中，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)、列號(hào)和元素值分別放入b->data的列號(hào)、行號(hào)和元素值中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。以圖5.7和圖5.8為例，設(shè)col=0，則掃描a->data找到列號(hào)為0的三元組依次是(0，0，3)和(2，0，2)，存入b->data后為(0，0，3)和(0，2，2)，恰好為B中第0行的兩個(gè)非零元素，只要依次取col=0，1，2，3，即可得到a->data的轉(zhuǎn)置矩陣b->data。下面給出具體的算法：該算法的時(shí)間主要耗費(fèi)在col和ano的二重循環(huán)上，算法的時(shí)間復(fù)雜度為O(n×t)。而通常用二維數(shù)組表示矩陣時(shí)，其轉(zhuǎn)置算法的時(shí)間復(fù)雜度是O(m×n)。如果非零元素個(gè)數(shù)大于矩陣的行數(shù)，則從轉(zhuǎn)置算法的時(shí)間復(fù)雜度來說，采用三元組表存儲(chǔ)就不合適了。

一、名詞解釋

串，順序串，鏈串，特殊矩陣，稀疏矩陣，對稱方陣，上(下)三角矩陣

二、填空題

1．含零個(gè)字符的串稱為______串，用______表示。其他串稱為______串。任何串中所含______的個(gè)數(shù)稱為該串的長度。

2．當(dāng)且僅當(dāng)兩個(gè)串的______相等并且各個(gè)對應(yīng)位置上的字符都______時(shí)，這兩個(gè)串相等。一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串的______串，該串稱為它所有子串的______串。習(xí)題5

3．通常將鏈串中每個(gè)存儲(chǔ)結(jié)點(diǎn)所存儲(chǔ)的字符個(gè)數(shù)稱為______。當(dāng)結(jié)點(diǎn)大小大于1時(shí)，鏈串的最后一個(gè)結(jié)點(diǎn)的各個(gè)數(shù)據(jù)域不一定總能全被字符占滿，此時(shí)，應(yīng)在這些未用的數(shù)據(jù)域里補(bǔ)上______。

4．一般地，一個(gè)n維數(shù)組可視為其數(shù)據(jù)元素為______維數(shù)組的線性表。數(shù)組通常只有______和_______兩種基本運(yùn)算。

5．通常采用_______存儲(chǔ)結(jié)構(gòu)來存放數(shù)組。對二維數(shù)組可有兩種存儲(chǔ)方法：一種是以______為主序的存儲(chǔ)方式，另一種是以______為主序的存儲(chǔ)方式。C語言數(shù)組用的是以______序?yàn)橹餍虻拇鎯?chǔ)方法。

6．?dāng)?shù)組M中每個(gè)元素的長度是3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址EA開始連續(xù)存放在存儲(chǔ)器中。若按行方式存放，則元素M[8][5]的起始地址為_______；若按列優(yōu)先方式存放，則元素M[8][5]的地址為_______。

7．二維數(shù)組M的成員是6個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要______個(gè)字節(jié)；M的第8列和第5行共占_______個(gè)字節(jié)；若M按行方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的_______元素的起始地址一致。

8．需要壓縮存儲(chǔ)的矩陣可分為_______矩陣和_______矩陣兩種。

9．對稱方陣中有近半的元素重復(fù)，若為每一對元素只分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元素壓縮存儲(chǔ)到_______個(gè)元素的存儲(chǔ)空間中。

10．假設(shè)以一維數(shù)組M(1..n(n+1)/2)作為n階對稱矩陣A的存儲(chǔ)結(jié)構(gòu)，以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對角線)中的元素，數(shù)組M和矩陣A間對應(yīng)的關(guān)系為_______。

11．上三角矩陣中，主對角線上的第t行(1≤t≤n)有_______個(gè)元素，按行優(yōu)先順序在一維數(shù)組M中存放上三角矩陣中的元素aij時(shí)，aij之前的前i-1行共有_______個(gè)元素，在第i行上，aij是該行的第_______個(gè)元素，M[k]和aij的對應(yīng)關(guān)系是_______。當(dāng)i>j時(shí)，aij=c(c表示常量)，c存放在M[________]中。

三、選擇題

1．在串的基本運(yùn)算中，能夠改變串值的運(yùn)算有()。

A.?EQAL(S,T) B.?LENGTH(S)

C.?CONCAT(S,T)

D.?REPLACE(S,T,R)

E.?INDEX(S,T)

2．在串的基本運(yùn)算中，不能夠改變串值的運(yùn)算有()。

A.?ASSIGN(S,T) B.?INSERT(S1,i,S2)

C.?DELETE(S,i,j)

D.?SUBSTR(S,i,j)

E.?REPLACE(S,T,R)

3．對于以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)來說，在數(shù)組A[c1..d1，c2..d2]中，c1和d1分別為數(shù)組A的第一個(gè)下標(biāo)的下界和上界，c2和d2分別為第二個(gè)下標(biāo)的下界和上界，每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任一元素a[i,j]的存儲(chǔ)位置可由()式確定。

A.?Loc(i,j)=Loc(c1,c2)+[(i-c1)*(d2-c2)+(j-c2)]*k

B.?Loc(i,j)=Loc(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k

C.?Loc(i,j)=Loc(c1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k

D.?Loc(i,j)=Loc(c1,c2)+[(j-c2)*(d1-c1)+(i-c1)]*k

4．對于C語言的二維數(shù)組DataTypeA[m][n],每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任意元素a[i,j]的存儲(chǔ)位置可由()式確定。

A.?Loc(i,j)=Loc(0,0)+[i*(n+1)+j]*k

B.?Loc(i,j)=Loc(0,0)+[j*(m+1)+i]*k

C.?Loc(i,j)=Loc(0,0)+(i*n+j)*k

D.?Loc(i,j)=Loc(0,0)+(j*m+i)*k

5．稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)()。

A.非零元素 B.三元組(i,j,aij)

C.?aij D.?i,j

6．基于三元組表的稀疏矩陣，對每個(gè)非零元素aij,可以用一個(gè)()唯一確定。

A.非零元素B.三元組(i,j,aij) C.?aijD.?i,j

7．二維數(shù)組M[i,j]的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5。若M按行存儲(chǔ)，元素M[3,5]的起始地址與M按列存儲(chǔ)時(shí)，元素()的起始地址相同。

A.?M[2,4] B.?M[3,4] C.?M[3,5] D.?M[4,4]

8．常對數(shù)組進(jìn)行的兩種基本操作是()。

A.建立與刪除 B.建立與修改

C.查找與修改 D.查找與索引四、問答及算法設(shè)計(jì)

1．簡述下列各對術(shù)語的區(qū)別。

空串和空格串；串變量和串常量；主串和子串；串變量的名字與串變量的值

2．設(shè)有A=“”,B=“mule”，C=“old”，D=“my”,試計(jì)算下列運(yùn)算的結(jié)果(注：A+B是CONCAT(A,B)的簡寫,A=“”表示含有兩個(gè)空格的字符串)。

(a)?A+B (b)?B+A

(c)?D+C+B

(d)?SUBS