2022年数据结构串讲+复习要点 .pdf

《2022年数据结构串讲+复习要点 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构串讲+复习要点 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第五章多维数组和广义表第五章多维数组和广义表51 多维数组一般用顺序存储的方式表示数组。常用方式有：1）行优先顺序，将数组元素按行向量排列；2）列优先顺序，将数组元素按列向量排列。计算地址的函数：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d52 矩阵的压缩存储为多个非零元素分配一个存储空间；对零元素不分配存储空间。1 对称矩阵在一个 n 阶的方阵 A 中，元素满足 Aij=Aji0=i,j(k-1)/2以行优先顺序存放的Aij 与 SAk 的关系：k=2i+j;522 稀疏矩阵当矩阵 A 中有非零元素 S个，且 S远小于元素总数时，称为稀疏矩

2、阵。对其压缩的方法有顺序存储和链式存储。1 三元组表将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类型定义：#define maxsize10000typedef int datatype;typedef structint i,j;datatypev;trituplenode;typedef structtrituplenode datamaxsize;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -int m,n,t;tritupletable;2.带行表的三元组表在按行

3、优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义：#define maxrow 100typedef structtritulpenode datamaxsize;int rowtabmaxrow;int m,n,t;rtritulpetable;5.3 广义表的概念广义表是线性表的推广。广义表是 n 个元素的有限序列，元素可以是原子或一个广义表，记为 LS。若元素是广义表称它为LS 的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。表的深度是指表展开后所含括号的层数。把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；允许结点共享的表称为再入表

4、；允许递归的表称为递归表；相互关系：线性表纯表再入表递归表；广义表的特殊运算：1）取表头 head(LS)；2）取表尾 tail(LS);附二:第五章多维数组和广义表*数组一般用顺序存储的方式表示。存储的方式有：行优先顺序，也就是把数组逐行依次排列。PASCAL、C 列优先顺序，就是把数组逐列依次排列。FORTRAN*地址的计算方法：按行优先顺序排列的数组：LOCa(ij)=LOCa(11)+(i-1)*n+(j-1)*d。按列优先顺序排列的数组：LOCa(ij)=LOCa(11)+(j-1)*n+(i-1)*d。*矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。特殊

5、矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。*名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -*特殊矩阵的类型：对称矩阵：满足 a(ij)=a(ji)。元素总数 n(n+1)/2。I=max(i,j)，J=min(i,j)，LOCa(ij)=LOC(sa0)+(I*(I+1)/2+J)*d。三角矩阵：上三角阵：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa0)+k*d。下三角阵：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa0)

6、+k*d。对角矩阵：k=2i+j，LOCa(ij)=LOC(sa0)+k*d。*稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。*广义表是 n(n0)个元素的有限序列，其中的元素是原子或者是一个广义表。广义表表头和表尾的概念：若广义表 LS 非空(n1),则这个广义表的第一个元素就是表头。其余的元素组成的表称为LS 的表尾，所以表尾必是一个子表。广义表有两种表示法，一种是括号表示法，一种是图形表示法。广义表与树(形

7、结构)相对应，这个广义表就是纯表。如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。允许递归的表称为递归表。线性表纯表(树)再入表递归表。可见，广义表是对线性表和树的推广。广义表有两个特殊的基本运算：取表头 head(LS)：取表中的第一个数据元素，不能对空表操作。取表尾 tail(LS)；取除表头外，其余数据元素构成的子表，不能对空表操作。前面我们学习的线性表、栈、队列 和 串 都是 线性结构，本章起学习的是非线性结构。它们的逻辑特征是：一个数据元素可能有多个直接前趋和多个直接后继。本章 重点 是熟悉 多维数组的 存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算

8、，难点是 稀疏矩阵的压缩存储表示下实现的算法。多维数组：(领会)多维数组的 逻辑结构特征：一个 m 维数组 An 1 n 2.n m 的每个元素都属于m 个向量，最多可以有m 个直接前趋和 m 个直接后继。多维数组的 顺序存储结构及其 地址计算方式:计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性序列存放在存储器中。排列的方式有两种，一是 行优先顺序，也就是把数组按一行一行的顺序依次排列。二是列优先顺序，就是把数组按一列列的顺序依次排列。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -地址的计算方法：我们按行优先顺序排列的数组，是这样计算的，假设每个

9、元素占用 d 个存储单元，某个元素的地址就是它前面所有行所占的单元加上它所在行前面所有列元素所占的单元数之和。不必去死记公式。数组是一种随机存储结构的原因：因为在顺序存储的情况下，每一个元素都有与其下标相对应的地址，因此可以对数组中的元素进行随机存储。矩阵的压缩存储：(领会)特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。我们在本章学习了对称矩阵、三角矩阵、对角矩阵这三种特殊矩阵。这三种特殊矩阵可以进行压缩存储。主要要理解的是其下标变换方法。稀疏矩阵的压缩存储方式三元组表就是把非零元素

10、的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。但是这种压缩存储方式将失去随机存储功能。相关算法的理解要建立在对三元组表的结构的全面掌握的基础上。但是本章的算法考试应不作要求。广义表的概念(领会)：广义表 又称列表(Lists),是线性表的推广。就是说，广义表中的元素不仅可以是数或一个结构，而且推广到可以是一个表(这个表又可以是广义表)。所以，广义表是 n(n0)个元素 a1,a2,a3.an的有限序列，其中的ai 或者是原子或者是一个广义表。(为什么叫原子?因为原子是作为结构上不可分割的成分。)广义表 表头 和 表尾 的概念：若广义表

11、LS 非空(n1),则这个广义表的第一个元素就是表头。(这个表头可以是原子，也可以是该广义表的子表。)而 其余的元素 组成的表称为 LS 的表尾(要注意，不是最后一个元素，这和队列的队尾是不同的)，所以表尾必是一个子表。广义表有两种表示法，一种是 括号表示 法，一种是 图形表示法。括号表示时，一般以大写字母表示广义表，以小写字母表示原子。如：A(x,L(a,b)。用图形表示时，图形中的分支结点对应广义表，非分支结点一般表示原子，如果一个广义表与树(形结构)相对应，这个广义表就是纯表。如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。允许递归的表称为递归表。有一个关系式：递归表(包

12、含)再入表(包含)纯表(树)(包含)线性表。可见，广义表是对线性表和树的推广。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -广义表有两个特殊的基本运算，取表头 head(LS)和 取表尾 tail(LS).(我们看到tail 这个词就是尾巴，是一条尾巴，而不是末尾，它可能是一个原子，但这个原子是作为子表来看待的)取表头和表尾的运算要在广义表非空的情况下进行。注意广义表()表示是空表，()则表示有一个元素的广义表，这个元素是一个空表。这两个运算很容易理解也应该掌握。第五章 多维数组和广义表复习要点本章复习要点是：多维数组和广义表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表示(画图形表示)。广义表是线性表的推广，也是树的推广。能画出广义表的图形表示法。广义表的取表头运算与取表尾运算要注意，表头是广义表的第一个元素，它不一定是原子，表尾则必是子表。本章可能出选择题、填空题和应用题。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -