|
|
| 线性表（linear_list）是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。一个数据元素可以由若干个数据项（item）组成，通常称为记录（record）,含有大量记录的线性表又被称为文件（file）。设序列中第i个元素为ai（1≤i≤n），则线性表一般表示为：
|
|
|
| （a1,a2,…,ai-1, a?, ai+1，…，an）
|
|
|
| 其中，ai-1在均ai的前面，称为ai的直接前驱元素。ai+1在ai的后面称为ai的直接后继元素。线性表中元素的个数n（n≥0）称为线性表的长度。当n=0时，线性表成为空表。
|
|
|
| 一个线性表也可以用标志符来命名，例如用A命名上面的线性表，则：
|
|
|
| A=（a1, a2,…,ai-1,ai, ai+1,…, an）
|
|
|
|
|
|
|
|
|
| 数据对象A=｛ai| 1≤i≤n,n≥0，ai为数据元素｝
|
|
|
| 数据关系R=｛i, ai+1>| 1≤i≤n-1｝
|
|
|
|
|
|
|
|
|
| 线性表是一个非常灵活的数据结构，对线性表的数据元素不仅可以访问，还可以对其进行诸如插入、删除等操作。因此，线性表的抽象数据类型包括了数据对象和数据关系两大部分，抽象数据类型的线性表定义如下所示：
|
|
|
|
|
|
|
| 线性表的存储结构有顺序、链接、散列等多种方式，顺序存储结构是其中最简单、最常见的一种。线性表的顺序存储结构就是用一组地址连续的存储单元依次存储线性表中的所有元素。因此，假设一个线性表中的每个元素需要占用k个存储单元，并且以该元素的第一个存储单元的地址作为该元素的存储位置。线性表中的第i个元素和第i+1个元素的存储位置有如下关系：
|
|
|
|
|
| 也就是说：LOC（ai）=LOC（a1）+（i-1）*k；
|
|
|
| 线性表的特点就在于它为线性表中相邻元素赋以了相邻的存储位置。只要确定了线性表的起始位置，就可以获得线性表的任意元素的存储位置。它的顺序存储结构图如下图所示。
|
|
|
|
|
|
|
| 为了便于线性表的操作，可以用记录类型来定义一个线性表List：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 线性表的顺序存储结构使得线性表的存储位置可以用一个简单、直观的公式来表示，但是在插入或删除操作的时候，需要移动大量的元素，十分不便。链式存储结构弥补了它的这个缺点。链式存储结构的特点是可以用一组任意的存储单元来存储线性表中的元素的存储结构，这些存储单元可以连续，也可以不连续。所以，为了表示数据元素ai与它的直接后继元素ai+1的逻辑关系，除了元素ai的基本信息之外，还存储了一个可以指明它的直接后继元素ai+1的存储位置的内容。它们共同组成ai的存储映像，称为结点（node）。存储元素ai的信息，被称为数据域，存储直接后继元素的存储位置的域，被称为指针域。n个结点（ai（1≤i≤n））组成一个链表，也就是线性表（a1，a2，…, an）的链式存储结构。其结构示意图如下图所示。
|
|
|
|
|
|
|
| 上图分别画出了链表的三种不同链式存储结构。若一个指针域的值为空，则在图形中通常用符号“Λ”表示，由于线性表中的第一个元素没有前驱元素，最后一个元素没有后继元素，所以用“Λ”表示。
|
|
|
| 循环链表是另一种形式的链式存储结构，它的特点是表中的最后一个结点的指针域指向头结点，整个链表形成一个环状结构，从表中任意一个结点出发都可以到达其他节点。操作与线性链表基本一致。
|
|
|
