[数据结构]线性表中的单链表

链表(Linked List)

链表是由链式存储的方式实现的顺序表。（不支持随机存取）

0x01 单链表

顺序表（顺序存储）：

• 优点：可随机存取，存储密度高
• 缺点：要求大片连续空间，改变容量不方便

单链表（链式存储）：

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

0x0101单链表的实现

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

或者,

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

两者等价。

要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个节点：

LNode *L; //声明一个指向单链表第一个节点的指针

或者,

LinkList L; //声明一个指向单链表第一个节点的指针（此方法可读性更强）

强调这是一个单链表 – 使用LinkList

强调这是一个结点 – 使用LNode

单链表又分为带头结点和不带头结点两种:
如果不带头结点,写代码更麻烦,对对一个数据结点和后续数据结点的处理需要用不同的代码逻辑.
对空表和非空表的处理需要用不同的代码逻辑

总之,用带头结点的单链表写代码更方便.

下面将会分别用代码演示一下带头结点和不带头结点的区别.

如果是考研的好哥哥,带头结点和不带头结点都有可能考,审题就完了.

0x02 带头结点的单链表

(头节点不存放数据data)

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
    int data; //每一个节点存放的数据
    struct LNode* next; //存放下一个结点
}LNode, *LinkList;

/*** 
 * @description: 初始化一个单链表，带头节点(头节点不存放数据data)
 * @param {LinkList&} L
 * @return {*}
 */
bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode)); //分配一个头节点
    if (L == NULL) return false; //内存不足，分配失败
    L->next = NULL; //头节点之后的节点为NULL，无子节点
    return true;
}

/*** 
 * @description: 判断带头节点的单链表是否为空表
 * @param {LinkList} L
 * @return {*}
 */
bool isEmpty(LinkList L) {
    if (L->next == NULL)
        return true;
    else
        return false;
    // or return (L->next == NULL);
}

int main(int argc, char const *argv[])
{
    LinkList L; //声明一个指向单链表的指针
    InitList(L); //初始化一个空表
    return 0;
}

0x0201 按位序插入操作

算法思想: 遍历链表, 找到需要插入的地方直接插入即可.

/*** 
 * @description: 在第i个位置插入元素e(带头结点的单链表)
 * @param {LinkList&} L
 * @param {int} i
 * @param {int} e
 * @return {*}
 */
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1)
        return false;
    LNode* p; //指针p指向当前扫描到的结点
    int j = 0; //当前p指向的是第几个结点
    p = L; //L指向头结点,头结点是第0个结点(不存数据)
    while (p != NULL && j < i - 1) { //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if (p == NULL) //即i值不合法
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; // 将结点s到p之后
    return true; //插入成功
}

注意⚠️: 第21行开始将结点e插入新开辟的空间s中,第22行和第23行的代码不能互换,
否则p->next = s之后p->next将会指向它自己,从而导致后方的链表被丢失.

0x0202 指定结点的后插操作

算法思想: 向p结点之后插入元素e, 只需要新分配一个空间, 然后将需要插入的元素e放进这个空间, 再把这个新开辟的空间给放入我们需要插入的地方就行了, 具体实现代码如下:

/*** 
 * @description: 在p结点之后插入元素e
 * @param {LNode*} p
 * @param {int} e
 * @return {*}
 */
bool InsertNextNode(LNode* p, int e) {
    if (p == NULL)
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) //如果内存分配失败return false;
        return false;
    s->data = e; //用结点s保存数据元素e
    s->next = p->next;
    p->next = s; //将结点s连到p之后
    return true;
}

0x0203 指定结点的前插操作

注意⚠️: 单链表在不知道链表头指针的情况下是无法知道某一个结点之前的链表区域的.

算法思想: 在给定的结点之前插入一个新的元素, 首先循环查找所给的都结点p的前驱结点q, 然后再对q进行后插操作.

/*** 
 * @description: 在链表L中的指定结点p前插入元素e
 * @param {LinkList&} L
 * @param {LNode*} p
 * @param {int} e
 * @return {*}
 */
bool InsertPriorNode(LinkList& L, LNode* p, int e) {
    LNode* q; //指针q用于指向当前扫描到的结点
    int j = 0; //当前q指针指向的是第几个结点
    q = L; //指向头结点,从第0个结点开始扫描
    while (p != NULL) { //遍历L找到p的前驱结点
        q = q->next; //前往下一个结点
        j++;
        if (q->next == p)//找到p的前驱结点q
            return InsertNextNode(q, e);
    }
    return false;//未找到结点p

}

通过上面的代码可以看出这个算法的时间复杂度为 $O(n)$.
而且必须知道链表的头指针L, 那有没有什么办法可以直接在所给结点p前面直接插入呢?答案是有的:

算法思想: 首先申请一片空间s, 先把新结点s连接🔗到所给结点p之后, 然后把p中的元素复制到新结点s中, 最后将结点p中的元素(data)覆盖为所要插入的元素e.

实现代码如下:

/*** 
 * @description: 在链表L中的指定结点p前插入元素e
 * @param {LNode*} p
 * @param {int} e
 * @return {*}
 */
bool InsertPriorNode(LNode* p, int e) {
    if (p == NULL)//指定结点为空
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) //分配空间失败
        return false;
    s->next = p->next; //将s和p原来的后继结点连接
    p->next = s; //将s连接到p之后
    s->data = p->data; //将p结点数据复制到结点s中
    p->data = e; //将元素e覆盖到原来的结点p中
    return true; //插入成功
}

通过上面的代码可以看出这个算法的时间复杂度为 $O(1)$, 优于第一种方法.

0x0203 按位序删除操作

算法思想: 遍历链表, 寻找位序i的上一个位序为i-1的结点p, 结点p下一个结点q就是我们需要删除的结点, 然后先用e存放该结点q的元素用于返回删除的元素, 然后使用p->next = q->next 直接删除该结点.

/*** 
 * @description: 删除第i个结点上的元素e
 * @param {LinkList&} L
 * @param {int} i
 * @param {int&} e
 * @return {*}
 */
bool ListDelete(LinkList& L, int i, int& e) {
    if (i < 1)
        return false;
    LNode* p; //指针p指向当前扫描到的结点
    int j = 0; //当前p指向的是第几个结点
    p = L; //L指向头结点,头结点是第0个结点(不存数据)
    while (p != NULL && j < i - 1) { //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if (p == NULL) //如果i值不合法
        return false;
    if (p->next == NULL) //如果第i-1个结点之后已无其他结点
        return false;
    LNode* q = p->next; //令q指向被删除的结点
    e = q->data; //用e返回被删除的元素的值
    p->next = q->next; //将*q结点从链中“断开”
    free(q); //释放结点的存储空间
    return true; //删除成功
}

0x0204 指定结点的删除操作

算法思想: 删除结点p, 只要把结点p的后继结点完完整整的复制过来,再把结点p的后继结点从链表中断开,并且释放这个p后继结点的空间.

注意⚠️:
必须要判断删除的结点p是否位于链表末尾,否则有p->next = NULL, 这时候如果再有p->next->next会报指向空指针的报错.

/*** 
 * @description: 删除指定结点p
 * @param {LNode*} p
 * @return {*}
 */
bool DeleteNode(LNode* p) {
    if (p == NULL)
        return false;
    if (p->next == NULL) { //假如p为末尾结点,也就是p->next == NULL
        p = NULL;
        free(p);//释放一个指针free(p)和p=NULL是两者缺一不可
    }
    else {
        LNode* q = p->next; //令q指向*p的后继结点
        p->data = p->next->data; //和后继结点交换数据域
        p->next = q->next; //将*q结点从链表中"断开"
        free(q); //释放后继结点的储存空间
    }
    return true;
}

0x0205 按位查找操作

算法思想: 遍历链表, 查找位序为i的结点, 并返回.

/*** 
 * @description: 返回第i个元素(带头结点)
 * @param {LinkList} L
 * @param {int} i
 * @return {*}
 */
LNode* GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    LNode* p; //指针p指向单钱扫描到的结点
    int j = 0; //当前p指向的是第几个结点
    p = L; //L指向头结点,头结点是第0个结点(不存数据)
    while (p != NULL && j < i) {// 循环找到第i个结点
        p = p->next;
        j++;
    }
    return p; //返回找到的结点
}

0x0206 按值查找操作

算法思想: 遍历链表, 一一对比每个结点的数据域与所需查找的值e是否相等,找到则返回该结点的指针,否则返回NULL.

/*** 
 * @description: 找到数据域为e的结点
 * @param {LinkList} L
 * @param {int} e
 * @return {*}
 */
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L->next;
    //从第1个结点开始查找数据域为e的结点(带头结点的单链表头结点无data域)
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p; //找到后返回该结点的指针,否则返回NULL表示该链表无值为e的结点
}

0x0207 求表的长度

算法思想: 从头到尾依次遍历, 然后用一个变量进行计数操作即可.

/*** 
 * @description: 求链表的长度
 * @param {LinkList} L
 * @return {*}
 */
int Length(LinkList L) {
    int len = 0; //统计表长
    LNode* p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

如果是不带头结点的单链表, 则需要在带头结点的表长的基础上加1, 因为带头结点的单链表头结点不带数据域不计入表长中.

0x03 不带头结点的单链表

不带头结点的单链表实现:

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
    int data; //每一个节点存放的数据
    struct LNode* next; //存放下一个结点
}LNode, *LinkList;

/*** 
 * @description: 初始化一个空链表，无头节点
 * @param {LinkList&} L
 * @return {*}
 */
bool InitList(LinkList& L) {
    L = NULL; //空表，暂时没有任何节点
    return true;
}

/*** 
 * @description: 判断不带头节点的单链表是否为空表
 * @param {LinkList} L
 * @return {*}
 */
bool isEmpty(LinkList L) {
    if (L == NULL)
        return true;
    else
        return false;
    //or return (L == NULL);
}

int main(int argc, char const *argv[])
{
    LinkList L; //声明一个指向单链表的指针
    InitList(L); //初始化一个空表
    return 0;
}

不带头结点的单链表,

• 第一个结点从位序i=1算起
• 而带头结点的位序从i=0这个头指针算起, 且头指针不带数据域.

只需要注意这两点即可, 下面的操作只做按位插入的演示(躺平开摆.jpg🤤), 其他的可参考带头结点的代码, 大致相同.

如果不涉及遍历操作, 两者的代码实现基本一致.

0x0301 按位序插入

不存在“第0个”结点,因此i=1时需要特殊处理.
在代码实现的时候第i个位置其实是找到第i-1个结点后将新的结点插入其后.

/*** 
 * @description: 在表L中的第i个位置上插入制定元素e
 * @param {LinkList&} L
 * @param {int} i
 * @param {int} e
 * @return {*}
 */
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1) 
        return false;
    if (i == 1) { //插入第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) { //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if (p == NULL) //i值不合法
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true; //插入成功return true;
}

0x04 单链表的建立

单链表的建立分为:

• 尾插法
• 头插法

如果给你很多个数据元素(ElemType), 需要把它们存到一个单链表里, 该怎么做呢?

Step 1: 初始化一个单链表

Step 2: 每次取一个数据元素, 插入到 表尾 或者 表头 .(对应尾插法和头插法)

0x0401 尾插法

算法思想:

初始化单链表;
设置变量length记录链表长度;
While 循环{
每次取一个数据元素e;
ListInsert(L, Length+1, e); //插到链表尾部
length++;
}

/*** 
 * @description: 尾插法建立单链表(带头结点)
 * @param {LinkList&} L
 * @return {*}
 */
LinkList List_TailInsert(LinkList& L) {
    int x; //输入的ElemType为int型
    L = (LNode*)malloc(sizeof(LNode)); //建立头结点
    LNode* s, * r = L; //设置r为表尾指针
    scanf("%d", &x); //输入一个值作为结点的数据域
    while (x != 999) { //此处999表示输入999则结束输入
        s = (LNode*)malloc(sizeof(LNode)); //开辟一个新的空间存放输入的数据x
        s->data = x; //存入x
        r->next = s; //在当前表尾插入新输入的数据(连接操作)
        r = s; //继续让r指针指向表尾
        scanf("%d", &x); //继续输入一个值作为数据域
    }
    r->next = NULL; //表尾的->next应为NULL
    return L; //返回创建好的单链表
}

0x0402 头插法

**算法思想: **

初始化单链表;
while 循环{
每次取一个数据元素e;
InsertNextNode(L, e); //使用结点后插法插入数据元素
}

/*** 
 * @description: 头插法建立单链表(带头结点)
 * @param {LinkList&} L
 * @return {*}
 */
LinkList List_HeadInsert(LinkList& L) {
    LNode* s;
    int e;
    L = (LNode*)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL; //初始化为空链表(必要,避免脏数据)
    scanf("%d", &e); //输入结点的值
    while (e != 999) { //此处999表示输入999则结束输入
        s = (LNode*)malloc(sizeof(LNode)); //开辟一个空间存放新的结点
        s->data = e;
        s->next = L->next;
        L->next = s; //将新的结点插入表中,L为头指针
        scanf("%d", &e);
    }
    return L;
}

关于头插法的应用还有很重要的一项: 链表的逆置! 其主要思想还是在于头插法.🥳