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

第四章 多维数组和广义表 1. 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。 ???同一数组的不同元素通过不同的下标标识。（a1,a2,…,an) 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。 多维数组 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量…… ???三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量…… 数组的顺序存储方式 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。（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数组元素的地址计算公式（1）按行优先顺序存储的二维数组Amn地址计算公式 ????? LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d×n+j]) ??? ①LOC(a11)是开始结点的存放地址（即基地址） 　　d为每个元素所占的存储单元数 　　由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。 （2）按列优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d×m+i]) （3）按行优先顺序存储的三维数组Amnp地址计算公式 LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d×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 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。（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(j)，J=min(j)，则k和i，j的对应关系可统一为： ??k=I×(I+1)/2+J 0≤kn(n+1)/2 （3）对称矩阵的地址计算公式LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d，其中I=max(i,j)，J=min(j) 9. 三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 上三角矩阵如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。 下三角矩阵与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。 10.三角矩阵的压缩存储三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1