线性结构
这里将讨论一些基本抽象数据类型——线性结构。所谓基本，只是相对而言，这些数
据类型是最基本，最简单的，并且是实现其他抽象数据类型的基础。
在下面的讨论中，首先我们将给出各种基本数据结构（ADT）的数学性质，然后在其
数学模型上定义一组运算，最后将讨论如何利用基本的数据类型（数组、指针、记录等）
来具体实现各种 ADT。
下面您将了解到以下常见的基本抽象数据类型的 ADT 操作以及这些操作用不同数据描
述方法的具体实现：
表的定义和性质
一、表的定义
表是由 n(n≥0)个同一类型的元素（结点）a
1
,a
2
,…,a
n
组成的有限序列。其中，元素的
个数 n 定义为表的长度。当 n=0 时称为空表。当 n≥l 时，我们说元素 a
i
位于该表的第 i 个位
置，或称 a
i
是表中第 i 个元素，i=1,2,…，n。根据各元素在表中的不同位置可以定义它们
在表中的前后次序。我们称元素 a
i
在元素 a
i+1
之前或 a
i
是 a
i+1
的前驱(i=1,2,…,n-1)。同时，
我们也称元素 a
i+1
在元素 a
i
之后，或 a
i+1
是 a
i
的后继。另外，称 a
1
为表头(head)，a
n
为表尾
(tail)。
由于表的元素具有线性性质，所以又称为线性表。
表是程序设计中使用得最频繁的一种 ADT，也是实现其他许多 ADT 的基础。
二、表的性质
从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有
且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。
注意：表和数组的区别
从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构。
从数学性质上来看，表是一个二元关系 R，<x,y>∈R 当且仅当 x 是 y 的前驱；如果将
该二元关系用关系图（将每一个元素用一个点来表示，若 x 与 y 有关系则从 x 到 y 连一条
有向线段）来表示，则得到的是一条单链 a
1
→a
2
→…→a
n
，因此表也可以看成是特殊的图
或特殊的树（每个节点有且仅有一个子节点）；而数组是从 1..n 的自然数集合到数组元素
集合的一一映射，其中 n 是数组的长度，1..n 中每一个自然数唯一地对应着一个数组元素，
反之亦然。所以数组可以用来实现映射。
剩余54页未读，继续阅读
评论0