數(shù)據(jù)結構數(shù)組廣義表學習教案

1、會計學1數(shù)據(jù)結構數(shù)據(jù)結構(sh j ji u)數(shù)組廣義表數(shù)組廣義表第一頁，共69頁。第第5 5章數(shù)組和廣義章數(shù)組和廣義(gungy)(gungy)表表 5.1 5.1 數(shù)組數(shù)組5.2 5.2 廣義廣義(gungy)(gungy)表表 教學內(nèi)容教學內(nèi)容Page 22022-4-19第1頁/共69頁第二頁，共69頁。5.1 數(shù)組數(shù)組Page 32022-4-19數(shù)據(jù)結構數(shù)據(jù)結構(sh j ji u)(sh j ji u)中的中的“數(shù)組數(shù)組”與高級語言與高級語言中的中的“數(shù)組數(shù)組”區(qū)別：區(qū)別：數(shù)據(jù)結構數(shù)據(jù)結構(sh j ji u)(sh j ji u)中的數(shù)組是一種線性結構中的數(shù)組是一種線性結構高級

2、語言中的數(shù)組是順序結構；高級語言中的數(shù)組是順序結構；第2頁/共69頁第三頁，共69頁。第3頁/共69頁第四頁，共69頁。Page 52022-4-19 多維數(shù)組多維數(shù)組 d(d3)維數(shù)組，看作一個由維數(shù)組，看作一個由d-1維數(shù)組作為數(shù)據(jù)元素的線維數(shù)組作為數(shù)據(jù)元素的線性表；性表； 數(shù)組是一種較復雜數(shù)組是一種較復雜(fz)的線性表結構，由簡單的數(shù)據(jù)結構的線性表結構，由簡單的數(shù)據(jù)結構即線性表輾轉合成而得。即線性表輾轉合成而得。三維數(shù)組 5.1.1 數(shù)組的定義數(shù)組的定義(dngy)第4頁/共69頁第五頁，共69頁。 5.1.1 數(shù)組的定義數(shù)組的定義(dngy)數(shù)組特點數(shù)組特點(tdin)數(shù)組結構固定數(shù)

3、組結構固定數(shù)據(jù)元素同構數(shù)據(jù)元素同構數(shù)組基本操作數(shù)組基本操作 (1) InitArray (&A,n,bound1, boundn) /構造構造(guzo)數(shù)組數(shù)組A (2) DestroyArray (&A) / 銷毀數(shù)組銷毀數(shù)組A (3) Value(A,&e,index1,indexn) /取數(shù)組元素值取數(shù)組元素值 (4) Assign (A,&e,index1,indexn) /給數(shù)組元素賦值給數(shù)組元素賦值第5頁/共69頁第六頁，共69頁。唯一的下標值對應；5.1.2數(shù)組的順序數(shù)組的順序(shnx)表示表示與實現(xiàn)與實現(xiàn) 已知以下三要素，求數(shù)組中任一元素的地

4、址： 開始結點的存放地址（即基地址） 維數(shù)和每維的上、下界(xi ji)； 每個數(shù)組元素所占用的單元數(shù)第6頁/共69頁第七頁，共69頁。a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 0 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(ai) =一維數(shù)組5.1.2 數(shù)組的順序表示數(shù)組的順序表示(biosh)與與實現(xiàn)實現(xiàn)LOC(a1)+（i-1）*l第7頁/共69頁第八頁，共69頁。以行序為主序以行序為主序C, PASCAL5.1.2 數(shù)組的順序表示數(shù)組的順序表示(biosh)與與實現(xiàn)實現(xiàn) 二維數(shù)組通常(tngchng)有兩種順序存儲方式： 以行序

5、為主序 以列序為主序第8頁/共69頁第九頁，共69頁。5.1.2 數(shù)組的順序數(shù)組的順序(shnx)表表示與實現(xiàn)示與實現(xiàn) a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)= 按行序為主序存放按行序為主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1nLoc(a11)+(i-1)n+(j-1)*L 第9頁/共69頁第十頁，共69頁。 以列序為主序FORTRAN 二維數(shù)組通常(tngchng)有兩種順序存儲方式： 以行序為主序 以列序為主序5.1.2 數(shù)組的順序表示數(shù)組的順序表示

6、(biosh)與實現(xiàn)與實現(xiàn)第10頁/共69頁第十一頁，共69頁。 按列序為主序存放按列序為主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=5.1.2 數(shù)組的順序表示數(shù)組的順序表示(biosh)與與實現(xiàn)實現(xiàn)Loc(a11)+(j-1)m+(i-1)*L第11頁/共69頁第十二頁，共69頁。111101121202111101101000nmamamanaaanaaanaaaa按列優(yōu)先按列優(yōu)先(yuxin) LOC ( i,

7、 j ) = a + ( j* m +i ) * l第12頁/共69頁第十三頁，共69頁。LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i1頁頁總總元素元素(yun s)個數(shù)個數(shù)第第i1頁頁的的前前i2行行總元素總元素(yun s)個數(shù)個數(shù)第13頁/共69頁第十四頁，共69頁。limianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 第14頁/共69頁第十五頁，共69頁。Page 162

8、022-4-19第15頁/共69頁第十六頁，共69頁。Page 172022-4-195.1.3矩陣矩陣(j zhn)的壓縮存的壓縮存儲儲第16頁/共69頁第十七頁，共69頁。1. 什么是壓縮存儲？什么是壓縮存儲？若多個數(shù)據(jù)元素的值都相同，則只分配一個元素值的存儲空若多個數(shù)據(jù)元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。間，且零元素不占存儲空間。2. 什么樣的矩陣能夠壓縮？什么樣的矩陣能夠壓縮？ 一些一些(yxi)特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。稀疏矩陣等。3. 什么叫稀疏矩陣？什么叫稀疏矩陣？矩陣中非零

9、元素的個數(shù)較少（一般小于矩陣中非零元素的個數(shù)較少（一般小于5%）5.1.3 矩陣矩陣(j zhn)的壓縮存的壓縮存儲儲第17頁/共69頁第十八頁，共69頁。5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲1. 對稱對稱(duchn)矩陣矩陣 a0,0 a0,1 . . A0,n-1 a1,0 a1,1 . . A1,n-1 an-1,0 an-1,1 . An-1,n-1 . ajiaij特點特點 在在nn的矩陣的矩陣a中，滿足如下性質(zhì)中，滿足如下性質(zhì)(xngzh)：aij=aji (1 i, j n)存儲方法存儲方法 只存儲下只存儲下(或者上或者上)三角三角(包括主對角線包括主對角線)的

10、數(shù)據(jù)元素。共占的數(shù)據(jù)元素。共占用用n(n+1)/2個元素空間。個元素空間。第18頁/共69頁第十九頁，共69頁。5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲1. 對稱對稱(duchn)矩陣矩陣 jiijjjijiik,2/)1(，2/)1(a0,0 a1,0 a1,1 a2,0 a2,1 aij an-1,n-1 . 0 1 2 3 4 k n(n+1)/2-1 按行序為主序：按行序為主序：ajiaijb a0,0 a0,1 . . A0,n-1 a1,0 a1,1 . . A1,n-1 an-1,0 an-1,1 . An-1,n-1 . 第19頁/共69頁第二十頁，共69頁。Pag

11、e 212022-4-191. 對稱對稱(duchn)矩陣矩陣 對稱對稱(duchn)矩陣矩陣 typedef int Elemtype;typedef struct sp_Matrix Elemtype *data;sp_Matrix;定義一個(y )壓縮矩陣結構void InitMatrix(sp_Matrix *M） M-data=(Elemtype *)malloc(sizeof(Elemtype)*(N*(N+1/2);初始化對稱矩陣的壓縮矩陣第20頁/共69頁第二十一頁，共69頁。Page 222022-4-191. 對稱對稱(duchn)矩陣矩陣 對稱對稱(duchn)矩陣矩陣

12、void AssignMatrix(sp_Matrix *M,Elemtype e,int i,int j) if(i=j) M-datai*(i+1)/2+j=e; else M-dataj*(j+1)/2+i=e;指定縮矩陣(j zhn)結構中的元素void PrintMatrix(sp_Matrix *M)/ int i,j; for(i=0;iN;i+) for(j=0;jj n(n+1)/2 ij5.1.3 矩陣矩陣(j zhn)的壓縮存的壓縮存儲儲 a0,0 0 0 . 0 a1,0 a1,1 0 . 0 an-1,0 an-1,1 an-1,2. an-1,n-1 . 0a0,0

13、 a1,0 a1,1 a1,2 a2,1 ai,j an-1,n-1 . 0 1 2 3 4 k n(n+1)/2-1 n(n+1)/2 按行序為主序：按行序為主序：0第23頁/共69頁第二十四頁，共69頁。 對角矩陣中，所有對角矩陣中，所有(suyu)(suyu)的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。 666556555445444334333223222112111001000000

14、00000000000000000000000000aaaaaaaaaaaaaaaaaaa 5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲第24頁/共69頁第二十五頁，共69頁。 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲術語(shy)b矩陣半帶寬：主對角線上下方各有b條次對角線；(2b+1)矩陣的帶寬。在一個nn的帶寬為三的對角矩陣中，只有n+n-1+n-1個非零元素，故只需3n-2個存儲單元即可，零元

15、已不占用存儲單元。 第25頁/共69頁第二十六頁，共69頁。5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲（a1,0 a2,1 a3,2 an-2,n-1）,有有j=i-1 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa （a0,0 a1,1 a2,2 an-1,n-1）,有有j=i（a0,1 a1,2 a2,3 an-2,n-1）,有有j=i+1第26頁/共69頁第二十七頁，共69頁。5.1.3 矩陣的壓縮矩陣的壓縮(y su)存儲存儲（a1,0 a2,1 a

16、3,2 an-2,n-1）,有有j=i-1（a0,0 a1,1 a2,2 an-1,n-1）,有有j=i（a0,1 a1,2 a2,3 an-2,n-1）,有有j=i+1用i、j確定(qudng)k前i行元素個數(shù)：2+3(i-1)=3i-1aij是本行第1個非零元素，k=3i-1 aij是本行第2個非零元素，k=3iaij是本行第3個非零元素，k=3i+1 =2i+j=2i+j=2i+j第27頁/共69頁第二十八頁，共69頁。Page 292022-4-191. 1. 數(shù)組數(shù)組A0.4,-1.-3,5.7A0.4,-1.-3,5.7中含有中含有(hn yu)(hn yu)元素的個數(shù)（元素的個數(shù)

17、（ ）。）。 A A55 B55 B45 C45 C36 D36 D16162.2.設二維數(shù)組設二維數(shù)組A1. mA1. m，1. n1. n（即（即m m行行n n列）按行存儲列）按行存儲(cn ch)(cn ch)在數(shù)組在數(shù)組B1. mB1. m* *nn中，則二維數(shù)組元素中，則二維數(shù)組元素Ai,jAi,j在一維數(shù)組在一維數(shù)組B B中的下標為（中的下標為（ ）。）。 A A(i-1)(i-1)* *n+j Bn+j B(i-1)(i-1)* *n+j-1 n+j-1 C Ci i* *(j-1) D(j-1) Dj j* *m+i-1 m+i-1 3.3.若對稱矩陣若對稱矩陣A1.n,1.

18、nA1.n,1.n以行序為主序方式將其下三角形的元素以行序為主序方式將其下三角形的元素( (包括主對角線上所有元素包括主對角線上所有元素) )依次依次(yc)(yc)存放于一維數(shù)組存放于一維數(shù)組B1.(n(n+1)/2B1.(n(n+1)/2中，則在中，則在B B中確定中確定aijaij（ijirow=M; Mt-col=N; Mt-num=0; /非零元素(yun s)個數(shù)先賦值為0 for(i=0;iM;i+) for(j=0;jdataMt-num.r=i; Mt-dataMt-num.c=j; Mt-dataMt-num.e=Aij; Mt-num+; 行行行行( (r ro ow w

19、) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8678 0000280000000091039000000006000017000110150022000第38頁/共69頁第三十九頁，共69頁。Page 402022-4-193）稀疏）稀疏(xsh)矩陣的基本操作矩陣的

20、基本操作bool Getvalue(SMatrix *Mt,ElemType *x,int i,int j); /獲取(huq)指定位置的元素值賦給變量x 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8678 int k=0; if(i

21、=Mt-row | j=Mt-col) /判斷位置是否(sh fu)合理 return false; while(knum & iMt-datak.r)k+; while(knum & jMt-datak.c) k+; if(i=Mt-datak.r & j=Mt-datak.c) / 找到了*x=Mt-datak.e; else *x=0; /沒找到，則為稀疏矩陣中的零值元素 return true;第39頁/共69頁第四十頁，共69頁。Page 412022-4-193）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作思考(sko)：為三元組元素賦值。 行行行行(

22、(r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5

23、2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5

24、 2 2 2 28 8情況一：為指定(zhdng)的非零元素重新賦值。例如：i=2，j=3，e=8情況二：指定的元素為零值元素例如：i=2，j=4，e=885 2 4 8678第40頁/共69頁第四十一頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N轉置轉置(zhun zh)第41頁/共69頁第四十二頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作row col

25、 valuerow col value0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187

26、 6 87 6 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8MN第42頁/共69頁第四十三頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作row col valuerow col value0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120

27、 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8轉置運算轉置運算(yn sun)算法一：按照算法一：按照M的列序來進行轉換的基本思想的列序來進行轉換的基本思想對對 M 從頭至尾掃描：從

28、頭至尾掃描：第一次掃描時，將第一次掃描時，將 M 中列號為中列號為0的所有元組交換行列值后，依次賦值到的所有元組交換行列值后，依次賦值到 N 中中。第二次掃描時，將第二次掃描時，將 N 中列號為中列號為1的所有元組交換行列值后，依次賦值到的所有元組交換行列值后，依次賦值到 N 中中。依此類推，直至將依此類推，直至將 M 的所有三元組賦值到的所有三元組賦值到 N 中。中。MN第43頁/共69頁第四十四頁，共69頁。i j vi j v0 1 120 1 120 2 90 2 92 0 -32 0 -32 5 142 5 143 2 243 2 244 1 184 1 185 0 155 0 15

29、5 3 -75 3 -7i j vi j v2 0 -32 0 -31 4 181 4 180 2 -30 2 -35 0 155 0 150 5 150 5 150 1 120 1 121 0 121 0 124 1 184 1 180 2 90 2 92 0 92 0 93 2 243 2 242 3 242 3 245 3 -75 3 -73 5 -73 5 -72 5 142 5 145 2 145 2 14M M矩陣矩陣(j (j zhn)zhn)N N矩陣矩陣(j (j zhn)zhn)對對M M七次掃描完成轉置七次掃描完成轉置(zhun zh)(zhun zh)運算運算第一次掃描

30、查找第第一次掃描查找第0 0列元素列元素第一次掃第一次掃描結束描結束第二次掃第二次掃描結束描結束第二次掃描查第二次掃描查找第找第1 1列元素列元素第三次掃描查找第第三次掃描查找第2 2列元素列元素第四次掃描查第四次掃描查找第找第3 3列元素列元素第五次掃描查找第五次掃描查找第第4 4列元素列元素第六次掃描查第六次掃描查找第找第5 5列元素列元素0 01 12 23 34 45 56 67 76 7 86 7 87 6 87 6 83）稀疏矩陣的基本操作）稀疏矩陣的基本操作第七次掃描查第七次掃描查找第找第6 6列元素列元素MN第44頁/共69頁第四十五頁，共69頁。Page 462022-4-1

31、93）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作void TransposeMatrix(SMatrix *Mt,SMatrix *T)/Mt轉置為T； int i,j,k=0; /k為轉置后T的下標標識值 T-row=Mt-col; T-col=Mt-row; T-num=Mt-num; for(i=0;icol;i+) /依次掃描(somio)Mt中的每一列 for(j=0;jnum;j+) /依次掃描(somio)每一個非零元素 if(Mt-dataj.c=i) T-datak.r=Mt-dataj.c; /將該元素行列互換放在T中 T-datak.c=Mt-dataj.r; T-

32、datak.e=Mt-dataj.e; k+; /*如果掃描的非零元素(yun s)的列值為當前列，則表示在當前列中找到了非零元素(yun s)*/設置轉置后的矩陣T的行、列、非零元素個數(shù)算法分析：算法分析：設矩陣三元組表總共有設矩陣三元組表總共有 Terms Terms 項，其時間代價為項，其時間代價為 OO ( ( ColsCols* * Terms Terms ) )。 T(n)=T(n)=O(O(M M的列數(shù)的列數(shù)n n 非零元個數(shù)非零元個數(shù)t)t)第45頁/共69頁第四十六頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作row col valuerow col va

33、lue0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8M中每一列(y

34、 li)非零元素個數(shù)c0：2c1：2c2：2c3：1C4：0c5：1c6：0MT第46頁/共69頁第四十七頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作第47頁/共69頁第四十八頁，共69頁。7600070015000001800000240001400003000000000009120Mcolnumcolcpotcol0212223140516002467783）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作第48頁/共69頁第四十九頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作void TransposeMatrix2(SMatrix *M,SM

35、atrix *T) T-row=Mt-col; T-col=Mt-row; T-num=Mt-num; /為兩個輔助向量(xingling)開辟空間 int *num=(int *)malloc(sizeof(int)* Mt-col) assert(num!=NULL); int * cpot=(int *)malloc(sizeof(int)*Mt-col); assert(cpot!=NULL); /開辟空間,存放M中每一列中非零元素的個數(shù)/開辟空間，用cpot存放M中每一列非零元素轉置后存放的起始位置第49頁/共69頁第五十頁，共69頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本

36、操作if(Mt-num!=0) for(int col=0;colcol;col+) /初始化num numcol=0; int t; for(t=0;tnum;t+) numMt-datat.c+; /計算每一列中第一個非零元素的起始位置 cpot0=0; /第0列第一個元素的起始位置為0 for(int col=1;colcol;col+) cpotcol=cpotcol-1+numcol-1; /依次從第1列開始(kish),當前列非零元素的起始位置/*查看查看(chkn)每個元素所在的列數(shù)每個元素所在的列數(shù),并并將對應的將對應的num個數(shù)個數(shù)+；*/第50頁/共69頁第五十一頁，共69

37、頁。3）稀疏）稀疏(xsh)矩陣的基本操作矩陣的基本操作int q=0;for(int p=0;pnum;p+) int col=Mt-datap.c; /依次獲取非零元素所在列 q=cpotcol; /再將第col列存放的首個位置賦值給q T-dataq.r=Mt-datap.c; T-dataq.c=Mt-datap.r; T-dataq.e=Mt-datap.e; /col列中已經(jīng)有元素占用了，所以要將位置向下移動(ydng)一個 cpotcol+; free(num); /釋放空間 free(cpot);/根據(jù)起始位置(wi zhi)，在T中放置M轉置后的非零元素第51頁/共69頁第五

38、十二頁，共69頁。Page 532022-4-19只保存(bocn)非零值為每一行設置一個(y )單獨鏈表，同時也為每一列設置一個(y )單獨鏈表。5.1.4 稀疏稀疏(xsh)矩陣矩陣4）稀疏矩陣的十字鏈表表示方法）稀疏矩陣的十字鏈表表示方法34008000450003A113418225234第52頁/共69頁第五十三頁，共69頁。 數(shù)據(jù)元素結點數(shù)據(jù)元素結點(ji din)定義：定義：typedef struct nodetypedef struct node int row,col,val; int row,col,val; struct node struct node * *down

39、, down, * *right;right;MatNode;MatNode;row col valdownright34008000450003A1134182252345.1.4 稀疏稀疏(xsh)矩陣矩陣4）稀疏矩陣的十字）稀疏矩陣的十字(sh z)鏈表表示方法鏈表表示方法第53頁/共69頁第五十四頁，共69頁。 補充：十字補充：十字(sh z)鏈表具體實現(xiàn)鏈表具體實現(xiàn)4）稀疏矩陣的十字）稀疏矩陣的十字(sh z)鏈表表示方法鏈表表示方法Mt=1 0 0 20 0 3 00 0 0 4第54頁/共69頁第五十五頁，共69頁。第第5 5章數(shù)組和廣義章數(shù)組和廣義(gungy)(gungy)表

40、表 5.1 5.1 數(shù)組數(shù)組5.2 5.2 廣義廣義(gungy)(gungy)表表 教學內(nèi)容教學內(nèi)容Page 562022-4-19第55頁/共69頁第五十六頁，共69頁。Page 572022-4-195.2廣義廣義(gungy)表表（1）定義(dngy) 廣義表是具有n個元素的有限序列.記為： GL=( a1,a2,an)注意: 一個廣義表通常用一對圓括號括起來，n是它的長度 ai可以是單個元素，也可以是廣義表，分別叫原子和子表,子表再用一對圓括號括起來. 用大寫字母表示廣義表的名稱,用小寫字母表示原子 廣義表非空時，第一個元素a1為LS的表頭(head)，其余(qy)元素組成的表(a2

41、,a3,an)時LS的表尾(tail)第56頁/共69頁第五十七頁，共69頁。(1)A=( ) (2)B=(a,（b,c） )(3) C=(x,y,z) (4) D=(B,C) (5) E=(a,E) 5.2 廣義廣義(gungy)表表A為空表，長度為空表，長度(chngd)為為0。B是長度為是長度為2的廣義表，第一項為原子，第二項為子表。的廣義表，第一項為原子，第二項為子表。C是長度為是長度為3的廣義表，每一項都是原子。的廣義表，每一項都是原子。D是長度為是長度為2的廣義表，每一項都是上面提到的子表。的廣義表，每一項都是上面提到的子表。是長度為是長度為2的廣義表，第一項為原子，第二項為它本身

42、。的廣義表，第一項為原子，第二項為它本身。(6)廣義表（廣義表（ ）、）、 ( ( ) )的長度分別為的長度分別為_ 、 _ 。 01第57頁/共69頁第五十八頁，共69頁。一個廣義表的深度是指該廣義表展開后所含括號一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。的層數(shù)。例如，例如，A=(b,c)的深度為的深度為1，B=(A,d)的深度為的深度為2，C=(f,B,h)的深度為的深度為3。示例示例(shl):設有廣義表設有廣義表D(a,b,D)，其長度為，其長度為_，深度為，深度為_。廣義表廣義表(a,(a,b),d,e,(i,j),k)的長度是的長度是_，深度是，深度是_。5.2 廣義廣義(

43、gungy)表表3無窮53第58頁/共69頁第五十九頁，共69頁。Page 602022-4-195.2 廣義廣義(gungy)表表A=()B=(e)C=(a,(b,c,d)D=(),(e),(a,(b,c,d)E=(a,(a,b),(a,b),c)第59頁/共69頁第六十頁，共69頁。若廣義表若廣義表LSLS（n=1)n=1)非空，則非空，則a1a1是是LSLS的表頭，其余的表頭，其余元素組成的表元素組成的表(a1,a2,an)(a1,a2,an)稱為稱為LSLS的表尾。的表尾。任何一個非空廣義表其表頭可能任何一個非空廣義表其表頭可能(knng)(knng)是原子表，是原子表，也可能也可能(

44、knng)(knng)是廣義表，而其表尾必定是廣義表。是廣義表，而其表尾必定是廣義表。廣義廣義(gungy)表表(a),a)的表頭是的表頭是 ，表尾是，表尾是 。 廣義廣義(gungy)表表(a,b),c,d)的表頭是的表頭是 ，表尾是，表尾是 。廣義廣義(gungy)表表(a,b,c,d)的表頭是的表頭是 ，表尾是，表尾是 。5.2 廣義表廣義表(a)(a)(a,b)(c,d)(b,c,d)a第60頁/共69頁第六十一頁，共69頁。設設HAEDpHAEDp為求廣義表為求廣義表p p的表頭函數(shù)，的表頭函數(shù)，TAILpTAILp為求為求廣義表廣義表p p的表尾函數(shù)，其中的表尾函數(shù)，其中是函數(shù)的符

45、號是函數(shù)的符號(fho)(fho)，給，給出下列廣義表的運算結果：出下列廣義表的運算結果：HEADHEAD（a a，b b，c c） 的結果是的結果是_ _ _ _ _。TAILTAIL（a,b,ca,b,c） 的結果是的結果是_ _ _。HEAD(a),(b)HEAD(a),(b)的結果是的結果是_ _ _。TAIL(a),(b)TAIL(a),(b)的結果是的結果是_。HEADTAIL(a,b,c)HEADTAIL(a,b,c)的結果是的結果是_ _ _TAILHEAD(a,b),(c,d)TAILHEAD(a,b),(c,d)的結果是的結果是_ _ _。HEADHEAD(a,b),(c,

46、d)HEADHEAD(a,b),(c,d)的結果是的結果是_ _ _。TAILTAIL(a,(c,d)TAILTAIL(a,(c,d)的結果是的結果是_ _ _。5.2 廣義廣義(gungy)表表第61頁/共69頁第六十二頁，共69頁。由于廣義表由于廣義表(a1,a2,a3,an)(a1,a2,a3,an)中的數(shù)據(jù)元素中的數(shù)據(jù)元素(yun s)(yun s)可以具有不同的結構，（或是原子，或是廣義表），因可以具有不同的結構，（或是原子，或是廣義表），因此，難以用順序存儲結構表示，通常采用鏈式存儲結構，此，難以用順序存儲結構表示，通常采用鏈式存儲結構，每個數(shù)據(jù)元素每個數(shù)據(jù)元素(yun s)(yun