前言
- 这个专栏将会用纯C实现常用的数据结构和简单的算法;
- 用C基础即可跟着学习,代码均可运行;
- 准备考研的也可跟着写,个人感觉,如果时间充裕,手写一遍比看书、刷题管用很多,这也是本人采用纯C语言实现的原因之一;
- 欢迎收藏 + 关注,本人将会持续更新。
文章目录
- :man_teacher:单链表讲解
- :information_desk_person:单链表程序设计
- 有头单链表
- 无头单链表
- 再封装写法
- 二级指针写法
- :man_factory_worker:单链表的一些操作
- 有序链表的构建
- 排序链表
- 链表反转
👨🏫单链表讲解
上一节我们学习了顺序表,顺序表是运用最多的和最简单的顺序存储结构,但是顺序表的删除很麻烦,顺序表的删除是一种伪删除,他删除元素是通过后面元素覆盖而来,假设要删除的元素在第一位,那么他的时间复杂度是O(n),而且他并没有释放那个内存,故如果我们的运用场景是需要有经常删除的需求,那这个顺序表就并不适合🙉🙉🙉,插入操作也同样的道理。
为了避免插入和删除的线性开销,研究数据结构的数学家就设计出了链式存储结构来存储数据,它允许表 可以不连续存储,在插入和删除的时候不需要整体移动,链式存储的存储结构如下图所示:
链表由一系列不必存在内存中连续的空间的结构组成;每一个结构都有包含元素的数据域
和指向下一个节点的指针域
,指针域存储指向下一个节点的指针,最后一个元素的指针指向为NULL
。
在这里我们首先回忆以下指针变量,指针他本身是一个变量,他储存的是一个变量的地址,故联系到我们这一部分的链表,假设我们有一个指向节点P
的变量,那么就可以通过P->next指针
来寻找下一个节点的位置,如下图所示:
链表之所以可以解决顺序表的删除和插入效率的问题,因为他每一个节点都储存了指向下一个元素的指针,所以,它可以通过修改指针的指向实现删除的命令,大概流程如下:
同样的道理,插入元素也是这样,当我们使用内存申请函数开辟了一篇内存后,通过修改指针的指向即可实现插入,大概流程如图:
💁单链表程序设计
📂 链表的操作,总的来说还在那句话:增删改查。
🕵 程序设计细节:
- 插入元素中,空表插入、头插、位置插入不同;
- 删除头的时候,由于修改了起始端,故要注意表头丢失的问题;
- 一般删除的时候,需要记录要删除位置的前一个位置节点的表元。
🔬 解决方法:
- 实际操作的时候分类讨论;
- 采用添加头节点的方法来解决,添加的节点称为表头或者哑节点,这种链表称为有头链表。
有头单链表
有头链表结构图如下:
通过引入头节点,其实主要解决了插入的时候指针的指向问题与插入过程会简单一点。
想要理解这个,最直观的方法就是通过学习有头链表和无头链表的代码实现过程.
⏺ 节点封装
typedef int DataType;
typedef struct Node {DataType data; // 数据域,储存数据struct Node* next; // 指针域,储存指向下一个节点的指针
}Node;
🍨 创建节点
采用内存申请的函数,申请一块内存来储存节点。
🤔 思考:如果使用malloc
去申请内存,那有什么区别呢????????????
// 创建节点
Node* create_node(DataType data)
{Node* node = calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}
⚜️ 创建链表
🤕 这一步就是创建了一块表头,也可以说叫做虚拟头节点、哑节点,里面储存的是什么数据,我们不需要担心。
Node* create_list()
{Node* list = calloc(1, sizeof(Node));assert(list);return list;
}
🤕 插入元素–头插
头插过程:
cc
📘 情况:
- 没有头;
- 有头,则在头前面插入。
void push_front(Node* head, DataType data)
{if (NULL == head) return;// 头为空if (head->next == NULL) {Node* new_node = create_node(data);head->next = new_node;}else { // 头不为空Node* cur = head->next; // 取头Node* new_node = create_node(data);new_node->next = cur;head->next = new_node;}
}
🌮 插入–尾插
void push_back(Node* head, DataType data)
{assert(head);// 空if (head->next == NULL) {Node* new_node = create_node(data);head->next = new_node;}else { // 不为空Node* cur = head->next; // 获取头// 找到尾while (cur->next) {cur = cur->next;}cur->next = create_node(data);}}
🗡指定位置插入
说明,以下说明完全是自己个人定义,学习思想为主,具体需要结合业务:
- 1、pos从1开始
- 2、在pos后面位置插入
- 3、如何位置超出了链表长度,则当作尾插
void insert(Node* head, int pos, DataType data)
{assert(head);Node* cur = head->next;while (cur->next != NULL && pos > 1) { // pos > 1,不是 pos > 0cur = cur->next;pos--;}Node* node = create_node(data);node->next = cur->next;cur->next = node;
}
🍯 删除–删除头
// 删除
void pop_front(Node* list)
{assert(list);Node* cur = list->next;list->next = cur->next;free(cur);cur = NULL;
}
🔚 删除尾巴
思路:
- 找到最后一个最后一个元素,并且找得到最后一个元素的前一个元素
注意:
- 要判断 只有一个节点和空链表的情况
void pop_back(Node* list)
{assert(list);Node* cur = list->next;Node* pre = NULL;if (cur == NULL) {printf("链表为空\n");return;}if (cur->next == NULL) { // 只有一个节点,头删pop_front(list);return;}// 其他情况while (cur->next != NULL) {pre = cur;cur = cur->next;}pre->next = NULL;free(cur);cur = NULL;
}
🌾 指定位置删除
删除的思路大概都一样,需要找到删除元素的前一个指针,只不过需要根据场景不同来写细节。
/*说明,以下说明完全是自己个人定义,学习思想为主,具体需要结合业务:
* 1、pos从1开始,1代表删除第一个节点(头)
* 2、如果超出了链表的长度,则删除失败
*/
void erase(Node* list, int pos)
{assert(list);// 头删除if (1 == pos) {pop_front(list);return;}int num = 0;Node* cur = list->next;Node* pre = list;while (cur->next && pos-- > 1) {pre = cur;cur = cur->next;}if (cur->next == NULL && pos > 1) {printf("超出链表范围\n"); }else {pre->next = cur->next;free(cur);cur = NULL;}
}
📖 总代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;// 创建链表
Node* create_list()
{Node* list = calloc(1, sizeof(Node));assert(list);return list;
}// 创建节点
Node* create_node(DataType data)
{Node* node = calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}// 插入
void push_front(Node* head, DataType data)
{if (NULL == head) return;// 头为空if (head->next == NULL) {Node* new_node = create_node(data);head->next = new_node;}else { // 头不为空Node* cur = head->next; // 取头Node* new_node = create_node(data);new_node->next = cur;head->next = new_node;}
}void push_back(Node* head, DataType data)
{assert(head);// 空if (head->next == NULL) {Node* new_node = create_node(data);head->next = new_node;}else { // 不为空Node* cur = head->next; // 获取头// 找到尾while (cur->next) {cur = cur->next;}cur->next = create_node(data);}}/*说明,以下说明完全是自己个人定义,学习思想为主,具体需要结合业务:
* 1、pos从1开始
* 2、在pos后面位置插入
* 3、如何位置超出了链表长度,则当作尾插
*/
void insert(Node* head, int pos, DataType data)
{assert(head);Node* cur = head->next;while (cur->next != NULL && pos > 1) { // pos > 1,不是 pos > 0cur = cur->next;pos--;}Node* node = create_node(data);node->next = cur->next;cur->next = node;
}// 删除
void pop_front(Node* list)
{assert(list);Node* cur = list->next;list->next = cur->next;free(cur);cur = NULL;
}void pop_back(Node* list)
{assert(list);Node* cur = list->next;Node* pre = NULL;if (cur == NULL) {printf("链表为空\n");return;}if (cur->next == NULL) { // 只有一个节点,头删pop_front(list);return;}// 其他情况while (cur->next != NULL) {pre = cur;cur = cur->next;}pre->next = NULL;free(cur);cur = NULL;
}/*说明,以下说明完全是自己个人定义,学习思想为主,具体需要结合业务:
* 1、pos从1开始,1代表删除第一个节点(头)
* 2、如果超出了链表的长度,则删除失败
*/
void erase(Node* list, int pos)
{assert(list);// 头删除if (1 == pos) {pop_front(list);return;}int num = 0;Node* cur = list->next;Node* pre = list;while (cur->next && pos-- > 1) {pre = cur;cur = cur->next;}if (cur->next == NULL && pos > 1) {printf("超出链表范围\n"); }else {pre->next = cur->next;free(cur);cur = NULL;}
}// 遍历
void travel(Node* head)
{assert(head);Node* cur = head->next;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}int main()
{Node* list = create_list();push_front(list, 1);push_front(list, 2);push_front(list, 3);travel(list);push_back(list, 5);push_back(list, 6);push_back(list, 7);travel(list);insert(list, 2, 22);insert(list, 5, 55);insert(list, 20, 20);travel(list);pop_front(list);travel(list);pop_back(list);travel(list);erase(list, 5);travel(list);return 0;
}
无头单链表
在有头链表中,我们是构造了一个虚拟节点作为头,这样可以简化很多操作,那如果不用创建新头节点又该怎么写呢?这里提供两种方法,再封装写法和二级指针写法
再封装写法
🌩 : 节点封装与链表再次封装
typedef struct Node {DataType data;struct Node* next;
}Node;
// 链表再次封装
typedef struct List {Node* headNode;int count;
}List;
🍨 创建节点
Node* create_node(DataType data)
{Node* new_node = (Node*)calloc(1, sizeof(Node));if (new_node == NULL) {return NULL;}new_node->data = data;return new_node;
}
⚜️ 创建链表
List* create_list()
{List* list = (List*)calloc(1, sizeof(List));assert(list);return list;
}
🤕 插入元素–头插
void push_front(List* list, DataType data)
{if (list == NULL) {return;}if (list->count == 0) {Node* node = create_node(data);assert(node);list->headNode = node;}else {Node* node = create_node(data);assert(node);node->next = list->headNode;list->headNode = node;}list->count++;
}
🌮 插入–尾插
void push_back(List* list, DataType data)
{if (list == NULL) {return;}if (list->count == 0) {push_front(list, data); // 相当于头插}else {Node* cur = list->headNode;while (cur->next) {cur = cur->next;}Node* node = create_node(data);assert(node);cur->next = node;}list->count++;
}
🗡指定位置插入
// 这里定义,在找到数据后位置插入
void insert(List* list, DataType posData, DataType insertData)
{if (list == NULL || list->count == 0)return;Node* cur = list->headNode;while (cur->next && cur->data != posData) {cur = cur->next;}// cur->next == null, cur->data == posdataif (cur->data != posData) {return;}else {Node* node = create_node(insertData);assert(node);node->next = cur->next;cur->next = node;}list->count++;
}
🍯 删除–删除头
void pop_front(List* list)
{if (list == NULL || list->count == 0)return;if (list->count == 1) {Node* t = list->headNode;list->headNode = NULL;free(t);t = NULL;}else {Node* t = list->headNode;list->headNode = t->next;free(t);t = NULL;}list->count--;
}
🔚 删除尾巴
void pop_back(List* list)
{if (list == NULL || list->count == 0)return;if (list->headNode->next == NULL) {free(list->headNode);list->headNode = NULL;}else {// 双指针Node* pre = list->headNode;Node* tail = list->headNode->next;while (tail->next != NULL) {pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}list->count--;
}
🌾 指定位置删除
void earse(List* list, DataType data)
{if (list == NULL || list->count == 0)return;Node* pre = NULL;Node* pos = list->headNode;// 没有到终点,且没有找到datawhile (pos != NULL && pos->data != data) {pre = pos;pos = pre->next;}if (pos == NULL) {return;}else if(pre == NULL){pop_front(list);}else {pre->next = pos->next;free(pos);pos = NULL;}list->count--;
}
⭕️ 总代码
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;typedef struct List {Node* headNode;int count;
}List;Node* create_node(DataType data)
{Node* new_node = (Node*)calloc(1, sizeof(Node));if (new_node == NULL) {return NULL;}new_node->data = data;return new_node;
}List* create_list()
{List* list = (List*)calloc(1, sizeof(List));assert(list);return list;
}void push_front(List* list, DataType data)
{if (list == NULL) {return;}if (list->count == 0) {Node* node = create_node(data);assert(node);list->headNode = node;}else {Node* node = create_node(data);assert(node);node->next = list->headNode;list->headNode = node;}list->count++;
}void push_back(List* list, DataType data)
{if (list == NULL) {return;}if (list->count == 0) {push_front(list, data); // 相当于头插}else {Node* cur = list->headNode;while (cur->next) {cur = cur->next;}Node* node = create_node(data);assert(node);cur->next = node;}list->count++;
}// 这里定义,在找到数据后位置插入
void insert(List* list, DataType posData, DataType insertData)
{if (list == NULL || list->count == 0)return;Node* cur = list->headNode;while (cur->next && cur->data != posData) {cur = cur->next;}// cur->next == null, cur->data == posdataif (cur->data != posData) {return;}else {Node* node = create_node(insertData);assert(node);node->next = cur->next;cur->next = node;}list->count++;
}void pop_front(List* list)
{if (list == NULL || list->count == 0)return;if (list->count == 1) {Node* t = list->headNode;list->headNode = NULL;free(t);t = NULL;}else {Node* t = list->headNode;list->headNode = t->next;free(t);t = NULL;}list->count--;
}void pop_back(List* list)
{if (list == NULL || list->count == 0)return;if (list->headNode->next == NULL) {free(list->headNode);list->headNode = NULL;}else {// 双指针Node* pre = list->headNode;Node* tail = list->headNode->next;while (tail->next != NULL) {pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}list->count--;
}void earse(List* list, DataType data)
{if (list == NULL || list->count == 0)return;Node* pre = NULL;Node* pos = list->headNode;// 没有到终点,且没有找到datawhile (pos != NULL && pos->data != data) {pre = pos;pos = pre->next;}if (pos == NULL) {return;}else if(pre == NULL){pop_front(list);}else {pre->next = pos->next;free(pos);pos = NULL;}list->count--;
}void travel(List* list)
{if (list == NULL) {return;}Node* cur = list->headNode;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}int main()
{List* list = create_list();push_front(list, 1);push_front(list, 2);push_front(list, 3);push_back(list, 4);push_back(list, 5);push_back(list, 6);travel(list);insert(list, 2, 22);insert(list, 6, 66);travel(list);pop_front(list);travel(list);pop_back(list);travel(list);earse(list, 22);earse(list, 6);travel(list);return 0;
}
二级指针写法
二级指针的写法主要在于创建节点的时候,
📦 节点封装:
typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;
🍨 创建节点:
Node* create_node(DataType data)
{Node* node = calloc(1, sizeof(Node));if (node == NULL) {return node;}node->data = data;return node;
}
🤕 插入–头插入:
void push_front(Node** list, DataType data)
{if (list == NULL) {return;}Node* new_node = create_node(data);if (*list == NULL) {*list = new_node;}else {new_node->next = *list;*list = new_node;}
}
🚖 插入–尾插入:
void push_back(Node** list, DataType data)
{if (list == NULL) {return;}// 无头if (*list == NULL) {*list = create_node(data);}else {Node* pos = (*list);Node* cur = (*list)->next;while (cur) {pos = cur;cur = cur->next;}pos->next = create_node(data);}}
⚡️ 插入–指定数据后插入:
// 在posData数据后插入
void insert(Node** list, DataType posData, DataType data)
{// *list == null,说明链表为空if (list == NULL || *list == NULL) {return;}Node* pos = *list;while (pos != NULL && pos->data != posData) {pos = pos->next;}// 不存在该节点if (pos == NULL) {return;}else {Node* t = create_node(data);t->next = pos->next;pos->next = t;}}
📚 总代码:
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;Node* create_node(DataType data)
{Node* node = calloc(1, sizeof(Node));if (node == NULL) {return node;}node->data = data;return node;
}void push_front(Node** list, DataType data)
{if (list == NULL) {return;}Node* new_node = create_node(data);if (*list == NULL) {*list = new_node;}else {new_node->next = *list;*list = new_node;}
}void push_back(Node** list, DataType data)
{if (list == NULL) {return;}// 无头if (*list == NULL) {*list = create_node(data);}else {Node* pos = (*list);Node* cur = (*list)->next;while (cur) {pos = cur;cur = cur->next;}pos->next = create_node(data);}}
// 在posData数据后插入
void insert(Node** list, DataType posData, DataType data)
{// *list == null,说明链表为空if (list == NULL || *list == NULL) {return;}Node* pos = *list;while (pos != NULL && pos->data != posData) {pos = pos->next;}// 不存在该节点if (pos == NULL) {return;}else {Node* t = create_node(data);t->next = pos->next;pos->next = t;}}void travel(Node* list)
{if (list == NULL) {return;}Node* cur = list;while (cur) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}int main()
{Node* list = NULL;push_front(&list, 1);push_front(&list, 2);push_front(&list, 3);travel(list);push_back(&list, 4);push_back(&list, 5);push_back(&list, 6);travel(list);insert(&list, 4, 44);insert(&list, 1, 11);travel(list);return 0;
}
👨🏭单链表的一些操作
🏀 准备工作:本次案例均采用有头链表进行操作,创建有头链表,与尾插法、遍历链表代码如下:
typedef struct Node {int data;struct Node* next;
}Node;Node* create_list()
{Node* list = (Node*)calloc(1, sizeof(Node));assert(list);return list;
}Node* create_node(int data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}// 插入
void push_back(Node* list, int data)
{assert(list);Node* headNode = list->next;if (headNode == NULL) {headNode = create_node(data);list->next = headNode;}else {Node* prev = NULL;Node* cur = headNode;while (cur != NULL) {prev = cur;cur = cur->next;}prev->next = create_node(data);}
}// 遍历
void travel(Node* list)
{assert(list);Node* curNode = list->next;while (curNode) {printf("%d ", curNode->data);curNode = curNode->next;}printf("\n");
}
注意、注意: 下面案例如果设计有序,默认是升序。
有序链表的构建
🔊 其实这个,就是插入排序的思想,在插入的时候,找到数据小于链表中某一个节点数据的第一个节点,有点绕,看代码会容易很多,然后就是正常的链表的插入了。
// 有序链表的构建
void push_sort(Node* list, int data)
{assert(list);Node* headNode = list->next;if (headNode == NULL) {headNode = create_node(data);list->next = headNode;}else {Node* prev = NULL;Node* curNode = headNode;while (curNode != NULL && curNode->data < data) { // 找prev = curNode;curNode = curNode->next;}Node* node = create_node(data);// 头插if (prev == NULL) {node->next = list->next;list->next = node;}else { // 找到第一个大于data、或者data是最大的情况node->next = prev->next;prev->next = node;}}
}
排序链表
🚅 这里仅采用最简单的算法,冒泡:
void bubble_sort(Node* list)
{assert(list);for (Node* i = list->next; i != NULL; i = i->next) {for (Node* j = list->next; j != NULL; j = j->next) {if (j->next != NULL && j->data > j->next->data) {int temp = j->data;j->data = j->next->data;j->next->data = temp;}}}
}
链表反转
🔙 其中,创建3个辅助指针,next 找节点,反转:prev与curNode指针不断转换的过程
void reversed(Node* list)
{// 至少需要两个节点if (list == NULL || list->next == NULL || list->next->next == NULL) {return;}Node* prev = NULL;Node* curNode = list->next;Node* nextNode = curNode->next;while (nextNode != NULL) {curNode->next = prev;prev = curNode;curNode = nextNode;nextNode = nextNode->next;}curNode->next = prev;list->next = curNode;
}