第2章线性表
本章主要内容：
1、线性表的概念、特点、及其基本操作定义
2、线性表的顺序存储结构及其算法实现
3、线性表的链式存储结构及其算法实现
4、循环链表及其线性表的应用
本章重点难点：
1、线性表的存储结构及算法实现。
2、链式存储结构及算法实现。
3、循环链表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义及特点
1.线性表的定义
线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。n表示线性表中数据元素的个数,称为线性表的长度(简称表长)。当n=0时，线性表为空，称为空线性表。
线性表的逻辑结构通常用数学中的向量形式表示：
L=( a
1,a
2
,...,a
i-1
,a
i
,a
i+1
,...,a
n
) 或者
L=( a
0,a
1
,...,a
i-1
,a
i
,a
i+1
,...,a
n-1
)
其中：L为线性表名称，习惯用大写书写；a
i
为组成该线性表的数据元素，元素的数据类型可以是可以表示出的任何类型。
例 1：分析下列线性表的数据类型：
La=（34，89，765，12，90，-34，22）；
Lb=(January, February，March，April，May，June，July，August，September，October，November，December，World, China,Welcome)；
Lc=（stu1,stu2,...,stu50) ；其中，数据元素stui的数据类型为：
struct student{
char Num; //学号
char *name; //姓名
};
2、线性表的特点。
除第一个元素外，每个元素有且仅有唯一一个直接前驱，第一个元素无直接前驱，除最后一个元素外，每个元素有且仅有唯一一个直接后继，最后一个元素无直接后继。1-1这种次序描述了元素之间的 1 对 1关系。此外，我们所研究的线性表的元素个数是有限的，各元素的数据类型是相同德，且数据元素可以是任意类型。
2.1.2、线性表的基本操作
（1）初始化线性表L InitList(L)
（2）清空线性表L ClearList(L)
（3）求线性表L的长度 ListLength(L)
（4）判断线性表L是否为空 IsEmpty(L)
（5）获取线性表L中的某个数据元素内容 GetElem(L,i,e)
（6）查找值为e的数据元素 LocateELem(L,e)
（7）返回线性表L中e的直接前驱元素 PriorElem(L,e)
（8）返回线性表L中e的直接后继元素 NextElem(L,e)
（9）在线性表L中插入一个数据元素 ListInsert(L,i,e)
（10）删除线性表L中第i个数据元素 ListDelete(L,i,e)
2. 2 线性表的顺序存储结构与操作算法实现
2.2.1 线性表的顺序存储结构定义及其特点
1、线性表的顺序存储结构（顺序表）
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如图2-1所示：
图 2-1 顺序表的存储
相邻两个数据元素的存储位置计算公式:
LOC(a i)=LOC(a i-1)+C (2-1)
线性表中任意一个数据元素的存储位置的计算公式为：
LOC(a i)=LOC(a1)+(i-1)*C (2-2)
或者：
LOC(a i)=LOC(a0)+i*C (2-3)
其中，C为每个数据元素所占据的存储单元数目。
2、顺序存储结构的特点
优点：
(1) 一致性。在顺序表中，利用数据元素的存储位置相邻，表示线性表中数据元素之间的相邻前后关系，逻辑结构与存储结构（物理结构）一致；
(2）可随机访问性。在访问顺序表时，可以利用公式(2-2),(2-3)，可以快速地计算出任何一个数据元素的存储地址。因此，访问每个数据元素所花费的时相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。
缺点：
（1）插入、删除低效。对插入、删除等操作效率较低，需要移动大量元素。
（2）不便于扩充。要动态增加元素个数较困难。
顺序表示适合于数据元素个数稳定、较少进行插入和删除操作、频繁进行查询操作的场合。
3、顺序存储结构的定义
#define LIST_MAX_LENGTH 100 //线性表的最大长度
typedef struct {
Elemtype elem[LIST_MAX_LENGTH]; //指向存放线性表中数据元素
int length; //线性表的当前长度
} SQLIST；
2.2.2 线性表的典型操作算法的实现
（1）初始化线性表L
viod InitList(SEQLIST *L)
{ L->length=0; //将当前线性表长度置0
}
（2）清空线性表L
void ClearList(SEQLIST *L)
{ L->length=0; //将线性表的长度置为0
}
上面的两个算法的具体操作都是一样的，但是含义却不一样。初始化一个线性表，是给出一个初始状态：表中没有元素，所以表长为0。而清空线性表是说表里面是否有元素我们不管，只要定义了表长为0，就肯定了表是空表。前者是对一个表的初始状态的描述，后者是强行达到空表的操作。
（3）求线性表L的长度
int GetLength(SEQLIST L)
{ return (L.length);
