第四章串和數(shù)組串及存儲結(jié)構(gòu)串運(yùn)算矩陣的壓縮存儲應(yīng)用實(shí)例串在文字編輯、詞法掃描、符號處理、自然語言翻譯系統(tǒng)及事務(wù)處理程序中有著廣泛的應(yīng)用。幾乎所有的程序設(shè)計(jì)語言都允許用數(shù)組來描述數(shù)據(jù)。數(shù)組可以看成是線性表的擴(kuò)展。串概念

串：由零個(gè)或多個(gè)字符組成的有限序列，記為S="a1a2a3…an"

子串：串中任意個(gè)連續(xù)的字符組成的子序列。【例1】

A=“Thisisastring.”長度17

主串

B=“string”長度6子串運(yùn)算①strcopy(S,T)賦值②strcat(S,T)連接③strlen(S)求串長④substr(S,i,j)求子串⑤strcmp(S,T)比較串大?、辤nsert(S,i,T)插入⑦delete(S,i,j)刪除⑧index(S,T)子串定位⑨replace(S,i,j,T)置換串的存儲結(jié)構(gòu)順序串用一組地址連續(xù)的存儲單元依次存儲串中的字符。順序串類型描述Thisisastring\0#defineMAXSIZE100 //串可能的最大長度

typedefstruct{charch[MAXSIZE];//串值

intlen;//串長度}SeqString;

鏈串類型描述typedefstructlinknode{chardata;structlinknode*next;}LinkString;LinkString

*S;abcds∧結(jié)點(diǎn)大小為1sabcdef∧結(jié)點(diǎn)大小為3串的存儲結(jié)構(gòu)串的索引存儲建立串名和串值之間對應(yīng)關(guān)系，為存取串值提供足夠信息。

帶長度索引表namelengthstadrs1s243…

workday…typedefstruct{charname[M];//串名intlength;//串長

char*stadr;//串值存入的起始地址}LenNode;串的存儲結(jié)構(gòu)串的存儲結(jié)構(gòu)

帶末指針的索引表typedefstruct{

charname[M];char*stadr,*enadr;}EndNode;namestadrenadrs1s2…workday…串的存儲結(jié)構(gòu)

帶特征位的索引表typedefstruct{

charname[maxsize];inttag;//特征位

union{char*stadr;charvalue[4];

}uval;}TagNode;nametagstadr/values1s2…work…01day\0串的存儲結(jié)構(gòu)說明

順序串空間是預(yù)先定義的，需避免溢出。若使用多個(gè)串，可共享空間、按需分配。解決問題：

刪除串所占空間的回收；插入操作時(shí)，如何擴(kuò)充串值空間等。freenamelengthstadrs1s281380………main()↙inta[10],i;↙maxsize-1串運(yùn)算的實(shí)現(xiàn)——串連接SeqString*StrCat(SeqString*s,SeqString*t){inti;SeqString*r=(SeqString*)malloc(sizeof(SeqString));

if(s->len+t->len>MAXSIZE)printf("上溢\n");

else{

for(i=0;i<s->len;i++)//將s串傳給r

r->ch[i]=s->ch[i];

for(i=0;i<t->len;i++)//將t串傳給r

r->ch[s->len+i]=t->ch[i];

r->ch[s->len+i]='\0';//最后一個(gè)位置賦'\0'

r->len=s->len+t->len;//串長度等于兩串之和

}

returnr;//返回新串}

//StrCatatSeqString*SubStr(SeqString*s,inti,intj){intk;SeqString*t;t=(SeqString*)malloc(sizeof(SeqString));

if(i+j-1>s->len){//i,j值超出允許范圍printf("超界\n");returnNULL;

}

else{

for(k=0;k<j;k++)t->ch[k]=s->ch[i+k-1];//將s中指定的子串傳給t

t->len=j;//將子串長度賦給t的長度域

t->ch[t->len]='\0';

returnt;

}}

//SubStr串運(yùn)算的實(shí)現(xiàn)——求子串模式匹配模式匹配從目標(biāo)S中查找模式T的過程。目標(biāo)S：s1s2s3…sm…sn

模式T：t1t2t3…tm

樸素的模式匹配（布魯特—福斯算法）

從目標(biāo)S的第一個(gè)字符開始和模式T中第一個(gè)字符比較，相等則繼續(xù)比較后續(xù)字符，否則從S的第二個(gè)字符開始重新比較。直至T中的每個(gè)字符依次和S中的某個(gè)子序列相等（匹配成功），否則匹配失敗。模式匹配第一趟：

abbabaabai=3j=3失敗第二趟：abbabaai=2j=1失敗第三趟：abbabaai=3j=1失敗第四趟：abbabaaba

成功【例2】

S=“abbaba”，T=“aba”為例的模式匹配模式匹配分析

如何從上一趟失敗的匹配中得到新一趟匹配S的比較位置i?在失敗的匹配中若si≠tj（1≤j≤m），則tj-1=si-1，tj-2=si-2，…，t1=si-j+1，即t1和si-j+1對應(yīng)新的一趟匹配開始時(shí)，i應(yīng)回溯到i-j+2。

第三趟：abbabaai=3j=1失敗第四趟：abbabaaba

成功模式匹配算法intIndex(SeqString*s,SeqString*t){inti=0,j=0;

while(i<s->len&&j<t->len){if(s->ch[i]==t->ch[j]){i++;j++;}else{i=i-j+1;j=0;}

}if(j==t->len)

returni-t->len;elsereturn-1;}

//Index模式匹配特點(diǎn)

算法過程簡單，易于理解，但由于i的回溯，效率不高。改進(jìn)

某趟匹配失敗，i值回溯后，可加入判斷：若S串剩余長度＜T串長度(S→len-i+1＜T→len)

即：i>S→len-T→len+1匹配失敗ababaaab

bb

i=5j=3失敗【例3】

因回溯后i=4，則i>6-4+1，故匹配不可能成功模式匹配時(shí)間性能最好的情況：O(m＋n)設(shè)從S的第i個(gè)位置與T匹配成功的概率為pi，第i趟成功匹配中字符比較的次數(shù)為m，則匹配成功時(shí)的平均比較次數(shù)：模式匹配設(shè)第i趟匹配成功，其概率為pi，每趟比較m次，則匹配成功時(shí)的平均比較次數(shù)：O(m×n)時(shí)間性能最壞的情況：模式匹配快速模式匹配（Knuth-Morris-Pratt,KMP匹配）基本思想

當(dāng)匹配過程中字符比較不等時(shí)，不需回溯i值，而利用已經(jīng)得到的"部分匹配"結(jié)果，將模式向右"滑動"盡可能遠(yuǎn)的距離后繼續(xù)比較。【例4】S=“ababcabcacbab”，T=“abcac”為例的模式匹配。模式匹配【例4】

S="ababcabcacbab"，T="abcac"為例的模式匹配。第一趟：ababcabcacbabab

ci=3j=3第二趟：ababcabcacbababcaci=7j=5ij=1第三趟：ababcabcacbab(a)bcacij=2模式匹配

分析S=“abbaba”，T=“aba”的匹配過程第一趟：abbabaabai=3j=3失敗即：s1＝t1s2＝t2s3≠t3

因：t1≠t2

則s2≠t1T右移一位比較一定不等

t1＝t3

則s3≠t1T再右移一位比較一定不等故可從s4開始與t1比較第二趟：abbabaaba前面部分匹配結(jié)果為后續(xù)匹配提供了信息模式匹配模式串的預(yù)處理

設(shè)置數(shù)組next[]保存匹配失敗后，從模式串t重新開始比較的位置1≤next[j]<j(1≤j≤m)若上趟模式串匹配失敗的位置是j，則下趟匹配應(yīng)將si與tnext[j]開始next[j]值僅依賴于模式串本身的前j個(gè)字符的組成模式匹配s1s2…si-j+1…si-2si-1sisi+1…t1…tk…tj-2tj-1tj…tj-k+1tj-k+2…tj-1＝si-k+1si-k+2…si-1設(shè)下一趟si可與tk(k<j)比較，則t中前k-1個(gè)字符的子串須滿足：t1t2…tk-1＝si-k+1si-k+2…si-1由部分匹配結(jié)果：t1t2…tk-1＝tj-k+1tj-k+2…tj-1故：計(jì)算next[j](=k)關(guān)鍵：是否存在從模式串第一個(gè)位置出發(fā)右移得到的子串和從模式串的第j-1個(gè)字符位置出發(fā)左移得到的子串匹配。模式匹配結(jié)論令next[j]=k，則失配時(shí)，用t中以k為下標(biāo)的字符與si進(jìn)行下一趟比較以加速匹配過程。k值僅依賴于t本身的前j個(gè)字符的組成。

0

j=1next[j]=

max{k|0＜k＜j，且使t1t2…tk-1=tj-k+1…tj-1成立}

1

其它情況若上趟匹配si與tj不等，模式匹配

【例5】S=“aaaabbb”，T=“aaab”

當(dāng)s4≠t4時(shí)，k可取2和3S：aaaa

bbbT：aaab

(a)aabk=2S：aaaa

bbbT：aaab(aa)a

b

k=3注意：為使t的右移不丟失任何匹配成功的可能，若同時(shí)存在多個(gè)滿足條件的k值，應(yīng)取其中的最大的，這樣移位j-k最小。成功失敗模式匹配【例6】計(jì)算T=“abaabcac”的next值。

解：j=1j=2j=3j=4j=5j=6j=7j=8next[1]=0next[2]=1同j=2next[3]=1有首尾相等的子串“a”，則next[4]=2next[5]=2next[6]=3next[7]=1next[8]=2模式匹配時(shí)間復(fù)雜度：T(n)=O(m)voidGetNext(SeqString*t,intnext){inti=0;//next數(shù)組下標(biāo),next[]值范圍0~m-1intj=-1;

next[0]=-1;//-1表示下一趟t0與si+1比較while(i<t->len){if(j==-1||t->ch[i]==t->ch[j]){++i;++j;next[i]=j;}

else

j=next[j];

}}//GetNext模式匹配intIndex(SeqString*s,SeqString*t){inti=0,j=0;while(i<s->len&&j<t->len){ if((j==-1)||(s->ch[i]==t->ch[j])){ i++;j++; }

else

j=next[j];//模式串T向右移

}

if(j==t->len)

returni-t->len; //匹配成功

else

return-1; //匹配失敗}

//Index模式匹配說明：（1）盡管樸素模式匹配算法時(shí)間復(fù)雜度是O(n×m)，但很多情況下其實(shí)際執(zhí)行時(shí)間近似于O(n+m)。（2）KMP算法僅當(dāng)模式與主串之間存在許多“部分匹配”的情況下才顯得比樸素匹配算法快得多。（3）KMP算法的最大特點(diǎn)是不需回溯，對目標(biāo)串僅需從頭至尾掃描一遍，這對處理從外設(shè)輸入的龐大文件很有效。多維數(shù)組的存儲實(shí)現(xiàn)當(dāng)數(shù)組維數(shù)為1時(shí)，數(shù)組是一種元素?cái)?shù)目固定的線性表；當(dāng)維數(shù)大于1時(shí)，數(shù)組可以看做是線性表的推廣。數(shù)組結(jié)構(gòu)的性質(zhì)數(shù)據(jù)元素?cái)?shù)目固定。一旦說明了一個(gè)數(shù)組結(jié)構(gòu)，其中的元素?cái)?shù)目就不再有增減變化。數(shù)據(jù)元素具有相同的類型。數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束，并且下標(biāo)有序。多維數(shù)組的存儲實(shí)現(xiàn)Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*d

按行序?yàn)橹餍虼娣臿11a12……..a1na21a22……..a2n

am1am2……..amn

……

amn

…

am2

am1…a2n

…

a22

a21a1n

…a12

a1101n-1m*n-1nLoc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*d

按列序?yàn)橹餍虼娣臿11a12……..a1na21a22……..a2n

am1am2……..amn

……

amn

…

a2n

a1n…am2

…

a22

a12am1

…a21

a1101n-1m*n-1n多維數(shù)組的存儲實(shí)現(xiàn)數(shù)組的順序存儲地址公式一般地，若A[c1…d1,c2…d2]，則Loc(aij)=Loc(ac1c2)+[(i－c1)×(d2－c2＋1)＋(j－c2)]×d以列為主序：Loc(aij)=Loc(a11)+[(j－1)×m＋(i－1)]×d二維數(shù)組Am×n

，每個(gè)元素占d個(gè)單元，則以行為主序：Loc(aij)=Loc(a11)+[(i－1)×n＋(j－1)]×d

數(shù)組的順序存儲三維數(shù)組Am×n×p

順下標(biāo)存儲，則Loc(aijk)=Loc(a111)+[(i－1)×n×p＋(j－1)×p＋k－1]×d如：A3×2×2

元素在內(nèi)存中的排列為：a000a001a010a011a100a101a110a111a200a201a210a211Loc(a210)=Loc(a000)+[i×n×p＋j×p＋k]×d=Loc(a000)+(8+2+0)×d矩陣的壓縮存儲壓縮存儲——零元素不分配存儲空間，多個(gè)值相同的元素分配一個(gè)空間。需壓縮存儲的矩陣：特殊矩陣、稀疏矩陣特殊矩陣的壓縮存儲對角陣a00

0

0

…………….0

0

a11

0

0

……………0

0

0

…0

an-2,n-2

0

0

0

……0

an-1n-10

0

a22

0

0

………0…存放在一維數(shù)組A[n]（以行為主序）A的下標(biāo)k與矩陣下標(biāo)i的對應(yīng)關(guān)系:k=i矩陣的壓縮存儲三角陣（以下三角陣為例）下三角矩陣上三角矩陣存放在一維數(shù)組A[n]（以行為主序）A的下標(biāo)k與矩陣下標(biāo)i的對應(yīng)關(guān)系:i*(i+1)/2+j

i≥jn*(n+1)/2i＜jk=k:0123……n(n+1)/2-1a00a10a11a20an-1,n-1……a00

00

……..0

a10a11

0

……..0an-1,0an-1,1

……..an-1,n-1

an-2,0…………….0……………0a11…

a1,n-2a1,n-1

a00

a01……..an-1,00

0

……..an-1,n-1

00

…an-2,n-2an-2,n-1

……………矩陣的壓縮存儲對稱陣a00a01

….

……..a0.n-1a10

a11

……..…….a1n-1an-1,0

an-1,1

……..an-1,n-1….存放在一維數(shù)組A[n]（以行為主序）A的下標(biāo)k與矩陣下標(biāo)i的對應(yīng)關(guān)系:K=I×(I+1)/2+J其中I=max(i,j)，J=min(i,j)i(i+1)/2+ji≥jj(j+1)/2+ii＜jk=k:0123……n(n+1)/2-1a00a10a11a20an-1,n-1……矩陣的壓縮存儲稀疏矩陣

定義非零元素較少，且分布沒有一定規(guī)律的矩陣。

壓縮存儲原則需存矩陣的行、列維數(shù)和每個(gè)非零元素的行、列下標(biāo)及其值。

壓縮存儲方式三元組表、十字鏈表矩陣的壓縮存儲

三元組表將表示非零元素的三元組（行號、列號、值）按行優(yōu)先（或列優(yōu)先）的順序排列，得到一個(gè)其結(jié)點(diǎn)是三元組的線性表。類型描述：typedefstruct{

inti,j;//行號，列號

Datatypev;//元素值}Node;typedefstruct{

intm,n,t;//行數(shù)，列數(shù)，非零元素個(gè)數(shù)

Nodedata[SMAX];//三元組表}Spmatrix;//稀疏矩陣類型矩陣的壓縮存儲【例7】三元組表示例011202920-3251432244118501553-7ijvnmt矩陣的壓縮存儲01-3051510121418209232435-75214i

j

vNM011202920-3251432244118501553-7i

j

v【例8】稀疏矩陣轉(zhuǎn)置。矩陣的壓縮存儲算法思路：將矩陣行、列維數(shù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序，使M中元素以N的行(M的列)為主序

按A的列序轉(zhuǎn)置。按N中三元組次序依次在M中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即從M的第一行掃描，依此將M中的j由小→大選擇，將選中的三元組i和j交換后順序放入N，直到M中的三元組全部放入N中。矩陣的壓縮存儲spmatrix*TRANSMAT(spmatrix*a){//求a矩陣的轉(zhuǎn)置矩陣bintmno,nno,col;spmatrix*b;//存放轉(zhuǎn)置后的矩陣

b=(spmatrix*)malloc(sizeof(spmatrix));b→m=a→n;b→n=a→m;//行列數(shù)交換

b→t=a→t;if(a→t>0){//有非零元素，則轉(zhuǎn)置

bno=0;for(col=0;col<a→n;col++)//按*a的列序轉(zhuǎn)置

for(ano=0;ano<a→t;ano++)//掃描整個(gè)三元組表

if(a→data[ano].j==col){//列號為col則進(jìn)行置換

b→data[bno].i=a→data[mno].j;b→data[bno].j=a→data[mno].i;b→data[bno].v=a→data[mno].v;bno++;//b→data結(jié)點(diǎn)序號加1}}returnb;//返回轉(zhuǎn)置結(jié)果指針

}

時(shí)間復(fù)雜度：T(n)=O(nt)問題要求實(shí)現(xiàn)稀疏矩陣的加法和轉(zhuǎn)置運(yùn)算。數(shù)據(jù)結(jié)構(gòu)typedefstruct{//三元組結(jié)點(diǎn)

introw;//行

intcol;//列

intval;//值

}Node;typedefstruct{

intm,n,t;//矩陣行數(shù),列數(shù),非零元素個(gè)數(shù)

Node

data[SMAX];//三元組表}Spmatrix;//稀疏矩陣類型應(yīng)用實(shí)例——稀疏矩陣的運(yùn)算應(yīng)用實(shí)例——稀疏矩