数据结构第五章(多维数组与广义表)串讲复习要点

数据结构第五章多维数组和xx表

第五章多维数组和xx表

5．1多维数组

一般用顺序存储的方式表示数组。常用方式有：1）行优先顺序，将数组元素按行向量排列；2）列优先顺序，将数组元素按列向量排列。

计算地址的函数：

LOC(Aij)=LOC(Ac1c2)+((i-c1)*(d2-c2+1)+j-c2)*d

5．2矩阵的压缩存储

为多个非零元素分配一个存储空间；对零元素不分配存储空间。

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;

地址计算：

LOC(Aij)=LOC(sa[k])=LOC(sa[0])+k*d= LOC(sa[0])+ (I*(I+1)/2+J )*d

2．三角矩阵

以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。

元素总数为：

(n(n+1)/2)+1;

以行优先顺序存放的Aij与SA[k]的关系：

上三角阵：

k=i*(2n-i+1)/2+j-i;

下三角阵：

k=i*(i+1)/2+j;

3.对角矩阵

所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为零。

|i-j|>(k-1)/2

以行优先顺序存放的Aij与SA[k]的关系：

k=2i+j

5．2．2稀疏矩阵

当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。

1．三元组表

将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。

其类型定义：

#define maxsize 100

typedef int datype;

typedef struct{

int i,j;

datype v;

}trituplenode;

typedef struct{

trituplenode data[maxsize];

int m,n,t;

}tritupletable;

2.带行表的三元组表

在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义：

#define maxrow 100

typedef struct{

tritulpenode data[maxsize];

int rowtab[maxrow];

int m, n, t;

}rtritulpetable;

5.3xx表的概念

广义表是线性表的推广。广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LS。

若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。

表的xx是指表展开后所含括号的层数。

把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；

允许结点共享的表称为再入表；

允许递归的表称为递归表；

相互关系：

线性表∈纯表∈再入表∈递归表；

广义表的特殊运算：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。

***************************************************************** *********************

矩阵的压缩存储：

为多个相同的非零元素分配一个存储空间；对零元素不分配空间。

特殊矩阵的概念：

所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。

稀疏矩阵的概念：

一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。

***************************************************************** ********************

特殊矩阵的类型：

·对称矩阵：

满足a(ij)=a(ji)。元素总数n(n+1)/2。I=max(i,j)，J=min(i,j)，

LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d。

·三角矩阵：

·上三角阵：

k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d。

·下三角阵：

k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d。

·对角矩阵：

k=2i+j，LOCa(ij)=LOC(sa[0])+k*d。

***************************************************************** ********************

稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。

***************************************************************** *******

广义表是n(n≥0)个元素的有限序列，其中的元素是原子或者是一个广义表。

xx表表头和表尾的概念：

·若广义表LS非空(n≥1),则这个广义表的第一个元素就是表头。

·其余的元素组成的表称为LS的表尾，所以表尾必是一个子表。

广义表有两种表示法，一种是括号表示法，一种是图形表示法。

广义表与树(形结构)相对应，这个广义表就是纯表。

如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。

允许递归的表称为递归表。

线性表∈纯表(树)∈再入表∈递归表。可见，广义表是对线性表和树的推广。

xx表有两个特殊的基本运算：

·取表头head(LS)：

取表中的第一个数据元素，不能对空表操作。

·取表尾tail(LS)；取除表头外，其余数据元素构成的子表，不能对空表操作。

前面我们学习的线性表、栈、队列和串都是线性结构，本章起学习的是非线性结构。它们的逻辑特征是：

一个数据元素可能有多个直接前趋和多个直接后继。

本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。

多维数组：

(领会)

多维数组的逻辑结构特征：

一个m维数组An 1 n 2 ... n m的每个元素都属于m个向量，最多可以有m 个直接前趋和m个直接后继。

多维数组的顺序存储结构及其地址计算方式:

计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性序列存放在存储器中。排列的方式有两种，一是行优先顺序，也就是把数组按一行的顺序依次排列。二是列优先顺序，就是把数组按一列列的顺序依次排列。地址的计算方法：

我们按行优先顺序排列的数组，是这样计算的，假设每个元素占用d个存储单元，某个元素的地址就是它前面所有行所占的单元加上它所在行前面所有列元素所占的单元数之和。不必去死记公式。

数组是一种随机存储结构的原因：

因为在顺序存储的情况下，每一个元素都有与其下标相对应的地址，因此可以对数组中的元素进行随机存储。

矩阵的压缩存储：

(领会)

特殊矩阵的概念：

所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。

稀疏矩阵的概念：

一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。

我们在本章学习了对称矩阵、三角矩阵、对角矩阵这三种特殊矩阵。这三种特殊矩阵可以进行压缩存储。主要要理解的是其下标变换方法。

稀疏矩阵的压缩存储方式三元组表就是把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。但是这种压缩存储方式将失去随机存储功能。

相关算法的理解要建立在对三元组表的结构的全面掌握的基础上。但是本章的算法考试应不作要求。

xx表的概念(领会)：

广义表又称列表(Lists),是线性表的推广。就是说，广义表中的元素不仅可以是数或一个结构，而且推广到可以是一个表(这个表又可以是广义表)。所以，广义表是n(n≥0)个元素a1,a2,a3...an的有限序列，其中的ai或者是原子或者是一个广义表。(为什么叫原子?因为原子是作为结构上不可分割的成分。)

xx表表头和表尾的概念：

若广义表LS非空(n≥1 ),则这个广义表的第一个元素就是表头。(这个表头可以是原子，也可以是该广义表的子表。)而其余的元素组成的表称为LS的表尾

(要注意，不是最后一个元素，这和队列的队尾是不同的)，所以表尾必是一个子表。

广义表有两种表示法，一种是括号表示法，一种是图形表示法。括号表示时，一般以大写字母表示广义表，以小写字母表示原子。如：

A(x,L(a,b))。用图形表示时，图形中的分支结点对应广义表，非分支结点一般表示原子，如果一个广义表与树(形结构)相对应，这个广义表就是纯表。如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。允许递归的表称为递归表。

有一个关系式：

递归表(包含)再入表(包含)纯表(树)(包含)线性表。可见，广义表是对线性表和树的推广。广义表有两个特殊的基本运算，取表头head(LS)和取表尾

tail(LS) .(我们看到tail这个词就是尾巴，是一条尾巴，而不是末尾，它可能是一个原子，但这个原子是作为子表来看待的)

取表头和表尾的运算要在广义表非空的情况下进行。注意广义表()表示是空表，(())则表示有一个元素的广义表，这个元素是一个空表。

这两个运算很容易理解也应该掌握。

第五章多维数组和xx表复习要点

本章复习要点是：

多维数组和xx表的逻辑结构特征：

它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。

多维数组的两种顺序存储方式：

行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。

几种特殊矩阵的特征及其压缩存储地址对应关系。

稀疏矩阵的三元组表示(画图形表示)。

xx表是线性表的推广，也是树的推广。

能画出xx表的图形表示法。

广义表的取表头运算与取表尾运算要注意，表头是广义表的第一个元素，它不一定是原子，表尾则必是子表。

本章可能出选择题、填空题和应用题。