数据结构与算法（C++版）课件第四章多维数组和广义表.pptx

《数据结构与算法（C++版）课件第四章多维数组和广义表.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法（C++版）课件第四章多维数组和广义表.pptx（47页珍藏版）》请在汇文网上搜索。

1、第四章-多维数组与广义表数据结构与算法(C语言版)线性结构非线性结构前几章介绍的数据结构都是线性结构，数据元素都属于原子类型，其值不分解使用。本章讨论的多维数组和广义表是线性结构的推广，从整体上看它们是多个元素组成的线性表，而从局部上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据结构。学习导引41 多维数组42 矩阵的压缩存储421 特殊矩阵422 稀疏矩阵43 广义表431 广义表的定义432 广义表的运算l理解二维数组的逻辑结构特征，掌握二维数组的顺序存储地址公式。l理解特殊矩阵的压缩存储方式，掌握根据下标计算存储地址的方法。l了解稀疏矩阵的表示及存储方法。l理解广义表

2、的定义、分类及运算。3主要内容目标一、多维数组的定义及存储1.多维数组的逻辑结构特征？数组中的元素具有相同类型，且下标一般具有固定的上界和下界。数组可以是一维的，也可以是多维的。下面以二维数组为例来分析。二维数组可以看成是由多个一维数组组成的。二维数组Amn既可看成由m个行向量组成的线性表，也可看成是由n个列向量组成的线性表。二维数组的逻辑结构具有如下特征：a00为开始结点，它没有直接前趋；am-1,n-1为终端结点，它没有直接后继；结点a0,n-1和am-1,0都有一个直接前趋和一个直接后继；除以上四个结点外，第一行和第一列的元素都有一个直接前趋和两个直接后继，最后一行和最后一列的元素都有两

3、个直接前趋和一个直接后继；其余的非边界元素aij同时处于第i+1行的行向量中和第j+1列的列向量中，都有两个直接前趋和两个直接后继。2.多维数组的存储以二维数组为例：二维数组一般采用顺序存储，因为元素个数固定，不插入删除。思考问题？如何让非线性的二维数组保存在线性的内存中？数据的排列原则方法：（1）先排列成线性序列；（2）再依次存放到内存中。排列方法：行优先和列优先 （1）行优先原则：一行一行排列。（2）列优先原则：一列一列排列。问题：C语言的数组属于哪种排列？行优先存储二维数组若二维数组Amn按行优先原则排列，其线性序列为：a00，a01，a0,n-1，a10，a11，a1,n-1，am-1

4、,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 二维数组的推广二维数组的逻辑特征可以推广到多维数组。三维数组中元素最多有三个前趋、三个后继二维数组的存储方法可以推广到多维数组。行优先或列优先排列，然后依次存储。二、矩阵的压缩存储工程中的矩阵（二维数组）往往阶数较大；而有效数据（非零元素）很少；

5、且分布没有规律；直接存储浪费大压缩存储。压缩存储方法压缩方法：只存储非零元素，对零元素不分配空间；为多个相同的非零元素分配一个存储空间。分别讨论特殊矩阵和稀疏矩阵的压缩存储。1.特殊矩阵特殊矩阵是指非零元素或零元素分布有一定规律的矩阵，可以根据规律来压缩存储。（1）对称矩阵（重点*）（2）三角矩阵（上三角阵和下三角阵）（3）对角矩阵不同的特殊矩阵中元素的分布规律不同，压缩存储的方法也不同。（1）对称矩阵满足aij=aji（1i，jn）的n阶方阵称为对称矩阵。压缩存储方法：对称矩阵中的数据元素按主对角线对称，只需存储下三角或上三角中的元素即可（重复元素只分配一个单元）。对称矩阵对于上三角或下三角

6、中的元素可按行优先或列优先存储。由此可得四种存储方法：行优先顺序存储下三角 列优先顺序存储下三角 行优先顺序存储上三角 列优先顺序存储上三角。aij可以通过公式计算出来：随机存取。重点：地址公式的推导。（1）行优先顺序存储下三角 （a）n阶对称矩阵 （b）行优先顺序存储下三角（c）对应的一维数组思考？（1）数组的大小？：n（n+1）/2（2）对应关系是什么？元素aij 存储在sa数组中的哪里？（3）下标k与i、j之间的关系：k=i（i+1）/2+j（4）上三角的aij怎么处理？答：上三角与下三角对应，例如a58=a85,若求上三角元素的值，那么将下标交换求地址。其他三种方法的下标计算公式(学会

7、推导)（2）列优先顺序存储下三角（3）行优先顺序存储上三角（4）列优先顺序存储上三角 （2）三角矩阵包括上三角阵和下三角阵两种。上三角阵的主对角线以下（不包括对角线）元素均为常数C，通常为0。图中为上三角阵。如何压缩存储？跟对称阵有什么区别与联系？三角矩阵压缩方法：相同元素只分配一个存储单元。上三角矩阵压缩存储：上三角没规律，依次存储，行优先或列优先。常数C=0，不分配空间；C0分配一个单元。则若C0，图中的上三角阵定义一个长度n（n+1）/2+1的数组，最后一个单元存储常数C。上三角矩阵地址公式 若上三角阵以行优先顺序存储，则地址公式为：若上三角阵以列优先顺序存储，地址公式会推导。下三角阵的

8、存储同理。（3）对角矩阵（了解）所有非零元素都集中在主对角线及主对角线两侧对称的带状区域，其余部分全部为零的n阶方阵为对角矩阵。常见的对角矩阵有三对角阵。如图：压缩存储方法：只存非零元。具体方法：也可以按照行优先顺序、列优先顺序或对角线顺序来进行存储，每一种地址公式不同。行优先顺序存储n阶三对角阵的一维数组如下：地址公式：k=2i+j。对角矩阵0 01 12 23 34 412123n-33n-3a a0000a a0101a a1010a a1111a a1212a a4444a a n-1,n-1n-1,n-12.稀疏矩阵定义：非零元素的个数远远小于矩阵元素的总个数。若mn的矩阵中有t个非

9、零元素，则定义矩阵的稀疏因子为=t/（mn），通常取0.05的矩阵为稀疏矩阵。稀疏矩阵的三元组表示压缩存储：通常采用只存储非零元素的方法。但是非零元素的分布没有规律，如何表示？答：三元组。稀疏矩阵A67的三元组表可表示为（1，2，11），（3，1，-3），（3，6，7），（4，4，6），（6，3，5）。若要唯一的表示一个稀疏矩阵，在存储三元组表的同时，还需要存储该矩阵的行数和列数，同时为了运算方便，一般还要存储非零元素的个数。稀疏矩阵的表示：三元组表+m+n+t稀疏矩阵的存储稀疏矩阵的存储就是三元组表的存储。三元组顺序表：顺序存储十字链表。：链接存储（1）三元组顺序表（1）将三元组按照行优先的

10、顺序排列成一个序列；（2）采用顺序存储方法存储该线性表；称为三元组顺序表。矩阵A的三元组顺序表如右图所示：0 01 12 23 34 4i i1 13 33 34 46 6j j2 21 16 64 43 3v v1111-3-37 76 65 5三元组顺序表存储结构的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;.（2）十

11、字链表链接存储结构：插入、删除效率较高。结点结构如图所示。i ij jv vdowndownrightright十字链表小节重点排列原则（行优先和列优先）地址公式（会推导）练习练习二维数组在采用顺序存储时，元素的排列方式有_和_两种。在特殊矩阵和稀疏矩阵中，经过压缩存储后会失去随机存取的特性的是_。设有一个10阶的对称矩阵A，以行优先顺序存储下三角元素，其中a00为第一元素，其存储地址为1，每个元素占一个字节，则a85的地址为_；若a11为第一元素，那么a85的地址为_。三、广义表1、广义的定义及表示：线性表的推广定义：n（n0）个元素a1，a2，ai，an的有限序列，元素ai可以是原子或者是

12、子表（子表亦是广义表）。符号表示：LS=（a1，a2，ai，an）广义表是一种递归的数据结构，因为广义表中的数据元素还可以是广义表。广义表与线性表广义表与线性表的区别与联系：线性表中的元素必须是原子。广义表允许表中的元素具有结构。当广义表中的所有元素都是原子时，此广义表就是线性表（广义表包含线性表）。广义表举例（1）A=（）空表（2）B=（a，b）只包含原子（3）C=（c，B）=（c，（a，b）既有原子，又有子表（4）D=（B，C，d）=（a，b），（c，（a，b），d）（5）E=（a，E）=（a，（a，（a，（）递归表一般：大写字母表示“表”，小写字母表示“原子”。大家观察：D和E有什么区别

13、？其他表示方法（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）广义表的图形表示：用非分支结点表示原子，用分支结点表示广义表（空表除外，空表中不含元素，所以也用非分支结点表示）。2、广义表的分类线性表：元素全为原子纯表：没有共享和递归（树）再入表：允许结点的共享但不允许递归（图）递归表举例嵌套括号表嵌套括号表示示展开写法展开写法带名字的广义表表示带名字的广义表表示长度长度备注备注A=A=（）（）A=（）A（）0空表B=B=（a a，b b）B=（a，b）B（a，b

14、）2线性表C=C=（c c，B B）C=（c，（a，b）C（c，B（a，b）2树D=D=（B B，C C）D=（a，b），（c，（a，b）D（B（a，b），C（c，（a，b）3图E=E=（a a，E E）E=（a，（a，（a，（）E（a，E（a，E（a，E（）递归表3、广义表的运算四个特殊的运算：取表头Head（LS）：第一个元素a1取表尾Tail（LS）：（a2，ai，an）求表深Depth（LS）：n求表长Length（LS）：括号嵌套的层数注：广义表的表头（Head）为广义表的第一个元素，广义表的表尾（Tail）为广义表中除第一个元素外，剩下所有的元素组成的广义表。广义表的运算四个特殊的

15、运算：取表头Head（LS）、取表尾Tail（LS）、求表深、求表长。广义表的表头（Head）为广义表的第一个元素，广义表的表尾（Tail）为广义表中除第一个元素外，剩下所有的元素组成的广义表。举例广义表广义表展开写法展开写法表头表头表尾表尾表深表深A=A=（）（）A=（）B=B=（a a，b b）B=（a，b）a（b）1C=C=（c c，B B）C=（c，（a，b）c（a，b）2D=D=（B B，C C）D=（a，b），（c，（a，b）（a，b）（c，（a，b）3E=E=（a a，E E）E=（a，（a，（a，（）a（E）练习练习下面说法正确的是：A.广义表的表尾通常是一个广义表，但有时也可以是一个原子；B.广义表的表尾总是一个广义表；C.广义表的表头总是一个广义表；D.广义表的表头总是一个原子。广义表常分成四类，分别是_、_、再入表和_。广义表（a,b）,（c,d）的表头是_，表尾是_，表长是_，表深_。本章重点重点重点矩阵压缩存储地址公式广义表的特点及运算