线性表 线性表（linear list）是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。 线性表是具有相同特征的数据元素的一个有限序列。
线性表由n（n>=0）个数据元素（结点）a1，a2，…，an组成的有限序列 线性表中元素的个数n（n≥0）称为线性表的长度，n=0时称为空表。 对于非空的线性表或线性结构,特点为: 1.存在唯一的一个被称作"第一个"的数据元素； 2.存在唯一的一个被称作"最后一个"的数据元素； 3.除第一个之外,结构中的每个数据元素均只有一个前驱； 4.除最后一个之外,结构中的每个数据元素均只有一个后继。 此图更直观的描述它们之间的关系： 类型定义 抽象数据类型线性表的定义如下： 基本操作： InitList（&L） （Initialization List）初始 //构造一个空的线性表L
DestroyList（&L） 销毁 //销毁线性表L
ClearList（&L） 清空 //将线性表L重置为空表
ListEmpty（L） //判断线性表L是否为空表，若为空表则返回TURE；否则返回FALSE
ListLength（L） 计算长度 //返回线性表L中的数据元素个数
GetElem（L，i，&e） 获取元素 //条件：1< = i < = ListLength（L） //用e返回线性表L中第i个数据元素的值
LocateElem（L，e） //返回L中第1个值与e相同的元素在L中的位置。若这样的元素不存在，则返回值为0
PriorElem（L，cue_e，&pre_e） 求前驱 //若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前趋；否则操作失败，pre_e无意义
NextElem（L，cur_e，&next_e） 求后继 //若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继；否则操作失败，next_e无意义
ListInsert（&L，i，e） 插入元素 //在第L的第i个位置之前插入新的数据元素e，L的长度加一
ListDelete（&L，i） 删除元素 //删除L的第i个数据元素，L的长度减一
ListTraverse（L） 遍历 //对线性表L进行遍历，在遍历过程中对L的每个结点访问一次
线性表的顺序表 顺序表是在计算机内存中以数组的形式保存的线性表，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
线性表的顺序存储 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
逻辑位序和物理位序相差1
线性表顺序存储结构占用一片连续的存储结构。知道某个元素的存储位置就可以知道其他元素的存储位置，所以线性表的顺序存储结构是一种随机存取的存储结构。 假设线性表的每个元素占 l 个存储单元，则第 l+1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系： LOC（ai+1）= LOC（ai）+ l 由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到： LOC（ai+1）= LOC（ai）+（i-1） * l
C语言中： 数组静态内存分配
#define MAXSIZE 100 //线性表存储空间的初始分配量 typedef struct { ElemType elem[MAXSIZE]; int length; //当前长度 }SqList; //顺序表类型数组动态内存分配
#define MAXSIZE 100 //线性表存储空间的初始分配量 typedef struct{ ElemType *elem; //存储空间的基地址 int length; //当前长度 }SqList; //顺序表类型C++实现顺序表基本操作
#include<stdio.h> #include<iostream> using namespace std; //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status 是函数的类型，其值是函数结果状态代码 typedef int Status; // Status 相当于 int typedef char ElemType; //Elemtype 相当于 char #define MAXSIZE 100 //线性表存储空间的初始分配量 typedef struct { ElemType* elem; //存储空间的基地址 int length; //当前长度 }SqList; //顺序表类型名称为Sqlist Status InitList(SqList& L); //初始化操作，建立一个空的线性表L void DestroyList(SqList& L); //销毁线性表L void ClearList(SqList& L); //清空线性表L int ListEmpty(SqList L); //判断线性表L是否为空表 int ListLength(SqList L); //返回线性表L中的数据元素个数 Status GetElem(SqList L, int i, ElemType& e); //用e返回线性表L中第i个元素 Status LocateElem(SqList L, ElemType e); //返回L中第1个值与e相同的元素在L中的位置。若这样的元素不存在，则返回值为0 Status ListInsert(SqList& L, int i, ElemType e); //在线性表L的第i个位置插入元素e Status ListDelete(SqList& L, int i, ElemType& e); //删除线性表L中第i个元素并用e返回 void ListTraversals(SqList& L); //对线性表L进行遍历，在遍历过程中对L的每个结点访问一次 int main() { SqList L; //创建线性表L if (InitList(L)) cout << "线性表L创建成功" << endl; // ListInsert(L,1,'s'); if (ListInsert(L, 1, 's')) //在线性表第一个位置里放入元素 cout << "插入成功" << endl; else cout << "插入失败" << endl; // ListInsert(L,2,'m'); if (ListInsert(L, 2, 'm')) cout << "插入成功" << endl; else cout << "插入失败" << endl; // ListInsert(L,3,'h'); if (ListInsert(L, 3, 'h')) cout << "插入成功" << endl; else cout << "插入失败" << endl; cout << "遍历线性表：" << endl; ListTraversals(L); cout << "线性表长度:" << ListLength(L) << endl; ElemType e; ListDelete(L, 1, e); cout << "被删除的元素:" << e << endl; cout << "被删除后线性表的长度:" << ListLength(L) << endl; ElemType a = 'm'; int aa = LocateElem(L, a); cout << "该元素" << a << "在表中序号为：" << aa << endl; GetElem(L, 1, e); cout << "线性表L第一个元素：" << e << endl; cout << "清空线性表" << endl; ClearList(L); ListEmpty(L); if (ListEmpty(L)) cout << "线性表为空" << endl; else cout << "线性表非空" << endl; DestroyList(L); cout << "线性表已销毁" << endl; return 0; } Status InitList(SqList& L){ //构造一个空的顺序表L L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间 if (!L.elem) exit(OVERFLOW); //存储分配失败 L.length = 0; //空表长度为0 return OK; } void DestroyList(SqList& L) { if (L.elem)delete L.elem; //释放存储空间 } void ClearList(SqList& L) { L.length = 0; //将线性表的长度设置为0 } int ListEmpty(SqList L) { if (L.length == 0) return 1; else return 0; } int ListLength(SqList L) { return (L.length); //调用SqList结构里length } Status GetElem(SqList L, int i, ElemType& e){ if (i < 1 || i > L.length) return ERROR; //判断i值是否合理 e = L.elem[i - 1]; //elem[i-1]存储第i个数据元素 return OK; } Status LocateElem(SqList L, ElemType e) { //在线性表L中查找值为e的数据元素，返回其序号（是第几个元素） for (int i = 0; i < L.length; i++) if (L.elem[i] == e) return i + 1; //查找成功，返回序号i+1 return 0; //查找失败，返回0 } Status ListInsert(SqList& L, int i, ElemType e){ if ((i < 1) || (i > L.length + 1)) return ERROR; if (L.length == MAXSIZE) return ERROR; for (int j = L.length - 1; j >= i - 1; j--) { L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移 } L.elem[i - 1] = e; //将新元素 e 放入第 i 个位置 ++L.length; //表长加1 return OK; } Status ListDelete(SqList& L, int i, ElemType& e){ if ((i < 1) || (i > L.length)) return ERROR; e = L.elem[i - 1]; for (int j = i; j <= L.length - 1; j++) L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; } void ListTraversals(SqList& L) { //遍历一遍 for (int i = 0; i < L.length; i++) { cout << L.elem[i] << endl; } }