数组和特殊矩阵.ppt

《数组和特殊矩阵.ppt》由会员分享，可在线阅读，更多相关《数组和特殊矩阵.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数组和特殊矩阵现在学习的是第1页，共42页数组的基本概念（数组的基本概念（P65）oo数组的定义数组的定义数组的定义数组的定义n n数组是由一组类型相同的数据元素构成的有序集合，每个数组是由一组类型相同的数据元素构成的有序集合，每个数组是由一组类型相同的数据元素构成的有序集合，每个数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受数据元素称为一个数组元素（简称为元素），每个元素受数据元素称为一个数组元素（简称为元素），每个元素受数据元素称为一个数组元素（简称为元素），每个元素受n n(n n1)1)个线性关系的约束，每个元素在个线性关系的约束，

2、每个元素在个线性关系的约束，每个元素在个线性关系的约束，每个元素在n n个线性关系中的序号个线性关系中的序号个线性关系中的序号个线性关系中的序号i i1 1、i i2 2、i in n称为该元素的下标，并称该数组为称为该元素的下标，并称该数组为称为该元素的下标，并称该数组为称为该元素的下标，并称该数组为 n n 维数组。维数组。维数组。维数组。oo数组的特点数组的特点数组的特点数组的特点n n元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；n n数组是一个具有固定格式

3、和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。现在学习的是第2页，共42页 a11 a12 a1n a21 a22 a2n am1 am2 amnA=A=(A1，A2，An)其中：其中：Ai=(a1i，a2i，ami)(1in)数组数组线性表的推广线性表的推广二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。数组的基本概念数组的基本概念现在学习的是第3页，共42页设设设设一一一一维维维维数数数数组组组组的的的的下下下下标标标标的的的的范范范范围围围围为为为为闭闭闭闭区区区区间间间间

4、l l，h，每每个个数数组组元元素素占占用用 c c 个个个个存存存存储储储储单单单单元元元元，则则则则其其其其任任任任一一一一元元元元素素素素 a ai i 的的的的存存存存储储储储地地地地址址址址可可可可由下式确定：由下式确定：由下式确定：由下式确定：Loc(Loc(a ai i)Loc(Loc(a al l)(il l)c c c al ai-1 ai ah al+1 Loc(al)Loc(ai)数组的存储结构数组的存储结构一维数组一维数组(P66)现在学习的是第4页，共42页常用的映射方法有两种：常用的映射方法有两种：常用的映射方法有两种：常用的映射方法有两种：按按按按行行行行优先：优

5、先：优先：优先：先行后列先行后列先行后列先行后列，先存储行号较小的元素，行号相，先存储行号较小的元素，行号相，先存储行号较小的元素，行号相，先存储行号较小的元素，行号相同者先存储列号较小的元素。同者先存储列号较小的元素。同者先存储列号较小的元素。同者先存储列号较小的元素。按按按按列列列列优先：优先：先列后行先列后行先列后行先列后行，先存储列号较小的元素，列号相，先存储列号较小的元素，列号相，先存储列号较小的元素，列号相，先存储列号较小的元素，列号相同者先存储行号较小的元素。同者先存储行号较小的元素。同者先存储行号较小的元素。同者先存储行号较小的元素。二维数组二维数组内内 存存二维结构二维结构一

6、维结构一维结构数组的存储结构数组的存储结构二维数组二维数组二维数组二维数组现在学习的是第5页，共42页特殊矩阵的压缩存储特殊矩阵的压缩存储o特殊矩阵：特殊矩阵：包括对称矩阵、三角矩阵、对角包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。矩阵和稀疏矩阵等。o稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。o压缩存储压缩存储的基本思想是：的基本思想是：n n为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；n n对零元素不分配存储空间。对零元素不分配存储空间。对零元素不分配存储空间。对零

7、元素不分配存储空间。现在学习的是第6页，共42页3647862842481697460582957A对称矩阵特点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分的元素。只存储下三角部分的元素。只存储下三角部分的元素。特殊矩阵的压缩存储特殊矩阵的压缩存储对称阵对称阵现在学习的是第7页，共42页对于下三角中的元素对于下三角中的元素对于下三角中的元素对于下三角中的元素a aij ij（i j j），在数组），在数组），在数组），在数组SASA中的下标中的下标k k与与i i、j的关系为：的关系为：k ki(i1)/21)/2j j。上三角中的元素上三

8、角中的元素上三角中的元素上三角中的元素aij ij（i ij j），因为），因为a aij ija aji ji，则访问和它对应，则访问和它对应，则访问和它对应，则访问和它对应的元素的元素的元素的元素a aji即可，即：即可，即：k kj j(j1)/21)/2i i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-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-1特殊矩阵的压缩存储特殊矩阵的压缩存储对称阵对称阵现在学习的是第8页，共42页3 cc

9、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(b)b)上三角矩阵上三角矩阵上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵三角阵三角阵现在学习的是第9页，共42页矩阵中任一元素矩阵中任一元素矩阵中任一元素矩阵中任一元素a aij在在在在数组数组数组数组中的下标中的下标中的下标中的下标k k与与与与i、j j的对应关系：的对应

10、关系：i(i1)/2j 当当ijn(n1)/2 当当ijk=0 0 1 1 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存储存储下三角下三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵现在学习的是第10页，共42页矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k k与与

11、与与i i、j j的对应关系：的对应关系：i(2ni1)/2ji 当当ijn(n1)/2 当当ijk=存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵现在学习的是第11页，共42页对角矩阵：对角矩阵：对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心的所有非零元素都集中在以主对角线为中心的带状区域中，除了主带状区域中，除了主对角线和它的上下方若干条对角线对角线和它的上下方若干条对角线对角线和它的上下方若干条对角线对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。的元素外，所有其他元素都为零。的元素外，所

12、有其他元素都为零。的元素外，所有其他元素都为零。a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵对角矩阵对角矩阵现在学习的是第12页，共42页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 a34a43 a44 0B

13、=sj-i+1t=i映射到二维数组映射到二维数组B中，映射关系中，映射关系特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵现在学习的是第13页，共42页按行按行存储存储 元素元素元素元素a aij ij在一维数组中的序号在一维数组中的序号在一维数组中的序号在一维数组中的序号=2+3=2+3(i i1 1)+(j ji i+2+2)=2=2i+ji+j+1+1 一维数组下标从一维数组下标从一维数组下标从一维数组下标从0 0开始开始开始开始元素元素元素元素a aij ij在一维数组中的下标在一维数组中的下标在一维数组中的下标在一维数组中的下标=2=2i+ji+j(b)寻址的计算方法寻址的计算方

14、法(c)压缩到一维数组中压缩到一维数组中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特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵对角矩阵对角矩阵现在学习的是第14页，共42页15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0

15、 9 0 0 0 0 0A=如何只存储非零元素？如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵现在学习的是第15页，共42页（1 1 1 1）三元组顺序表（）三元组顺序表（）三元组顺序表（）三元组顺序表（P69P69）将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素

16、值行号，列号，非零元素值行号，列号，非零元素值行号，列号，非零元素值)三元组三元组三元组三元组（2）十字链表（）十字链表（）十字链表（）十字链表（P72P72）采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：结构为：结构为：结构为：稀疏矩阵的压缩存储稀疏矩阵的压缩存储rowcolitemdownright现在学习的是第16页，共42页例：例：

17、例：例：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 0 91 0 0 0 0 0A=三元组顺序表操作三元组顺序表操作转置操作转置操作现在学习的是第17页，共42页 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（矩阵的列数）（矩阵的列

18、数）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（非零元个数）（非零元个数）三元组顺序表操作三元组顺序表操作三元组顺序表操作三元组顺序表操作转置操作转置操作转置操作转置操作现在学习的是第18页，共42页三元组顺序表操作三元组顺序表操作转置算法转置算法1o基本思想：基本思想：在在A的三元组顺序表中依次找第的三元组顺序表中依次找第0列、第列、第1列、列、直到最后一列的

19、三元组，直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序并将找到的每个三元组的行、列交换后顺序存储到存储到B的三元组顺序表中。的三元组顺序表中。现在学习的是第19页，共42页 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（非零元个数）（非

20、零元个数）三元组顺序表操作三元组顺序表操作转置算法转置算法1 1现在学习的是第20页，共42页 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 A中查找第中查找第中查找第中查找第0 0列非零元，顺序

21、存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 0 0 15 0 0 15 0 4 91 0 4 91现在学习的是第21页，共42页 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（非零元个数）（非零元

22、个数）0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第1 1列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中现在学习的是第22页，共42页 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 item0

23、123456MaxTerm-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列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中现在学习的是第23页，共42页 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col ite

24、m0123456MaxTerm-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 22 3 2 6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第3 3列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到

25、矩阵B B中中中中现在学习的是第24页，共42页 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 2

26、6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第4 4列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 3 0 22 3 0 22现在学习的是第25页，共42页 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（矩阵的行

27、数）（矩阵的行数）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 B中中中中现在学习的是第26页，共42页 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空

28、闲闲 闲闲 闲闲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 22 3 2 6 3 2 6 5 0 -15 5 0 -15在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第6 6列非零元，顺序存储到矩

29、阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中现在学习的是第27页，共42页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中查找列号为中查找列号为中查找列

30、号为中查找列号为colcol的三元组；的三元组；的三元组；的三元组；3.2 3.2 交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入B B中中中中q q位置；位置；位置；位置；3.3 3.3 q+q+；三元组顺序表操作三元组顺序表操作转置算法转置算法转置算法转置算法1现在学习的是第28页，共42页三元组顺序表操作三元组顺序表操作转置算法转置算法1oo该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在colcol和和和和p p的两重循环上。的两重循环上。的两重循环上。的两重循环上。oo对于一个对于一个对于一个对

31、于一个mm行行行行n n列且非零元素个数为列且非零元素个数为列且非零元素个数为列且非零元素个数为t t的稀疏矩阵而言，该的稀疏矩阵而言，该的稀疏矩阵而言，该的稀疏矩阵而言，该算法的时间复杂度为算法的时间复杂度为算法的时间复杂度为算法的时间复杂度为O O(tntn)。oo最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数t t与与与与mnmn同数量级同数量级同数量级同数量级时，上述算法的时间复杂度就为时，上述算法的时间复杂度就为时，上述算法的时间复杂度就为时，上述算法的时间复杂度就为O O(mn

32、mn2)2)。oo显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。现在学习的是第29页，共42页分析分析：A A中第中第中第中第0 0列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在B B中下标中下标为为0的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在B B中后面连中后面连中后面连中后面连续的位置上，那么第续的位置上，那么第续的位置上，那么第续的位置上，那么第1 1列的第一个非零元素在列的第一个非零元素在列的第

33、一个非零元素在列的第一个非零元素在B B中的位置便等中的位置便等中的位置便等中的位置便等于第于第于第于第0 0列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在B B中的位置加上第中的位置加上第0列的非零列的非零元素的个数，以此类推。元素的个数，以此类推。基本思想：基本思想：基本思想：基本思想：顺序取，直接存。顺序取，直接存。顺序取，直接存。顺序取，直接存。即即在在在在A中依次取三元组，交中依次取三元组，交中依次取三元组，交中依次取三元组，交换其行号和列号放到换其行号和列号放到换其行号和列号放到换其行号和列号放到B B 中中中中适当适当位置。位置。位置。位置。如何

34、确定当前从如何确定当前从A中取出的三元组在中取出的三元组在B中的位置？中的位置？三元组顺序表操作三元组顺序表操作转置算法转置算法转置算法转置算法2 2现在学习的是第30页，共42页 row col itemrow col item0 01 12 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

35、 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15第第0列第列第1个非零元素个非零元素第第0列有列有2个非零元素个非零元素第第1列第列第1个非零元素个非零元素三元组顺序表操作三元组顺序表操作转置算法转置算法2 2现在学习的是第31页，共42页引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：cnumcolscnumcols：存储矩阵：存储矩阵：存储矩阵：存储矩阵A A中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；cpotclos：初值表示矩阵

36、：初值表示矩阵：初值表示矩阵：初值表示矩阵A A中某列的第一个非零元素在中某列的第一个非零元素在中某列的第一个非零元素在中某列的第一个非零元素在B中的位置。中的位置。中的位置。中的位置。数据结构设计：数据结构设计：cpot0=0cpot0=0；cpotcol=cpotcolcpotcol=cpotcol-1+cnumcol1+cnumcol-11；1col1colcols-1cols-1cnum与与与与cpotcpot存在如下递推关系：存在如下递推关系：存在如下递推关系：存在如下递推关系：三元组顺序表操作三元组顺序表操作转置算法转置算法转置算法转置算法2现在学习的是第32页，共42页 0 0

37、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 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 现在学习的是第33页，共42页 0

38、 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中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item0123456

39、6 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot0cpot0cpot1cpot1cpot2cpot2cpot3cpot3cpot4 cpot5cpot4 cpot5 0 0 15 0 0 15cpot0cpot0现在学习的是第34页，共42页 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（矩阵的

40、行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot3cpot3cpot4 cpot5cpot4 cpot5 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3

41、cpot3现在学习的是第35页，共42页 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中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的

42、位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5cpot5cpot5现在学习的是第36页，共42页 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 空空空

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

44、pot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11cpot1cpot1现在学习的是第37页，共42页 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

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

46、1现在学习的是第38页，共42页 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中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 r

47、ow 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 -15cpot5cpot5 1 1 11 1 1 11 2 1 3 2 1 3cpot2cpot2cpot1cpot1 3 2 6 3 2 6cpot3cpot3现在学习的是第39页，共42页 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

48、 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（非零元个数）（非零元个数）cpot4cpot4

49、0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11 2 1 3 2 1 3cpot2cpot2cpot1cpot1 3 2 6 3 2 6cpot3cpot3 0 4 91 0 4 91cpot0cpot0现在学习的是第40页，共42页1.设置转置后矩阵设置转置后矩阵B B的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；2.2.计算计算计算计算A A中每一列的非零元素个数；中每一列的非零元素个数；中每一列的非零元素个数；

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