数据结构2331第4章数组和广义表

1、124.1 数组数组4.2 广义表广义表3 数组可看成是一种特殊的线性表，其特殊在于，表中的数组元数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。素本身也是一种线性表。Amn=a0 0 a0 1 a0 2 a0 n-1a1 0 a1 1 a1 2 a1 n-1a2 0 a2 1 a2 2 a2 n-1 am-1 0 am-1 1 am-1 2 am-1 n-14.1 数数 组组4.1.1 数组的逻辑结构和运算数组的逻辑结构和运算 数组数组是是线性表的推广线性表的推广，其每个元素由一个值和一，其每个元素由一个值和一 组下标组成，其中下标个数称为组下标组成，其中下标个数

2、称为数组的维数数组的维数。 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于唯一可供使用的数据类型。由于数组中各元素具有统一的类型数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是线性表的推广。例处理比其它复杂的结构更为简单。多维数组是线性表的推广。例如，二维数组：如，二维数组： 4 二维数组Amn可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 数组一旦被定

3、义，它的维数和维界就不再改变。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组通常只有因此，除了结构的初始化和销毁之外，数组通常只有两种基本运算两种基本运算： 读读给定一组下标，读取相应的数据元素；给定一组下标，读取相应的数据元素； 写写给定一组下标，修改相应的数据元素；给定一组下标，修改相应的数据元素； Amn=a0 0 a0 1 a0 2 a0 n-1a1 0 a1 1 a1 2 a1 n-1a2 0 a2 1 a2 2 a2 n-1 am-1 0 am-1 1 am-1 2 am-1 n-151.1.存储结构存储结构顺序存储结构顺序存储结构 由于计算机的由

4、于计算机的内存结构是一维的内存结构是一维的，因此用一维内，因此用一维内存来表示多维数组，就必须按某种次序将数组元素存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器排成一列序列，然后将这个线性序列存放在存储器中。中。 又由于对数组一般不做插入和删除操作，也就是又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是关系就不再发生变化。因此，一般都是采用顺序存采用顺序存储储的方法来表示数组。的方法来表示数组。 4.1.2 数组的存储结构数组的存储结构6

5、2.2.存储方式：存储方式：（通常有两种顺序存储方式）（通常有两种顺序存储方式）行优先顺序（以行为主存放）行优先顺序（以行为主存放）将数组元素按行排将数组元素按行排列，第列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个行向量后面个行向量后面。以二维数组。以二维数组为例，按行优先顺序存储的线性序列为：为例，按行优先顺序存储的线性序列为： a a0 00 0，a a0 10 1,a,a0 20 2, ,a,a0 n-10 n-1, a, a1 01 0，a a1 11 1,a,a1 21 2, ,a a1 n-11 n-1, , ,a ,am-1 0m-1 0, , a am-1 1m-

6、1 1, a, am-1 2m-1 2 ， ,a ,am-1 n-1m-1 n-1 在在PASCALPASCAL、C C语言语言中，数组就是按中，数组就是按行优先顺序行优先顺序顺序存储的。顺序存储的。列优先顺序（以列为主存放）列优先顺序（以列为主存放）将数组元素按列向将数组元素按列向量排列，第量排列，第j+1j+1个列向量紧接在第个列向量紧接在第j j个列向量之后个列向量之后，A A的的m m* *n n个元素按列优先顺序存储的线性序列为：个元素按列优先顺序存储的线性序列为： a a0 00 0,a,a1 01 0, ,a,am-1 0m-1 0,a,a0 10 1,a,a1 11 1, ,a

7、 am-1 1m-1 1, ,a,a0 n-10 n-1,a,a1 n-11 n-1, , , a, am-m-1 n-11 n-1 在在FORTRANFORTRAN语言中，数组就是按语言中，数组就是按列优先顺序列优先顺序顺序存储的。顺序存储的。7 以上规则可以推广到多维数组的情况：以上规则可以推广到多维数组的情况：行优先顺序（以行为主存放）行优先顺序（以行为主存放）以下标最右以下标最右边变化最快，最左边变化最慢的规则存放。边变化最快，最左边变化最慢的规则存放。列优先顺序（以列为主存放）列优先顺序（以列为主存放）以下标最左以下标最左边变化最快，最右边变化最慢的规则存放。边变化最快，最右边变化最

8、慢的规则存放。 按上述两种方式顺序存储的数组，只要知道开始元素的存放地按上述两种方式顺序存储的数组，只要知道开始元素的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以用的单元数，就可以将数组元素的存放地址表示为其下标的线性函将数组元素的存放地址表示为其下标的线性函数数。因此，数组中的任一元素可以在相同的时间内存取，即。因此，数组中的任一元素可以在相同的时间内存取，即顺序存顺序存储的数组是一个随机存取结构。储的数组是一个随机存取结构。83.3.寻址公式（以行为主存放）寻址公式（以行为主存放） 例如，例如，

9、二维数组二维数组A Amnmn按按“行优先顺序行优先顺序”存储在内存中存储在内存中，假设，假设每个元素占用每个元素占用k k个存储单元个存储单元。 元素元素a aijij的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在a aijij前面的元素所占用的单元数。因为前面的元素所占用的单元数。因为a aijij位于第位于第i i行、第行、第j j列，前面列，前面i i行一共有行一共有i in n个元素，第个元素，第i i行上行上a aijij前面又有前面又有j j个元素，故它前面一共有个元素，故它前面一共有i in+jn+j个元素，因此，个元素，因此，a aijij的的地址计算函

10、数为：地址计算函数为： LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+j)n+j)* *k k 9 在科学与工程计算问题中，矩阵是一种常用的数学在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为也非常简单，并且存储的密度为1 1。但是在矩阵中非零

11、。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为况下，看起来存储密度仍为1 1，但实际上占用了许多单，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，成极大的浪费，为了节省存储空间， 我们可以对这类我们可以对这类矩阵进行矩阵进行压缩存储压缩存储：即为多个相同的非零元素只分配一即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间个存储空间；对零元素不分配空间。4.1.3 矩阵的压缩存储矩阵的压缩存储1

12、01 1、对称矩阵、对称矩阵 1.1.定义：定义：在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji 0i,jn-1 0i,jn-1 则称则称A A为对称矩阵为对称矩阵。如下图便是一个。如下图便是一个5 5阶对称矩阵。阶对称矩阵。 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 特殊矩阵特殊矩阵即即指非零元素或零元素的分布有一定规指非零元素或零元素的分布有一定规律的矩阵律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。下面我们讨论几种特殊矩阵的压缩存储。一、特殊矩阵一、特殊矩阵11

13、 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i i个元素，元素总个元素，元素总数为：数为： (i)=n(n+1)/2(i)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在因此，我们可以按图中箭头所指的次序将这些元素存放在一个一维数组一个一维数组S1.n(n+1)/2S1.n(n+1)/2中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中的中的元素，我们必须在元素，我们必须在a aijij和和SkSk之间找一个对应关系。之间找一个对应关系。 2.2.物理存储：物理存储： 对称矩阵中的元素关于主对角线对称，故对称矩阵中的元素关于主对角线对称，故只要存

14、储矩阵只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间存储空间，这样，能节约近一半的存储空间。不失一般性，这样，能节约近一半的存储空间。不失一般性，我们按我们按“行优先行优先顺序顺序”存储主对角线（包括对角线）以下的存储主对角线（包括对角线）以下的元素，其存储形式如图所示元素，其存储形式如图所示：a0 0a1 0 a 1 1a2 0 a2 1 a2 2 .an-1 0 a n-1 1 a n-1 2 a n-1 n -1 12 (1) 若若ij，则，则ai j在在下三角形下三角形中。中。ai j之前的之前的i行（从第行

15、（从第0 行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，在第个元素，在第i行上，行上， ai j之前恰有之前恰有j个元素（即个元素（即ai 0,ai 1,ai 2,ai 3,ai j-1），）， 因此有：因此有：(2) 若若ij，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以只，所以只 要交换上述对应关系式中的要交换上述对应关系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 -1下标变换公式下标变换公式：（以：（以下三角下三角表示）表示）即：即： ai jSSi*(i+1)/2+j k=i*(i+1

16、)/2+j 0k n(n+1)/2-1 令令 I=max(i,j)， J=min(i,j)，则，则k和和 i, j的对应关系的对应关系 可统一为：可统一为： k=I*(I-1)/2+J 0kn(n+1)/2 -113 有了上述的下标交换关系，对于任意给定一组下标有了上述的下标交换关系，对于任意给定一组下标(i(i，j)j)，均可在，均可在SkSk中找到矩阵元素中找到矩阵元素a aijij，反之，对所有，反之，对所有的的k=0,1,2,3,k=0,1,2,3,n(n+1)/2-1n(n+1)/2-1，都能确定，都能确定SkSk中的元素在中的元素在矩阵中的位置矩阵中的位置(i,j)(i,j)。由此

17、，称。由此，称Sn(n+1)/2Sn(n+1)/2为对称矩阵为对称矩阵A A的压缩存储，见下图：的压缩存储，见下图：a00a10a12a21an-1 1 an-1 n-1k=0 1 2 3 n(n+1)/2-1 例如例如a31和和a13均存储在均存储在 sa4中，这是因为：中，这是因为： k=I*(I-1)/2+J=3*(3-1)/2+1=4142、三角矩阵、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它

18、的主对中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩下三角矩15 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，其余的可共享一个存储空间，其余的元素正好有元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压缩存

19、储到个，因此，三角矩阵可压缩存储到向量向量s0.n(n+1)/2s0.n(n+1)/2中，其中中，其中c c存放在向量的最后一个分存放在向量的最后一个分量中。量中。 上三角矩阵中上三角矩阵中，主对角线之上的第，主对角线之上的第p p行行(0pn)(0pjijk= 下三角矩阵下三角矩阵的存储和对称矩阵类似，的存储和对称矩阵类似，sksk和和a aijij对应对应关系是：关系是： i i(i+1)/2+j (i+1)/2+j ijij n(n+1)/2n(n+1)/2 i ij jk=163 3、对角矩阵、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线对角矩阵中，所有的非零元素集中在以主对角

20、线为了中心的带状区域中，即除了主对角线和主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个为零。下图给出了一个三对角矩阵三对角矩阵: : a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-10 00 017 在三对角矩阵中非0元素的分布有明显的规律，可将它们压缩存储到一维数组中，并找到每个非0元素在一维数组中的对应关系。 可按行优序为主序来存储三对角矩阵。除第0行和第n

21、-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 数组数组s中的元素中的元素sk与三对角带状矩阵中的元素与三对角带状矩阵中的元素aij存在存在一一对应关系，在一一对应关系，在aij之前有之前有i行行,共有共有3*i-1个非零元素，在个非零元素，在第第i行，有行，有j-i+1个非零元素，这样，非零元素个非零元素，这样，非零元素aij的地址为：的地址为： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*L =LOC(0,0)+(2

22、i+j)*L18 上例中，上例中，a a3434对应着对应着s10s10。 k=k=2 2* *i+ji+j=2=2* *3+4=103+4=10 a a2121对应着对应着s5 s5 k=2 k=2* *2+1=52+1=5 由此，我们称由此，我们称s0.3s0.3* *n-2n-2是三对角是三对角带状矩阵带状矩阵A A的压缩存储表示。的压缩存储表示。 上述的各种特殊矩阵，其非零元素的分布都是有规上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的向量中，并且一般

23、都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。机存取。19 什么是稀疏矩阵？简单说，什么是稀疏矩阵？简单说，设矩阵设矩阵A A中有中有s s个非零元素，个非零元素，若若s s远远小于矩阵元素的总数，则称远远小于矩阵元素的总数，则称A A为稀疏矩阵为稀疏矩阵。稀疏矩阵的压缩存储稀疏矩阵的压缩存储即只存储稀疏矩阵中的非零元即只存储稀疏矩阵中的非零元素。有两种存储方法。素。有两种存储方法。 精确点，设在的矩阵精确点，设在的矩阵A A中，有中，有s s个非零元素。令个非零元素。令 e=s/(me=s/(m* *n)n)

24、，称，称e e为矩阵的稀疏因子。通常认为为矩阵的稀疏因子。通常认为e0.05e0.05时称之为稀疏矩阵。在存时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。方法。 由于非零元素的分布一般是没有规律的，因此在存储非零元素由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（的同时，还必须同时记下它所在的行和列的位置（i,j)i,j)。反之，。反之，一个三元组一个三元组(i,j,a(i,j,aijij) )唯一确定了矩阵唯一确定了矩阵A A的一个非零元。因此，稀疏

25、的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。矩阵可由表示非零元的三元组及其行列数唯一确定。二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储20 例如，下列三元组表例如，下列三元组表 ( (1,2,12)，(1,3,9)，(3,1,- 3)，(3,6,14)，(4,3,24), (5,2,18)，(6,1,15)，(6,4,-7) ) 加上加上(6,7)(6,7)这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵M M的另的另一种描述。而由上述三元组表的不同表示方法可引出一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。稀疏矩阵不同的压缩存

26、储方法。 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 0 15 0 0 15 0 0 7 0 0 0 7 0 0 0 M=T=0 0 -3 0 0 150 0 -3 0 0 1512 0 0 0 18 012 0 0 0 18 09 0 0 24 0 09 0 0 24 0 00 0 0 0 0 0 0 0 0 0 7 70 0 14 0 0 0

27、 0 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0211 1、三元组顺序表、三元组顺序表 稀疏矩阵的三元组顺序表表示法稀疏矩阵的三元组顺序表表示法将矩阵中的非零元将矩阵中的非零元素化成三元组形式并按行的不减次序（同行按列的递增素化成三元组形式并按行的不减次序（同行按列的递增次序）存放在内存中。次序）存放在内存中。1).1).三元组表结构：三元组表结构： 假设以顺序存储结构来表示三元组表，则可得到稀疏假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法矩阵的一种压缩存储方法三元组顺序表。三元组顺序表。 #defin

28、e maxnum 10#define maxnum 10 typedef struct node typedef struct node int i, j; / int i, j; /* *非零元的行下标和列下标非零元的行下标和列下标* */ / DataType v; / DataType v; /* *非零元素的值非零元素的值* */ / NODENODE; ;三元组三元组 22 typedef struct spmatrix typedef struct spmatrix NODE datamaxnum+1; NODE datamaxnum+1; / /* *非零元三元组表非零元三元组表

29、* */ / int mu,nu,tu; int mu,nu,tu; / /* *矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数* */ / SpMatrixTp;SpMatrixTp;稀疏矩阵三元组表存储类型稀疏矩阵三元组表存储类型 设设:SpMatrixTp M ; :SpMatrixTp M ; 则下图中所示的稀疏矩阵的三则下图中所示的稀疏矩阵的三元组的表示如右：元组的表示如右： 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 -3 0 0 0 0 14 0 0 0 24 0 0

30、 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 0 15 0 0 15 0 0 7 0 0 07 0 0 0 i j v i j v 1 1 2 12 1 1 2 12 2 1 3 9 2 1 3 9 3 3 1 -3 3 3 1 -3 4 3 6 14 4 3 6 14 5 4 3 24 5 4 3 24 6 5 2 18 6 5 2 18 7 6 1 15 7 6 1 15 8 6 4 -78 6 4 -7 三元组表三元组表M.datap.iM.datap.jM.datap.v 232). 稀疏矩阵的转置运算稀疏矩阵的转置运算 设：稀疏矩阵采

31、用三元组表存储表示，现求稀疏矩阵设：稀疏矩阵采用三元组表存储表示，现求稀疏矩阵M M的转置矩阵的转置矩阵T T（M M、T T均是三元组表）。均是三元组表）。转置的含义转置的含义： m mn n的矩阵的矩阵M M转置转置方法方法：将将M M转置为转置为T T，就是将，就是将M M的三元组表的三元组表M.dataM.data置换为置换为T T的三元组表的三元组表T.dataT.data，如果只是简单地交换，如果只是简单地交换M.dataM.data中中i i和和j j的内容，那么得到的的内容，那么得到的T.dataT.data将是一个按列优先顺序存储将是一个按列优先顺序存储的稀疏矩阵的稀疏矩阵T

32、 T，要得到按行优先顺序存储的，要得到按行优先顺序存储的T.dataT.data，就必，就必须重新排列三元组的顺序。须重新排列三元组的顺序。 由于由于M M的列是的列是T T的行，因此，按的行，因此，按M.dataM.data的列序转置，所的列序转置，所得到的转置矩阵得到的转置矩阵B B的三元组表的三元组表T.dataT.data必定是按行优先存放必定是按行优先存放的。的。 n nm m的矩阵的矩阵T T， 且：且： Mij=Tji Mij=Tji （1 1i im m，1 1j jn n）24 按这种方法设计的算法，按这种方法设计的算法，其基本思想是其基本思想是：对对M M中的每一列中的每一

33、列 col(1col(1colcoln)n)，通过从头至尾扫描三元表，通过从头至尾扫描三元表M.dataM.data，找出，找出所有列号等于所有列号等于colcol的那些三元组，将它们的行号和列号互换的那些三元组，将它们的行号和列号互换后依次放入后依次放入T.dataT.data中，即可得到中，即可得到T T的按行优先的压缩存储表的按行优先的压缩存储表示。示。 r c v r c v 1 1 2 12 1 1 2 12 2 1 3 9 2 1 3 9 3 3 1 -3 3 3 1 -3 4 3 6 14 4 3 6 14 5 4 3 24 5 4 3 24 6 5 2 18 6 5 2 18

34、7 6 1 15 7 6 1 15 8 6 4 -78 6 4 -7 r c v r c v 1 1 3 -3 1 1 3 -3 2 1 6 15 2 1 6 15 3 2 1 12 3 2 1 12 4 2 5 18 4 2 5 18 5 3 1 9 5 3 1 9 6 3 4 24 6 3 4 24 7 4 6 -7 7 4 6 -7 8 6 3 148 6 3 14 转置转置25稀疏矩阵三元组表表示下的稀疏矩阵三元组表表示下的转置运算算法转置运算算法：（见（见P59算法）算法） SpMatrixTp *transmat ( SpMatrixTp *a ) /*用三元组表存储表示，求稀疏矩

35、阵用三元组表存储表示，求稀疏矩阵a a的转置矩阵并返回的转置矩阵并返回* */ / int p, q, col; int p, q, col; SpMatrixTp SpMatrixTp * *b ;b ; b=molloc(sizeof(spmatrix); b=molloc(sizeof(spmatrix); / /* *申请三元组申请三元组b b的存储空间的存储空间* */ / b-mu=a-nu ; b-nu=a-mu ; b-tu=a-tu ; b-mu=a-nu ; b-nu=a-mu ; b-tu=a-tu ; if (b-tu0) if (b-tu0) q=0 ; /*q指示三

36、元组指示三元组b的当前结点序号的当前结点序号*/ for ( col=1; colnu; col+ ) for ( p=1; ptu; p+) if ( a-datap.j=col ) b-dataq.i=a-datap.j; b-dataq.j=a-datap.i; b-dataq.v=a-datap.v ; q+; return b; 26 分析这个算法，主要的工作是在分析这个算法，主要的工作是在p p和和colcol的两的两个循环中完成的，故算法的时间复杂度为个循环中完成的，故算法的时间复杂度为O(nO(n* *t)t)，即矩阵的列数和非零元的个数的乘积，即矩阵的列数和非零元的个数的乘积

37、成正比。而一般传统矩阵的转置算法为：成正比。而一般传统矩阵的转置算法为： for(col=1;col=n;+col)for(col=1;col=n;+col) for(row=1;row=m;+row) for(row=1;row=m;+row) tcolrow=mrowcol; tcolrow=mrowcol; 其时间复杂度为其时间复杂度为O(nO(n* *m)m)。当非零元素的个数。当非零元素的个数t t和和m m* *n n同数量级时，算法同数量级时，算法TranposeSMatrixTranposeSMatrix的时的时间复杂度为间复杂度为O(nO(n* *n n2 2) )。27 三

38、元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。 下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。28 为了预先确定矩阵为了预先确定矩阵M M中的每一列的第一个非零元素在数组中的每一列的第一个非零元素在数组B B中应有的位置，需要先求得矩阵中应有的位置，需要先求得矩阵M M中的每一列中非零元素中的每一列中非零元素的个数。因为：矩阵

39、的个数。因为：矩阵M M中第一列的第一个非零元素在数组中第一列的第一个非零元素在数组B B中应有的位置等于前一列第一个非零元素的位置加上前列中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。非零元素的个数。 为此，需要设置两个一维数为此，需要设置两个一维数 num0.nnum0.n和和cpot0.ncpot0.n num0.n num0.n：统计统计M M中每列非零元素的个数，中每列非零元素的个数， numcolnumcol的值可以由的值可以由A A的第二列求得。的第二列求得。 cpot0.ncpot0.n：由递推关系得出：由递推关系得出M M中的每列第一个非中的每列第一个非

40、零元素在零元素在B B中的位置。中的位置。29 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 930 1 2 vqA i j v第一列元素个数 第二列元素个数 第三列元素个数numcpotq=cpotcol2 1 vpp31快速转置算法如下：快速转置算法如下： void fasttranstri(tritu

41、pletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;321. C语言中对数组元素的存放方式通常采用语言中对数组元素的存放方式通常采用( ) A. 按行为主的存储结构按行为主的存储结构 B.按行或列为主的存储结构按行或列为主的存储结构 C. 按列为主的存储结构按列为主的存储结构 D

42、.按行和列为主的存储结构按行和列为主的存储结构2. 一个一个nn的对称矩阵，如果以行为主序压缩存入内存，则其容量的对称矩阵，如果以行为主序压缩存入内存，则其容量 为（为（ ） An-1 B. n C. nn D. n(n+1)/2 3. 稀疏矩阵一般采用下列哪种方法压缩存储？（稀疏矩阵一般采用下列哪种方法压缩存储？（ ） A.三维数组三维数组 B.单链表单链表 C. 三元组表三元组表 D. 散列表散列表 4. 二维数组在机器级的具体实现，通常均采用二维数组在机器级的具体实现，通常均采用_ _存存储结构。储结构。5. 数组通常具有两种基本运算，即数组通常具有两种基本运算，即_。6. 矩阵压缩存储

43、的基本思想是为值相同的多个元素只分配一个存储矩阵压缩存储的基本思想是为值相同的多个元素只分配一个存储空间，为空间，为_不分配空间。不分配空间。请你给出答案请你给出答案思考题思考题想一想想一想337. 同一数组中的元素，它们（同一数组中的元素，它们（ ） A. 长度可以不同长度可以不同 B.类型不限类型不限 C. 类型相同类型相同 D.长度不限长度不限8. 数组是一个数组是一个( )线性表结构线性表结构. A. 不加限制的不加限制的 B. 加了限制的加了限制的 C. 推广了的推广了的 D. 非非9. 数组占用的空间数组占用的空间( ) A. 必须连续必须连续 B.可以不连续可以不连续 C. 不能连续不能连续 D. 不必连续不必连续10. 数组通常只有数组通常只有_和和_二种运算二种运算,因此常采用因此常采用_来存储数组。来存储数组。请你给出答案请你给出答案思考题思考题想一想想一想广义表广义表1广义表的定义广义表的定义2广义表的基本运算广义表的基本运算3广义表的存储结构广义