数据结构 第4章 广义线性表(g)

1、数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义第四章第四章 广义线性表广义线性表本章的基本内容是：本章的基本内容是：数组的逻辑结构特征数组的逻辑结构特征数组的存储方式及寻址方法数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构广义表的基本概念和存储结构数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义第四章第四章 广义线性表广义线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除位置线性表线性表具有相同类型的数据元素的有限

2、序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特殊线性表特殊线性表数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义第四章第四章 广义线性表广义线性表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广义线性表广义线性表（多维）数组

3、（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有线性表，但所有元素的类型相同元素的类型相同。广义表广义表线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且且元素的类型可以不相同元素的类型可以不相同。数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义数组的定义数组的定义数组是由一组数组是由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集合合，每个数据元素称为一个数组元素（简称为元每个数据元素称为一个数组元素（简称为元素），每个元素受素），每个元素受n(n1)个个线性关系线性关系的约束，的约束，每每个元素在个元素在n个线

4、性关系中的序号个线性关系中的序号i1、i2、in称为称为该元素的下标，并称该数组为该元素的下标，并称该数组为 n 维数组。维数组。 数组的特点数组的特点元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合数组是一个具有固定格式和数量的数据集合。广义线性表广义线性表多维数组多维数组数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义线性表广义线性表多维数组多维数组 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受两个线性关系的约束，在行上有受两个线

5、性关系的约束，在行上有一个行前驱一个行前驱a21和一个行后继和一个行后继a23，在列上有一个列，在列上有一个列前驱前驱a12和和一个列后继和和一个列后继a32。数组示例数组示例数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)数组数组线性表的推广线性表的推广二维数组是二维数组是数据元素为线性表数据元素为线性表的的线性表线性表。广义线性表广义线性表多维数组多维数组数据结构（数据结构（C+版）版）广东海洋大学广东海洋大

6、学 谢仕义谢仕义数组的基本操作数组的基本操作广义线性表广义线性表多维数组多维数组在数组中插入（或删除）一个元素有意义吗？在数组中插入（或删除）一个元素有意义吗？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=将元素将元素 x 插入插入到数组中第到数组中第1行第行第2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=删除数组中删除数组中第第1行第行第2列元素。列元素。数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义数组的基本操作数组的基本操作 存取存取：给定一组下标，读出对应的数组元素；：给定一组下标，读出对应

7、的数组元素； 修改修改：给定一组下标，存储或修改与其相对应的：给定一组下标，存储或修改与其相对应的数组元素。数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？数组没有插入和删除操作，所以，不用预留空间，数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。适合采用顺序存储。广义线性表广义线性表多维数组多维数组数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义数组的存储结构与寻址数组的存储结构与寻址一维数组一维数组设一维数组的下标的范围为闭区间设一维数组的下标的范围为闭区间l，h，

8、每个每个数组元素占用数组元素占用 c 个存储单元，则个存储单元，则其其任一元任一元素素 ai 的的存储地址可由下式确定：存储地址可由下式确定： Loc(ai)Loc(al)(il)c 广义线性表广义线性表多维数组多维数组c al ai-1 ai ah al+1 Loc(al)Loc(ai)数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义常用的映射方法有两种：常用的映射方法有两种：按按行行优先：优先：先行后列先行后列，先存储行号较小的元素，先存储行号较小的元素，行号相同者先存储列号较小的元素。行号相同者先存储列号较小的元素。 按按列列优先：优先：先列后行先列后行，先存储列号

9、较小的元素，先存储列号较小的元素，列号相同者先存储行号较小的元素。列号相同者先存储行号较小的元素。 广义线性表广义线性表多维数组多维数组数组的存储结构与寻址数组的存储结构与寻址二维数组二维数组二维数组二维数组内内 存存二维结构二维结构一维结构一维结构数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义线性表广义线性表多维数组多维数组l2h2 l1h1(a) 二维数组二维数组aij前面的元素个数前面的元素个数=阴影部分的面积阴影部分的面积=整行数每行元素个数整行数每行元素个数+本行中本行中aij前面的元素个数前面的元素个数=( (i - -l1) )( (h2 - -l21

10、) )( (j - -l2) )本行中本行中aij前面的元素个数前面的元素个数每行元素个数每行元素个数整整行行数数aij按行优先存储的寻址按行优先存储的寻址数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义线性表广义线性表多维数组多维数组第第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(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按行优先存

11、储的寻址按行优先存储的寻址按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c 广义线性表广义线性表多维数组多维数组 n（n2）维维数组一般也采用数组一般也采用按行优先和按列按行优先和按列优先两种存储方优先两种存储方法。法。请自行推导请自行推导任一元素存储地任一元素存储地址的计算方法。址的计算方法。数组的存储结构与寻址数组的存储结构与寻址多维数组多维数组数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵

12、的压缩存储矩阵的压缩存储特殊矩阵：特殊矩阵：矩阵中很多值相同的元素并且它们的分布矩阵中很多值相同的元素并且它们的分布有一定的规律。有一定的规律。稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。压缩存储的基本思想是：压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间；存储空间； 对对零零元素元素不分配不分配存储空间。存储空间。 特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 3647862842481697460582957A对称矩阵特

13、点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分的元素。矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义(a) 下三角矩阵下三角矩阵 (b) 存储说明存储说明 (c) 计算方法计算方法aij在一维数组中的序号在一维数组中的序号=阴影部分的面积阴影部分的面积= i( (i+1) )/2+ j+1一维数组下标从一维数组下标从0开始开始aij在一维数组中的下标在一维数组中的下标k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素个数每行元素个数12iaij在本行中

14、的序号在本行中的序号aij第第0行行第第1行行第第i-1行行对称矩阵的压缩存储对称矩阵的压缩存储 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义对于下三角中的元素对于下三角中的元素aij（ij），在数组，在数组SA中的下标中的下标k与与i、j的关系为：的关系为：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因为因为aijaji，则访问和则访问和它对应的元素它对应的元素aji即可，即：即可，即：kj(j1)/2i 。对称矩阵的压缩存储对称矩阵的压缩存储 第第1行行第第n-1行行第第0行行 a00 a10 a11 a20

15、a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-1矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩阵下三角矩阵3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。矩阵的压缩存储

16、矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系：i( (i1) )/2j 当当ijn( (n1) )/2 当当ijk=下三角矩阵的压缩存储下三角矩阵的压缩存储0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22矩阵的压缩存储矩阵的压缩存储存储存储下三角下三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个数据结构（数据结构（C+版）版）广东海洋大学广东海洋

17、大学 谢仕义谢仕义矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： i( (2ni1) )/2ji 当当ijn( (n1) ) /2 当当ijk=上三角矩阵的压缩存储上三角矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主的带状区域中，除了主对角

18、线和它的上下方若干条对对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义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

19、a33 a34a43 a44 0B=sj- -i+1t=i映射到二维数组映射到二维数组B中中(Aij=Bts)， 映射关系为映射关系为对角矩阵的压缩存储（方式一）对角矩阵的压缩存储（方式一）矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义按行按行存储存储 元素元素aij在一维数组中的序号在一维数组中的序号=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一维数组下标从一维数组下标从0开始开始元素元素aij在一维数组中的下标在一维数组中的下标=2i+ j(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数组中压缩到一维

20、数组中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 a44数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义稀疏矩阵的压缩存储稀疏矩阵的压缩存储 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0

21、0 0 0 0 0 0 0 9 0 0 0 0 0A=如何只存储非零元素？如何只存储非零元素？矩阵的压缩存储矩阵的压缩存储注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义template struct element int row, col; /行号，列号行号，列号 T item /非零元素值非零元素值;将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( (行号，列号，非零元素值行号，列号，非零元素值) )三元组三元组矩阵的压缩存储矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩

22、阵的压缩存储 定义三元组定义三元组：数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义三元组表三元组表：将稀疏矩阵的非零元素对应的三元组所将稀疏矩阵的非零元素对应的三元组所构成的集合，构成的集合，按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。矩阵的压缩存储矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储 三元组表三元组表( (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=如何存储三元组表？如何存储三元组

23、表？数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表15 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=矩阵的压缩存储矩阵的压缩存储三元组顺序表是否三元组顺序表是否需要预留存储空间？需要预留存储空间？稀疏矩阵的修改操作稀疏矩阵的修改操作三元组顺序表的插入三元组顺序表的插入/ /删除操作删除操作数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义稀疏矩阵的压

24、缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -1矩阵的压缩存储矩阵的压缩存储15 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（矩阵的

25、列数）（矩阵的列数）数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义存储结构定义：存储结构定义： const int MaxTerm=100; template struct SparseMatrix T dataMaxTerm; /存储非零元素存储非零元素 int mu, nu, tu; /行数，列数，非零元个数行数，列数，非零元个数 ;矩阵的压缩存储矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义三元组顺序表操作三元组顺序表操作转置操作转置操作例：例： 15 0 0 0 9

26、1 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 0 91 0 0 0 0 0A=矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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（矩阵的行数）（矩

27、阵的行数）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（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义三元组顺序表转置算法三元组顺序表转置算法算法算法 基本思想：基本思想：直接取，顺序存直接取，顺序存。即。即在在A的三元组顺序的三元组顺序表中表中依次依次找第找第0列、第列、第1列

28、、列、直到最后一列的三元直到最后一列的三元组，并将找到的每个三元组的行、列交换后组，并将找到的每个三元组的行、列交换后顺序顺序存存储到储到B的三元组顺序表中。的三元组顺序表中。 矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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

29、col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）设置矩阵设置矩阵B的行数、列数、非零元个数的行数、列数、非零元个数数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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

30、 col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第0列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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（矩阵的列数）（

31、矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第1列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456Max

32、Term- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第2列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11 2 1 3数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空

33、空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第3列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储

34、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（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第4列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2

35、6数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第5列非零元，顺序存储到矩阵列非零

36、元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储 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（矩阵的行数）（矩阵的行数）5（

37、矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵A中查找第中查找第6列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义1. 设置转置后矩阵设置转置后矩阵B的行数、列数和非零元个数；的行数、列数和非零元个数；2. 在在B中设置初始存储位置中设置初始存储位置pb；3. for (col=最小列号最小列号; col=最大列号最大列号; col+) 3.1 在在A中查找列号为中查找列号为col的三元组；的三元组；

38、3.2 交换其行号和列号，存入交换其行号和列号，存入B中中pb位置；位置； 3.3 pb+；矩阵的压缩存储矩阵的压缩存储三元组顺序表转置算法三元组顺序表转置算法伪代码伪代码数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义分析分析：A中第中第0列的第一个非零元素一定存储在列的第一个非零元素一定存储在B中下中下标为标为0的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在B中中后面连续的位置上，那么第后面连续的位置上，那么第1列的第一个非零元素在列的第一个非零元素在B中的位置便等于第中的位置便等于第0列的第一个非零元素在列的第一个非零元素在B中的位中的位置

39、加上第置加上第0列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。 基本思想：基本思想：顺序取，直接存。顺序取，直接存。即即在在A中依次取三元中依次取三元组，交换其行号和列号放到组，交换其行号和列号放到B 中中适当适当位置。位置。矩阵的压缩存储矩阵的压缩存储三元组顺序表转置算法三元组顺序表转置算法算法算法如何确定当前从如何确定当前从A中取出的三元组在中取出的三元组在B中的位置？中的位置？数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义矩阵的压缩存储矩阵的压缩存储三元组顺序表转置算法三元组顺序表转置算法算法算法 row col item0123456MaxTerm

40、- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15第第0列第列第1个非零元素个非零元素第第0列有列有2个非零元素个非零元素第第1列第列第1个非零元素个非零元素数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：numnu：存储矩阵存储矩阵A中某列的非零元素的个数；中某列的非零元素的个数；cpotnu：初值表示矩阵初值表示矩阵A中某列的第一个非零元素中某列的第一个非零元素在在B

41、中的位置。中的位置。 数据结构设计：数据结构设计：cpot0=0；cpotcol=cpotcol- -1+numcol- -1； 1colnunum与与cpot存在如下递推关系：存在如下递推关系：矩阵的压缩存储矩阵的压缩存储三元组顺序表转置算法三元组顺序表转置算法算法算法数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 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

42、（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储 col 0 1 2 3 4 5 numcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根据矩阵根据矩阵A计算计算num和和cpot 数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列

43、元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot0cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数

44、）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0 3 0 22cpot3数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01

45、234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5cpot5数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1

46、 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1数据结构（数据结构（C+

47、版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot2cpot4 0 0 15cpo

48、t0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1 2 1 3cpot2cpot1数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234

49、566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）矩阵的压缩存储矩阵的

50、压缩存储将矩阵将矩阵A中中col列元素存放在列元素存放在B中下标为中下标为cpotcol的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot4 0 0 15cpot0 3 0 22 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3 0 4 91cpot0数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义1. 设置转置后矩阵设置转置后矩阵B的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；2. 计算计算A中每一列的非零元素个数

51、；中每一列的非零元素个数；3. 计算计算A中每一列的第一个非零元素在中每一列的第一个非零元素在B中的下标；中的下标；4. 依次取依次取A中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组； 4.1 确定该元素在确定该元素在B中的下标中的下标pb； 4.2 将该元素的行号列号交换后存入将该元素的行号列号交换后存入B中中pb的位置；的位置； 4.3 预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；矩阵的压缩存储矩阵的压缩存储三元组顺序表转置算法三元组顺序表转置算法伪代码伪代码数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义采用采用链

52、接链接存储结构存储三元组表，每个非零元素对应存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：的三元组存储为一个链表结点，结构为： rowcolitemdownrightrow：存储非零元素的行号存储非零元素的行号col：存储非零元素的列号存储非零元素的列号item：存储非零元素的值存储非零元素的值right：指针域，指向同一行中的下一个三元组指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组指针域，指向同一列中的下一个三元组矩阵的压缩存储矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表数据结构（数据结构（C+版）版）广东海

53、洋大学广东海洋大学 谢仕义谢仕义 2 0 2M=3 0 0 50 1 0 02 0 0 0矩阵的压缩存储矩阵的压缩存储 0 0 3 0 3 5 1 1 1稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义表：广义表：n（n0）个数据元素的有限序列，记作：个数据元素的有限序列，记作： LS(a1，a2，an)其中：其中：LS是广义表的名称，是广义表的名称，ai（1in）是是LS的成员的成员（或直接元素），（或直接元素），它可以是单个的数据元素它可以是单个的数据元素，也可以也可以是一个广义表是一个广义表，分别称为，分别称为

54、LS的的单元素（或原子）单元素（或原子）和和子子表表。 广义线性表广义线性表广义表广义表广义表的逻辑结构：直接元素之间是线性关系。广义表的逻辑结构：直接元素之间是线性关系。广义表的基本概念广义表的基本概念通常用大写字母表示广义表，用小写字母表示单元素。通常用大写字母表示广义表，用小写字母表示单元素。 数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义长度：长度：广义表广义表LS中的直接元素的个数；中的直接元素的个数；深度：深度：广义表广义表LS中括号的最大嵌套层数。中括号的最大嵌套层数。表头：表头：广义表广义表LS非空时，称第一个元素为非空时，称第一个元素为LS的表头；的表

55、头；表尾：表尾：广义表广义表LS中除表头外其余元素组成的广义表。中除表头外其余元素组成的广义表。广义线性表广义线性表广义表广义表广义表广义表( )( )和广义表和广义表( )( )有什么不同？有什么不同？ 广义表的基本概念广义表的基本概念数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义A ( )B (e)C (a, (b，c，d)D (A, B, C) E (a, E)F ( )广义线性表广义线性表广义表广义表广义表的示例广义表的示例长度？深度？表头？表尾？长度？深度？表头？表尾？数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义A ( )B (e)C

56、 (a, (b，c，d)D (A, B, C) E (a, E)F ( )广义线性表广义线性表广义表广义表广义表的图形表示广义表的图形表示ABeCabcdD数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义线性表广义线性表广义表广义表广义表可以采用顺序存储结构吗？广义表可以采用顺序存储结构吗？由于广义表中的数据元素的类型不统一，因此难以由于广义表中的数据元素的类型不统一，因此难以采用顺序存储结构来存储。采用顺序存储结构来存储。 若广义表不空，则可分解为表头和表尾；反之，一若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。对确定的表头和表尾可唯一地确定一个广义表。 采用头尾表示法存储广义表采用头尾表示法存储广义表 如何采用链接存储结构存储广义表？如何采用链接存储结构存储广义表？数据结构（数据结构（C+版）版）广东海洋大学广东海洋大学 谢仕义谢仕义广义表的存储结构广义表的存储结构头尾表示法头尾表示法广义线性表广义线性表广义表广义表广义表中的数