第4章字符串和多維數組

第4

章字符串和多維數組

本章的基本內容是：

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

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

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

s1

s2……sn

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

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

串的邏輯結構例：S1="ab12cd"，S2="ab12"，S3="ab13"4.1字符串方案1：用一個變量來表示串的實際長度。

如何表示串的長度？串的存儲結構0123456……Max-1

abcdefg9空閑4.1字符串方案1：用一個變量來表示串的實際長度。

串的存儲結構如何表示串的長度？01234567……Max-1

abcdefg\0空閑方案2：在串尾存儲一個不會在串中出現的特殊字符作為串的終結符，表示串的結尾。

4.1字符串方案3：用數組的0號單元存放串的長度，從1號單元開始存放串值。串的存儲結構如何表示串的長度？方案2：在串尾存儲一個不會在串中出現的特殊字符作為串的終結符，表示串的結尾。

方案1：用一個變量來表示串的實際長度。

01234567……Max-1

9

abcdefg空閑4.1字符串模式匹配

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

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

否則，從主串S的第二個字符開始和模式T的第一個字符進行比較；重復上述過程，直到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失敗；i回溯到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中設比較的起始下標i和j；2.循環(huán)直到S或T的所有字符均比較完2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個字符；2.2否則，將i和j回溯，準備下一趟比較；3.如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標；否則，匹配失敗，返回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算法設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況：例如：S="aaaaaaaaaabcdccccc"T="bcd"4.1字符串最好情況：不成功的匹配都發(fā)生在串T的第1個字符。模式匹配——BF算法設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況：最好情況：不成功的匹配都發(fā)生在串T的第1個字符。設匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能情況共有n-m+1種，則：)(2)()1(11mnOmnmipmnii+=+=?+-′+-=4.1字符串模式匹配——BF算法設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串T的最后一個字符。例如：S="aaaaaaaaaaabccccc"T="aaab"4.1字符串模式匹配——BF算法設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串T的最后一個字符。設匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)×m次，第i趟成功的匹配共比較了m次，所以總共比較了i×m次，因此4.1字符串模式匹配——KMP算法為什么BF算法時間性能低？在每趟匹配不成功時存在大量回溯，沒有利用已經部分匹配的結果。如何在匹配不成功時主串不回溯？主串不回溯，模式就需要向右滑動一段距離。如何確定模式的滑動距離？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字符串需要討論兩個問題：①如何由當前部分匹配結果確定模式向右滑動的新比較起點k？②模式應該向右滑多遠才是最高效率的?結論：i可以不回溯，模式向右滑動到的新比較起點k

，并且k僅與模式串T有關！模式匹配——KMP算法4.1字符串抓住部分匹配時的兩個特征：設模式滑動到第k個字符（1）則T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法4.1字符串ababcab……abcacijababcab……abcacij=k下一趟抓住部分匹配時的兩個特征：設模式滑動到第k個字符（1）則T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法4.1字符串ababca

b……abcacijababca

b……abcacij=k下一趟（2）則T[j-k]~T[j-1]=S[i-k]~S[i-1]兩式聯立可得：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

具有函數關系，由當前失配位置j，可以計算出滑動位置k（即比較的新起點）；（2）滑動位置k

僅與模式串T有關。從第0位往右經過k位從j-1位往左經過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]的物理意義是什么？模式應該向右滑多遠才是最高效率的?模式匹配——KMP算法4.1字符串

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

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

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

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

可能失配位j：01234新匹配位k=next[j]:-100模式匹配——KMP算法4.1字符串j=0時,next[j]＝-1；j=1時,next[j]＝0；j=2時,T[0]≠T[1]，因此，k=0；j=3時,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時,next[j]＝-1；j=1時,next[j]＝0；j=2時,T[0]≠T[1]，因此，k=0；j=3時,T[0]＝T[2]，T[0]T[1]≠T[1]T[2]，因此，k=1；j=4時,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中分別設比較的起始下標i和j；2.循環(huán)直到S或T的所有字符均比較完2.1如果S[i]=T[j]，繼續(xù)比較S和T的下一個字符；否則2.2將j向右滑動到next[j]位置，即j=next[j]；2.3如果j=-1，則將i和j分別加1，準備下一趟比較；3.如果T中所有字符均比較完畢，則返回匹配的起始下標；否則返回0；

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

a11a12…a1na21

a22…a2n

…………

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

多維數組數組的定義

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

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

a11a12…a1na21a22…a2n

…………

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

a11a12…a1na21a22…a2n

…………

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

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

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

數組的存儲結構與尋址——二維數組二維數組內存二維結構一維結構4.2多維數組l2h2

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

-l1)×(h2

-l2＋1)＋(j

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

-l1)×(h2

-l2＋1)＋(j

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

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

對零元素不分配存儲空間。

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

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

1…

in1…j…n

aij每行元素個數12…i-1aij在本行中的序號aij第1行第2行…第i-1行對稱矩陣的壓縮存儲

4.3矩陣的壓縮存儲對于下三角中的元素aij（i≥j），在數組SA中的下標k與i、j的關系為：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因為aij＝aji，則訪問和它對應的元素aji即可，即：k＝j×(j＋1)/2＋i。對稱矩陣的壓縮存儲

第1行第n-1行第0行

a11

a21

a22

a31

a32

a33

aij…

an1

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

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣如何壓縮存儲？只存儲上三角（或下三角）部分的元素。4.3矩陣的壓縮存儲矩陣中任一元素aij在數組中的下標k與i、j的對應關系：i×(i＋1)/2＋j

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

k

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

a11

a21

a22

a31

a32

aij…ann…第2行

c

a33存儲下三角元素對角線上方的常數——只存一個4.3矩陣的壓縮存儲矩陣中任一元素aij在數組中的下標k與i、j的對應關系：

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

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

特殊矩陣的壓縮存儲——對角矩陣

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

a00a01000a10a11

a12000a21

a22

a23000

a32

a33

a34000a43

a44A=4.3矩陣的壓縮存儲a00a010

00a10a11

a12000a21

a22

a23

000

a32

a33

a34000a43

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

a01a10a11

a12a21

a22

a23a32a33

a34a43

a440B=s＝j-i+1t=i映射到二維數組B中，映射關系對角矩陣的壓縮存儲4.3矩陣的壓縮存儲按行存儲元素aij在一維數組中的序號=2+3(i－1)+(j－i+2)=2i+j+1

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

(a)三對角矩陣

0

00

000

000

000

A=a00a01a10a11

a12a21a22

a23a32a33

a34a43a444.3矩陣的壓縮存儲對角矩陣的特點：零元素的兩個下標i和j之差的絕對值大于帶寬；零元素的個數為:

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

n2-(n-s)*(n-s-1)或n*(2s+1)-s*(s+1)4.3矩陣的壓縮存儲為了計算方便，除第1行和最后1行外，其余行均在非零端補足成2s+1個元素，再進行順序存儲。所需空間元為：(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矩陣的壓縮存儲A6×6=1107000312811002966300-8353050012280003756ss

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

1500000

0110000

000600

0000009

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

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

0110000

000600

0000009

00000A=如何存儲三元組表？4.3矩陣的壓縮存儲稀疏矩陣的壓縮存儲—三元組順序表采用順序存儲結構存儲三元組表1500220-15

0113000

000600

00000091

00000A=三元組順序表是否需要預留存儲空間？稀疏矩陣的修改操作三元組順序表的插入/刪除操作4.3矩陣的壓縮存儲采用順序存儲結構存儲三元組表

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-11500220-15

0113000

000600

00000091

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

0113000

000600

00000091

00000A=三元組順序表操作—轉置操作4.3矩陣的壓縮存儲0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）00150491

1111

213

3022

326

50-15

空空空閑閑閑rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）4.3矩陣的壓縮存儲三元組順序表轉置算法—算法Ⅰ

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

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）設置矩陣B的行數、列數、非零元個數4.3矩陣的壓縮存儲

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）在矩陣A中查找第0列非零元，順序存儲到矩陣B中

0015

04914.3矩陣的壓縮存儲

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

0015

0491

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

0015

0491

1111

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

0015

0491

1111

213

3022

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）0015049111112133022326

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）001504911111213302232650-15在矩陣A中查找第6列非零元，順序存儲到矩陣B中4.3矩陣的壓縮存儲1.設置轉置后矩陣B的行數、列數和非零元個數；2.在B中設置初始存儲位置pb；3.for(col=最小列號;col<=最大列號;col++)3.1在A中查找列號為col的三元組；3.2交換其行號和列號，存入B中pb位置；3.3pb++；三元組順序表轉置算法Ⅰ—偽代碼4.3矩陣的壓縮存儲分析：A中第0列的第一個非零元素一定存儲在B中下標為0的位置上，該列中其它非零元素應存放在B中后面連續(xù)的位置上，那么第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數，以此類推?；舅枷耄喉樞蛉。苯哟?。即在A中依次取三元組，交換其行號和列號放到B中適當位置。三元組順序表轉置算法—算法Ⅱ如何確定當前從A中取出的三元組在B中的位置？4.3矩陣的壓縮存儲三元組順序表轉置算法—算法Ⅱ

rowcolitem0123456MaxTerm-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

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

0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

col012345num[col]21

12

01cpot[col]

023466根據矩陣A計算num和cpot

4.3矩陣的壓縮存儲

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

rowcolitem01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[0]cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]4.3矩陣的壓縮存儲

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]

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

4.3矩陣的壓縮存儲

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）

rowcolitem01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[1]cpot[2]cpot[4]