1、第 5章 数组和广义表5 1数组的定义 二维数组：我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如。图 5 1 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5 2数组的顺序表示和实现一采用顺序存储结构：一般不作插入或删除操作 ,因此，采用顺序存储结构二存储顺序：存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据元素就有次序约定问题。 对二维数组可有两种存储方式：1以列序为主序 (co1umn major order)的存储方式，如图 5 2(a)所示2以行序为主序 (
2、row major order)的存储方式，如图 5 2(b)所示。三元素存储位置计算： 以行序为主序的二维数组存储结构为例 :二维数组 A中任一元素 aij的存储位置可由下式确定LOC(i,j) LOC(0,0)十 (b2i十 j)L (5-1)式中：b2是数组的第二维长度，即列数；L是每个数据元素占的存储单元个数；LOC(i,j)是 aij的存储位置；LOC(0,0)是 a00的存储位置，即二维数组 A的基地址或基址。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。 5 3矩阵的压缩存储压缩存储是指：为多个值相同的元只分配
3、一个存储空间；对零元不分配空间。5 3 1 特殊矩阵：一对称矩阵：1特点： aij=aji 1i,jn2存储：可压缩存储，不失一般性，以行主序存储下 三角中的元（包括对角线上的元）。 3映像关系：以数组 san(n+1)/2存储 n阶对称矩阵 A，称 san(n+1)/2为 n阶对称矩阵 A的压缩存储。（图 5.3）则 sak和矩阵元 aij间关系：二三角矩阵：1特点：下 (上 )三角矩阵指矩阵的上 (下 )三角 (不包括 对角线 )中的元均为常数 c或零的 n阶矩阵。2存储：存储其下 (上 )三角中的元和常数 c。3映像关系：以数组 san(n+1)/2存储， sa0可用来存储常数 c三对角
4、矩阵：1特点：所有的非零元都集中在以主对角线为中心的带状区域中。如图 5 4所示。2存储：亦可按某个原则 (或以行为主，或以对角线的顺序 )将其压缩存储到一维数组上。5 3 2 稀疏矩阵：一什么是稀疏矩阵：二抽象数据类型稀疏矩阵的定义：（ P96）三稀疏矩阵压缩存储：只存非零元。以图 5.5矩阵为例1三元组顺序表：#define MAXSIZE 12500 /稀疏矩阵中非 0元素的最大数目typedef struct int i,j; /非 0元素的行号、列号ElemType e; /非 0元素的值Triple; /三元组数据类型名typedef struct int mu， nu， tu; /稀疏矩阵的行数、列数、非 0元素的数目Triple dataMAXSIZE+1; /三元组数组， data0未用 TSMatrix; /三元组顺序表数据类型名
