线性表的定义和特点
1. 定义
线性表（Linear List）：由n（n>=0）个具有相同特性的数据元素（结点）a1,a2, ... , 组成的有限序列。
- 其中数据元素的个数n定义为表的长度；
- 当n = 0 时称为空表；
- 将非空的线性表（n>0）记作：（a1 , a2 , ... , an）
- 这里的数据元素ai（1 <= i <= n）只是一个抽象的符号，其具体含义在不同的情况下可以不同。
2.线性表的逻辑特征
- 在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继；
- 有且仅有一个终端结点a1，它没有直接后继，而仅有一个直接前趋a ~n-1~ ；
- 其余的内部结点a~i~（2 <= i <= n-1）都有且仅有一个直接前趋a ~n-1~和一个直接后继a ~n+1~；
- ==线性表是一种典型的线性结构==。
抽象数据类型线性表的定义如下：
ADT List{
数据对象 : D = {a[i] | a[i]属于Element,(i=1,2,...,n)}
数据关系 : R = {<a[i-1],a[i]> | a[i-1],a[i]属于D,(i=1,2,...,n)}
基本操作 :
InitList(&L); DestroyList(&L);
ListInsert(&L,i,e); ListDelete(&L,i,&e);
......等等
}ADT List线性表的顺序表示
把逻辑相邻的数据元素存储在物理上相邻的存储单元中的存储结构。知道某个元素的存储位置就可以计算出其他元素的存储位置。
假设线性表的每个元素需占 l 个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系：
==Loc(a~i+1~) = Loc(a~i~) + l==
由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到
==Loc(a~i~) = Loc(a~1~) + (i +1) x l==
顺序表的元素地址连续、依次存放、随机存取、类型相同，所以可用数组来表示顺序表； 线性表的长度可变，因此用一变量表示顺序表的长度属性。
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef struct {
ElemType elem[LIST_INIT_SIZE ];
int length; //当前长度
}例如，多项式的顺序存储结构类型定义为：
p~n~(x) = p~1~(x)x^e1^ + p~2~(x)x^e2^ + ... + p~m~(x)x^em^,
线性表 P = ( (p1,e1) , (p2,e2) , ... , (pm,em) );
#define MAXSIZE 1000 //多项式可能达到的最大长度
typedef struct { //多项式非零项的定义
float p; //系数
int e; //指数
}Polynomial;
typedef struct {
Polynomial *elem; //存储空间的基地址
int length; //多项式中当前项的个数
}SqList; //多项式的顺序存储结构类型为SqList顺序表的基本实现
1. 线性表L的初始化
Status initList_Sq(SqlList &L){ //构造一个空的顺序表L
L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
if(!L.elem) //存储空间分配失败
return;
L.length = 0; //空表长度为0
return;
}2. 销毁顺序表L
void DestroyList(SqList &L){
if(L.elem)
delete L.elem; //释放存储空间
}3. 清空顺序表L
void ClearList(SqList &L){
L.length = 0; //将线性表的长度置为0
}4. 求线性表L的长度
int DestroyList(SqList L){
return L.length;5. 判断线性表是否为空
int IsEmpty(SqList L){
if(L.length == 0) return 1;
else return 0;
}6. 顺序表的求值（根据位置i获取相应位置数据元素的内容）
int GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length)
return ERROR; //判断i值是否合理，若不合理，返回ERROR
e = L.elem[i-1]; //第i-1的单元存储着第i个数据
return OK;
}7. 顺序表的查找
算法思想：
- 在线性表L中查找与指定e相同的数据元素的位置
- 从表的一段开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0。
int LocateElem(SqList L,Element e){
//在线性表L中查找值为e的数据元素。返回其序号（是第几个元素）
for(i=0li<L.length;i++)
if(L.elem[i] == e) return i+1; //查找成功，返回序号
return 0; //查找失败，返回0
}顺序表的查找算法分析：
平均查找长度ASL（Average Search Length）:
为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值（平均值）叫做查找算法 的平均查找长度。
对含有n个记录的表，查找成功时：
其中，Pi为找到第i个记录需要比较的次数。Ci为第i个记录被查找的概率。
顺序查找的平均查找长度：
==ASL=P~1~ + 2P~2~ + ... + (n-1)P~n-1~ + nP~n~==,
假设每个记录的查找概率相等：
则：
由此，得顺序表查找的时间复杂度为==O(n) ~ n==
8. 顺序表的插入
线性表的插入运算是指在表的第i个位置上，插入一个新结点e，使长度为n的线性表（a1,... ,ai-1,ai,...,an）变成长度为n+1的线性表（a1,... ,ai-1, e ,ai,...,an）。
算法思想：
- 判断插入位置i是否合法，
- 判断顺序表的存储空间是否已满，
- 将第n至第i位的元素依次向后移动一个位置，空出第i个位置，
- 将要插入的新元素e放入第i个位置，
- 表长加1。
Status ListInsert_Sq(SqList &L,int i,ElemType e){
if(i<1||i>L.length) return; //i值不合法
if(L.length == MAXSIZE) return; //当前存储空间已满
for(j=L.length-1;j>=i-1;j++){
L.emel[j+1] = L.elem[j]; //插入位置及之后的元素后移
}
L.elem[i-1]=e; //将新元素e放入第i个位置
L.length++; //表长加1
return;
}
9. 顺序表的删除
线性表的删除操作运算是指将表的第i个结点删除，使长度为n的线性表（a1,... ,ai-1,ai,ai+1...,an）变成长度为n-1的线性表（a1,... ,ai-1, ai+1,...,an）。
算法思想：
- 判断删除位置i是否合法，
- 将欲删除的元素保留在e中，
- 将第i+1至第n位的元素依次向前移动一个位置，
- 表长减1，删除成功。
Status ListDelete_Sq(SqList &L,int i){
if(i<1||i>L.length) return; //i值不合法
for(j=i;j<=L.length-1;j++){
L.emel[j-1] = L.elem[j]; //被删除元素之后的元素前移
}
L.length--; //表长加1
return;
}总结
顺序表的优缺点：
优点：
- 存储密度大（结点本身所占存储量/结点结构所占存储量）
- 可以随机存取表中任一元素
缺点
- 在插入、删除某一元素时，需要大量移动元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
