本文最后更新于 54 天前，如有失效或谬误请评论区留言。

线性结构的数学模型中的数据元素存在一对一的逻辑关系：

模型中存在唯一的一个元素作为”第一个”数据元素
模型中存在唯一的一个元素作为”最后一个”数据元素
除第一个元素外，其他的每个元素都有其唯一的直接前驱
除最后一个元素外，其他的每个元素都有其唯一的直接后继

1 线性表的逻辑定义

线性表是$n\geq0$个数据元素的有限序列，记作$List=(a_{1},a_{2},\dots,a_{n})$，满足上述所说的线性结构的四个特点，并且这些$a_{1},a_{2},\dots a_{n}$性质完全相同，属于同一个数据对象

人话就是类似数组这样的逻辑结构，有序，有头尾，且元素都是同类型

数据元素在线性表中的位置取决于它自身的序号

1.1 线性表的基本操作

线性表的基本操作包括：增、删、改、查等，这些基本操作的实现要根据线性表的物理存储结构去设计

综上，我们可以设计出线性表的抽象数据类型定义

ADT List{ // List是抽象类型定义的名字
    数据对象：D={ai:ai ∈ ElemSet;1 ≤ i ≤ n;n ≥ 0} // ElemSet是某一类数据类型的集合
    数据关系：R={<a_i,a_{i+1}>:ai,a_{i+1} ∈ D,1 ≤ i ≤ n-1} // 一对一的逻辑关系
    基本操作：
        InitList(&L)
            初始条件：表L不存在
            操作结果：构造一个空的线性表
        DestroyList(&L) 
            初始条件：线性表L存在 
            操作结果：销毁线性表L
        ClearList(&L) 
            初始条件：线性表L存在 
            操作结果：将线性表L置为空表 
        ListEmpty(L) 
            初始条件：线性表L存在 
            操作结果：若L为空，则返回TRUE;否则 返回FALSE 
        GetElem(L,i, &e) 
            初始条件：表L存在且1 ≤ i ≤ List Length(L) 
            操作结果：返回线性表L中的第i个元素的值 
        List Length (L) 
            初始条件：表L存在 
            操作结果：返回线性表中的所含元素的个数
        ……
}ADT List

如果我们实现了上述抽象数据类型定义之后，就可以定义该类型的变量，并且调用其包含的基本操作，我们需要解决：

顺序表的存储
实现定义的基本操作

2 线性表的顺序存储结构

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

它的特点就是它既是逻辑相邻，也是物理相邻，支持随机存取，即若已知一个元素序号i，可以计算出该元素的内存地址，直接在该地址进行操作，不用从第一个元素一个一个找，找到第i个元素，这也导致了它取用元素的速度很快，是常数级别$O(1)$

2.1 顺序表的实现

2.1.1 静态数组

#define maxlen 100
typedef struct{
    int elem[maxlen];// 足够大的数组存放线性表
    int length; // 数据元素个数
} SeqList;
SeqList L;
L.length = n
printf(L.elem[0]) // 输出线性表第一个元素

地址连续的存储在内部使用数组模拟实现，通过数组下标的形式存取元素

2.1.2 指针数组

#define LIST_INIT_SIZE 100 // 初始申请空间的大小
#define LISTINCREMENT 10// 指针数组每次扩大空间的大小
typedef struct{
    int *elem;
    int length; // 实际含有的数据元素个数n
    int listsize; // 现在的数组大小
} SqList;

int InitList(SqList &L){
    L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));// 申请LIST_INIT_SIZE个整型变量的空间，并把首地址的指针赋值给elem
    if(L.elem==0) // elem不是上面赋值的首地址
        exit(OVERFLOW); // 建立空表失败
    L.length=0; // 建的是空的线性表，实际上含有0个元素
    L.listsize=LIST_INIT_SIZE;// 当前的数组容量
    return OK; //OK是宏定义的常量1，表示空表成功建立
}
// 调用函数建立一个空表
SqList L;
int initStatus = 0;
initStatus = InitList(L)

教材和课件常用的宏定义和类型：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

2.1.3 顺序表的插入

在顺序表的第i个数据元素前插入一个值为x的新元素，我们需要考虑的有：

插入位置是否合理：$1\leq i\leq n+1$
线性表空间是不是够用：L.length < L.listsize或L.length<maxlen

所以我们想出如下的插入步骤：

判断插入位置是否合法
判断存储空间是不是溢出
将$a_{i}\to a_{n}$中间的元素向下移动，为新元素让出位置
把x置入第i个位置
修改表长

指针数组的实现如下

int InsertList(SqList &L,int i,int x){
    int j,*newbase;
    if(i<1||i>L.length+1)
        return -1; // 检查插入位置是否合理
    // 检查空间还够不够用
    if(L.length == L.listsize){
        //若不够用，则增大空间
        newbase = (int*)realloc(L.elem,(L.listsize+ LISTINCREMENT)* sizeof(int));// 重新申请一份加了增量的内存空间
        if(newbase == 0)
            exit(OVERFLOW); // 申请内存空间失败
        L.elem = newbase; // 把申请到的内存空间替换给原来指针
        L.listsize = L.listsize + LISTINCREMENT;
    }
    // 将an ~ ai 向下移动 ， 给新元素让出位置
    for(j = L.length;j >= i;j--)
        L.elem[j] = L.elem[j-1]
    L.elem[i-1] = x; // 插入新元素
    ++L.length; // 修改表长
    return 1;
}

该算法的基本操作是数据移动，在最坏情况下(往第一个元素前插入元素)，该算法要把后面n个元素全部移动，所以该算法时间复杂度为$O(n)$，当然你也可以通过列出插入位置和移动次数的表格，然后求平均观察得到式子的最高次项的方法求得，你也可以通过观察代码循环计数循环次数的方式(仅适用于循环，涉及递归等一般就看不出来了，需要计算)

2.1.4 顺序表的删除操作

删除顺序表的第i个数据元素，我们需要考虑：

删除的元素是否合法，$1\leq i\leq n$

步骤：

将$a_{i+1}\to a_{n}$向上移动
修改表长

这个算法的实现和插入差不多，这里不写出具体实现

它的时间复杂度也是$O(n)$

2.1.5 顺序表的查找操作

在顺序表中查找与给定值e相等的数据元素，若存在返回其位置序号

直接把顺序表枚举，直到找到和e相等的，返回其序号，或者直到枚举到末尾也没有找到符合要求的元素，返回-1

int ListSearch(SqList L,int e){
    int i;
    for(i = 1;i <= L.length;i++){
        if(L.elem[i-1] == e)
            return i; // 返回
        return -1;
    }
}

这个算法时间复杂度显然是$O(n)$

3 线性表的链式表示和实现

3.1 定义

用一组地址任意的存储单元存放线性表的数据元素，其中每个数据元素存放的空间称为一个结点，每个结点包含两部分内容：值和指针，指针指示表中元素的逻辑关系

其特点是逻辑相邻的元素不一定物理相邻，所以只能顺序存取，如果要访问第i个元素，必须从第一个元素开始遍历直到找到第i个元素

在单链表(结点只存储一个指针)中指针既可以表示该结点的直接后继，也可以表示直接前驱，无非是方向的问题，总之都是表示节点之间相接的逻辑关系

3.2 两种单链表

3.2.1 不带表头节点的线性单链表

头指针直接指向第一个数据元素的结点空间，头指针对应空间的数据值是第一个数据元素，指针指向第二个数据元素的结点空间

这种单链表插入和删除操作略复杂，因为涉及头指针的修改，比如删除第一个数据元素，就需要修改头指针去指向第二个元素的结点空间

3.2.2 带表头节点的线性单链表

头指针指向的第一个结点是表头结点，表头结点的直接后继才是第一个数据元素，表头结点的值一般空着或者存放链表的特殊信息，比如其长度

这种链表的插入删除操作不会修改头指针，但是会多用一个结点空间

3.3 线性单链表的实现

线性单链表的实现同样有两种方式：动态链表和静态链表

3.3.1 静态链表

静态链表在课程要求中属于自学内容，这里先叙述，下面的函数实现全部基于动态链表

逻辑结构上相邻的元素，存储在指定的一大块内存空间中，数据元素只允许在这片内存空间中随机存放，这种结合顺序表和链表特点的链表叫做静态链表，也就是说静态链表其实就是在用数组模拟链表，它的优点和动态链表一样，删除和插入元素时间复杂度低，但是和数组一样，它需要提前分配一块较大的空间，这种实现方法一般用于在不提供访问内存的直接方法(如指针)时实现链表

#define MAX_SIZE 20

typedef struct ListNode{
    ElemType data; // 数据值
    int cur; // 静态链表中的游标
}ListNode

//实际上静态链表就是结构体数组
typedef ListNode StaticList[MAX_SIZE];

游标用于表示逻辑上的前后关系，结构体的数组下标仅用于存储数据元素，便于做遍历查找操作，在删除和插入的时候只需要移动游标即可

3.3.2 动态链表

typedef struct node{
    ElemType data;
    struct node *next;
} Node,*LinkList;
LinkList h,p; // 指针类型
Node *q; // 指针类型

初始化指针变量时需要使用malloc申请一块内存空间

p = (LinkList)malloc(sizeof(Node));
/*
p->data 就是结点的值域
p->next 就是结点的指针域
*/

3.3.3 动态链表的查找操作

在头指针为h的带表头结点的单链表中查找是否存在值为x的结点(链表已经建好)

思路就是顺次比较，从表的第一个元素顺次比较直到找到x，或找到末尾

LinkList search(LinkList h , int x){
    p = h->next; //带表头，所以第一个元素是表头直接后继
    while(p != NULL && p->data != x)// 没有找到末尾，没有找到x
        p = p-> next // 继续找
    return p; // 如果找到了，p就是需要的元素，如果没有，p为NULL
}

该算法时间复杂度显然为$O(n)$

不带表头、换一种实现方法的版本：

LinkList search(LinkList j , int x){
    p=h; // 不带表头，第一个就是第一个元素的结点地址
    while(p != NULL){
        if(p->data == x)
            return p; // 找到了，返回x所在结点地址
        else
            p=p->next;
    }
    return NULL; // 没找到，返回空指针
}

3.3.4 动态链表的插入操作

在动态链表的p结点之后插入一个新的数据元素x(链表已经建好)

步骤：

申请一块结点空间s
插入的数据x放入结点空间s
p的直接后继为新结点的s的直接后继
新结点s为p的直接后继

void insert(LinkList &p,int x){
    LinkList s;
    s = (LinkList)malloc(sizeof(Node)); // 申请结点空间s
    s->data = x;
    s->next = p->next; // p的直接后继为新结点的直接后继
    p->next = s; // p的新的直接后继是s
}

该算法显然时间复杂度为$O(1)$

3.3.5 动态链表的删除操作

删除动态链表中结点p的直接后继结点

步骤：

确认p是否存在直接后继q
p的新的直接后继变成q的直接后继
释放q的内存空间

void delete(LinkList &p){
    LinkList q;
    if(p->next != NULL){
        q = p->next;
        p->next = q->next;
        free(q);
    }
}

显然该算法时间复杂度也为$O(1)$

3.3.6 建立单链表

动态建立单链表是从一个空表开始，通过插入操作开始，有两种方法：

首插法
尾插法

看这个名字很容易就能想出来它们的实现方式，首插法就是对于一个空链表p，逆序读入n个需要加入链表的数据，对每个数据申请一块结点空间，把它插入到表中作为表头节点的直接后继；尾插法就是对于一个空链表p，顺序读入n个需要加入链表的数据，对每个数据申请一块结点空间，把它插入到表中做表尾结点的直接后继

尾插法：

void headCreateList(ListLink &L,int n){
    LinkList p , s; // s是表尾 p用于储存每次加入链表的数据的指针
    int i;
    L = (LinkList)malloc(sizeof(Node)); // 为头结点分配一块内存
    L->next = NULL; // 初始头结点没有直接后继
    s=L;
    for(i = 1;i <= n; i++){
        p=(LinkList)malloc(sizeof(Node));// 为插入的结点分配内存
        scanf("%d",&p->data); // 读入数据
        p->next = NULL; // 因为是尾插，所以每次插入的结点是表尾
        s->next = p; // 表尾的直接后继
        s = p; // 更新新的表尾
    }
}

首插法略

3.4 循环单列表

表尾结点的直接后继是头结点：

从表中任意结点出发能找到所有结点
p结点为尾结点的条件：p->next == h，h是表头节点
为空表的条件：h->next == h

3.5 双向链表

每个结点空间包括值，两个指针，分别储存结点的直接后继和直接前驱：

从任意结点出发可以找到所有结点

4 一元多项式的表示和相加

使用线性表，元素的下标$0,1,\dots,n$表示指数，元素的值表示系数，很简单不多说