数据结构（2） 线性表
第二章 线性表
http://jpkc.jnu.edu.cn/sjjg/upload/jiaoyan/
线性结构是一个数据元素的有序（次序）集。
线性结构的基本特征：
1. 集合中必存在唯一的一个“第一元素”；
2. 集合中必存在唯一的一个“最后元素”；
3. 除最后元素在外，均有唯一的后继；
4. 除第一元素之外，均有唯一的前驱。
—————–
线性表的类型定义
抽象数据类型的线性表的定义如下：
ADT List {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,…,n, n≥0 }
{称n为线性表的表长; 称n=0时的线性表为空表。}
数据关系：R1＝{
{设线性表为 (a1，a2,…，ai，…，an), 称i为ai在线性表中的位序。}
基本操作：
{结构初始化}
InitList( &L )
操作结果：构造一个空的线性表L。
{销毁结构}
DestroyList( &L )
初始条件：线性表L已存在。
操作结果：销毁线性表L。
{引用型操作}
ListEmpty( L )
初始条件：线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则FALSE。
ListLength( L )
初始条件：线性表L已存在。
操作结果：返回L中元素个数。
PriorElem( L, cur_e, &pre_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。
NextElem( L, cur_e, &next_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
GetElem( L, cur_e, &next_e )
初始条件：线性表L已存在， 1≤i≤LengthList(L)
操作结果：用e返回L中第i个元素的值。
LocateElem( L, e, compare( ) )
初始条件：线性表L已存在，compare( )是元素判定函数。
操作结果：返回L中第1个与e满足关系compare( )的元素的位序。
若这样的元素不存在，则返回值为0。
ListTraverse(L, visit( ))
初始条件：线性表L已存在。
操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。
{加工型操作}
ClearList( &L )
初始条件：线性表L已存在。
操作结果：将L重置为空表。
PutElem( L, i, &e )
初始条件：线性表L已存在，1≤i≤LengthList(L)
操作结果：L中第i个元素赋值同e的值。
ListInsert( &L, i, e )
初始条件：线性表L已存在，1≤i≤LengthList(L)+1
操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。
ListDelete(&L, i, &e)
初始条件：线性表L已存在且非空，1≤i≤LengthList(L)
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。
} ADT List
利用上述定义的线性表可以完成其它更复杂的操作。
—————–
线性表类型的实现——顺序映像
用一组地址连续的存储单元依次存放线性表中的数据元素。
—————–
线性表类型的实现——链式映像
一、单链表
用一组地址任意的存储单元存放线性表中的数据元素。
以元素（数据元素的映像）+指针（指示后继元素存储位置的）=结点（表示数据元素）
以“结点的序列”表示线性表——称作链表。
以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针。
二、结点和单链表的C语言描述
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
} LNode,*LinkList;
三、单链表操作的实现
四、一个带头结点的线性链表类型
五、其它形式的链表
—————–
一元多项式的表示
—————–
学习要点
1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
2. 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式(L=j-i+1, i=j-L+1, j=i+L-1)，链表中指针p和结点*p的对应关系 (结点*(p->next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。
3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。
4. 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。
5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。