1、1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,2,第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）,以銷毀數(shù)組函數(shù)為例,11,Status InitArray(Array /ap為va_list類型，是存放變長(zhǎng)參數(shù)表信息的類型,數(shù)組的基本操作函數(shù)說明（5個(gè)） （見教材P93-95）,12,for(i=0;i=0;-i) A.constants

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

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

4、如存放其所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。 實(shí)現(xiàn)方法： 將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組表來表示。,二、稀疏矩陣的操作,20,例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：用線性表表示：,21,法2：用三元組矩陣表示：,注意：為更可靠描述，通

5、常再加一行“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個(gè)數(shù),稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能 :-(,22,法三：用帶輔助向量的三元組表示。,方法： 增加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),23,法四：用十字鏈表表示,用途：方便稀疏矩陣的加減運(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)，即呈十字鏈狀。,以剛才的稀疏矩陣為例：,24,#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ù)

7、 int tu; /矩陣中非零元素總個(gè)數(shù) TsMatrix;,三元組表的順序存儲(chǔ)表示（見教材P98）：,/一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義,/整個(gè)三元組表的定義,25,二、稀疏矩陣的操作,三 元 組 表 a.data,三 元 組 表 b.data,M,T,（以轉(zhuǎn)置運(yùn)算為例）,目的：,26,答：肯定不正確！ 除了： （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è)元素

8、的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？,有兩種實(shí)現(xiàn)方法,壓縮轉(zhuǎn)置 (壓縮)快速轉(zhuǎn)置,提問：,27,方法1：壓縮轉(zhuǎn)置,思路：反復(fù)掃描a.data中的列序，從小到大依次進(jìn)行轉(zhuǎn)置。,三 元 組 表 a.data,三 元 組 表 b.data,1,1,2,2,col,q,1,2,3,4,28,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),29,1、主要時(shí)間消耗在

9、查找M.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)置算法的效率分析：,30,方法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,31,如果能預(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è)非零元素必定先被掃描到。,32,令：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

12、,3 5 7 8 8,col 1 2 3 4 5 6,33,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)值，供同一列下一非零元素定位之用！,34,1. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組(num 和cpos ）。,傳統(tǒng)轉(zhuǎn)置：O(mu*nu) 壓縮轉(zhuǎn)置：O(mu*tu) 壓縮快速

13、轉(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; for(col = 2; col =M.nu; col+) 循環(huán)次數(shù)nu; for( p =1; p =M.tu ; p + ) 循環(huán)次數(shù)tu; 該算法的時(shí)間復(fù)雜度(nu*2)+(tu*2)=O(nu+tu）,討論：最惡劣情況是tu=nu*mu(即矩陣中全部是非零元素）， 而此時(shí)的時(shí)間復(fù)雜

14、度也只是O(mu*nu)，并未超過傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。,小結(jié)：,稀疏矩陣相乘的算法見教材P101-103,35,5.4 廣義表的定義,廣義表是線性表的推廣，也稱為列表（lists） 記為： LS = ( a1 , a2 , ， an ),廣義表名 表頭(Head） 表尾 (Tail),1、定義：, 第一個(gè)元素是表頭，而其余元素組成的表稱為表尾； 用小寫字母表示原子類型，用大寫字母表示列表。,n是表長(zhǎng),在廣義表中約定：,討論：廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類型，也可以是列表； 當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。,36,2、特點(diǎn)：,有次序性 有長(zhǎng)度 有深度

15、可遞歸 可共享,一個(gè)直接前驅(qū)和一個(gè)直接后繼 表中元素個(gè)數(shù) 表中括號(hào)的重?cái)?shù) 自己可以作為自己的子表 可以為其他廣義表所共享,特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。,37,E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為遞歸表,1）A =( ) 2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C ) 5）E=(a, E),例1：求下列廣義表的長(zhǎng)度。,n=0，因?yàn)锳是空表 n=1，表中元素e是原子 n=2，a 為原子，(b,c,d)為子表 n=3，3個(gè)元素都是子表 n=2，a 為原子，E為子表,

16、D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表,38, A=( a , (b, A) ),例2：試用圖形表示下列廣義表. （設(shè) 代表原子， 代表子表）,e, D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ),的長(zhǎng)度為3，深度為3,的長(zhǎng)度為2，深度為,39,介紹兩種特殊的基本操作： GetHead( L) 取表頭(可能是原子或列表); GetTail(L ) 取表尾(一定是列表) 。,廣義表的抽象數(shù)據(jù)類型定義見教材P107-108,40,1. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;,例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10）,(k, p, h),（b）,(a,b),5. GetTail【（e）】 ; 6. GetHead 【 ( ( ) )】 . 7. GetTail【 ( ( ) ) 】 .,( ),(c,d),( ),( ),(c,d),41,5.5 廣義表的存儲(chǔ)結(jié)構(gòu),由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲(chǔ)結(jié)構(gòu)表示 ，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。,1.原子