1、2022年3月22日數據結構講義1第五章 數組、特殊矩陣和廣義表教學內容：教學內容：5.1 多維數組 5.2 特殊矩陣的壓縮存儲 5.3 稀疏矩陣 5.4 廣義表教學目的：教學目的：理解多維數組的結構特點和在內存中的兩種順序存儲方式； 理解并掌握矩陣和特殊矩陣元素在存儲區中地址的計算； 領會稀疏矩陣的壓縮方式和簡單運算； 了解廣義表的定義和基本運算。教學重點：教學重點：多維數組的邏輯結構； 多維組的兩種順序存儲方式，計算給定元素在存儲區中的地址； 對稱矩陣、三角矩陣的壓縮存儲方式； 稀疏矩陣的三元組表表示方法。教學難點：教學難點： 稀疏矩陣的壓縮存儲表示下的運算的實現學時安排：學時安排：4學時

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

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

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

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

6、)*n + j-1 ) * l 在C語言中，數組中每一維的下界定義為0，則： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推廣到一般的二維數組：Ac1.d1 c2.d2，則aij的物理地址計算函數為： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l2022年3月22日數據結構講義9 同理對于三維數組Amnp，即mnp數組，對于數組元素aijk其物理地址為： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推廣到一般的三維數組：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日數據結構講義10三維數組的邏輯結構和以行為主序的分配示意圖如圖所示。2022年3月22日數據結構講義11例5.1 若矩陣Amn 中存在某個元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。 基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否

8、是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個二維數組表示。2022年3月22日數據結構講義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+)/*檢測該行中的每一個最小值是否是鞍點*/ if (Aij=min ) k=j; p=0; while (pm & Apj=m) printf (%d,

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

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

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

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

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

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

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

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