數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組B

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第第5章章 數(shù)組和廣義表（數(shù)組和廣義表（Arrays & Lists）5.1 數(shù)組的定義數(shù)組的定義5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)5.4 廣義表的定義廣義表的定義5.5 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu) 元素的值并非原子類型，元素的值并非原子類型，可以再分解可以再分解，表中元素也是一個(gè)，表中元素也是一個(gè)線性表（即廣義的線性表）。線性表（即廣義的線性表）。 所有數(shù)據(jù)元素仍屬所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型同一數(shù)據(jù)類型。數(shù)組和廣義表的特點(diǎn)：數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表一種特殊的線性表3順序存儲(chǔ)方

2、式：順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。數(shù)組。（難點(diǎn)是：多維數(shù)組與一維數(shù)組的地址映射關(guān)系難點(diǎn)是：多維數(shù)組與一維數(shù)組的地址映射關(guān)系）例例1：已知二維數(shù)組已知二維數(shù)組Am,m按按行行存儲(chǔ)的元素地址公式是：存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 請(qǐng)問(wèn)按請(qǐng)問(wèn)按列列存儲(chǔ)的公式相同嗎？存儲(chǔ)的公式相同嗎？ 答：答：盡管是方陣，但公式仍不同，要作修改：盡管是方陣，但公式仍不同，要作修改： Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K例例2：00年計(jì)算機(jī)系考研題年計(jì)算機(jī)

3、系考研題設(shè)數(shù)組設(shè)數(shù)組a160, 170的基地的基地址為址為2048，每個(gè)元素占，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎮(zhèn)€存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素儲(chǔ)，則元素a32,58的存儲(chǔ)地址為的存儲(chǔ)地址為 。根據(jù)列優(yōu)先公式根據(jù)列優(yōu)先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：答：請(qǐng)注意審題！請(qǐng)注意審題！想一想：若數(shù)組是想一想：若數(shù)組是a059, 069，結(jié)果是否仍為結(jié)果是否仍為8950？4例例3：【?？瓶佳匈Y格考試專科考研資格考試】假設(shè)有假設(shè)有三維三維數(shù)組數(shù)組A798，

4、每個(gè)，每個(gè)元素用相鄰的元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起的起始存儲(chǔ)位置（基地址）為始存儲(chǔ)位置（基地址）為1000，末尾元素，末尾元素A687的第一個(gè)的第一個(gè)字節(jié)地址為多少？若按字節(jié)地址為多少？若按高地址優(yōu)先高地址優(yōu)先存儲(chǔ)時(shí)，元素存儲(chǔ)時(shí)，元素A476的的第一個(gè)字節(jié)地址為多少？第一個(gè)字節(jié)地址為多少？ 答：答： 末尾元素末尾元素A687的第的第1個(gè)字節(jié)地址個(gè)字節(jié)地址 1000 +(798)66=4018 按按高地址優(yōu)先高地址優(yōu)先存儲(chǔ)時(shí)，元素存儲(chǔ)時(shí)，元素A476的第的第1個(gè)字節(jié)地址個(gè)字節(jié)地址提示：提示：將第將第3維看作維看作“頁(yè)碼頁(yè)碼”，前面兩維就

5、是每頁(yè)上的二維數(shù)組，前面兩維就是每頁(yè)上的二維數(shù)組。（高維地址計(jì)算通式參見清華殷人昆教材的解釋高維地址計(jì)算通式參見清華殷人昆教材的解釋）35865行指針向量行指針向量a11a12a1nam1am2amn補(bǔ)充：數(shù)組的鏈?zhǔn)酱鎯?chǔ)方式補(bǔ)充：數(shù)組的鏈?zhǔn)酱鎯?chǔ)方式用用帶行指針向量的單鏈表帶行指針向量的單鏈表來(lái)表示。來(lái)表示。注：注：鏈?zhǔn)綌?shù)組的運(yùn)算請(qǐng)參見鏈?zhǔn)綌?shù)組的運(yùn)算請(qǐng)參見“稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置”注意：注意： 本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也

6、可以是的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。，用戶可根據(jù)需要選擇。65.3 5.3 矩陣的壓縮存儲(chǔ)討論：討論：1. 什么是壓縮存儲(chǔ)？什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的若多個(gè)數(shù)據(jù)元素的值都相同值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。且零元素不占存儲(chǔ)空間。2. 所有二維數(shù)組（矩陣）都能壓縮嗎？所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。未必，要看矩陣是否具備以上壓縮條件。3. 什么樣的矩陣具備以上壓縮條件？什么樣的矩陣具備以上壓縮條件？ 一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩一些特殊矩陣，如：對(duì)稱

7、矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。陣等。4. 什么叫什么叫稀疏矩陣？稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于矩陣中非零元素的個(gè)數(shù)較少（一般小于5%5%）重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。7一、一、稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)問(wèn)題：?jiǎn)栴}：如果只存儲(chǔ)如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的稀疏矩陣中的非零元素，那這些元素的位置信息位置信息該如何表示？該如何表示？解決思路：解決思路：對(duì)每個(gè)非零元素對(duì)每個(gè)非零元素增開增開若干存儲(chǔ)單元，用來(lái)存放其所若干存儲(chǔ)單元，用來(lái)存放其所在的在的行號(hào)行號(hào)和和列號(hào)列號(hào)，便可準(zhǔn)確反映該元素所在位置。，便可準(zhǔn)確反映該

8、元素所在位置。實(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)表示。二、二、稀疏矩陣的操作稀疏矩陣的操作8例例1 ： 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的元素的 、 和和 。 行下標(biāo)行下標(biāo)列下標(biāo)列下標(biāo)元素值元素值例例2 2：寫出右圖所示稀疏矩陣寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。的壓縮存儲(chǔ)形式。0 12 9 0 0 00 0 0 0

9、0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0解：解：至少有至少有4 4種存儲(chǔ)形式。種存儲(chǔ)形式。法法1 1：用線性表表示：用線性表表示：0 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 0 09法法2 2：用三元組矩陣表示：用三元組矩陣表示：0 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 0 0121213931-335144324521861156

10、4-7注意：注意：為更可靠描述，為更可靠描述，通常再加一行通常再加一行“總體總體”信息：即信息：即總行數(shù)、總總行數(shù)、總列數(shù)、非零元素總個(gè)列數(shù)、非零元素總個(gè)數(shù)數(shù)668ijvalue稀疏矩陣壓縮存儲(chǔ)的稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)缺點(diǎn)：將失去隨機(jī)將失去隨機(jī)存取功能存取功能 ！10法三：法三：用用帶輔助向量帶輔助向量的三元組表示。的三元組表示。 方法：方法： 增加增加2個(gè)輔助向量：個(gè)輔助向量： 記錄每行非記錄每行非0元素個(gè)數(shù)，用元素個(gè)數(shù)，用NUM（i）表示；表示； 記錄稀疏矩陣中每行第一個(gè)非記錄稀疏矩陣中每行第一個(gè)非0元素在元素在三三元組中的元組中的行號(hào)行號(hào)，用，用POS（i）表示。表示。765312112

11、02NUM( i)6543POS( i )21i0 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 0 0-7461516182524341453-3139311221866vji0123456783用途：用途：便于便于高效訪問(wèn)高效訪問(wèn)稀疏矩陣中稀疏矩陣中任一非任一非零元素零元素。POS(POS(i i) )如何計(jì)算？如何計(jì)算？POS(1)1POS(i)POS(i-1)+NUM(i-1)11法四：法四：用用十字鏈表十字鏈表表示表示用途：用途：方便稀疏矩陣的方便稀疏矩陣的加減加減運(yùn)算運(yùn)算方法：方法：每個(gè)非每

12、個(gè)非0元素占用元素占用5個(gè)域個(gè)域right downvji同一同一列列中下一非中下一非零元素的指針零元素的指針同一同一行行中下一非中下一非零元素的指針零元素的指針十字鏈表的特點(diǎn)：十字鏈表的特點(diǎn)：每行非零元素鏈接每行非零元素鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表；成帶表頭結(jié)點(diǎn)的循環(huán)鏈表；每列非零元素也鏈接每列非零元素也鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表。成帶表頭結(jié)點(diǎn)的循環(huán)鏈表。則每個(gè)非零元素既是行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)；又是列循環(huán)則每個(gè)非零元素既是行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)；又是列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，即鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。呈十字鏈狀。122100H1931182512typedef structtypede

13、f struct TripleTriple datadataMAXSIZE+1; MAXSIZE+1; /三元組表，以行為主序存入一三元組表，以行為主序存入一維向量維向量 data data 中中 int int mumu; ; /矩陣總行數(shù)矩陣總行數(shù) int int nunu; ; /矩陣總列數(shù)矩陣總列數(shù) int tu; int tu; /矩陣中非零元素總個(gè)數(shù)矩陣中非零元素總個(gè)數(shù) TsMatrixTsMatrix; ; 三元組表的順序存儲(chǔ)表示三元組表的順序存儲(chǔ)表示（見教材（見教材P98P98）對(duì)三元組表對(duì)三元組表的整體定義的整體定義 #define MAXSIZE 125000 #defin

14、e MAXSIZE 125000 /設(shè)非零元素最大個(gè)數(shù)設(shè)非零元素最大個(gè)數(shù)125000125000 typedef struct typedef struct int i; int i; /元素行號(hào)元素行號(hào) int j; int j; /元素列號(hào)元素列號(hào) ElemType e; ElemType e; /元素值元素值 TripleTriple; ; 對(duì)表中每對(duì)表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義13二、二、稀疏矩陣的操作稀疏矩陣的操作 0 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 0 00 0 3 0

15、 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)置運(yùn)算為例）（以轉(zhuǎn)置運(yùn)算為例）目的：目的：14答：答：肯定不正確！肯定不

16、正確！除了：除了： （1 1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的中的i i和和j j互換互換）；）；還需要：還需要：（2 2） T T的總行數(shù)的總行數(shù)mumu和總列數(shù)和總列數(shù)nunu也要也要互換；互換； （3 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ǔ)稀疏矩陣，只要把每個(gè)元素的元素的行下

17、標(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)置快速快速( (壓縮壓縮) )轉(zhuǎn)置轉(zhuǎn)置提問(wèn)：提問(wèn)：15方法方法1 1：壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置思路：思路：反復(fù)掃描反復(fù)掃描a a表表（記為（記為a.dataa.data）中的中的列序列序，從從j=1j=1n n依次進(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

18、, -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)11col q1234討論：每個(gè)元素的列分量怎樣書寫？討論：每個(gè)元素的列分量怎樣書寫？a.datap.j p123416Status TransPoseSMatrix(TSMatrix M, TSMatrix &T)T.mu=M.nu; T.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;

19、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)置算法描述：（見教材（見教材P99）/用三元組表存放稀疏矩陣用三元組表存放稀疏矩陣M M，求，求M M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T T/q q是轉(zhuǎn)置矩陣是轉(zhuǎn)置矩陣T T的結(jié)點(diǎn)編號(hào)的結(jié)點(diǎn)編號(hào)/colcol是掃描是掃描M M三元表列序的變量三元表列序的變量/p是是M M三元表中結(jié)點(diǎn)編號(hào)三元表中結(jié)點(diǎn)編號(hào)17三三元元組組表表a.data三

20、三元元組組表表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)(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)11col q1234 p12341 1、主要時(shí)間消耗在主要時(shí)間消耗在查找查找M.datap.j=colM.datap.j=col的元素的元素，由兩重循，由兩重循環(huán)完成環(huán)完成: : for(col=1; col=M.nu; col+) 循環(huán)次數(shù)列長(zhǎng)

21、度循環(huán)次數(shù)列長(zhǎng)度nu for(p=1; p=M.tu; p+) 循環(huán)次數(shù)非零元素個(gè)數(shù)循環(huán)次數(shù)非零元素個(gè)數(shù)tu壓縮轉(zhuǎn)置算法的效率分析壓縮轉(zhuǎn)置算法的效率分析：所以該算法的時(shí)間復(fù)雜度為所以該算法的時(shí)間復(fù)雜度為O(O(nunu* *tutu) ) - -即即M M的列數(shù)與的列數(shù)與M M中非零元素的個(gè)數(shù)之中非零元素的個(gè)數(shù)之積積最惡劣情況：最惡劣情況：M M中全是非零元素，此時(shí)非零元素總數(shù)中全是非零元素，此時(shí)非零元素總數(shù)tu=mutu=mu* *nunu， 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(O(nunu2 2* *mumu ) )注：注：若若M M中基本上是非零元素時(shí)，即使用傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)中基本上是非零

22、元素時(shí)，即使用傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過(guò)是雜度也不過(guò)是O(O(nunu* *mumu) ) （程序見教材（程序見教材P99P99）結(jié)論：結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。壓縮轉(zhuǎn)置算法不能濫用。前提：前提：僅適用于非零元素個(gè)數(shù)很少（即僅適用于非零元素個(gè)數(shù)很少（即tutumumu* *nunu）的情況。）的情況。18方法方法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 )(

23、3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路：思路：依次依次把把a(bǔ).dataa.data中的元素直接送入中的元素直接送入b.datab.data的恰當(dāng)位的恰當(dāng)位置上（置上（即即M M三元組的三元組的p p指針不回溯指針不回溯）。）。關(guān)鍵：關(guān)鍵：怎樣尋找怎樣尋找b.datab.data的的“恰當(dāng)恰當(dāng)”位置？位置？ p1234 q 3 519如果能如果能預(yù)知預(yù)知M矩陣矩陣每一列每一列( (即即T的每一行的每一行) )的的非零元素個(gè)數(shù)非零元素個(gè)數(shù)，又能預(yù)知又能預(yù)知第一個(gè)非零元素第一個(gè)非零元素在在b.datab.data中的

24、中的位置位置, ,則掃描則掃描a.data時(shí)便可以將每個(gè)元素準(zhǔn)確定位（時(shí)便可以將每個(gè)元素準(zhǔn)確定位（因?yàn)橐阎舾蓞⒖键c(diǎn)因?yàn)橐阎舾蓞⒖键c(diǎn)）。）。技巧：先生成技巧：先生成三元組表的三元組表的兩個(gè)輔助向量?jī)蓚€(gè)輔助向量，讓它攜帶每行（或，讓它攜帶每行（或列）的非零元素個(gè)數(shù)列）的非零元素個(gè)數(shù) NUM(i)以及每行（或列）的第一以及每行（或列）的第一個(gè)非零元素在三元組表中的位置個(gè)非零元素在三元組表中的位置POS(i) 等信息。等信息。設(shè)計(jì)思路：設(shè)計(jì)思路：i123456NUM(i)202112POS( i )133567注：為實(shí)現(xiàn)轉(zhuǎn)置運(yùn)算，應(yīng)當(dāng)注：為實(shí)現(xiàn)轉(zhuǎn)置運(yùn)算，應(yīng)當(dāng)按列按列生成生成 M 矩陣的輔助向量矩陣

25、的輔助向量計(jì)算式計(jì)算式：POS(1)1POS(i)POS(i-1)+NUM(i-1)輔助向量的樣式：輔助向量的樣式：請(qǐng)注意請(qǐng)注意a.dataa.data特征：每列首個(gè)非零元素必定先被掃描到。特征：每列首個(gè)非零元素必定先被掃描到。20令：令：M矩陣中的矩陣中的列列變量用變量用col表示；表示； num col ：存放存放M中第中第col 列中非列中非0 0元素個(gè)數(shù)元素個(gè)數(shù) cpot col ：存放存放M中第中第col列的第一個(gè)非列的第一個(gè)非0 0元素的位置元素的位置 （即（即b.datab.data中待計(jì)算的中待計(jì)算的“恰當(dāng)恰當(dāng)”位置所需參考點(diǎn)）位置所需參考點(diǎn)）討論：討論：求出求出按列優(yōu)先按列優(yōu)

26、先的的輔助向量輔助向量后，后，如何如何實(shí)現(xiàn)快速轉(zhuǎn)置？實(shí)現(xiàn)快速轉(zhuǎn)置？col123456numcol222110cpotcol1計(jì)算式：計(jì)算式： cpot(1)1cpotcol cpotcol-1 + numcol-1 3 5 7 8 90 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 0 0Mcol 1 2 3 4 5 6由由a a.data.data中每個(gè)元素的列信息，可以直接中每個(gè)元素的列信息，可以直接從輔助向量從輔助向量cpotcol中查出在中查出在b b.data.data中的中的“基準(zhǔn)基準(zhǔn)”位置，

27、進(jìn)而得到當(dāng)前元素之位置。位置，進(jìn)而得到當(dāng)前元素之位置。三三元元組組表表a.data(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)col p1234想一想：是從原始矩陣想一想：是從原始矩陣M M中統(tǒng)計(jì)中統(tǒng)計(jì)numcol方便些，方便些，還是從對(duì)應(yīng)的三元組表還是從對(duì)應(yīng)的三元組表a.dataa.data中統(tǒng)計(jì)更方便？中統(tǒng)計(jì)更方便？21Status FastTransposeSMatrix（TSMatirx M, TSMatirx &T） T.mu = M.nu ;T .nu = M

28、.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.datai .j ; +num 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 ; =cpos col ; T.dataq.i = M.datap. j; T.dataq.j = M.dat

29、ap. i; T.dataq. value = M.datap. value; /for /ifreturn OK; /FastTranposeSMatrix;快速轉(zhuǎn)置算法描述快速轉(zhuǎn)置算法描述：/M/M是順序存儲(chǔ)的三元組表，求是順序存儲(chǔ)的三元組表，求M M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T T/先統(tǒng)計(jì)每列非零元素個(gè)數(shù)先統(tǒng)計(jì)每列非零元素個(gè)數(shù)/再生成每列首元位置輔助向量再生成每列首元位置輔助向量/p/p指向指向a.dataa.data，循環(huán)次數(shù)為非，循環(huán)次數(shù)為非0 0元素總個(gè)數(shù)元素總個(gè)數(shù)tutu/查輔助向量得查輔助向量得 ，即，即T T中位置中位置前前3 3個(gè)個(gè)forfor循環(huán)循環(huán)用來(lái)產(chǎn)生兩個(gè)用來(lái)產(chǎn)生兩個(gè)輔助

30、向量輔助向量重要！修改向量?jī)?nèi)容（列坐標(biāo)加重要！修改向量?jī)?nèi)容（列坐標(biāo)加1 1），），預(yù)備給預(yù)備給同列同列的下一非零元素定位之用的下一非零元素定位之用元素轉(zhuǎn)置元素轉(zhuǎn)置221.1. 與常規(guī)算法相比，附加了與常規(guī)算法相比，附加了生成輔助向量表生成輔助向量表的工作。增開了的工作。增開了2 2個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組個(gè)長(zhǎng)度為列長(zhǎng)的數(shù)組( (num 和和cpos ）。傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：O(O(mumu* *nunu) ) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：O(O(mumu* *tutu) ) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：O(O(nu+nu+tutu) )快速轉(zhuǎn)置算法的效率分析快速轉(zhuǎn)置算法的效率分析：2.2. 從時(shí)間上，此算法

31、用了從時(shí)間上，此算法用了4 4個(gè)并列的單循環(huán)，而且其中前個(gè)并列的單循環(huán)，而且其中前3 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)次數(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+tu+nu+tu=O(nu+tu+nu

32、+tu=O(nu+tunu+tu）討論：討論：最惡劣情況是矩陣中全為非零元素，此時(shí)最惡劣情況是矩陣中全為非零元素，此時(shí)tu=nutu=nu* *mumu而此時(shí)的時(shí)間復(fù)雜度也只是而此時(shí)的時(shí)間復(fù)雜度也只是O(O(mumu* *nunu) )，并未超過(guò)傳統(tǒng)轉(zhuǎn)置算，并未超過(guò)傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。法的時(shí)間復(fù)雜度。小結(jié)：小結(jié)：稀疏矩陣相乘的算法略，稀疏矩陣相乘的算法略，見教材見教材P101-103P101-103增設(shè)輔助向量，犧牲空間增設(shè)輔助向量，犧牲空間效率換取時(shí)間效率。效率換取時(shí)間效率。235.4 5.4 廣義表的定義廣義表的定義廣義表是線性表的推廣，也稱為列表（廣義表是線性表的推廣，也稱為列表（

33、lists）記為：記為： LS = ( a1 , a2 , ， an ) 廣義表名廣義表名 表頭表頭(Head） 表尾表尾 (Tail)1、定義：、定義： 第一個(gè)第一個(gè)元素是表頭元素是表頭，而其余元素組成的，而其余元素組成的表稱為表尾表稱為表尾； 用小寫字母表示原子類型，用用小寫字母表示原子類型，用大寫字母大寫字母表示列表。表示列表。n n是表長(zhǎng)是表長(zhǎng)在廣義表中約定：在廣義表中約定：討論：討論：廣義表與線性表的區(qū)別和聯(lián)系？廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類型，也可以是列表；廣義表中元素既可以是原子類型，也可以是列表；當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。當(dāng)每個(gè)元素都

34、為原子且類型相同時(shí)，就是線性表。242、特點(diǎn)：、特點(diǎn)： 有次序性有次序性 有長(zhǎng)度有長(zhǎng)度 有深度有深度 可遞歸可遞歸 可共享可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼一個(gè)直接前驅(qū)和一個(gè)直接后繼表中元素個(gè)數(shù)表中元素個(gè)數(shù)表中括號(hào)的重?cái)?shù)表中括號(hào)的重?cái)?shù)自己可以作為自己的子表自己可以作為自己的子表可以為其他廣義表所共享可以為其他廣義表所共享特別提示：特別提示：任何一個(gè)非空表，表頭可能是原子，也可能任何一個(gè)非空表，表頭可能是原子，也可能是列表；但是列表；但表尾一定是列表表尾一定是列表。25E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為為遞歸表遞歸表1）A =( )2）B = ( e ) 3）C =(

35、 a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)例例1：求下列廣義表的長(zhǎng)度。求下列廣義表的長(zhǎng)度。n=0，因?yàn)橐驗(yàn)锳 A是空表是空表n=1，表中元素表中元素e e是原子是原子n=2，a a 為原子，為原子，(b,c,d)(b,c,d)為子表為子表n=3，3 3個(gè)元素都是子表個(gè)元素都是子表n=2，a a 為原子，為原子，E E為子表為子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表26ABDCeabcd A=( a , (b, A) )例例2 2：試用圖形表示下列廣義表試用圖形表示下列廣義表. .（設(shè)（設(shè) 代表子表，代表子表， 代表元素）代表元素） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的長(zhǎng)度為的長(zhǎng)度為3，深度為，深度為3的長(zhǎng)度為的長(zhǎng)度為2，深度為，深度為深度括號(hào)的重?cái)?shù)深度括