数据结构案例教程（CC++版）第2版 课件 第5章 元素扩展的线性表：矩阵和广义表

第5章元素扩展的线性表：

矩阵和广义表个性化推荐系统中的用户评分表导学问题1矩阵的基本操作⑴存取：给定一组下标，读出对应的数组元素；⑵修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作——寻址矩阵应该采用何种方式存储？矩阵没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。知识学习——矩阵的基本概念设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×c

calai-1ai……ahal+1……Loc(al)Loc(ai)知识学习——矩阵的存储结构常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

二维数组内存二维结构一维结构知识学习——矩阵的存储结构l2h2

l1h1(a)二维数组aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i

-l1)×(h2

-l2＋1)＋(j

-l2)本行中aij前面的元素个数每行元素个数整行数aij按行优先存储的寻址知识学习——矩阵的存储结构第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按列优先存储的寻址方法与此类似。知识学习——矩阵的存储结构按行优先存储的寻址知识学习——特殊矩阵的压缩存储特殊矩阵：包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。

稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：为多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。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=如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储——稀疏矩阵typedefstruct{

inti,j;

ElemTypee;}Triple;将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)——三元组定义三元组：稀疏矩阵的压缩存储——三元组顺序表typedefstruct{

Tripledata[MAXSIZE];

intmu,nu,tu;}SparseMatrix;定义三元组顺序表：三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。三元组表＝((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（矩阵的列数）稀疏矩阵的压缩存储——三元组顺序表创建基于三元组顺序表结构的稀疏矩阵: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的两重循环上。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，该算法的时间复杂度为O(tn)。最坏情况是，当稀疏矩阵中的非零元素个数t与mn同数量级时，上述算法的时间复杂度就为O(mn2)。显然这种情况下，该朴素算法效率较低。分析：A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第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循环。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，循环次数分别为n和t两种，故此算法时间复杂度为O(n+t)。显然该算法优于转置算法1。为培养本科生的综合实践与研究创新能力，从国家到各高校都实施了大学生创新实践项目。在项目实施过程中，教师指导n个本科生，如果教师是硕导或博导，本科生可接收教师的直接指导，部分本科生也可以在硕士研究生或博士研究生的指导下进行项目研究。本科生创新实践项目中的人员关系具有如下形式：（1）若导师不带研究生：

(导师,(本科生1,…,本科生k))（2）若导师带研究生：

(导师,((研究生1,(本科生1,…,本科生m)),(本科生1,…,本科生n),…))请设计一种数据结构，存储以上人员关系，为简单起见，各类人员信息仅保留姓名。问题：本科生创新实践项目中的人员关系(本科生1,…,本科