数据结构教案第5章 数组和广义表
- 格式：pdf
- 大小：103.44 KB
- 文档页数：14
... ... a1n ⎤ ⎥ ... ... a2 n ⎥ ⎥ ... ... ... ⎥ ⎥ ... ... amn ⎥ ⎦
例：二维数组的两种存储方式：行序和列序 行序： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 列序： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm
5．3矩阵的压缩存储
在科学与工程计算问题中，矩阵是一种常用 的数学对象，在高级语言编制程序时，简单而又 自然的方法，就是将一个矩阵描述为一个二维数 组。矩阵在这种存储表示之下，可以对其元素进 行随机存取，各种矩阵运算也非常简单，并且存 储的密度为1。
但是在矩阵中非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，看起来存储密 度仍为1，但实际上占用了许多单元去存储重复的 非零元素或零元素，这对高阶矩阵会造成极大的 浪费，为了节省存储空间， 我们可以对这类矩阵 进行压缩存储：即为多个相同的非零元素只分配 一个存储空间；对零元素不分配空间。 带来的问题：如何实现数据元素aij通过下标到存储 空间地址的映射。
5．2数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内 存来表示多维数组，就必须按某种次序将数组元素 排成一列序列，然后将这个线性序列存放在存储器 中。 （数组定义后不变，用顺序存储比较自然）
Am×n
⎡ a11 ⎢ ⎢ a21 =⎢ ⎢ ... ⎢ ⎢am1 ⎣
a12 a22 ...ion求解（不管是按行存储和 按列存储）：一般是给出数组元素的首元素地址和每个元 掌握 素占用的地址空间并组给出多维数组的维数，然后要求你 求出该数组中的某个元素所在的位置 特殊矩阵的定义 特殊矩阵的压缩，包括对称矩阵，上（下）三角矩阵，对 角矩阵，具有某种特点的稀疏矩阵等 了解 掌握
当i ≥ j 当i p j
aij
●三角矩阵： 以主对角线划分，三角矩阵有上三角和下三角 两种。上三角矩阵的下三角（不包括主对角线）中的 元素均为常数。下三角矩阵正好相反，它的主对角线 上方均为常数。
三角矩阵中的重复元素c可共享一个存储空间，其 余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存 储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一 个分量中，下标变换后都指向该单元，如上三角矩阵 中：if i<j then k=n(n+1)/2;
0 1
以上规则可以推广到多维数组的情况：行优先顺序可规定 为先排最右的下标，从右到左，最后排最左下标：列优先顺序 与此相反，先排最左下标，从左向右，最后排最右下标。以三 维数组为例：
给出下标便可求得相应数组元素的存储位置 二维数组，设以行为主序（先存第一行）： LOC(i, j)=LOC(0, 0)+(b2×i+j)L 注：从0行开始，用初始地址加上前面出现的数据元素的个数
●数据元素个数
∏b
i =1
n
i
● 另一种看法
例：图5.1 二维数组中，每行或每列看成一个数据元素，则二维 数组是一个数据元素为线性表的线性表。 typedef ElemType Array2[m][n]; 等价于：typedef ElemType Array1[n]; typedef Array1 Array2[m]; 注：同理，n维数组由线性表辗转合成。
a11 a12 按行序为主序存放 ……. a1n n-1 a21 n a22 a11 a12 …….. a1n …….. a21 a22 …….. a2n a2n …………………. ………. am1 am1 am2 …….. amn am2 Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l …….. m*n-1 amn
a11
0
a21
1
a22
2
a31
3
ann
n(n+1)/2-1
sa[n(n+1)/2], aij→?sa[k]
a11 a 21 a 22 a 31 a 32 a 33 .... ..... .... .... .... ....
⎧ i (i − 1) ⎪ 2 + j −1 k =⎨ j ( j − 1) ⎪ + i −1 ⎩ 2
例：设有5对角矩阵A=(aij)20×20，按特殊矩阵压缩存储的方式将 其5条对角线上的元素存于数组B[m]中，计算元素A15,15的存储 位置。（东北大学1998年试题）
总 结
数组这一张要注意特殊矩阵压缩方面的题目
数组的定义以及如何理解它们是线性表的扩展 数组除了初始化和销毁之外只能进行存取和修改操作 识记 理解
第五章 数组和广义表
数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素 本身也是一种线性表。 5．1数组的定义 ADT Array{ 数据对象：ji=0,...,bi-1, i=1,2,..,n D={aj1j2...jn|n(>0)称为数组的维数，bi是数组第i维的长度， ji是数组元素第i维下标，aj1j2...jn ∈ElemSet} 数据关系：RI={R1,R2,...,Rn} Ri={<aj1...ji...jn,aj1...ji+1...jn>| \*每个元素受n个关系的制约，在每个关系中都有直接后继 0≤jk≤bk-1, 1≤k≤n,且k≠i, 0≤ji≤bi-2, aj1...ji...jn,aj1...ji+1...jn ∈D, i=2,..,n} 基本操作： 存取元素；修改元素； }ADT Array;
●三对角矩阵： 所有的非零元素集中在以主对角线为了中心的带状区域 中，即除了主对角线和主对角线相邻两侧的若干条对角线上的 元素之外，其余元素皆为零。下图给出了一个三对角矩阵：
a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0 0 a32 a33 a34 0 ……… 0 …………………………… 0 0 … an-1,n-2 an-1,n-1 an-1,n 0 0 … …an,n-1 ann.
5．3．1特殊矩阵（分布有规律） 对称矩阵： aij=aji 1≤i,j≤n 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上 三角或下三角中的元素，让每两个对称的元素共享一个存储空间 ，这样，能节约近一半的存储空间。 为每一对对称元分配一个存储空间，需n(n+1)/2个存储单 元，存储方式见图5.3（按行存）, 为了便于访问对称矩阵A中的 元素，我们必须在aij和sa[k] 之间找一个对应关系。
