第4章广义线性表-1

1、1第第4章章 广义广义线性表线性表多维数组和广义表多维数组和广义表本章的基本内容是：本章的基本内容是：数组的逻辑结构特征数组的逻辑结构特征数组的存储方式及寻址方法数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构广义表的基本概念和存储结构2线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除位置线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操

2、作的线性表。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特殊线性表特殊线性表3线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广义线性表广义线性表（多维）数组（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。广义表广义表线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且元素的类型可以不相同。且元素的类型可以不相同

3、。44.1 多维数组多维数组多维数组的知识点组织结构图多维数组的知识点组织结构图多维数组的逻辑结构多维数组的逻辑结构数组的定义数组的定义数组的数组的ADT定义定义数组的存储结构数组的存储结构顺序存储顺序存储行优先行优先列优先列优先压缩存储压缩存储特殊矩阵特殊矩阵稀疏矩阵稀疏矩阵5数组的定义数组的定义数组是由一组数组是由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集合，每个数据元素称为一个数组元素（简称为元合，每个数据元素称为一个数组元素（简称为元素），每个元素受素），每个元素受n n( (n n1)1)个个线性关系线性关系的约束，每的约束，每个元素在个元素在n n个线性关系中

4、的序号个线性关系中的序号i i1 1、i i2 2、i in n称称为该元素的下标，并称该数组为为该元素的下标，并称该数组为 n n 维数组。维数组。 数组的特点数组的特点元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。6 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a a2222受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有一个行前驱一个行前驱a a2121和一个行后继和一个行后继a a2323，在列上有一个列

5、，在列上有一个列前驱前驱a a1212和和一个列后继和和一个列后继a a3232。数组示例数组示例7 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)数组数组线性表的推广线性表的推广二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。8数组的基本操作数组的基本操作在数组中插入（或）一个元素有意义吗？在数组中插入（或）一个元素有意义吗？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=将元素将元素 x x 插入插入到数组中第到数组中第1 1

6、行第行第2 2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=删除数组中删除数组中第第1 1行第行第2 2列元素。列元素。9数组的基本操作数组的基本操作 存取（读）：给定一组下标，读出对应的数组存取（读）：给定一组下标，读出对应的数组元素；元素； 修改（写）：给定一组下标，存储或修改与其修改（写）：给定一组下标，存储或修改与其相对应的数组元素。相对应的数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？适合采用顺序存储。适合采用顺序存储。数组的数组的ADTADT定义（教材

7、定义（教材P116)P116)10数组的存储结构与寻址数组的存储结构与寻址一维数组一维数组设一维数组的设一维数组的下标的范围下标的范围为闭区间为闭区间l l，h h，每个，每个数组元素占用数组元素占用 c c 个存储单元，则其个存储单元，则其任一元任一元素素 a ai i 的的存储地址可由下式确定：存储地址可由下式确定： Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)11常用的映射方法有两种：常用的映射方法有两种：按按行行优先：优先：先行后列先行后列，先存储行号较小的元素，先存储行号较小的元素，行号相同者先存储列号较小的元素。行号

8、相同者先存储列号较小的元素。 按按列列优先：优先：先列后行先列后行，先存储列号较小的元素，先存储列号较小的元素，列号相同者先存储行号较小的元素。列号相同者先存储行号较小的元素。 二维数组二维数组内内 存存二维结构二维结构一维结构一维结构数组的存储结构与寻址数组的存储结构与寻址二维数组二维数组12l2h2 l1h1(a) (a) 二维数组二维数组aij前面的元素个数前面的元素个数= =整行数整行数每行元素个数每行元素个数+ +本行中本行中aij前面的元素个数前面的元素个数=( (i - -l1) )( (h2 - -l21) )( (j - -l2) )本行中本行中a aijij前面的元素个数前

9、面的元素个数每行元素个数每行元素个数整整行行数数aij按行优先存储的寻址按行优先存储的寻址13按行优先存储的寻址按行优先存储的寻址第第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按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。a(0,0)a(0,1)a(0,3)a(1,0)a(1,1)a(1,3)a(3

10、,2)a(6,0)a(6,3) 012 3例例1 1：如何求出：如何求出的存储地址？的存储地址？要事先确定：要事先确定：是行优先方式还是列优先方式？是行优先方式还是列优先方式？数组的首地址是多少？数组的首地址是多少？每个元素的长度？每个元素的长度？否则无法否则无法求出结果求出结果15111101121202111101101000mnananamaaamaaamaaaa设数组开始存放位置设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用每个元素占用 l 个存储单元个存储单元 则则aij的存储地址：的存储地址： LOC ( i, j ) = a + ( j *n +i ) * l

11、按列优先存储的寻址按列优先存储的寻址例例2：例例3 3：一个二维数组：一个二维数组A A，行下标的范围是，行下标的范围是1 1到到6 6，列下标的，列下标的范围是范围是0 0到到7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，存个字节存储，存储器按字节编址。那么，这个数组的体积是储器按字节编址。那么，这个数组的体积是 个字节。个字节。 288288答：答： Volume=mVolume=m* *n n* *L=(6-1L=(6-1+1+1) )* *(7- 0 (7- 0 +1+1) )* *6=486=48* *6=2886=288例例4 4：已知二维数组：已知二维数组A

12、 Am,mm,m按行存储的元素地址公式是：按行存储的元素地址公式是： Loc(aLoc(aijij)= Loc(a)= Loc(a1111)+(i-1)+(i-1)* *m+(j-1)m+(j-1)* *K , K , 请问请问按列存储的公式相同吗？按列存储的公式相同吗？答：尽管是方阵，但公式仍不同。应为：答：尽管是方阵，但公式仍不同。应为： Loc(aLoc(aijij)=Loc(a)=Loc(a1111)+(j-1)+(j-1)* *m+(i-1)m+(i-1)* *K K 例例5 5 ：设数组：设数组a1a160, 160, 17070的基地址为的基地址为20482048，每个，每个元素

13、占元素占2 2个存储单元，若以列序为主序顺序存储，则元个存储单元，若以列序为主序顺序存储，则元素素a32,58a32,58的存储地址为的存储地址为 。根据列优先公式根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：请注意审题！答：请注意审题！想一想：若数组是想一想：若数组是a059, 069，结果是否仍为结果是否仍为8950？维界虽未变，但此时的维界虽未变，但此时的a32, 58不再是原来的不再是原来的a32, 5819 n（n2）维数组一般维数组一般也采用按行优先和按列也

14、采用按行优先和按列优先两种存储方法。优先两种存储方法。（1 1）按行优先：最右边）按行优先：最右边的下标先变化，即最右的下标先变化，即最右边下标从小到大，循环边下标从小到大，循环一遍后，右边第一遍后，右边第2 2个下标个下标再变，再变，最后是最左，最后是最左下标。下标。（2 2）按列优先：）按列优先：P118P118数组的存储结构与寻址数组的存储结构与寻址多维数组多维数组三维数组且列优三维数组且列优先时的元素地址先时的元素地址要会计算！要会计算！例例6 6：假设有三维数组假设有三维数组A A7 79 98 8，每个元素用相邻的，每个元素用相邻的6 6个个字节存储，存储器按字节编址。已知字节存储

15、，存储器按字节编址。已知A A的起始存储位的起始存储位置（基地址）为置（基地址）为10001000，末尾元素，末尾元素A687A687的第一的第一个字节地址为多少？若按个字节地址为多少？若按列优先（高地址优先）列优先（高地址优先）存存储时，元素储时，元素A476A476的第一个字节地址为多少？的第一个字节地址为多少？ 答：答： 末尾元素末尾元素A687A687的第的第1 1个字节地址个字节地址 1000 +(798)66=4018 按高地址优先存储时，元素按高地址优先存储时，元素A476A476的第的第1 1个字节个字节地址地址? ?A476=1000+(7 9 6) 6+(7 7+4 ) 6

16、=3586214.2 矩阵的压缩存储矩阵的压缩存储特殊矩阵：特殊矩阵：矩阵中很多值相同的元素并且它们的分布矩阵中很多值相同的元素并且它们的分布有一定的规律。有一定的规律。稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。压缩存储的基本思想是：压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间；存储空间； 对对零零元素元素不分配不分配存储空间。存储空间。 特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵22特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 3647862842481697460582957A对称矩阵特点对称矩阵特点：aij=aji如何压缩存

17、储？如何压缩存储？只存储下三角（或上三角）部分的元素。只存储下三角（或上三角）部分的元素。23特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 (a) (a) 下三角矩阵下三角矩阵 (b) (b) 存储说明存储说明 (c) (c) 计算方法计算方法一维数组下标从一维数组下标从0开开始始aij在一维数组中的下在一维数组中的下标标k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素个数每行元素个数12iaij在本行中的序号在本行中的序号aij第第0行行第第1行行第第i-1行行24特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 对于对于下三角中的元素下三

18、角中的元素aij（ij），），在数组在数组SASA中的下标中的下标k与与i、j的关系为的关系为：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因为因为aijaji，则访问和则访问和它对应的元素它对应的元素aji即可，即即可，即：kj(j1)/2i 。第第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 k n(n+1)/2-125特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5

19、 7(a)(a)下三角矩阵下三角矩阵3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)(b)上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。26下三角矩阵的压缩存储下三角矩阵的压缩存储矩阵中任一元素矩阵中任一元素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行行

20、c a22存储存储下三角下三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个27上三角矩阵的压缩存储上三角矩阵的压缩存储矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： i( (2ni1) )/2ji 当当ijn( (n1) ) /2 当当ijk=存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个28特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对的带状区域中，除了主

21、对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=29特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 按行按行存储存储 元素元素aij在一维数组中的序号在一维数组中的序号 一维数组下标从一维数组下标从0开始开始元素元素aij在一维数组中的下标在一维数组中的下标=2 + 3(i1)+( ji + 1)=2i+ j(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数组中压缩到一维数组中a00 a01 a

22、10 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 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 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、。template struct element int row, col; /行号，列号行号，列号 T item /非零元素值非零元素值;将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( (行号，列号，非零元素值行号，列号，非零元素值) )三元组三元组定义三元组定义三元组： 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 三元组表三元组表：将稀疏矩阵的非零元素对应的三元组所将稀疏矩阵的非零元素对应的三元组所构成的集合，构成的集合，按按行优先行优先的顺序排列成一个线性表。的顺序排列成一个线性表。三元组表三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9

24、) )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=如何存储三元组表？如何存储三元组表？ 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表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=三元组顺序表是否三元组顺序表是否需要预留存储空间？需要预留存储空间？稀疏矩阵的修改操作稀疏矩阵的修改操作三元组顺序表的插入三元组顺序表的插

25、入/ /删除操作删除操作采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表 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（矩阵的列数）（矩阵的列数）稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表

26、三元组顺序表存储结构定义：存储结构定义： const int MaxTerm=100; struct SparseMatrix element dataMaxTerm; /存储非零元素存储非零元素 int mu, nu, tu; /行数，列数，非零元个数行数，列数，非零元个数 ;稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表三元组顺序表操作三元组顺序表操作转置操作转置操作例：例： 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

27、0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元组顺序表操作三元组顺序表操作转置操作转置操作 A第第1 1列列第第2 2列列 第第3 3列列第第4 4列列 第第5 5列列第第6 6列列 第第7 7列列 . . B B第第1 1行行第第2 2行行 第第3 3行行第第4 4行行 第第5 5行行第第6 6行行 第第7 7行行 . .0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0

28、 -70 0 14 0 0 00 0 0 0 0 0(0, 1, 12)(0, 2, 9 )(2, 0, -3)(2, 4, 14)(3, 2, 24)(4, 1, 18)(5, 0, 15)(5, 3, -7)(0, 2, -3)(0, 5, 15)(1, 0, 12)(1, 4, 18)(2, 0, 9)(2, 3, 24)(3, 5, -7)(4, 2, 14)已知已知三三元元组组顺顺序序表表A.data求求三三元元组组顺顺序序表表B.data转置后转置后AB目的：目的：答：肯定不正确！答：肯定不正确！除了：除了： （1 1）每个元素的行下标和列下标互换（即）每个元素的行下标和列下标互换

29、（即三元组中的三元组中的i i和和j j互换互换）；）；还需要：还需要：（2 2）T T的总行数的总行数mumu和总列数和总列数nunu也要也要互换；互换； 若采用三元组顺序表，只要把每个元素的若采用三元组顺序表，只要把每个元素的行行下标和列下标互换下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 提问：提问：矩阵 B矩阵 A（3 3）重排重排三元组顺三元组顺序表内各元素顺序序表内各元素顺序，使转置后的三元，使转置后的三元组顺序表也按行（组顺序表也按行（或列）为主序有规或列）为主序有规律的排列。律的排列。( (B.dataB.data

30、相对矩阵相对矩阵B B来说仍以行序为主来说仍以行序为主序序进行排列，即进行排列，即相相对对A A按列序为主序按列序为主序进进行排列，即按列号行排列，即按列号从小到大，列号一从小到大，列号一样的按行号从小到样的按行号从小到大进行排列大进行排列) )(0, 1, 12)(0, 2, 9 )(2, 0, -3)(2, 4, 14)(3, 2, 24)(4, 1, 18)(5, 0, 15)(5, 3, -7)(0, 2, -3)(0, 5, 15)(1, 0, 12)(1, 4, 18)(2, 0, 9)(2, 3, 24)(3, 5, -7)(4, 2, 14)除了：除了： （1 1）每个元素的行

31、下标和列下标互换（即三元组中的）每个元素的行下标和列下标互换（即三元组中的i i和和j j互换互换）；）；还需要：（还需要：（2 2）B B的总行数的总行数mumu和总列数和总列数nunu也要也要互换；互换； （3 3）重排重排三元组顺序表内各元素顺序三元组顺序表内各元素顺序，使转置后的三元，使转置后的三元组顺序表也按行（或列）为主序有规律的排列。组顺序表也按行（或列）为主序有规律的排列。( ( B.dataB.data相对矩阵相对矩阵B B来说仍以行序为主序进行排列，来说仍以行序为主序进行排列，即相对即相对A A按列序为主序进行排列，即按列号从小到按列序为主序进行排列，即按列号从小到大，列号

32、一样的按行号从小到大进行排列大，列号一样的按行号从小到大进行排列) )上述（上述（1 1）和（）和（2 2）容易实现，）容易实现，难点在（难点在（3 3）。有两种实现有两种实现转置的方法转置的方法反复扫描反复扫描A A表，顺序存表，顺序存扫描一次扫描一次A A表，直接存表，直接存三元组顺序表转置算法三元组顺序表转置算法算法算法 基本思想：基本思想：反复扫描反复扫描A A表，顺序存表，顺序存。即。即在在A A的三元组的三元组顺序表中顺序表中依次依次找第找第0 0列、第列、第1 1列、列、直到最后一列的直到最后一列的三元组，并将找到的每个三元组的行、列交换后三元组，并将找到的每个三元组的行、列交换

33、后顺顺序序存储到存储到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（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）设置矩阵设置矩阵B B的行数、列数、非零元个数的行数、列数、非零元个数 0 0 15 0 3 22

34、 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列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中 0 0 15 0 4 91 0 0 15 0 3 22 0 5 - -15 1 1 11

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

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

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

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

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

40、 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中查找第中查找第6 6列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15

41、算法算法I I的的C+C+描述不做要求描述不做要求三元组顺序表转置算法三元组顺序表转置算法时间复杂度时间复杂度分析该算法的时间复杂度：分析该算法的时间复杂度：对三元组顺序表对三元组顺序表A A扫描多少趟？扫描多少趟？共扫描列数共扫描列数nunu趟趟某趟（假设为第某趟（假设为第colcol趟）扫描的操作是什么？趟）扫描的操作是什么？查找列号为查找列号为colcol的三元组，行列号交换后存储到的三元组，行列号交换后存储到B B表中表中算法算法I I的时间复杂度为的时间复杂度为O(nuO(nu* *tutu) ), ,与常规存储方式下与常规存储方式下矩阵转置算法（矩阵转置算法（O(nuO(nu* *

42、mu)mu)）相比，当）相比，当tutumumu时，算时，算法的时间性能更差一些。法的时间性能更差一些。分析分析：A A表中第表中第0 0列的第一个非零元素一定存储在列的第一个非零元素一定存储在B B表表中下标为中下标为0 0的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在B B表中后面连续的位置上，那么第表中后面连续的位置上，那么第1 1列的第一个非零列的第一个非零元素在元素在B B表中的位置便等于第表中的位置便等于第0 0列的第一个非零元素列的第一个非零元素在在B B表中的位置加上第表中的位置加上第0 0列的非零元素的个数，以此列的非零元素的个数，以此类推。类推。

43、基本思想：基本思想：扫描一次扫描一次A A表，直接存。表，直接存。即即在在A A表中依次表中依次取三元组，交换其行号和列号放到取三元组，交换其行号和列号放到B B 表中表中适当适当位置。位置。三元组顺序表转置算法三元组顺序表转置算法算法算法如何确定当前从如何确定当前从A A表中取出的三元组在表中取出的三元组在B B表中的位表中的位置？置？关键：关键：怎样寻找怎样寻找B B表中的表中的“恰当恰当”位置？位置？如果能如果能预知预知A矩阵矩阵每一列每一列( (即即B的每一行的每一行) )的的非零元素个非零元素个数数，又能很快得知，又能很快得知每列第一个非零元素每列第一个非零元素在在B B表中的表中的

44、位置位置, ,则扫描则扫描A表表时便可以将每个元素准确定位时便可以将每个元素准确定位( (因已知若干因已知若干参考点参考点) )请注意请注意A A表特征表特征：每列首个非零元素必定先被扫描到。：每列首个非零元素必定先被扫描到。技巧：技巧：为实现转置运算，应当按列生成为实现转置运算，应当按列生成A A矩阵的矩阵的两个辅两个辅助数组助数组，让它携带每列的非零元素个数，让它携带每列的非零元素个数 num(inum(i) ) 以及每以及每列的第一个非零元素在三元组表中的位置列的第一个非零元素在三元组表中的位置cpot(icpot(i) ) 等信等信息。息。引入两个数组作为辅助数据结构：引入两个数组作为

45、辅助数据结构：numnunumnu ：存储矩阵：存储矩阵A A中某列的非零元素的个数；中某列的非零元素的个数；cpotnucpotnu ：初值初值表示矩阵表示矩阵A A中某列的第一个非零元中某列的第一个非零元素在素在B B中的位置。中的位置。 数据结构设计：数据结构设计：cpot0=0cpot0=0；cpotcolcpotcol=cpotcol-1+numcol-1=cpotcol-1+numcol-1；1col1colnununumnum与与cpotcpot存在如下递推关系：存在如下递推关系：三元组顺序表转置算法三元组顺序表转置算法算法算法讨论：讨论：求出求出按列优先按列优先的的辅助数组辅助

46、数组后，后，如何实现快速转置？如何实现快速转置？col012345numcol222110cpotcol0计算式：计算式： cpot(0)0cpotcol cpotcol-1 + numcol-1 2 4 6 7 80 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0Mcol 0 1 2 3 4 5三三元元组组表表A(5, 3, -7)(5, 0, 15)(4, 1, 18)(3, 2, 24)(2, 4, 14)(2, 0, -3)(0, 2, 9 )(0, 1, 12)col p1234想一想：是

47、从原始矩阵想一想：是从原始矩阵A A中统计中统计numcol方便些，还是从对应的三元组顺序表方便些，还是从对应的三元组顺序表A A中中统计更方便？统计更方便？ 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（非零元个数）（非零元个数） col 0 1 2 3 4 5 numcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根据矩阵根据矩阵A A的三元组顺序表计算的三元

48、组顺序表计算numnum和和cpotcpot 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 A中中colcol列元素存放在列元素存放在B B中下标为中下标为cpotcolcpotcol 的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot0cpot1cpot2cpot3

49、cpot4 cpot5 0 0 15cpot0 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 A中中colcol列元素存放在列元素存放在B B中下标为中下标为cpotcolcpotcol 的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2cpot3cpot

50、4 cpot5 0 0 15cpot0 3 0 22cpot3 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 A中中colcol列元素存放在列元素存放在B B中下标为中下标为cpotcolcpotcol 的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2c

51、pot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5cpot5 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 A中中colcol列元素存放在列元素存放在B B中下标为中下标为cpotcolcpotcol 的位置的位置 row col item01234566（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1 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（非零元个数）（非零元个数）将矩