一、线性表的定义

---

线性表（Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。

其中：

• 数据元素的个数n定义为表的长度 = “list”.length() （”list”.length() = 0（表里没有一个元素）时称为空表）
• 将非空的线性表（n>=0）记作：（a[0]，a[1]，a[2]，…，a[n-1]）
• 数据元素a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同

一个数据元素可以由若干个数据项组成。数据元素称为记录，含有大量记录的线性表又称为文件。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。

二、线性表的抽象数据定义

---

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2, ......, an}，每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，
    除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。
Operation
    InitList(*L):               初始化操作，建立一个空的线性表L。
    ListEmpty(L):               若线性表为空，返回true，否则返回false。
    ClearList(*L):              将线性表清空。成功返回true，否则返回false。
    GetElem(L, i, *e):          将线性表L中的第i个位置元素值返回给e。
    LocateElem(L, e):           在线性表L中查找与给定值e相等的元素，
                                如果查找成功，返回该元素在表中序号表示成功；
    ListInsert(*L,i,e):         在L的第i个位置插入新元素e。
    ListDelete(*L,i,*e):        删除L中的第i个元素，并用e返回其值。
    ListLength(L):              返回L中的元素个数
    DestroyList(*L):            销毁顺序线性表L
    PriorElem(L,cur_e,*pre_e):  若cur_e是L的数据元素，且不是第一个，
                                则用pre_e返回它的前驱，否则操作失败，pre_e无定义
    NextElem(L,cur_e,*next_e):  若cur_e是L的数据元素，且不是最后一个，
                                则用next_e返回它的后继，否则操作失败，next_e无定义
endADT

三、线性表的顺序存储结构

---

线性表的顺序存储结构，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

3.1 存储结构

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW 1
#define INFEASIBLE 2
#include <stdio.h>
#include <stdlib.h>

/* 线性表的动态分配顺序存储结构 */
#define LIST_INIT_SIZE 10       /* 线性表存储空间的初始分配量 */
#define LIST_INCREMENT 2        /* 线性表存储空间的分配增量 */
typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType *elem;     /* 存储空间基址 */
    int length;         /* 当前长度 */
    int listsize;       /* 当前分配的存储容量(以sizeof(ElemType)为单位) */
}SqList;

3.2 具体代码如下

/* 顺序表示的线性表的基本操作(12个) */
void InitList(SqList *L) /* 算法2.3 */
{ /* 操作结果：构造一个空的顺序线性表L */
    L->elem = malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L->elem)
        exit(OVERFLOW); /* 存储分配失败 */
    L->length = 0; /* 空表长度为0 */
    L->listsize = LIST_INIT_SIZE; /* 初始存储容量 */
}

void DestroyList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

void ClearList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    L->length = 0;
}

Status ListEmpty(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
    if(L.length == 0)
        return TRUE;
    else
        return FALSE;
}

int ListLength(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
    return L.length;
}

Status GetElem(SqList L,int i,ElemType *e)
{ /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值 */
    if(i < 1 || i > L.length)
        return ERROR;
    *e =* (L.elem + i - 1);
    return OK;
}

int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */
    /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
    /*           若这样的数据元素不存在，则返回值为0。 */
    ElemType *p;
    int i = 1; /* i的初值为第1个元素的位序 */
    p = L.elem; /* p的初值为第1个元素的存储位置 */
    while (i <= L.length && !compare(*p++,e))
        ++i;
    if(i <= L.length)
        return i;
    else
        return 0;
}

Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
    /*           否则操作失败，pre_e无定义 */
    int i = 2;
    ElemType *p = L.elem+1;
    while(i <= L.length && *p != cur_e)
    {/*?为什么前面使用函数指针,但是此却却直接使用值比较呢?*/
        p++;
        i++;
    }
    if(i > L.length)
        return INFEASIBLE; /* 操作失败 */
    else
    {
        *pre_e =* --p;
        return OK;
    }
}

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
    /*           否则操作失败，next_e无定义 */
    int i = 1;
    ElemType *p = L.elem;
    while(i < L.length && *p != cur_e)
    {
        i++;
        p++;
    }
    if(i == L.length)
        return INFEASIBLE; /* 操作失败 */
    else
    {
        *next_e =* ++p;
        return OK;
    }
}

Status ListInsert(SqList *L,int i,ElemType e)
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */
    /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    ElemType *newbase,*q,*p;
    if(i < 1 || i > L->length + 1) /* i值不合法 */
        return ERROR;
    if(L->length >= L->listsize) /* 当前存储空间已满,增加分配 */
    {
        newbase=realloc(L->elem,(L->listsize + LIST_INCREMENT)*sizeof(ElemType));
        if(!newbase)
            exit(OVERFLOW); /* 存储分配失败 */
        L->elem = newbase; /* 新基址 */
        L->listsize += LIST_INCREMENT; /* 增加存储容量 */
    }
    q = L->elem + i - 1; /* q为插入位置 */
    for(p = L->elem + L->length - 1;p >= q;--p) /* 插入位置及之后的元素右移 */
        *(p+1) =* p;
    *q = e; /* 插入e */
    ++L->length; /* 表长增1 */
    return OK;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    ElemType *p,*q;
    if(i < 1 || i > L->length) /* i值不合法 */
        return ERROR;
    p = L->elem + i - 1; /* p为被删除元素的位置 */
    *e = *p; /* 被删除元素的值赋给e */
    q = L->elem + L->length - 1; /* 表尾元素的位置 */
    for(++p;p <= q;++p) /* 被删除元素之后的元素左移 */
        *(p-1) = *p;
    L->length--; /* 表长减1 */
    return OK;
}

四、顺序线性表的优缺点

4.1 时间性能：

• 查找： O(1)
• 插入和删除： O(N)

4.2 空间性能：

• 顺序存储结构需要预分配存储空间
  分配大了容易造成空间浪费，分小了容易发生溢出。

五、适用场景

• 尾插尾删较多
• 绝大多数都是读取