数据结构基础-数组

数组

数组是定长线性表在维数上的扩展，即线性表中的元素又是一个线性表。

n维数组是一种”同构“的数据结构，也就是指其每个数据元素类型相同、结构相同。

数组其实就是同一类型的多个变量的集合。

数组元素的特点：

• 数据元素数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化。
• 数据元素具有相同的类型。
• 数据元素的下标关系具有上下界的约束且下标有序。

数组的基本运算：

• 给定一组下标，存取相应的数据元素。
• 给定一组下标，修改相应的数据元素中某个数据项的值。

如在JAVA中，数组的操作如下图所示:

JAVA数组操作

数组的顺序存储：

数组一般不做插入和删除运算，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数据适合于采用顺序存储结构。

广义表

广义表是由0个或多个单元素或子表组成的有限序列，是线性表的推广。

广义表与线性表的区别：

线性表的元素都是结构上不可分的单元素，而广义表可以是单元素，也可以是有结构的表。

广义表一般记为：LS = (a1,a2,...,an),n>=1。其中a1...an等元素既可以是单个元素，也可以是广义表。分别称为原子和子表。

广义表通常用圆括号括起来，用逗号分隔其中的元素,书写时用大写字母表示广义表，用小写字母表示原子。

广义表的长度与深度：

长度：指广义表中元素的个数。

深度：指广义表展开后，所含的括号的最大层数。

如：

N=(),　N是一个空表，其长度为0。

L=(a，b)，L是长度为2的广义表，它的两个元素都是原子,深度为1

M=(x,L)=(x，(a，b)),M是长度为2的广义表，第一个元素是原子x，第二个元素是子表L，深度为2。

• 基本操作

广义表的操作与线性表类似，但由于广义表的结构比较复杂，运算的实现也不如线性表简单，下面列出两个比较特殊的运算：

取表头：非空广义表的第一个元素称为表头，它可以是一个单元素，也可以是一个子表。

取表尾：非空广义表除表头元素之外，由其余元素构成的表称为表尾。非空广义表的表尾必定是一个表。

• 存储结构：

广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。

非空广义表可以分解为表头和表尾两部分，反之，一对确定的表头和表尾可唯一确定一个广义表。

广义表的元素有两种类型，因此链表结点结构也有两种，如下图所示，

广义表链表结点结构

tag 标记位：区分是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1。

hp 指针：用于连接本子表中存储的原子或子表。

tp 指针：用于连接广义表中下一个原子或子表。

对于广义表C=(a,(b,c,d))，链式存储结构如下图所示：

广义表(a,(b,c,d))存储结构示意图