线性结构基本介绍：
线性结构应用非常广泛，作为一种数据结构，用来解决各种问题
线性结构
线性结构：数据元素的有序（次序）集合。（“有序”是指数据元素之间存在一个“领先”或“落后”的次序关系。
特征： 1）集合中存在唯一“第一元素”； 2）集合中存在唯一“最后元素”； 3）除最后元素之外，其它数据元素均有唯一的“后继”； 4）除第一元素之外，其它数据元素均有唯一的“前驱” 。
线性表
线性表(Linear List) ：由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。
- 其中数据元素的个数n定义为表的长度。 （有n-1个有序对）
- 当n=0时，称为空表，常常将非空的线性表(n>0)记作： (a1，a2，…an)
- i为ai 在线性表中的位序。
线性表的抽象数据类型定义
ADT List {
数据对象：D＝{ ai | ai ∈ ElemSet， i=1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1 ,ai > | ai-1 ,ai∈D, i=2,...,n }
基本操作：
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, i, &e )
初始条件：线性表 L 已存在，1≤i≤LengthList(L)。
操作结果：用 e 返回 L 中第 i 个元素的值。
LocateElem( L, e, compare( ) )
初始条件：线性表 L 已存在，compare( ) 是元素判定函数。
操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。
ListTraverse( L, visit( ) )
初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。
操作结果：依次对 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
线性表类型的应用
相关算法
判别两个集合是否相等
“判别两个线性表中的数据元素是否完全相同”的算法的基本思想为：
- 首先判别两者的表长是否相等；
- 在表长相等的前提下，如果对于一个表中的所有元素，都能在另一个表中找到和它相等的元素的话，便可得到“两个线性表表示的集合相等”的结论；
- 反之，只要有一个元素在另一个表中不能找到相等元素时，便可得出”不等”的结论。
线性表的顺序表示和表现
顺序表
用一组地址连续的存储单元依次存放线性表中的数据元素”，即以”存储位置相邻”表示”位序相继的两个数据元素之间的前驱和后继的关系(有序对< ，>)”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。（类数组）
- LOC( a i ) = LOC( a i-1 ) + C
- LOC( a i ) = LOC( a 1 ) + ( i -1 )×C （a1为基地址，C为一个元素所占存储量）
顺序表的存储结构：
const int MAXSIZE=60; //预设的存储空间最大容量
typedef struct {
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //允许的最大存储容量
//（以sizeof(ElemType)为单位
}SqList;
顺序表基本操作
初始化操作
实质是为顺序表分配一个元素的存储空间。
由用户根据它对线性表的使用要求定义一个最大存储容量 maxsize，并约定当用户没有提出特殊需求(maxsize=0) 时，按预设的最大存储量 MAXLISTSIZE 进行分配。初始化后的顺序表是一个空表，当前长度为0.
void InitList(SqList &L,int maxsize)
{//构造一个空的线性表L
if(maxsize==0){
maxsize=MAXLISTSIZE;
}
L.elem=new ElemType[maxsize];
if(!L.elem){//分配完之后一定要记得验证是否分配成功
exit(1);
}
L.length=0;// 顺序表的初始长度为0
L.listsize=maxsize; // 该顺序表可以存储元素的最大容量
}//InitList
此算法时间复杂度为O（1）
元素定位操作
在顺序表中“查询”是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。
int LocateElem（SqList L,ElemType e)
{//在顺序表L中查找第1个满足与e满足判定条件的元素
//若找到，则返回其在L中的位序，否则返回0。
i=1;
p=L.elem;
while(i<=L.length&&e不满足条件){
i++;
}
if(i<=L.length){
return i;
}
else{
return 0;
}
}//LocateElem
时间复杂度为O（ListLength（L)）
插入元素操作
bool ListInsert(SqList &L,int pos, ElemType e)
{// 若存储空间不满且1≤pos≤Listlength(L)+1，则在顺序表 L 的 // 第 pos 个元素前插入新元素 e 且返回TRUE，否则返回FALSE
if(pos<1||pos>=L.length){//位置不合法
return FALSE;
}
if(L.length>=Listsize){//注意考虑存储空间已满的情况，无法插入
return FALSE;
}
for(int i=L.length-1;i>=pos;i--){
*L.elem[i+1]=*L.elem[i];
}
*L.elem[pos]=e;//插入e
++L.length;//表长增1
return TURE;
}//ListInsert
时间复杂度为O（ListLength（L))
删除元素操作
bool ListDelete(SqList &L， int pos， ElemType &e)
{ // 若1≤pos≤Listlength(L)，则以 e 带回从顺序表 L 中删除的 // 第 pos 个元素且返回 TRUE，否则返回 FALSE
if ((pos < 1) || (pos > L.length)) return FALSE ； // 删除位置不合法
e =* L.elem[pos-1];
for (j = pos； j<L.length；++j)
L.elem[j-1] = L.elem[j]； // 被删除元素之后的元素左移
--L.length； // 表长减1
return TRUE；
} // ListDelete
时间复杂度为O(ListLength(L)
销毁元素操作
和“初始化”操作分配空间相对应，销毁结构的实质是释放它所占的全部空间，以便使存储空间得到充分的利用。
void DestroyList( SqList &L )
{ // 释放顺序表 L 所占存储空间
delete[] L.elem；
L.listsize = 0；
L.length = 0；
} // DestroyList_Sq
时间复杂度为 O(1)
