线性表的链式存储结构 / 链表

1.1 定义：

线性表的链式存储结构不限制数据元素的物理存储状态，也就是说，其数据元素的物理位置是随机的。

对于每一个元素来说，它需要存储自身信息在数据域中，还需要存储直接后继的位置信息在指针域中，这两部分信息共同构成一个结点（Node）。n 个结点就链结成一个链表，如果每一个结点只有一个指针域，那么它就是单链表。

头指针：头指针保存第一个结点（首元结点）的存储位置，因为最后一个结点没有后继结点，所以它的指针域为空(NULL / ^)。

头结点：有时候，首元结点前还会设置一个头结点，有头结点的时候，头指针保存的是头结点的存储位置。对于头结点，其数据域不一定要包含信息，其指针域则保存的是首元结点的存储位置。如下图所示：

Tip: 设计头结点是为了操作的统一。

链表并不是随机存取结构，并不能根据一个给定元素就能马上找到另一个目标元素，而是只能从头指针开始顺链查找，这称为顺序存取结构。

1.2 单链表：

在开始之前，我们还是先定义单链表中每个结点的结构：

typedef struct Link{
    char elem; // 数据域
    struct Link *next; // 指针域
}link; // link为结点名，每个结点都是一个 link 结构体

Tip：因为指针也是指向一个结点，这里尤其要注意将指针类型声明为 struct Link

(1) 初始化空表：

link *initLink(){
    link *p = (link*)malloc(sizeof(link));// 创建一个头结点
    link *temp = p;// 声明头指针并指向头结点
    temp->next = NULL; // 头结点的指针域置空
    return p;
}

(2) 整表创建：

例如，创建一个存储 {1,2,3,4} 且无头结点的链表：

link *initLink(){    // 这里函数返回一个 link 类型的指针，所以函数名加 *
    link *temp = (link*)malloc(sizeof(link));// 创建首元结点
    link *p = temp;// 创建头指针并指向首元结点
    
    // 首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    
    // 从第二个节点开始创建
    for (int i=2; i<5; i++) {
     // 创建一个新节点并初始化
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        // 将temp节点与新建立的a节点建立逻辑关系
        temp->next=a;
        // 指针temp每次都指向新链表的最后一个节点
        temp=temp->next;
    }
    //返回建立的节点，只返回头指针 p 即可，通过头指针即可找到整个链表
    return p;
}

(3) 查找元素：

p 为原链表，elem 表示被查找的元素
link *selectElem(link *p,int elem){
    // 新建一个指针，直接指向首元结点
    link *t = p->next;
    while(t && t->elem != elem){
        t=t->next;
    }
    return t;
}

因为存在头结点，所以这里首先获取首元结点，然后从首元结点开始依次往后面遍历，查找是否有符合的元素。如果查找成功，返回的 t 是元素的地址，查找失败则返回 NULL。

(4) 修改元素：

// change 表示目标结点在链表中的位置，newElem 为新的数据域的值
link *changeElem(link *p,int change,int newElem){
    link *temp = p->next;
    // 遍历到要修改的结点
    for (int i = 1;i<change;i++) {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}

(5) 删除元素：
包括两步，一个是摘除结点并改变连接，一个是释放被摘除结点的内存。关键代码是：

temp->next = temp->next->next;

如下图所示：

具体实现代码是：

//p为原链表，add 为要删除元素的位序
link *delElem(link *p,int add){
    // temp 首先指向首元结点
    link *temp = p;
    // 先寻找被删除结点的上一个结点
    for (int i = 1; i<add-1; i++) {
        temp = temp->next;
    }
    link *del = temp->next;// 单独设置一个指针指向被删除结点，后面方便释放其内存
    temp->next = temp->next->next;
    free(del);// 手动释放该结点，防止内存泄漏
    return p;
}

注意这是没有头结点的情况，如果有头结点，循环判断应该是 i<add，因为初始的 temp 指向的是头结点。

(6) 插入元素：
包括两步，一个是将插入位置后的结点作为新结点的 next，一个是将新结点作为插入位置前的结点的 next，也就是关键代码：

new->next = temp->next;
temp->next = new;

如下图所示：

注意：这里顺序不能颠倒，如果是先确定插入位置前结点和新结点的连接，那么插入位置后结点将无法获取，因为其获取是依赖于插入位置前结点的next的，而这个next已经被覆盖。

具体代码为：

// p为原链表，elem表示新数据元素，add表示新元素插入的位置
link *insertElem(link *p,int elem,int add){
    link *temp = p;// 创建指向首元结点的指针
    // 遍历寻找插入位置前的结点
    for(int i = 1;i<add;i++){
        if(temp == NULL){
            printf("插入位置无效\n");
            return p;
        }
        temp = temp->next;
    }
    // 创建新结点并初始化
    link *c = (link*)malloc(sizeof(link));
    c->elem = elem;
    // 改变连接关系
    c->next = temp->next;
    temp->next = c;
    return p;
}

if 语句用来判断 add 是否合法，因为如果 add 过大，那么一直遍历下去会得到一个 next 为 NULL 的temp，之后报错。

1.3 循环链表：

当单链表中最后一个结点的指针域不为空，而是指向头结点的时候，就形成一个环，这叫循环链表。循环链表进行元素遍历的时候，循环终止条件不再是 p->next = NULL，而是 p->next = L。

如果使用尾指针，那么可以用 O(1) 的时间找到尾结点和首元结点，而且可以简化合并两个循环链表的过程：

对于上面这两个循环链表，合并的思路大概是：A表尾连B表头。所以这里要改变 rearA->next，事先要先保存一开始的 rearA->next，即A表的头结点，之后将B表的首元结点给 rearA->next；之后我们要将一开始保留的A表头结点作为 rearB->next，事先要先保存一开始的 rearA->next，即B表的头结点，方便最后释放内存。

用图片表示的思路是：

用代码表示的思路是：

p = rearA->next;
rearA->next = rearB->next->next;
reerB->next = p;
free(p);

1.4 双向链表

单链表的每一个结点中，额外多出一个指向前驱结点的指针域，这时候就成了双向链表。双向链表的尾结点指针域指向头结点时，就成了双向循环链表，如下图：

插入操作

插入操作一定要注意顺序，我们可以先处理新结点的前驱和后继，之后再依次处理后结点、前结点。

// 新结点的前驱后继
s->prior = p;
s->next = p->next;
// 后结点
p->next->prior = s;
// 前结点
p->next = s;

删除操作

删除很简单，如下图把中间的 p 删除，那么对于后结点，我们要修复它的前驱指针；对于前结点，我们要修复它的后继指针，最后一步是释放被删除结点的内存

p->prior->next = p->next;
p->next-prior = p->prior;