數據結構案例教程（CC++版）第2版 課件 第5章 元素擴展的線性表：矩陣和廣義表

第5章元素擴展的線性表：

矩陣和廣義表個性化推薦系統中的用戶評分表導學問題1矩陣的基本操作⑴存?。航o定一組下標，讀出對應的數組元素；⑵修改：給定一組下標，存儲或修改與其相對應的數組元素。存取和修改操作本質上只對應一種操作——尋址矩陣應該采用何種方式存儲？矩陣沒有插入和刪除操作，所以，不用預留空間，適合采用順序存儲。知識學習——矩陣的基本概念設一維數組的下標的范圍為閉區(qū)間［l，h］，每個數組元素占用c個存儲單元，則其任一元素ai的存儲地址可由下式確定：Loc(ai)＝Loc(al)＋(i－l)×c

calai-1ai……ahal+1……Loc(al)Loc(ai)知識學習——矩陣的存儲結構常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。

按列優(yōu)先：先列后行，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。

二維數組內存二維結構一維結構知識學習——矩陣的存儲結構l2h2

l1h1(a)二維數組aij前面的元素個數=陰影部分的面積=整行數×每行元素個數+本行中aij前面的元素個數=(i

-l1)×(h2

-l2＋1)＋(j

-l2)本行中aij前面的元素個數每行元素個數整行數aij按行優(yōu)先存儲的尋址知識學習——矩陣的存儲結構第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2＋1)＋(j

-l2)個元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按列優(yōu)先存儲的尋址方法與此類似。知識學習——矩陣的存儲結構按行優(yōu)先存儲的尋址知識學習——特殊矩陣的壓縮存儲特殊矩陣：包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣等。

稀疏矩陣：矩陣中有很多零元素。壓縮存儲的基本思想是：為多個值相同的元素只分配一個存儲空間；對零元素不分配存儲空間。3647862842481697460582957A＝對稱矩陣特點：aij=aji如何壓縮存儲？只存儲下三角部分的元素。特殊矩陣的壓縮存儲——對稱陣(a)下三角矩陣(b)存儲說明(c)計算方法aij在一維數組中的序號=陰影部分的面積=

i×(i-1)/2+j-1∵一維數組下標從0開始∴aij在一維數組中的下標k=i×(i-1)/2+j-1

1…

in-11

…j…n-1

aij每行元素個數12…iaij在本行中的序號aij第1行第2行…第i-1行特殊矩陣的壓縮存儲——對稱陣對于下三角中的元素aij（i≥j），在數組SA中的下標k與i、j的關系為：k＝i×(i-1)/2＋j-1。上三角中的元素aij（i＜j），因為aij＝aji，則訪問和它對應的元素aji即可，即：k＝j×(j-1)/2＋i-1

。第2行第n行第1行

a11

a21

a22

a31

a32

a33

aij…

a

n1

an2…ann…第3行012345kn(n+1)/2-1特殊矩陣的壓縮存儲——對稱陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣如何壓縮存儲？只存儲上三角（或下三角）部分的元素。特殊矩陣的壓縮存儲——三角陣矩陣中任一元素aij在數組中的下標k與i、j的對應關系：i×(i-1)/2＋j-1

當i≥jn×(n＋1)/2當i＜jk=012345

k

n(n+1)/2第2行第1行

a11

a21

a22

a31

a32

aij…ann…第3行

c

a33存儲下三角元素對角線上方的常數——只存一個特殊矩陣的壓縮存儲——三角陣矩陣中任一元素aij在數組中的下標k與i、j的對應關系：

(i-1)×(2n－i＋2)/2＋j－i

當i≤jn×(n＋1)/2當i＞jk=存儲上三角元素對角線上方的常數——只存一個特殊矩陣的壓縮存儲——三角陣按行存儲元素aij在一維數組中的序號=3(i－1)-1+(

j－i+1)=2i+j-3

∵一維數組下標從0開始∴元素aij在一維數組中的下標=2i+j-3(b)尋址的計算方法(c)壓縮到一維數組中a11a12a21a22a23a32a33a34a43a44a45a54a550123456789101112(a)三對角矩陣

0

00

000

000

000

A=a11a12a21a22

a23a32a33

a34a43a44

a45a54a55特殊矩陣的壓縮存儲——對角矩陣1500000

0110000

000600

0000009

00000A=如何只存儲非零元素？注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。特殊矩陣的壓縮存儲——稀疏矩陣typedefstruct{

inti,j;

ElemTypee;}Triple;將稀疏矩陣中的每個非零元素表示為：(行號，列號，非零元素值)——三元組定義三元組：稀疏矩陣的壓縮存儲——三元組順序表typedefstruct{

Tripledata[MAXSIZE];

intmu,nu,tu;}SparseMatrix;定義三元組順序表：三元組表：將稀疏矩陣的非零元素對應的三元組所構成的集合，按行優(yōu)先的順序排列成一個線性表。三元組表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))1500000

0110000

000600

0000009

00000A=如何存儲三元組表？稀疏矩陣的壓縮存儲——三元組順序表采用順序存儲結構存儲三元組表1500220-15

0113000

000600

00000091

00000A=三元組順序表是否需要預留存儲空間？稀疏矩陣的修改操作三元組順序表的插入/刪除操作稀疏矩陣的壓縮存儲——三元組順序表采用順序存儲結構存儲三元組表

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑

ije0123456MAXSIZE-11500220-15

0113000

000600

00000091

00000A=7（非零元個數）是否對應惟一的稀疏矩陣？5（矩陣的行數）6（矩陣的列數）稀疏矩陣的壓縮存儲——三元組順序表創(chuàng)建基于三元組順序表結構的稀疏矩陣:voidCreateMatrix(SparseMatrix&M){ cout<<"請輸入矩陣行數："; cin>>M.mu; cout<<"請輸入矩陣列數："; cin>>M.nu; cout<<"請輸入非零元素個數："; cin>>M.tu; cout<<"請輸入非零元素（輸入格式為：行號列號元素值）：\n"; for(intp=0;p<M.tu;p++) cin>>M.data[p].i>>M.data[p].j>>M.data[p].e;}稀疏矩陣的壓縮存儲——三元組順序表采用鏈接存儲結構存儲三元組表，每個非零元素對應的三元組存儲為一個鏈表結點，結構為：ijedownrighti：存儲非零元素的行號j：存儲非零元素的列號e：存儲非零元素的值right：指針域，指向同一行中的下一個三元組down：指針域，指向同一列中的下一個三元組稀疏矩陣的壓縮存儲——十字鏈表

312∧M=300501002000

113

145∧∧

221∧∧∧∧稀疏矩陣的壓縮存儲——十字鏈表按矩陣形式顯示基于三元組順序表結構的稀疏矩陣:voidShowMatrix(SparseMatrixM){ intk=0;//記錄遍歷到的非零元素個數 for(inti=1;i<=M.mu;i++) { for(intj=1;j<=M.nu;j++) { if(k==M.tu) k=0; if(i==M.data[k].i&&j==M.data[k].j&&k<M.tu) { cout<<M.data[k].e<<"\t"; k++; } else cout<<"0"<<"\t"; } cout<<endl; }}知識應用——導學問題1的實現例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=知識拓展——稀疏矩陣轉置

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

1

1

15

1

591

2211

323

4122

436

61-15

空空空閑閑閑0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）知識拓展——稀疏矩陣轉置

ije

ije知識拓展——稀疏矩陣轉置基本思想：在A的三元組順序表中依次找第1列、第2列、…直到最后一列的三元組，并將找到的每個三元組的行、列交換后順序存儲到B的三元組順序表中。

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）知識拓展——稀疏矩陣轉置

ije

ije0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）在矩陣A中查找第1列非零元，順序存儲到矩陣B中

1115

1591

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211在矩陣A中查找第2列非零元，順序存儲到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211

323在矩陣A中查找第3列非零元，順序存儲到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211

323

4122

436在矩陣A中查找第4列非零元，順序存儲到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211

323

436在矩陣A中查找第5列非零元，順序存儲到矩陣B中

4122

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2111

323

4122

436

61-15在矩陣A中查找第6列非零元，順序存儲到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211

323

4122

436

61-15在矩陣A中查找第7列非零元，順序存儲到矩陣B中

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑1.設置轉置后矩陣B的行數、列數和非零元個數；2.在B中設置初始存儲位置q；3.for(col=最小列號;col<=最大列號;col++)3.1在A中查找列號為col的三元組；3.2交換其行號和列號，存入B中q位置；3.3q++；三元組順序表操作——轉置算法1三元組順序表操作——轉置算法1該算法的主要時間耗費是在col和p的兩重循環(huán)上。對于一個m行n列且非零元素個數為t的稀疏矩陣而言，該算法的時間復雜度為O(tn)。最壞情況是，當稀疏矩陣中的非零元素個數t與mn同數量級時，上述算法的時間復雜度就為O(mn2)。顯然這種情況下，該樸素算法效率較低。分析：A中第0列的第一個非零元素一定存儲在B中下標為0的位置上，該列中其它非零元素應存放在B中后面連續(xù)的位置上，那么第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數，以此類推。基本思想：順序取，直接存。即在A中依次取三元組，交換其行號和列號放到B中適當位置。如何確定當前從A中取出的三元組在B中的位置？三元組順序表操作——轉置算法2

0123456MAXSIZE-16（矩陣的行數）5（矩陣的列數）7（非零元個數）

1115

1591

2211

323

4122

436

61-15第1列第1個非零元素第1列有2個非零元素第2列第2個非零元素三元組順序表操作——轉置算法2觀察轉置后矩陣的三元組順序表

ije引入兩個數組作為輔助數據結構：cnum[cols]：存儲矩陣A中某列的非零元素的個數；cpot[clos]：初值表示矩陣A中某列的第一個非零元素在B中的位置。數據結構設計：cpot[1]=0；cpot[col]=cpot[col-1]+cnum[col-1]；1<col<=cols-1cnum與cpot存在如下遞推關系：三元組順序表操作——轉置算法2

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑ije0123456MAXSIZE-15（矩陣的行數）6（矩陣的列數）7（非零元個數）

col123456cnum[col]21

12

01cpot[col]

023466根據矩陣A計算cnum和cpot

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]

1115cpot[1]

ije

ije01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]

1115cpot[1]

4122cpot[4]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[2]cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]cpot[6]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[2]cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211cpot[2]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[3]cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211cpot[2]

323cpot[3]cpot[2]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[5]

1115cpot[1]

4122cpot[4]

61-15cpot[6]

2211

323cpot[3]cpot[2]

436cpot[4]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑01234565（矩陣的行數）6（矩陣的列數）7（非零元個數）將矩陣A中col列元素存放在B中下標為cpot[col]的位置

01234566（矩陣的行數）5（矩陣的列數）7（非零元個數）cpot[5]

1115cpot[1]

4122

61-15cpot[6]

2211

323cpot[3]cpot[2]

436cpot[4]

1591cpot[1]

ije

ije

1

1

15

1

4

22

1

6

-15

2

2

11

2

3

3

3

4

6

5

1

91

空空空閑閑閑1.設置轉置后矩陣B的行數、列數和非零元素的個數；2.計算A中每一列的非零元素個數；3.計算A中每一列的第一個非零元素在B中的下標；4.依次取A中的每一個非零元素對應的三元組；4.1確定該元素在B中的下標q；4.2將該元素的行號列號交換后存入B中q的位置；4.3預置該元素所在列的下一個元素的存放位置；三元組順序表操作——轉置算法2三元組順序表操作——轉置算法2該算法中有4個平行的for循環(huán)。對于一個m行n列且非零元素個數為t的稀疏矩陣而言，循環(huán)次數分別為n和t兩種，故此算法時間復雜度為O(n+t)。顯然該算法優(yōu)于轉置算法1。為培養(yǎng)本科生的綜合實踐與研究創(chuàng)新能力，從國家到各高校都實施了大學生創(chuàng)新實踐項目。在項目實施過程中，教師指導n個本科生，如果教師是碩導或博導，本科生可接收教師的直接指導，部分本科生也可以在碩士研究生或博士研究生的指導下進行項目研究。本科生創(chuàng)新實踐項目中的人員關系具有如下形式：（1）若導師不帶研究生：

(導師,(本科生1,…,本科生k))（2）若導師帶研究生：

(導師,((研究生1,(本科生1,…,本科生m)),(本科生1,…,本科生n),…))請設計一種數據結構，存儲以上人員關系，為簡單起見，各類人員信息僅保留姓名。問題：本科生創(chuàng)新實踐項目中的人員關系(本科生1,…,本科