当前位置：文档之家 › 第五章 数组和广义表

第五章 数组和广义表

  • 格式：ppt
  • 大小：149.00 KB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

数据结构第五章 数组与广义表

数据结构第五章 数组与广义表
an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<j
q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

第五章数组和广义表

第五章数组和广义表
ai,1 ai,2 … ai,j … ai,n an,1 an,2… an,j … an,n
i(i-1)/2+j-1 (i≥j) k= 第五章数j组(j和-1广)义/2表+i-1 (i＜j)
第五章数组和广义表
5.1 数组的类型定义 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.4 广义表
第五章数组和广义表
5.1 数组的定义和运算
数组是一种数据类型。从逻辑结构上看，数 组可以看成是一般线性表的扩充。二维数组可 以看成是线性表的线性表。例如：
Am×n=
a11 a12 … a1j ……
LO(0C ,0,..0.) , ci ji (Cn=L,ci-1=bi*ci,1<i≤n) i1
数组元素的存储位置是其下标的线性函数，由于计算各 个元素存储位置的时间相等，所以存储数组中任一元素的 时间也相等，称具有这一第五特章数点组和的广义存表 储结构为随机存储结构。
N维数组数据元素存储地址计算
i= （ai1，ai2， …，aij ，…，ain）。
B
‖
a11 a12 … a1j … a1n
1
……
…
Am×n= ai1 ai2 … aij … ain
i
……
…
am1 am2 … amj … amn
m
第五章数组和广义表
看一个二维数组的简单情况。
D={aij|0≤i≤b1-1,0≤j≤b2-1, aij∈ ElemType}
}
第五章数组和广义表
5.3 矩阵的压缩存储
• 压缩存储：为多个值相同的元素只分配一个存 储空间，对零元素不分配空间。
• 目的：节省存储空间 • 任务：压缩存储矩阵并使矩阵的运算有效进行。 • 矩阵的存储：二维数组 • 可压缩存储的矩阵有两类:

数据结构-第五章 数组与广义表-文档资料

数据结构-第五章 数组与广义表-文档资料

上 三 角 矩 阵 下 三 角 矩 阵
a00 a10 a 20 an10
0 1 2
a01 a11 a21 an11
3 4
a02 a12 a22 an12
5

6 7
a0 n1 a1n1 a2 n1 an1n1
行 列 值 (row) (col) (value) 0 4 91 1 1 11 2 5 28 3 0 22 3 2 -6 5 1 17 5 3 39 6 0 16
用三元组表表示的稀疏矩阵及其转置
行 列 值 (row) (col) (value) 0 3 22 0 6 15 1 1 11 1 5 17 2 3 -6 3 5 39 4 0 91 5 2 28 行 列 值 (row) (col) (value) 0 4 91 1 1 11 2 5 28 3 0 22 3 2 -6 5 1 17 5 3 39 6 0 16
4 5 6 7 8 9 10
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1
三对角矩阵中除主对角线及在主对角线上 下最临 近的两条对角线上的元素外，所有其它元素均为 0。总共有3n-2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存放在 一维数组 B 中，且a00存放于B[0]。 在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1 在一维数组 B 中 A[i][j] 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所 以元素 A[i][j] 在 B 中位置为 k = 2*i + j。
三对角矩阵的压缩存储

数据结构第五章数组和广义表

数据结构第五章数组和广义表
typedef elemtype Array2[m][n]; 等价于
typedef elemtype Array1[n]; typedef Array1 Array2[m]; 同理，可以用 n-1 维数组的数据类型来定义 n 维数组。
8
第8页
5．2 数组的顺序存贮结构
一、数组的顺序表示和实现
(1) 类型特点 ① 只有引用型操作，一般不作插入或删除操作； ② 数组是多维的结构，而存储空间是一个一维的结构。
第 17 页
(2) 压缩存储的有关概念 ① 压缩存储：为多个值相同的元素分配一个存储空间，对零 元不分配空间。 ② 特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定 规律。 ③ 稀疏矩阵：值相同的元素或者零元素在矩阵中的分布无规 律。
第 18 页
(3) 特殊矩阵
① 概念：若n阶矩阵 A 中的元满足：aij=aji 1≤i,j≤n，则 称为n 阶对称矩阵。
第1页
第五章 数组和广义表
5. 1 数组的定义 5.2 数组的顺序存储结构 5. 3 矩阵的压缩存储 5. 4 广义表的定义 5.5 广义表的存储结构
第2页
第五章 数组和广义表
前4章介绍的数据结构共同特点： ▲ 都属于线性数据结构； ▲ 每种数据结构中的数据元素，都作为原子数据， 不再进行分解； 本章讨论的两种数据结构：数组和广义表，其共 同特点是： ▲ 从逻辑结构上看它们，可看成是线性结构的一 种扩展； ▲ 数据元素本身也是一个数据结构；
4
第4页
(2) 二维数组的解释
二维数组中的每个元素都受两个 线性关系的约束，即行关系和列关系， 在每个关系中，每个元素aij都有且仅 有一个直接前趋，都有且仅有一个直 接后继。
aa … 00 01

《数据结构——用C语言描述(第二版)》第5章 数组和广义表

《数据结构——用C语言描述(第二版)》第5章 数组和广义表
是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下 三角矩阵则与之相反，如图5.3所示。
第五章 数组和广义表
在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素 为零则可不必分配空间，而其余的元素有 n(n+1)/2个，因此三角矩阵 可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一 个下标变量中。
假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以 按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在 a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得 到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对 三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就 可以实现转置。
LOC ( aij ) =LOC ( a00) +(i×n+j) × c 同理可推导出以列为主序优先存储时数据元素a i j 的存储地址，其计算公式 为：
LOC( a i j ) =LOC( a00 ) +( j × n +i ) × c 对于三维数组Am×n×p而言，若以行为主序优先存储时，则其数据元 素aijk的存储地址可为： LOC ( a i j k) =LOC ( a000) +[ i × m×p +j ×p +k] × c 对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是 0，a i j 的地址为： LOC ( a i j ) =LOC ( a c 1 c 2 ) +[ ( i – c 1 )* ( d 2 – c 2 +1) +j – c 2 ] * c

第五章 数组与广义表

第五章 数组与广义表

第五章数组、特殊矩阵和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n 列的二维数组。

标识，因此，在数组上不能做插入、删除数据元素的操作。

通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。

在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。

(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。

我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

第5章 数组和广义表[28页]


1 4 91
( 2 3 10 )
2 3 10
(2 5 3 )
B= 2 5 3
( 3 6 28 )
3 6 28
( 4 2 22 )
4 2 22
(4 4 9 )
44 9
( 6 1 -15)
6 1 -15
把该三元组表表示成一个三列二维数组B，为使三列二维数组B
与所表示的矩阵N建立起唯一的对应关系，还需要表示出矩阵
i (i-1)/2 + j i≥ j
k=
j ( j-1)/2+ i i < j
此时矩阵A中各元素值可由下式得到：
aij= B(k)
2.5 数组与矩阵的表示
3. 对角矩阵 对角矩阵——非0元素分布在主对角线及对称两侧
如，n 阶的五对角矩阵A： 若用一维数组B以行为主存放A中的非0元素, 当2≤i<n 时，A中非0元素aij的下标i、j与元 素在 B 中的下标 k 之间的对应关系为： k = 5(i-1) – 3 + [j-(i-3)] = 4i + j-5 矩阵A中各元素值可由下式得到：
2 = ( a21 a22 … …a2n ) ﹕
a11
﹕
a12
…
m= ( am1 am2… …amn )
即 A=(1， 2… … m ) 构成线性表 , 按顺序存放行向量及其中的元素，则有：
a1n a21
根据存储关系，容易计算出aij的地址：
a22
…
ADR(aij)=ADR(a11)+[(i-1)*n+j-1]*l
N的行、列数和非0元素个数，称之为三元组顺序表
2.5 数组与矩阵的表示
用三元组表B表示后，访问矩阵元素Nij的方法有： (1) 根据i, j值从B的第0行开始查找 ( 先查找 i, 再查找 j ):

数组和广义表 数据结构


3.建立广义表的存储结构 假定广义表中的元素类型ElemType为chai类型，每个原子的值被限 定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一 个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号 内不包含任何字符。例如“(a，(b, c, d))”就是一个符合上述规定的广 义表格式。 建立广义表存储结构的算法同样是一个递归算法。该算法使用一个 具有广义表格式的字符串参数s,返回由它生成的广义表存储结构的头结 点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当 碰到左括号时，表明它是一个表元素的开始，则应建立一个由h指向的表 结点，并用它的sublist域作为子表的表头指针进行递归调用，来建立子 表的存储结构；当碰到一个英文字母时，表明它是一个原子，则应建立 一个由h指向的原子结点；当碰到一个“）”字符时，表明它是一个空表， 则应置h为空。当建立了一个由h指向的结点后，接着碰到逗号字符时， 表明存在后继结点，需要建立当前结点(即由h指向的结点）的后继表； 当碰到右括号或分号字符时，表明当前所处理的表已结束，应该置当前 结点的link域为空。 4.输出广义表 5.广义表的复制
广义表的转换过程
为了使子表和原子两类结点既能在形式上保持一致，又能进
行区别，可采用如下结构形式：
其中，tag域为标志字段，用于区分两类结点。sublist或data
域由tag决定。若tag=0，表示该结点为原子结点，则第二个 域为data，存放相应原子元素的信息；若tag=l，表示该结点 为表结点，则第二个域为sublist，存放相应子表第一个元素 对应结点的地址。link域存放与本元素同一层的下一个元素所 在结点的地址，当本元素是所在层的最后一个元素时，link域 为NULL。 例：前面的广义表C的存储结构如下图所示(很多《数据结构 公教科书上称之为带表头结点的广义表的链表存储结构

第5章 数组和广义表

第五章数组和广义表讲课提要【主要内容】1．多维数组的顺序存储结构2．特殊矩阵的压缩存储3．广义表的定义及其与线性表的关系4．广义表的存储结构5．广义表运算实现中递归的应用【教学目标】1．掌握多维数组的顺序存储结构2．掌握特殊矩阵的压缩存储方法3．掌握广义表的定义及其与线性表的关系4．掌握广义表的存储结构5．了解广义表运算实现中递归的应用学习指导1．多维数组的顺序存储结构对于多维数组，有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。

设有m×n二维数组A mn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。

设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算a ij 的物理地址的函数为：LOC(a ij) = LOC(a11) + ( (i-1)*n + j-1 ) * L同理，对于三维数组A mnp，即m×n×p数组，对于数组元素a ijk其物理地址为：LOC(a ijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L注意：在C语言中，数组中每一维的下界定义为0，则：LOC(a ij) = LOC(a00) + ( i*n + j ) * L【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

第5章数组和广义表

//L=1,指针的增减以元素的大小为单位 For(i=dim-2;i>0;--i)
A.contants[i]=A.bounds[i+1]*A.constants[i+1]; return ok; }
第5章 数组和广义表
Status DestoryArray(Array &A){ //销毁数组 if(!A.base) return ERROR; free(A.base)； A.base=NULL; if(!A.bounds) return ERROR; free(A.bounds); A.bounds=NULL; if(!A.contants) return ERROR; free(A.contants) A.contants=NULL; return ok;
（3） Value（A，&e, index1, …, indexn）： 若下标合法，则 用e返回数组A中由index1, …, indexn所指定的元素的值。
（4） Assign(&A,e,indexl,…indexn)：若各下标不超界， 则将e赋值为所指定的A的元素值，并返回OK。 。
第5章 数组和广义表
三维数组A（1..r , 1..m , 1..n）可以看成是r个m×n的二维数组，
如图5.5所示。
n
m n
r j－ 1
m
k－ 1
图5.5 三维数组看成r个m×n的二维数组
第5章 数组和广义表
假定每个元素占一个存储单元，采用以行为主序的方法存 放，即行下标r变化最慢， 纵下标n变化最快。 首元素a111的地 址为Loc［1, 1, 1］，求任意元素aijk的地址。
第5章 数组和广义表
以上我们以二维数组为例介绍了数组的结构特性，实际 上数组是一组有固定个数的元素的集合。也就是说，一旦定 义了数组的维数和每一维的上下限，数组中元素的个数就固 定了。 例如二维数组A3×4，它有3行、4列，即由12个元素组 成。由于这个性质，使得对数组的操作不像对线性表的操作 那样可以在表中任意一个合法的位置插入或删除一个元素。 对于数组的操作一般只有两类：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第五章 数组和广义表
数组与广义表可视为线性表的推广，其特点是 数据元素仍然是一个表。
5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 5.6 广义表的递归算法
5.1 数组的定义
数组的逻辑结构 其特点是结构中的元素本身可以是具有某种结构的 数据，但属于同一数据类型。 比如：一维数组可以看作一个线性表，二维数组 可以看作“数据元素是一维数组”的一维数组， 三维数组可以看作“数据元素是二维数组”的一 维数组，依此类推。例如，二维数组： a11 a12 … a1n a21 a22 … a2n Amn= … … …… am1 am2 … amn


数组：是一个具有固定格式和数量的数据有序集， 每一个数据元素有唯一的一组下标来标识。 通常在各种高级语言中数组一旦被定义，每一维的 大小及上下界都不能改变。

在数组上不能做插入、删除数据元素的操作，在数 组中通常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相 对应的数据元素。
这样的存储方法确实节约了存储空间，但矩阵的运算从算 法上可能变的复杂些。 下面我们讨论这种存储方式下的稀疏矩阵的两种运算：转 置和相乘。
define SMAX 1024 /*一个足够大的数*/ typedef struct { int i,j; /*非零元素的行、列*/ datatype v; /*非零元素值*/ }SPNode; /*三元组类型*/ typedef struct { int mu,nu,tu; /*矩阵的行、列及非零元素的个数*/ SPNode data[SMAX]; /*三元组表*/ } SPMatrix; /*三元组表的存储类型*/
M=
T=
图5.4 稀疏矩阵M和T
一、三元组顺序表
将三元组按行优先的顺序，同一行中列号从小到 大的规律排列成一个线性表，称为三元组表， 采用顺序存储方法存储该表。如图5.11稀疏矩 阵对应的三元组表为图5.12。 显然，要唯一的表示一个稀疏矩阵，还需要存储 三元组表的同时存储该矩阵的行、列，为了运 算方便，矩阵的非零元素的个数也同时存储。 这种存储的思想实现如下：
LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l
同理对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l
例如，下列三元组表 ((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7))
加上(6,7)这一对行、列值便可作为下列矩阵M的另 一种描述。而由上述三元组表的不同表示方法可 引出稀疏矩阵不同的压缩存储方法。
0 12 9 0 0 0 18 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 –7 0 0 0 0 0 0 0 0 0 -3 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 14 0 0 0 24 0 0 0 0 0 15 18 0 0 0 0 –7 0 0 0 0 0 0 0 -3 0 0 15
LOC(i,j)=LOC(1,1)+[3*(i-1)-1+(j-i+1)]*d =LOC(1,1)+(2i+j-3)*d 上例中，a34对应着sa[7]。 k=2*i+j-3=2*3+4-3=7 a21对应着sa[2] k=2*2+1-3=2 由此，我们称sa[0..3*n-2]是阶三对角带 状矩阵A的压缩存储表示。
5.3.1特殊矩阵
所谓特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要 存储矩阵中上三角或下三角中的元素，让每两个 对称的元素共享一个存储空间，这样，能节约近 一半的存储空间。不失一般性，我们按“行优先
有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有 的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵 中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的 压缩存储，见下图： a11 a21 k=0 1 a22 a31 2 3 …… an1 … n(n-1)/2 … an,n n(n-1)/2-1
5.2 数组的顺序表示和实现
用向量作为数组的一种存储结构，因为内存的地址空间是一维 的，数组的行列固定后，通过一个映象函数，则可根据数组 元素的下标得到它的存储地址。 l 一维数组：按下标顺序分配 l 多维数组：一般有两种存储方式 1．以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、 COBOL、C等 2．以列为主序（先列后行）的顺序存放，如FORTRAN语言 以行为主序的分配规律是：最右边的下标先变化，即最右下标 从小到大，循环一遍后，右边第二个下标再变，…，从右向 左，最后是左下标。 以列为主序分配的规律恰好相反：最左边的下标先变化，即最 左下标从小到大，循环一遍后，左边第二个下标再变，…， 从左向右，最后是右下标。
设有m×n二维数组Amn，按元素的下标求其地址的计算：
以“ 以行为主序” 的分配为例： 设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址 可用一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则：LOC(aij) = LOC(a00) + ( i*n + j)*l 推广到一般的二维数组：A[c1..d1] [c2..d2]，则aij的物理地址计算函数为：
顺序”存储主对角线（包括对角线）以下的元素，其 存储形式如图所示：
1 5 1 3 7 5 1 3 7 0 8 0 0 8 9 2 6 0 2 5 1 0 6 1 3 a11 a21 a 22 a31 a32 a33 ……………….. an1 a n2 a n3 …a nn
图 5.1 对称矩阵
在这个下三角矩阵中，第i行恰有i个元素，元素总 数为： n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些 元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便 于访问对称矩阵A中的元素，我们必须在aij和sa[k]
例：一个2×3二维数组，逻辑结构可以用图 5.2表示。以行为主序的内存映象如图5.3（a） 所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ， a22 ，a23 ; 以列为主序的分配顺序为：a11 ， a21 ，a12 ，a22 ，a13 ，a23 ; 它的内存映象 如图5.3（b）所示。
2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情况下， 三角矩阵常数为零。 a11 a12 … a 1 n a11 c … c c a22 … a 2 n a21 a22 … c ………………….. …………….. c c … a nn an1 an2 … ann (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵
推广到一般的三维数组：A[c1..d1] [c2..d2] [c3..d3]，则aijk的物理地址为：
LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3))*l
a11 a12 a21 a22 a23 a32 … … a nn-1 a nn
K=0 1 2 3 4 5 … … 3n-4 3n-3 数组sa中的元素sa[k]与三对角带状矩阵中的元 素aij存在一一对应关系，在aij之前有i-1行,共有 3*(i-1)-1个非零元素，在第i行，有j-i+1个非零元 素，这样，非零元素aij的地址为：
之间找一个对应关系。 若i≧j，则ai j在下三角形中。 ai j之前的i-1行（从第1 行到第i-1行）一共有1+2+…+(i-1)=i(i-1)/2个元素，在 第i行上， ai j之前恰有j-1个元素（即ai1,ai2,ai3,…,aij-1）， 因此有： k=i*(i-1)/2+j-1 0≦k<n(n+1)/2 若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要 交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 0≦ k<n(n+1)/2
a11 a12 a21 a22 a23 a32 a33 a34 …. ….. …. an-1 n-2 an-1 n-1 an-1 n ann-1 ann
图5.3 对角矩阵
Hale Waihona Puke 对这种矩阵，我们也可按行优序为主序来存储。除 第1行和第n行是2个元素外，每行的非零元素都 要是3个，因此，需存储的元素个数为3n-2。
下三角矩阵的存储和对称矩阵类似，sa[k]和aij对 应关系是： i(i-1)/2+j-1 i≧j k= n(n+1)/2 i<j 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线 为了中心的带状区域中，即除了主对角线和主对 角线相邻两侧的若干条对角线上的元素之外，其 余元素皆为零。下图给出了一个三对角矩阵，