当前位置：文档之家 › 数据结构- 数组和广义表(全)

数据结构- 数组和广义表(全)

  • 格式：ppt
  • 大小：995.50 KB
  • 文档页数：57

下载文档原格式

  / 57

合集下载

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

数据结构第五章 数组与广义表
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中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

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

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

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

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

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

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

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

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

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

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

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

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数据结构(数组和广义表)习题与答案

数据结构(数组和广义表)习题与答案

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

数据结构第5章

数据结构第5章

第5章：数组和广义表 1. 了解数组的定义；填空题：1、假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 。

2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。

2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址；填空题：1、已知A 的起始存储位置（基地址）为1000，若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1，c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950选择题：（ A ）1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

（无第0行第0列元素）A ．16902B ．16904C ．14454D ．答案A, B, C 均不对 答：此题（57列×60行＋31行）×2字节＋10000=16902( B )2、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：A ．i(i-1)/2+j-1B ．i(i-1)/2+jC ．i(i+1)/2+j-1D ．i(i+1)/2+j3、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构第5章数组和广义表2广义表ppt课件PPT精品文档33页

数据结构第5章数组和广义表2广义表ppt课件PPT精品文档33页
所以在对应的存储结构中，其存储结点也有相应划分。 对于原子结点，应包含值域； 对于表结点，应包含指示表头的表头指针域(指向
表中的第一个元素)和指示表尾的表尾指针域(指向除 去原表头元素后的广义表)。
4）D=( A , B ,C )
n=3，3个元素都是子表
5）E=(a, E)
n=2，a 为原子，E为子表
D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表
E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表
§5.4 广义表的类型定义
❖试用图形表示下列广义表
§5.4 广义表的类型定义 ❖广义表的特点
▪ 可共享
广义表的元素可以为其他广义表所共享 A = ( a , B ) =( a , ( b , c , d ) )
§5.4 广义表的类型定义
❖例1：求下列广义表的长度
1）A =( )
n=0，因为A是空表
2）B = ( e )
n=1，表中元素e是原子
3）C =( a ,( b , c , d ) ) n=2，a 为原子，(b, c, d)为子表
6. GetHead{ ( ( ) ) }＝ ( ) .
7. GetTail{ ( ( ) ) }＝ ( ) .
(a, b)
§5.4 广义表的类型定义 ❖注意：( )和( ( ) )的区别
前者为空表，长度=0，深度=1； 后者长度=1，深度=2，表头、表尾均为( )
§5.5 广义表的存储结构
❖广义表的存储结构
§5.4 广义表的类型定义
❖广义表的特点
▪ 有深度
广义表的深度定义为广义表中括弧的最大重数
如: H = (d, (e,( )))深度为3 注意：(1)空表的深度为1；

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

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

数据结构第五章数组和广义表(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

大学数据结构课件--第5章 数组和广义表


a 32 a 33 a 34 0 0
a 43 a 44 a 45 0
a 54 a 55 a 56 a 65 a 66
5.3.2 稀疏矩阵
稀疏矩阵的存储：如何表示非零元素的位置信息 1. 三元组表：每个元素用一个三元组（i，j，v）来表示。 i j v
0 1 6 1 1 6 2 3 8 12 9
2
3 4 5 6 7 8
2
5.2 数组的顺序表示和实现
a00 a00 a10 a01 存储单元是一维结构，而数组是个多维结构 , …… …… 则用一组连续存储单元存放数组的数据元素就有 am-1,0 a0,n-1 个次序约定问题。 a01 a10
a11
……
a11
……
二维数组可有两种存储方式： am-1,1 a1,n-1
……
K=
i*n-i(i-1)/2+j-i n(n+1)/2
当 i≤j 当i>j
0 a11 ... a1n-1 ... ... ... ... 0 0 0 an-1n-1
当i ≤ j时,a[i][j]是非零元素, a[i][j]前面有i行,共有n+(n-1)+(n-2)+…(n-(i-1))
=i(n+[n-(i-1)])/2=i*n-i(i-1)/2个元素，a[i][j]前面有j列，共j-i个非零元素，
A m× n
( a10 a11 … a1,n-1 )
=
注：
( … … …… ) ( am-1,0 am-1,2 … am-1,n-1 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值

数据结构(C)严蔚敏(数组与广义表)PPT课件


a00
Am×n
=
a10 ...
am-1,0
a01 a11 ...
am-1,1
a02 a12 ...
am-1,2
... a0,n-1
...
a1,n-1
... ...
... am-1,n-1
Data Structure
03.12.2020
Page 5
按行序为主序存放
0
1
n-1
Am×n
=
a00 a10 ...
a00
Am×n
=
a10 ...
am-1,0
a01 a11 ...
am-1,1
a02 a12 ...
am-1,2
... a0,n-1
...
a1,n-1
... ...
... am-1,n-1
列向量
a00
Am×n
=
a10 ...
am-1,0
a01 a11 ...
am-1,1
a02 a12 ...
初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。
Assign(&A, e, index1, ..., indexn)
初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。
a00 a10 ……. am-1,1 a01 a11 …….. am-1,1 ………. a0,n-1 a1,n-1 …….. am-1 ,n-1
Page 7
按行序为主序存放
0
Am×n

数据结构数组和广义表

数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。

5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。

其数据元素通常也称为数组元素。

数组地每个数据元素都有一个序号,称为下标。

可以通过数组下标访问数据元素。

数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。

如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。

如aij表示第i行j列地数据元素。

数组也是一种线性数据结构,它可以看成是线性表地一种扩充。

一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。

如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。

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


5.3.1
特殊矩阵
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 1≤i,j≤n 则称A为对称矩阵。 a11 1 5 1 3 7 a21 a 22 5 0 8 0 0 a31 a32 a33 1 8 9 2 6 ……………….. 3 0 2 5 1 an 1 a n 2 a n 3 …a n n 7 0 6 1 3
第5章
数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.1 数组的定义
数组-----线性表的扩展 A =(a0,a1,a2,…，an-1)
a00 a10 ┇ Am×n= ai0 ┇ am-1,0 a01 … a0j … a11 … a1j … ┇ ai2 … aij … ┇ am-1,2 … am-1,j … a0,n-1 a1,n-1 ai,n-1 am-1,n-1 α0 α1 ┇ Am×n= α i ┇ α m-1
Assign( &A, e, index1, ..., indexn) 赋值操作 初始条件：A是n维数组,e为元素变量,随后是n个下标值。 操作结果：若下标不超界,则将e的值赋给所指定的A的元 素,并返回OK。 对于数组来说一旦维数确定了，每个元素的下标确定了, 那么整个数组就确定了，这样的一个数组结构除了能改变 某元素的值，其他的不能再改变。
5.2 数组的顺序表示和实现
数组类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式。
有两种顺序映像方法： 1）以行序为主序(行优先，先行后列)：先存储行号较小 的元素，行号相同者先存储列号较小的元素；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

14
Status Assign(Array &A,ElemType e,…){
//A是n维数组，e为元素变量，随后是n个下标值， 若各下标不超界，则e的值赋为所指定的A的元素值， 即：将e值写入指定数组单元。
va_start(ap,e); if((result=Locate(A,ap,off))<=0) return result; *(A.base+off)=e; return OK; }
一个元 素长度 第i维长度
与所存元素个数有关的系 数，可用递推法求出
8
N维数组的顺序存储表示（见教材P93） #define MAX_ARRAY_DIM 8 //假设最大维数为8 typedef struct{ ELemType *base; //数组元素基址 int dim; //数组维数 int *bound; //数组各维长度信息保存区基址 int *constants; //数组映像函数常量的基址 }Array;
重点介绍稀疏矩阵的压缩和相应的操作。
17
一、稀疏矩阵的压缩存储
二、稀疏矩阵的操作
问题： 如果只存储稀疏矩阵中的非零元素，那这些元素的 位置信息该如何表示？ 解决思路： 对每个非零元素增开若干存储单元，例如存放其所 在的行号和列号，便可准确反映该元素所在位置。 实现方法： 将每个非零元素用一个三元组（i，j，aij）来表示， 则每个稀疏矩阵可用一个三元组表来表示。
行数 总列数，即 第2维长度 元素个数
ij
补充：计算二维数组元素地址的通式
设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
单个元素 长度
二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
6
例1〖软考题〗：一个二维数组A，行下标的范围是1到6，列下
12
Status Locate(Array A,va_list ap,int &off) {
//若ap指示的各下标值合法，则求出该元素在A中，相对地址off
off=0; for(i=0;i<A.dim;++i) { ind=va_arg(ap,int); if(ind<0||ind>A.bounds[i]) return OVERFLOW; off+=A.constants[i] *ind; } return OK; }
}
ห้องสมุดไป่ตู้11
数组基址指针
各维长度保 存区指针
映像函数Ci 保存区指针
Status DestroyArray(Array &A) { //销毁数组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.constants ) return ERROR; free ( A. constants ) ; A. constants = NULL; return OK; }
Amn=
N维数组的特点： n个下标，每个元素受到n个关系约束
一个n维数组可以看成是由若干个n－1维数组组成的线性表。
3
N维数组的数据类型定义 n_ARRAY = (D, R)
其中：
数据对象：D = {aj1,j2…jn| ji为数组元素的第i 维下标 ，aj1,j2…jn Elemset} 数据关系：R = { R1 ,R2，…. Rn } Ri = {<aj1,j2,…ji…jn , aj1,j2,…ji+1…jn >| aj1,j2,…ji…jn , aj1,j2,…ji+1…jn D , i=2,…n} 基本操作：构造数组、销毁数组、读数组元素、写数组元素
7
若是N维数组，其中任一元素的地址该如何计算？ 教材已给出低维优先的地址计算公式，见P93（5-2）式
该式称为n维数组的映像函数：
n
Loc(j1,j2,…jn)=LOC(0,0,…0)＋i 1
数组基址
C j
i i
前面若干元素占用 的地址字节总数
其中Cn=L, Ci-1=bi×Ci， 1<i≤n
5
无论规定行优先或列优先，只要知道以下三要素便可随时求出任 一元素的地址（这样数组中的任一元素便可以随机存取！）： ①开始结点的存放地址（即基地址） ②维数和每维的上、下界； ac1,c2 … ac1,d2 ③每个数组元素所占用的单元数 Amn= … aij … ad1,c2 … ad1,d2 则行优先存储时的地址公式为： LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L aij之前的 数组基址 a 本行前面的
法1：用线性表表示：
(( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7))
19
法2：用三元组矩阵表示：
0 1 2
i 6 1 1 3
j 6 2 3 1
value 8 12 9 -3
3
4 5 6 7 8
10
for(i=0;i<dim;++i){ A.bounds[i]=va_arg(ap,int); if(A.bounds[i]<0) return UNDERFLOW; elemtotal *=A.bounds[i]; } va_end(ap); A.base=(ElemType * )malloc(elemtotal * sizeof(ElemType)); if(!A.base) exit(OVERFLOW); A.constants=(int * )malloc(dim *sizeof(int)); if(!A.constans) exit(OVERFLOW); A.constans[dim-1]=1; for(i=dim-2;i>=0;--i) A.constants[i]=A.bounds[i+1]*A.constants[i+1]; return OK;
第5章 数组和广义表（Arrays & Lists）
数组和广义表的特点：一种特殊的线性表
① 元素的值并非原子类型，可以再分解，表中元素也是一 个线性表（即广义的线性表）。 ② 所有数据元素仍属同一数据类型。
5.1 5.2 5.3 5.4 5.5
数组的定义 数组的顺序表示和实现 矩阵的压缩存储 广义表的定义 广义表的存储结构
讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的存储空间， 且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩 阵等。 4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）
标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器 按字节编址。那么，这个数组的体积是 288 个字节。
答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
例2：已知二维数组Am,m按行存储的元素地址公式是：
Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 按列存储的公式是？
18
例1 ：三元素组表中的每个结点对应于稀疏矩阵的 一个非零元素，它包含有三个数据项，分别表示该 元素的 行下标 、 列下标 和 元素值 。 例2：写出右图所示稀疏 矩阵的压缩存储形式。
0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0
20
0 法三：用带辅助向量的三元组表示。 0 用途：通过三元组高效访问稀疏矩阵中 -3 任一非零元素。 0 方法： 增加2个辅助向量： 0 ① 记录每行非0元素个数，用NUM（i）表示； 15
1
5.1 数组的定义
数组： 由一组名字相同、下标不同的变量构成
注意： 本章所讨论的数组与高级语言中的数组有所区别：高 级语言中的数组是顺序结构；而本章的数组既可以是顺序的， 也可以是链式结构，用户可根据需要选择。 讨论：“数组的处理比其它复杂的结构要简单”，对吗？ 答：对的。因为： ① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数组一 旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单，除了结构的初始化和销毁之 外，只有存取元素和修改元素值的操作。
13
Status Value(Array A,ElemType &e,…){
//A是n维数组，e为元素变量，随后是n个下标值，若 各下标不超界，则e赋值为所指定的A的元素值，即将指 定元素值读到e变量中。
va_start(ap,e); if((result=Locate(A,ap,off))<=0) return result; e=*(A.base+off); return OK; }
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
3
4 5
5
3 2
14
24 18
6
6
1
4
15
-7
注意：为更可靠描述， 通常再加一行“总体” 信息：即总行数、总 列数、非零元素总个 数