系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 栈

---

---

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

---

一、示例问题：单程旅行

1.单程车票

我们都曾期望，一次说走就走的旅行，一场奋不顾身的爱情！不问目的地，只有我和你。于是我们买了单程票，踏上了属于我们的单程旅行。

单程票：顾名思义就是从一个地方去往另一个地方，但无法顺原路返回

2.单程旅行

单程旅行：旅行自然是要去往好几个地方，将这些地方串联起来便成了一条线

3.单链表的引入

单链表引入：由前一个地址指向后一个地址，依此类推便形成了单链表的雏形

二、单链表的概念

1.定义

链表：由 n 个节点链接成一个链表，即线性表的链式存储结构

节点：

1. 我们把存储数据元素信息的域称为数据域。
2. 存储数据元素之间的链接信息即下一个存储数据元素地址的部分称为指针域。
3. 由数据域和指针域组成的数据元素a的存储映像称为节点。

2.结构

单链表的结构类型

typedef int SLTDateType;        // 便于更改存储类型

typedef struct SListNode {
    SLTDateType date;           // 数据域：存储数据元素信息
    struct SListNode *next;     // 指针域：存储下一个节点地址信息
} SListNode;
1
2
3
4
5
6

3.存储

存储：用动态开辟的sizeof(SListNode)大小的一块空间进行存储

1.带哨兵位

带哨兵位的增删查改相对比较简单——证易证者留自证

2.不带哨兵位

不带哨兵位的增删查改考虑的情况比较多——详细图解辅助理解

三、单链表的接口函数（无哨）

1.初始化

对单链表的动态申请一块空间并进行初始设置

// 动态申请一个结点
SListNode *BuySListNode(SLTDateType x) {
    SListNode *node = (SListNode *) malloc(sizeof(SListNode));
    node->date = x;
    node->next = NULL;
    return node;
}
1
2
3
4
5
6
7

2.查找数据

查找某元素是否在单链表中，如果是返回该元素所在地址

// 单链表查找
SListNode *SListFind(SListNode *plist, SLTDateType x) {
    SListNode *cur = plist;
    while (cur != NULL) {
        if (cur->date == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

3.头部插入

单链表的头节点之前插入：

• 将新节点设为头节点，然后指向原先的头节点即可

// 单链表头插
void SListPushFront(SListNode **pplist, SLTDateType x) {
    SListNode *newNode = BuySListNode(x);
    newNode->next = *pplist;
    *pplist = newNode;
}
1
2
3
4
5
6

4.尾部插入

单链表的尾节点之后插入：

• 空：它既是头节点也是尾节点
• 非空：将原先的尾节点指向新节点，然后新节点指向 NULL 即可

// 单链表尾插
void SListPushBack(SListNode **pplist, SLTDateType x) {
    SListNode *newNode = BuySListNode(x);
    if (*pplist == NULL) {          //pplist (空)
        *pplist = newNode;
    } else {                        //pplist (非空)
        SListNode *tail = *pplist;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.头部删除

删除单链表的头节点：

• 空：不需要删，直接返回
• 非空：将原先头节点指向的下一个节点作为新的头节点

// 单链表头删
void SListPopFront(SListNode **pplist) {
    if (*pplist == NULL) {                      //1.没有节点
        return;
    } else {                                    //2.多个节点
        SListNode *next = (*pplist)->next;
        free(*pplist);
        *pplist = next;
    }
}
1
2
3
4
5
6
7
8
9
10

6.尾部删除

删除单链表的尾节点：

• 空：不需要删，直接返回
• 一个节点：删除之后，就是空指针
• 多个节点：将倒数第二个节点所指向的下一个节点置为 NULL

// 单链表尾删
void SListPopBack(SListNode **pplist) {
    if (*pplist == NULL) {                      //1.没有节点
        return;
    } else if ((*pplist)->next == NULL) {       //2.一个节点
        free(*pplist);
        *pplist = NULL;
    } else {                                    //3.多个节点
        SListNode *prev = NULL;
        SListNode *tail = *pplist;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.指定位置之后插入

在指定位置 pos 之后插入：

• 让 心插入的节点New指向pos的下一个节点，然后 pos 指向新插入的节点。
• 注意代码顺序，否则会丢失 pos 所指向的原先的节点

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode *pos, SLTDateType x) {
    assert(pos);
    SListNode *newNode = BuySListNode(x);
    newNode->next = pos->next;
    pos->next = newNode;
}
1
2
3
4
5
6
7

8.指定位置之后删除

删除指定位置 pos 之后的一个节点：

• 空：不需要删，直接返回
• 非空：注意，删除完成后不要忘记将 pos 指向 pos->next 所指向的节点

// 单链表在pos位置之后的元素删除
void SListEraseAfter(SListNode *pos) {
    assert(pos);
    if (pos->next == NULL) {
        return;
    } else {
        SListNode *next = pos->next;
        pos->next = pos->next->next;
        free(next);
        next = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

---

四、总结

单链表是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。单链表的各种接口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。