5 数组和广义表b+6 树a

井冈山大学电子与信息工程学院井冈山大学电子与信息工程学院井冈山大学电子与信息工程学院井冈山大学电子与信息工程学院计算机科学系计算机科学系计算机科学系计算机科学系孙凌宇孙凌宇孙凌宇孙凌宇sunlingyujgsu.edu.cnsunlingyujgsu.edu.cn 数组的定义数组的定义 线性表在一定含义下的扩展线性表在一定含义下的扩展 数组的顺序存储（多维到一维的映射）数组的顺序存储（多维到一维的映射） 以行序为主序以行序为主序/低下标优先变化低下标优先变化知识回顾知识回顾以行序为主序以行序为主序/低下标优先变化低下标优先变化 以列序为主序以列序为主序/高下标优先变化高下标优先变化 多维数组的地址映像函数多维数组的地址映像函数5.3 矩阵的压缩存储矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的在科学与工程计算问题中，矩阵是一种常用的 数学对象。数学对象。在数学上，矩阵是这样定义的：它是一个由在数学上，矩阵是这样定义的：它是一个由 m××n个元素排成的个元素排成的m行行（横向横向）n列列（纵向纵向）的表。）的表。mnmmnnaaaaaaaaa.212222111211用高级语言编程时，通常将矩阵描述为一个二维用高级语言编程时，通常将矩阵描述为一个二维 数组。在这种存储表示之下，可以对其中的元素进行数组。在这种存储表示之下，可以对其中的元素进行 随机存取，各种矩阵运算也非常简单。随机存取，各种矩阵运算也非常简单。然而，当矩阵中然而，当矩阵中非零非零元素元素呈某呈某种种规律分布规律分布或者或者其其 中中出现大量零出现大量零元素元素，实际会占用了许多单元去存储重，实际会占用了许多单元去存储重 复的非零元素或零元素，这对高阶矩阵造成极大的浪复的非零元素或零元素，这对高阶矩阵造成极大的浪 费费为了节省存储空间为了节省存储空间可以对这类矩阵进行可以对这类矩阵进行压缩压缩费费。为了节省存储空间为了节省存储空间，可以对这类矩阵进行可以对这类矩阵进行压缩压缩 存储存储：为为多个多个相同相同的的非零非零元素元素只分配只分配一个存储一个存储空空 间；间；对对零零元素元素则不分配空间则不分配空间。5.3.1 特殊特殊矩阵矩阵特殊特殊矩阵矩阵：非零非零元素元素或零或零元素的元素的分布有分布有一定一定规律规律的矩阵的矩阵。本节主要研究本节主要研究对对称称矩阵矩阵、三角三角矩阵矩阵和和对对角角矩阵矩阵（带状矩阵）的压缩存储。（带状矩阵）的压缩存储。如果矩阵的行数和列数相等，则称该矩如果矩阵的行数和列数相等，则称该矩 阵为方阵。若阵为方阵。若n××n阶的方阵阶的方阵A满足：满足： aij=aji(1in , 1jn) 则称矩阵则称矩阵A为为对对称称矩阵矩阵。在对称矩阵中，。在对称矩阵中，几乎几乎 有有一一半半元素的元素的值值是对是对应相等应相等的的。如下所示：。如下所示：1423417232012341275173510下（上）下（上）三角三角矩阵矩阵下（上）下（上）三角三角矩阵矩阵的特点是：的特点是：的特点是：的特点是：n n阶矩阵阶矩阵阶矩阵阶矩阵 的上（下）三角（不包括对角线）中的元素的上（下）三角（不包括对角线）中的元素的上（下）三角（不包括对角线）中的元素的上（下）三角（不包括对角线）中的元素 均为常数均为常数均为常数均为常数c c或零值等固定的值，下（上）半或零值等固定的值，下（上）半或零值等固定的值，下（上）半或零值等固定的值，下（上）半 部分的元素值没有任何规律。部分的元素值没有任何规律。部分的元素值没有任何规律。如下所示：部分的元素值没有任何规律。如下所示：a11a12 a 1na11c ca11a12 a 1na11c cc a22 a 2na21a22 c. c c a nnan1an2 an n (a)上三角矩阵上三角矩阵(b)下三角矩阵下三角矩阵图三角矩阵图三角矩阵对对角角矩阵矩阵的特点是：所有的非零元素都的特点是：所有的非零元素都 集中在集中在以主对以主对角角线为中线为中心心的的带状区域带状区域中。如中。如 下面的下面的3阶对角矩阵：阶对角矩阵： 002059000123 11340006921000177300002059对于这些特殊矩阵，应该对于这些特殊矩阵，应该充分利充分利用元素用元素值值的的 分布规律分布规律，将其进行压缩存储，将其进行压缩存储。选择压缩存储的。选择压缩存储的 方法应遵循两条原则：方法应遵循两条原则： Ø尽可能地压缩数据量；尽可能地压缩数据量； Ø压缩后仍可以比较容易地进行各项基本操作。压缩后仍可以比较容易地进行各项基本操作。即：找到一种方法即：找到一种方法将它将它们们压缩存储到一个向压缩存储到一个向 量量中，中，并且并且一一般般都都能找能找到到矩阵中的元素矩阵中的元素与与该该向向量量 的的对对应应关系关系，通过这个关系，仍能对矩阵的元素，通过这个关系，仍能对矩阵的元素 进行进行随机存取随机存取。对对称称矩阵的压缩存储矩阵的压缩存储对对称称矩阵的压缩存储矩阵的压缩存储对称矩阵的特点是对称矩阵的特点是aij=aji。一个。一个n阶方阵，共阶方阵，共有有n2个元素，而实际上在对称矩阵中有个元素，而实际上在对称矩阵中有n(n-1)/2个个元素可以通过其他元素获得元素可以通过其他元素获得。元素可以通过其他元素获得元素可以通过其他元素获得。压缩的方法是压缩的方法是首首先将二维先将二维关系关系映射成一维映射成一维关系关系，并并只只存储其中存储其中必必要要的的n(n+1)/2个（主对个（主对角角线线和和下下三三角角）元素）元素内容内容，这些元素的存储顺序以行为主序。这些元素的存储顺序以行为主序。假设定义一个数组存储假设定义一个数组存储 如右的对称矩阵：如右的对称矩阵：int SA10;则则SAk和矩阵元素和矩阵元素aij之间之间 存在如下一一对应关系：存在如下一一对应关系：14234172320123412751735100123456789 1057312201742314=0个元个元素素a1,a2,a3,an的有限序列。线性表的元素仅的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构。它可以是一个数或一个结构。若放松对表元素的这种限制，容许它们具有若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。其自身结构，这样就产生了广义表的概念。广广义表的义表的ADT定义定义参见教材参见教材P107。广广义表的义表的递归递归定义定义：是是n(n>=0)个元素个元素a1,a2,an的的有有限限序列，序列， 其中其中ai或者或者是是单单个元素个元素(原子项原子项)，或者或者是一个是一个广广 义表。义表。记作记作LS=（a1,a2,an)LS是广义是广义表表的的名名字，字，n为为表表长长。若。若ai也是广也是广义表，则称它为义表，则称它为LS的的子子表表。通常用圆括号将广义表括起来，用逗号分隔通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时其中的元素。为了区别原子和广义表，书写时用用大大写字母写字母表示表示广广义表，用义表，用小小写字母写字母表示表示原子原子。显然显然广广义表是义表是递归递归定义定义的线性的线性结构结构。广义表的。广义表的 例子：例子：（1）A=（）（） A是一个空表，其长度为零是一个空表，其长度为零（2）B=（e）表表B只有一个原子只有一个原子e，B的长度为的长度为1（3）C=（a,(b,c,d)表表C的长度为的长度为2，两个元素，两个元素 分别为原子分别为原子a和子表和子表(b,c,d)（4）D=（A，B，C）表表D的长度为的长度为3，三个元素，三个元素 都是广义表。显然，将子表的值代入后，则有都是广义表。显然，将子表的值代入后，则有D=( ),(e),(a,(b,c,d)（5）E=（a,E）这是一个递归的表，它的长度这是一个递归的表，它的长度 为为2，E相当于一个无限的广义表相当于一个无限的广义表E=(a,(a,(a,(a,)广广义表的义表的结构结构特点特点：Ø 广义表的数据元素有相对广义表的数据元素有相对次次序序；Ø 广义表的广义表的长度长度定义为最外层包含元素个数；定义为最外层包含元素个数；Ø 广义表的广义表的深深度度定义为所含括弧的重数；定义为所含括弧的重数；Ø广义表是一个广义表是一个多多层层次次的结构，可以用图形象地表的结构，可以用图形象地表 示。参见教材示。参见教材P108图图5.7。Ø广义表可为其它表所广义表可为其它表所共共享享；如广义表；如广义表D。广广义表的义表的结构结构特点特点(续续)：Ø广义表可以是一个广义表可以是一个递归递归的表；的表；递归表的深度是无穷值，长度是有限值。如递归表的深度是无穷值，长度是有限值。如E的的 长度为长度为2。Ø任何一个非空广义表任何一个非空广义表LS=(a1,a2,a3,an)均可分解均可分解任何一个非空广义表任何一个非空广义表LS=(a1,a2,a3,an)均可分解均可分解 为为表表头头GetHead(LS)=a1和和表表尾尾GetTail(LS)=(a2,a3,an)两部分。两部分。任何任何一个一个非空非空广广义表其表义表其表头头可可能能是是原子原子，也也可可 能能是是广广义表，义表，而而其表其表尾尾必必定是定是广广义表。义表。如：如：GetHead(B)=e GetTail(B)=( )GetHead(D)=A GetTail(D)=(B,C)由于（由于（B，C）为非空广义表，则可继续分解得到：）为非空广义表，则可继续分解得到：GetHead(B,C)=B GetTail(B,C)=(C)注意：注意：广广义表（）义表（）和和( ( ) )不同不同。前者是前者是长度长度为为0的的空空表表，对其不能做求表头的和，对其不能做求表头的和 表尾的运算；而后者是表尾的运算；而后者是长度长度为为1的的非空非空表表（只不过该（只不过该 表中唯一的一个元素是空表）。对其可进行分解，表中唯一的一个元素是空表）。对其可进行分解， 得到表头和表尾均为空表（）。得到表头和表尾均为空表（）。5.5 广广义表的存储义表的存储结构结构由于广义表由于广义表(a1,a2,a3,an)中的数据元素可中的数据元素可以具有不同的结构，（或是原子，或是广义表），以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，因此，难以用顺序存储结构表示，通常通常采采用用链式链式存储存储结构结构，每个数据元素可用一个结点表示每个数据元素可用一个结点表示。两两存储存储结构结构，每个数据元素可用一个结点表示每个数据元素可用一个结点表示。两两种结点种结点:一种是表结点，一种是原子结点。一种是表结点，一种是原子结点。Ø 广义表的头尾链表存储表示。广义表的头尾链表存储表示。Ø 参见教材参见教材P109图图5.9Ø 广义表的扩展线性链表存储表示。广义表的扩展线性链表存储表示。Ø 参见教材参见教材P110图图5.10 数组的定义和数组的定义和ADT 数组的顺序存储（行主序、列主序）数组的顺序存储（行主序、列主序） 矩阵的压缩存储矩阵的压缩存储 特殊矩阵：对称、三角、对角矩阵特殊矩阵：对称、三角、对角矩阵 稀疏矩阵稀疏矩阵三元组表示法三元组表示法本章小结本章小