线性结构的定义：
若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为：（a1 , a2 , ……, an）
线性表
线性结构表达式：（a1 , a2 , ……, an）
线性结构的特点：
① 只有一个首结点和尾结点；
② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
简言之，线性结构反映结点间的逻辑关系是 一对一 的
线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是线性表
一、线性表的定义和特点
线性表的定义：用数据元素的有限序列表示
例1 分析26 个英文字母组成的英文表
（ A, B, C, D, …… , Z） 数据元素都是字母; 元素间关系是线性
例2 分析学生情况登记表
数据元素都是记录；
元素间关系是线性
同一线性表中的元素必定具有相同特性
顺序存储结构存在问题
存储空间分配不灵活
运算的空间复杂度高
总结
线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作
二、线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单
元中的存储结构。
简言之，逻辑上相邻，物理上也相邻
顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，
可通过数组V[n]来实现。
顺序表的类型定义
#define MAXSIZE 100 // 最大长度 typedef struct { ElemType *elem; // 指向数据元素的基地址 int length; // 线性表的当前长度 }SqList；
线性表的重要五大基本操作
1、初始化线性表L （参数用引用）
Status InitList_Sq(SqList &L) //构造一个空的顺序表L { L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; }
1、初始化线性表L （参数用指针）
Status InitList_Sq(SqList *L) //构造一个空的顺序表L { L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0 return OK; }
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 GetLength(SqList L) { return (L.length); }
5、判断线性表L是否为空
int IsEmpty(SqList L) { if (L.length==0) return 1; else return 0; }
取值操作
（根据位置i获取相应位置数据元素的内容）
获取线性表L中的某个数据元素的内容
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; }
查找操作
// 在线性表L中查找值为e的数据元素 int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; return 0; }
插入操作(插在第i个结点之前)
算法步骤
（1）判断插入位置 i 是否合法。
（2）判断顺序表的存储空间是否已满。
（3）将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。
（4）将要插入的新元素e放入第i个位置。
（5）表长加1，插入成功返回OK。
// 在线性表L中第i个数据元素之前插入数据元素e Status ListInsert_Sq(SqList &L,int i ,ElemType e) { if(i<1 || i>L.length+1) return ERROR; // i值不合法 if(L.length==MAXSIZE) return ERROR; // 当前存储空间已满 for(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; }
5.删除操作(删除第i个结点)
算法步骤
（1）判断删除位置i 是否合法（合法值为1≤i≤n）。
（2）将欲删除的元素保留在e中。
（3）将第i+1至第n 位的元素依次向前移动一个位置。
（4）表长减1，删除成功返回OK。
// 将线性表L中第i个数据元素删除 Status ListDelete_Sq(SqList &L,int i) { if((i<1)||(i>L.length)) return ERROR; // i值不合法 for (j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; // 被删除元素之后的元素前移 --L.length; // 表长减1 return OK; }
三、顺序表(顺序存储结构)的特点
（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
四、顺序表的优缺点
优点：
- 存储密度大（结点本身所占存储量/结点结构所占存储量）
- 可以随机存取表中任一元素
缺点：
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
