3、数据结构——简单的线性表——单链表（二）

单链表是什么？

对比一下顺序表和单链表，前者的各个元素在内存中分配是顺序的，是一个接着一个的；但是单链表的各个节点是分隔开的，地址不连续，通过指针指向的形式指向下一个元素，每个结点里面都存有各种类型的数据以及指向下一个结点的内存空间的地址的指针变量，最后一个结点的指向就是NULL。

​ image-20240214163904216

定义单链表的结构体（每个结点对应的数据）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 写法1.0
struct LNode{
    ElemType data; // 数据域
    struct LNode *NEXT; //指针域，指向下一个结点，存放其对应的地址
};
struct LNode *p = (struct LNode *)malloc(sizeof LNode); // 添加一个新结点。这段代码的含义是，为p分配一段类型为struct LNode *的内存空间，记住这种写法，我们之后会用到很多次


// 写法2.0
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;

// 需要表示一个单链表的时候，只需要声明一个头指针L，指向单链表的第一个结点
LNode *L;
or
LinkList L;
//这两种写法实际作用是一致的，但是我们一般在表示这是一个单链表的时候使用LinkList;是一个结点的时候使用LNode *

image-20240214165021890

不带头结点的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio>
typedef struct LNode{
    ElemType data;
    struct LNode * NEXT;
}LNode, *LinkList;

LinkList(ListList &L) { // 注意这里的&绝对不可以拉下，&的作用前面已经讲的很清楚了
    L = NULL; // 空表，暂时没有指向单链表的指针
    return true;
}

bool Empty(LinkList L) {
    return L == NULL;
}

int main()
{
    LinkList L; // 声明了一个指向单链表的指针。注意这里没有创建一个结点，因为没有为其分配内存空间
    // 初始化一个空表
    LinkList(L);
}

带头结点的单链表（头结点不存储数据）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio>
typedef struct LNode{
    ElemType data;
    struct LNode * NEXT;
}LNode, *LinkList;

LinkList(ListList &L) { 
	L = (LNode *)malloc(sizeof LNode); // 分配一个头结点
    if (L == NULL) return false; // 内存不足，分配空间失败，基本不会出现这种情况
    L->NEXT = NULL; // 头结点之后暂时还没有结点
    return true;
}

bool Empty(LinkList L) {
    return L->NEXT == NULL;
}

int main()
{
    LinkList L; // 声明了一个指向单链表的指针。注意这里没有创建一个结点，因为没有为其分配内存空间
    // 初始化一个空表
    LinkList(L);
}

对比

​ 我们一般都会使用带头结点的单链表的这种写法，因为编写代码更加方便，简洁。

按位序插入（带头结点）

图解

第一步： 定义需要插入的节点p

image-20240214181306504

第二、三步： 结点3指向结点6，结点6指向结点4

image-20240214181429804image-20240214181449739

代码（别看这么多解释，实际上就是几行代码，只不过我做的解释比较多，废话很多）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
前面代码重复写了多次了，就省略了......
// 插入操作主要流程就是上面的三张图片
// 在第i个结点插入元素e，指的就是在第i-1个结点后面插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
    if (i < 1) return false; // i表示第i个元素，i如果小于1则不合法，直接插入失败
    LNode *p; // 定义新结点，指针p指向当前遍历到的结点
    int j = 0; // 表示当前p指向的是第j个结点
    p = L; // L指向头结点，头结点可以理解为第0个元素，里面不存储数据，只存储第1个结点的指针变量,里面存的就是第1个结点的地址
    while (p != NULL && j < i - 1) { // 由于单链表最后一个结点指向的是NULL，所以可以这样判断是否到链表尾部。后面的j<i-1则是指当遍历到第i-1个结点时候停止遍历，准备在这个结点后面插入元素。j = i - 1才会停止循环
        p = p -> next; // 这个含义就是将p的下一个结点赋给p自己，以上图为例，假设p当前指向的是结点1，那么就是将p指向的结点2赋给p，那么p指向的就变成了结点2了。
        j++; 
    }
    if (p == NULL) return false; // 这种情况就表示j还没有遍历到第i - 1个元素链表就已经到尾部了，这就表示链表不存在第i-1个元素，那么就是一个不合法的操作。比如说，1 2 3 4这个数列，我说想在第6个位置插入1个5，一共就只有4个元素，肯定是不合法的操作。
    
    // 如果程序可以运行到这里，那就代表这次插入操作是合法的，p里面存储的就是链表第i - 1个元素对应结点
    LNode *s = (LNode *)malloc(sizeof LNode); // 为需要插入的结点分配内存空间。
    s->data = e; // 设置结点的元素
    s->NEXT=p->NEXT; // 1、新结点指向第i-1个元素指向的下一个元素（也就是第i个元素），s->NEXT表示新结点的指向，p->NEXT表示第i - 1个元素的指向（也就是第i个元素），合起来就是新结点指向第i个元素。对不对(*^▽^*)！
    p->NEXT=s; // 2、最后一步就是将第i - 1个元素指向新结点。
    
    // 注意：上面的两步是不可以颠倒的
	// 如果我们最后两行换个位置写成了
    // p->NEXT=s;
    // s->NEXT=p->NEXT; 
    // 这样的话你就会发现，第一步还是没有问题的，问题就是出现在第2步，因为第一步操作之后p->NEXT就不再指向第i个元素了，而是指向s，那么我们s->NEXT=p->NEXT就相当于写成了s->NEXT=s;
    // 这样写很明显就是错了咯，后面的学习这样的事情会出现很多，大家需要在自己的大脑里面好好构思一番
    
    return true;
}

按位序插入（不带头结点）

image-20240214185412515 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
前面代码重复写了多次了，就省略了......
bool ListInsert(LinkList &L, int i, ElemType e){
    // 基本思路和上面是相同的，区别就是在插入第1个元素的时候需要特殊处理
    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;
    int j = 0;
    p = L; 
    while (p != NULL && j < i - 1) { 
        p = p -> next; 
        j++; 
    }
    if (p == NULL) return false; 
    LNode *s = (LNode *)malloc(sizeof LNode); 
    s->data = e;
    s->NEXT=p->NEXT; 
    p->NEXT=s; 
    return true;
}

指定节点后插操作（比如在第i个元素后面插入一个新结点，实际上就是前面代码的变形罢了，几乎是一模一样）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
前面代码重复写了多次了，就省略了......
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;
    int j = 0;
    p = L; 
    while (p != NULL && j < i) { // 唯一的区别，遍历到第i个元素，之前是遍历到第i - 1个元素
        p = p -> next; 
        j++; 
    }
    if (p == NULL) return false; 
    LNode *s = (LNode *)malloc(sizeof LNode); 
    s->data = e;
    s->NEXT=p->NEXT; 
    p->NEXT=s; 
    return true;
}

指定节点前插操作（在一个结点前面插入一个元素，这里可以使用一个新思路）

代码（现在假定我们已经知道了我们的目标结点）

1
2
3
4
5
6
7
8
9
10
bool InsertPriorNode(LNode *p, LNode *s) { // 看下图，我们现在的目标是在p的前面插入元素e，下面代码的基本思路就是首先将s结点插入到p指向结点后面，然后再将p和s结点位置交换一下即可
    if (p == NULL || s == NULL) return false;
    s -> NEXT = p -> NEXT;
    p -> NEXT = s;
    // 下面三步将两个结点的元素进行交换
    ElemType temp = p -> data;
    p -> data = s -> data;
    s -> data = temp;
    return true
}
image-20240214191128823

按位序删除（带头结点）

image-20240214191710694image-20240214191816268

image-20240214191908857

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 || p ->NEXT == NULL) return false;
    
    // 正式开始删除元素，前面全是判断是否可以删除。
    LNode *q = p -> NEXT; // q存放需要删除的元素
    e = q -> data; // 由于使用的类型用了&，所以可以将删除元素存下来
    p -> NEXT = q -> NEXT;
    free(p);
    return true;
}

内容真他喵得多呀！！！！

image-20240214192448548

指定结点删除（基本思路就是将删除元素的后一个元素的值赋给需要删除的元素结点，将该结点指向后面的后面的元素，请看图解）

代码

1
2
3
4
5
6
7
8
9
10
11
bool DeleteNode (LNode *p) {
    if (p == NULL) return false;
    if (p -> NEXT ==  NULL) { // 当需要删除的元素是单链表最后一个元素的时候
        free(p); // 空间释放完之后就OK了
    } 
    LNode *q = p -> NEXT;
    p -> data = p -> NEXT -> data;
    p -> NEXT = q -> NEXT;
    free(p);
    return true;
}

image-20240214192851198image-20240214193055169

按位查找（返回第i个元素，如果你前面的知识都掌握了，这里应该自己就可以实现了）

代码

1
2
3
4
5
6
7
8
9
10
11
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;
}

image-20240214193945422

​ 写到这里我们会发现我们这里的代码和前面修改第i个元素的代码是不是重复了，这时候我们就可以将前面的那一坨代码改为GetElem()的函数形式。这样的操作就叫做封装 （可以避免重复代码，简洁、易于维护）

按值查找

代码

1
2
3
4
5
6
7
LNode * LocateElem(LinkList L,ElemType e) {
    LNode *p = L -> NEXT;
    while (p != NULL && p -> data != e) {
        p = p -> NEXT;
    }
    return p;
}

求表的长度

代码

1
2
3
4
5
6
7
8
9
int length(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p -> NEXT != NULL){
        p = p -> NEXT;
        len ++;
    }
    return len;
}
image-20240214195452336

尾插法

代码
1
2
3
4
5
6
7
8
9
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 -> NEXT = p -> NEXT;
    p -> NEXT = s;
    return true;
}
下面代码可以看明白即可
image-20240214200144946

头插法

头结点的后插操作

代码
1
2
3
4
5
6
7
8
9
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof LNode);
    if (s == NULL) returne false; // 可有可无
    s -> data = e;
    s -> NEXT = p -> NEXT;
    p -> NEXT = s;
    return true;
}

​ 看懂即可，注意L->next这段代码不可以省略，因为L->NEXT并不是NULL，而是内存空间中的神秘空间（就是随意指向一个内存空间，不知道这个空间是否存有数据，可能存在着脏数据）

image-20240214200615695

下一节内容是：4、简单的线性表——双链表！！！

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..