线性表

线性表

定义

线性表(Linear List)是具有相同数据类型的 n ($n\geqslant0$) 个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表。若用 L 命名线性表，则一般表示为 $$ L=(a_1, a_2,\cdots,a_j, a_{j+1},\cdots,a_n) $$ 相同：意味着每个数据元素所占空间一样大
有限序列：意味着所有按大小增加的整数不是一个线性表

$a_i$ 是线性表中“第 i 个” , 是元素线性表中的位序
$a_1$ 是表头元素，$a_n$ 是表尾元素. 有前继，后继的概念

基本操作

InitList(&L):初始化表
DestroyList(&L)：销毁操作
ListInsert(&L,i,e):插入操作，在表 L 中的第 i 个位置插入指定元素 e
ListDelete(&L,i,e):删除操作。删除表 L 在第 i 个位置的元素，并用 e 返回删除元素的值。
LocateElem(L,e):按值查找操作。在表 L 中查找具有给定关键字值的元素
GetElem(L,i):按位查找。获取表 L 中第 i 个位置元素的值。

其他常用操作

Length(L):求表长。返回线性表 L 的长度，即 L 中数据元素的个数.
PrintList(L):输出操作。按前后顺序输出线性表 L 的所有元素值。
Empty(L):判空操作，若L为空表，则返回true，否则返回false

注

一般操作为：初始化、销毁、增删改查
实际开发中可根据实际需求定义基本操作
函数名，参数的形式可自行更改，但是需要具有可读性
要确定什么时候需要使用引用类型

为什么需要实现基本操作

团队合作编程，定义的数据结构要让别人能够很方便的使用(封装)
将常用的操作/运算封装称函数，避免重复工作，降低出错风险

顺序表

顺序表，即用顺序存储的方式实现线性表
顺序存储，即逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

因此，在顺序表中，知道了第一个元素的存放位置为 LOC(L)，那么我们就知道了第一个元素的位置为 LOC(L)+数据元素的大小
数据元素的大小我们可通过 sizeof(ElemType) 获得

LOC 为 location的缩写

顺序表的实现-静态分配

#define MAXSIZE 10
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList;

sq 是 sequence 的缩写.

静态分配的局限性，数组的大小是不变的

顺序表的实现-动态分配

#define INITSIZE 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList;

// 初始化
void InitList(SeqList &L){
    L.data = (int *)malloc(INITSIZE*sizeof(ElemType));
    L.length = 0;
    L.MaxSize = INITSIZE;
}

// 增加动态的长度
void IncreaseSize(SeqList &L, int len){
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(ElemType));
    // 将数据复制到新区域
    for(int i=0;i<L.length;i++){
        L.data[i]=p[i];
    }
    // 顺序表最大长度增加 len
    L.MaxSize = L.MaxSize +len;
    // 释放原来的内存内存空间
    free(p);
}

特点

随机访问，即可在 O(1) 时间内找到第 i 个元素
存储密度高，每个节点只存储数据元素
拓展容量不方便（即使采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
删除、插入不方便

顺序表-插入

以静态分配为基础来写基本操作

void ListInsert(SqList &L, int i, int e){
    for(int j=L.length; j>=i; j++){
        // 从最后一个元素开始往后移，到第i个元素
        L.data[j]=L.data[j-1]; 
    }
    L.data[i-1]=e; // 第i个元素的索引为i-1
    L.length++;
}

由于可能遇到插入位置不对，顺序表已满等问题，插入操作代码的健壮性不够，因此可以进行修改

// 返回一个 bool值去表示插入状态：成功、失败
bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1)
        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; // 第i个元素的索引为i-1
    L.length++;
    return true;
}

顺序表-删除

// 删除，并返回被删除的值，并返回操作的状态：成功、失败
bool ListDelete(SqLsit &L, int i, int &e){
    if(i<1||i>L.length)
        return false;
    e = L.data[i-1];
    for(int j=i; j<L.length; j++)
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}

要注意，删除时和插入时，移动元素的顺序

顺序表-按位查找

静态存储

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

ElemType GetElem(SqList L, int i){
    return L.data[i-1];
}

动态分配也是一样的方法，因为分配的内存也是连续的

顺序表-按值查找

#define InitSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList;

// 返回第一个值相等的元素的位序.
// 这边假设了e可以直接用==比较
int locateElem(SeqList L, ElemType e){
    for(int i =0; i<L.length;i++){
        if  (L.data[i] == e) {return i+1;}
    }
    return 0;
}

按值查找的时间复杂度

最好时间复杂度=O(1)
最坏时间复杂度=O(n)
平均时间复杂度=O(n)

链表

优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

定义

struct LNode{             // 定义单链表节点类型
    ElemType data;        // 每个节点存放一个数据元素
    struct LNode *next;   // 指针指向下一个节点
}
struct LNode *p = (struct LNode *) malloc(sizeof(struct LNode))

这里声明变量的时候都是用的 struct LNode 这是C语言的特性，在C++中不需要，在C语言中为了方便我们可以使用关键字 typedef 给数据类型重命名

typedef <数据类型> <别名>
// e.g 
typedef struct LNode LNode;
LNode *p = (LNode *) malloc(sizeof(LNode));

更简洁的方法就是之前的写法

typedef struct LNode{    // 定义单链表节点类型
    ElemType data;       // 每个节点存放一个数据元素
    struct Lnode *next;  // 指针指向下一个节点
}LNode,*LinkList;

这段等价于

struct Lnode{
    ElemType data;
    struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

后者可读性更强.

LinkList 就是单链表的意思
代码中使用LinkList 和 LNode * 本质上没有区别，但是 LinkList 强调这是一个单链表，LNode * 强调这是一个节点

单链表-初始化

不带头节点的初始化

// 初始化
bool InitList(LinkList &L){
    L = NULL;
    return true;
}

// 判断是否为空
bool Empty(LinkList L){
    if(L == NULL)
        return true;
    else
        return false;
}

// 更简洁的写法
// bool Empty(LinkList L){return (L==NULL)}
int main(){
    LinkList L;
    // 初始化一个空表
    InitList(L);
}

带头节点的初始化

// 初始化
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode)); // 分配一个头节点
    if(L==NULL)
        return false;
    L->next = NULL;
    return true;
}

// 判断是否为空
bool Empty(LinkList L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

// 更简洁的写法
// bool Empty(LinkList L){return (L->next==NULL)}

int main(){
    LinkList L;
    // 初始化一个空表
    InitList(L);
}

头节点本身不存储数据，只是表示一个头

单链表-按位序插入

带头元素

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;  // 指针p指向当前扫描到的节点
    int j=0;   // 当前p指向的市第几个节点
    p = L;     // L指向头节点，头结点是第0个节点
    while (p! = NULL && j<i-1){
        p = p->next;
        j++;
    }
    if(p==NULL) // 判断第i-1个节点是否存在
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

先找到第i-1个节点p，然后新建一个节点s，分配空间，存储数据，先将p的下一个节点地址存在s中，再将s的地址存在p中，这两步不能颠倒.

最坏时间复杂度为O(n) 平均时间复杂度为O(n)

不带头节点

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;  // 头指针指向新节点
        return true;
    }
    LNode *p;  // 指针p指向当前扫描到的节点
    int j=1;   // 当前p指向的市第几个节点
    p = L;     // p指向第1个节点
    while (p! = NULL && j<i-1){
        p = p->next;
        j++;
    }
    if(p==NULL) // 判断第i-1个节点是否存在
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

一般使用带头结点的

单链表-后插操作

在指定节点后插入元素 e

bool InsertNextNode (LNode *p, ElemType e){
    if (p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)  // 内存分配失败(内存不足)
        return false;
    s->data = e;  // 用结点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

单链表-前插操作

在指定节点p前插入元素 e
当你知道p前面的任意一个节点时
直接遍历，直到找到p，获得他的前驱结点.

当你对p之前的结点一无所知时：

bool InsertPriorNode (LNode *p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->next = p->next;
    s->data = p->data;
    p->next = s;    // 新节点 s 连接到 p 之后
    p->data = e;    // 将 p 中元素复制到 s 中
    return true;    // p 中元素覆盖为 e
}

这种方法的和后插操作差不多，在指定结点后插入一个新结点，将新结点的数据换成指定结点的数据，然后将指定节点的数据换成需要插入的数据，秒啊！
更妙之处在于时间复杂度为 O(1).

单链表-按位序删除

之后都默认单链表是带头结点
删除表L中第i个位置的元素，并用e返回删除元素的值.

bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p;
    int j=0;
    p = L;
    while (p!=NULL && j<i-1>) {
        p = p->next;
        j++;
    }
    if (p==NULL)
        return false;
    if (p->next == NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

先存好该位序的结点信息，将前驱结点的next存后继结点的地址，然后再释放(描述的有点不太清楚，代码很清楚)

单链表-删除指定结点

能够找到前驱节点时，和按位序删除差不多，只需要循环即可

这里主要是讲找不到前驱节点时，如何删除，和前插操作类似

当指定结点有后继结点时

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q = p->next;
    p->data = p->next->data
    p->next = q->next;
    free(q);
    return true;
}

把后继结点的数据拷贝到指定节点，然后释放后继节点，效果一样，当不存在后继节点时会出现问题，这时只能通过前驱节点来循环查找了

单链表-按位查找

LNode * GetElem(LinkList L, int i){
    if(i<0)
        return NULL;
    LNode *p;
    int j=0;
    p = L;
    while (p!=NULL && j<i){
        p = p->next;
        j++;
    }
    return p;
}

找第0个结点，会返回头节点，找超过单链表长度的结点会返回NULL，平均时间复杂度为O(n)

这个时候我们已经封装了多个基本操作，重新回去看一些基本操作的实现变得更简单

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p = GetElem(L, i-1);
    if(p==NULL) // 判断第i-1个节点是否存在
        return false;
    return InsertPriorNode(p, e); // 插入指定元素后面
}

避免了重复代码、简介、易维护

单链表-按值查找

LNode * LocateElem(LinkList L, ElemType e) {
    LNode *p =L->next;
    // 从第1个结点开始数据域为e的结点
    while(p != NULL && p->data != e)
        p = p->next;
    return p;
}

如果要查的数据不存在，会返回NULL

单链表-获取长度

int Length(LinkList L){
    int len = 0;
    LNode *p = L;
    while (p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

同样的，这种操作时间复杂度也是O(n)

单链表-尾插法

LinkList List_TailInsert(LinkList &L){ // 正向建立单链表
    int x;    // 设ElemType为整型
    L = (LinkList)malloc(sizeof(LNode)); // 建立头指针
    LNode *s, *r = L;   // r为表尾指针 
    scanf("%d", &x);    // 输入结点的值
    while(x!=9999){     // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r=s;            // r指向新的表尾结点 
        scanf("%d",&x);
    }
    r->next = NULL; //尾结点指针置空
    return L;
}

会发现这个链表不能存9999，只是一个表示结束的方式，其他结束方式也可以

单链表-头插法

LinkList List_HeadInsert(LinkList &L){ // 你想建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 创建头节点
    L->next = NULL; // 初始化为空链表
    scanf("%d", &x);// 输入结点的值
    while(x!=9999){ // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));// 创建新节点
        s->data = x;
        s->next = L->next;
        L->next = s; // 将新节点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

为什么要初始化？
因为没有初始化的指针可能会指向原本存在的脏数据，会出现一些问题

怎么将单链表逆置？
可以将链表从头到尾读一遍到新的链表里，通过头插法建立这个新的链表

双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

初始化

带头结点

bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode)); // 分配一个头节点
    if (L==NULL)  // 内存不足，分配失败
        return false;
    L->prior = NULL; // 头结点的 prior 永远指向NULL
    L->next = NULL;  // 头结点之后暂时还没有结点
    return true;
}

同样的，DNode * 和 DLinklist 是等价的，一个强调是结点，一个强调是链表

判断双链表是否为空（带头结点）

bool Empty(DLinklist L){
    if (L->next == NULL)
        return true;
    else
        return false;
}

双链表-插入

在指定结点p后插入结点s

bool InsertNextDNode(DNode *p, DNode *s){
    if (p==NULL|| s==NULL)
        return false;
    s->next = p->next;
    if(p->next != NULL)
        p->next->prior = s
    s->prior = p;
    p->next = s;
    return true;
}

要注意语序的顺序，不然可能会出问题

前插操作只需要找到指定结点的前驱结点，对其进行后插操作即可，然后对特殊情况进行处理，比如指定节点为第一个结点

双链表-删除

删除给定结点p的后继节点

bool DeleteNextDNode(DNode *p){
    if (p == NULL)// 判断输入是否合法
        return false;
    DNode *q = p->next;// q 是 p 的后继结点
    if (q == NULL) // 判断q是不是最后一个结点
        q->next->prior = p;
    free(q);  // 释放结点空间
    return true;
}

销毁链表：

void DestoryList(DLinklist &L){
    // 循环释放各个数据结点
    while (L->next != NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL; // 头指针指向NULL，防止指向位置数据
}

双链表-遍历

// 1. 后向遍历
while (p!=NULL){
    // 对结点p做处理
    p = p->next;
}

// 2. 前向遍历
while (p != NULL){
    // 对结点p做相应处理
    p = p->prior;
}

// 3. 前向遍历（跳过头结点）
while (p->prior != NULL){
    // 对结点 p 做相应处理
    p = p->prior;
}

双链表不可随机存取，因此安慰查找，按值查找都只能用遍历的方式实现。时间复杂度O(n)

循环链表

循环单链表

结点定义

typrdef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

初始化一个循环单链表

bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
    if (L==NULL)
        return false;
    L->next = L;
    return true;
}

判断循环单链表是否为空

bool Empty(LinkList L){
    if (L->next == L)
        return true;
    else
        return false;
}

判断结点p是否为为循环单链表的表尾结点

bool isTail(LinkList L, LNode *p){
    if (p->next == L)
        return true;
    else
        return false;
}

循环单链表可以从一个结点出发找到其他任何一个结点

循环双链表

结点定义：

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

初始化一个空的循环双链表

bool initDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));
    if (L==NULL) // 内存不足，分配失败
        return false;
    L->prior = L;
    L->next = L;
    return true;
}

判断循环双链表是否为空

bool Empty(DLinklist L){
    if (L->next == L)
        return true;
    else
        return false;
}

判断结点p是否为循环双链表的表尾结点

bool isTail(DLinklist L, DNode *p){
    if (p->next ==L)
        return true
    else
        return false;
}

双链表的插入
在结点p之后插入s结点

bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p-next = s;
}

双链表的删除
删除结点p的后继结点q

p->next=q->next;
q->next->prior= p;
free(q);

静态链表

单链表：结点零散
静态链表：分配一整片的连续空间，各个结点集中安放

静态链表-定义

#define MaxSize 10
struct Node{
    ElemType data; // 存储数据元素
    int next;      // 下一个元素的数组下标
}

void test(){
    struct Node a[MaxSize]; // 数组a作为静态链表
}

用另一种方法定义

#define MaxSize 10
typrdef struct {
    ElemType data;
    int next;
}SLinkList[MaxSize];

等价于

#define MaxSize 10
struct Node{
    Elemtype data;
    int next;
};
typedef struct Node SLinkList[MaxSize];
void test(){
    SlinkList a;
    printf("size a=%d",sizeof(a));
}

这个得到的结果为size a=80
SLinkList a 相当于定义了一个长度为MaxSize 的Node型数组

虽然是连续的一个空间，看起来和数组很像，或者是和顺序表很像，但是数据的顺序和数组下标并不相关，有单独存下一个元素偏移量的一个元素，物理上相邻，但是逻辑上可能不相邻

初始化静态链表的时候，应当把空闲节点标记出来，在删除一个节点的时候，也要把空闲的结点标注出来

静态链表适用场景：

不支持指针的低级语言
数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

顺序表和链表的比较

顺序表

顺序存储
优点：支持随机存取、存储密度高
缺点：大片连续空间分配不方便，改变容量不方便

链表

链式存储
优点：离散的小空间分配方便，改变容量方便
缺点：不可随机存取，存储密度低

基本操作

创建（初始化）
- 顺序表：需要分配大片连续空间。若分配空间过小，则之后不方便拓展容量：若分配空间过大，则浪费内存资源
  - 静态分配：静态数组（容量不可改变）
  - 动态分配：动态数组（malloc、free）容量可改变，但需要移动大量元素时，时间代价高
- 链表：只需要分配一个头结点（也可以不要头结点，之声明一个头指针），之后方便拓展
销毁
- 顺序表：修改Length=0
  - 静态分配：静态数组，系统自动回收空间
  - 动态分配：动态数组（malloc、free）
- 链表：依次删除各个结点（free）
增删改查
- 插入/删除元素
  - 顺序表：时间复杂度为O(n)，时间开销主要来自于移动元素
  - 链表：时间复杂度O(n)，时间开销主要来自查找目标元素
  - 查找比移动的开销更低

malloc 和 free 必须成对出现

表长难以估计、经常要增加/删除元素时使用链表更好
表长可预估、查询（搜索）操作较多时使用顺序表更好

实现顺序表时，用顺序表好还是链表好？

顺序表和链表的逻辑结构都是线性结构，都属于线性表
但二者的存储结构不同，顺序表采用顺序存储……(特点，带来的优点缺点)
链表采用链式存储……(特点、导致的优缺点)
由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时……; 当插入一个数据元素时……; 当删除一个数据元素时……; 当查找一个数据元素时……