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

定义

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

特点：

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

划分：

顺序存储： 顺序表
链式存储：

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

注意：

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

线性表的基本操作

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;

插入操作
在顺序表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;
}

删除操作
删除表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;
}

按值查找
在表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)。

顺序表的特点：

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