线性表（二）
在开始这篇文章之前，我先把程序当中用到的一些头文件以及预定义给出
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //线性表初始分配空间大小
typedef int ElemType //预定义ElemType为int类型标识符
#define ERROR -1 //预定义ERROR的值为-1
#define OK 1 //预定义OK的值为1l 线性表的顺序存储表示
算法描述：
线性表中的数据元素我们一般用结构体来表示
代码实现：
/**************************/
/*线性表的数据元素类型定义*/
/**************************/
typedef struct //结构定义
{
ElemType *elem;//存储空间的基地址
int length; //当前长度（含几个元素）
}SqList; //线性表顺序存储结构类型名l 构造一个空线性表
算法描述：
（1）按给定的线性表存储空间进行分配
（2）令线性表长为0
代码实现：
/**************************************************/
/* 函数功能：构造一个空的线性表 */
/* 函数参数：指向SqList型变量的引用变量L */
/* 函数返回值：空 */
/* 函数名：InitList() */
/*************************************************/
void InitList(SqList &L)
{
L.elem = (ElemType*)malloc(MAXSIZE *sizeof(ElemType));//分配存储空间
L.length = 0;//初始化表长为0（没有元素）
}l 销毁线性表
算法描述：
分配内存空间用的是C语言的malloc函数，销毁线性表就是释放所分配的内存空间，所以用delete函数，但是要先判断线性表是否存在
代码实现：
/*************************************************/
/* 函数功能：销毁线性表 */
/* 函数参数：SqList的引用变量L */
/* 函数返回值：空 */
/* 函数名：DestroyList() */
/*************************************************/
void DestroyList(SqList &L)
{
if(L.elem) //线性表存在
delete[] L.elem;//释放存储空间
}l 清空线性表
算法描述：
只需要将线性表的长度置为0即可（先判断线性表是否存在）
代码实现：
/**************************************************/
/* 函数功能：清空线性表 */
/* 函数参数：SqList的引用变量L */
/* 函数返回值：空 */
/* 函数名：ClearList() */
/**************************************************/
void ClearList(SqList &L)
{
if(L.elem) //线性表存在
L.length = 0;//将线性表的长度置为0
}l 判断是否为空表
算法描述：
为空表就是线性表中没有数据元素，则length等于0
代码实现：
/**************************************************/
/* 函数功能：判断是否为空表 */
/* 函数参数：SqList的引用变量L */
/* 函数返回值：int */
/* 函数名：EmptyList() */
/**************************************************/
int EmptyList(SqList &L)
{
if(L.length == 0)//线性表长度为0，则是空表，返回1
return OK;
else
return ERROR; //不是空表，则返回-1
}l 求线性表的长度
算法描述：
长度就是length，直接返回length的值即可
代码实现：
/**************************************************/
/* 函数功能：求线性表的长度 */
/* 函数参数：SqList的引用变量L */
/* 函数返回值：int */
/* 函数名：LengthList() */
/**************************************************/
int LengthList(SqList &L)
{
return L.length;//返回线性表的长度（数据元素个数）
}l 求线性表中某位置的数据元素值
算法描述：
用户传入位置值i，首先要进行判断，i是否合法，即不能小于1或者是大于线性表的长度，然后用一个变量来保存得到的值
代码实现：
/********************************************************/
/* 函数功能：获取线性表某位置的数据元素值 */
/* 函数参数：SqList的引用变量L,位置i,实参的引用变量e */
/* 函数返回值：int */
/* 函数名：GetElem() */
/********************************************************/
int GetElem(SqList &L,int i,ElemType &e)
{
if(i < 1 || i > L.length)//判断i的值是否合理
return ERROR; //不合理则返回ERROR
e = L.elem[i-1]; //第i-1的单元存储着第i个数据
return OK;
}l 查找线性表中值为e的元素
算法描述：
一般方法是从第一个元素开始，与e进行匹配，如果不相等，就往后继续匹配，如果相等了就返回该值的位置，这个遍历过程，通过循环来实现
图1 查找16
图2 查找50
代码实现：
/********************************************************/
/* 函数功能：查找线性表中值为e的元素 */
/* 函数参数：SqList的引用变量L,变量e */
/* 函数返回值：int */
/* 函数名：LocateElem() */
/********************************************************/
int LocateElem(SqList &L,ElemType &e)
{
for(int i = 0;i < L.length;i++)//遍历整个线性表
if(L.elem[i] == e) //如果与所找的值匹配
return i+1; //返回位置
return 0; //线性表遍历结束都没找到，则返回0
}l 在线性表的第i个元素之前插入元素e
算法描述：
（1）判断插入位置i是否合法
（2）判断顺序表的存储空间是否已满
（3）将第n至第i位的元素依次向后移动一个位置，空出第i个位置
（4）将要插入的新元素e放入第i个位置
（5）表长+1，插入成功，返回OK
图3 插入99
分析：
插入的时候，是从最后一个元素开始向后移，插在第4个节点之前，移动了6-4+1次，那么插在第n个节点之前，移动n-i+1次
代码实现：
/********************************************************/
/* 函数功能：在线性表第i个元素之前插入元素e */
/* 函数参数：SqList的引用变量L,位置i,变量e */
/* 函数返回值：int */
/* 函数名：InsertList() */
/********************************************************/
int InsertList(SqList &L,int i,ElemType e)
{
if(i < 1 || i > L.length+1) //i值不合法
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;
}l 将线性表中第i个元素删除
算法描述：
（1）判断插入位置i是否合法
（2）将第i+1至第n位的元素依次向前移动一个位置
（3）表长-1，删除成功，返回OK
图4 删除第四个元素
分析：
删除的时候，是从第i+1个开始向前移，删除第4个节点，移动6-4次，删除第i个节点，移动n-i次
代码实现：
/********************************************************/
/* 函数功能：将线性表中第i个元素删除 */
/* 函数参数：SqList的引用变量L,位置i */
/* 函数返回值：int */
/* 函数名：DeleteList() */
/********************************************************/
int DeleteList(SqList &L,int i)
{
if(i < 1 || i > L.length) //i值不合法
return ERROR;
for(int j = i;j < L.length;j++)
L.elem[j-1] = L.elem[j];//被删除元素后面的元素前移
L.length--; //表长-1
return OK;
}总结一下：
（1）查找、插入、删除算法的平均时间复杂度为O(n)
（2）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
（3）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
（4）这种存取元素的方法被称为随机存取法
顺序表的优点：
（1）存储密度大（结点本身所占存储量/结点结构所占存储量）
（2）可以随机存取表中任一元素
顺序表的缺点：
（1）在插入、删除某一元素时，需要移动大量元素
（2）经常浪费存储空间
（3）属于静态存储形式，数据元素的个数不能自右扩充
为了克服这一缺点，下一篇文章我就会讲到另一种数据结构——链表。我的博客地址http://www.mathor.top/
腾讯云开发者
