数据结构：第五章 数组和广义表

《数据结构：第五章 数组和广义表》由会员分享，可在线阅读，更多相关《数据结构：第五章 数组和广义表（90页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 数组和广义表数组和广义表 限制插入、删除位置限制插入、删除位置线性表线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。线性表线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。队列队列队列队列

2、在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。删除操作的线性表。删除操作的线性表。串串串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特特特特殊殊殊殊线线线线性性性性表表表表回忆：回忆：特点：特点：特点：特点：数据元素都是非数据元素都是非数据元素都是非数据元素都是非结构的原子类型，元素结构的原子类型，元素结构的原子类型，元素结构的原子类型，元素的值是不再分割的。的值是不再分割的。的值是不再分割的。的值是不再

3、分割的。什么是线性表？什么是线性表？线性表线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广广广广义义义义线线线线性性性性表表表表（多维）数组（多维）数组（多维）数组（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。广义表广义表广义表广义表线性表中的数据元素可以是线性表，线性

4、表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且元素的类型可以不相同。且元素的类型可以不相同。且元素的类型可以不相同。且元素的类型可以不相同。数组和广义表数组和广义表 本章讨论的两种数据结构本章讨论的两种数据结构本章讨论的两种数据结构本章讨论的两种数据结构数组和广义表数组和广义表数组和广义表数组和广义表可以看成是线性表的扩展，即可以看成是线性表的扩展，即可以看成是线性表的扩展，即可以看成是线性表的扩展，即表中的数据元素表中的数据元素表中的数据元素表中的数据元素本身也是一个数据结构。本身也是一个数据结构。本身也是一个数据结构。本身也是一个数据结构。5

5、.1数组数组的定义的定义5.3矩阵矩阵的压缩存储的压缩存储5.2数组数组的顺序表示和实现的顺序表示和实现5.4广义表广义表的类型定义的类型定义5.5广义表广义表的表示方法的表示方法第第5章章 数组和广义表数组和广义表5.1 数组的定义数组的定义n n数组的定义数组的定义数组的定义数组的定义qq数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元个数据元素称为一个数组元素（简称为元素），每个元个数据元素称为一个

6、数组元素（简称为元素），每个元个数据元素称为一个数组元素（简称为元素），每个元素受素受素受素受n n( (n n1)1)个线性关系的约束，每个元素在个线性关系的约束，每个元素在个线性关系的约束，每个元素在个线性关系的约束，每个元素在n n个线性关个线性关个线性关个线性关系中的序号系中的序号系中的序号系中的序号i i1 1、i i2 2、i in n称为该元素的下标，并称该数称为该元素的下标，并称该数称为该元素的下标，并称该数称为该元素的下标，并称该数组为组为组为组为 n n 维数组。维数组。维数组。维数组。 n n数组的特点数组的特点数组的特点数组的特点qq元素本身可以具有某种结构，属于同一数

7、据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；qq数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，Am) 其中：其中： Ai=(ai1，ai2，ain) (1im)数组数组线性表的推广线性表的推广二维数组是二维数组是数据元素为线性表的线性表。数据元素为线性表的线性表。5.1 数组的定义数组的定义

8、a a1111 a a1212 a a1n1n a a21 21 a a2222 a a2n2n a am1 m1 a am2m2 a amnmnA=例如，元素例如，元素a a2222受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有一个行前驱一个行前驱一个行前驱一个行前驱a a2121和一个行后继和一个行后继和一个行后继和一个行后继a a2323，在列上有一个列前，在列上有一个列前，在列上有一个列前，在列上有一个列前驱驱驱驱a a1 12 2和和一个列后继和和一个列后继和和一个列后继和和一个列后继a a3232。数组示例数

9、组示例5.1 数组的定义数组的定义数组的基本操作数组的基本操作在在在在数数数数组组组组中中中中插插插插入入入入（或或或或删删删删除除除除）一一一一个个个个元元元元素素素素有有有有意意意意义义义义吗吗吗吗？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=将元素将元素将元素将元素 x x 插入插入插入插入到数组中第到数组中第到数组中第到数组中第1 1行第行第行第行第2 2列。列。列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=删除数组中删除数组中删除数组中删除数组中第第第第1 1行第行第行第行第2 2列元素。列元素。列元素。列元素。

10、5.1 数组的定义数组的定义数组一旦被定义，数组一旦被定义，它的维数和维界就它的维数和维界就不再改变，一般不不再改变，一般不做插入和删除操作做插入和删除操作数组的基本操作数组的基本操作 存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素； 修修修修改改改改：给给给给定定定定一一一一组组组组下下下下标标标标，存存存存储储储储或或或或修修修修改改改改与与与与其其其其相相相相对对对对应应应应的的的的数组元素。数组元素。数组元素。数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只

11、对应一种操作存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？数数数数组组组组没没没没有有有有插插插插入入入入和和和和删删删删除除除除操操操操作作作作，所所所所以以以以，不不不不用用用用预预预预留留留留空空空空间间间间，适合采用顺序存储。适合采用顺序存储。适合采用顺序存储。适合采用顺序存储。5.1 数组的定义数组的定义5.2数组数组的顺序表示和实现的顺序表示和实现一维数组一维数组内内内内 存存存存二维结构二维结构二维结构二维结构一维结构一维结构一维结构一维结构二维数组二维数组二维数组二维数组常用的映射方法有两

12、种：常用的映射方法有两种：常用的映射方法有两种：常用的映射方法有两种：按按按按行行行行优先：优先：优先：优先：先行后列先行后列先行后列先行后列，先存储行号较小的元素，行，先存储行号较小的元素，行，先存储行号较小的元素，行，先存储行号较小的元素，行号相同者先存储列号较小的元素号相同者先存储列号较小的元素号相同者先存储列号较小的元素号相同者先存储列号较小的元素。PASCAL、C;按按按按列列列列优先：优先：优先：优先：先列后行先列后行先列后行先列后行，先存储列号较小的元素，列，先存储列号较小的元素，列，先存储列号较小的元素，列，先存储列号较小的元素，列号相同者先存储行号较小的元素。号相同者先存储行

13、号较小的元素。号相同者先存储行号较小的元素。号相同者先存储行号较小的元素。FORTRAN;5.2数组数组的顺序表示和实现的顺序表示和实现二维数组二维数组a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,21.1.先行后列的映射方法先行后列的映射方法先行后列的映射方法先行后列的映射方法2.2.先行后列的映射方法先行后列的映射方法先行后列的映射方法先行后列的映射方法a0,1,a0,0a0,2a1,0a1,1a1,2a1,0a0,0a0,1a1,1a0,2a1,2设设设设一一一一维维维维数数数数组组组组的的的的下下下下标标标标的的的的范范范范围围围围为为为

14、为闭闭闭闭区区区区间间间间l l，h h，每每每每个个个个数数数数组组组组元元元元素素素素占占占占用用用用 c c 个个个个存存存存储储储储单单单单元元元元，则则则则其其其其任任任任一一一一元元元元素素素素 a ai i 的的的的存存存存储地址可由下式确定：储地址可由下式确定：储地址可由下式确定：储地址可由下式确定： Loc(Loc(a ai i) )Loc(Loc(a al l) )( (i il l) )c c c al ai-1 ai ah al+1 Loc(al)Loc(ai)5.2数组数组的顺序表示和实现的顺序表示和实现二维数组二维数组l2h2 l1h1(a) 二维数组二维数组a a

15、ij ij前面的元素个数前面的元素个数前面的元素个数前面的元素个数= =阴影部分表示的元素个数阴影部分表示的元素个数阴影部分表示的元素个数阴影部分表示的元素个数= =整整整整行行行行数数数数 每每每每行行行行元元元元素素素素个个个个数数数数+ +本本本本行行行行中中中中a aij ij前面的元素个数前面的元素个数前面的元素个数前面的元素个数= =( ( ( (i i - - - -l l1 1) ) ) ) ( ( ( (h h2 2 - - - -l l2 21 1) ) ) )( ( ( (j j - - - -l l2 2) ) ) )本行中本行中本行中本行中a aij ij前面的元素个

16、数前面的元素个数前面的元素个数前面的元素个数每行元素个数每行元素个数每行元素个数每行元素个数整整整整行行行行数数数数aij按行优先存储的寻址按行优先存储的寻址按行优先存储的寻址按行优先存储的寻址5.2数组数组的顺序表示和实现的顺序表示和实现二维数组二维数组第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )个元素个元素Loc(Loc(a aij ij) )Loc(Loc(a al l1 1l l2 2)

17、)( (i il l1 1)()(h h2 2l l2 21)1)( (j jl l2 2)c c按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。按行优先存储的寻址按行优先存储的寻址按行优先存储的寻址按行优先存储的寻址5.2数组数组的顺序表示和实现的顺序表示和实现二维数组二维数组例例例例5.2.15.2.1：以矩阵形式表示的：以矩阵形式表示的：以矩阵形式表示的：以矩阵形式表示的mm行行行行n n列的二维数组如下：列的二维数组如下：列的二维数组如下：列的二维数组如下：若每个数组元素占用若每个数组元素占用若每个数组元素占用若每个数组元素占用 L L 个存储单元，个存储单元，个存储单

18、元，个存储单元，计算分别以计算分别以计算分别以计算分别以行序、列序为主序时行序、列序为主序时行序、列序为主序时行序、列序为主序时数据元素数据元素aij的存储位置。的存储位置。Amn=a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1行序为主序的存储示图：行序为主序的存储示图：a00a01a0n-1a10a11a1n-1am-1,0am-1,1am-1,n-1数据元素数据元素aij的存储位置：的存储位置：loc(i,j)=loc(0,0)+aij之前的元素个数之前的元素个数LAmn=a00a01a02a0,n-1a10a11a12a1

19、,n-1am-1,0am-1,1am-1,2am-1,n-1(i*n+j)列序为主序的存储示图：列序为主序的存储示图：a00a10am-10a01a11am-1,1a0,n-1a1,n-1am-1,n-1Amn=a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1数据元素的存储位置：数据元素的存储位置：loc(i,j)=loc(0,0)+aij之前的元素个数之前的元素个数Lj*m+i书上p93给出了数组的顺序存储表示和实现。（自己看，不做要求）n n一般矩阵的存储可以用上述转换为一维结构实现一般矩阵的存储可以用上述转换为一维结构实现一

20、般矩阵的存储可以用上述转换为一维结构实现一般矩阵的存储可以用上述转换为一维结构实现n n特殊特殊特殊特殊矩阵矩阵矩阵矩阵：值相同的元素或者零元素在矩阵中分布：值相同的元素或者零元素在矩阵中分布：值相同的元素或者零元素在矩阵中分布：值相同的元素或者零元素在矩阵中分布有一定规律，有一定规律，有一定规律，有一定规律，包括包括包括包括对称矩阵、三角矩阵、对角矩阵对称矩阵、三角矩阵、对角矩阵对称矩阵、三角矩阵、对角矩阵对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。和稀疏矩阵等。和稀疏矩阵等。和稀疏矩阵等。 n n稀疏矩阵：稀疏矩阵：稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。矩阵中有很多零元

21、素。矩阵中有很多零元素。n n压缩存储压缩存储压缩存储压缩存储的基本思想是：的基本思想是：的基本思想是：的基本思想是：qq为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；qq对零元素不分配存储空间。对零元素不分配存储空间。对零元素不分配存储空间。对零元素不分配存储空间。 5.3矩阵矩阵的压缩存储的压缩存储3647862842481697460582957A对称矩阵特点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分

22、的元素。只存储下三角部分的元素。只存储下三角部分的元素。5.3.1特殊矩阵特殊矩阵的压缩存储的压缩存储对称矩阵对称矩阵( (a) a) 下下下下三三三三角角角角矩矩矩矩阵阵阵阵 ( (b) b) 存存存存储储储储说说说说明明明明 ( (c) c) 计计计计算算算算方方方方法法法法数组下标从数组下标从数组下标从数组下标从0 0开始开始开始开始a aij ij在一维数组中的序号在一维数组中的序号在一维数组中的序号在一维数组中的序号= =该元素前面的元素个数该元素前面的元素个数该元素前面的元素个数该元素前面的元素个数= = i i ( ( ( (i i+1+1) ) ) )/2+ /2+ j j一维

23、数组下标从一维数组下标从一维数组下标从一维数组下标从0 0开始开始开始开始a aij ij在一维数组中的下标在一维数组中的下标在一维数组中的下标在一维数组中的下标k k= = i i ( ( ( (i i+1+1) ) ) )/2+ /2+ j j 0 in- -10 j n- -1 aij每行元素个数每行元素个数12iaij在本行中的序号在本行中的序号aij第第0行行第第1行行第第i-1行行5.3.1特殊矩阵特殊矩阵的压缩存储的压缩存储对称矩阵对称矩阵对于下三角中的元素对于下三角中的元素对于下三角中的元素对于下三角中的元素a aij ij（i i j j），在数组，在数组，在数组，在数组SA

24、SA中的下标中的下标中的下标中的下标k k与与与与i i、j j的关系为：的关系为：的关系为：的关系为：k ki i(i i1)/21)/2j j 。上三角中的元素上三角中的元素上三角中的元素上三角中的元素a aij ij（i ij j），），），），因为因为因为因为a aij ija aji ji，则访问和则访问和则访问和则访问和它对应的元素它对应的元素它对应的元素它对应的元素a aji ji即可，即：即可，即：即可，即：即可，即：k kj j ( (j j1)/21)/2i i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an

25、-11 an-1n-1 第第2行行0 1 2 3 4 5 0 1 2 3 4 5 k k n(n+1)/2-1 n(n+1)/2-15.3.1特殊矩阵特殊矩阵的压缩存储的压缩存储对称矩阵对称矩阵令令令令 I I = maxi,j, = maxi,j, = maxi,j, = maxi,j,J J = mini,j, = mini,j, = mini,j, = mini,j,则则则则3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7( (a)a)下三角矩阵下三角矩阵下三角矩阵下三角矩阵3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(

26、(b)b)上三角矩阵上三角矩阵上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。5.3.2特殊矩阵特殊矩阵的压缩存储的压缩存储三角矩阵三角矩阵矩阵中任一元素矩阵中任一元素矩阵中任一元素矩阵中任一元素a aij ij在在在在数组数组数组数组中的下标中的下标中的下标中的下标k k与与与与i i、j j的对应关系：的对应关系：的对应关系：的对应关系：i( (i1) )/2j 当当ijn( (n1) )/2 当当ijk=0 0 1 1

27、 2 2 3 3 4 4 5 5 k k n(n+1)/2n(n+1)/2第第第第1 1行行行行第第第第0 0行行行行 a a0000 a a1010 a a1111 a a2020 a a2121 a aij ij a an n-1-1n n-1-1 第第第第2 2行行行行 c c a a2222存储存储存储存储下三角下三角下三角下三角元素元素元素元素对角线上方的常数对角线上方的常数对角线上方的常数对角线上方的常数只存一个只存一个只存一个只存一个5.3.2特殊矩阵特殊矩阵的压缩存储的压缩存储三角矩阵三角矩阵矩阵中任一元素矩阵中任一元素矩阵中任一元素矩阵中任一元素a aij ij在在在在数组数

28、组数组数组中的下标中的下标中的下标中的下标k k与与与与i i、j j的对应关系：的对应关系：的对应关系：的对应关系： i i ( ( ( (2 2n ni i1 1) ) ) )/2/2j ji i 当当当当i i j jn n ( ( ( (n n1 1) ) ) ) /2 /2 当当当当i ij jk=k=存储存储存储存储上三角上三角上三角上三角元素元素元素元素对角线下方的常数对角线下方的常数对角线下方的常数对角线下方的常数只存一个只存一个只存一个只存一个5.3.1特殊矩阵特殊矩阵的压缩存储的压缩存储三角矩阵三角矩阵nn-i+1例例5.3.1：n n假设以一维数组作为假设以一维数组作为n

29、阶对称矩阵阶对称矩阵A的的存储空存储空间（行和列下标均从间（行和列下标均从0开始），开始），以行序为主序以行序为主序存储存储A的下三角，则元素的下三角，则元素A56的值存储在的值存储在S_中。中。n n5*(5+1)/2+6=21对角矩阵：对角矩阵：对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主的带状区域中，除了主的带状区域中，除了主的带状区域中，除了主对角线和它的上下方若干条对对角线和它的上下方若干条对对角线和它的上下方若干条对对角线和它的上下方若干条对角

30、线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=5.3.3特殊矩阵特殊矩阵的压缩存储的压缩存储对角矩阵对角矩阵a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=将带状区将带状区域立起来域立起来0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a4

31、3 a44 0B=5.3.3特殊矩阵特殊矩阵的压缩存储的压缩存储对角矩阵对角矩阵按行按行存储存储 元素元素元素元素a aij ij前面的元素个数前面的元素个数前面的元素个数前面的元素个数=2 + 3=2 + 3( ( ( (i i1 1) ) ) )+ +( ( ( ( j ji i + 1+ 1) ) ) )=2=2i+ ji+ j 一维数组下标从一维数组下标从一维数组下标从一维数组下标从0 0开始开始开始开始元素元素元素元素a aij ij在一维数组中的下标在一维数组中的下标在一维数组中的下标在一维数组中的下标=2=2i+ ji+ j(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数

32、组中压缩到一维数组中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6 7 8 9 10 11 12(a) 三对角矩阵三对角矩阵 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a445.3.3特殊矩阵特殊矩阵的压缩存储的压缩存储对角矩阵对角矩阵15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0 A=如何只存储非零元素？如何只存储非零元素？如何只存储非零元素？

33、如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。5.3.4特殊矩阵特殊矩阵的压缩存储的压缩存储稀疏矩阵稀疏矩阵typedef structtypedef struct int i, j; / int i, j; /行下标，列下标行下标，列下标行下标，列下标行下标，列下标 ElemType e; / ElemType e; /非零元素值非零元素值非零元素值非零元素值 Triple ; Triple ;将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素

34、表示为将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( ( ( (行号，列号，非零元素值行号，列号，非零元素值行号，列号，非零元素值行号，列号，非零元素值) ) ) )三元组三元组三元组三元组定义三元组：定义三元组：定义三元组：定义三元组：方法一方法一：稀疏矩阵的压缩存储：稀疏矩阵的压缩存储三元组三元组5.3.4特殊矩阵特殊矩阵的压缩存储的压缩存储稀疏矩阵稀疏矩阵三元组表三元组表三元组表三元组表：将稀疏矩阵的非零元素对应的三元组所构将稀疏矩阵的非零元素对应的三元组所构将稀疏矩阵的非零元素对应的三元组所构将稀疏矩阵的非零元素对应的三元组所构成的集合，成的集合，成的集合，成的集

35、合，按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。三元组表三元组表三元组表三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存储三元组表？如何存储三元组表？如何存储三元组表？如何存储三元组表？稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组三元组采用顺序存储结构存储三元组表采

36、用顺序存储结构存储三元组表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -115 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=7（非零元个数）（非零元个数）是否对应唯一的稀疏矩阵？是否对应唯一的稀疏矩阵？是否对应唯一的稀疏矩阵？是否对应唯一的稀疏矩阵？5（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数

37、）稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组三元组三元组顺序表以顺序存储结构表示三元组表，是稀疏矩阵的一种压缩存储方式。#defineMAXSIZE12500#defineMAXSIZE12500/ /非零元个数最大值非零元个数最大值非零元个数最大值非零元个数最大值typedefstructtypedefstructinti,j;inti,j;/ /行下标和列下标行下标和列下标行下标和列下标行下标和列下标ElemTypee;ElemTypee;Triple;Triple;typedefstructtypedefstructTripledataMAXSIZE+1;TripledataMAXSIZ

38、E+1;/ /非零元三元组表非零元三元组表非零元三元组表非零元三元组表,data0,data0未用未用未用未用intmu,nu,tu;intmu,nu,tu;/ /行数、列数、非零元个数行数、列数、非零元个数行数、列数、非零元个数行数、列数、非零元个数TSMatrix;TSMatrix;TSMatrixa,b;TSMatrixa,b;例：例：例：例： 15 0 0 0 91 0 11 0 0 0 0 3 0 0 0 22 0 6 0 0 0 0 0 0 0 - -15 0 0 0 0 B=15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0

39、0 91 0 0 0 0 0A=三元组顺序表操作三元组顺序表操作转置操作转置操作 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列

40、数）（矩阵的列数）7（非零元个数）（非零元个数）三元组顺序表操作三元组顺序表操作转置操作转置操作三元组顺序表操作三元组顺序表操作转置算法转置算法1n n基本思想：基本思想：在在A的三元组顺序表中依次找第的三元组顺序表中依次找第0列、第列、第1列、列、直到最后一列的三元组，并将直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。的三元组顺序表中。 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456Max

41、Term- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）三元组顺序表操作三元组顺序表操作转置算法转置算法1 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） ro

42、w col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第0 0列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 0 0 15 0 0 15 0 4 91 0 4 91 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的

43、行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第1 1列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空

44、闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第2 2列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩

45、阵B B中中中中 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 2

46、2 3 2 6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第3 3列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的

47、列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 2 6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第4 4列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 3 0 22 3 0 22 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行

48、数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第5 5列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B

49、 B中中中中1. 1. 设置转置后矩阵设置转置后矩阵设置转置后矩阵设置转置后矩阵B B的行数、列数和非零元个数；的行数、列数和非零元个数；的行数、列数和非零元个数；的行数、列数和非零元个数；2. 2. 在在在在B B中设置初始存储位置中设置初始存储位置中设置初始存储位置中设置初始存储位置q q；3. for (col=3. for (col=最小列号最小列号最小列号最小列号; ; col=col=最大列号最大列号最大列号最大列号; ; col+)col+) 3.1 3.1 在在在在A A中查找列号为中查找列号为中查找列号为中查找列号为colcol的三元组；的三元组；的三元组；的三元组； 3.2

50、 3.2 交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入B B中中中中q q位置；位置；位置；位置； 3.3 3.3 q+q+；三元组顺序表操作三元组顺序表操作转置算法转置算法1稀疏矩阵的转置稀疏矩阵的转置稀疏矩阵的转置稀疏矩阵的转置 ( (算法算法算法算法5.1)5.1) StatusTransposeSMatrix(TSMatrixM,TSMatrix&T)intq,col,p;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu)q=1;for(col=1;col=T.mu;+col)for(p=1;p=M.tu;+p)

51、if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;returnOK;三元组顺序表操作三元组顺序表操作转置算法转置算法1n n该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在colcol和和和和p p的两重循环上。的两重循环上。的两重循环上。的两重循环上。n n对于一个对于一个对于一个对于一个mm行行行行n n列且非零元素个数为列且非零元素个数为列且非零元素个数为列且非零元素个数为t t的稀疏矩阵而言，的稀疏矩阵而言，的稀疏矩阵而言，的稀疏

52、矩阵而言，该算法的时间复杂度为该算法的时间复杂度为该算法的时间复杂度为该算法的时间复杂度为O O( (t t* *n n) )。n n例：若矩阵有例：若矩阵有例：若矩阵有例：若矩阵有200200行，行，行，行，200200列，列，列，列，10,00010,000个非零元素，个非零元素，个非零元素，个非零元素，总共有总共有总共有总共有2,000,0002,000,000次处理。次处理。次处理。次处理。n n最坏最坏最坏最坏情况是，当稀疏矩阵中的非零元素个数情况是，当稀疏矩阵中的非零元素个数情况是，当稀疏矩阵中的非零元素个数情况是，当稀疏矩阵中的非零元素个数t t与与与与mnmn同同同同数量级时，

53、上述算法的时间复杂度就为数量级时，上述算法的时间复杂度就为数量级时，上述算法的时间复杂度就为数量级时，上述算法的时间复杂度就为O O( (mnmn2 2) )。n n显然这种情况下，显然这种情况下，显然这种情况下，显然这种情况下，该算法该算法该算法该算法效率较低。效率较低。效率较低。效率较低。 分析分析分析分析：A A中第中第中第中第0 0列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在B B中下中下中下中下标为标为标为标为0 0的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应

54、存放在的位置上，该列中其它非零元素应存放在B B中中中中后面连续的位置上，那么第后面连续的位置上，那么第后面连续的位置上，那么第后面连续的位置上，那么第1 1列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在B B中的位置便等于第中的位置便等于第中的位置便等于第中的位置便等于第0 0列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在B B中的位中的位中的位中的位置加上第置加上第置加上第置加上第0 0列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。 基本思想：基本思

55、想：基本思想：基本思想：顺序取，直接存。顺序取，直接存。顺序取，直接存。顺序取，直接存。即即即即在在在在A A中依次取三元中依次取三元中依次取三元中依次取三元组，交换其行号和列号放到组，交换其行号和列号放到组，交换其行号和列号放到组，交换其行号和列号放到B B 中中中中适当适当适当适当位置。位置。位置。位置。 如何确定当前从如何确定当前从如何确定当前从如何确定当前从A A中取出的三元组在中取出的三元组在中取出的三元组在中取出的三元组在B B中的位置？中的位置？中的位置？中的位置？三元组顺序表操作三元组顺序表操作转置算法转置算法2 row col itemrow col item0 01 12

56、23 34 45 56 6MaxTermMaxTerm- - - -1 16 6（矩阵的行数）（矩阵的行数）（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15第第0列第列第1个非零元素个非零元素第第0列有列有3个非零元素个非零元素第第1列第列第1个非零元素个非零元素三元组顺序表操作三元组顺序表操作转置算法

57、转置算法2引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：cnumcolscnumcols：存储矩阵存储矩阵存储矩阵存储矩阵A A中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；cpotcloscpotclos：初值表示矩阵初值表示矩阵初值表示矩阵初值表示矩阵A A中某列的第一个非零元中某列的第一个非零元中某列的第一个非零元中某列的第一个非零元素在素在素在素在B B中的位置。中的位置。中的位置。中的位置。 数据结构设计：数据结构设计：数据结构设计：数据结构设计：cpot0=0

58、cpot0=0；cpotcol=cpotcolcpotcol=cpotcol- - - -1+cnumcol1+cnumcol- - - -11； 1col 1colcols-1cols-1cnumcnum与与与与cpotcpot存在如下递推关系：存在如下递推关系：存在如下递推关系：存在如下递推关系：三元组顺序表操作三元组顺序表操作转置算法转置算法2 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲

59、闲 闲闲闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） col 0 1 2 3 4 5 cnumcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根据矩阵根据矩阵根据矩阵根据矩阵A A计算计算计算计算cnumcnum和和和和cpotcpot 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空

60、闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - -

61、-1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7

62、 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot3cpot3cpot4 cpot5cpot4 cpot5 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元

63、个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 3 0 22 3 0 22 5 0 -15 5 0 -15 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6

64、2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 3 0 22

65、3 0 22 5 0 -15 5 0 -15 1 1 11 1 1 11 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cp

66、otcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 3 0 22 3 0 22 5 0 -15 5 0 -15 1 1 11 1 1 11 2 1 3 2 1 3 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row c

67、ol item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cp

68、ot5cpot5 1 1 11 1 1 11 2 1 3 2 1 3cpot2cpot2cpot1cpot1 3 2 6 3 2 6cpot3cpot3 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放

69、在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 3 0 22 3 0 22 5 0 -15 5 0 -15 1 1 11 1 1 11 2 1 3 2 1 3 3 2 6 3 2 6 0 4 91 0 4 91 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3

70、1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0

71、0 15 3 0 22 3 0 22 5 0 -15 5 0 -15 1 1 11 1 1 11 2 1 3 2 1 3 3 2 6 3 2 6 0 4 91 0 4 911. 1. 设置转置后矩阵设置转置后矩阵设置转置后矩阵设置转置后矩阵B B的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；2. 2. 计算计算计算计算A A中每一列的非零元素个数；中每一列的非零元素个数；中每一列的非零元素个数；中每一列的非零元素个数；3. 3. 计算计算计算计算A A中每一列的第一个非零元素在中每一列的第一个非零元素在中每一列的第一个非

72、零元素在中每一列的第一个非零元素在B B中的下标；中的下标；中的下标；中的下标；4. 4. 依次取依次取依次取依次取A A中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组； 4.1 4.1 确定该元素在确定该元素在确定该元素在确定该元素在B B中的下标中的下标中的下标中的下标q q； 4.2 4.2 将该元素的行号列号交换后存入将该元素的行号列号交换后存入将该元素的行号列号交换后存入将该元素的行号列号交换后存入B B中中中中q q的位置；的位置；的位置；的位置； 4.3 4.3 预置该元素所在列的下一个元素的存放位置

73、；预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；三元组顺序表操作三元组顺序表操作转置算法转置算法2三元组顺序表操作三元组顺序表操作转置算法转置算法2n n该算法中有该算法中有4个平行的个平行的for循环。循环。n n对于一个对于一个m行行n列且非零元素个数为列且非零元素个数为t的稀疏矩的稀疏矩阵而言，循环次数分别为阵而言，循环次数分别为n和和t两种，故此算法两种，故此算法时间复杂度为时间复杂度为O(n+t)。n n显然该算法优于转置算法显然该算法优于转置算法1。 方法二：稀疏矩阵的压缩存储方法二：稀疏矩阵的压缩存储十字链

74、表十字链表n n当矩阵中非零元素的当矩阵中非零元素的当矩阵中非零元素的当矩阵中非零元素的个数个数个数个数和和和和位置位置位置位置经过运算后经过运算后经过运算后经过运算后变化变化变化变化较大较大较大较大时，就不宜采用顺序存储结构，而应采用时，就不宜采用顺序存储结构，而应采用时，就不宜采用顺序存储结构，而应采用时，就不宜采用顺序存储结构，而应采用链链链链式存储结构式存储结构式存储结构式存储结构来表示三元组。来表示三元组。来表示三元组。来表示三元组。n n稀疏矩阵的链接表示采用十字链表：稀疏矩阵的链接表示采用十字链表：稀疏矩阵的链接表示采用十字链表：稀疏矩阵的链接表示采用十字链表：行链表行链表行链表

75、行链表与与与与列列列列链表链表链表链表十字交叉。十字交叉。十字交叉。十字交叉。n n行链表与列链表都是行链表与列链表都是行链表与列链表都是行链表与列链表都是带表头结点的循环链表带表头结点的循环链表带表头结点的循环链表带表头结点的循环链表。用。用。用。用表头结点表征是第几行，第几列。表头结点表征是第几行，第几列。表头结点表征是第几行，第几列。表头结点表征是第几行，第几列。n n元素结点元素结点元素结点元素结点qrightright指向同一行中下一指向同一行中下一个非零元素的指针（向右域）个非零元素的指针（向右域）qdowndown指向同一列中下一指向同一列中下一个非零元素的指针（向下域）个非零元

76、素的指针（向下域）n n表头结点表头结点表头结点表头结点q 行表头结点行表头结点q 列表头结点列表头结点q nextnext用于表示头结点的链接用于表示头结点的链接rowcolnextrightdownrowcolvalrightdown稀疏矩阵的十字链表表示的示例稀疏矩阵的十字链表表示的示例51122334455n n需要辅助结点作链表的表头，同时每个结点要需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。疏时才能起到节省空间的效果。十字链表的类型定义十字链表的类型定义typedefstruct

77、OLNodetypedefstructOLNode/ /元素结点元素结点元素结点元素结点inti,j;inti,j;/ /非零元的行和列下标非零元的行和列下标非零元的行和列下标非零元的行和列下标ElemTypee;ElemTypee;structOLNode*right,*down;structOLNode*right,*down;/ /该非零元所在行表和列该非零元所在行表和列该非零元所在行表和列该非零元所在行表和列表的后继链域表的后继链域表的后继链域表的后继链域OLNode,*OLink;OLNode,*OLink;typedefstructtypedefstructOLink*rhead,

78、*chead;OLink*rhead,*chead;/ /行和列链表头指针数组行和列链表头指针数组行和列链表头指针数组行和列链表头指针数组intmu,nu,tu;intmu,nu,tu;CrossList;CrossList; 2 0 2M=3 0 0 50 1 0 02 0 0 0 0 0 3 0 3 5 1 1 1稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象：数据对象：D ei | i=1,2,.,n; n0; eiAtomSet 或或 eiGList, AtomSet为某个数据对象为某个数据对象 数据关系：数据关

79、系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作: LS = ( 1, 2, , n )其中：其中： i 可以为单个元素，也可以为广义表可以为单个元素，也可以为广义表n表示长度表示长度 i 为为原子原子 或或 为为子表子表习惯习惯大写大写表示表示广义表广义表，小写小写表示表示原子原子例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ) /广义表是广义表是递归递归定义的定义的线性结构线性结构 递归表递归表广义表是一个广义表是一个多层次多层次的

80、的线性结构线性结构例如：例如：D=(E, F)其中其中: : E=(a, (b, c) F=(d, (e)DEFa( )d( )bce广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点:1) 广义表中的数据元素有相对广义表中的数据元素有相对次序次序;2)广义表的广义表的长度长度定义为最外层包含元素个数定义为最外层包含元素个数;3) 广义表的广义表的深度深度定义为所含括弧的重数定义为所含括弧的重数; 注意注意:“原子原子”的深度为的深度为 0 ; “空表空表”的深度为的深度为 1 。4) 广义表可以广义表可以共享共享;5) 广义表可以是一个广义表可以是一个递归递归的表的表 递

81、归表的深度是无穷值，长度是有限值。递归表的深度是无穷值，长度是有限值。6) 任何一个非空广义表任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为均可分解为 表头表头 Head(LS) = 1 和和 表尾表尾 Tail(LS) = ( 2, , n) 两部分两部分例如例如: D = (E, F) = (a, (b, c)，F )Head(D) = E Tail(D) = (F)Head(E) = a Tail(E) = (b, c)Head(b, c) = (b, c) Tail(b, c) = ( )Head(b, c) = b Tail(b, c) = (c)Head(c)

82、= c Tail(c) = ( ) 广义表中的长度广义表中的长度E=( ) 长度为长度为0L=(a,b) 长度为长度为2A=(x,(a,b) 长度为长度为2B=(x,(a,b),y)长度为长度为2C=(x,(a,b), (x,(a,b),y)长度为长度为2D=(a,(a,(a,(a,() 长度为长度为2 返回返回 广义表中的深度广义表中的深度L=(a,b) 深度为深度为1A=(x,(a,b) 深度为深度为2B=(x,(a,b),y) 深度为深度为3C=(x,(a,b), (x,(a,b),y)深度为深度为4D=(a,(a,(a,(a,() 深度为无穷大深度为无穷大 返回返回 结构的创建和销毁结

83、构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基基本本操操作作 状态函数状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit( );5.5 广义表的表示方法广义表的表示方法由于广义表中的数据类型不一样，所以很难用顺序结

84、构来表示，通常采用链式结构来表示如何设定结点结构呢？由于列表中的数据可以是原子或列表，需表结点：表示列表原子结点：表示原子表结点表结点:原子结点：原子结点：tag=0 datatag=1 hp tp表头、表尾分析法表头、表尾分析法:构造存储结构的方法构造存储结构的方法: :若表头为原子，则为若表头为原子，则为空表空表 ls = NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。否则，依次类推。按层次来，先看整体有多少个按层次来，先看整体有多少个“子表子表”，从表头，从表头指针出来就有多少个表结点，然后从出来的表结指针出来就有多少个表结点，然后从

85、出来的表结点按次序在进行延展，对于第一个表结点代表的点按次序在进行延展，对于第一个表结点代表的是第一个子表，那么第一个子表里有多少个子表是第一个子表，那么第一个子表里有多少个子表或者原子节点，从这个表结点里就延伸出多少个或者原子节点，从这个表结点里就延伸出多少个“二代二代”表结点，层层向下，直到表结点指示原表结点，层层向下，直到表结点指示原子节点子节点.A=（）B=（e）C=(a,(b,c,d)D=(A,B,C)=(),(e), (a,(b,c,d)n除空表的表头指针为空外，其它的除空表的表头指针为空外，其它的hp指向表头，指向表头，tp指向表尾指向表尾n容易分清层次容易分清层次n最高层的表结

86、点数则为列表的长度最高层的表结点数则为列表的长度3 0 0 50 -1 0 02 0 0 01、画出矩阵的十字链表。、画出矩阵的十字链表。思考题：思考题：2、画出矩阵X的三元组表和十字链表。思考题：思考题：3、广义表 F=(a),b),( ),(d),(e,f) 画出其图形表示及存储结构。思考题：思考题：1111110f0e0b0a11110d1113、4、广义表 G=(a,b,( ),( ),(a,(b),( ) 画出其图形表示及存储结构。5 5、假设有二维数组假设有二维数组elemtype a68 ; elemtype a68 ; 每个数每个数据元素占据元素占6 6个字节个字节, ,存储器按字节编址。存储器按字节编址。a a的基地址的基地址为为1000,1000,则：则： (1)(1)数组数组a a的体积；的体积； (2)(2)数组数组a a的最后一个元素的第一个字节的地址；的最后一个元素的第一个字节的地址； (3)(3)按行存储时，按行存储时，a2,4a2,4的第一个字节的地址；的第一个字节的地址； (4)(4)按列存储时，按列存储时，a2,4a2,4的第一个字节的地址的第一个字节的地址；思考题：思考题：111111110a0a0b1110b4、第五章内容到此结束