线性表
线性表是n个数据特性相同的元素的组成有限序列，是最基本且常用的一种线性结构(线性表，栈，队列，串和数组都是线性结构），同时也是其他数据结构的基础。
对于非空的线性表或者线性结构的特点：
（1）存在唯一的一个被称作“第一个”的数据元素；
（2）存在唯一的一个被称作“最后一个”的数据元素；
（3）除第一个外，结构中的每个数据元素均只有一个前驱；
（4）除最后一个外，结构中的每个数据元素均只有一个后继；
二、线性表的两种实现方式
1、顺序表示（顺序表）
概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。
特点：逻辑上相邻的数据元素，物理次序也是相邻的。
只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。
2、代码实现
以最简单的图书信息管理为例：首先先创建两个数据结构，如下：
#define maxsize 100 //定义图书最大数量
//图书信息的数据结构
typedef struct
{
char no[20]; //图书ISBN
char name[30]; //图书名字
float price; //图书价格
}Book;
//顺序表数据结构
typedef struct
{
Book*elem; //储存空间的基地址
int length; //数据结构的长度 也就是图书表中图书的个数
}SqList; //图书表的顺序存储结构类型为SqList
//定义SqList类型的变量
SqList L;
3、顺序表中基本操作的实现
（一）初始化：顺序表的初始化操作就是构造一个空的顺序表
【算法步骤】
1.为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
2.将表的当前长度设为0。
【算法描述】
Status InitList(SqList &L)
{ //构造一个空的顺序表L
L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if( ! L.elem ) {
exit(OVERFLOW); //存储分配失败退出
}
L.length = 0; //空表长度为0
return OK;
}
动态分配线性表的存储区域可以更有效的利用系统的资源，当不需要线性表时，可以使用销毁操作及时释放占用的存储空间。
（二）取值：取值操作就是根据指定的位置序号 i 获取顺序表中第 i 个数据元素的值
【算法步骤】
1.判断指定位置序号 i 值是否合理（1<= i <= L.length）若不合理，则返回ERROR。
2.若i值合理，则将第i个数据元素L.elem[i-1]赋给参数e，通过e返回第i个元素的传值。
【算法描述】
Status GetElem(SqList L, int i, ElemType &e)
{
if(i<1 || i>L.length ){
return ERROR; //判断 i 值是否合理若不合理，则返回ERROR。
}
e = L.elem[i-1]; //elem[i-1]单元存储第i个数据元素
return OK;
}
【算法分析】
显然，顺序表取值操作算法的时间复杂程度为O(1)
（三）查找：查找操作是根据指定元素值e，查找顺序表中第1个与相等的元素。若查找成功，则返回该元素在表中的位置序号；若失败，则返回0。
【算法步骤】
1.从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i],则查找成功，返回该元素的序号i+1。
2.若遍历整个顺序表都没有找到，则查找失败，返回0。
【算法描述】
int LocateElem(SqList L, ElemType e)
{ //在顺序表L中查找值为e的数据元素，返回其序号
for(i = 0; i < L.length; i++){
if(L.elem[i] == e){
return i+1; //查找成功，返回序号i+1
}
}
return 0;
}
【算法分析】
显然，顺序表取值操作算法的时间复杂程度为O(1)
（四）插入：线性表的插入操作是指在第i个位置插入一个新的数据元素 e ，使长度为n的线线性表变成长度为 n+1 的线性表。
【算法步骤】
1.判断插入位置i是否合法（i值合法范围是 1<= i <= n+1）,若不合法则返回ERROR。
2.判断顺序表的存储空间是否已满，已满则返回ERROR。
3.将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时移动）。
4.将要插入的元素e放在第i的位置。
5.表长加1.
【算法描述】
Status ListInsert (SqList &L, int i, ElemmType e){
//在顺序表L中的第i位置插入新的元素e，i值的合法范围是1<= i <= L.length+1
if((i<1) || (i.length+1)){
return ERROR; //i值不合法
}
if((i<1) || (i.length+1)){
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.lemgth; //表长加1
return OK;
}
【算法分析】
在顺序表中插入一个数据时，其时间主要耗费在移动元素上，但是移动元素取决于元素的插入数据的位置
所以，其时间复杂程度为O(n)。
（五）删除：线性表的删除操作是指将顺序表中的第i个元素删去，将长度为n的表变成长度为n-1。
【算法步骤】
1.判断删除位置i是否合法（i值合法范围是 1<= i <= n）,若不合法则返回ERROR。
2.将i+1个至i个元素依次向前移动一个位置（i = n时不用移动）。
3.将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时移动）。
4.表长减1。
【算法描述】
Status ListInsert (SqList &L, int i){
//将顺序表L中的第i位置的元素删除，i值的合法范围是1<= i <= L.length+1
if((i<1) || (i.length+1)){
return ERROR; //i值不合法
}
for(j = i; j <= L.length-1; j++){
L.elem[j-1] = L.elem[j]; //插入位置及之后的元素后移
}
L.elem[i-1] = e; //将新元素e放入第i个位置
--L.lemgth; //表长加1
return OK;
}
【算法分析】
在顺序表中删除一个数据时，其时间主要耗费在移动元素上，但是移动元素取决于元素的删除数据的位置
所以，其时间复杂程度为O(n)。
网友评论