数据结构第五章串讲复习要点

1、数据结构第五章多维数组和 xx 表第五章多维数组和 xx 表51 多维数组一般用顺序存储的方式表示数组。常用方式有：1)行优先顺序，将数组元素按行向量排列； 2)列优先顺序，将数组元素按列向量排列。计算地址的函数：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d52 矩阵的压缩存储为多个非零元素分配一个存储空间；对零元素不分配存储空间。1对称矩阵在一个n阶的方阵A中，元素满足Aij=Aji 0<=i,j<=n-1称为对称矩阵。元素的总数为：n(n+1)/2;设：I=i或j中大的一个数；J=i或j中小的一个数；则：k=I*(I+1)/2+J;地

2、址计算：LOC(Aij)=LOC(sak)=LOC(sa0)+k*d= LOC(sa0)+ (I*(I+1)/2+J )*d2三角矩阵以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素 均为常数C；下三角的主对角线上元素均为常数C。元素总数为：(n(n+1)/2)+1;以行优先顺序存放的Aij与SAk的关系：上三角阵：k=i*(2n-i+1)/2+j-i;下三角阵：k=i*(i+1)/2+j;3.对角矩阵所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为J | A零。|i-j|>(k-1)/2以行优先顺序存放的Aij与SAk的关系：k=2i+j522 稀疏矩阵

3、当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对 其压缩的方法有顺序存储和链式存储。1三元组表将表示稀疏矩阵的非零元素的三元组(行号、列号、值)按行或列优先的 顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三 元组表。其类型定义：#define maxsize 100 typedef int datype;typedef structint i,j;datype v; trituplenode;typedef struct trituplenode datamaxsize;int m,n,t;tritupletable;2.带行表的三元组表 在按行优先存储的

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

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

6、不分配空间。 特殊矩阵的概念： 所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 稀疏矩阵的概念： 一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀 疏矩阵。*特殊矩阵的类型：对称矩阵：满足 a(ij)二a(ji)。元素总数 n(n+1)/2。匸max(i,j), J=min(i,j),LOCa(ij)二LOC(sa0)+(l*(l+1)/2+J)*。三角矩阵：上三角阵：k=i*(2n-i+1)/2+j-i，LOCa(ij)二LOC(sa0)+k*d下三角阵：k二i*(i+1)/2+j, LOCa(ij)二LOC(sa0)+k*。对角矩阵：k=2i+j, LOCa(ij)

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

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

9、的算法。多维数组：(领会)多维数组的逻辑结构特征：一个m维数组An 1 n 2 . n m的每个元素都属于 m个向量，最多可以有 m个直接前趋和 m 个直接后继。多维数组的顺序存储结构及其地址计算方式 :计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个 线性序列存放在存储器中。排列的方式有两种，一是行优先顺序，也就是把数 组按一行的顺序依次排列。二是列优先顺序，就是把数组按一列列的顺序依次 排列。地址的计算方法：我们按行优先顺序排列的数组，是这样计算的，假设每个元素占用 d 个存 储单元，某个元素的地址就是它前面所有行所占的单元加上它所在行前面所有 列元素所占的单元数之和。不必

10、去死记公式。数组是一种随机存储结构的原因：因为在顺序存储的情况下，每一个元素都有与其下标相对应的地址，因此 可以对数组中的元素进行随机存储。矩阵的压缩存储：（领会）特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀 疏矩阵。我们在本章学习了对称矩阵、三角矩阵、对角矩阵这三种特殊矩阵。这三 种特殊矩阵可以进行压缩存储。主要要理解的是其下标变换方法。稀疏矩阵的压缩存储方式三元组表就是把非零元素的值和它所在的行号列 号做为一个结点存放在一起，用这些结点组成的一个线性表（三元组表 ）来表示这个稀疏矩阵。

11、但是这种压缩存储方式将失去随机存储功能。相关算法的理解要建立在对三元组表的结构的全面掌握的基础上。但是本 章的算法考试应不作要求。xx 表的概念 （领会 ）：广义表又称列表（Lists）是线性表的推广。就是说，广义表中的元素不仅可以 是数或一个结构，而且推广到可以是一个表（这个表又可以是广义表 ）。所以，广义表是n（n >0个元素a1,a2,a3.an的有限序列，其中的ai或者是原子或者是一 个广义表。（为什么叫原子？因为原子是作为结构上不可分割的成分。）xx 表表头和表尾的概念：若广义表LS非空（n > 1则这个广义表的第一个元素就是表头。（这个表头可 以是原子，也可以是该广义表

12、的子表。）而其余的元素组成的表称为LS的表尾（要注意，不是最后一个元素，这和队列的队尾是不同的 ），所以表尾必是一个子 表。广义表有两种表示法，一种是括号表示法，一种是图形表示法。括号表示 时，一般以大写字母表示广义表，以小写字母表示原子。如：A（x,L（a,b）。用图形表示时，图形中的分支结点对应广义表，非分支结点一 般表示原子，如果一个广义表与树 （形结构 ）相对应，这个广义表就是纯表。如果 一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。允许递归 的表称为递归表。有一个关系式：递归表 （包含）再入表（包含）纯表（树）（包含）线性表。可见，广义表是对线性表 和树的推广。广义表有两个特殊的基本运算，取表头 head（LS和取表尾 tail（LS） .（我们看到 tail 这个词就是尾巴，是一条尾巴，而不是末尾，它可能是一 个原子，但这个原子是作为子表来看待的 ）取表头和表尾的运算要在广义表非空的情况下进行。注意广义表（）表示是空表， （）则表示有一个元素的广义表，这个元素是一个空表。这两个运算很容易理解也应该掌握。第五章多维数组和xx表复习要点本章复习要点是：多维数组和xx表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素