【考纲内容】

（一） 线性表的基本概念
（二） 线性表的实现
顺序存储；链式存储
（三） 线性表的应用

【知识框架】

【复习提示】

线性表是算法题命题的重点。这类算法题实现起来比较容易且代码量较少，但是要求具有最优的性能（时间复杂度、空间复杂度），才能获得满分。因此，应牢固掌握线性表的各种基本操作（基于两种存储结构），在平时的学习中多注重培养动手能力。另外，需要提醒的是，算法最重要的是思想！考场上的时间紧迫，在试卷上不一定要求代码具有实际的可执行性，因此应尽力表达出算法的思想和步骤，而不必过于拘泥每个细节。注意算法题只能用C/C++语言实现。

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表是具有相同数据类型的个数据元素的有限序列，其中为表长，当时线性表是一个空表。若用命名线性表，则其一般表示为

式中，是唯一的“第一个” 数据元素，又称表头元素；是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。
由此，我们得出线性表的特点如下：

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

2.1.2 线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下：

• InitList(&L):初始化表。构造一个空的线性表。
• Length(L):求表长。返回线性表L的长度，即工中数据元素的个数。
• LocateElem(L,e):按值查找操作。在表工中查找具有给定关键字值的元素。
• GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
• ListInsert (&L,i,e):插入操作。在表工中的第i个位置上插入指定元素e.
• ListDelete(&L,i,&e):删除操作。删除表工中第i个位置的元素，并用e返回删除元素的值。
• PrintList(L):输出操作。按前后顺序输出线性表工的所有元素值。
• Empty(L):判空操作。若L为空表，则返回true,否则返回false.
• DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

注意：

1. 基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。
2. “&”表示C++语言中的引用调用，在C语言中采用指针也可达到同样的效果。

   2.2 线性表的顺序表示

   2.2.1 顺序表的定义

   线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素,在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。假设线性表存储的起始位置为LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小，则表所对应的顺序存储如图2.1所示。

数组下标	顺序表	内存地址
0		LOC(A)
1		LOC(A)+sizeof(ElemType)
i-1		LOC(A)+(i-1)*sizeof(ElemType)
n-1		LOC(A)+(n-1)*sizeof(ElemType)
MaxSize-1		LOC(A)+(MaxSize-1)*sizeof(ElemType)

图2.1 线性表的顺序存储结构
每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。
注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为

#define Maxsize 50                //定义线性表的最大长度
typedef struct{
    ElemType data [Maxsize];    //顺序表的元素
    int length;                    //顺序表的当前长度
}SqList;                        //顺序表的类型定义

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。
而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

#define InitSize 100    //表长度的初始定义
typedef struct{
    ElemType *data;        //指示动态分配数组的指针
    int Maxsize,length;    //数组的最大容量和当前个数
} SeqList;                //动态分配数组顺序表的类型定义

C的初始动态分配语句为
L.data=(ElemType*)malloc(sizeof (ElemType)*Initsize);
C++的初始动态分配语句为
L.data=new ElemType [Initsize];
注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。
顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2.2 顺序表上基本操作的实现

2.3 线性表的链式表示

2.3.1 单链表的定义

2.3.2 单链表上基本操作的实现

2.3.3 双链表

2.3.4 循环链表

2.3.5 静态链表

2.3.6 顺序表和链表的比较