02331数据结构-04数组和广义表

第四章 多维数组和广义表

1. 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。

2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。

同一数组的不同元素通过不同的下标标识。（a1,a2,…,an) 3. 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。

4. 多维数组: 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……

三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量……

5. 数组的顺序存储方式: 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。 （1）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。 【例】二维数组Amn的按行优先存储的线性序列为： a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn （2）列优先顺序

将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。 【例】二维数组Amn的按列优先存储的线性序列为： a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn 6.数组元素的地址计算公式:

（1）按行优先顺序存储的二维数组Amn地址计算公式

LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d (注：此公式下界为1，如下界为0，则公式变为[i×n+j]) ①LOC(a11)是开始结点的存放地址（即基地址） ②d为每个元素所占的存储单元数

③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。

即顺序存储的数组是随机存取结构。

（2）按列优先顺序存储的二维数组Amn地址计算公式

LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d(注：此公式下界为1，如下界为0，则公式变为[j×m+i]) （3）按行优先顺序存储的三维数组Amnp地址计算公式

LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d

(注：此公式下界为1，如下界为0，则公式变为[i×n×p+j×p+k]) （4）下界不为1的二维数组的地址计算公式

①二维数组A[c1..d1,c2..d2]的地址计算公式： LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d ②下界为0的二维数组的地址计算公式（C语言中使用） LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d

7. 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。

矩阵的压缩：矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。 8. 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。 （1）对称矩阵

在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≤i，j≤n-1 （2）对称矩阵的压缩存储

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。

①按\行优先顺序\存储主对角线(包括对角线)以下的元素 （下三角矩阵中，元素总数为n(n+1)/2）。

即按a00,a10,a11,……，an-1,0,an-1,1…，an-1,n-1次序存放在一个向量sa[0．．n(n+1)/2-1]中

sa[0]=a00 ,sa[1]=a10 ,……,sa[n(n+1)/2-1]= an-1,n-1 ②元素aij的存放位置: sa[i×(i+1)/2+j]=aij

③aij和sa[k]之间的对应关系：

令I=max(i,j)，J=min(i,j)，则k和i，j的对应关系可统一为： k=I×(I+1)/2+J 0≤k

LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d，其中I=max(i,j)，J=min(i,j) 9. 三角矩阵的划分：

以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 ①上三角矩阵：如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。

②下三角矩阵：与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。

10.三角矩阵的压缩存储

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)/2]中，其中c存放在向量的最后一个分量中。

①上三角矩阵中aij和sa[k]之间的对应关系 k=i×(2n-i+1)/2+j-i 当i≤j k=n×(n+1)/2 当i＞j

②下三角矩阵中aij和sa[k]之间的对应关系 k=i×(i+1)/2+j 当i≥j k=n×(n+1)/2 当i＜j

三角矩阵的压缩存储结构是随机存取结构。 11. 对角矩阵

所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。

若|i-j|>(k-1)／2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

12. 稀疏矩阵:设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<

其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。

13. 三元组表：将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。

14.压缩存储结构上矩阵的转置运算

一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：A[i][j]=B[j][i]，0≤i

三元组表表示的矩阵转置的思想方法

第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。

第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data 15.三元组表的转置

由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。

按这种方法设计的算法，其基本思想是：对A中的每一列

col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。该算法的时间主要耗费在col和p的二重循环上：若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。

16.带行表的三元组表

为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。

17. 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。 其中：

①ai--或者是原子或者是一个广义表。

②广义表通常记作：Ls=( a1，a2，…，ai，…，an)。 ③Ls是广义表的名字，n为它的长度。 ④若ai是广义表，则称它为Ls的子表。 注意：

①广义表通常用圆括号括起来，用逗号分隔其中的元素。

②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。

③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。 ④广义表是递归定义的

广义表的深度：一个表的\深度\是指表展开后所含括号的层数。 18. 广义表的图形形状划分：

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

②允许结点共享的表称再入表，上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素；

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

上图(e)，表D是其自身的子表。

19. 广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。

根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。

head=(a，b)=a，tail(a，b)=(b) head(A，y)=A， tail(A，y)=(y)

由于tail(L)是非空表，可继续分解得到： head(tail(L))=b， tail(tail(L))=() 对非空表A和(y)，也可继续分解。 注意:

广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。

本文来源：https://www.bwwdw.com/article/k84p.html