ch5- 數(shù)組和廣義表(全)

1、1 元素的值并非原子類型，可以再分解，表中元素也是一元素的值并非原子類型，可以再分解，表中元素也是一個線性表（即廣義的線性表）。個線性表（即廣義的線性表）。 所有數(shù)據(jù)元素仍屬所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型同一數(shù)據(jù)類型。5.1 數(shù)組的定義數(shù)組的定義5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)5.3 矩陣的壓縮存儲矩陣的壓縮存儲5.4 廣義表的定義廣義表的定義5.5 廣義表的存儲結構廣義表的存儲結構數(shù)組和廣義表的特點：數(shù)組和廣義表的特點：一種特殊的線性表一種特殊的線性表2數(shù)組：數(shù)組： 由一組名字相同、下標不同的變量構成由一組名字相同、下標不同的變量構成注意：注意： 本章所討論的數(shù)組與高級語言中的

2、數(shù)組有所區(qū)別：高本章所討論的數(shù)組與高級語言中的數(shù)組有所區(qū)別：高級語言中的數(shù)組是順序結構；而級語言中的數(shù)組是順序結構；而本章的數(shù)組既可以是順序的，本章的數(shù)組既可以是順序的，也可以是鏈式結構也可以是鏈式結構，用戶可根據(jù)需要選擇。，用戶可根據(jù)需要選擇。答：答：對的對的。因為：。因為： 數(shù)組中各元素具有數(shù)組中各元素具有統(tǒng)一的類型統(tǒng)一的類型； 數(shù)組元素的下標一般具有數(shù)組元素的下標一般具有固定的上界和下界固定的上界和下界，即數(shù)組一，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的數(shù)組的基本操作比較簡單基本操作比較簡單，除了結構的初始化和銷毀之，除了結構的初始化和銷毀之

3、外，只有存取元素和修改元素值的操作。外，只有存取元素和修改元素值的操作。討論：討論：“數(shù)組的處理比其它復雜的結構要簡單數(shù)組的處理比其它復雜的結構要簡單”，對嗎？，對嗎？3一維數(shù)組的特點：一維數(shù)組的特點：1 1個下標，個下標，a ai i 是是a ai+1i+1的直接前驅的直接前驅2 2個下標，個下標，每個元素每個元素ai,j受到兩個關系受到兩個關系（行關系和列關系）的約束：（行關系和列關系）的約束：一個一個mn的二維數(shù)組可以的二維數(shù)組可以看成是看成是m行的一維數(shù)組，或行的一維數(shù)組，或者者n列的一維數(shù)組。列的一維數(shù)組。N N維數(shù)組的特點：維數(shù)組的特點：n n個下標，個下標，每個元素受到每個元素受

4、到n n個關系約束個關系約束一個一個n維數(shù)組可以看成是維數(shù)組可以看成是由若干個由若干個n1維數(shù)組組成的線性表。維數(shù)組組成的線性表。 a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=4n_ARRAY = (D, R)其中： Ri = | aj1,j2,jijn , aj1,j2,ji+1jn D , 數(shù)據(jù)關系：數(shù)據(jù)關系：R = R1 ,R2，. Rn 數(shù)據(jù)對象：數(shù)據(jù)對象：D = aj1,j2jn| ji為數(shù)組元素的第為數(shù)組元素的第i 維下標維下標 ，aj1,j2jn Elemset數(shù)組的抽象數(shù)據(jù)類型定義數(shù)組的抽象數(shù)據(jù)類型定義略略，參見教材參見教材P90P90構造數(shù)

5、組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素構造數(shù)組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素基本操作：基本操作：5問題：問題：計算機的存儲結構是一維的，而數(shù)組一般是多維的，計算機的存儲結構是一維的，而數(shù)組一般是多維的，怎樣存放？怎樣存放？解決辦法：解決辦法：事先約定按某種次序將數(shù)組元素排成一列序列，事先約定按某種次序將數(shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。然后將這個線性序列存入存儲器中。例如：例如：在二維數(shù)組中，我們既可以規(guī)定按在二維數(shù)組中，我們既可以規(guī)定按行行存儲，也可以存儲，也可以規(guī)定按規(guī)定按列列存儲存儲。注意：注意： 若規(guī)定好了次序，則數(shù)組中任意一個元素的存放地址便若規(guī)定好了次序，則數(shù)

6、組中任意一個元素的存放地址便有規(guī)律可尋，可形成地址計算公式；有規(guī)律可尋，可形成地址計算公式； 約定的次序不同，則計算元素地址的公式也有所不同；約定的次序不同，則計算元素地址的公式也有所不同； C C和和PASCALPASCAL中一般采用行優(yōu)先順序；中一般采用行優(yōu)先順序；FORTRANFORTRAN采用列優(yōu)先。采用列優(yōu)先。6無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時求出任無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時求出任一元素的地址（一元素的地址（這樣數(shù)組中的任一元素便可以隨機存取！這樣數(shù)組中的任一元素便可以隨機存取?。憾S數(shù)組二維數(shù)組列優(yōu)先列優(yōu)先存儲的通式為：存儲的通式為：LO

7、C(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=單個元素單個元素長度長度aij之前的之前的行數(shù)行數(shù)數(shù)組基址數(shù)組基址總列數(shù)，即總列數(shù)，即第第2 2維長度維長度aij本行前面的本行前面的元素個數(shù)元素個數(shù)開始結點的存放地址（即基地址）開始結點的存放地址（即基地址）維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個數(shù)組元素所占用的單元數(shù)每個數(shù)組元素所占用的單元數(shù)則則行優(yōu)先行優(yōu)先存儲時的地址公式為：存儲時的地址公式為：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j

8、-c2)*L7例1軟考題：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是 個字節(jié)。 288例3：00年計算機系考研題設數(shù)組a160, 170的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a32,58的存儲地址為 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：請注意審題！答：請注意審題！利用列優(yōu)先通式：答：答： Volume=m*n*

9、L=(6-1+1)*(7- 0 +1)*6=48*6=2888niii1jC其中其中Cn=L, Ci-1=biCi， 1in一個元一個元素長度素長度數(shù)組基址數(shù)組基址前面若干元素占用前面若干元素占用的地址字節(jié)總數(shù)的地址字節(jié)總數(shù)第第i i維長度維長度與所存元素個數(shù)有關的系與所存元素個數(shù)有關的系數(shù)，可用遞推法求出數(shù)，可用遞推法求出教材已給出教材已給出低維低維優(yōu)先的地址計算公式，優(yōu)先的地址計算公式，見見P93P93（5-25-2）式）式該式稱為該式稱為n n維數(shù)組的映像函數(shù)維數(shù)組的映像函數(shù)：9#define MAX_ARRAY_DIM 8 /假設最大維數(shù)為假設最大維數(shù)為8 typedef struct

10、 ELemType *base; /數(shù)組元素基址數(shù)組元素基址 int dim; /數(shù)組維數(shù)數(shù)組維數(shù) int *bound; /數(shù)組數(shù)組各維長度信息保存區(qū)各維長度信息保存區(qū)基址基址 int *constants; /數(shù)組數(shù)組映像函數(shù)常量映像函數(shù)常量的基址的基址 Array;即即Ci信息保存區(qū)信息保存區(qū)數(shù)組的基本操作函數(shù)說明（有數(shù)組的基本操作函數(shù)說明（有5個）個）（請閱讀教材（請閱讀教材P93-95P93-95）以銷毀數(shù)組函數(shù)為例以銷毀數(shù)組函數(shù)為例10Status InitArray(Array &A,int dim,) /若維數(shù)若維數(shù)dimdim和各維長度合法，則和各維長度合法，則并返回

11、并返回OKOK if(dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim * sizeof(int); if(!a.bounds) exit(OVERFLOW); /若各維長度合法，則存入若各維長度合法，則存入A.bounds,A.bounds,并求出并求出A A的元素總數(shù)的元素總數(shù)elemtotalelemtotal elemtotal=1; va_start(ap.dim); /ap/ap為為va_listva_list類型，是存放變長參數(shù)表信類型，是存放變長參數(shù)表信息的類型息的類型數(shù)組的基本操作函數(shù)說

12、明（數(shù)組的基本操作函數(shù)說明（5個）個） （見教材見教材P93-95P93-95）11 for(i=0;idim;+i) A.boundsi=va_arg(ap,int); if(A.boundsi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK; 12數(shù)組基址指針數(shù)組基址指針各維長度保各維長度保存區(qū)指針存區(qū)指針映像函數(shù)映像函數(shù)CiCi保存區(qū)指針保存區(qū)指針Status DestroyArray(Array &A) /銷毀數(shù)組銷毀數(shù)組A A if ( ! A . base ) return ERROR; free( A .

13、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; 13Status Locate(Array A,va_list ap,int &off) /若若apap指示的各下標值合法，則求出該元素在指示的各下標值合法，則求出該元素在A A中，相對地址中，相對地址offoff of

14、f=0; for(i=0;iA.dim;+i) ind=va_arg(ap,int); if(indA.boundsi) return OVERFLOW; off+=A.constantsi *ind; return OK; 14Status Value(Array A,ElemType &e,) /A/A是是n n維數(shù)組，維數(shù)組，e e為元素變量，隨后是為元素變量，隨后是n n個下標值，若個下標值，若各下標不超界，則各下標不超界，則e e賦值為所指定的賦值為所指定的A A的元素值，即將指的元素值，即將指定元素值讀到定元素值讀到e e變量中。變量中。 va_start(ap,e); i

15、f(result=Locate(A,ap,off)=0) return result; e=*(A.base+off); return OK; 15Status Assign(Array &A,ElemType e,) /A/A是是n n維數(shù)組，維數(shù)組，e e為元素變量，隨后是為元素變量，隨后是n n個下標值，個下標值，若各下標不超界，則若各下標不超界，則e e的值賦為所指定的的值賦為所指定的A A的元素值，的元素值， va_start(ap,e); if(result=Locate(A,ap,off)=0) return result; *(A.base+off)=e; return

16、 OK; 16行指針向量行指針向量a11a12a1nam1am2amn補充：補充：鏈式存儲方式：鏈式存儲方式：用用帶行指針向量的單鏈表帶行指針向量的單鏈表來表示。來表示。注：數(shù)組的運算參見下一節(jié)實例（稀疏矩陣的轉置）注：數(shù)組的運算參見下一節(jié)實例（稀疏矩陣的轉置）（難點是多維數(shù)組與一維數(shù)組的地址映射關系難點是多維數(shù)組與一維數(shù)組的地址映射關系）17討論：討論：1. 什么是壓縮存儲？什么是壓縮存儲？若多個數(shù)據(jù)元素的若多個數(shù)據(jù)元素的值都相同值都相同，則只分配一個元素值的存儲空間，則只分配一個元素值的存儲空間，且零元素不占存儲空間。且零元素不占存儲空間。2. 所有二維數(shù)組（矩陣）都能壓縮嗎？所有二維數(shù)組

17、（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。未必，要看矩陣是否具備以上壓縮條件。3. 什么樣的矩陣具備以上壓縮條件？什么樣的矩陣具備以上壓縮條件？ 一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。陣等。4. 什么叫什么叫稀疏矩陣？稀疏矩陣？矩陣中非零元素的個數(shù)較少（一般小于矩陣中非零元素的個數(shù)較少（一般小于5%5%）重點介紹稀疏矩陣的壓縮和相應的操作。重點介紹稀疏矩陣的壓縮和相應的操作。18問題：問題：如果只存儲如果只存儲稀疏矩陣中的非零元素，那這些元素的稀疏矩陣中的非零元素，那這些元素的位置信息位置信息該如何表示？

18、該如何表示？解決思路：解決思路：對每個非零元素對每個非零元素增開增開若干存儲單元，例如存放其所若干存儲單元，例如存放其所在的行號和列號，便可準確反映該元素所在位置。在的行號和列號，便可準確反映該元素所在位置。實現(xiàn)方法：實現(xiàn)方法：將每個非零元素用一個三元組將每個非零元素用一個三元組（i，j，aij）來表示，）來表示，則每個則每個稀疏矩陣可用一個稀疏矩陣可用一個三元組表三元組表來表示。來表示。二、稀疏矩陣的操作二、稀疏矩陣的操作19行下標行下標列下標列下標元素值元素值例例2 2：寫出右圖所示稀疏寫出右圖所示稀疏矩陣的壓縮存儲形式。矩陣的壓縮存儲形式。0 12 9 0 0 00 0 0 0 0 0

19、-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0( ( 1,2,12)( 1,2,12) ，(1,3,9)(1,3,9)， (3,1,-3)(3,1,-3)， (3,5,14)(3,5,14)， (4,3,24)(4,3,24)， (5,2,18) (5,2,18) ，(6,1,15)(6,1,15)， (6,4,-7)(6,4,-7) )法法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 020法法2 2：用

20、三元組矩陣表示：用三元組矩陣表示：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-3351443245218611564-7注意：注意：為更可靠描述，為更可靠描述，通常再加一行通常再加一行“總體總體”信息：即信息：即總行數(shù)、總總行數(shù)、總列數(shù)、非零元素總個列數(shù)、非零元素總個數(shù)數(shù)668ijvalue稀疏矩陣壓縮存儲的稀疏矩陣壓縮存儲的缺點缺點：將失去隨機存取功能將失去隨機存取功能 :-(2176531211202NUM( i)6543POS( i )21i0 12 9 0 0 0

21、0 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用途：用途：通過三元組通過三元組高效訪問稀疏矩陣高效訪問稀疏矩陣中中任一非零元素。任一非零元素。規(guī)律：規(guī)律：POS(1)1 POS(i)POS(i-1)+NUM(i-1)22用途：用途：方便稀疏矩陣的加減運算；方便稀疏矩陣的加減運算；方法：方法：每個非每個非0元素占用元素占用5個域。個域。right downvji同一列中下一非同一列中下一非零元素的指針零元素的指針同一行中下一非

22、同一行中下一非零元素的指針零元素的指針十字鏈表的特點：十字鏈表的特點：每行非零元素鏈接每行非零元素鏈接成帶表頭結點的循環(huán)鏈表；成帶表頭結點的循環(huán)鏈表；每列非零元素也鏈接每列非零元素也鏈接成帶表頭結點的循環(huán)鏈表。成帶表頭結點的循環(huán)鏈表。則每個非零元素既是行循環(huán)鏈表中的一個結點；又是列循環(huán)則每個非零元素既是行循環(huán)鏈表中的一個結點；又是列循環(huán)鏈表中的一個結點，即鏈表中的一個結點，即呈十字鏈狀。呈十字鏈狀。以剛才的以剛才的稀疏矩陣稀疏矩陣為例：為例：122100H1931182523 #define MAXSIZE 125000 #define MAXSIZE 125000 /設非零元素最大個數(shù)設非零

23、元素最大個數(shù)125000125000 typedef struct typedef struct int i; int i; /元素行號元素行號 int j; int j; /元素列號元素列號 ElemType e; ElemType e; /元素值元素值 TripleTriple; ; typedef structtypedef struct TripleTriple dataMAXSIZE+1; dataMAXSIZE+1; /三元組表，以行為主序存入一維向量三元組表，以行為主序存入一維向量 data data 中中 int mu; int mu; /矩陣總行數(shù)矩陣總行數(shù) int nu;

24、int nu; /矩陣總列數(shù)矩陣總列數(shù) int tu; int tu; /矩陣中非零元素總個數(shù)矩陣中非零元素總個數(shù) TsMatrixTsMatrix; ; 三元組表的順序存儲表示三元組表的順序存儲表示（見教材（見教材P98P98）：）：/一個結點的結構定義一個結點的結構定義/整個三元組表的定義整個三元組表的定義240 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 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

25、 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轉置后轉置后MT（以轉置運算為例）（以轉置運算為例）目的：目的：25答：答：肯定不正確！肯定不正確！除了：除了： （1 1）每個元素的行下標和列下標互換（即三元組）每個元素的行下標和列下標互換（即三元組中的中的i i和

26、和j j互換互換）；）；還應該：還應該：（2 2）T T的總行數(shù)的總行數(shù)mumu和總列數(shù)和總列數(shù)nunu與與M M值不同值不同（互換）；互換）； （3 3）重排重排三元組內元素順序三元組內元素順序，使轉置后的三元組，使轉置后的三元組也按行（或列）為主序有規(guī)律的排列。也按行（或列）為主序有規(guī)律的排列。上述（上述（1 1）和（）和（2 2）容易實現(xiàn)，難點在）容易實現(xiàn)，難點在（3 3）。 若采用三元組壓縮技術存儲稀疏矩陣，只要把每個若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的元素的行下標和列下標互換行下標和列下標互換，就完成了對該矩陣的轉置運，就完成了對該矩陣的轉置運算，這種說法正確嗎？算，這

27、種說法正確嗎？ 有兩種實現(xiàn)方法有兩種實現(xiàn)方法壓縮轉置壓縮轉置( (壓縮壓縮) )快速轉置快速轉置提問：提問：26思路：思路：反復掃描反復掃描a.dataa.data中的中的列序列序，從小到大依次進行轉置。，從小到大依次進行轉置。三三元元組組表表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

28、, -7)11 22col q1234 p123427Status 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; 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;壓縮轉

29、置算法描述壓縮轉置算法描述：（見教材（見教材P99）/用三元組表存放稀疏矩陣用三元組表存放稀疏矩陣M M，求，求M M的轉置矩陣的轉置矩陣T T/q q是轉置矩陣是轉置矩陣T T的結點編號的結點編號/colcol是掃描是掃描M M三元表列序的變量三元表列序的變量/p是是M M三元表中結點編號三元表中結點編號281 1、主要時間消耗在主要時間消耗在查找查找M.datap.j=colM.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所

30、以該算法的時間復雜度為所以該算法的時間復雜度為O(O(nunu* *tutu) ) - -即即M M的列數(shù)與的列數(shù)與M M中非零元素的個數(shù)之中非零元素的個數(shù)之積積最惡劣情況：最惡劣情況：M M中全是非零元素，此時中全是非零元素，此時tu=mutu=mu* *nunu， 時間復雜度為時間復雜度為 O(O(nunu2 2* *mumu ) )注：注：若若M M中基本上是非零元素時，即使用非壓縮傳統(tǒng)轉置算法中基本上是非零元素時，即使用非壓縮傳統(tǒng)轉置算法的時間復雜度也不過是的時間復雜度也不過是O(O(nunu* *mumu) ) （程序見（程序見教材教材P99P99）結論：結論：壓縮轉置算法不能濫用。

31、壓縮轉置算法不能濫用。前提：前提：僅適用于非零元素個數(shù)很少（即僅適用于非零元素個數(shù)很少（即tutumumu* *nunu）的情況。）的情況。壓縮轉置算法的效率分析壓縮轉置算法的效率分析：29三三元元組組表表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.data

32、a.data中的元素直接送入中的元素直接送入b.datab.data的恰當位的恰當位置上（置上（即即M M三元組的三元組的p p指針不回溯指針不回溯）。）。關鍵：關鍵：怎樣尋找怎樣尋找b.datab.data的的“恰當恰當”位置？位置？ p1234 q 3 530如果能如果能預知預知M矩陣矩陣每一列每一列( (即即T的每一行的每一行) )的的非零元素個數(shù)非零元素個數(shù)，又能預知又能預知第一個非零元素第一個非零元素在在b.datab.data中的中的位置位置, ,則掃描則掃描a.data時便可以將每個元素準確定位（時便可以將每個元素準確定位（因為已知若干參考點因為已知若干參考點）。）。技巧：技巧：

33、利用利用帶輔助向量帶輔助向量的三元組表，它正好攜帶每行（或列）的三元組表，它正好攜帶每行（或列）的非零元素個數(shù)的非零元素個數(shù) NUM(i)以及每行（或列）的第一個非以及每行（或列）的第一個非零元素在三元組表中的位置零元素在三元組表中的位置POS(i) 等信息。等信息。i123456NUM(i)202112POS( i )133567不過我們需要的是不過我們需要的是按列生成的按列生成的M矩陣的輔助向量。矩陣的輔助向量。規(guī)律：規(guī)律：POS(1)1POS(i)POS(i-1)+NUM(i-1)請回憶：請回憶：請注意請注意a.dataa.data特征：每列首個非零元素必定先被掃描到。特征：每列首個非零

34、元素必定先被掃描到。31討論：討論：按列優(yōu)先按列優(yōu)先的輔助向量求出后，的輔助向量求出后，下一步該如何操作？下一步該如何操作？由由a.dataa.data中每個元素的中每個元素的列列信息，即可直接查出信息，即可直接查出b.datab.data中的中的重要參考點之位置，進而可確定當前元素之位置！重要參考點之位置，進而可確定當前元素之位置！col123456numcol222110cpotcol1規(guī)律：規(guī)律： cpot(1)1cpotcol cpotcol-1 + numcol-10 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 0

35、15 0 0 -7 0 0M 3 5 7 8 8col 1 2 3 4 5 632Status 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 ; +num col ; cpos 1 =1; for(col = 2; col =M.nu; col+) cposcol =c

36、poscol-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;快速轉置算法描述快速轉置算法描述：/M/M用順序存儲表示，求用順序存儲表示，求M M的轉置矩陣的轉置矩陣T T/先統(tǒng)計每列非零元素個數(shù)先統(tǒng)計每列非零元素個數(shù)/再生成每列首元位置輔助向量表再生成每

37、列首元位置輔助向量表/p/p指向指向a.dataa.data，循環(huán)次數(shù)為非，循環(huán)次數(shù)為非0 0元素總個數(shù)元素總個數(shù)tutu/查輔助向量表得查輔助向量表得q q，即，即T T中位置中位置/重要語句！重要語句！修改向量表中列坐標值，供修改向量表中列坐標值，供同一列同一列下一非零元素定位之用！下一非零元素定位之用！331.1. 與常規(guī)算法相比，附加了與常規(guī)算法相比，附加了生成輔助向量表生成輔助向量表的工作。增開了的工作。增開了2 2個長度為列長的數(shù)組個長度為列長的數(shù)組( (num 和和cpos ）。 傳統(tǒng)轉置：傳統(tǒng)轉置：O(O(mumu* *nunu) ) 壓縮轉置：壓縮轉置：O(O(mumu* *

38、tutu) ) 壓縮快速轉置：壓縮快速轉置：O(O(nu+nu+tutu)犧牲空間效率換時間效率。犧牲空間效率換時間效率。快速轉置算法的效率分析快速轉置算法的效率分析：2.2. 從時間上，此算法用了從時間上，此算法用了4 4個并列的單循環(huán)，而且其中前個并列的單循環(huán)，而且其中前3 3個個單循環(huán)都是用來產(chǎn)生輔助向量表的。單循環(huán)都是用來產(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ù)

39、nu;nu; for( p =1; p =M.tu ; p + ) 循環(huán)次數(shù)循環(huán)次數(shù)tu;tu; 該算法的時間復雜度該算法的時間復雜度(nu(nu* *2)+(tu2)+(tu* *2)=O(2)=O(nu+tunu+tu）討論：討論：最惡劣情況是最惡劣情況是tu=nutu=nu* *mumu( (即矩陣中全部是非零元素），即矩陣中全部是非零元素），而此時的時間復雜度也只是而此時的時間復雜度也只是O(O(mumu* *nunu) )，并未超過傳統(tǒng)轉置算，并未超過傳統(tǒng)轉置算法的時間復雜度。法的時間復雜度。小結：小結：稀疏矩陣相乘的算法見教材稀疏矩陣相乘的算法見教材P101-103P101-103

40、34三、三、 十字鏈表十字鏈表3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 3536廣義表是遞歸遞歸定義的線性結構線性結構， LS = ( 1, 2, , n )其中：i 或為原子 或為廣義表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )37廣義表廣義表 LS = ( 1, 2, , n )的結構特點的結構特點:1) 廣義表中的數(shù)據(jù)元素有相對次序次序;2) 廣義表的長度長度定義為最外層包含元素個數(shù);3) 廣義表的深度深度定義

41、為所含括弧的重數(shù); 注意:“原子”的深度為 0 ; “空表”的深度為 1 。4) 廣義表可以共享共享;5) 廣義表可以是一個遞歸遞歸的表; 遞歸表的深度是無窮值，長度是有限值。386) 任何一個非空廣義表非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭表頭 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 兩部分例如例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) )

42、= ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )39E=(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：求下列廣義表的長度。求下列廣義表的長度。n=0，因為因為A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 為原子，為原子，(b,

43、c,d)為子表為子表n=3，3個元素都是子表個元素都是子表n=2，a 為原子，為原子，E為子表為子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表40ABDCeabcd A=( a , (b, A) )例例2 2：試用圖形表示下列廣義表試用圖形表示下列廣義表. .（設（設 代表原子，代表原子， 代表子表）代表子表） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的長度為的長度為3，深度為，深度為3的長度為的長度為2，深度為，深度為深度括號的重數(shù)深度括號的重數(shù) 結點的層數(shù)結點的層數(shù)41廣義表是一個多層次多層次的線性結構線性結構例如：例如

44、：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce425.4 廣義表的類型定義廣義表的類型定義ADT Glist 數(shù)據(jù)對象數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個數(shù)據(jù)對象 數(shù)據(jù)關系：數(shù)據(jù)關系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作:43 結構的創(chuàng)建和銷毀結構的創(chuàng)建和銷毀 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L

45、);基本操作基本操作 狀態(tài)函數(shù)狀態(tài)函數(shù) GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和刪除操作插入和刪除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();44介紹兩種特殊的基本操作：介紹兩種特殊的基本操作：GetHead( L) 取表頭取表頭(可能是原子或列表可能是原子或列表);GetTail(L ) 取表尾取表尾(一定是列表一定是列表) 。廣義表的抽象數(shù)據(jù)類型定義見廣義表的抽象數(shù)據(jù)類型定義見教材教材P107-108P107-108451. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;例：例：求下列廣義表操作的結果（求下列廣義表操作的結果（嚴題集嚴題集5.10）(k, p, h)（b）(a,b)