05数组和广义表20231.pdfVIP

第五章数组和广义表

主要内容

本章主要内容：

•数组的定义、基本运算和存储结构

•特殊矩阵和稀疏矩阵的压缩存储

•广义表的逻辑结构和存储结构

重点掌握：

•数组的地址计算方法

•稀疏矩阵的三元组形式的顺序表示和十字链

表的表示方法

•用三元组的形式来实现稀疏矩阵的转置运算。

前4章介绍的数据结构共同特点：

（1）都属于线性数据结构；

（2）每种数据结构中的数据元素，都作为原子数

据，不再进行分解；

本章讨论的数据结构：数组，其特点是：

1）从逻辑结构上看，可看成是线性结构的一种扩

展；

2）数据元素本身也是一个数据结构。

3

一维数组具有线性表的结构，但操作简单，一般

不进行插入和删除操作，只定义给定下标读取元

素和修改元素的操作

二维数组中，每个数据元素对应一对数组下标，

在行方向上和列方向上都存在一个线性关系，即

存在两个前驱（前件）和两个后继（后件）。也

可看作是以线性表为数据元素的线性表。

n维数组中，每个数据元素对应n个下标，受n个

关系的制约，其中任一个关系都是线性关系。可

看作是数据元素为n-1维数组的一维数组。

因此，多维数组和广义表是对线性表的扩展：线

性表中的数据元素本身又是一个多层次的线性表。

5.1数组的定义

5.2数组的顺序表示和实现

5.3矩阵的压缩存储

5.4广义表

5.1数组的定义

数组的抽象数据类型

ADTArray{

数据对象：j=0,…,b,i=1,2,…,n,

ii-1

•D={a|n(0)称为数组的维数，b是数组第i

j1j2…jni

维的长度，ji是数组元素的第i维下标，

aj1j2…jn∈ElemSet}

数据关系：R={R,R,…,Rn}

12

Ri={a,a|0≤j≤b-1,1≤k≤n且

j1…ji…jnj1…ji+1…jnkk

k≠i,0≤j≤b-2,a,a∈D,i=2,…n}

iij1…ji…jnj1…ji+1…jn

基本操作：见下页

基本操作：

①InitArray(A,n,bound1,…,boundn)

已知维数n和各维长度，构造数组A

②DestroyArray(A)

销毁数组

③Value(A,e,index1,…,indexn)

返回指定下标的元素的值给e

④Assign(A,e,index1,…,indexn)

将e的值赋给指定下标的A的元素

}ADTArray

例：二维数组的逻辑结构定义成：A=(D,R)

0001…0,−1

1011…1,−1

A=

×⋮⋮⋮⋮

−1,0−1,1…