2.2 基本数据结构
2.2.1 线性表
线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式
L=(a1,a2,…,ai−1,ai,ai+1,…,an)
其中，L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。
下面列举3种线性表。
☢ La = (34,89,765,12,90,-34,22)，数据元素类型为int型。
☢ Ls = ("Hello","World", "China", "Welcome")，数据元素类型为string型。
☢ Lb = (book1, book2,…, book100)，数据元素类型为结构体类型。结构体bookinfo定义为
线性表是一种抽象的数据结构类别，数组、链表、栈和队列都属于线性表的范畴。线性表有两种存储结构：顺序存储、链式存储。下面简要介绍这两种存储结构的原理。
1．线性表的顺序存储结构
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如图2-3所示，其中d为线性表存储空间的首地址，L为每个数据元素所占据的存储单元数目（或者字节数）。
图2-3 线性表的顺序存储结构
在顺序存储的线性表中，相邻两个数据元素的存储位置计算公式为
LOC(ai+1)=LOC(ai)+l
线性表中任意一个数据元素的存储位置的计算公式为
LOC(ai+1)=LOC(a1)+(i−1)×l
顺序存储线性表具有以下特点。
① 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致。
②在访问线性表时，可以利用上述数学公式快速地计算任何一个数据元素的存储地址。也就是说，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构称为随机存储结构。
③ 顺序存储结构表示的线性表，在进行插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较多，并且经常对其进行插入或删除操作时，执行效率会比较低，这一点需要考虑。
在C语言中，实现线性表的顺序存储结构的类型可定义如下：
其中，EntryType是数据元素类型的抽象表示，其结构体的定义需要具体问题具体分析。
2．线性表的链式存储结构
线性表的链式存储结构是指用一组任意存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，表中不仅包括每个数据元素的具体内容，还要附加表示它的直接后继元素存储位置的信息。在链式存储的线性表中，表示每个数据元素的两部分信息组合在一起被称为结点。其中，表示数据元素内容的部分被称为数据域（data），表示直接后继元素存储地址的部分被称为指针或指针域（next）。
假设有一个线性表(a, b, c, d)，可用图2-4所示的形式存储。
图2-4 线性表的链式存储结构
常用的链式线性表包括单链表、循环链表和双向循环链表三种。
（1）单链表
单链表可形象地描述为图2-5。其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。最后一个结点没有直接后继结点，所以它的指针域放入一个特殊值NULL。NULL值在图示中常用“^”表示。
图2-5 单链表
单链表的结点可定义如下：
其中，EntryType是数据元素类型的抽象表示，其结构体的定义需要具体问题具体分析。然后，单链表可通过头结点指针来定义，即：
（2）循环链表
若将单链表中最后一个结点的next域指向头结点，则得到循环链表，如图2-6所示。
图2-6 循环链表
实现循环链表的类型定义与单链表完全相同，所有操作也与单链表类似，只是链表初始化和判断链表结束有所不同。下面列举两个循环链表操作的算法示例。
① 初始化循环链表CL
② 在循环链表CL中检索值为e的数据元素
（3）双向循环链表
在循环链表中，访问后继结点只需向后走一步，而访问前驱结点需要转一圈。可以看出，循环链表并不适用于经常访问前驱结点的情况。在需要频繁地同时访问前驱和后继结点的时候，往往使用双向循环链表。
双向循环链表就是每个结点有两个指针域，一个指向后继结点，另一个指向前驱结点，如图2-7所示。
图2-7 双向循环链表
双向循环链表的结点可以定义如下：
其中，EntryType是数据元素类型的抽象表示，其结构体的定义需要具体问题具体分析。然后，双向循环链表通过头结点指针来定义，即：
双向循环链表的操作与单向循环链表类似，只需添加前驱指针的处理。
无论是单链表还是循环链表，它们都具有以下特点：
① 线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致。
② 在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后（或者向前）扫描其余结点，具有这种特点的存取方式被称为顺序存取方式。
在STL中，容器vector实现了顺序存储线性表，容器list实现了链式存储线性表，具体调用方法见2.3节。