第5章
数组和广义表
前几章讨论的线性结构中的数据元素都是非结构的原子类型,原子类型的数据元素是不能再分解的。本章讨论的两种数据结构(数组和广义表)与之前讨论的数据结构有所不同,这两种数据结构均可以被看成是线性表在下述含义上的扩展,即表中的数据元素本身也是一个数据结构。
数组是C/C 中常见的数据类型,几乎所有的程序设计语言都把数组类型设定为固有类型。本章以抽象数据类型的形式讨论数组的定义和实现,便于加深对数组类型的理解。
5.1数组的定义及抽象数据类型
5.1.1数组的定义
数组是由多个类型相同的数据元素组成的一个有限序列。在定义上,数组与线性表的形式几乎一致。从逻辑结构上看,数组A是由n(n>1)个相同类型数据元素a1,a2,…,an构成的有限序列,其逻辑表示为
A=(a1,a2,…,an)
其中,ai(1≤i≤n)表示数组A的第i个元素。
一个二维数组可以被看作是一个特殊的一维数组,即每个数组元素都是相同类型的一维数组。以此类推,任何多维数组都可以被看成是一个线性表,且表中的每个数据元素也是一个线性表。多维数组是线性表的推广。
推广到d(d≥3)维数组,不妨把它看作是一个以d-1维数组作为数据元素的线性表; 或者这样理解,它是一种较复杂的线性表结构,由简单的数据结构(即线性表)辗转合成而得。
5.1.2数组的抽象数据类型
抽象数据类型d维数组的定义如下。
ADT Array{
数据对象:
D={aj1,j2,…,jd| ji=1,…,bi,i=l,2,…,d}//第i维的长度为bi
数据关系:
R={r1,r2,…,rd}
ri={<aj1…ji…jd,aj1…ji 1…jd>|1≤jk≤bk ,1≤k≤d且k≠i,1≤ji≤bi-1,i=2,…,d}
基本运算:
Value(A,&e,index1,…,indexd)
初始条件:A是d维数组,e为元素变量,随后是d个下标值。
操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。
Assign(&A,e,index1,…,indexn)
初始条件:A是d维数组,e为元素变量,随后是d个下标值。
操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK。
ADisp(A,b1,b2,…,bd)
初始条件:A是d维数组,随后是d个下标值。
操作结果:输出d维数组A的所有元素值。
} ADT Array
数组一般不进行插入和删除操作。通常,数组被建立以后,元素的个数和元素之间的关系不再发生变化。这个特点使得数组不像线性表那样,可以在表中的任意位置上进行插入和删除元素。数组中常见的操作是: 给定下标读取数组元素的值和修改数组元素的值。因此,除了使用下标,也可以通过计算数组元素的地址实现上述操作。