数据结构--线性表的顺序实现

线性表

线性表是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)。