数据结构多维数组及广义表.ppt

第四章 多维数组及广义表,前几章介绍的数据结构都是线性结构，数据元素都属于原子类型，其值不分解使用。 本章讨论的多维数组和广义表是线性结构的推广，从整体上看它们是多个元素组成的线性表，而从局部上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据结构。,主要内容：,41 多维数组 多维数组的逻辑结构特征及存储方式 42 矩阵的压缩存储 特殊矩阵和稀疏矩阵的压缩存储 43 广义表 广义表的定义和运算,41 多维数组,一、多维数组的逻辑结构特征 数组中的元素具有相同类型，且下标一般具有固定的上界和下界。 数组可以是一维的，也可以是多维的。 本章主要以二维数组为例来分析多维数组的逻辑结构特征和存储结构。,二维数组可以看成是由多个一维数组组成的。例如，二维数组Amn既可看成由m个行向量组成的线性表，也可看成是由n个列向量组成的线性表。,二维数组的逻辑结构具有如下特征： a00为开始结点，它没有直接前趋； am-1,n-1为终端结点，它没有直接后继； 结点a0,n-1和am-1,0都有一个直接前趋和一个直接后继； 除以上四个结点外，第一行和第一列的元素都有一个直接前趋和两个直接后继，最后一行和最后一列的元素都有两个直接前趋和一个直接后继； 其余的非边界元素aij同时处于第i+1行的行向量中和第j+1列的列向量中，都有两个直接前趋和两个直接后继。,二、多维数组的存储 二维数组一般采用顺序存储。 由于内存单元是一维的线性关系，而二维数组中元素之间的关系是非线性的，所以若要顺序存储二维数组，首先需要将二维数组中的元素按照某种原则排列成点的线性序列，然后再依次存放到连续的存储单元中。 通常二维数组有行优先和列优先两种排列原则。 （1）行优先原则，是指先排列二维数组的第一行中的数据元素，再排列第二行中的数据元素，以此类推。 （2）列优先原则，是指先排列二维数组的第一列中的数据元素，再排列第二列中的数据元素，以此类推。,数据元素的存储地址可根据数组的首地址、元素的存储空间大小及元素的序号三个信息计算出来，从而实现随机存取。 若二维数组Amn按行优先原则排列，其线性序列为： a00，a01，a0,n-1，a10，a11，a1,n-1，am-1,n-1 存储后的内存状态如图所示: aij的地址为：LOC（aij）= LOC（a00）+（in+j） d,若二维数组Amn按列优先原则排列，则线性序列为： a00，a10，am-1,0，a01，a11，am-1,1，am-1,n-1 存储后的内存状态如图所示: aij的地址为：LOC（aij）= LOC（a00）+（jm+i） d,二维数组的逻辑特征和存储方法可以很容易地推广到多维数组。 例如三维数组可以看成是由二维数组组成的线性表，三维数组中的每个元素最多有三个直接前趋和三个直接后继。 同样，行优先原则和列优先原则也可以推广到多维数组，按行优先原则时先排最右的下标，按列优先原则时先排最左的下标。 得到行优先或列优先序列后，可以把它们依次存放在连续的存储空间中，这就是多维数组的顺序存储，同样可实现随机存取。,42 矩阵的压缩存储,计算机在处理工程问题时，通常使用二维数组来存储矩阵，但是实际问题中的矩阵往往阶数较大，而有效数据（非零元素）很少且分布没有规律，若用上面讨论的二维数组存储，其存储密度小（存储了大量的零元素），浪费了存储空间。 矩阵的压缩存储通常指在存储数据元素时，只存储非零元素，对零元素不分配空间；为多个相同的非零元素分配一个存储空间。 下面分别讨论特殊矩阵和稀疏矩阵的压缩存储。,一、特殊矩阵,特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。例如，对称矩阵、三角矩阵（上三角阵和下三角阵）及对角矩阵，特殊矩阵可以根据元素的分布规律来进行压缩存储。 不同的特殊矩阵中元素的分布规律不同，压缩存储的方法也不同。,1对称矩阵,满足aij=aji（1i，jn）的n阶方阵称为对称矩阵。 对称矩阵中的数据元素按主对角线对称，只需存储下三角或上三角中的元素即可。上三角或下三角中的元素可按行优先或列优先存储。由此可得四种存储方法： 行优先顺序存储下三角 列优先顺序存储下三角 行优先顺序存储上三角 列优先顺序存储上三角。 每种方法中元素的存储地址都可以通过公式计算出来，且具有随机存取的特点。,（1）行优先顺序存储下三角 以图（a）所示的n阶方阵为例，行优先顺序存储下三角时元素的排列顺序如图（b）所示，存储在一维数组中如图（c）所示。,（a） n阶对称矩阵 （b） 行优先顺序存储下三角,（c）对应的一维数组,设长度为n（n+1）/2的数组sa存储下三角中的元素。 设矩阵下三角中的某一个元素aij（ij）对应存储在一维数组的下标变量sak中，则上三角中的某一个元素aij（ij）存储在与aji对应的存储单元中。 下三角中任一数据元素aij （ij），位于第i+1行的第j+1列，则排在它前面的i行元素共有1+2+3+i-1+i=i（i+1）/2个，在第i+1行中排在它前面的元素还有j个，因此排在它前面的元素总共有i（i+1）/2+j个元素。由于一维数组的下标从0开始，因此元素aij在一维数组中的下标为i（i+1）/2+j。综上可得下标k的计算公式为：,同理可得其他三种方法存储时，元素aij在一维数组中 的下标计算公式： （2）列优先顺序存储下三角 （3）行优先顺序存储上三角 （4）列优先顺序存储上三角,2三角矩阵,包括上三角阵和下三角阵两种。 上三角阵的主对角线以下（不包括对角线）元素均为常数C，通常为0。而下三角阵主对角线以上（不包括对角线）元素均为常数C，通常为0。 利用压缩存储的原理，只为矩阵中下三角的相同元素C分配一个存储单元，且当常数C为零时，不分配存储空间。则为图中的上三角阵定义一个长度n（n+1）/2+1的数组，最后一个单元存储常数C。,若上三角阵以行优先顺序存储，则地址公式与对称矩阵的行优先顺序存储上三角的地址公式相似，元素的下标k为： 若上三角阵以列优先顺序存储，则地址公式与对称矩阵的列优先顺序存储上三角的地址公式相似，元素的下标k为： 下三角阵的存储同理。,3对角矩阵,所有非零元素都集中在主对角线及主对角线两侧对称的带状区域，其余部分全部为零的n阶方阵为对角矩阵。 常见的对角矩阵有三对角阵，对角阵可以按照行优先顺序、列优先顺序或对角线顺序来进行存储，每一种存储顺序下都存在非零元素的下标与一维数组中下标之间的对应关系。 以行优先顺序为例，n阶三对角阵以行优先顺序存储的一维数组如下： 排在aij前面的i行中共2+（i-1）3=3i-1个元素；在第i+1行中，排在它前面的还有j-（i-1）=j-i+1个元素；则排在元素aij之前的共2i+j个元素，即下标k=2i+j。,二、 稀疏矩阵,在一个矩阵中，若非零元素的个数远远小于矩阵元素的总个数，则该矩阵称为稀疏矩阵。若mn的矩阵中有t个非零元素，则定义矩阵的稀疏因子为=t/（mn），通常取0.05的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储，通常采用只存储非零元素的方法。 由于非零元素的分布没有规律，所以在存储非零元素值的同时，还需要存储非零元素的位置，即行号和列号。因此，矩阵中的每一个非零元素都由一个包括非零元素所在的行、列以及它的值构成的三元组（i，j，v）来唯一确定，这样就可以将稀疏矩阵用非零元素三元组的线性表来表示。 稀疏矩阵A67的三元组表可表示为（1，2，11），（3，1，-3），（3，6，7），（4，4，6），（6，3，5）。 稀疏矩阵的存储就可以转化为三元组表的存储，三元组表可以采用顺序存储或链接存储，对应稀疏矩阵的三元组顺序表和十字链表。 若要唯一的表示一个稀疏矩阵，在存储三元组表的同时，还需要存储该矩阵的行数和列数，同时为了运算方便，一般还要存储非零元素的个数。,1三元组顺序表,将三元组表中的三元组按照行优先的顺序排列成一个序列，然后采用顺序存储方法存储该线性表，称为三元组顺序表。矩阵A的三元组顺序表为：,三元组顺序表存储结构的C语言描述如下： #define MAX 16 /*大于非零元素个数的一个常数*/ typedef int DataType; typedef struct int i,j; /*非零元素所在的行、列*/ DataType v; /*非零元素值*/ Node; /* 三元组类型 */ typedef struct int m,n,t; /* 矩阵的行、列及非零元素的个数 */ Node dataMAX; /* 三元组表 */ Matrix; /* 三元组顺序表的存储类型 */ Matrix A,B;,下面以矩阵加法为例，分析在三元组顺序表上的算法实现。 设有同构的两个稀疏矩阵A和B，求矩阵Q=A+B。三个矩阵都用三元组顺序表存储。该算法的具体思想如下： （1）分别从矩阵A和B中取出编号最小的两个非零元素，并比较二者编号。 （2）若两个编号相等（行号、列号都相等），则求两个非零元素的和v，若v不等于零，则存入Q。 （3）若A中当前元素的编号较小（行号较小，或行号相等列号较小），则将A中当前元素存入Q；否则将B中当前元素存入Q。 （4）若A、B其中一个矩阵中的元素全部存入Q，则将另外一个矩阵中剩余元素依次存入Q中。,2十字链表,十字链表是稀疏矩阵的一种链接存储结构，在插入、删除操作时，不需要移动元素，效率较高。 十字链表存储稀疏矩阵的基本思想是：将稀疏矩阵中的每个非零元素都用一个包含五个域的结点来表示，存储非零元素所在行的行号域i，存储非零元素所在列的列号域j，存储非零元素值的值域v，以及行指针域right和列指针域down，分别指向同一行中的下一个非零元素结点和同一列中的下一个非零元素结点，其结点结构如图所示。,在十字链表中，同一行中的非零元素通过right域链接在一个单链表中，同一列中的非零元素通过down域也链接在一个单链表中，每个非零元素既处于某行链表中，也处于某列链表中，就形成了交叉的十字链表。 通常，为方便运算，稀疏矩阵中每一行的非零元素结点按其列号从小到大顺序由right域链成一个带表头结点的循环链表，同样每一列中的非零元素按其行号从小到大顺序由down域也链成一个带表头结点的循环链表。行列链表共用一个头结点。 为了方便地找到每一行或每一列，将每行（列）的头结点链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i行（列）的头结点的值域指向第i+1行（列）的头结点，依此类推，形成一个循环链表。这个循环链表又设一个头结点，这个头结点就是总头结点，总头结点的i和j域存储矩阵的行数和列数。,因为非零元素结点的值域是DataType类型，而表头结点中此域是指针类型，为了使整个结构的结点一致，该域用一个共用体类型来表示。十字链表结点的存储结构C语言描述如下： typedef int DataType; /*非零元素值的类型*/ typedef struct Node int i,j; /*非零元素所在的行、列*/ struct Node *down , *right; /*行指针域和列指针域*/ union v_next /*非零元素结点的值域*/ DataType v; struct node *next; MNode，*MLink;/*十字链表中结点和结点指针的类型*/,43 广义表,广义表是线性表的推广，它放松了对线性表中的元素必须是原子的限制，允许表中的元素具有结构。 广义表（General List），也称为列表（Lists）是n（n0）个元素a1， a2， ，ai， an的有限序列，元素ai可以是原子或者是子表（子表亦是广义表）。数据元素的个数n为广义表的长度。n0时称为空表，即表中不含任何元素。通常将非空的广义表（n0）记为： LS =（a1， a2， ，ai， an） 其中，LS是广义表的名字。a1为广义表的第一个元素，ai 为广义表的第i个元素。显然，广义表是一种递归的数据结构，因为广义表中的数据元素还可以是广义表。当广义表中的所有元素都是原子时，此广义表就是线性表。,下面是一些广义表的例子： （1）A=（） A是一个空表，其长度为0。 （2）B=（a，b） B是一个长度为2的广义表，它的两个元素都是原子，因此它就是一个线性表。 （3）C=（c，B）=（c，（a，b） C是长度为2的广义表，第一个元素是原子c，第二个元素是子表B。 （4）D=（B，C，d）=（a，b），（c，（a，b），d） D是长度为3的广义表，第一个元素和第二个元素都为子表，第三个元素为原子d。 （5）E=（a，E）=（a，（a，（a，（） E是长度为2的广义表，第一个元素是原子，第二个元素是E自身，它是一个无限递归的广义表。,广义表还有其他的表示方法，如： （1）带名字的广义表表示：在每个表的前面冠以该表的名字 A（） B（a，b） C（c，B（a，b） D（ B（a，b），C（c，（a，b），d） E（a，E（a，E（a，E（） （2）广义表的图形表示 用非分支结点表示原子，用分支结点表示广义表（空表除外，空表中不含元素，所以也用非分支结点表示）。,广义表分为：线性表、纯表、再入表和递归表四种。 当广义表中的元素全部都是原子时，广义表就是线性表，因此也可以说线性表是广义表的一种特殊形式。上图中的广义表B就是一个线性表。 若广义表中既包含原子，又包含子表，但没有共享和递归，如广义表C，则此时的广义表就是一棵树（将在第五章讨论），称这种广义表为纯表。 允许结点的共享但不允许递归的广义表为再入表，上图中的广义表D，子表B为共享结点，它既是表D的一个元素，又是子表C的一个元素。这样的广义表与数据结构的图形结构对应（将在第六章讨论）。 允许递归的表称为递归表