目录
前言
动态顺序表的缺陷
单链表的概念
单链表中节点的结构
单链表逻辑结构示意图编辑
实现单链表前的准备工作
实现单链表
1. 定义节点的指针
2. 创建节点
3. 打印单链表中的所有数据
4. 在单链表头部插入数据
5. 在单链表尾部插入数据
6. 在单链表头部删除数据
7. 在单链表尾部删除数据
8. 在单链表中查找指定的节点
9. 在单链表中 pos 节点插入数据
1. 在 pos 节点之前插入
2. 在 pos 节点之后插入
10. 在单链表中 pos 节点删除数据
1. 删除 pos 节点
2. 删除 pos 节点后一个节点
11. 释放单链表的所有节点
SList.h 的所有代码
SList.c 的所有代码
前言
在前几章,讲解了动态顺序表的实现和相关oj题
数据结构 ——— C语言实现动态顺序表-CSDN博客
数据结构 ——— 顺序表oj题:移除 nums 数组中的 val 元素(快慢指针)-CSDN博客
数据结构 ——— 顺序表oj题:编写函数,删除有序数组中的重复项-CSDN博客
接下来讲解的是动态顺序表的缺陷和单链表的概念以及实现
动态顺序表的缺陷
- 顺序表中间部分的插入删除函数和头部插入删除函数,时间复杂度都为O(N)
- 增容需要申请新的空间,拷贝数据,释放旧空间,会有不小的空间消耗,且还存在原地扩容或者异地扩容的问题
- 合理的增容机制一般是乘以原空间的2倍的增长,但势必还是会有一定的空间浪费
由以上的顺序表的缺陷,给出了新的数据结构 —— 单链表,单链表的结构可以完美的解决以上问题
单链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构,那么链表的顺序逻辑是通过链表中的指针链接(串联)次序实现的,且链表中的每一个节点都是独立的空间
链表这样设计的好处有:
- 解决了头部/中部插入删除时需要挪动数据的问题
- 按需申请或释放,不会存在浪费空间的问题
- 不会扩容,也不会存在扩容时的原地扩容或者异地扩容
单链表中节点的结构
// 单链表中数据的类型
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //单链表的数据
struct SListNode* next; //指向下一个节点的指针
}SLTNode;
以上的结构是单链表中每一个节点的结构
节点的结构由两部分组成:当前节点的数据和指向下一个节点的指针
通过 next 指针把各个节点串联起来,最后一个节点的指针指向 NULL 表示链表的尾节点,这样的结构就称之为单链表
单链表逻辑结构示意图
单链表中的每一个节点存储的都是数据和下一个节点的地址(指针)
只有最后一个节点的地址存储的是NULL(作用是用来标记结束)
实现单链表前的准备工作
和实现顺序表一样,需要准备3个文件
test.c 文件:用来测试代码功能的完善性
SList.h 文件:用来声明头文件和定义单链表的结构以及函数的声明
SList.c 文件:用来实现单链表的功能函数
实现单链表
1. 定义节点的指针
SLTNode* plist = NULL;
2. 创建节点
static SLTNode* BuyLTNode(SLTDataType x)
{
// 开辟节点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
// 判断是否开辟成功
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
添加 static 关键字用作保护,因为 创建节点函数 只会在 插入节点相关的函数 中使用,避免被用户直接使用,防止内存泄漏
newnode->data 存储数据 X
newnode->next 默认指向 NULL
3. 打印单链表中的所有数据
void SLTPrint(SLTNode* phead)
{
// 判断 phead 指针的有效性
assert(phead != NULL);
SLTNode* cur = phead;
// 当前单链表中无数据时
if (cur == NULL)
{
printf("当前链表无数据\n");
return;
}
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
一般在操作单链表时,不会直接使用 phead 指针,而是将 phead 指针赋值给同类型的 cur 指针来进行操作(因为会对指针的指向进行改动)
cur->data 是当前节点的数据,先打印当前数据
cur->next 是指向下一个节点的地址(指针)
cur->next 的类型是 struct SListNode* ,cur 的类型同样是 struct SListNode* ,所以把 cur->next 赋值给 cur ,那么 cur 这个指针就指向了下一个节点
直到 cur 为 NULL 就停止,因为单链表最后一个节点的 next 是NULL
4. 在单链表头部插入数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
plist 本身就是 SLTNode* 类型的指针,且不论是头插还是尾插,只要涉及到要改变 plist 的指向或者节点中的数据时,那么就要传递 plist 指针的地址才可以,所以函数的形参部分就要用二级指针接收(*pphead == plist)
第一次头插时:将 newnode 的 next 指向 *pphead(因为第一次头插时的 *pphead 就是 NULL ,那么 newnode 就是尾节点,所以刚好让尾节点的 next 指向了 NULL)
最后将 *pphead 指向新节点 newnode ,这样就完成了在单链表的头部插入数据
多次头插时:*pphead 就是原链表头节点的地址,直接将要头插的新节点 newnode 的 next 指向 *pphead ,这样就完成了头插和节点的链接,最后再将 *pphead 指向新的头节点 newnode
测试代码:
5. 在单链表尾部插入数据
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* cur = *pphead;
// 找到尾节点
while (cur->next != NULL)
cur = cur->next;
cur->next = newnode;
}
}
尾插数据要分两种情况看待:
当单链表为空链表时:那么直接将 *pphead 指向 newnode 即可
当单链表不为空链表时:先要找到尾节点,再把尾节点的 next 指向 newnode ,这样就实现了在单链表尾部插入数据
测试代码:
6. 在单链表头部删除数据
void SLTPopFront(SLTNode** pphead)
{
// 当链表为空时
if (*pphead == NULL)
{
printf("无数据可删除\n");
return;
}
SLTNode* cur = *pphead;
*pphead = cur->next;
free(cur);
}
头删数据要分两种情况看待:
当单链表为空时:没有数据可删除,提醒用户后返回即可
当单链表不为空时(一个或多个节点时):利用 cur 指针记录头节点的地址也就是 *pphead ,cur->next 就是第二个节点的地址,直接赋值给 *pphead 即可,这样就改变了 plist 的指向,最后再用 free 把头节点释放掉(以上代码逻辑在只有一个节点时同样适用)
测试代码:
7. 在单链表尾部删除数据
void SLTPopBack(SLTNode** pphead)
{
// 当前链表为空时
if (*pphead == NULL)
{
printf("无数据可删除\n");
return;
}
// 当只有一个节点时
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else // 有多个节点时
{
SLTNode* cur = *pphead;
// 找到尾节点的前一个节点
while (cur->next->next != NULL)
cur = cur->next;
free(cur->next);
cur->next = NULL;
}
}
尾删数据要分三种情况看待:
当单链表为空时:没有数据可删除,同样提醒用户后返回即可
当单链表只有一个节点时:直接 free 当前节点,也就是 *pphead 指向的节点,再置空
当单链表有多个节点时:利用 cur->next->next != NULL 找到尾节点的前一个节点,找到后,那么 cur->next 就是尾节点的地址,直接 ferr 再置空即可
测试代码:
8. 在单链表中查找指定的节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
根据数据找指定的节点,数据 X 和每个节点依次比较,找到了指定节点就返回指定节点的地址(指针),没有找到就返回 NULL
且 SLTFind 函数同时具备读和写的功能,因为返回的是一个节点的指针,所以可以接收返回值对节点的数据进行修改
9. 在单链表中 pos 节点插入数据
1. 在 pos 节点之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
// pos 节点会通过 SLTFind 函数查找,所以要确保 pos 节点的存在
assert(pos != NULL);
// 当第一个节点就是 pos 时
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
// 找到 pos 节点的前一个节点
while (cur->next != pos)
cur = cur->next;
prev = cur;
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
当第一个节点就是 pos 时:在 pos 之前插入就是头插的逻辑,直接调用 SLTPushFont 函数即可
其他情况:先要从头找到 pos 节点的前一个节点 prev,再通过各自的 next 串联起来
测试代码:
2. 在 pos 节点之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
// pos 节点会通过 SLTFind 函数查找,所以要确保 pos 节点的存在
assert(pos != NULL);
// 找到 pos 节点的下一个节点
SLTNode* nextnode = pos->next;
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
pos->next = newnode;
newnode->next = nextnode;
}
需要注意先后顺序,要先找到 pos 节点的下一个节点 nextnode,再通过各自的 next 串联起来
测试代码:
10. 在单链表中 pos 节点删除数据
1. 删除 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos != NULL);
/// 当第一个节点就是 pos 时
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
// 找到 pos 节点的前一个节点
while (cur->next != pos)
cur = cur->next;
prev = cur;
prev->next = pos->next;
free(pos);
}
}
当第一个节点就是 pos 时:删除 pos 节点就是头删的逻辑,调用 SLTPopFront 函数即可
其他情况:先要找到 pos 节点的前一个节点 prev ,再和 pos 的下一个节点通过 next 串联
测试代码:
2. 删除 pos 节点后一个节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pos != NULL);
// 当 pos 是最后一个节点时
if (pos->next == NULL)
{
printf("无数据可删除\n");
return;
}
else
{
// 找到 pos 节点的下两个节点
SLTNode* nextnode = pos->next->next;
free(pos->next);
pos->next = nextnode;
}
}
pos 节点为最后一个节点时:那么 pos 后就没有节点,提醒用户后返回即可
其他情况:先找到 pos 节点的后两个节点 nextnode,在释放 pos 节点的下一个节点,最后再将 pos 节点和 nextnode 节点串联
测试代码:
11. 释放单链表的所有节点
void SLTDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
while (cur != NULL)
{
prev = cur->next;
free(cur);
cur = prev;
}
}
释放当前 cur 节点前要先存储下一个节点的地址到 prev ,否则释放了当前 cur 节点就找不到下一个节点了
SList.h 的所有代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 单链表中数据的类型
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //单链表的数据
struct SListNode* next; //指向下一个节点的指针
}SLTNode;
// 打印
void SLTPrint(SLTNode* phead);
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 头删
void SLTPopFront(SLTNode** pphead);
// 尾删
void SLTPopBack(SLTNode** pphead);
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// pos位置插入(在 pos 之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// pos位置插入(在 pos 之后插入)
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
// pos位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
// 释放
void SLTDestroy(SLTNode** pphead);
SList.c 的所有代码
#include"SList.h"
// 打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
// 当前单链表中无数据时
if (cur == NULL)
{
printf("当前链表无数据\n");
return;
}
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 创建节点
static SLTNode* BuyLTNode(SLTDataType x)
{
// 开辟节点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
// 判断是否开辟成功
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* cur = *pphead;
// 找到尾节点
while (cur->next != NULL)
cur = cur->next;
cur->next = newnode;
}
}
// 头删
void SLTPopFront(SLTNode** pphead)
{
// 当前链表为空时
if (*pphead == NULL)
{
printf("无数据可删除\n");
return;
}
SLTNode* cur = *pphead;
*pphead = cur->next;
free(cur);
}
// 尾删
void SLTPopBack(SLTNode** pphead)
{
// 当前链表为空时
if (*pphead == NULL)
{
printf("无数据可删除\n");
return;
}
// 当只有一个节点时
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else // 有多个节点时
{
SLTNode* cur = *pphead;
// 找到尾节点的前一个节点
while (cur->next->next != NULL)
cur = cur->next;
free(cur->next);
cur->next = NULL;
}
}
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
// 任意位置插入(在 pos 之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
// pos 节点会通过 SLTFind 函数查找,所以要确保 pos 节点的存在
assert(pos != NULL);
// 当第一个节点就是 pos 时
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
// 找到 pos 节点的前一个节点
while (cur->next != pos)
cur = cur->next;
prev = cur;
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
// 任意位置插入(在 pos 之后插入)
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
// pos 节点会通过 SLTFind 函数查找,所以要确保 pos 节点的存在
assert(pos != NULL);
// 找到 pos 节点的下一个节点
SLTNode* nextnode = pos->next;
// 申请新节点
SLTNode* newnode = BuyLTNode(x);
pos->next = newnode;
newnode->next = nextnode;
}
// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos != NULL);
/// 当第一个节点就是 pos 时
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
// 找到 pos 节点的前一个节点
while (cur->next != pos)
cur = cur->next;
prev = cur;
prev->next = pos->next;
free(pos);
}
}
// pos位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pos != NULL);
// 当 pos 是最后一个节点时
if (pos->next == NULL)
{
printf("无数据可删除\n");
return;
}
else
{
// 找到 pos 节点的下两个节点
SLTNode* nextnode = pos->next->next;
free(pos->next);
pos->next = nextnode;
}
}
// 释放
void SLTDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
while (cur != NULL)
{
prev = cur->next;
free(cur);
cur = prev;
}
}