數(shù)據(jù)結(jié)構(gòu) 課件 第05章.ppt

1、1,第5章 數(shù)組和廣義表（Arrays /數(shù)組元素基址 int dim; /數(shù)組維數(shù) int *bound; /數(shù)組各維長(zhǎng)度信息保存區(qū)基址 int *constants; /數(shù)組映像函數(shù)常量的基址 Array;,即Ci信息保存區(qū),數(shù)組的基本操作函數(shù)說明（有5個(gè)） （請(qǐng)閱讀教材P93-95）,N維數(shù)組的順序存儲(chǔ)表示（見教材P93）,10,Status InitArray(Array /*ap為va_list類型，是存放變長(zhǎng)參數(shù)表信息的類型,dim參數(shù)的寫法是類C的*/,數(shù)組的基本操作函數(shù)說明（5個(gè)） （見教材P93-95）,11,for(i=0;i=0;-i) A.constantsi=A.bo

2、undsi+1*A.constantsi+1; return OK; ,12,數(shù)組基址指針,各維長(zhǎng)度保存區(qū)指針,映像函數(shù)Ci保存區(qū)指針,Status DestroyArray(Array ,13,Status Locate(Array A, va_list ap, int ,14,Status Value(Array A, ElemType ,15,Status Assign(Array ,16,順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。,行指針向量,補(bǔ)充：鏈?zhǔn)酱鎯?chǔ)方式：用帶行指針向量的單鏈表來表示。,注：數(shù)組的運(yùn)算參見下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）,（難點(diǎn)是多維數(shù)組與一維數(shù)組

3、的地址映射關(guān)系）,17,5.3 矩陣的壓縮存儲(chǔ),討論： 1. 什么是壓縮存儲(chǔ)？ 若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。 2. 所有二維數(shù)組（矩陣）都能壓縮嗎？ 未必，要看矩陣是否具備以上壓縮條件。 3. 什么樣的矩陣具備以上壓縮條件？ 一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。 4. 什么叫稀疏矩陣？ 矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）,重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。,18,一、稀疏矩陣的壓縮存儲(chǔ),問題： 如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？ 解決思路： 對(duì)每個(gè)非零元素增開若干存儲(chǔ)單元，例如存放其

4、所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。 實(shí)現(xiàn)方法： 將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組表來表示。,二、稀疏矩陣的操作,19,例1 ：,三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 、 和 。,行下標(biāo),列下標(biāo),元素值,例2：寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。,( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7),法1：用線性表表示：,20,法2：用三元組矩陣表示：,注意：為更可靠描述，通常再加一

5、行“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個(gè)數(shù),稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能 : (,21,法三：用帶輔助向量的三元組表示。,方法： 增加2個(gè)輔助向量： 記錄每行非0元素個(gè)數(shù)，用NUM（i）表示； 記錄稀疏矩陣中每行第一個(gè)非0元素在三元組中的行號(hào)，用POS（i）表示。,7,6,5,3,1,3,用途：通過三元組高效訪問稀疏矩陣中任一非零元素。,規(guī)律：POS(1)1 POS(i)POS(i-1)+NUM(i-1),22,法四：用十字鏈表表示,用途：方便稀疏矩陣的加減運(yùn)算； 方法：每個(gè)非0元素占用5個(gè)域。,同一列中下一非零元素的指針,同一行中下一非零元素的指針,十字鏈表的特點(diǎn)： 每行

6、非零元素鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表； 每列非零元素也鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表。 則每個(gè)非零元素既是行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)；又是列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。,以剛才的稀疏矩陣為例：,23,#define MAXSIZE 125000 /設(shè)非零元素最大個(gè)數(shù)125000 typedef struct int i; /元素行號(hào) int j; /元素列號(hào) ElemType e; /元素值 Triple; typedef struct Triple dataMAXSIZE+1; /三元組表，以行為主序存入一維向量 data 中 int mu; /矩陣總行數(shù) int nu; /矩陣總列數(shù) int

7、 tu; /矩陣中非零元素總個(gè)數(shù) TsMatrix;,三元組表的順序存儲(chǔ)表示（見教材P98）：,/一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義,/整個(gè)三元組表的定義,24,二、稀疏矩陣的操作,三 元 組 表 a.data,三 元 組 表 b.data,M,T,（以轉(zhuǎn)置運(yùn)算為例）,目的：,25,答：肯定不正確！ 除了： （1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i和j互換）； 還應(yīng)該：（2）T的總行數(shù)mu和總列數(shù)nu與M值不同（互換）； （3）重排三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。,上述（1）和（2）容易實(shí)現(xiàn)，難點(diǎn)在（3）。,若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)

8、和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？,有兩種實(shí)現(xiàn)方法,壓縮轉(zhuǎn)置 (壓縮)快速轉(zhuǎn)置,提問：,26,方法1：壓縮轉(zhuǎn)置,思路：反復(fù)掃描a.data中的列序，從小到大依次進(jìn)行轉(zhuǎn)置。,三 元 組 表 a.data,三 元 組 表 b.data,1,1,2,2,col,q,1,2,3,4,27,Status TransposeSMatrix(TSMatrix M, TSMatrix ,壓縮轉(zhuǎn)置算法描述：（見教材P99）,/用三元組表存放稀疏矩陣M，求M的轉(zhuǎn)置矩陣T,/q是轉(zhuǎn)置矩陣T的結(jié)點(diǎn)編號(hào),/col是掃描M三元表列序的變量,/p是M三元表中結(jié)點(diǎn)編號(hào),28,1、主要時(shí)間消耗在查找M.

9、datap.j= =col的元素，由兩重循環(huán)完成: for(col=1; col=M.nu; col+) 循環(huán)次數(shù)nu for(p=1; p=M.tu; p+) 循環(huán)次數(shù)tu 所以該算法的時(shí)間復(fù)雜度為O(nu*tu) -即M的列數(shù)與M中非零元素的個(gè)數(shù)之積 最惡劣情況：M中全是非零元素，此時(shí)tu=mu*nu， 時(shí)間復(fù)雜度為 O(nu2*mu ) 注：若M中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過是O(nu*mu) （程序見教材P99） 結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。 前提：僅適用于非零元素個(gè)數(shù)很少（即tumu*nu）的情況。,壓縮轉(zhuǎn)置算法的效率分析：,29,方法2 快速轉(zhuǎn)置,

10、三 元 組 表 a.data,三 元 組 表 b.data,思路：依次把a(bǔ).data中的元素直接送入b.data的恰當(dāng)位置上（即M三元組的p指針不回溯）。,關(guān)鍵：怎樣尋找b.data的“恰當(dāng)”位置？,q,3,5,30,如果能預(yù)知M矩陣每一列(即T的每一行)的非零元素個(gè)數(shù)，又能預(yù)知第一個(gè)非零元素在b.data中的位置,則掃描a.data時(shí)便可以將每個(gè)元素準(zhǔn)確定位（因?yàn)橐阎舾蓞⒖键c(diǎn)）。,技巧：利用帶輔助向量的三元組表，它正好攜帶每行（或列）的非零元素個(gè)數(shù) NUM(i)以及每行（或列）的第一個(gè)非零元素在三元組表中的位置POS(i) 等信息。,設(shè)計(jì)思路：,不過我們需要的是按列生成的M矩陣的輔助向量。

11、,規(guī)律：POS(1)1 POS(i)POS(i-1)+NUM(i-1),請(qǐng)回憶：,請(qǐng)注意a.data特征：每列首個(gè)非零元素必定先被掃描到。,31,令：M中的列變量用col表示； num col ：存放M中第col 列中非0元素個(gè)數(shù)， cpot col ：存放M中第col列的第一個(gè)非0元素的位置， （即b.data中待計(jì)算的“恰當(dāng)”位置所需參考點(diǎn)）,討論：按列優(yōu)先的輔助向量求出后，下一步該如何操作？ 由a.data中每個(gè)元素的列信息，即可直接查出b.data中的重要參考點(diǎn)之位置，進(jìn)而可確定當(dāng)前元素之位置！,規(guī)律： cpot(1)1 cpotcol cpotcol-1 + numcol-1,M,3

12、 5 7 8 8,col 1 2 3 4 5 6,32,Status FastTransposeSMatrix（TSMatirx M, TSMatirx ,快速轉(zhuǎn)置算法描述：,/M用順序存儲(chǔ)表示，求M的轉(zhuǎn)置矩陣T,/先統(tǒng)計(jì)每列非零元素個(gè)數(shù),/再生成每列首元位置輔助向量表,/p指向a.data，循環(huán)次數(shù)為非0元素總個(gè)數(shù)tu,/查輔助向量表得q，即T中位置,/*重要語句修改向量表中列坐標(biāo)值，供同一列下一非零元素定位之用！同時(shí)cpot向量應(yīng)該有備份以便以后對(duì)轉(zhuǎn)置后的矩陣進(jìn)行其他的操作*/,33,1. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組(num 和cpot ）。,傳統(tǒng)轉(zhuǎn)置：O(mu*nu) 壓縮轉(zhuǎn)置：O(mu*tu) 壓縮快速轉(zhuǎn)置：O(nu+tu)犧牲空間效率換時(shí)間效率。,快速轉(zhuǎn)置算法的效率分析：,2. 從時(shí)間上，此算法用了4個(gè)并列的單循環(huán)，而且其中前3個(gè)單循環(huán)都是用來產(chǎn)生輔助向量表的。 for(col = 1; col =M.nu; col+) 循環(huán)次數(shù)nu; for( i = 1; i =M.tu; i +) 循環(huán)次數(shù)tu; fo