注意：线性表中数据元素的位序从“1”开始，而数组下标从“0”开始。
3、线性表的特点：1）表中元素个数有限；
2）表中元素有逻辑上的顺序性，表中元素有先后次序；
3）表中元素都是数据元素，每个元素都是单个元素；
4）表中元素数据类型都相同，每个元素占有相同大小的存储空间；
5）表中元素具抽象性，仅讨论元素间的逻辑关系，不考虑元素表示的是什么内容。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
顺序表和链表是指存储结构。
4、线性表的基本操作：1）InitList(&L)：初始化表。构造一个空的线性表。
2）Length(L)：求表长。返回 L 中数据元素的个数。
3）LocateElem(L,e)：按值查找操作。
4）GetElem(L,i)：按位查找操作。获取表中第 i 个位置的元素值。
5）ListInsert(&L,i,e)：插入操作。在表中第 i 个位置插入指定元素e。
6）ListDelete(&L,i,&e)：删除操作。删除表中第 i 个位置的元素，并用e返回删除元素的值。
7）PrintList(L)：输出操作。按前后顺序输出线性表的所有元素值。
8）Empty(L)：判空操作。空表返回true，非空返回false。
9）DestroyList(&L)：销毁操作。销毁线性表，并释放线性表所占用的内存空间。
二、线性表的顺序表示 1、顺序表：线性表的顺序存储又称顺序表。逻辑上相邻的两个元素在物理位置上也相邻。 2、sizeof(ElemType)：每个数据元素所占用存储空间的大小。 3、线性表的顺序存储类型描述为:静态分配：使用“静态数组”实现，数组大小一旦确定就无法改变。
#define MaxSize 50 //定义线性表的最大长度
typedef struct
{
ElemType data[MaxSize]; //顺序表的元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
4、动态分配：
1）顺序表存满时，可再用malloc()函数动态拓展顺序表的最大容量。
2）动态分配时需要将数据元素复制到新的存储区域，并用free()函数释放原区域的内存空间。
#define InitSize 100 //表长度的初始定义
typedef struct
{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length; //数组的最大容量和当前个数
}SqList; //动态分配数组顺序表的类型定义
5、C的初始动态分配语句为：
L.data=(ElemType*)malloc(Sizeof(ElemType)*InitSize);
6、C++的初始动态分配语句为：
L.data=new ElemType[InitSize];
1）随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
2）存储密度高，每个结点只存储数据元素。
3）拓展容量不方便，即使采用动态分配的方式实现，拓展长度的时间复杂度也计较高。
4）插入、删除操作不方便，需要移动大量元素。
8、顺序表的基本操作的实现 1）插入操作
ListInsert(&L,i,e) 将新元素e插入到L的第i个位置。插入位置之后的所有元素都要后移，顺序表长度增加1。
bool ListInsert(SqList &L,int i,ElemType e)
{
if(i<1 || i>L.length+1) //判断i的范围是否有效
return false;
if(L.length >= MaxSize) //当前存储空间已满,不能插入
return false;
for(int j = L.length ; j>=i ; j–) //将第i个元素之后的元素后移
L.data[j] = L.data[j-1];
L.data[i-1] = e; //在位置i处放入e
L.length++; //线性表长度+1
return true;
}
最好情况：表尾插入，O(1)
最坏情况：表首插入，O(n)
平均情况：平均移动次数为n/2，O(n)
2）删除操作
ListDelete(&L, i, &e) 删除顺序表L中第i(1<=i<=L.length)个位置的元素，删除位置之后的元素都要前移。并将被删除的元素引用变量e返回。
bool ListDelete(SqList &L,int i,ElemType &e)
{
if(i<1 || i>L.length) //判断i的范围是否有效
return false;
e = L.data[i-1]; //将被删除的元素赋值给e
for(int j = i; j < L.length; j++) //将第i个位置后的元素前移
L.data[j-1] = L.data[j];
L.length--; //线性表长度减1
return true;
}
最好情况：删除表尾元素，O(1)
最坏情况：删除表头元素，O(n)
平均情况：平均次数为(n-1)/2，O(n)
3）按值查找(顺序查找)
顺序表L中查找第一个元素值等于e的元素,并返回其位序。
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=0; i < L.length; i++)
if(L.data[i] == e)
return i+1; //下标为i的元素值等于e，返回其位序i + 1
return 0; //退出循环,说明查找失败
}
最好情况：查找元素在表头，比较一次，O(1)
最坏情况：查找元素在表尾或不存在，比较n次，O(n)
平均情况：平均次数为(n+1)/2，O(n)
