数组和广义表

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

1、南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 1 1第第5 5章章 数组和广义表数组和广义表 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 2 2主要内容主要内容n 数组的定义数组的定义 n 数组的顺序表示和实现数组的顺序表示和实现n 矩阵的压缩存储及典型算法矩阵的压缩存储及典型算法n 广义表及其应用（选讲）广义表及其应用（选讲）第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 3 3主要内容主要内容n 数组的逻辑特征数组的逻辑特征n一个数据元素可能有多个直接前

2、趋和多个直一个数据元素可能有多个直接前趋和多个直接后继接后继第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 4 4重点与难点重点与难点n 本章的重点本章的重点n二维数组的存储方式、几种特殊矩阵的二维数组的存储方式、几种特殊矩阵的存储方式（对称矩阵、上存储方式（对称矩阵、上/下三角矩阵、下三角矩阵、稀疏矩阵）、稀疏矩阵）、稀疏矩阵的快速转置算法稀疏矩阵的快速转置算法n 本章的难点本章的难点n稀疏矩阵的三元组表示及其三元组表示稀疏矩阵的三元组表示及其三元组表示下的快速转置、相乘算法下的快速转置、相乘算法第第5 5章章 数组和广义表数组和广义

3、表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 5 55.1 5.1 数组的定义数组的定义n数组的特点数组的特点n数组中各元素具有统一的类型。数组中各元素具有统一的类型。n数组元素的下标一般具有固定的上界和下界。数组元素的下标一般具有固定的上界和下界。n可以看成是由可以看成是由m个行向量组成的向量，也可以个行向量组成的向量，也可以看成是看成是n个列向量组成的向量。个列向量组成的向量。n二维数组二维数组Amnn每个数据元素可以又是一个线性表结构。每个数据元素可以又是一个线性表结构。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 ht

4、tp:/ 6 65.1 5.1 数组的定义数组的定义n每个数据元素可以又是一个线性表结构。每个数据元素可以又是一个线性表结构。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 7 75.1 5.1 数组的定义数组的定义n在在C语言中，一个二维数组类型可定义为其语言中，一个二维数组类型可定义为其分量类型为一维数组类型的一维数组类型分量类型为一维数组类型的一维数组类型 nelemtype array2mn;等价于：等价于：nelemtype array1n;narray1 array2m;第第5 5章章 数组和广义表数组和广义表 南昌航空大学

5、信息工程学院南昌航空大学信息工程学院 http:/ 8 85.1 5.1 数组的定义数组的定义n数组的定义数组的定义n若线性表中的数据元素为非结构的简单元素，若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。数组结构，则称作三维数组。n线性表结构是数组结构的一个特例，而数线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。组结

6、构又是线性表结构的扩展。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 9 95.1 5.1 数组的定义数组的定义n抽象数据类型数组的抽象数据类型数组的ADT定义定义ADT Array n数据对象数据对象: ji=0,.,bi-1,i=1,2,.,n; D=aj1j2.jn|n(0)称为数组的维数称为数组的维数,bi是数组第是数组第i维维的长度的长度,ji是数组元素的第是数组元素的第i维下标维下标,aj1j2.jn (-ElemSet n数据关系数据关系:R=R1,R2,.Rn Ri=| 0=jk=bk-1,1=k=n且且ki, 0=j

7、i=bi-2, aj1.ji.jn,aj1.ji+1 .jn(-D,i=2,.n)第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 10105.1 5.1 数组的定义数组的定义n抽象数据类型数组的抽象数据类型数组的ADT定义定义n基本操作基本操作: InitArray(&A,n,bound1,.,boundn) 操作结果：若维数和各维长度合法操作结果：若维数和各维长度合法,则构造相应数组则构造相应数组A,返回返回OK。DestroyArray(&A) 操作结果操作结果:销毁数组销毁数组A。Value(A,&e,index1,.,index

8、n) 初始条件初始条件:A是是n维数组维数组,e为元素变量为元素变量,随后是随后是n个下标值。个下标值。 操作结果操作结果:若各下标不超界若各下标不超界,则则e赋值为所指定赋值为所指定A的元素值的元素值,返回返回OK。 Assign(&A,e,index1,.,indexn) 初始条件初始条件:A是是n维数组维数组,e为元素变量为元素变量,随后是随后是n个下标值。个下标值。操作结果操作结果:若下标不超界若下标不超界,则将则将e的值赋给的值赋给 所指定的所指定的A的元素的元素,并返并返回回OK。ADT Array第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工

9、程学院 http:/ 11115.2 5.2 数组的顺序表示和实现数组的顺序表示和实现n存储结构存储结构n顺序存储：（多）对数组一般不做插入和删除操作顺序存储：（多）对数组一般不做插入和删除操作n链式存储：链式存储：（少）对稀疏矩阵（少）对稀疏矩阵n计算机的存储结构是一维的，而数组一般是多维计算机的存储结构是一维的，而数组一般是多维的，怎样存放？的，怎样存放？n事先约定按某种次序将数组元素排成一列序列，然后将事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。这个线性序列存入存储器中。n二维数组二维数组n行优先顺序（行优先顺序（Row Major Order）nBASIC

10、BASIC、PL/1PL/1、COBOLCOBOL、PASCALPASCAL和和C C语言语言n列优先顺序（列优先顺序（Column Major Order）nFORTRANFORTRAN语言语言 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 12125.2 5.2 数组的顺序表示和实现数组的顺序表示和实现 列优先列优先 行优行优先先第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 13135.2 5.2 数组的顺序表示和实现数组的顺序表示和实现n无论规定行优先或列优先，只要知道

11、以下三要素无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任便可随时求出任一元素的地址（这样数组中的任一元素便可以一元素便可以随机存取随机存取！）：！）：n开始结点的存放地址（即基地址）；开始结点的存放地址（即基地址）；n维数和每维的上、下界；维数和每维的上、下界；n每个数组元素所占用的单元数每个数组元素所占用的单元数n二维数组二维数组Ac1.d1,c2.d2，行优先存储，行优先存储nLOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+j-c2)*L n列优先存储列优先存储nLOC(aij)=LOC(ac1,c2)+(j-c2)*(d1

12、-c1+1)+i-c1)*L第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 14145.2 5.2 数组的顺序表示和实现数组的顺序表示和实现n例：一个二维数组例：一个二维数组A，行下标的范围是，行下标的范围是1到到6，列，列下标的范围是下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个个字节存储，存储器按字节编址。那么，这个数组字节存储，存储器按字节编址。那么，这个数组的体积是的体积是 个字节。个字节。n例：设数组例：设数组a160, 170的基地址为的基地址为2048，每个元素占每个元素占2个存储单元，若以列序为主序

13、顺序存个存储单元，若以列序为主序顺序存储，则元素储，则元素a32,58的存储地址为的存储地址为 。2888950nLOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*2第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 15155.3 5.3 矩阵的压缩存储矩阵的压缩存储n如何存储矩阵的元，从而使矩阵的各种运算能有如何存储矩阵的元，从而使矩阵的各种运算能有效地进行？效地进行？n用高级语言编制程序时，用二维数组来存储矩阵用高级语言编制程序时，用二维数组来存储矩阵元，可以随机存取元素，存储的密度为元，可以随机存取元素，

14、存储的密度为1 1。n在数值分析中经常出现一些阶数很高的矩阵，同在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中非零元素呈某种规律分布或者出现大时在矩阵中非零元素呈某种规律分布或者出现大量的零元素，看起来存储密度仍为量的零元素，看起来存储密度仍为1 1，但实际上占，但实际上占用了许多单元存储重复的非零元素或零元素，这用了许多单元存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空对高阶矩阵会造成极大的浪费，为了节省存储空间，可对这类矩阵进行间，可对这类矩阵进行压缩存储：压缩存储：n为多个相同的非零元素只分配一个存储空间；为多个相同的非零元素只分配一个存储空间；n对零元素

15、不分配空间。对零元素不分配空间。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 16165.3 5.3 矩阵的压缩存储矩阵的压缩存储n两种矩阵的压缩存储两种矩阵的压缩存储n特殊矩阵特殊矩阵值相同的元素或者零元素在矩阵值相同的元素或者零元素在矩阵中的分布有一定规律。中的分布有一定规律。n对称矩阵：不存相同元素对称矩阵：不存相同元素n三角矩阵：不存相同元素三角矩阵：不存相同元素n对角矩阵：只存非对角矩阵：只存非0元素元素n稀疏矩阵稀疏矩阵存在大量的零元素，但分布没有存在大量的零元素，但分布没有规律。规律。n三元组顺序表：存非三元组顺序表：存

16、非0元素的位置和值元素的位置和值n行逻辑链接的顺序表：存非行逻辑链接的顺序表：存非0元素的位置、元素的位置、值和每行非零元素在三元组表中的起始位置值和每行非零元素在三元组表中的起始位置第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 17175.3 5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵n对称矩阵对称矩阵nn n阶方阵阶方阵A A若满足下述性质，则称若满足下述性质，则称A A为对称矩阵。为对称矩阵。naij=aji 0 i,j n-1 n只要存储矩阵中上三角或下三角中的元素，让每两个对只要存储矩阵中上三角或下三角中的元素，让

17、每两个对称的元素共享一个存储空间，能节约近一半的存储空间。称的元素共享一个存储空间，能节约近一半的存储空间。 n元素总数为：元素总数为：1+2+3+n=n(n+1)/21 5 1 3 7 a005 0 8 0 0 a10 a111 8 9 2 6 a20 a21 a233 0 2 5 1 .7 0 6 1 3 an-10 a n-11 a n-1 2 a n-1 n-1 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 18185.3 5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵n对称矩阵对称矩阵A A的压缩存储的压缩存储san(

18、n+1)/2san(n+1)/2 na aijij和和saksak 之间的对应关系。之间的对应关系。 当ij第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 19195.3 5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵n三角矩阵三角矩阵 n分为上三角、下三角分为上三角、下三角 a00 a01 a 0 n-1 a00 c cc a11 a 1 n-1 a10 a11 c. .c c a n-1 n-1 an-10 an-11 an-1n-1 n三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，其余的可共享一个存储空间

19、，其余的元素正好有元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压缩存储到个，因此，三角矩阵可压缩存储到向量向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中，其中c c存放在向量的最后一个存放在向量的最后一个分量中。分量中。 n元素总数为：元素总数为：1+2+3+n+1=n(n+1)/2+1第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 20205.3 5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵n下三角矩阵下三角矩阵 A A的压缩存储的压缩存储san(n+1)/2san(n+1)/2 n下三角矩阵

20、下三角矩阵 A A中中a aijij和和saksak 之间的对应关系。之间的对应关系。 当ijn(n-1)第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 21215.3 5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵n对角矩阵对角矩阵n所有的非零元素集中在以主对角线为中心的带状区域中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如：的元素之外，其余元素皆为零。如：三对角矩阵三对角矩阵 第第5 5章章 数

21、组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 22225.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵稀疏矩阵n设矩阵设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩阵元素的远远小于矩阵元素的总数（即总数（即smsmn n），则称），则称A A为稀疏矩阵为稀疏矩阵n稀疏因子稀疏因子 e 0.05e 0.05 (e=(e=s/(ms/(m*n)*n) ) )n如果只存储稀疏矩阵中的非零元素，那这些元如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？素的位置信息该如何表示？n对每个非零元素增开若干存

22、储单元，例如存放其所对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。在的行号和列号，便可准确反映该元素所在位置。n具体实现：将每个非零元素用一个三元组具体实现：将每个非零元素用一个三元组（i i，j j，a aijij）来表示，则每个稀疏矩阵可用一个三元来表示，则每个稀疏矩阵可用一个三元组表来表示。组表来表示。行下标行下标列下标列下标元素值元素值第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 23235.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵稀疏矩阵A6 7 0 12

23、9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0n表示方法表示方法n三元组顺序表三元组顺序表n用线性表表示：用线性表表示：不能随机存取不能随机存取n用三元组矩阵表示：用三元组矩阵表示：不能随机存取不能随机存取n行逻辑链接的顺序表行逻辑链接的顺序表可随机存取可随机存取第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 24245.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的三元组顺序表表示稀疏矩阵的三

24、元组顺序表表示 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0n用线性表表示：用线性表表示：(1,2,12)(1,2,12)，(1,3,9)(1,3,9)，(3,1,-3)(3,1,-3)，(3,6,14)(3,6,14)，(4,3,24)(4,3,24)，(5,2,18)(5,2,18)，(6,1,15)(6,1,15)，(6,4,-7)(6,4,-7)n用三元组矩阵表示：用三元组矩阵表示： 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌

25、航空大学信息工程学院 http:/ 25255.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的三元组顺序表存储结构稀疏矩阵的三元组顺序表存储结构 n#define #define maxsizemaxsize 12500 12500 typedeftypedef structstruct intint i,ji,j; ; ElemTypeElemType e; e;Triple;Triple; typedeftypedef structstruct Triple datamaxsize+1; / data0 Triple datamaxsize+1; / data0未用未

26、用 intint mu,nu,tumu,nu,tu; ; TSMatrixTSMatrix; ;第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 26265.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的转置稀疏矩阵的转置n一个一个m mn n的矩阵的矩阵M M，它的转置，它的转置T T是一个是一个n nm m的矩阵，且的矩阵，且aijaij=bjibji ，0im0im，0jn0jn 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0

27、0 14 0 9 0 0 24 0 0 M 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 27275.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的转置稀疏矩阵的转置 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 28285.3 5.3 矩阵的压缩存储矩阵的压缩

28、存储稀疏矩阵稀疏矩阵n稀疏矩阵的一般转置算法稀疏矩阵的一般转置算法n方法一：将方法一：将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 T，必须重新排列三元组，必须重新排列三元组T T的顺序，得到按的顺序，得到按行优先顺序存储的行优先顺序存储的T.dataT.data。( (不可取，为什么？不可取，为什么？

29、) )n对对M M中的每一列中的每一列 col(0coln-1)col(0coln-1)，通过从头至尾，通过从头至尾扫描三元组表扫描三元组表M.dataM.data，找出所有列号等于，找出所有列号等于colcol的那些的那些三元组，将它们的行号和列号互换后依次放入三元组，将它们的行号和列号互换后依次放入T.dataT.data中，即可得到中，即可得到T T的按行优先的压缩存储表示。的按行优先的压缩存储表示。（算法（算法5.15.1）第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 29295.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩

30、阵稀疏矩阵n稀疏矩阵的一般转置算法稀疏矩阵的一般转置算法（P98 P98 算法算法5.15.1）nStatus Status TransposeSMatrix(TSMatrixTransposeSMatrix(TSMatrix M, M, TSMatrixTSMatrix &T) &T) T.muT.mu= =M.nuM.nu; ; T.nuT.nu= =M.muM.mu; ; T.tuT.tu= =M.tuM.tu; ; if ( if (T.tuT.tu=0) =0) q=1; q=1; for ( for (colcol=1;col=1;col=M.nu;+colM.nu;+col) )

31、 for (p=1;p= for (p=1;p=M.tu;+pM.tu;+p) ) if ( if (M.datap.jM.datap.j=colcol) T.dataq.iT.dataq.i= =M.datap.jM.datap.j; ; T.dataq.jT.dataq.j= =M.datap.iM.datap.i; ; T.dataq.vT.dataq.v= =M.datap.vM.datap.v; +q; ; +q; return OK; return OK; / /TransposeSMatrixTransposeSMatrix第第5 5章章 数组和广义表数组和广义表 南昌航空大学信

32、息工程学院南昌航空大学信息工程学院 http:/ 30305.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n算法算法5.1分析分析n算法的时间复杂度为算法的时间复杂度为O(nuO(nu* *tutu) )，即矩阵的列数和非零元的个，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：数的乘积成正比。而一般传统矩阵的转置算法为： for(colfor(col=0;col=n-1;+col)=0;col=n-1;+col) for(rowfor(row=0;row=0;row=m;+rowm;+row) ) TcolrowTcolrow=MrowcolMrowcol;其

33、时间复杂度为其时间复杂度为O(nO(n*m)*m)。当非零元素的个数。当非零元素的个数t t和和m*nm*n同数量同数量级时，算法级时，算法TransposeSMatrixTransposeSMatrix的时间复杂度为的时间复杂度为O(nO(n*n2)*n2)。n三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于因此，此算法仅适用于 tutu=mumu* *nunu 的情况。的情况。第第5 5章章 数组和广义表数组和广

34、义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 31315.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的快速转置算法稀疏矩阵的快速转置算法（P100 P100 算法算法5.25.2）n算法思想：对算法思想：对M.dataM.data扫描一次，按扫描一次，按M.dataM.data第二列提供的第二列提供的列号一次确定位置装入列号一次确定位置装入B B的一个三元组。的一个三元组。n具体实现：一遍扫描先确定三元组的位置关系，二次扫具体实现：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法描由位置关系装入三元组。可见，

35、位置关系是此种算法的关键。的关键。n为了预先确定矩阵为了预先确定矩阵M M中的每一列的第一个非零元素在数中的每一列的第一个非零元素在数组组T T中应有的位置，需要先求得矩阵中应有的位置，需要先求得矩阵M M中的每一列中非零中的每一列中非零元素的个数。因为：矩阵元素的个数。因为：矩阵M M中第一列的第一个非零元素中第一列的第一个非零元素在数组在数组T T中应有的位置等于前一列第一个非零元素的位中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。置加上前列非零元素的个数。 为此，需要设置两个一为此，需要设置两个一维数组维数组num0.nnum0.n和和cpot0.ncpot0.n第第

36、5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 32325.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n两个一维数组两个一维数组num0.nnum0.n和和cpot0.ncpot0.n：nnum0.nnum0.n：统计：统计M M中每列非零元素的个数，中每列非零元素的个数，numcolnumcol 的的值可以由值可以由A A的第二列求得。的第二列求得。ncpot0.ncpot0.n：由递推关系得出：由递推关系得出M M中的每列第一个非零元中的每列第一个非零元素在素在B B中的位置。中的位置。n算法通过算法通过cpotcpot数

37、组建立位置对应关系：数组建立位置对应关系：ncpot1=1cpot1=1ncpotcolcpotcol=cpotcol-1+numcol-1=cpotcol-1+numcol-1 （ 2= 2= colcol = = M.nuM.nu）n矩阵矩阵M M和相应的三元组和相应的三元组M.dataM.data可以求得可以求得: :ncolcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7nnumcolnumcol 2 2 2 1 0 1 0 2 2 2 1 0 1 0ncpotcolcpotcol 1 3 5 7 8 8 9 1 3 5 7 8 8 9 第第5 5章章 数组和广义表数组和

38、广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 33335.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的快速转置算法稀疏矩阵的快速转置算法（P100 P100 算法算法5.25.2）nStatus Status FastTransposeSMatrix(TSMatrixFastTransposeSMatrix(TSMatrix M, M, TSMatrixTSMatrix &T) &T) T.muT.mu= =M.nuM.nu; ; T.nuT.nu= =M.muM.mu; ; T.tuT.tu= =M.tuM.tu; ; if ( if (T.

39、tuT.tu) ) for ( for (colcol=1;col=1;col=M.nu;+colM.nu;+col) ) numcolnumcol=0;=0; for (t=1;t= for (t=1;t=M.tu;+tM.tu;+t) +) +numM.datat.jnumM.datat.j; cpot1=1; cpot1=1; for ( for (colcol=2;col=2;col=M.nu;+colM.nu;+col) ) cpotcolcpotcol=cpotcol-1+numcol-1;=cpotcol-1+numcol-1; for (p=1;p= for (p=1;p=M.

40、tu;+pM.tu;+p) colcol= =M.datap.jM.datap.j; q=; q=cpotcolcpotcol; T.dataq.iT.dataq.i= =M.datap.jM.datap.j; ; T.dataq.jT.dataq.j= =M.datap.iM.datap.i; ; T.dataq.vT.dataq.v= =M.datap.vM.datap.v; ; +cpotcolcpotcol; return OK; return OK; / / FastTransposeSMatrixFastTransposeSMatrix第第5 5章章 数组和广义表数组和广义表 南昌

41、航空大学信息工程学院南昌航空大学信息工程学院 http:/ 34345.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n算法算法5.2分析分析n算法的时间复杂度为算法的时间复杂度为O(muO(mu* *nunu) )，与一般传统矩，与一般传统矩阵的转置算法的时间复杂度相同。阵的转置算法的时间复杂度相同。n三元组顺序表又称三元组顺序表又称“有序的双下标法有序的双下标法”，其特，其特点：点：n非零元在表中按行序有序存储，方便依行顺序处理非零元在表中按行序有序存储，方便依行顺序处理的矩阵运算，但不能进行随机存取，需从头开始进的矩阵运算，但不能进行随机存取，需从头开始进行查找。行查找。n引入

42、引入行逻辑链接的顺序表行逻辑链接的顺序表可随机存取可随机存取第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 35355.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n稀疏矩阵的稀疏矩阵的行逻辑链接的顺序表行逻辑链接的顺序表存储结构存储结构 n#define #define maxsizemaxsize 12500 12500 typedeftypedef structstruct intint i,ji,j; ; ElemTypeElemType e; e;Triple;Triple; typedeftypedef stru

43、ctstruct Triple datamaxsize+1; Triple datamaxsize+1; / / 非零元三元组表非零元三元组表intint rposMAXRC+1; rposMAXRC+1; / / 各行第一个非零元的位置表各行第一个非零元的位置表 intint mu,nu,tumu,nu,tu; ; / / 矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数 TSMatrixTSMatrix; ;第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 36365.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n

44、两个稀疏矩阵相乘算法两个稀疏矩阵相乘算法n从两个稀疏矩阵相乘的例子，容易看出从两个稀疏矩阵相乘的例子，容易看出行逻辑链接的顺序表行逻辑链接的顺序表表表示方法的优越性。示方法的优越性。n两个矩阵相乘的经典算法：若设两个矩阵相乘的经典算法：若设Q=M*NQ=M*N，其中，其中，M M是是m1*n1m1*n1矩阵，矩阵，N N是是m2*n2m2*n2矩阵，当矩阵，当n1=m2n1=m2时，有：时，有：for(ifor(i=1;i=m1;+i)=1;i=m1;+i) for(jfor(j=1;j=n2;+j)=1;j=n2;+j) qijqij=0=0 for(kfor(k=1;k=n1;+k) =1

45、;k=n1;+k) qijqij+=+=mikmik*nkjnkj; n此算法的复杂度为此算法的复杂度为O(m1*n1*n2)O(m1*n1*n2)。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 37375.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n两个稀疏矩阵相乘算法两个稀疏矩阵相乘算法 3 0 0 5 0 2 0 63 0 0 5 0 2 0 6M = 0 M = 0 1 0 0 N = 1 0 Q = -1 01 0 0 N = 1 0 Q = -1 0 2 0 0 0 -2 4 0 4 2 0 0 0 -2 4

46、 0 4 0 0 0 0 i j v i j v i j vi j v i j v i j v 1 1 3 1 2 2 1 2 6 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 1 4 5 2 1 1 2 1 -1 2 2 -1 3 1 -2 3 2 4 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 3 1 2 3 2 4第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 38385.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n两个稀疏矩阵相乘算法两个稀疏矩阵相乘算法（P102 P

47、102 算法算法5.35.3）n设计思想设计思想: :对对M M中每个元素，找到中每个元素，找到N N中所有满足条件的元素，中所有满足条件的元素，求得和的乘积，乘积矩阵求得和的乘积，乘积矩阵Q Q中每个元素的值是个累加和，中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组设一累加和的变量，其初值为零，然后扫描数组M M，求得，求得相应元素的乘积并累加到适当的求累计和的变量上。相应元素的乘积并累加到适当的求累计和的变量上。 Q Q初始化；初始化； if (Qif (Q是非零矩阵是

48、非零矩阵) ) / /逐行求积逐行求积 for (for (arowarow = 1; = 1; arowarow = = M.muM.mu; +; +arowarow) /) /处理处理M M的每一行的每一行 ctempctemp=0; /=0; /累加器清零累加器清零 计算计算Q Q中第中第arowarow行的积并存入行的积并存入ctempctemp 中中; ; 将将ctempctemp 中非零元压缩存储到中非零元压缩存储到Q.dataQ.data; ; /for /for arowarow /if /if 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息

49、工程学院 http:/ 39395.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵n两个稀疏矩阵相乘算法两个稀疏矩阵相乘算法（P102 P102 算法算法5.35.3）nStatus Status MultSMatrix(RLSMatrixMultSMatrix(RLSMatrix M,RLSMatrixM,RLSMatrix N,RLSMatrixN,RLSMatrix &Q) &Q) if ( if (M.nuM.nu != != N.muN.mu) return ERROR;) return ERROR; Q.muQ.mu = = M.muM.mu; ; Q.nuQ.nu =

50、= N.nuN.nu; ; Q.tuQ.tu=0; /Q=0; /Q初始化初始化 if ( if (M.tuM.tu * * N.tuN.tu != 0) != 0)/Q/Q是非零是非零 for(arrowfor(arrow = 1; arrow = = 1; arrow = M.mM.m; +; +arowarow) ctemparowctemparow=0;=0; Q.rposarowQ.rposarow=Q.tu+1; =Q.tu+1; if ( if (arowarow M.muM.mu) ) tptp=M.rposarow+1;=M.rposarow+1; else else tpt

51、p=M.tu+1;=M.tu+1;第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 40405.3 5.3 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵 for (p= for (p=M.rposarow;pM.rposarow;p tp;+ptp;+p) brow= brow=M.datap.jM.datap.j; ; if (brow if (browN.muN.mu) t=N.rposbrow+1;) t=N.rposbrow+1; else t=N.tu+1; else t=N.tu+1; for ( q = for ( q =

52、N.rposbrowN.rposbrow; q; qt;+qt;+q) ccolccol= =N.dataq.jN.dataq.j; ; ctempccolctempccol += += M.datap.eM.datap.e * * N.dataq.eN.dataq.e; /for q; /for q /for p /for p for(ccolfor(ccol=1;ccol=1;ccolMAXSIZE) return ERROR;MAXSIZE) return ERROR; Q.dataQ.tuQ.dataQ.tu=arow,ccol,ctempccolarow,ccol,ctempccol

53、; /if; /if /for /for arowarow /if /if return OK; return OK; / /MultSMatrixMultSMatrix第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 41415.4 5.4 广义表的定义广义表的定义n广义表广义表n（ListsLists，又称列表）是线性表的推广。，又称列表）是线性表的推广。n线性表定义为线性表定义为n=0n=0个元素个元素a1,a2,a3,a1,a2,a3,an,an的有限序列。的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分线性表的元素仅

54、限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。了广义表的概念。n广义表是广义表是n(nn(n=0)=0)个元素个元素a1,a2,a3,a1,a2,a3,an,an的有限序列，的有限序列，其中其中aiai或者是原子项，或者是一个广义表。通常记作或者是原子项，或者是一个广义表。通常记作LS=LS=（a1,a2,a3,a1,a2,a3,an),an)。LSLS是广义表的名字，是广义表的名字，n n为它的为它

55、的长度。若长度。若aiai是广义表，称它为是广义表，称它为LSLS的子表。的子表。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 42425.4 5.4 广义表的定义广义表的定义n抽象数据类型抽象数据类型广义表广义表的的ADT定义定义ADT GList n数据对象数据对象: D=i=1,2,.,n=0;ei(-AtomSet或或ei(-GList,AtomSet为某个数据对象为某个数据对象 n数据关系数据关系:R1=|ei-1,ei(-D,2=i=n)n基本操作基本操作:InitGlist(&L); 操作结果操作结果:创建空的广义表创建

56、空的广义表L。 CreateGList(&L,S); 初始条件初始条件:S是广义表的书写形式串；是广义表的书写形式串； 操作结果操作结果:由由S创建广义表创建广义表L。 DestroyGlist(&L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:销毁广义表销毁广义表L。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 43435.4 5.4 广义表的定义广义表的定义CopyGlist(&T,L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:由广义表由广义表L复制得到广义表复制得到广义表T。GL

57、istLength(L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:求广义表求广义表L的长度的长度,即元素个数。即元素个数。GListDepth(L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:求广义表求广义表L的深度。的深度。GlistEmpty(L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:判断广义表判断广义表L是否为空。是否为空。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 44445.4 5.4 广义表的定义广义表的定义GetHead(L); 初始条件初

58、始条件:广义表广义表L存在；存在； 操作结果操作结果:取广义表取广义表L的头。的头。GetTail(L); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:取广义表取广义表L的尾。的尾。InsertFirst_GL(&L,e); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:插入元素插入元素e作为广义表作为广义表L的第一元素。的第一元素。DeleteFirst_GL(&L,&e); 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:删除广义表删除广义表L的第一元素的第一元素,并用并用e返回其值。返回其值。Traverse_GL(L,Visit()

59、; 初始条件初始条件:广义表广义表L存在；存在； 操作结果操作结果:遍历广义表遍历广义表L,用函数用函数Visit处理每个元素。处理每个元素。ADT GList；第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 45455.4 5.4 广义表的定义广义表的定义n广义表一般记作广义表一般记作:LS=(a1,a2,.,an):LS=(a1,a2,.,an) nLSLS是广义表的名称是广义表的名称,n,n是它的长度是它的长度, ,aiai可以是单可以是单个元素也可是广义表个元素也可是广义表, ,分别称为原子和子表。分别称为原子和子表。n当广义表

60、非空时当广义表非空时, ,称第一个元素称第一个元素a1a1为为LSLS的的表头表头称其余元素组成的广义表为称其余元素组成的广义表为表尾表尾。第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 46465.4 5.4 广义表的定义广义表的定义n广义表的存储结构广义表的存储结构 n广义表的头尾链表存储表示广义表的头尾链表存储表示 typedeftypedef emnuATOM,LISTemnuATOM,LIST ElemTagElemTag; ; typedeftypedef structstruct GLNodeGLNode ElemTagE

61、lemTag tag; tag; union union AtomTypeAtomType atom; atom; structstructstructstruct GLNodeGLNode *hp,* *hp,*tp;ptrtp;ptr; ; 第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 47475.4 5.4 广义表的定义广义表的定义n例：有例：有A A、B B、C C、D D、E E五个广义表的描述如下：五个广义表的描述如下：nA=() AA=() A是一个空表是一个空表, ,它的长度为零它的长度为零nB=(e) B=(e) 列

62、表列表B B只有一个原子只有一个原子e,Be,B的长度为的长度为1 1nC=(C=(a,(b,c,da,(b,c,d) ) 列表列表C C的长度为的长度为2,2,两个元素分别为原两个元素分别为原子子a a和子表和子表( (b,c,db,c,d) )nD=(A,B,C) D=(A,B,C) 列表列表D D的长度为的长度为3,3,三个元素都是列表三个元素都是列表, ,显然显然, ,将子表的值代入后将子表的值代入后, ,则有则有D=(),(D=(),(e),(a,(b,c,de),(a,(b,c,d)nE=(E=(a,Ea,E) ) 这是一个递归的表这是一个递归的表, ,它的长度为它的长度为2,E2

63、,E相当于一相当于一个无限的列表个无限的列表E=(E=(a,(a,(aa,(a,(a,.),.)第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 4848第第5 5章作业章作业 nP95P124n以下题目做在书本上：以下题目做在书本上： 5.4.15.4.1、 5.4.25.4.2（1.1.8.8.）n以下题目做在习题本上，必以下题目做在习题本上，必须抄题须抄题 例例5.15.1、例例5.55.5、5.4.35.4.3（2.2.、4.4.）5.4.45.4.4（5.5.）第第5 5章章 数组和广义表数组和广义表 南昌航空大学信息工程学院南昌航空大学信息工程学院 http:/ 4949The EndThe EndData StructureData Structure