线性表（List）

是指由零个或者多个数据元素组成的有限序列（有顺序，有具体个数，只有一个前驱和一个后驱）。如班级的点名册就是一个比较复杂的线性表。

ADT 线性表（List）
Data
    线性表的数据对象集合为 {a1, a2, ... , an}, 每个元素的类型均为 Elem_Type。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    init_list(*L)：初始化表。构造一个空的线性表L。
    clear_list(*L)：清空线性表。
    list_is_empty(L)：判空操作。如果线性表L为空表，则返回true，否则返回 false。
    list_length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
    list_locate_elem(L,e)：按值查找操作。在线性表L中查找与给定值e相等的元素，如果查找成功，则返回该元素在表中序号；否则，返回0表示失败。（通常将0号位空出，不放元素）
    list_get_elem(L,i,*e)：按位查找操作。获取线性表L中第i个位置的元素的值给e。
    list_insert(*L,i,e)：插入操作。在线性表L中第i个位置插入指定元素e。
    list_delete(*L,i,*e)：删除操作。删除线性表L中第i个位置的元素，并用e返回删除元素的值。
endADT

我们只要结合以上的基本操作就可以实现我们想要的功能。

顺序存储线性表

线性表有两种物理存储方式：顺序存储结构和链式存储结构。在此先介绍顺序存储结构的线性表。

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据单元。就和C语言中的数组一样，唯一的区别就是我们习惯将线性表的0号位空出（也可以用来存放元素的个数）。

实现

构建表

这里我们将数组进行封装就构成了顺序存储线性表，在数组的基础上增加了当前长度和数组最大长度的变量。

#define MAX_SIZE 20 // 顺序线性表的每次增长的最大长度
typedef int Elem_Type; // 顺序线性表的数据类型

/* 构建了顺序线性表 */
struct SQ_List // 自定义类型名为sequential lists的缩写
{
    Elem_Type *data; // 数据存放区
    int length; // 为线性表当前长度
    int size; // 线性表当前尺寸
} list; // 声明一个线性表
/* C语言要加这些，C++不用 */
typedef struct SQ_List SQ_List;
typedef int bool;
#define true 1
#define false 0

初始化

初始化中创建数组方法就是清空数组。

对这个线性表按顺序赋了初值。

void init_list(SQ_List *L)
{
    clear_list(L); // 创建数组方法和清空数组一样
    /* 赋初值 */
    L->data[0] = 0;
    for(int i=1 ; i<=MAX_SIZE ; i++)
    {
        L->length++;
        L->data[L->length] = i;
    }
}

清空

申请空间时由于我们从1开始数元素，所以头节点不放元素且要申请的空间得加1。

void clear_list(SQ_List *L)
{
    L->size = MAX_SIZE; // 初始化表尺寸
    L->length = 0; // 初始化表长
    L->data = (Elem_Type *)malloc(sizeof(Elem_Type)*(1+MAX_SIZE)); // 申请空间
}

判空

bool list_is_empty(SQ_List L)
{
    if(L.length == 0)
    {
        return true;
    }
    return false;
}

获取表长

int list_length(SQ_List L)
{
    return L.length;
}

按值查找

按值查找是采用遍历的方式，因此时间复杂度是O(n)。

如果查找成功，则返回该元素在表中的位置；否则，返回0表示失败。

int list_locate_elem(SQ_List L,Elem_Type e)
{
    for(int i=1 ; i<=L.length ;i++)
    {
        if(L.data[i] == e)
        {
            return i;
        }
    }
    return 0;
}

按位查找并获取

按位查找的时间复杂度为O(1)，因此我们可以说其有着随机存储的结构特点。

bool list_get_elem(SQ_List L,int i,Elem_Type *e)
{
    if(0<i && i<=L.length) // 判断要找的位是否在表中
    {
        *e = L.data[i];
        return true;
    }
    return false;
}

插入

插入的情况有多种：

如果线性表长度已经等于其尺寸，则抛出异常或者动态增加数组容量（这里我们选择扩容）；
插入位置不合适，退出插入并抛出异常；
插入不在表尾，则要从最后一个元素开始向前遍历到插入的第i位，将这些元素向后移一位；
插入在表尾，直接插入。

若插入成功，表长+1。

bool list_insert(SQ_List *L,int i,Elem_Type e)
{
    if(L->length == L->size) // 是否要扩容
    {
        L->size += MAX_SIZE;
        L->data = (Elem_Type *)realloc(L->data,sizeof(Elem_Type)*(L->size+1));
    }
    if(i<1 || i>(L->length+1)) // 插入位置是否正确
    {
        return false;
    }
    if(i <= L->length) // 当插入的位置不是表尾时
    {
        /* 原表中插入位及以后的元素向后移 */
        for(int j=L->length ; j>=i ; j--)
        {
            L->data[j+1] = L->data[j];
        }
    }
    L->data[i] = e; // 插入元素
    L->length++; // 表长增加
    return true;
}

删除

删除的情况也有多种：

空表，抛出异常；
删除位置不合理，抛出异常；
删除位置正确，取出删除位置的元素，然后从删除元素后的位置开始遍历到最后一位元素的位置，分别将它们向前移动一位。

如果删除成功，则表长-1，并判断是否可以缩容。

bool list_delete(SQ_List *L,int i,Elem_Type *e)
{
    if(L->length == 0) // 是空表时
    {
        return false;
    }
    if(i<1 || i>L->length) // 插入位置是否正确
    {
        return false;
    }
    *e = L->data[i]; // 获取将要删除的元素
    /* 原表中删除位后的元素向前移 */
    for(int j=i ; j<L->length ; j++)
    {
        L->data[j] = L->data[j+1];
    }
    L->length--; // 表长-1
    if((L->size-L->length) == MAX_SIZE) // 是否可以缩容
    {
        L->size -= MAX_SIZE;
        L->data = (Elem_Type *)realloc(L->data,sizeof(Elem_Type)*(L->size+1));
    }
    return true;
}

最好情况：如果插入和删除操作都刚好在表尾，那么时间复杂度为O(1)。

最坏情况：如果插入和删除操作都刚好在表头，那么时间复杂度为O(n)。

平均情况：O((n-1)/2)，简化后是O(n)。

其他部分

/* 打印表 */
void print_list(SQ_List L)
{
    for(int i=1 ; i<=L.length ; i++)
    {
        if(sizeof(Elem_Type) == 4) // 若Elem_Type是int时
        {
            printf("%d ",L.data[i]);
        }
    }
    printf("\n");
}