第5章 数组和广义表
本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个表。要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的压缩存储的有关内容。
重点提示：
●多维数组的存储方式和存取特点
●特殊矩阵的存储
●稀疏矩阵的存储
●广义表的表示形式
5-1 重点难点指导
5-1-1 相关术语
1．特殊矩阵
要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。
2．对称矩阵
要点：一种特殊矩阵；n阶方阵的元素满足性质：aij=aji （0≤i，j≤n-1）。
3．三角矩阵
要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，均为常数c，称为下三角矩阵。
4．对角矩阵
要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。
5．稀疏矩阵
要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。
6．三元组表
要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按行优先的顺序排列；得到结点均是三元组的线性表。
7．广义表
要点：是线性表的推广；是n个元素a1,a2,…,an的有限序列；其中ai或者是原子或者是广义表；通常记为LS=(a1,a2,…,an)，LS为广义表的名字。
5-1-2 多维数组
1．对n维数组逻辑结构的理解
n维数组可视为由n-1维数组为元素的线性结构。
举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中每个一维数组又由n个单元素组成。
2．数组的顺序存储方式
（1）行优先顺序——将数组元素按行向量排列，即第i＋1行紧接在第i行后面。如Amn的存储序列为：
（2）列优先顺序——将数组元素按列向量排列，即第i＋1列紧接在第i列后面，如Amm的存储序列为：
3．数组元素的存储地址（以行优先顺序计算，假设每个元素为d个单元）
（1）二维数组中aij的地址
LOC(aij)= LOC(a11)+[(i-1)*n+j-1]*d
在C（Visual C++）语言中，因数组下标从0起，故
LOC(aij)=LOC(a00)+(i*n+j)*d
（2）三维数组中aijk的地址（Amnp）
LOC(aijk)= LOC(a111)+ [(i-1)*n*p+(j-1)*p+(k-1)]*d
在Visual C++语言中，因数组下标从0起，故
LOC(aijk)=LOC(a000)+(i*n*p+j*p+k)*d
（3）对于一般的二维数组A[c1 … d1,c2 … d2]
LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2]*d
5-1-3 特殊矩阵
矩阵在存储中常用二维数组，而对于一些特殊的矩阵，可将其按一定规律压缩存储在一维向量中，如sa[ ]中。
1．对称矩阵
（1）特点：在n阶方阵A中有aij=aji （0≤i，j≤n-1）。
（2）存储：按行优先的存储顺序为：a00,a10,a11,a21,a22, … an-1 0,an-1 1 … an-1 n-1
（3）元素的二维下标(i，j)与其在一维向量中的位置k的对应关系：
I=max(i，j)， J=min(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．三角矩阵
（1）特点：n阶方阵A中，上三角或下三角（不包括主对角线）元素均为常数c。
（2）存储：按行优先存放。
上三角矩阵的存储序列为：
下三角矩阵的存储序列为：
（3）元素的二维下标（i,j）与其在一维向量中的位置k的对应关系：
上三角矩阵：
i≤ j
i>j （常数c的位置）
下三角矩阵：
i≤ j
i>j （常数c的位置）
即有：LOC(aij)=LOC(sa[k])
3．对角矩阵
（1）特点：除对角线和其相邻两侧的若干条对角线上的元素之外，其余元素皆为零。
（2）存储：以3条带的带状矩阵为例，即主对角线两侧各有一条带的元素，见图5-1。
其存储特点为第一行和最后一行为两个元素，其他各行为3个元素。
a00 a01
a10 a11 a12
a21 a22 a23
… … …
an-2n-3 an-2n-2 an-2n-1
an-1n-2 an-1n-1
图5-1 n×n的带状矩阵
（3）按行优先的存储序列为：
元素的二维下标(i,j)与其在一维向量中的位置k的对应关系：
k=3i-1+j-i＋1=2i+j
即有：LOC(aij)＝LOC(sa[k])
说明：由于对向量起始下标的定义不同，对特殊矩阵压缩存储位置的计算表达式也会有所不同，读者应掌握其分析计算的方法，根据具体情况推出相应计算表达式。
5-1-4 稀疏矩阵
（1）特点：矩阵中非零元素的个数远小于矩阵元素的总数。
（2）存储：
① 三元组表
特点：按行优先（或列优先）；仅存非零元素；每个非零元素存贮3个信息（行、列、值）；还需存上矩阵的行数、列数及非零元素个数。
存储类型定义：
#define Smax …… //定义三元组表的大小
typedef int DataType; //定义三元组表的元素值的类型
typedef struct{ //三元组表元素结构
int i,j; //非零元素的行、列号
DataType v; //非零元素的值
}SPNode;
typedef struct{ //三元组表类型
SPNode data[SMax]; //三元组表空间
int mu,nu,tu; //矩阵的行数、列数及非零元个数
}SPMatrix;
例：如图5-2（a）所示的稀疏矩阵A存储的三元组表如图5-2（b）所示。
其中定义三元组表类型的变量SPMatrix *a，用三元组表a存储矩阵A。
图5-2 稀疏矩阵A与其三元组表和行表的示意
② 带行表的三元组表
特点：在按行优先存储的三元表中，加入一行表记录，稀疏矩阵每行的非零元素在三元组表的起始位置。
目的：便于矩阵运算。
存储类型定义：
#define MaxRow ……
typedef struct{
SPNode data[MaxSize];
int RowTab[MaxRow];
int mu,nu,tu;
}RSPMatrix;
例：如图5-2（a）所示的稀疏矩阵A存储的三元组表如图5-2（b）所示；行表如图5.2（c）所示。其中定义a为带行表的三元组表类型的变量，用三元组表a存储矩阵A。
5-1-5 广义表
（1）特点
① n个元素的有限序列。
② 每个元素或者是原子或者是一个广义表。
（2）有关概念：
① 广义表的长度
要点：若广义表LS＝(a1,a2,…,an)，则其长度为n。
② 表头
要点：广义表的第一个元素。
若广义表LS＝(a1,a2,…,an)，则a1是其表头。
注意表头是原表中的一个元素。
③ 表尾
要点：广义表除第一个元素之外其余元素组成的子表。
若广义表LS＝(a1数组和链表,a2,…,an)，则（a2，…，an）是其表尾。
注意表尾仍是表。
④ 纯表
要点：与树对应的广义表；限制了表中成份的共享与递归。
⑤ 再入表
要点：允许结点共享的广义表。
⑥ 递归表
要点：允许递归的广义表。
⑦ 表的深度
要点：表展开后所含括号的层数。
（3）表示
① 括号表示法
格式：表名（表元素列表）
举例：
ⅰ）线性表 L(a,b)
说明：表名为L，表的两个元素a和b为同一类型，是广义表退化为线性表。
表L长度为2，深度为1。
ⅱ）纯表 A(x,L(a,b))
说明：表名为A，表内有两个元素，一个是原子x，另一个是表L。
表A长度为2，深度为2。
ⅲ）再入表 C(A(x,L(a,b)),B(A(x,L(a,b)),y))
说明：表名为C，表内有两个表元素，分别是表A和表B。
其中表A又是表B中的第一个元素，即被表B所共享。
表C长度为2，深度为4。
ⅳ）递归表 D(a,D(a,D(…）））
说明：表名为D，表内有两个元素，一个是原子，另一个是表D自身。
表D长度为2，深度为∞。
② 图形表示法
方法：结点表示表或是原子；若表示有n个元素的表结点，该表结点就有n条出边指向这n个元素；原子结点只有入边没有出边。
举例：用括号表示法列举的4个例子的图形表示如图5-3所示。
图5-3 广义表的图形表示
（4）几种广义表之间的关系
递归表 再入表 纯表 线性表
（5）两个基本运算
① head(LS) 取表LS的表头。
② tail(LS) 取表LS的表尾。
5-2 典型例题解析
5-2-1 填空题
1．数组M中每个元素的长度是3个字节，行下标i从0到7，列下标j从0到9，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M[7][5]的起始地址为（ ）；若按列优先方式存放，元素M[7][5]的起始地址为（ ）。
【分析】
按行优先方式存储时，M[7][5]的前面已经存放了75（7×10＋5=75）个元素，它们共占用了75×3=225个字节，所以M[7][5]的起始地址为EA＋225。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论