第4章字符串和多維數(shù)組

第4

章字符串和多維數(shù)組

本章的基本內(nèi)容是：

字符串。在程序設(shè)計(jì)語言中大都有串變量的概念，而且實(shí)現(xiàn)了基本的串操作，本章重點(diǎn)討論串的存儲(chǔ)結(jié)構(gòu)及模式匹配算法。數(shù)組。在程序設(shè)計(jì)語言中大都提供了數(shù)組作為構(gòu)造數(shù)據(jù)類型，本章重點(diǎn)討論數(shù)組以及特殊矩陣的存儲(chǔ)與尋址。線性表——具有相同類型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置?！獌H在表的一端進(jìn)行插入和刪除操作隊(duì)列——在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作第4章字符串和多維數(shù)組

線性表——具有相同類型的數(shù)據(jù)元素的有限序列。將元素類型擴(kuò)充為線性表（多維）數(shù)組——線性表中的數(shù)據(jù)元素可以是線性表第4章字符串和多維數(shù)組

將元素類型限制為字符串——零個(gè)或多個(gè)字符組成的有限序列4.1字符串串的邏輯結(jié)構(gòu)非空串通常記為：S="

s1

s2……sn

"其中：S是串名，雙引號(hào)是定界符，雙引號(hào)引起來的部分是串值，si（1≤i≤n）是一個(gè)任意字符。串：零個(gè)或多個(gè)字符組成的有限序列。串長(zhǎng)度：串中所包含的字符個(gè)數(shù)。空串：長(zhǎng)度為0的串，記為：""。S1="ab12cd"S2="ab12"S3="ab13"S4="ab12φ"S5=""S6="φφφ"串的邏輯結(jié)構(gòu)子串：串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串。子串的位置：子串的第一個(gè)字符在主串中的序號(hào)。4.1字符串串的邏輯結(jié)構(gòu)串的數(shù)據(jù)對(duì)象約束為某個(gè)字符集。微機(jī)上常用的字符集是標(biāo)準(zhǔn)ASCII碼，由7位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示128個(gè)字符。擴(kuò)展ASCII碼由8位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示256個(gè)字符，足夠表示英語和一些特殊符號(hào)，但無法滿足國(guó)際需要。Unicode由16位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示216個(gè)字符，能夠表示世界上所有語言的所有字符，包括亞洲國(guó)家的表意字符。為了保持兼容性，Unicode字符集中的前256個(gè)字符與擴(kuò)展ASCII碼完全相同。4.1字符串串的比較：通過組成串的字符之間的比較來進(jìn)行的。

給定兩個(gè)串：X="x1x2…xn"和Y="y1y2…ym"，則：1.當(dāng)n=m且x1=y1，…，xn=ym時(shí)，稱X=Y；2.當(dāng)下列條件之一成立時(shí)，稱X＜Y：⑴n＜m且xi=yi（1≤i≤n）；⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。

串的邏輯結(jié)構(gòu)例：S1="ab12cd"，S2="ab12"，S3="ab13"4.1字符串方案1：用一個(gè)變量來表示串的實(shí)際長(zhǎng)度。

如何表示串的長(zhǎng)度？串的存儲(chǔ)結(jié)構(gòu)0123456……Max-1

abcdefg9空閑4.1字符串方案1：用一個(gè)變量來表示串的實(shí)際長(zhǎng)度。

串的存儲(chǔ)結(jié)構(gòu)如何表示串的長(zhǎng)度？01234567……Max-1

abcdefg\0空閑方案2：在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。

4.1字符串方案3：用數(shù)組的0號(hào)單元存放串的長(zhǎng)度，從1號(hào)單元開始存放串值。串的存儲(chǔ)結(jié)構(gòu)如何表示串的長(zhǎng)度？方案2：在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。

方案1：用一個(gè)變量來表示串的實(shí)際長(zhǎng)度。

01234567……Max-1

9

abcdefg空閑4.1字符串模式匹配

模式匹配：給定主串S="s1s2…sn"和模式T="t1t2…tm"，在S中尋找T的過程稱為模式匹配。如果匹配成功，返回T在S中的位置；如果匹配失敗，返回0。⑴算法的一次執(zhí)行時(shí)間不容忽視：?jiǎn)栴}規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配；⑵算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。模式匹配問題有什么特點(diǎn)？4.1字符串在下面的討論中，為了和C++語言中的字符數(shù)組保持一致，采用第2種順序存儲(chǔ)方法，即從數(shù)組下標(biāo)0開始存放字符，并且在串尾存儲(chǔ)終結(jié)符'\0'。01234567……Max-1abcdefg\0空閑4.1字符串模式匹配

基本思想：從主串S的第一個(gè)字符開始和模式T的第一個(gè)字符進(jìn)行比較：若相等，則繼續(xù)比較兩者的后續(xù)字符；

否則，從主串S的第二個(gè)字符開始和模式T的第一個(gè)字符進(jìn)行比較；重復(fù)上述過程，直到T中的字符全部比較完畢，則說明本趟匹配成功；或S中字符全部比較完，則說明匹配失敗。模式匹配——BF算法4.1字符串

si

……主串S模式T

tjji…模式匹配——BF算法回溯i回溯j4.1字符串si

……主串S模式Tji模式匹配——BF算法…

tj4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=2失?。籭回溯到1，j回溯到0ij模式匹配——BF算法ijij第1趟abcac

4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabj模式匹配——BF算法i第1趟abcac

4.1字符串i=2，j=2失??；i回溯到1，j回溯到0例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=1，j=0失敗i回溯到2，j回溯到0模式匹配——BF算法第2趟ijabcac

4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbab模式匹配——BF算法第2趟ijabcac

4.1字符串i=1，j=0失敗i回溯到2，j回溯到0例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=6，j=4失敗i回溯到3，j回溯到0模式匹配——BF算法第3趟ijijijijij4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

模式匹配——BF算法第3趟ij4.1字符串i=6，j=4失敗i回溯到3，j回溯到0例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=3，j=0失敗i回溯到4，j回溯到0模式匹配——BF算法第4趟ij4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

模式匹配——BF算法第4趟ij4.1字符串i=3，j=0失敗i回溯到4，j回溯到0例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=4，j=0失敗i回溯到5，j回溯到0模式匹配——BF算法第5趟ij4.1字符串例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

模式匹配——BF算法第5趟ij4.1字符串i=4，j=0失敗i回溯到5，j回溯到0例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbababcac

i=10，j=5，T中全部字符都比較完畢，匹配成功模式匹配——BF算法第6趟ijijijijij4.1字符串1.在串S和串T中設(shè)比較的起始下標(biāo)i和j；2.循環(huán)直到S或T的所有字符均比較完2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個(gè)字符；2.2否則，將i和j回溯，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標(biāo)；否則，匹配失敗，返回0；模式匹配——BF算法4.1字符串intBF(charS[],charT[]){i=0;j=0;

while(S[0]!='\0'&&T[0]!='\0'){if(S[i]==T[j]){i++;j++;}else{i=i-j+1;j=0;}}

if(T[j]=='\0')return(i-j+1);

elsereturn0;}模式匹配——BF算法intBF(charS[],charT[]){i=0;j=0;start=0;

while(S[0]!='\0'&&T[0]!='\0'){if(S[i]==T[j]){i++;j++;}else{

start++;i=start;j=0;}}

if(T[j]=='\0')returnstart;

elsereturn0;}4.1字符串模式匹配——BF算法設(shè)串S長(zhǎng)度為n，串T長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：例如：S="aaaaaaaaaabcdccccc"T="bcd"4.1字符串最好情況：不成功的匹配都發(fā)生在串T的第1個(gè)字符。模式匹配——BF算法設(shè)串S長(zhǎng)度為n，串T長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：最好情況：不成功的匹配都發(fā)生在串T的第1個(gè)字符。設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能情況共有n-m+1種，則：)(2)()1(11mnOmnmipmnii+=+=?+-′+-=4.1字符串模式匹配——BF算法設(shè)串S長(zhǎng)度為n，串T長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串T的最后一個(gè)字符。例如：S="aaaaaaaaaaabccccc"T="aaab"4.1字符串模式匹配——BF算法設(shè)串S長(zhǎng)度為n，串T長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串T的最后一個(gè)字符。設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)×m次，第i趟成功的匹配共比較了m次，所以總共比較了i×m次，因此4.1字符串模式匹配——KMP算法為什么BF算法時(shí)間性能低？在每趟匹配不成功時(shí)存在大量回溯，沒有利用已經(jīng)部分匹配的結(jié)果。如何在匹配不成功時(shí)主串不回溯？主串不回溯，模式就需要向右滑動(dòng)一段距離。如何確定模式的滑動(dòng)距離？4.1字符串i=2，j=2失?。?/p>

s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]模式匹配——KMP算法ababcabcacbabij第1趟abcac

ababcabcacbab第2趟abcac

4.1字符串i=2，j=2失敗；

s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]模式匹配——KMP算法ababcabcacbabij第1趟abcac

ababcabcacbababcac

第3趟4.1字符串模式匹配——KMP算法ababcabcacbababcac

第3趟iji=6，j=4失敗s[3]=t[1];t[0]≠t[1]∴t[0]≠s[3]ababcabcacbababcac

第4趟4.1字符串模式匹配——KMP算法ababcabcacbababcac

第3趟iji=6，j=4失敗s[4]=t[2];t[0]≠t[2]∴t[0]≠s[4]ababcabcacbababcac

第5趟4.1字符串模式匹配——KMP算法ababcabcacbababcac

第3趟ijababcabcacbababcac

第6趟匹配成功4.1字符串需要討論兩個(gè)問題：①如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)k？②模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?結(jié)論：i可以不回溯，模式向右滑動(dòng)到的新比較起點(diǎn)k

，并且k僅與模式串T有關(guān)！模式匹配——KMP算法4.1字符串抓住部分匹配時(shí)的兩個(gè)特征：設(shè)模式滑動(dòng)到第k個(gè)字符（1）則T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法4.1字符串a(chǎn)babcab……abcacijababcab……abcacij=k下一趟抓住部分匹配時(shí)的兩個(gè)特征：設(shè)模式滑動(dòng)到第k個(gè)字符（1）則T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法4.1字符串a(chǎn)babca

b……abcacijababca

b……abcacij=k下一趟（2）則T[j-k]~T[j-1]=S[i-k]~S[i-1]兩式聯(lián)立可得：T[0]~T[k-1]=T[j-k]~T[j-1]T[0]~T[k-1]=T[j-k]~T[j-1]說明了什么？（1）k

與

j

具有函數(shù)關(guān)系，由當(dāng)前失配位置j，可以計(jì)算出滑動(dòng)位置k（即比較的新起點(diǎn)）；（2）滑動(dòng)位置k

僅與模式串T有關(guān)。從第0位往右經(jīng)過k位從j-1位往左經(jīng)過k位max{k|1≤k＜j

且T[0]…T[k-1]=T[j-k]…T[j-1]}T[0]~T[k-1]=T[j-k]~T[j-1]的物理意義是什么？模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?模式匹配——KMP算法4.1字符串

next[j]函數(shù)值表示模式T中最大相同前綴和后綴（注意：是真子串）的長(zhǎng)度。模式中相似部分越多，next[j]函數(shù)值越大，表示模式T字符之間的相關(guān)度越高，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越好。模式匹配——KMP算法4.1字符串-1j=0max{k|1≤k＜j

且T[0]…T[k-1]=T[j-k]

…T[j-1]}0其它情況next[j]=當(dāng)j=0時(shí)，next[j]=-1；//next[j]=-1表示不進(jìn)行字符比較當(dāng)j>0時(shí)，next[j]的值為：模式串的位置從0到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長(zhǎng)度。當(dāng)無首尾相同的子串時(shí)next[j]的值為0。//next[j]=0表示從模式串頭部開始進(jìn)行字符比較計(jì)算next[j]的方法：模式匹配——KMP算法4.1字符串j=0時(shí),next[j]＝-1；j=1時(shí),next[j]＝0；模式串T：ababc

可能失配位j：01234新匹配位k=next[j]:-10模式匹配——KMP算法4.1字符串j=0時(shí),next[j]＝-1；j=1時(shí),next[j]＝0；j=2時(shí),T[0]≠T[1]，因此，k=0；模式串T：ababc

可能失配位j：01234新匹配位k=next[j]:-100模式匹配——KMP算法4.1字符串j=0時(shí),next[j]＝-1；j=1時(shí),next[j]＝0；j=2時(shí),T[0]≠T[1]，因此，k=0；j=3時(shí),T[0]＝T[2]，T[0]T[1]≠T[1]T[2]，因此，k=1；模式串T：ababc

可能失配位j：01234新匹配位k=next[j]:-1001模式匹配——KMP算法4.1字符串j=0時(shí),next[j]＝-1；j=1時(shí),next[j]＝0；j=2時(shí),T[0]≠T[1]，因此，k=0；j=3時(shí),T[0]＝T[2]，T[0]T[1]≠T[1]T[2]，因此，k=1；j=4時(shí),T[0]≠T[3]，T[0]T[1]=T[2]T[3]，T[0]T[1]T[2]≠T[1]T[2]T[3]，因此，k=2；模式串T：ababc

可能失配位j：01234新匹配位k=next[j]:-10012模式匹配——KMP算法4.1字符串模式匹配——KMP算法4.1字符串i=4，j=4失??；

j=next[4]=2ababaababcb

ij第1趟ababcnext[j]={-1,0,0,1,2}ababaababcb

ij第2趟ababc模式匹配——KMP算法4.1字符串i=5，j=3失??；

j=next[3]=1next[j]={-1,0,0,1,2}ababaababcb

ij第2趟ababcababaababcb

ij第3趟ababc模式匹配——KMP算法4.1字符串i=5，j=1失??；

j=next[1]=0next[j]={-1,0,0,1,2}ababaababcb

i第3趟jababcababaababcb

i第4趟jababc1.在串S和串T中分別設(shè)比較的起始下標(biāo)i和j；2.循環(huán)直到S或T的所有字符均比較完2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個(gè)字符；否則2.2將j向右滑動(dòng)到next[j]位置，即j=next[j]；2.3如果j=-1，則將i和j分別加1，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回0；

KMP算法的偽代碼描述4.1字符串?dāng)?shù)組的定義數(shù)組是由一組類型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素（簡(jiǎn)稱為元素），每個(gè)元素受n(n≥1)個(gè)線性關(guān)系的約束，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)i1、i2、…、in稱為該元素的下標(biāo)，并稱該數(shù)組為n維數(shù)組。數(shù)組的特點(diǎn)元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。4.2多維數(shù)組

a11a12…a1na21

a22…a2n

…………

am1am2…amnA=例如，元素a22受兩個(gè)線性關(guān)系的約束，在行上有一個(gè)行前驅(qū)a21和一個(gè)行后繼a23，在列上有一個(gè)列前驅(qū)a12和和一個(gè)列后繼a32。4.2

多維數(shù)組數(shù)組的定義

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)數(shù)組——線性表的推廣二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。4.2多維數(shù)組數(shù)組的基本操作在數(shù)組中插入（或）一個(gè)元素有意義嗎？

a11a12…a1na21a22…a2n

…………

am1am2…amnA=將元素x插入到數(shù)組中第1行第2列。x

a11a12…a1na21a22…a2n

…………

am1am2…amnA=刪除數(shù)組中第1行第2列元素。4.2多維數(shù)組數(shù)組的基本操作⑴存?。航o定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；⑵修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。存取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作——尋址數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲(chǔ)。4.2多維數(shù)組數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——一維數(shù)組設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間［l，h］，每個(gè)數(shù)組元素占用c個(gè)存儲(chǔ)單元，則其任一元素ai的存儲(chǔ)地址可由下式確定：Loc(ai)＝Loc(al)＋(i－l)×c

calai-1ai……ahal+1……Loc(al)Loc(ai)4.2多維數(shù)組常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。

按列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。

數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——二維數(shù)組二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)4.2多維數(shù)組l2h2

l1h1(a)二維數(shù)組aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)本行中aij前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aij按行優(yōu)先存儲(chǔ)的尋址4.2多維數(shù)組第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2＋1)＋(j

-l2)個(gè)元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按行優(yōu)先存儲(chǔ)的尋址按列優(yōu)先存儲(chǔ)的尋址方法與此類似。4.2多維數(shù)組Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×c

n（n＞2）維數(shù)組一般也采用按行優(yōu)先和按列優(yōu)先兩種存儲(chǔ)方法。請(qǐng)自行推導(dǎo)任一元素存儲(chǔ)地址的計(jì)算方法。數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——多維數(shù)組4.2多維數(shù)組4.3矩陣的壓縮存儲(chǔ)特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。稀疏矩陣：矩陣中有很多零元素。壓縮存儲(chǔ)的基本思想是：⑴為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；⑵

對(duì)零元素不分配存儲(chǔ)空間。

特殊矩陣和稀疏矩陣特殊矩陣的壓縮存儲(chǔ)——對(duì)稱矩陣3647862842481697460582957A＝對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。4.3矩陣的壓縮存儲(chǔ)(a)下三角矩陣(b)存儲(chǔ)說明(c)計(jì)算方法aij在一維數(shù)組中的序號(hào)=陰影部分的面積=

i×(i-1)/2+j-1∵一維數(shù)組下標(biāo)從0開始∴aij在一維數(shù)組中的下標(biāo)k=i×(i+1)/2+j

1…

in1…j…n

aij每行元素個(gè)數(shù)12…i-1aij在本行中的序號(hào)aij第1行第2行…第i-1行對(duì)稱矩陣的壓縮存儲(chǔ)

4.3矩陣的壓縮存儲(chǔ)對(duì)于下三角中的元素aij（i≥j），在數(shù)組SA中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因?yàn)閍ij＝aji，則訪問和它對(duì)應(yīng)的元素aji即可，即：k＝j(luò)×(j＋1)/2＋i。對(duì)稱矩陣的壓縮存儲(chǔ)

第1行第n-1行第0行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…第2行012345kn(n+1)/2-14.3矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)——三角矩陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣如何壓縮存儲(chǔ)？只存儲(chǔ)上三角（或下三角）部分的元素。4.3矩陣的壓縮存儲(chǔ)矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：i×(i＋1)/2＋j

當(dāng)i≥jn×(n＋1)/2當(dāng)i＜jk=下三角矩陣的壓縮存儲(chǔ)012345

k

n(n+1)/2第1行第0行

a11

a21

a22

a31

a32

aij…ann…第2行

c

a33存儲(chǔ)下三角元素對(duì)角線上方的常數(shù)——只存一個(gè)4.3矩陣的壓縮存儲(chǔ)矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：

上三角矩陣的壓縮存儲(chǔ)存儲(chǔ)上三角元素對(duì)角線上方的常數(shù)——只存一個(gè)4.3矩陣的壓縮存儲(chǔ)i×(2n－i＋1)/2＋j－i

當(dāng)i≤jn×(n＋1)/2當(dāng)i＞jk=A6×6=10000031200002960004-8355005991232053173756數(shù)據(jù)元素的物理位置:(L為一個(gè)數(shù)據(jù)的長(zhǎng)度)Loc(i,j)=Loc(0,0)+(i×(i+1)/2)×L+j×L4.3矩陣的壓縮存儲(chǔ)1、在一個(gè)n×n的方陣A中，若矩陣元素具有性質(zhì)：Aij=Aji(1≤i≤n,1≤j≤n)則稱方陣A為對(duì)稱方陣。2、在一個(gè)矩陣（方陣）中，只有上三角中（或下三角中）的元素不為零，而其余的元素均為零。稱為三角陣。壓縮存儲(chǔ)：只存儲(chǔ)上三角（或下三角），包括對(duì)角線的元素，所占存儲(chǔ)空間元為：從n2n(n+1)/24.3矩陣的壓縮存儲(chǔ)

特殊矩陣的壓縮存儲(chǔ)——對(duì)角矩陣

對(duì)角矩陣：所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零。

a00a01000a10a11

a12000a21

a22

a23000

a32

a33

a34000a43

a44A=4.3矩陣的壓縮存儲(chǔ)a00a010

00a10a11

a12000a21

a22

a23

000

a32

a33

a34000a43

a44A=將帶狀區(qū)域立起來0a00

a01a10a11

a12a21

a22

a23a32a33

a34a43

a440B=s＝j(luò)-i+1t=i映射到二維數(shù)組B中，映射關(guān)系對(duì)角矩陣的壓縮存儲(chǔ)4.3矩陣的壓縮存儲(chǔ)按行存儲(chǔ)元素aij在一維數(shù)組中的序號(hào)=2+3(i－1)+(j－i+2)=2i+j+1

∵一維數(shù)組下標(biāo)從0開始∴元素aij在一維數(shù)組中的下標(biāo)=2i+j(b)尋址的計(jì)算方法(c)壓縮到一維數(shù)組中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112對(duì)角矩陣的壓縮存儲(chǔ)

(a)三對(duì)角矩陣

0

00

000

000

000

A=a00a01a10a11

a12a21a22

a23a32a33

a34a43a444.3矩陣的壓縮存儲(chǔ)對(duì)角矩陣的特點(diǎn)：零元素的兩個(gè)下標(biāo)i和j之差的絕對(duì)值大于帶寬；零元素的個(gè)數(shù)為:

(n-s)*(n-s-1);每行的非零元素的個(gè)數(shù)最大不超過2s+1個(gè)；需要存儲(chǔ)的非零元素的個(gè)數(shù)為：

n2-(n-s)*(n-s-1)或n*(2s+1)-s*(s+1)4.3矩陣的壓縮存儲(chǔ)為了計(jì)算方便，除第1行和最后1行外，其余行均在非零端補(bǔ)足成2s+1個(gè)元素，再進(jìn)行順序存儲(chǔ)。所需空間元為：(2s+1)*(n-2)+2*(s+1)Loc(i+1,i+1)=loc(i,i)+(2s+1)*LLoc(i,j)=Loc(i,i)+(j-i)*LLoc(i,i)=Loc(1,1)(2s+1)*(i-1)*LLoc(i,j)=Loc(1,1)+((2s+1)*(i-1)+(j-i))*L4.3矩陣的壓縮存儲(chǔ)A6×6=1107000312811002966300-8353050012280003756ss

階:n=6帶寬:s=2L:一個(gè)數(shù)據(jù)的長(zhǎng)度Loc(i,j)=Loc(0,0)+(i×(2s+1))×L+(j-i)×L4.3矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)

1500000

0110000

000600

0000009

00000A=如何只存儲(chǔ)非零元素？注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。4.3矩陣的壓縮存儲(chǔ)template<classT>structelement{

introw,col;//行號(hào)，列號(hào)Titem//非零元素值};將稀疏矩陣中的每個(gè)非零元素表示為：(行號(hào)，列號(hào)，非零元素值)——三元組稀疏矩陣的壓縮存儲(chǔ)定義三元組：4.3矩陣的壓縮存儲(chǔ)三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。稀疏矩陣的壓縮存儲(chǔ)三元組表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))1500000

0110000

000600

0000009

00000A=如何存儲(chǔ)三元組表？4.3矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)—三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表1500220-15

0113000

000600

00000091

00000A=三元組順序表是否需要預(yù)留存儲(chǔ)空間？稀疏矩陣的修改操作三元組順序表的插入/刪除操作4.3矩陣的壓縮存儲(chǔ)采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-11500220-15

0113000

000600

00000091

00000A=7（非零元個(gè)數(shù)）是否對(duì)應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）6（矩陣的列數(shù)）稀疏矩陣的壓縮存儲(chǔ)—三元組順序表4.3矩陣的壓縮存儲(chǔ)存儲(chǔ)結(jié)構(gòu)定義：constintMaxTerm=100;template<classT>structSparseMatrix{Tdata[MaxTerm];//存儲(chǔ)非零元素intmu,nu,tu;//行數(shù)，列數(shù)，非零元個(gè)數(shù)};稀疏矩陣的壓縮存儲(chǔ)—三元組順序表4.3矩陣的壓縮存儲(chǔ)例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=三元組順序表操作—轉(zhuǎn)置操作4.3矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）00150491

1111

213

3022

326

50-15

空空空閑閑閑rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）4.3矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法—算法Ⅰ

基本思想：直接取，順序存。即在A的三元組順序表中依次找第0列、第1列、…直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B的三元組順序表中。4.3矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）設(shè)置矩陣B的行數(shù)、列數(shù)、非零元個(gè)數(shù)4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第0列非零元，順序存儲(chǔ)到矩陣B中

0015

04914.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0015

0491

1111在矩陣A中查找第1列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0015

0491

1111

213在矩陣A中查找第2列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0015

0491

1111

213

3022

326在矩陣A中查找第3列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）0015049111112133022326在矩陣A中查找第4列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）0015049111112133022326

50-15在矩陣A中查找第5列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）001504911111213302232650-15在矩陣A中查找第6列非零元，順序存儲(chǔ)到矩陣B中4.3矩陣的壓縮存儲(chǔ)1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個(gè)數(shù)；2.在B中設(shè)置初始存儲(chǔ)位置pb；3.for(col=最小列號(hào);col<=最大列號(hào);col++)3.1在A中查找列號(hào)為col的三元組；3.2交換其行號(hào)和列號(hào)，存入B中pb位置；3.3pb++；三元組順序表轉(zhuǎn)置算法Ⅰ—偽代碼4.3矩陣的壓縮存儲(chǔ)分析：A中第0列的第一個(gè)非零元素一定存儲(chǔ)在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在B中的位置便等于第0列的第一個(gè)非零元素在B中的位置加上第0列的非零元素的個(gè)數(shù)，以此類推。基本思想：順序取，直接存。即在A中依次取三元組，交換其行號(hào)和列號(hào)放到B中適當(dāng)位置。三元組順序表轉(zhuǎn)置算法—算法Ⅱ如何確定當(dāng)前從A中取出的三元組在B中的位置？4.3矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法—算法Ⅱ

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

001504911111213302232650-15第0列第1個(gè)非零元素第0列有2個(gè)非零元素第1列第1個(gè)非零元素4.3矩陣的壓縮存儲(chǔ)引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：num[nu]：存儲(chǔ)矩陣A中某列的非零元素的個(gè)數(shù)；cpot[nu]：初值表示矩陣A中某列的第一個(gè)非零元素在B中的位置。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：cpot[0]=0；cpot[col]=cpot[col-1]+num[col-1]；1≤col＜nunum與cpot存在如下遞推關(guān)系：三元組順序表轉(zhuǎn)置算法—算法Ⅱ4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

col012345num[col]21

12

01cpot[col]

023466根據(jù)矩陣A計(jì)算num和cpot

4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[0]cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]

3022cpot[3]將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

4.3矩陣的壓縮存儲(chǔ)

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[4]