数据结构之线性表（顺序表示）

定义

线性表是具有相同数据类型的$n(n>=0)$个数据元素的有限序列。其中$n$为表长，当$n=0$时，线性表是一个空表。若用$L$命名线性表，则一般表示如下：
$$
L = (a_1,a_2,…,a_i,a_{i+1},..,a_n)
$$
其中，$a_1$是唯一的第一个数据元素，又称为表头元素；$a_n$是唯一的最后一个元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

特点：

1. 表中元素个数有限且具有逻辑上的有序性
2. 表中元素数据类型相同
3. 表中元素具有抽象性，仅讨论元素逻辑关系，不考虑元素内容

划分：

1. 顺序存储： 顺序表
2. 链式存储：

   • 单链表 （指针实现）
   • 双链表（指针实现）
   • 循环链表（指针实现）
   • 静态链表（借助数组实现）

注意：

1. 线性表是逻辑结构，表示元素之间一对一的相邻关系
2. 顺序表和链表是指存储结构

线性表的基本操作

• InitList(&L)：初始化表
• Length(L)：求表长
• LocateElem(L,e)：按值查找
• GetElem(L,i)：按位查找
• ListInsert(&L,i,e)：插入操作
• ListDelete(&L,i,&e)：删除操作
• PrintList(L)：输出
• Empty(L)：判空
• DestroyList(&L)：销毁

线性表的顺序存储

线性表的顺序存储又称顺序表，它是一组地址连续的存储单元，它的逻辑顺序和物理顺序相同。
注意：线性表中的位序是从1开始的，而数组中元素的下标是从0开始的。

假定线性表的元素类型为ElemType，那么线性表的顺序存储类型可以描述如下：

#define MaxSize 50          //定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize]; //顺序表的元素
    int length;             //顺序表的当前长度
}SqList;                    //顺序表的类型定义

一维数组可以是静态分配的（数据可能溢出），也可以是动态分布的。C的初始动态分配语句为：

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)

#define InitSize 100       //表长的初始定义
typedef struct{            
    ElemType *data;       // 动态分布数组的指针
    int MaxSize,length;   // 数组的最大容量和当前个数
}SeqList;

1. 插入操作
   在顺序表L的第i个位置插入新的元素e

   bool ListInsert(SqList &L,int i,ElemType e){
       if(i<1||i>L.length+1)           //判断i范围是否有效
           return false;
       if(L.length>=MaxSize)          //若当前空间已满，则不能插入
           return false;
       for(int j=L.length;j>=i;j--)  //将第i个元素及后面的元素后移
           L.data[j]=L.data[j-1]
       L.data[i-1]=e;               //插入元素e
       L.length++;                  //表长加1
       return true;
   }

2. 删除操作
   删除表L中第i个位置的元素，删除的元素用变量e返回

   bool ListDelete(SqList &L,int i,&e){
       if(i<1||i>L.length)           //判断i范围是否有效
           return false;
       e=L.data[i-1];               //将被删除的元素赋值给e
       for(j=i;j<L.length;j++)      //将第i个位置后的元素前移
           L.data[j-1]=L.data[j]
       L.length--;                 //表长减1
       return true;
   }

3. 按值查找
   在表L中查找第一个元素值等于e的元素，并返回其位序

   int LocateElem(SqList &L, ElemType e){
       int i;
       for(i=0;i<L.length;i++)
           if(L.data[i]==e)
               return i+1;
       return 0;
   }

总结：上述三种操作的时间复杂度均为O(n)。

顺序表的特点：

1. 随机访问，通过首地址和元素序号可以在O(1)的时间内找到指定元素
2. 存储密度高，每个结点只存储数据元素
3. 逻辑相邻元素物理上也相邻，插入和删除需要移动大量元素