數(shù)據(jù)結構-第4章-字符串、數(shù)組和矩陣

4.1串第4章字符串、數(shù)組和矩陣4.1.1串的基本概念和抽象數(shù)據(jù)類型串（string）是由零個或多個字符組成的有限序列。一般記為：s=’a1a2a3……ai……an’ (n≥0)其中s是串的名字；單引號是串的定界符，其本身不屬于串；單引號中的字符序列a1a2a3……ai……an是串的值；ai（1≤i≤n）可以是字母、數(shù)字或其它字符；n為串的長度。具有0個字符的串稱為空串，其長度為0，記為s=’’，一般用Φ表示。注意：空串與由空格組成的串不是一個概念，后者稱為空格串，是有長度的，不是空串。串中任意個連續(xù)的字符組成的子序列稱為串的子串，包含子串的串對應地稱為主串?？沾侨我獯淖哟?。單個字符在序列中的序號稱為該字符在串中的位置。子串在主串中的位置為其第一個字符在串中的位置。4.1串第4章字符串、數(shù)組和矩陣4.1.2串的靜態(tài)存儲和操作實現(xiàn)串作為一種計算機要處理的一種對象，在程序設計中，可以賦給它一個變量名，通過變量名訪問值。對串的存儲有靜態(tài)和動態(tài)兩種，所謂靜態(tài)存儲是指串值的存儲分配在編譯時完成，可以根據(jù)串名直接訪問到串值；而動態(tài)存儲是指串值的存儲分配是在程序運行時完成的，在串名和串值之間有一個稱之為存儲映像的對照表，通過此對照表訪問串值。本節(jié)介紹串的靜態(tài)存儲和基于此種存儲方式的操作實現(xiàn)。4.1串第4章字符串、數(shù)組和矩陣串的靜態(tài)存儲結構是指用一段地址連續(xù)的存儲單元存儲串的字符序列。和線性表的順序存儲結構相類似，一般也稱為串的順序存儲結構。一般描述如下：#define MAXLEN 255 /*串的最大長度*/typedef struct{ chardata[MAXLEN+1]; /*定義存儲串的空間*/ int len; /*當前串的實際長度*/}sqString;4.1串第4章字符串、數(shù)組和矩陣1.串賦值把字符串常量（如“Data_Structure”）賦值給一個串。如果字符串常量的長度小于MAXLEN則返回OK；否則字符串被截斷，并返回CUT。

StatusStrAssign(sqString*S,charchars[]) {

inti=0;

while(chars[i]!=‘\0’&&i<MAXLEN) /*把字符串常量賦值給串S*/ {

S->data[i]=chars[i];

i++; } S->data[i]=‘\0’; S->len=i; if(i==MAXLEN&&chars[i]!=‘\0’) /*字符串常量被截斷*/

returnCUT; else

returnOK; }4.1串第4章字符串、數(shù)組和矩陣2.求串的長度

intStrLength(sqStringS) {

returnS.len;

}3.串比較串的比較實際是依次比較兩個串（如S和T）中的對應字符。若串中的所有對應字符均相等，則兩個串相等、返回0；若S中的字符大于T中的對應字符，則串S>T、返回正數(shù)；若S中的字符小于T中的對應字符，則串S<T、返回負數(shù)。intStrCmp(sqStringS,sqStringT){ inti; for(i=0;i<S.len&&i<T.len;i++)

if(S.data[i]!=T.data[i])returnS.data[i]-T.data[i];

returnS.len-T.len;}4.1串第4章字符串、數(shù)組和矩陣5.求子串從串S中第pos個字符開始，有Sub返回長度為len的子串。若len超出了從pos到S結尾的子串的長度，則Sub只包含S中從pos到結尾的部分，并返回OK。StatusSubStr(sqString*Sub,sqStringS,intpos,intlen){ inti; if(S.len==0||pos<1||pos>S.len||len<0) returnERROR; if(pos+len>S.len) len=S.len–pos+1; for(i=0;i<=len;i++) Sub->data[i]=S.data[i+pos-1]; Sub->data[len]=‘\0’;Sub->len=len; returnOK;}4.1串第4章字符串、數(shù)組和矩陣4.1.3串的動態(tài)存儲和操作實現(xiàn)1.串的鏈式存儲與線性表的鏈式存儲結構相類似，串也可以采用鏈表的形式來存儲。但是與線性表的鏈式存儲不同的是，串的鏈式存儲存在一個“結點大小”的問題，即每個結點可以存放一個字符，也可以存放多個字符。對于結點大小大于1的情況，由于串的長度不一定恰好是結點大小的整數(shù)倍，所以串鏈表的最后一個結點一般用“\0”填充至滿。4.1串第4章字符串、數(shù)組和矩陣串的鏈式存儲一般定義如下： #define NODE_SIZE 4 /*每個結點的大小*/typedef structstrNode{ chardata[NODE_SIZE]; structstrNode*next; }StrNode;typedefstruct{ StrNode*head; intlen;}nodeString;4.1串第4章字符串、數(shù)組和矩陣2.串的堆式存儲在串的實際應用中，經(jīng)常采用另外一種動態(tài)存儲結構，即堆式存儲結構。堆式存儲結構是指系統(tǒng)開辟一個連續(xù)且足夠大的空間用來存儲串值，但存儲地址是在程序執(zhí)行的過程中動態(tài)分配的。在C語言中，一般用系統(tǒng)函數(shù)malloc（）和free（）來管理這個存儲區(qū)域。當要建立新串時，系統(tǒng)用malloc（）函數(shù)為其分配一個和串長大小相同的空間來存儲串值。如果分配成功，則返回一個指向該串的起始地址的指針，通過該指針可以訪問到該串。當某個串不在被使用的時候，系統(tǒng)用free（）函數(shù)收回該串占用的存儲空間，以備后續(xù)分配時使用。4.1串第4章字符串、數(shù)組和矩陣串的堆式存儲一般定義如下：typedef struct{

char*data; /*定義存儲串空間的指針*/

int len; /*當前串的實際長度*/}heapString;（1）串賦值

為串動態(tài)分配一存儲空間，把字符串常量（如“Data_Structure”）賦值給該串。如果成功返回OK，否則返回失敗。StatusStrAssign(heapString**S,charchars[]){intlen=0,i=0;while(chars[len]!='\0')/*計算字符串常量的長度*/len++;if(*S!=NULL)/*釋放原串的內容*/free((*S)->data);else*S=(heapString*)malloc(sizeof(heapString));if(!*S)/*分配空間失敗*/returnERROR;(*S)->data=(char*)malloc((len+1)*sizeof(char));if(!(*S)->data)/*分配空間失敗*/returnERROR;(*S)->len=len;for(i=0;i<=(*S)->len;i++)(*S)->data[i]=chars[i];returnOK;}4.1串第4章字符串、數(shù)組和矩陣堆式存儲的基本操作主要介紹以下幾種：（2）求串的長度

intStrLength(heapStringS) {

returnS.len;

}（3）串比較比較兩個串（如S和T）的大小。若兩個串相等則返回0；若S>T則返回正數(shù)；若S<T則返回負數(shù)。intStrCmp(heapStringS,heapStringT){

inti;

for(i=0;i<S.len&&i<T.len;i++) if(S->data[i]!=T->data[i])returnS->data[i]-T->data[i]; returnS.len-T.len;}4.1串第4章字符串、數(shù)組和矩陣

（4）串連接把T連接到S的尾部，并由S返回新的串。StatusStrConcat(heapString*S,heapStringT){inti;S->data=(char*)realloc(S->data,(S->len+T.len+1)*sizeof(char));if(!S->data)/*分配空間失敗*/ returnERROR;for(i=0;i<T.len;i++){S->data[S->len+i]=T.data[i];}S->len=S->len+i;S->data[S->len]='\0';returnOK;}4.1串第4章字符串、數(shù)組和矩陣

（5）求子串從串S中第pos個字符開始，有Sub返回長度為len的子串。若len超出了從pos到S結尾的子串的長度，則Sub只包含S中從pos到結尾的部分，并返回OK。StatusSubStr(heapString*Sub,heapStringS,intpos,intlen){ inti; if(S.len==0||pos<1||pos>S.len||len<0) returnERROR; if(pos+len>S.len) len=S.len–pos+1; if(S->len>0) /*釋放原串的內容*/ free(S->data); Sub->data=(char*)malloc((len+1)*sizeof(char)); if(!Sub->data) /*分配空間失敗*/ returnERROR; for(i=0;i<=len;i++) Sub->data[i]=S.data[i+pos-1]; Sub->data[len]=‘\0’;Sub->len=len; returnOK;}4.1串第4章字符串、數(shù)組和矩陣4.2串的模式匹配第4章字符串、數(shù)組和矩陣4.2.1Brute-Force算法1.基本思想Brute-Force算法的思想比較簡單：首先將主串的第一個字符和模式串的第一個字符相比較，若相等，則比較二者的下一個字符；若不等，則將主串的下一個字符和模式串的第一個字符相比較。重復此過程，直至主串從某一個字符起，依次和模式串中的字符相等，則匹配成功；否則，匹配失敗。從上述思想中可以看到，此算法的關鍵是主串和模式串中的字符比較和移動?？梢栽O定兩個指針i、j分別指向主串和模式串中的字符。首先i=1，j=1進行比較，若相等，則i、j分別自加1，繼續(xù)進行比較；若不等，則i自加1，j重置為1，進行比較。重復此過程，直至匹配成功或失敗。4.2串的模式匹配第4章字符串、數(shù)組和矩陣2.算法實現(xiàn) 基于順序存儲的Brute-Force算法描述如下，基于堆式存儲的實現(xiàn)算法也類似。

intBFIndex(sqStringS,sqStringT) { /*在主串S中尋找子串T第一次出現(xiàn)的位置。若匹配失敗，則返回-1*/ inti=0,j=0,k=-1; while(i<S.len&&j<T.len) { if(S.data[i]==T.data[j]) /*相等則繼續(xù)比較*/ { i++; j++; } else { i=i–j+1; j=0; } /*不相等則回溯*/ } if(j>=T.len) /*全部匹配*/ k=i–T.len; returnk; }4.2串的模式匹配第4章字符串、數(shù)組和矩陣3.效率分析若主串的長度為n，模式串長度為m，則Brute-Force算法的比較次數(shù)分別為：最好的情況，主串的前m個字符剛好為模式串的m個字符，因此只需m次比較，所以時間復雜度為O(m)。最惡劣情況，每一趟匹配時，模式串的前m-1個字符序列與主串的相應字符序列比較總是相等，但模式串的第m個字符和主串的相應字符比較總是不等。此時i指針需回溯，總的比較趟數(shù)為n-m+1，每趟進行m次比較，所以總次數(shù)為m*(n-m+1)，因此其時間復雜度為O(n*m)。4.2串的模式匹配第4章字符串、數(shù)組和矩陣4.2.2KMP算法1.基本思想在4.4.1節(jié)中的例子中可以看到，每次發(fā)生主串和模式串不等的情況，指針都需回溯，以重新比較。如圖4-2中，當i=3，j=3發(fā)生不等時，重新比較i=2，j=1；仍然不等，則回溯，重新比較i=3，j=1；仍然不等，繼續(xù)回溯。4.2串的模式匹配第4章字符串、數(shù)組和矩陣2.算法實現(xiàn)

根據(jù)上述分析，KMP算法描述如下： intKMPIndex(sqStringS,sqStringT) { /*在主串S中尋找子串T第一次出現(xiàn)的位置。若匹配失敗，則返回-1*/ inti=1,j=1,k=-1; while(i<=S.len&&j<=T.len) { if(j==0||S.data[i]==T.data[j]) { i++; j++; } else j=next[j]; /*不相等則模式串的指針回溯*/ } if(j>T.len) /*全部匹配*/ k=i–T.len; returnk; }4.2串的模式匹配第4章字符串、數(shù)組和矩陣3.效率分析

由于KMP算法不需要回溯主串的指針，所以總的時間復雜度為O(n+m)。GetNext函數(shù)的時間復雜度為O(m)，但通常模式串的長度要比主串的長度小的多，所以本算法所增加的時間相對整個KMP算法來說可以忽略。4.3數(shù)組第4章字符串、數(shù)組和矩陣4.3.1數(shù)組的定義組可以看作是線性表的推廣，數(shù)組作為一種數(shù)據(jù)結構，其特點是結構中的元素本身可以是具有某種結構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表；二維數(shù)組Amn可視為由m個行向量組成的向量，或由n個列向量組成的向量，二維數(shù)組中的每個元素aij既屬于第i行的行向量，又屬于第j列的列向量。三維數(shù)組Amnp可視為以二維數(shù)組為數(shù)據(jù)元素的向量，三維數(shù)組中的每個元素aijk都屬于三個向量。依此類推。一個n維數(shù)組可以定義為其數(shù)據(jù)元素為n-l維數(shù)組類型的一維數(shù)組類型。數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素由惟一的一組下標來標識。對于數(shù)組，通常只有兩種操作：(1)結定一組下標，存取相應的數(shù)據(jù)元素；(2)給定一組下標，修改相應數(shù)據(jù)元素中的某一個或幾個數(shù)據(jù)項的值。4.3數(shù)組第4章字符串、數(shù)組和矩陣4.3.2數(shù)組的順序存儲及實現(xiàn)1.行優(yōu)先順序將數(shù)組元素按行向量排列，第i+1個行向量緊接在第i個行向量后面。例如：二維數(shù)組Amn按行優(yōu)先存儲的線性序列為：a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn。應該注意的是，在C語言中，數(shù)組按行優(yōu)先順序存儲；其次，行優(yōu)先順序推廣到多維數(shù)組時，可規(guī)定為先排最右的下標。4.3數(shù)組第4章字符串、數(shù)組和矩陣2.列優(yōu)先順序將數(shù)組元素按列向量排列，第i+1個列向量緊接在第i個列向量后面。例如：二維數(shù)組Amn按列優(yōu)先存儲的線性序列為：a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn。應該注意的是，F(xiàn)ORTRAN語言中，數(shù)組按列優(yōu)先順序存儲；列優(yōu)先順序推廣到多維數(shù)組時，可規(guī)定為先排最左的下標。4.3數(shù)組第4章字符串、數(shù)組和矩陣3.數(shù)組元素的地址計算公式（1）按行優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d其中：①LOC(a11)是開始結點的存放地址（即基地址）；②d為每個元素所占的存儲單元數(shù)；③由地址計算公式可得，數(shù)組中任意一個元素可通過地址公式隨機存取，即順序存儲的數(shù)組是隨機存取結構；（2）按列優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d4.3數(shù)組第4章字符串、數(shù)組和矩陣（3）按行優(yōu)先順序存儲的三維數(shù)組Amnp地址計算公式LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d（4）下界不為1的二維數(shù)組的地址計算公式①二維數(shù)組A[c1..d1][c2..d2]的地址計算公式LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d②下界為0的二維數(shù)組的地址計算公式（C語言中使用）LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣4.4.1特殊矩陣的壓縮存儲所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。常見的有對稱矩陣、三角矩陣和對角矩陣等。下面我們討論這幾種特殊矩陣的壓縮存儲。1．對稱矩陣（1）對稱矩陣在一個n階方陣A中，若元素滿足下述性質：aij=aji(0≤i，j≤n-1)則稱A為對稱矩陣。4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣（2）對稱矩陣的壓縮存儲對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間。這樣，能節(jié)約近一半的存儲空間。①按"行優(yōu)先順序"存儲主對角線(包括對角線)以下的元素圖4-7對稱矩陣的行優(yōu)先存放4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣（3）對稱矩陣的地址計算公式LOC(aij)=LOC(sa[k])=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d通過下標變換公式，對于任意給定一組下標(i，j)，均可在sa[k]中找到矩陣元素aij。例如，a21和a12均存儲在sa[4]中，反之，對所有的k＝0，1，…，n×(n+1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i，j)。由此，稱sa[n×(n+1)/2]為n階對稱矩陣A的壓縮存儲，如圖4-8所示，這種壓縮存儲也是隨機存取結構。圖4-8對稱矩陣的壓組存儲4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣2．三角矩陣（1）三角矩陣的劃分以主對角線劃分，三角矩陣有上三角矩陣和下三角矩陣兩種，如圖4-9所示。圖4-9(a)所示為上三角矩陣，它的下三角(不包括主角線)中的元素均為常數(shù)c；圖4-9(b)所示為下三角矩陣，與上三角矩陣相反，主對角線上方均為常數(shù)c。圖4-9三角矩陣4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣3．對角矩陣對角矩陣也稱為帶狀矩陣。在這種矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。我們把非零元素集中的帶狀區(qū)域中對角線的條數(shù)稱為帶狀矩陣的帶寬。如圖4-11給出了一個三對角矩陣。圖4-11三對角矩陣4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣4.4.2稀疏矩陣的壓縮存儲設矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)(即s<<m×n)，且非零元素分布沒有一定規(guī)律，稱A為稀疏矩陣。1．稀疏矩陣的壓縮存儲為了節(jié)省存儲單元，可只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，為了能找到相應的元素，所以僅存儲非零元素的值是不夠的，還必須存儲非零元素所在的行號、列號，才能確定一個非零元素是矩陣中的哪一個元素。其中每一個非零元素所在的行號、列號和值組成一個三元組(i，j，aij)，并由此三元組惟一確定。稀疏矩陣的壓縮存儲會失去隨機存取功能。稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲和鏈式存儲。4.4矩陣的壓縮存檔第4章字符串、數(shù)組和矩陣2．三元組順序表將表示稀疏矩陣的非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，并依次存放在向量中，這種稀疏矩陣的順序存儲結構稱為三元組順序表。在下述討論中，均假設三元組是按行優(yōu)先順序排列的。3．帶行表的三元組表為了方便某些矩陣運算，在按行優(yōu)先存儲的三元組表中，加