1、第四章 多維數(shù)組數(shù)據(jù)結構(sh j ji u)與STL共三十一頁數(shù)據(jù)結構(sh j ji u)與STL2第四章 多維數(shù)組和廣義(gungy)表學習內容：4.1 多維數(shù)組 4.2 矩陣的壓縮存儲 4.3 廣義表 (略) 4.4 實例分析4.5 使用STL操作多維數(shù)組共三十一頁數(shù)據(jù)結構(sh j ji u)與STL34.1 多維數(shù)組 由類型相同的數(shù)據(jù)元素(yun s)構成的有序集合。 對于k 維數(shù)組，每個元素都要受k個線性關系的約束。 數(shù)組一般不執(zhí)行刪除和插入操作，所以常采用順序存儲方法來存儲數(shù)組。通常有兩種存儲方式：行優(yōu)先存儲和列優(yōu)先存儲。共三十一頁數(shù)據(jù)結構(sh j ji u)與STL4 行優(yōu)

2、先存儲(cn ch) 按行存儲，即存完第i行再接著存儲第i+1行。按行優(yōu)先順序存儲二維數(shù)組Amn，線性a11,a12,a1n,a21,a22,a2n,am1,am2,amnLoc(aij) =Loc(a11) + (i-1)*n + j-1)*c 在C+、PASCAL等語言中，數(shù)組都是按行優(yōu)先存儲的 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL5 列優(yōu)先存儲 按列存儲，即存完第i列再接著(ji zhe)存儲第i+1列。 存儲二維數(shù)組Amn，按列優(yōu)先順序存儲的線性序列為： a11,a21,am1,a12,a22,am2,a1n,a2n,amnLoc(aij)=Loc(a11)+ (i-1 +

3、 m*(j-1)*c 在FORTRAN語言中，數(shù)組是按列優(yōu)先存儲的共三十一頁三維數(shù)組示意(shy)：Amnp m-片，n-行，p-列 行優(yōu)先方式(fngsh)：先排最右端的下標，從右向左。12mnp先排第一片第一行 第一片第二行 第n行 第二片第一行 第二行 m共三十一頁數(shù)據(jù)結構(sh j ji u)與STL7多維數(shù)組的存儲(cn ch) C+中設三維數(shù)組Amnp，第一個元素為a000，若按行優(yōu)先存儲，則aijk前面共有inp+jp+k個元素;若按列優(yōu)先存儲，則aijk前面共有i+mj+mnk個元素; 試分析四維數(shù)組或更高維數(shù)組的行優(yōu)先存儲和列優(yōu)先存儲。 共三十一頁數(shù)據(jù)結構(sh j ji u

4、)與STL8第四章 多維數(shù)組學習內容：4.1 多維數(shù)組 4.2 矩陣的壓縮存儲 4.3 廣義表 4.4 實例分析4.5 使用(shyng)STL操作多維數(shù)組共三十一頁數(shù)據(jù)結構(sh j ji u)與STL94.2 矩陣(j zhn)的壓縮存儲 矩陣是一種常見的處理對象 矩陣可看作是二維數(shù)組 對于一些數(shù)據(jù)元素具有特殊規(guī)律的矩陣，常常采用一些特殊的存儲方法以節(jié)省存儲空間 對稱矩陣特殊矩陣壓縮存儲 三角矩陣 對角矩陣 稀疏矩陣壓縮存儲 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL10 對稱(duchn)矩陣 共需要存儲的元素數(shù)目 設所有元素存儲到一維數(shù)組Sa中，aij存儲在Sak中，k 與 ij

5、 的關系？ k = i(i+1)/2 + j （ij）若aij位于矩陣的上三角，如何存儲？共三十一頁數(shù)據(jù)結構(sh j ji u)與STL11 上三角中的元素aij（ij），因為aij aji ， 則訪問(fngwn)和它對應的元素aji即可： kj(j1)/2i 。思考：設n階對稱矩陣按行優(yōu)先方式存儲下三角元素，元素a00存儲在Sa0元素中，元素aij存儲在Sa100元素中，則下標i、j的值為多少？共三十一頁數(shù)據(jù)結構(sh j ji u)與STL12三角(snjio)矩陣 三角矩陣分為上三角矩陣和下三角矩陣。設n階方陣A，若其下三角的元素除對角線外均為常數(shù)c，即aij=c，0jin，則稱該方

6、陣為 上三角矩陣 對于n階三角矩陣，需要存儲n(n+1)/2+1個元素 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL13 按行優(yōu)先存儲n階上三角(snjio)矩陣，設aij存儲到sak中 若aij位于矩陣上三角，有0ijn，則在存儲aij之前， sa數(shù)組中首先要存儲前i行上三角的元素，然后再存儲aij所在行從aii到ai,j-1的元素 ： 若aij位于矩陣下三角，有0jin，此時所有的aij具有相同的值，只需保存1個值 k = n(n+1)/2 (0jin)共三十一頁數(shù)據(jù)結構(sh j ji u)與STL14思 考 按行優(yōu)先存儲n階下三角矩陣時，首先存儲下三角的元素，最后(zuhu)存儲上

7、三角的常數(shù)項c。給出aij與sak的對應關系。 對于按列優(yōu)先方式存儲的n階三角矩陣，請推導元素存儲位置k與下標i、j的對應關系 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL15對角(du jio)矩陣 所有非零元素都集中在對角線附近的方陣 三對角矩陣 在存儲對角矩陣時，可將對角線附近的帶狀區(qū)域元素立起來，形成一個列數(shù)較少的新矩陣，然后可按行優(yōu)先方式存儲這個新矩陣。 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL16 n 維 m 對角矩陣A（m為奇數(shù)），設其對角線附近的元素aij存儲到一維數(shù)組元素sak中。由于aij在對角線附近，因此有：max(i-(m-1)/2,0)jmin(i+(m-

8、1)/2,n-1) aij之前共有i行，每行m個元素，因此首先要存儲這mi個元素。在aij所在(suzi)行上，aij之前共有j-i+(m-1)/2個元素。因此在存儲aij之前，總共要存儲mi+j-i+(m-1)/2個元素，即有：k=mi+j-i+(m-1)/2=(m-1)i+j+(m-1)/2共三十一頁數(shù)據(jù)結構(sh j ji u)與STL174.2.2 稀疏(xsh)矩陣壓縮存儲 矩陣Amn中的非零元素個數(shù)s 遠遠小于矩陣元素的總數(shù)mn 存儲稀疏矩陣時，只需要存儲非零元素。 常見的稀疏矩陣壓縮方法：三元組表和十字鏈表 稀疏矩陣中每個非零元素的行號、列號及值構成一個三元組（3-triples

9、） 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL18#define MAX_ELEMENT_NUMBER 1000template struct MatrixNode /定義三元組結構int row;/非零元素(yun s)的行號int col;/非零元素的列號T value;/非零元素的值;template struct SpareMatrix/定義三元組表結構int m;/稀疏矩陣的行數(shù)int n;/稀疏矩陣的列數(shù)int t;/稀疏矩陣非零元素的個數(shù)MatrixNode dataMAX_ELEMENT_NUMBER; /存儲非零元素對應的三元組;共三十一頁數(shù)據(jù)結構(sh j ji u)

10、與STL19稀疏矩陣(j zhn)的轉置操作 轉置共三十一頁數(shù)據(jù)結構(sh j ji u)與STL20稀疏矩陣簡單轉置(zhun zh)算法 遍歷n 趟三元組表： 第一趟遍歷找出列號為0的三元組，并將其行號和列號對調，添加到轉置矩陣對應的三元組表中。 第二趟遍歷找出列號為1的三元組并進行相同操作， 依次類推，最后一趟遍歷找出列號為n-1的三元組。 由于每趟遍歷都需要比較所有的t個三元組的列號，因此算法的時間復雜度為O(nt)。 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL21簡單(jindn)轉置算法/將稀疏矩陣OrigMat轉置為TransMattemplate void TransMa

11、t(SpareMatrix * OrigMat, SpareMatrix * TransMat) TransMat-m = OrigMat-n; /設置轉置矩陣的行數(shù) TransMat-n = OrigMat-m; /設置轉置矩陣的列數(shù) TransMat-t = 0; /初始時轉置矩陣的非零元素個數(shù)為 for (int col=0;coln;col+) for (int j=0;jt;j+)if (OrigMat-dataj.col = col) /找出列號為col的三元組 TransMat-dataTransMat-t.col = OrigMat-dataj.row ; TransMat-d

12、ataTransMat-t.row = OrigMat-dataj.col ; TransMat-dataTransMat-t.value = OrigMat-dataj.value ; TransMat-t+; /非零元素個數(shù)增共三十一頁數(shù)據(jù)結構(sh j ji u)與STL22快速稀疏矩陣轉置(zhun zh)算法時間復雜度為O(n+t) 在原始三元組表（設為A）依次取每個三元組，交換其行號和列號后，直接存放到轉置矩陣的三元組表（設為B）中的適當位置。 關鍵的問題：如何確定三元組在B中的位置 A中第0列的第一個非零元素一定存儲在B中下標為0的位置上，該列中其它非零元素應存放在B0后面連續(xù)的

13、位置上。 第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數(shù)。共三十一頁數(shù)據(jù)結構(sh j ji u)與STL23引入兩個數(shù)組作為輔助數(shù)據(jù)結構(sh j ji u)：numbern： 存儲矩陣A中每列非零元素的個數(shù)；positionn：初始值表示矩陣A中每列的第一個非零 元素在B中的位置 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL24A=15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0number 0 0 15 0 3 22 0 5 -15 1 1 11 1

14、 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 矩陣的行數(shù)5 矩陣的列數(shù)6 非零元個數(shù)7row col item0123456Max-1position21120123466 空 空 空 閑 閑 閑 矩陣的行數(shù)6 矩陣的列數(shù)5 非零元個數(shù)7row col item0123456Max-10015010 1 2 3 4 53022550-157111132134326604912共三十一頁數(shù)據(jù)結構(sh j ji u)與STL25算法(sun f)偽代碼1. 設置轉置矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)；2. 計算A中每一列的非零元素個數(shù)，存儲到number數(shù)組；3. 計算A中每一列的

15、第一個非零元素在B中的下標，存儲到position數(shù)組；4. 依次取A中的每一個非零元素對應的三元組； 4.1 確定該元素在B中的下標pb； 4.2 將該元素的行號列號交換后存入B中pb的位置； 4.3 預置該元素所在列的下一個元素的存放位置；共三十一頁數(shù)據(jù)結構(sh j ji u)與STL26十字(sh z)鏈表 每個非零元素，采用一個五元組結點表示 template struct snode/十字鏈表五元組結點int row,col;/行號與列號T val;/值struct snode * cnext, rnext;/列指針與行指針;同一行的非零元素構成一個帶頭結點的循環(huán)鏈表，同一列的非零

16、元素也構成一個帶頭結點的循環(huán)鏈表。 共三十一頁數(shù)據(jù)結構(sh j ji u)與STL27共三十一頁數(shù)據(jù)結構(sh j ji u)與STL28第四章 多維數(shù)組和廣義(gungy)表學習內容：4.1 多維數(shù)組 4.2 矩陣的壓縮存儲 4.3 廣義表 （略） 4.4 實例分析4.5 使用STL操作多維數(shù)組共三十一頁數(shù)據(jù)結構(sh j ji u)與STL294.5 使用(shyng)STL操作多維數(shù)組 STL本身并沒有二維、三維等多維數(shù)組的概念，但并不能說STL不支持多維數(shù)組 vector vector ivv; 對象ivv是向量的向量，相當于一個二維數(shù)組，但各維上元素的數(shù)目可以不同。 注意：“ ”非

17、“” 如果希望向量各維上的元素數(shù)目都相同，可以基于vector單獨設計一個二維數(shù)組的類來完成此功能。見教材對C2DVector類的定義。C2DVector my2DArray(3,4); /建立一個 34 的數(shù)組。My2DArray.GrowCol(5); /動態(tài)增加到 5 列。類中已經(jīng)重載了操作符 ，因此它可以像常規(guī) C/C+ 二維數(shù)組一樣使用。my2DArrayxy = 5；共三十一頁數(shù)據(jù)結構(sh j ji u)與STL30本章(bn zhn)小結多維數(shù)組廣義表實例分析操作多維數(shù)組邏輯結構存儲結構存儲尋址行優(yōu)先存儲列優(yōu)先存儲對稱矩陣三角矩陣對角矩陣邏輯結構存儲結構稀疏矩陣三元組表STL矩陣壓縮十字鏈表廣義鏈表BMP文件操作圖像平滑轉置算法共三十一頁內容摘要第四章 多維數(shù)組。對于k 維數(shù)組，每個元素(yun s)都要受k個線性關系的約束。行優(yōu)先存儲。列優(yōu)先存儲。若按行優(yōu)先存儲，則aijk前面共