1、2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義1第五章 數(shù)組、特殊矩陣和廣義表教學(xué)內(nèi)容：教學(xué)內(nèi)容：5.1 多維數(shù)組 5.2 特殊矩陣的壓縮存儲(chǔ) 5.3 稀疏矩陣 5.4 廣義表教學(xué)目的：教學(xué)目的：理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式； 理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算； 領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡單運(yùn)算； 了解廣義表的定義和基本運(yùn)算。教學(xué)重點(diǎn)：教學(xué)重點(diǎn)：多維數(shù)組的邏輯結(jié)構(gòu)； 多維組的兩種順序存儲(chǔ)方式，計(jì)算給定元素在存儲(chǔ)區(qū)中的地址； 對(duì)稱矩陣、三角矩陣的壓縮存儲(chǔ)方式； 稀疏矩陣的三元組表表示方法。教學(xué)難點(diǎn)：教學(xué)難點(diǎn)： 稀疏矩陣的壓縮存儲(chǔ)表示下的運(yùn)算的實(shí)現(xiàn)學(xué)時(shí)安排：學(xué)時(shí)安排：4學(xué)時(shí)

2、2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義25.1 多維數(shù)組 數(shù)組的邏輯結(jié)構(gòu)數(shù)組的邏輯結(jié)構(gòu) 數(shù)組的內(nèi)存映象數(shù)組的內(nèi)存映象2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義35.1.1 數(shù)組的邏輯結(jié)構(gòu) 數(shù)組是我們熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義4 數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來標(biāo)識(shí)，因此，在數(shù)組上不能做插入、

3、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1) 取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。 (2) 賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。 我們著重研究二維和三維數(shù)組，因?yàn)樗鼈兊膽?yīng)用是廣泛的，尤其是二維數(shù)組。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義5 5.1.2 數(shù)組的內(nèi)存映象 通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲(chǔ)結(jié)構(gòu)，這是因?yàn)閮?nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一個(gè)映象函數(shù)，則可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址。 對(duì)于一維數(shù)組按下標(biāo)順序分配即可。 對(duì)多維數(shù)組分配時(shí)，要把它的

4、元素映象存儲(chǔ)在一維存儲(chǔ)器中，一般有兩種存儲(chǔ)方式：一是以行為主序（或先行后列）的順序存放，如BASIC、PASCAL、COBOL、C等程序設(shè)計(jì)語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，如FORTRAN語言中，用的是以列為主序的分配順序，即一列一列地分配。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義6 以行為主序的分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個(gè)下標(biāo)再變，從右向左，最后是左下標(biāo)。以列為主序分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，從左向右，最后是右下標(biāo)。 2

5、022年3月22日數(shù)據(jù)結(jié)構(gòu)講義7 例如一個(gè)23二維數(shù)組，邏輯結(jié)構(gòu)可以用左圖表示。以行為主序的內(nèi)存映象如右圖（a）所示。 分配順序?yàn)椋篴11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列為主序的分配順序?yàn)椋篴11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它的內(nèi)存映象如右圖（b）所示。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義8 設(shè)有mn二維數(shù)組Amn，下面我們看按元素的下標(biāo)求其地址的計(jì)算： 以“以行為主序”的分配為例：設(shè)數(shù)組的基址為LOC(a11)，每個(gè)數(shù)組元素占據(jù)l個(gè)地址單元，那么aij 的物理地址可用一線性尋址函數(shù)計(jì)算： LOC(aij) = LOC(a11) + ( (i-1

6、)*n + j-1 ) * l 在C語言中，數(shù)組中每一維的下界定義為0，則： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推廣到一般的二維數(shù)組：Ac1.d1 c2.d2，則aij的物理地址計(jì)算函數(shù)為： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義9 同理對(duì)于三維數(shù)組Amnp，即mnp數(shù)組，對(duì)于數(shù)組元素aijk其物理地址為： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推廣到一般的三維數(shù)組：Ac1.d

7、1 c2.d2 c3.d3，則aijk的物理地址為： LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義10三維數(shù)組的邏輯結(jié)構(gòu)和以行為主序的分配示意圖如圖所示。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義11例5.1 若矩陣Amn 中存在某個(gè)元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫一個(gè)算法，找出A中的所有鞍點(diǎn)。 基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否

8、是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個(gè)二維數(shù)組表示。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義12void saddle (int A ,int m, int n) /*m,n是矩陣A的行和列*/ int i,j,min; for (i=0;im;i+) /*按行處理*/ min=Ai0 for (j=1; jn; j+) if (Aijmin ) min=Aij;/*找第i行最小值*/ for (j=0; jn; j+)/*檢測該行中的每一個(gè)最小值是否是鞍點(diǎn)*/ if (Aij=min ) k=j; p=0; while (pm & Apj=m) printf (%d,

9、%d,%dn, i ,k,min); 算法的時(shí)間性能為O(m*(n+m*n)。 2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義135.2 特殊矩陣的壓縮存儲(chǔ) 對(duì)稱矩陣對(duì)稱矩陣 三角矩陣三角矩陣 帶狀矩陣帶狀矩陣2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義145.2.1 對(duì)稱矩陣 對(duì)稱矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij=aji ，其中1i , jn，如圖所示是一個(gè)階對(duì)稱矩陣。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義15 對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分即可。比如，只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是中ji且1in，對(duì)于上三角中的元素aij ，它和對(duì)應(yīng)的aji相等，因此當(dāng)訪問的元素在上三角時(shí)，直接去訪

10、問和它對(duì)應(yīng)的下三角元素即可，這樣，原來需要n*n個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n+1)/2個(gè)存儲(chǔ)單元了，節(jié)約了n(n-1)/2個(gè)存儲(chǔ)單元，當(dāng)n較大時(shí)，這是可觀的一部分存儲(chǔ)資源。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義16 如何只存儲(chǔ)下三角部分？對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n*(n+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SAn(n+1)/2中，存儲(chǔ)順序可用下圖示意，這樣，原矩陣下三角中的某一個(gè)元素aij則具體對(duì)應(yīng)一個(gè)sak，下面的問題是要找到k與i、j之間的關(guān)系。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義17 對(duì)于下三角中的元素aij，其特點(diǎn)是：ij且1in，存儲(chǔ)到SA中后，根

11、據(jù)存儲(chǔ)原則，它前面有i-1行，共有1+2+i-1=i*(i-1)/2個(gè)元素，而aij又是它所在的行中的第j個(gè)，所以在上面的排列順序中，aij是第i*(i-1)/2+j個(gè)元素，因此它在SA中的下標(biāo)k與i、j的關(guān)系為： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 若ij，則aij是上三角中的元素，因?yàn)閍ij=aji ，這樣，訪問上三角中的元素aij時(shí)則去訪問和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素在SA中的對(duì)應(yīng)關(guān)系： k=j*(j-1)/2+i-1 (kn*(n+1)/2 ) 綜上所述，對(duì)于對(duì)稱矩陣中的任意元素ai j，若令I(lǐng)=max(i,j)，

12、J=min(i,j)，則將上面兩個(gè)式子綜合起來得到： k=I*(I-1)/2+J-1。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義185.2.2 三角矩陣三角矩陣 形如下圖的矩陣稱為三角矩陣，其中c為某個(gè)常數(shù)。其中(a)為下三角矩陣：主對(duì)角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對(duì)角線以下均為同一個(gè)常數(shù)；下面討論它們的壓縮存儲(chǔ)方法。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義191. 下三角矩陣 與對(duì)稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量，因?yàn)槭峭粋€(gè)常數(shù)，所以存一個(gè)即可，這樣一共存儲(chǔ)了n*(n+1)+1個(gè)元素，設(shè)存入向量：SAn*(n+1)+1中，這種的存儲(chǔ)方式可節(jié)約n*(n

13、-1)-1個(gè)存儲(chǔ)單元，sak 與aji 的對(duì)應(yīng)關(guān)系為：2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義202. 上三角矩陣 對(duì)于上三角矩陣，存儲(chǔ)思想與下三角類似，以行為主序順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常量。對(duì)于第1行，存儲(chǔ)n個(gè)元素，第2行存儲(chǔ)n-1個(gè)元素，第p行存儲(chǔ)(n-p+1)個(gè)元素，aij的前面有i-1行，共存儲(chǔ)：個(gè)元素，aij 是它所在的行中要存儲(chǔ)的第（j-i+1）個(gè)也就是上三角存儲(chǔ)順序中的第 (i-1)*(2n-i+2)/2+(j-i+1)個(gè)，因此它在SA中的下標(biāo)為：k=(i-1)*(2n-i+2)/2+j-i。 綜上， sak 與aji 的對(duì)應(yīng)關(guān)系為：2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義21

14、5.2.3 帶狀矩陣 n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m ，滿足當(dāng) i-j m 時(shí)，aij =0，這時(shí)稱w=2m-1為矩陣A的帶寬。下圖是一個(gè)w=3(m=2)的帶狀矩陣。帶狀矩陣也稱為對(duì)角矩陣。由下圖可看出，在這種矩陣中，所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零(或同一個(gè)常數(shù)c)。2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義22 一種壓縮方法是將A壓縮到一個(gè)n行w列的二維數(shù)組B中，如下圖所示，當(dāng)某行非零元素的個(gè)數(shù)小于帶寬w時(shí)，先存放非零元素后補(bǔ)零。那么aij 映射為b ij，映射關(guān)系為：2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義23

15、 另一種壓縮方法是將帶狀矩陣壓縮到向量C中去，按以行為主序，順序的存儲(chǔ)其非零元素，如下圖所示，按其壓縮規(guī)律，找到相應(yīng)的映象函數(shù)。 如當(dāng)w=3時(shí)，映象函數(shù)為： k=2*i+j-32022年3月22日數(shù)據(jù)結(jié)構(gòu)講義245.3 稀疏矩陣 稀疏矩陣的稀疏矩陣的三元組表存儲(chǔ)三元組表存儲(chǔ) 稀疏矩陣的十字鏈表存儲(chǔ)稀疏矩陣的十字鏈表存儲(chǔ)2022年3月22日數(shù)據(jù)結(jié)構(gòu)講義252022年3月22日數(shù)據(jù)結(jié)構(gòu)講義262022年3月22日數(shù)據(jù)結(jié)構(gòu)講義272022年3月22日數(shù)據(jù)結(jié)構(gòu)講義282022年3月22日數(shù)據(jù)結(jié)構(gòu)講義292022年3月22日數(shù)據(jù)結(jié)構(gòu)講義302022年3月22日數(shù)據(jù)結(jié)構(gòu)講義312022年3月22日數(shù)據(jù)結(jié)構(gòu)

16、講義322022年3月22日數(shù)據(jù)結(jié)構(gòu)講義332022年3月22日數(shù)據(jù)結(jié)構(gòu)講義342022年3月22日數(shù)據(jù)結(jié)構(gòu)講義352022年3月22日數(shù)據(jù)結(jié)構(gòu)講義362022年3月22日數(shù)據(jù)結(jié)構(gòu)講義372022年3月22日數(shù)據(jù)結(jié)構(gòu)講義382022年3月22日數(shù)據(jù)結(jié)構(gòu)講義392022年3月22日數(shù)據(jù)結(jié)構(gòu)講義402022年3月22日數(shù)據(jù)結(jié)構(gòu)講義412022年3月22日數(shù)據(jù)結(jié)構(gòu)講義422022年3月22日數(shù)據(jù)結(jié)構(gòu)講義432022年3月22日數(shù)據(jù)結(jié)構(gòu)講義442022年3月22日數(shù)據(jù)結(jié)構(gòu)講義452022年3月22日數(shù)據(jù)結(jié)構(gòu)講義462022年3月22日數(shù)據(jù)結(jié)構(gòu)講義472022年3月22日數(shù)據(jù)結(jié)構(gòu)講義482022年3月22日數(shù)據(jù)結(jié)構(gòu)講義492022年3月22日數(shù)據(jù)結(jié)構(gòu)講義502022年3月22日數(shù)據(jù)結(jié)構(gòu)講義512022年3月22日數(shù)據(jù)結(jié)構(gòu)講義522022年3月22日數(shù)據(jù)結(jié)構(gòu)講義532022年3月22日數(shù)據(jù)結(jié)構(gòu)講義542022年3月22日數(shù)據(jù)結(jié)構(gòu)講義552022年3月22日數(shù)據(jù)結(jié)構(gòu)講義562022年3月22日數(shù)據(jù)結(jié)構(gòu)講義572022年3月22日數(shù)據(jù)結(jié)構(gòu)講義582022年3月22日數(shù)據(jù)結(jié)構(gòu)講義592022年3月