1、线性表定义
线性表是具有相同特性的数据元素的一个有限序列。
线性表 n(n≥0)个数据元素(结点) a1,a2,...,an组成的有限序列。
其中数据元素的个数 n定义为表的长度；
当 n==0时，称为空表；
将非空的线性表(a1,a2,...,an)
这里的数据元素 ai(1≤i≤n)只是一个抽象符号，其具体含义在不同的情况下可以不同。
同一个线性表中的元素必定具有相同的特性，数据元素间的关系式线性关系。
2、线性表的逻辑特征
在非空的线性表，有且仅有一个开始结点 a1，它没有直接前趋，而仅有一个直接后继a2；
有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋an−1；
其余的内部结点ai(2≤i≤n−1)都有且仅有一个直接前趋 ai−1和一个直接后继 ai+1
线性表是一种典型的线性结构。
3、线性表的抽象数据类型
抽象数据类型线性表的定义如下：
ADT List
{数据对象： D = { a i ∣ a i 属于Element，(i=1,2,...,n,n≥0)}
数据关系：R={<ai−1,ai>∣ai−1,ai属于D,(i=2,3,...,n)}
基本操作：
InitList(&L);
Destroy(&L);
ListInsert(&L,i,e);//在位置i插入元素e
ListDelete(&L,i,&e);//在位置i删除元素e
DestroyList(&L);//销毁线性表
ClearList(&L);//将线性表L重置为空表
ListEmpty(L);//判断线性表L是否为空
ListLength(L);//返回线性表中数据元素的个数
GetElem(L,i,&e);//用e返回线性表中第i个元素的值
LocateElem(L,e,compare());//返回L中第1个与e满足compare()的数据元素的位序。若这样的元素不存在，则返回值为0
PriorElem(L,cur_e,&pre_e);//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前趋，否则操作失败，pre_e无意义
NextElem(L, cur_e, &next_e);//若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无意义
ListTraverse(&L, visited());//遍历线性表中每一个元素，并做一个基本操作(这个基本操作不一定是做什么)visited()
… …
}ADT List
4、线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或者顺序映像，其中顺序存储的定义为：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表的存储结构依次存储，地址连续，中间没有空出的存储单元，线性表顺序存储结构占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置。假设线性表的每个元素需要占 l个存储单元，则第 i个数据元素的存储位置和第1个元素的存储位置之间满足关系：
Loc(ai)=Loc(a1)+(i−1)∗l
线性表中第一个元素的地址称为基地址，根据上式可知，线性表中查找某个元素的时间复杂度是) O(1)。
顺序表的顺序存储表示，顺序表元素的地址连续，依次存放，随机存取，类型相同，所以可以ongoing一个数组来表示顺序表；但是线性表的长度是可变的，但数组的长度不可以动态定义，为了解决这个问题，可以使用一个变量表示顺序表的长度属性，在长度不够用时，重新构建一个新的顺序表，将旧表的元素进行相应的拷贝。顺序表的模板定义如下所示：
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 typedef struct { ElemType elem[LIST_INIT_SIZE ];//静态数组定义 int length; //当前长度 }Sqlist;
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 typedef struct { ElemType *elem; //动态数组定义 int length; //当前长度 }Sqlist; L.elem = (ElemType*) malloc(sizeof(ElemType)*LIST_INIT_SIZE); //L.elem = new ElemType(LIST_INIT_SIZE);
//基于C++模板的线性表定义 template<class Elem> class MyVector { private: Elem *data; int length; int size; public: MyVector() {}; //空构造函数 MyVector(MyVector &L); //赋值构造1 MyVector(int num); //赋值构造2 };
线性表的基本操作包括以下几种：
InitList(&L); Destroy(&L); ListInsert(&L,i,e);//在位置i插入元素e ListDelete(&L,i,&e);//在位置i删除元素e DestroyList(&L);//销毁线性表 ClearList(&L);//将线性表L重置为空表 ListEmpty(L);//判断线性表L是否为空 ListLength(L);//返回线性表中数据元素的个数 GetElem(L,i,&e);//用e返回线性表中第i个元素的值 LocateElem(L,e,compare());//返回L中第1个与e满足compare()的数据元素的位序。若这样的元素不存在，则返回值为0 PriorElem(L,cur_e,&pre_e);//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前趋，否则操作失败，pre_e无意义 NextElem(L, cur_e, &next_e);//若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无意义 ListTraverse(&L, visited());//遍历线性表中每一个元素，并做一个基本操作(这个基本操作不一定是做什么)visited()
//函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;
//初始化线性表-基于C++实现 template<class Elem> MyVector<Elem>::MyVector(MyVector &L) {//赋值构造1 try { data = new Elem(L.size); } catch (const std::bad_alloc& e) { throw std::exception("内存分配失败！"); } memcpy(data,L.data,sizeof(Elem)*L.length); length = L.length; size = L.size; } template<class Elem> MyVector<Elem>::MyVector(int num) {//赋值构造2 try { data = new Elem[MyMAXSIZE]; } catch (const std::bad_alloc& e) { throw std::exception("内存分配失败！"); } length = num; size = MyMAXSIZE; }
//销毁线性表 template<class Elem> MyVector<Elem>::~MyVector() {//销毁线性表 if(!data) delete data; }
//清空线性表 template<class Elem> void MyVector<Elem>::MyClear() {//清空线性表 length = 0; }
//求线性表的长度 template<class Elem> int MyVector<Elem>::GetLength() {//获取线性表中元素的个数 return length; }
//判断线性表是否为空 template<class Elem> bool MyVector<Elem>::IsEmpty() {//获取线性表中元素的个数 return length==0; }
template<class Elem> Elem& MyVector<Elem>::GetElem(int pos) {//获取pos处的元素值 try { if (pos < 0 || pos > length - 1) throw exception("索引超过数组长度，GetElem下标越界！"); } catch (const exception &e) { cout << e.what() << endl; exit(-1); } return data[pos]; }
template<class Elem> Elem& MyVector<Elem>::operator [](int n) {//重载取元素运算符 try { if(n < 0 || n > length - 1) throw exception("索引超过数组长度，GetElem下标越界！"); } catch (const exception &e){ cout << e.what() << endl; exit(-1); } return data[n]; }
template<class Elem> int MyVector<Elem>::FindElem(Elem elem) {//查找线性表中指定值Elem的位置，若查找到则返回位置下标，否则返回-1表示没有查找到或者线性表为空 for (int i = 0; i < length; ++i) { if (data[i] == elem) return i; } return -1; }
平均查找长度ASL(Average Search Length)
为确定记录在表中的位置，需要与给定的值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。对含有 n n n个记录的表，查找成功时，
ASL=i=1∑nPiCi
其中 Pi表示第i个记录被查找的概率；Ci表示第i个记录需要比较的次数。将上式展开即为：
ASL=P1+2P2+...+(n−1)Pn−1+nPn
若假设线性表中没有重复元素，，则每个记录被查找的概率相等： 1/n，则
ASL=1/n(1+2+...+n)=2nn(n+1)=2n+1
所以线性表的查找时间复杂度为O(n)
template<class Elem>//线性表的扩容操作 void MyVector<Elem>::_expandSize() {//线性表的size变为两倍 size *= 2; Elem *tempData = new Elem[size]; memcpy(tempData,data,length*sizeof(Elem)); delete data;//删除之前的旧表 data = tempData; }
template<class Elem> void MyVector<Elem>::MyPush(Elem elem) {//往线性表末尾插入一个元素 if (length == size) {//线性表需要扩容 _expandSize(); } data[length++] = elem; }
template<class Elem> void MyVector<Elem>::MyInsert(int pos, Elem elem) { if (length == size) {//线性表需要扩容 _expandSize(); } if (pos == length) {//尾部插入 MyPush(elem); return; } else {//中间插入,将pos之后的值依次往后搬运 for (int i = length - 1; i >= pos; --i) data[i + 1] = data[i]; data[pos] = elem; } ++length;
插入操作的平均算法移动次数：
Eins=n+11i=1∑n+1(n−i+1)=n+11[(n+1)(n+1)−[(n+1)+2n(n+1)]]=
n+112n(n+1)=2n
所以算法的时间复杂度为 O ( n )
template<class Elem> void MyVector<Elem>::MyPopBack() {//删除尾部元素 if (length == 0) return; --length; }
template<class Elem> void MyVector<Elem>::MyDelete(int pos) {//随机删除一个元素 if (pos < 0 || pos > length - 1) { cout << "删除位置有误，删除操作失败！" << endl; throw exception(); } if (pos == length - 1) { MyPopBack(); return; } else {//删除中间元素 for (int i = pos; i < length - 1; ++i) data[i] = data[i + 1]; } --length; }
删除操作的平均算法移动次数：
Edel=n1i=1∑n(n−i)=n12n(n−1)=2n−1
所以算法的时间复杂度为 O ( n )
5、线性表的优缺点
优点： 存储密度大，节点本身所占存储量/节点结构所占存储量=1；可以随机存取表中任意元素；
缺点： 在插入，删除某个元素时，需要移动大量的元素；某些申请的存储空间没有充分利用，浪费存储空间
