ch5 數(shù)組和廣義表

1、1第第5章章 數(shù)組和廣義表（數(shù)組和廣義表（Arrays & Lists）5.1 數(shù)組的定義數(shù)組的定義5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)(即數(shù)組的應(yīng)用即數(shù)組的應(yīng)用)5.4 廣義表的定義廣義表的定義5.5 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu)2線(xiàn)性表線(xiàn)性表具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置限制插入、刪除位置線(xiàn)性表線(xiàn)性表具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。限制元素類(lèi)型為字符限制元素類(lèi)型為字符棧棧僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表

2、。隊(duì)列隊(duì)列在一端進(jìn)行插入操作，而另一端進(jìn)行在一端進(jìn)行插入操作，而另一端進(jìn)行 刪除操作的線(xiàn)性表。刪除操作的線(xiàn)性表。串串零個(gè)或多個(gè)字符組成的有限序列零個(gè)或多個(gè)字符組成的有限序列 。特殊線(xiàn)性表特殊線(xiàn)性表第第5章章 數(shù)組和廣義表數(shù)組和廣義表 3線(xiàn)性表線(xiàn)性表具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。具有相同類(lèi)型的數(shù)據(jù)元素的有限序列。將元素的類(lèi)型進(jìn)行擴(kuò)充將元素的類(lèi)型進(jìn)行擴(kuò)充廣義線(xiàn)性表廣義線(xiàn)性表（多維）數(shù)組（多維）數(shù)組線(xiàn)性表中的數(shù)據(jù)元素可以是線(xiàn)性表中的數(shù)據(jù)元素可以是線(xiàn)性表，但所有元素的類(lèi)型相同。線(xiàn)性表，但所有元素的類(lèi)型相同。廣義表廣義表線(xiàn)性表中的數(shù)據(jù)元素可以是線(xiàn)性表，線(xiàn)性表中的數(shù)據(jù)元素可以是線(xiàn)性表，且元素的類(lèi)型可以

3、不相同。且元素的類(lèi)型可以不相同。第第5章章 數(shù)組和廣義表數(shù)組和廣義表 45.1 數(shù)組的定義數(shù)組的定義數(shù)組是由一組數(shù)組是由一組類(lèi)型相同類(lèi)型相同的數(shù)據(jù)元素構(gòu)成的的數(shù)據(jù)元素構(gòu)成的有序有序集集合合，每個(gè)數(shù)據(jù)元素稱(chēng)為一個(gè)數(shù)組元素（簡(jiǎn)稱(chēng)為元每個(gè)數(shù)據(jù)元素稱(chēng)為一個(gè)數(shù)組元素（簡(jiǎn)稱(chēng)為元素），每個(gè)元素受素），每個(gè)元素受n(n1)個(gè)個(gè)線(xiàn)性關(guān)系線(xiàn)性關(guān)系的約束，的約束，每每個(gè)元素在個(gè)元素在n個(gè)線(xiàn)性關(guān)系中的序號(hào)個(gè)線(xiàn)性關(guān)系中的序號(hào)i1、i2、in稱(chēng)為稱(chēng)為該元素的下標(biāo)，并稱(chēng)該數(shù)組為該元素的下標(biāo)，并稱(chēng)該數(shù)組為 n 維數(shù)組。維數(shù)組。 數(shù)組的特點(diǎn)數(shù)組的特點(diǎn)元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類(lèi)型；元素本身可以具有某種結(jié)構(gòu)，屬于同一

4、數(shù)據(jù)類(lèi)型；數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。5 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受兩個(gè)線(xiàn)性關(guān)系的約束，在行上有受兩個(gè)線(xiàn)性關(guān)系的約束，在行上有一個(gè)行前驅(qū)一個(gè)行前驅(qū)a21和一個(gè)行后繼和一個(gè)行后繼a23，在列上有一個(gè)列，在列上有一個(gè)列前驅(qū)前驅(qū)a12和和一個(gè)列后繼和和一個(gè)列后繼a32。數(shù)組示例數(shù)組示例5.1 數(shù)組的定義數(shù)組的定義6 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)

5、二維數(shù)組是數(shù)據(jù)元素為線(xiàn)性表的線(xiàn)性表。二維數(shù)組是數(shù)據(jù)元素為線(xiàn)性表的線(xiàn)性表。5.1 數(shù)組的定義數(shù)組的定義7ADT Array 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:5.1 數(shù)組的定義數(shù)組的定義8二維數(shù)組的定義二維數(shù)組的定義:數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: : D = aij | 0ib1-1, 0 jb2-1數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: : R = ROW, COL

6、ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-29基本操作基本操作：InitArray (&A, n, bound1, ., boundn)DestroyArray(&A)操作結(jié)果：操作結(jié)果：若維數(shù)若維數(shù) n 和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的 數(shù)組數(shù)組A，并返回，并返回OK。操作結(jié)果：操作結(jié)果：銷(xiāo)毀數(shù)組銷(xiāo)毀數(shù)組A。10Value(A, &e, index1, ., indexn) 初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素變量，隨后是為元素變量，隨后是n 個(gè)個(gè) 下標(biāo)值。下標(biāo)值。 操作結(jié)果：操作

7、結(jié)果：若各下標(biāo)不超界，則若各下標(biāo)不超界，則e賦值為所指定的賦值為所指定的A 的元素值，并返回的元素值，并返回OK。Assign(&A, e, index1, ., indexn)初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素變量，隨后是為元素變量，隨后是n 個(gè)下個(gè)下 標(biāo)值。標(biāo)值。操作結(jié)果：操作結(jié)果：若下標(biāo)不超界，則將若下標(biāo)不超界，則將e的值賦給所指定的的值賦給所指定的A的的 元素，并返回元素，并返回OK?；静僮骰静僮鳎?1數(shù)組的基本操作數(shù)組的基本操作 存取：給定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；存?。航o定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素； 修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的修

8、改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。數(shù)組元素。存取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作存取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作尋址尋址數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組沒(méi)有插入和刪除操作，所以，不用預(yù)留空間，數(shù)組沒(méi)有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲(chǔ)。適合采用順序存儲(chǔ)。5.1 數(shù)組的定義數(shù)組的定義12類(lèi)型特點(diǎn)類(lèi)型特點(diǎn):1) 只有引用型操作，沒(méi)有加工型操作只有引用型操作，沒(méi)有加工型操作;2) 數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)個(gè) 一維的結(jié)構(gòu)。一維的結(jié)構(gòu)。有兩種順序映象的方式有兩種順序映象的方式:1)以行序?yàn)橹餍蛞孕行驗(yàn)橹餍?/p>

9、(低下標(biāo)優(yōu)先低下標(biāo)優(yōu)先);2)以列序?yàn)橹餍蛞粤行驗(yàn)橹餍?高下標(biāo)優(yōu)先高下標(biāo)優(yōu)先);5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn) 135.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)一維一維設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間l，h，每個(gè)每個(gè)數(shù)組元素占用數(shù)組元素占用 c 個(gè)存儲(chǔ)單元，則個(gè)存儲(chǔ)單元，則其其任一元任一元素素 ai 的的存儲(chǔ)地址可由下式確定：存儲(chǔ)地址可由下式確定： Loc(ai)Loc(al) (il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)14常用的映射方法有兩種：常用的映射方法有兩種：按按行行優(yōu)先：優(yōu)先：先行后列先行后列，

10、先存儲(chǔ)行號(hào)較小的元素，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。 按按列列優(yōu)先：優(yōu)先：先列后行先列后行，先存儲(chǔ)列號(hào)較小的元素，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。 二維數(shù)組二維數(shù)組內(nèi)內(nèi) 存存二維結(jié)構(gòu)二維結(jié)構(gòu)一維結(jié)構(gòu)一維結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)二維二維15l2h2 l1h1(a) 二維數(shù)組二維數(shù)組aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)=陰影部分的面積陰影部分的面積=整行數(shù)每行元素個(gè)數(shù)整行數(shù)每行元素個(gè)數(shù)+本行中本行中aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)=( (i - -l1) )(

11、(h2 - -l21) )( (j - -l2) )本行中本行中aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)每行元素個(gè)數(shù)每行元素個(gè)數(shù)整整行行數(shù)數(shù)aij按行優(yōu)先存儲(chǔ)的尋址按行優(yōu)先存儲(chǔ)的尋址5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)二維二維16第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )個(gè)元素個(gè)元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按行優(yōu)先存儲(chǔ)的尋址按行優(yōu)先存儲(chǔ)的尋址

12、按列優(yōu)先存儲(chǔ)的尋址方法與此類(lèi)似。按列優(yōu)先存儲(chǔ)的尋址方法與此類(lèi)似。5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)二維二維17Loc (j1, j2, jn)=LOC(0,0,0)若是若是N維數(shù)組，其中任一元素的地址該如何計(jì)算？維數(shù)組，其中任一元素的地址該如何計(jì)算？niii1jC其中其中Cn=L, Ci-1=biCi， 1in Ci = bi+1 bi+2 bn L一個(gè)元素長(zhǎng)度一個(gè)元素長(zhǎng)度數(shù)組基址數(shù)組基址前面若干元素占用前面若干元素占用的地址字節(jié)總數(shù)的地址字節(jié)總數(shù)第第i i維長(zhǎng)度維長(zhǎng)度與所存元素個(gè)數(shù)有關(guān)的系與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出數(shù)，可用遞推法求出教材已給出教材已給出低維優(yōu)先低維

13、優(yōu)先的地址計(jì)算公式，的地址計(jì)算公式，見(jiàn)見(jiàn)P93（5-2）式式該式稱(chēng)為該式稱(chēng)為n n維數(shù)組的映像函數(shù)維數(shù)組的映像函數(shù)： C i = b i+1 b i+2 b n L5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)NN維維18“行序?yàn)橹餍蛐行驗(yàn)橹餍颉?即即 “低下標(biāo)優(yōu)低下標(biāo)優(yōu)先先”“列序?yàn)橹餍蛄行驗(yàn)橹餍颉?即即 “高下標(biāo)優(yōu)高下標(biāo)優(yōu)先先”如如: A324 的存儲(chǔ)次序?yàn)榈拇鎯?chǔ)次序?yàn)?(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,0),(0,1,3),(1,0,0),(1,1,0),(1,1,3),(2,0,0),(2,1,3)(0,0,0),(1,0,0),(2,0,0)

14、,(0,1,0),(2,1,0),(0,0,1),(0,1,1),(0,0,2),(2,1,2),(0,0,3),(2,1,3)則則 A324 的存儲(chǔ)次序?yàn)榈拇鎯?chǔ)次序?yàn)?19例例2：已知二維數(shù)組已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K 按列存儲(chǔ)的公式是？按列存儲(chǔ)的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （盡管是方陣，但公式仍不同）（盡管是方陣，但公式仍不同）例例1軟考題軟考題：一個(gè)二維數(shù)組一個(gè)二維數(shù)組A A，行下標(biāo)的范圍是，行下標(biāo)的范圍是1到到6， 列下標(biāo)

15、的范圍是列下標(biāo)的范圍是0到到7，每個(gè)數(shù)組元素用相鄰的，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存?zhèn)€字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是多少儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是多少個(gè)字節(jié)？個(gè)字節(jié)？ 288答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288練習(xí)：練習(xí)：20例例3：設(shè)數(shù)組設(shè)數(shù)組a160, 170的基地址為的基地址為2048，每個(gè)元，每個(gè)元素占素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的存儲(chǔ)地址為的存儲(chǔ)地址為 。LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-

16、c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：答：請(qǐng)注意審題！請(qǐng)注意審題！ 利用列優(yōu)先通式：利用列優(yōu)先通式：8950練習(xí)：練習(xí)：21#define MAX_ARRAY_DIM 8 /假設(shè)最大維數(shù)為假設(shè)最大維數(shù)為8 8 typedef struct ELemType *base; /數(shù)組元素基址數(shù)組元素基址 int dim; /數(shù)組維數(shù)數(shù)組維數(shù) int *bound; /數(shù)組數(shù)組各維長(zhǎng)度信息保存區(qū)各維長(zhǎng)度信息保存區(qū)基址基址 int *constants; /數(shù)組數(shù)組映像函數(shù)常量映像函數(shù)常量的基址的基址 Array;即

17、即Ci信息保存區(qū)信息保存區(qū)數(shù)組的基本操作函數(shù)說(shuō)明（有數(shù)組的基本操作函數(shù)說(shuō)明（有4個(gè)）個(gè)）（請(qǐng)閱讀教材（請(qǐng)閱讀教材P93-95）N維數(shù)組的順序存儲(chǔ)表示（見(jiàn)教材見(jiàn)教材P93）以銷(xiāo)毀數(shù)組函數(shù)為例以銷(xiāo)毀數(shù)組函數(shù)為例22 ：利用宏利用宏va_start、va_arg和和va_end提供提供遍歷未知數(shù)目和類(lèi)型的函數(shù)參數(shù)表的功能。遍歷未知數(shù)目和類(lèi)型的函數(shù)參數(shù)表的功能。Va_start ( va_list ap, x )：初始化初始化ap，使其指向所，使其指向所在函數(shù)的參數(shù)在函數(shù)的參數(shù)x x之后的第一個(gè)參數(shù)。之后的第一個(gè)參數(shù)。Va_arg ( va_list ap , 類(lèi)型類(lèi)型)：返回返回apap當(dāng)前指向的參

18、數(shù)當(dāng)前指向的參數(shù)的值，并修改的值，并修改ap，使得，使得ap指向下一個(gè)參數(shù)（指向下一個(gè)參數(shù)（“類(lèi)型類(lèi)型”為參數(shù)類(lèi)型）。為參數(shù)類(lèi)型）。Va_end ( va_list ap)：用在所有的參數(shù)處理完畢之后，用在所有的參數(shù)處理完畢之后，表示表示ap使用完畢。使用完畢。幾個(gè)函數(shù)說(shuō)明：幾個(gè)函數(shù)說(shuō)明：23Status InitArray (Array &A, int dim,) /若維數(shù)若維數(shù)dim和各維長(zhǎng)度合法，則和各維長(zhǎng)度合法，則并返回并返回OK if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim

19、* sizeof(int); if(!a.bounds) exit (OVERFLOW); / 分配存放分配存放“各維長(zhǎng)度各維長(zhǎng)度”的空間的空間 /若各維長(zhǎng)度合法，則存入若各維長(zhǎng)度合法，則存入A.bounds, ,并求出并求出A的元素總數(shù)的元素總數(shù)elemtotal elemtotal=1; va_start(ap, dim); /ap為為va_list類(lèi)型，是存放變長(zhǎng)參數(shù)表信息的類(lèi)型，將類(lèi)型，是存放變長(zhǎng)參數(shù)表信息的類(lèi)型，將ap指指向向dim后后的第一個(gè)參數(shù)的第一個(gè)參數(shù)數(shù)組的基本操作函數(shù)說(shuō)明（數(shù)組的基本操作函數(shù)說(shuō)明（5個(gè)）個(gè)） （見(jiàn)教材見(jiàn)教材P93-95）24 for(i=0;idim;+i)

20、 A.boundsi=va_arg (ap, int); / 返回返回ap當(dāng)前指向的參數(shù)，并按參數(shù)類(lèi)型將當(dāng)前指向的參數(shù)，并按參數(shù)類(lèi)型將ap指向下一個(gè)參數(shù)指向下一個(gè)參數(shù) if (A.boundsi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK; b i+1 C i+1 26數(shù)組基址指針數(shù)組基址指針各維長(zhǎng)度保各維長(zhǎng)度保存區(qū)指針存區(qū)指針映像函數(shù)映像函數(shù)Ci保存區(qū)指針保存區(qū)指針Status DestroyArray (Array &A) /銷(xiāo)毀數(shù)組銷(xiāo)毀數(shù)組A A if ( ! A.base ) return ERROR; fr

21、ee(A.base); A .base = NULL; if ( ! A.bounds ) return ERROR; free( A .bounds ); A.bounds = NULL; if ( !A.constants ) return ERROR; free ( A. constants ) ; A. constants = NULL; return OK; 數(shù)組的基本操作函數(shù)數(shù)組的基本操作函數(shù) 27Status Locate(Array A, va_list ap, int &off) /若若ap指示的各下標(biāo)值合法，則求出該元素在指示的各下標(biāo)值合法，則求出該元素在A中相對(duì)地

22、址中相對(duì)地址off off=0; for(i=0;iA.dim;+i) ind= va_arg(ap, int); if (indA.boundsi) return OVERFLOW; off += A.constantsi * ind ; C i j i return OK; 數(shù)組的基本操作函數(shù)數(shù)組的基本操作函數(shù) 28Status Value(Array A, ElemType &e,) /A是是n n維數(shù)組，維數(shù)組，e e為元素變量，隨后是為元素變量，隨后是n n個(gè)下標(biāo)值，若各下個(gè)下標(biāo)值，若各下 標(biāo)不超界，則標(biāo)不超界，則e e賦值為所指定的賦值為所指定的A A的元素值，即將指定元素

23、的元素值，即將指定元素 值讀到值讀到e e變量中。變量中。 va_start (ap, e); / / 將將apap指向指向e e后的參數(shù)后的參數(shù) if (result=Locate(A, ap, off)=0) return result; e=*(A.base+off); return OK; 數(shù)組的基本操作函數(shù)數(shù)組的基本操作函數(shù) 29Status Assign(Array &A,ElemType e,) /A是是n n維數(shù)組，維數(shù)組，e e為元素變量，隨后是為元素變量，隨后是n n個(gè)下標(biāo)值，若各下個(gè)下標(biāo)值，若各下 標(biāo)不超界，則標(biāo)不超界，則e e的值賦為所指定的的值賦為所指定的A

24、A的元素值，的元素值， va_start(ap,e); if( (result=Locate(A,ap,off ) )=0) return result; *(A.base+off)=e; return OK; 數(shù)組的基本操作函數(shù)數(shù)組的基本操作函數(shù) 30行指針向量行指針向量a11a12a1nam1am2amn 鏈?zhǔn)酱鎯?chǔ)方式：鏈?zhǔn)酱鎯?chǔ)方式：用帶行指針向量的單鏈表來(lái)表示。用帶行指針向量的單鏈表來(lái)表示。注：注：數(shù)組的運(yùn)算參見(jiàn)下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）數(shù)組的運(yùn)算參見(jiàn)下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）補(bǔ)充：補(bǔ)充： 315.3 矩陣的壓縮存儲(chǔ)一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ) 二二. 稀疏矩陣的壓縮

25、存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三三. 稀疏矩陣的轉(zhuǎn)置操作稀疏矩陣的轉(zhuǎn)置操作 325.3 矩陣的壓縮存儲(chǔ)討論：討論：1. 什么是壓縮存儲(chǔ)？什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的若多個(gè)數(shù)據(jù)元素的值都相同值都相同，則只分配一個(gè)元素值的，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2. 什么樣的矩陣具備壓縮條件？什么樣的矩陣具備壓縮條件？ 特殊矩陣（對(duì)稱(chēng)矩陣，對(duì)角矩陣，三角矩陣）特殊矩陣（對(duì)稱(chēng)矩陣，對(duì)角矩陣，三角矩陣）和稀疏矩陣。和稀疏矩陣。33特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的分布矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。有一定的規(guī)律。稀疏矩陣稀疏

26、矩陣: :矩陣中非零元素的個(gè)數(shù)較少（一般小于矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）壓縮存儲(chǔ)的基本思想是：壓縮存儲(chǔ)的基本思想是： 為多個(gè)值為多個(gè)值相同相同的元素只分配的元素只分配一個(gè)一個(gè)存儲(chǔ)空間；存儲(chǔ)空間； 對(duì)對(duì)零零元素元素不分配不分配存儲(chǔ)空間。存儲(chǔ)空間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣5.3 矩陣的壓縮存儲(chǔ)34一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩對(duì)稱(chēng)矩陣陣 3647862842481697460582957A對(duì)稱(chēng)矩陣特點(diǎn)：對(duì)稱(chēng)矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。只存儲(chǔ)下三角部分的元素。35(a) 下三角矩陣下三角矩陣 (b) 存儲(chǔ)說(shuō)

27、明存儲(chǔ)說(shuō)明 (c) 計(jì)算方法計(jì)算方法aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=陰影部分的面積陰影部分的面積= i( (i+1) )/2+ j+1一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開(kāi)始開(kāi)始aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素個(gè)數(shù)每行元素個(gè)數(shù)12iaij在本行中的序號(hào)在本行中的序號(hào)aij第第0行行第第1行行第第i-1行行一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩對(duì)稱(chēng)矩陣陣 36對(duì)于對(duì)于下三角下三角中的元素中的元素aij（ij），在數(shù)組，在數(shù)組SA中的下標(biāo)中的下標(biāo)k與與i、j的關(guān)系為：的關(guān)系為：ki(

28、i1)/2j 。上三角上三角中的元素中的元素aij（ij），），因?yàn)橐驗(yàn)閍ijaji，則訪(fǎng)問(wèn)和則訪(fǎng)問(wèn)和它對(duì)應(yīng)的元素它對(duì)應(yīng)的元素aji即可，即：即可，即：kj(j1)/2i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-1一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩對(duì)稱(chēng)矩陣陣 37一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)三角矩陣三角矩陣 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩陣下三角矩陣

29、3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩陣上三角矩陣如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)上三角（或下三角）部分的元素。只存儲(chǔ)上三角（或下三角）部分的元素。38矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系：i( (i1) )/2j 當(dāng)當(dāng)ijn( (n1) )/2 當(dāng)當(dāng)ijk=下三角矩陣的壓縮存儲(chǔ)下三角矩陣的壓縮存儲(chǔ)0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22存儲(chǔ)存儲(chǔ)下三角下三角元素元素對(duì)角

30、線(xiàn)上方的常數(shù)對(duì)角線(xiàn)上方的常數(shù)只存一個(gè)只存一個(gè)一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)三角矩陣三角矩陣 39矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系： i( (2ni1) )/2ji 當(dāng)當(dāng)ijn( (n1) ) /2 當(dāng)當(dāng)ijk=上三角矩陣的壓縮存儲(chǔ)上三角矩陣的壓縮存儲(chǔ)存儲(chǔ)存儲(chǔ)上三角上三角元素元素對(duì)角線(xiàn)上方的常數(shù)對(duì)角線(xiàn)上方的常數(shù)只存一個(gè)只存一個(gè)一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)三角矩陣三角矩陣 40對(duì)角矩陣：對(duì)角矩陣：所有非零元素都集中在以主對(duì)角線(xiàn)為中心所有非零元素都集中在以主對(duì)角線(xiàn)為中心的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了

31、主對(duì)角線(xiàn)和它的上下方若干條對(duì)對(duì)角線(xiàn)和它的上下方若干條對(duì)角線(xiàn)的元素外，所有其他元素都為零。角線(xiàn)的元素外，所有其他元素都為零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 41a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=將帶狀區(qū)將帶狀區(qū)域立起來(lái)域立起來(lái)0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a4

32、4 0B=sj- -i+1t=i映射到二維數(shù)組映射到二維數(shù)組B中，映射關(guān)系中，映射關(guān)系一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 42按行按行存儲(chǔ)存儲(chǔ) 元素元素aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開(kāi)始開(kāi)始元素元素aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)=2i+ j(b) 尋址的計(jì)算方法尋址的計(jì)算方法(c) 壓縮到一維數(shù)組中壓縮到一維數(shù)組中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6

33、7 8 9 10 11 12(a) 三對(duì)角矩陣三對(duì)角矩陣 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44一一. 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 43二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存儲(chǔ)問(wèn)題：?jiǎn)栴}：如果只存儲(chǔ)如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的稀疏矩陣中的非零元素，那這些元素的位置信息位置信息該如何表示？該如何表示？解決思路：解決思路：對(duì)每個(gè)非零元素對(duì)每個(gè)非零元素增開(kāi)增開(kāi)若干存儲(chǔ)單元，例如存放其所若干存儲(chǔ)單元，例如存放其所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置

34、。在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。實(shí)現(xiàn)方法：實(shí)現(xiàn)方法：將每個(gè)非零元素用一個(gè)三元組將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來(lái)表示，來(lái)表示，則每個(gè)則每個(gè)稀疏矩陣可用一個(gè)稀疏矩陣可用一個(gè)三元組表三元組表來(lái)表示。來(lái)表示。44將稀疏矩陣中的每個(gè)非零元素表示為將稀疏矩陣中的每個(gè)非零元素表示為：( (行號(hào)，列號(hào)，非零元素值行號(hào)，列號(hào)，非零元素值) )三元組三元組定義三元組：定義三元組：二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存儲(chǔ)#define MAXSIZE 125000 /設(shè)非零元素最大個(gè)數(shù)設(shè)非零元素最大個(gè)數(shù)125000 typedef struct int i; /元素行號(hào)元素行號(hào) in

35、t j; /元素列號(hào)元素列號(hào) ElemType e; /元素值元素值 Triple;/一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義45三元組表三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線(xiàn)性表。按行優(yōu)先的順序排列成一個(gè)線(xiàn)性表。三元組表三元組表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存儲(chǔ)三元組表？如何存儲(chǔ)三元組表？二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存

36、儲(chǔ)46稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組順序表三元組順序表二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存儲(chǔ)typedef struct Triple dataMAXSIZE+1; /三元組表，以行為主序存入一維向量三元組表，以行為主序存入一維向量 data 中中 int mu; /矩陣總行數(shù)矩陣總行數(shù) int nu; /矩陣總列數(shù)矩陣總列數(shù) int tu; /矩陣中非零元素總個(gè)數(shù)矩陣中非零元素總個(gè)數(shù) TsMatrix; /整個(gè)三元組表的定義整個(gè)三元組表的定義47采用采用鏈接鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表，每個(gè)非零元素對(duì)應(yīng)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表，每個(gè)非零元素對(duì)應(yīng)的三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為：的

37、三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為： rowcolitemdownrightrow：存儲(chǔ)非零元素的行號(hào)存儲(chǔ)非零元素的行號(hào)col：存儲(chǔ)非零元素的列號(hào)存儲(chǔ)非零元素的列號(hào)item：存儲(chǔ)非零元素的值存儲(chǔ)非零元素的值right：指針域，指向同一行中的下一個(gè)三元組指針域，指向同一行中的下一個(gè)三元組down：指針域，指向同一列中的下一個(gè)三元組指針域，指向同一列中的下一個(gè)三元組稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)十字鏈表十字鏈表二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存儲(chǔ)480 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7

38、 0 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(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, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三三元元組組表表a.data三三元元組組表表b.data轉(zhuǎn)置后轉(zhuǎn)置后MT目的：目的：三、稀疏矩陣的轉(zhuǎn)置操作三、稀疏矩陣的轉(zhuǎn)置操作

39、49答：答：肯定不正確！肯定不正確！除了：除了： （1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的的i i和和j j互換互換）；）；還應(yīng)該還應(yīng)該：（：（2）T T的總行數(shù)的總行數(shù)mumu和總列數(shù)和總列數(shù)nunu與與M M的不同的不同（互換）；互換）； （3）重排重排三元組內(nèi)元素順序三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。按行（或列）為主序有規(guī)律的排列。上述（上述（1 1）和（）和（2 2）容易實(shí)現(xiàn)，難點(diǎn)在）容易實(shí)現(xiàn)，難點(diǎn)在（3 3）。 若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)若采用三元組壓縮技術(shù)存儲(chǔ)稀疏

40、矩陣，只要把每個(gè)元素的元素的行下標(biāo)和列下標(biāo)互換行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說(shuō)法正確嗎？算，這種說(shuō)法正確嗎？ 有兩種實(shí)現(xiàn)方法有兩種實(shí)現(xiàn)方法壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置( (壓縮壓縮) )快速轉(zhuǎn)置快速轉(zhuǎn)置提問(wèn)：提問(wèn)：50算法算法 壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置基本思想：基本思想：直接取，順序存直接取，順序存。即。即在在A的三元組順序的三元組順序表中表中依次依次找第找第0列、第列、第1列、列、直到最后一列的三元直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后組，并將找到的每個(gè)三元組的行、列交換后順序順序存存儲(chǔ)到儲(chǔ)到B的三元組順序表中。的三元組順序表中。 三、稀疏矩陣的

41、轉(zhuǎn)置操作三、稀疏矩陣的轉(zhuǎn)置操作51方法方法1 1：壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置思路：思路：反復(fù)掃描反復(fù)掃描a.data中的中的列序列序，從小到大依次進(jìn)行轉(zhuǎn)置。，從小到大依次進(jìn)行轉(zhuǎn)置。三三元元組組表表a.data三三元元組組表表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)11 22col q1234 p1234521.

42、 設(shè)置轉(zhuǎn)置后矩陣設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個(gè)數(shù)；的行數(shù)、列數(shù)和非零元個(gè)數(shù)；2. 在在B中設(shè)置初始存儲(chǔ)位置中設(shè)置初始存儲(chǔ)位置pb；3. for (col=最小列號(hào)最小列號(hào); col=最大列號(hào)最大列號(hào); col+) 3.1 在在A中查找列號(hào)為中查找列號(hào)為col的三元組；的三元組； 3.2 交換其行號(hào)和列號(hào)，存入交換其行號(hào)和列號(hào)，存入B中中pb位置；位置； 3.3 pb+；算法算法 壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置偽代碼偽代碼三、稀疏矩陣的轉(zhuǎn)置操作三、稀疏矩陣的轉(zhuǎn)置操作53Status TransPoseSMatrix ( TSMatrix M, TSMatrix &T)T.mu=M.nu; T.

43、nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for(col=1; col=M.nu; col+) for(p=1; p=M.tu; p+) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.value=M.datap.value; q+; return OK; /TranposeSMatrix;壓縮轉(zhuǎn)置算法描述壓縮轉(zhuǎn)置算法描述：（見(jiàn)教材（見(jiàn)教材P99）/用三元組表存放稀疏矩陣用三元組表存放稀疏矩陣M M，求，求M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T/q是轉(zhuǎn)置矩陣是轉(zhuǎn)置矩陣T T的結(jié)點(diǎn)編號(hào)的結(jié)點(diǎn)編

44、號(hào)/col是掃描是掃描M三元表列序的變量三元表列序的變量/p是是M三元表中結(jié)點(diǎn)編號(hào)三元表中結(jié)點(diǎn)編號(hào)541、主要時(shí)間消耗主要時(shí)間消耗在查找在查找M.datap.j=col的元素的元素，由兩重循環(huán)，由兩重循環(huán)完成完成: : for(col=1; col=M.nu; col+) 循環(huán)次數(shù)循環(huán)次數(shù)nu for(p=1; p=M.tu; p+) 循環(huán)次數(shù)循環(huán)次數(shù)tu所以該算法的時(shí)間復(fù)雜度為所以該算法的時(shí)間復(fù)雜度為O(O(nu*tu) ) - -即即M的列數(shù)與的列數(shù)與M中非零元素的個(gè)數(shù)中非零元素的個(gè)數(shù)之積之積最?lèi)毫忧闆r：最?lèi)毫忧闆r：M M中全是非零元素，此時(shí)中全是非零元素，此時(shí)tu=mu*nu， 時(shí)間復(fù)雜

45、度為時(shí)間復(fù)雜度為 O(O(nu2*mu ) )注：注：若若M M中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過(guò)是的時(shí)間復(fù)雜度也不過(guò)是O(O(nu*mu) ) （程序見(jiàn)（程序見(jiàn)教材教材P99P99）結(jié)論：結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。壓縮轉(zhuǎn)置算法不能濫用。前提：前提：僅適用于非零元素個(gè)數(shù)很少（即僅適用于非零元素個(gè)數(shù)很少（即tumu*nu）的情況。）的情況。壓縮轉(zhuǎn)置算法的效率分析壓縮轉(zhuǎn)置算法的效率分析：55分析：分析：A中第中第0列的第一個(gè)非零元素一定存儲(chǔ)在列的第一個(gè)非零元素一定存儲(chǔ)在B中下中下標(biāo)為標(biāo)為0的位置上，該列中其它非零元素應(yīng)存

46、放在的位置上，該列中其它非零元素應(yīng)存放在B中中后面連續(xù)的位置上，那么第后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在列的第一個(gè)非零元素在B中的位置便等于第中的位置便等于第0列的第一個(gè)非零元素在列的第一個(gè)非零元素在B中的位中的位置加上第置加上第0列的非零元素的個(gè)數(shù)，以此類(lèi)推。列的非零元素的個(gè)數(shù)，以此類(lèi)推。 基本思想：基本思想：順序取，直接存。順序取，直接存。即即在在A中依次取三元中依次取三元組，交換其行號(hào)和列號(hào)放到組，交換其行號(hào)和列號(hào)放到B 中中適當(dāng)適當(dāng)位置。位置。算法算法 快速轉(zhuǎn)置快速轉(zhuǎn)置如何確定當(dāng)前從如何確定當(dāng)前從A中取出的三元組在中取出的三元組在B中的位置？中的位置？三、稀疏矩陣的轉(zhuǎn)置操作

47、三、稀疏矩陣的轉(zhuǎn)置操作56方法方法2 2 快速轉(zhuǎn)置快速轉(zhuǎn)置三三元元組組表表a.data三三元元組組表表b.data(1, 3, -3)(2 ,1,12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路：依次思路：依次把把a(bǔ).data中的元素直接送入中的元素直接送入b.data的恰當(dāng)位置的恰當(dāng)位置上（上（即即M M三元組的三元組的p p指針不回溯指針不回溯）。）。關(guān)

48、鍵：關(guān)鍵：怎樣尋找怎樣尋找b.data的的“恰當(dāng)恰當(dāng)”位置？位置？ p1234 q 3 557引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：numnu：存儲(chǔ)矩陣存儲(chǔ)矩陣A中某列的非零元素的個(gè)數(shù)；中某列的非零元素的個(gè)數(shù)；cpotnu：初值表示矩陣初值表示矩陣A中某列的第一個(gè)非零元素中某列的第一個(gè)非零元素在在B中的位置。中的位置。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：cpot0=0；cpotcol=cpotcol- -1+numcol- -1； 1colnunum與與cpot存在如下遞推關(guān)系：存在如下遞推關(guān)系：算法算法 快速轉(zhuǎn)置快速轉(zhuǎn)置三、稀疏矩陣的轉(zhuǎn)置操作三、稀疏矩陣的轉(zhuǎn)置操作58如果能如

49、果能預(yù)知預(yù)知M矩陣矩陣每一列每一列( (即即T的每一行的每一行) )的的非零元素個(gè)數(shù)非零元素個(gè)數(shù)，又，又能預(yù)知能預(yù)知第一個(gè)非零元素第一個(gè)非零元素在在b.datab.data中的中的位置位置, ,則掃描則掃描a.data時(shí)便時(shí)便可以將每個(gè)元素準(zhǔn)確定位（可以將每個(gè)元素準(zhǔn)確定位（因?yàn)橐阎舾蓞⒖键c(diǎn)因?yàn)橐阎舾蓞⒖键c(diǎn)）。）。技巧：技巧：利用利用帶輔助向量帶輔助向量的三元組表，它正好攜帶每行（或列）的三元組表，它正好攜帶每行（或列）的非零元素個(gè)數(shù)的非零元素個(gè)數(shù) NUM(i)以及每行（或列）的第一個(gè)非以及每行（或列）的第一個(gè)非零元素在三元組表中的位置零元素在三元組表中的位置POS(i) 等信息。等信息。設(shè)

50、計(jì)思路：設(shè)計(jì)思路：i123456NUM(i)202112POS( i )133567不過(guò)我們需要的是不過(guò)我們需要的是按列生成的按列生成的M矩陣的輔助向量。矩陣的輔助向量。規(guī)律：規(guī)律：POS(1)1POS(i)POS(i-1)+NUM(i-1)請(qǐng)回憶：請(qǐng)回憶：請(qǐng)注意請(qǐng)注意a.data特征：每列首個(gè)非零元素必定先被掃描到。特征：每列首個(gè)非零元素必定先被掃描到。59令：令：M中的列變量用中的列變量用col表示；表示； num col ：存放存放M中第中第col 列中非列中非0 0元素個(gè)數(shù)，元素個(gè)數(shù)， cpot col ：存放存放M中第中第col列的第一個(gè)非列的第一個(gè)非0 0元素的位置，元素的位置，

51、（即即b.data中待計(jì)算的中待計(jì)算的“恰當(dāng)恰當(dāng)”位置所需參考點(diǎn)位置所需參考點(diǎn)）討論：討論：按列優(yōu)先的輔助向量求出后，按列優(yōu)先的輔助向量求出后，下一步該如何操作？下一步該如何操作？由由a.dataa.data中每個(gè)元素的列信息，即可直接查出中每個(gè)元素的列信息，即可直接查出b.datab.data中的中的重要參考點(diǎn)之位置，進(jìn)而可確定當(dāng)前元素之位置！重要參考點(diǎn)之位置，進(jìn)而可確定當(dāng)前元素之位置！col123456numcol222110cpotcol1規(guī)律：規(guī)律： cpot(1)1 cpotcol cpotcol-1 + numcol-10 12 9 0 0 00 0 0 0 0 0-3 0 0 0

52、 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M 3 5 7 8 8col 1 2 3 4 5 6601. 設(shè)置轉(zhuǎn)置后矩陣設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2. 計(jì)算計(jì)算A中每一列的非零元素個(gè)數(shù)；中每一列的非零元素個(gè)數(shù)；3. 計(jì)算計(jì)算A中每一列的第一個(gè)非零元素在中每一列的第一個(gè)非零元素在B中的下標(biāo)；中的下標(biāo)；4. 依次取依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；中的每一個(gè)非零元素對(duì)應(yīng)的三元組； 4.1 確定該元素在確定該元素在B中的下標(biāo)中的下標(biāo)pb； 4.2 將該元素的行號(hào)列號(hào)交換后存入將該元素的行號(hào)列號(hào)交換后存入B

53、中中pb的位置；的位置； 4.3 預(yù)置該元素所在列的下一個(gè)元素的存放位置；預(yù)置該元素所在列的下一個(gè)元素的存放位置；算法算法 快速轉(zhuǎn)置快速轉(zhuǎn)置偽代碼偽代碼三、稀疏矩陣的轉(zhuǎn)置操作三、稀疏矩陣的轉(zhuǎn)置操作61Status FastTransposeSMatrix（TSMatirx M, TSMatirx &T） T.mu = M.nu ;T .nu = M.mu ; T.tu = M.tu ; if ( T.tu ) for(col = 1; col =M.nu; col+) numcol =0; for( i = 1; i =M.tu; i +) col =M.data i .j ; +nu

54、m col ; cpos 1 =1; for(col = 2; col =M.nu; col+) cposcol =cposcol-1+num col-1 ; for( p =1; p =M.tu ; p + ) col =M.data p . j ; q =cpos col ; T.dataq.i = M.datap. j; T.dataq.j = M.datap. i; T.dataq. value = M.datap. value; /for /ifreturn OK; /FastTranposeSMatrix;快速轉(zhuǎn)置算法描述快速轉(zhuǎn)置算法描述：/M用順序存儲(chǔ)表示，求用順序存儲(chǔ)表示，求M

55、的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T/初始化初始化M中各列元素個(gè)數(shù)為中各列元素個(gè)數(shù)為0/再生成每列首元位置輔助向量表再生成每列首元位置輔助向量表/p指向指向a.data，循環(huán)次數(shù)為非，循環(huán)次數(shù)為非0元素總個(gè)數(shù)元素總個(gè)數(shù)tu/查輔助向量表得查輔助向量表得q，即，即T中位置中位置/重要語(yǔ)句！重要語(yǔ)句！修改向量表中列坐標(biāo)值，供修改向量表中列坐標(biāo)值，供同同一列一列下一非零元素定位之用！下一非零元素定位之用！621. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開(kāi)了與常規(guī)算法相比，附加了生成輔助向量表的工作。增開(kāi)了2個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組( (num 和和cpos ）。 傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：O( mu

56、*nu) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：O ( mu*tu) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：O( nu+tu)犧牲空間效率換時(shí)間效率犧牲空間效率換時(shí)間效率?？焖俎D(zhuǎn)置算法的效率分析快速轉(zhuǎn)置算法的效率分析：2. 從時(shí)間上，此算法用了從時(shí)間上，此算法用了4個(gè)并列的單循環(huán)個(gè)并列的單循環(huán)，而且其中前，而且其中前3個(gè)單個(gè)單循環(huán)都是用來(lái)產(chǎn)生輔助向量表的。循環(huán)都是用來(lái)產(chǎn)生輔助向量表的。 for(col = 1; col =M.nu; col+) 循環(huán)次數(shù)循環(huán)次數(shù)nu;nu; for( i = 1; i =M.tu; i +) 循環(huán)次數(shù)循環(huán)次數(shù)tu;tu; for(col = 2; col =M.nu; col+) 循環(huán)次

57、數(shù)循環(huán)次數(shù)nu;nu; for( p =1; p =M.tu ; p + ) 循環(huán)次數(shù)循環(huán)次數(shù)tu;tu; 該算法的時(shí)間復(fù)雜度該算法的時(shí)間復(fù)雜度(nu*2)+(tu*2)=O (nu+tu）討論：討論：最?lèi)毫忧闆r是最?lèi)毫忧闆r是tu=nu*mu( (即矩陣中全部是非零元素），即矩陣中全部是非零元素），而此時(shí)的時(shí)間復(fù)雜度也只是而此時(shí)的時(shí)間復(fù)雜度也只是O(mu*nu)，并未超過(guò)傳統(tǒng)轉(zhuǎn)置算法，并未超過(guò)傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。的時(shí)間復(fù)雜度。小結(jié)：小結(jié)：稀疏矩陣相乘的算法見(jiàn)教材稀疏矩陣相乘的算法見(jiàn)教材P101-103635.4 廣義表的定義廣義表的定義廣義表是線(xiàn)性表的推廣，也稱(chēng)為列表（廣義表是線(xiàn)性表的推廣，也稱(chēng)為列表（lists）記為：記為： LS = ( a1 , a2 , ， an ) 廣義表名廣義表名1. 定義：定義： 第一個(gè)元素是表頭，而其余元素第一個(gè)元素是表頭，而其余元素組成的表組成的表稱(chēng)為表尾；稱(chēng)為表尾； 用用小寫(xiě)小寫(xiě)字母表示字母表示原子類(lèi)型原子類(lèi)型，用，用大寫(xiě)大寫(xiě)字母表示字母表示列表列表。n是表長(zhǎng)是表長(zhǎng)在廣義表中約定：在廣義表中約定：討論：討論：廣義表與線(xiàn)性表的區(qū)別和聯(lián)系？廣義表與線(xiàn)性表的區(qū)別和聯(lián)系？ 廣義表中元素廣義表中元素既可以既可以是原子類(lèi)型，是原子類(lèi)型，也可以也可以是列表；是列表；當(dāng)每個(gè)元素都為原子且類(lèi)型相同時(shí)，就是線(xiàn)性表。當(dāng)每個(gè)元素都為原子