第2章线性表
线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：
●线性表的逻辑结构特征
●线性表的顺序存储和链式存储两种存储结构的特点
●在两种存储结构下基本操作的实现
2-1 重点难点指导
2-1-1 相关术语
1．线性表
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表
顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表
用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表
每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针
要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。
6．头结点
要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．头结点的作用
要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储
1．顺序表
顺序存储的线性表称为顺序表。其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
具体实现：在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等，即表长是可变的，因此，数组的容量需设计得足够大，设用data[MaxSize]来表示，其中MaxSize是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0] 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MaxSize个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。
这种存储思想的具体实现可以是多样的。
方法一：可以用一个数组和表示长度的变量共同完成上述思想，如：
#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数
DataType data[MaxSize];
int last;
这样表示的顺序表如图2-1所示。数据元素分别存放在data[0]到data[last]中。
这样使用简单方便，但有时不便管理。
0 1 …i-1 i …n-1 n MaxSize-1
data
last
图2-1 线性表的顺序存储示意图
方法二：从结构上考虑，通常将data 和last 封装成一个结构作为顺序表的类型：
#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数
typedef struct{
DataType data[MaxSize];
int last; //表示线性表最后一个元素位置。
}SeqList;
定义一个顺序表变量：SeqList L ;
这样表示的线性表如图2-2（a）所示。表长为st+1，线性表中的数据元素a1~a n分别存储在L.data[0]~L.data[st]中。
方法三：由于教科书中的算法用Visual C++语言描述，根据Visual C++语言中的一些规则，有时定义一个指向SeqList 类型的指针更为方便：
SeqList *L ；
L是一个指针变量，线性表的存储空间通过L=new SeqList操作（Visual C++语句，
不同的语言版本可能有所不同）来获得。
L 中存放的是顺序表的地址，这样表示的线性表如图2-2（b ）所示。表长表示为（*L ）.last+1或L -＞last+1，线性表中数据元素的存储空间为：
L-＞data[0] ~ L-＞data[L-＞last]。
读者通过上述介绍的几种表示方式，进一步体会顺序存储的“理念”，做题时根据题意灵活掌握，在读写算法时注意相关数据结构的类型说明。
图2-2 线性表的顺序存储示意图
2．顺序表的优缺点
优点1：顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。 设a １的存储地址为Loc(a １)，每个数据元素占d 个存储地址，则第i 个数据元素的地址为：
Loc(a i )=Loc(a １)+(i-1)*d 1≤i ≤n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i 个数据元素的地址来，这就是顺序表具有按数据元素的序号随机存取的特点。
优点2：存储密度高。
缺点1：在顺序表中做插入和删除运算时，平均需移动大约表中一半的元素；
缺点2：顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，因此分配不足则会造成溢出；分配过大，又可能造成存储单元的浪费。
2-1-3 链表
1．单链表
链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素a i ，除了存放数据元素自身的信息 a i 之外，还需要和a i 一起存放其后继 a i+1 所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图2-3所示，每个元素都如此。因此n 个元素的线性表通过每个结点的指针域拉成了一个“链子”，称
之为链表。因为每个结点中只有一个指向后继的指针，所以称其
图2-3 单链表结点结构
L.data L ->data 0 1 2 3 4 5
st MaxSize -1
（a ）表长为st+1
（b ）表长为L->last+1
MaxSize -1
L ->length 6
4
3 2 1 0 a 1 a 2 a 3 a
4 a
5 a 6
…
…
a 1 a 2 a 3 a 4 a 5 a 6
L->last 5 6
6
