AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】单链表的增删查改（C语言实现）(2)

2022-11-19 74
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】单链表的增删查改（C语言实现）(2)

8、在头部删除数据

特别注意： 和插入数据一样，因为我们删除的可能是链表中的最后一个数据，即可能会改变 plist 的指向 (让 plist 重新指向 NULL)，所以不管我们在什么地方删除数据，都需要传递二级指针。


其次，由于我们这里是删除数据，所以函数调用者需要保证调用此函数时链表中至少是含有一个数据的；所以我们对 *pphead (等价于 plist) 进行断言，当调用者错误使用此函数时，我们直接报错并介绍程序。

//在头部删除数据
void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //当链表为空时，删除元素报错
  SLTNode* tmp = (*pphead)->next;  //注意：* 和 -> 优先级一样，要加括号
  free(*pphead);
  *pphead = tmp;
}

9、在尾部删除数据

在尾部删除数据面临着和尾插一样的问题，需要改变前一个节点的next指针，所以时间复杂度也为O(N)。

//在尾部删除数据
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //当链表为空时，删除元素报错
  if ((*pphead)->next == NULL)  //当链表只有一个元素时，相当于头删
  {
    SListPopFront(pphead);
    return;
  }
  //先找到链表的尾及其前一个节点
  SLTNode* cur = *pphead;
  SLTNode* prev = cur;
  while (cur->next != NULL)
  {
    prev = cur;
    cur = cur->next;
  }
  prev->next = NULL;
  free(cur);
  cur = NULL;
}

10、删除pos位置前的数据

//删除pos位置前的数据
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && pos);
  assert(*pphead);  //当链表为空时，删除元素报错
  if (pos == *pphead)  //pos等于*pphead时相当于头删
  {
    SListPopFront(pphead);
    return;
  }
  //找到pos的前一个节点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    assert(prev);  //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错
    prev = prev->next;
  }
  SLTNode* tmp = pos->next;
  prev->next = tmp;
  free(pos);
  pos = NULL;
}

11、删除pos位置后的数据

和在pos位置后插入数据一样，为了提高效率，人们也设计了一个在pos位置后删除数据的函数。

//删除pos位置后的数据
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && pos);
  assert(*pphead);  //当链表为空时，删除元素报错
  assert((*pphead)->next);  //当链表只有一个元素时，也不能调用此函数
  SLTNode* tmp = pos->next->next;
  free(pos->next);
  pos->next = tmp;
}

12、修改pos位置处的数据

修改数据也不会改变头指针，所以这里传一级指针；同时，为了保证代码的鲁棒性，我们这里对 phead 和 pos 断言一下。

//修改pos位置处的数据
void SListModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
  assert(phead && pos);
  SLTNode* cur = phead;
  while (cur != pos)
  {
    assert(cur);  //如果cur为空循环还没停止，说明在链表中找不到pos，直接报错
    cur = cur->next;
  }
  cur->data = x;
}

13、打印链表中的数据

打印数据也不会改变头指针，所以这里传一级指针；但是这里和修改数据不一样的地方是，当链表为空的时候我们打印的逻辑也是正常的，只是说调用此函数什么都不打印而已，但是我们不能对其断言让其为空时报错。

//打印链表
void SListPrint(SLTNode* phead)  //打印不需要改变plist
{
  //不用对Phead进行断言，当链表为空时打印的逻辑是正常的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);  //-> 和 NULL 是为了让我们的链表更形象化
    cur = cur->next;
  }
  printf("NULL\n");
}

14、销毁链表

销毁链表需要将 plist 值为空，所以这里我们传递二级指针。

//销毁链表
void SListDestory(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur != NULL)
  {
    SLTNode* tmp = cur->next;  //保存下一个节点的地方
    free(cur);  //释放
    cur = tmp;
  }
  *pphead = NULL;  //将plist置为空
}

三、完整代码

1、SList.h

#pragma once  //防止头文件重复包含
//头文件的包含
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//符号和结构的声明
typedef int SLTDataType;  //数据类型重命名
typedef struct SListNode   //链表的一个节点
{
  SLTDataType data;
  struct SListNode* next;  //存放下一个节点的地址
}SLTNode;
//函数的声明
//创建新建节点
SLTNode* BuySLTNode(SLTDataType x);
//在头部插入数据
void SListPushFront(SLTNode** pphead, SLTDataType x);
//销毁链表
void SListDestory(SLTNode** pphead);
//在尾部插入数据
void SListPushBack(SLTNode** pphead, SLTDataType x);
//查找数据
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos之前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入数据
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//打印链表
void SListPrint(SLTNode* phead);
//在头部删除数据
void SListPopFront(SLTNode** pphead);
//在尾部删除数据
void SListPopBack(SLTNode** pphead);
//删除pos位置处的数据
void SListErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置后的数据
void SListEraseAfter(SLTNode** pphead, SLTNode* pos);
//修改pos位置处的函数
void SListModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

2、SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    return NULL;  //如果malloc失败，返回NULL
  }
  newNode->data = x;
  newNode->next = NULL;
  return newNode;
}
//销毁链表
void SListDestory(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur != NULL)
  {
    SLTNode* tmp = cur->next;  //保存下一个节点的地方
    free(cur);  //释放
    cur = tmp;
  }
  *pphead = NULL;  //将plist置为空
}
//在头部插入数据
void SListPushFront(SLTNode** pphead, SLTDataType x)  //要改变plist，所以用二级指针来接收plist的地址
{
  assert(pphead);  //pphead为plist的地址，一定不为空
  //assert(*pphead);  //error：*pphead得到plist，而链表可能没有节点，所以plist可以为空，不用断言
  SLTNode* newNode = BuySLTNode(x);  //开辟新节点
  newNode->next = *pphead;
  *pphead = newNode;
}
//打印链表
void SListPrint(SLTNode* phead)  //打印不需要改变plist
{
  //不用对Phead进行断言，当链表为空时打印的逻辑是正常的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);  //-> 和 NULL 是为了让我们的链表更形象化
    cur = cur->next;
  }
  printf("NULL\n");
}
//在尾部插入数据
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);  //plist的地址一定不为空
  SLTNode* newNode = BuySLTNode(x);
  if (*pphead == NULL)  //如果链表为空
  {
    newNode->next = *pphead;
    *pphead = newNode;
    return;
  }
  //如果链表不为空，我们需要找到链表的尾
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newNode;
}
//查找数据
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  assert(phead);  //链表为空查找直接报错
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
      return cur;  //找到返回节点地址
    cur = cur->next;
  }
  return NULL;  //找不到返回空
}
//在pos位置前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)  //如果pos等于*pphead，相当于头插
  {
    SListPushFront(pphead, x);
    return;
  }
  SLTNode* newNode = BuySLTNode(x);
  //找到pos位置的前一个节点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    assert(prev);  //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错
    prev = prev->next;
  }
  prev->next = newNode;
  newNode->next = pos;
}
//在pos位置之后插入数据
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead && pos);
  SLTNode* next = pos->next;
  SLTNode* newNode = BuySLTNode(x);
  pos->next = newNode;
  newNode->next = next;
}
//在头部删除数据
void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //当链表为空时，删除元素报错
  SLTNode* tmp = (*pphead)->next;  //注意：* 和 -> 优先级一样，要加括号
  free(*pphead);
  *pphead = tmp;
}
//在尾部删除数据
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //当链表为空时，删除元素报错
  if ((*pphead)->next == NULL)  //当链表只有一个元素时，相当于头删
  {
    SListPopFront(pphead);
    return;
  }
  //先找到链表的尾及其前一个节点
  SLTNode* cur = *pphead;
  SLTNode* prev = cur;
  while (cur->next != NULL)
  {
    prev = cur;
    cur = cur->next;
  }
  prev->next = NULL;
  free(cur);
  cur = NULL;
}
//删除pos位置处的数据
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && pos);
  assert(*pphead);  //当链表为空时，删除元素报错
  if (pos == *pphead)  //pos等于*pphead时相当于头删
  {
    SListPopFront(pphead);
    return;
  }
  //找到pos的前一个节点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    assert(prev);  //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错
    prev = prev->next;
  }
  SLTNode* tmp = pos->next;
  prev->next = tmp;
  free(pos);
  pos = NULL;
}
//删除pos位置后的数据
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && pos);
  assert(*pphead);  //当链表为空时，删除元素报错
  assert((*pphead)->next);  //当链表只有一个元素时，也不能调用此函数
  SLTNode* tmp = pos->next->next;
  free(pos->next);
  pos->next = tmp;
}
//修改pos位置处的数据
void SListModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
  assert(phead && pos);
  SLTNode* cur = phead;
  while (cur != pos)
  {
    assert(cur);  //如果cur为空循环还没停止，说明在链表中找不到pos，直接报错
    cur = cur->next;
  }
  cur->data = x;
}

3、test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void test1()   //测试插入
{
  SLTNode* plist = NULL;  //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL；
  //头插
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPrint(plist);
  //尾插
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPushBack(&plist, 6);
  SListPrint(plist);
  //在pos位置前插入
  SLTNode* pos = SListFind(plist, 5);
  if (pos != NULL)
  {
    SListInsert(&plist, pos, 50);
  }
  pos = SListFind(plist, 3);
  if (pos != NULL)
  {
    SListInsert(&plist, pos, 30);
  }
  SListPrint(plist);
  pos = SListFind(plist, 6);
  if (pos != NULL)
  {
    SListInsert(&plist, pos, 60);
  }
  SListPrint(plist);
  //在pos位置后插入
  pos = SListFind(plist, 1);
  if (pos != NULL)
  {
    SListInsertAfter(&plist, pos, 10);
  }
  pos = SListFind(plist, 3);
  if (pos != NULL)
  {
    SListInsertAfter(&plist, pos, 30);
  }
  SListPrint(plist);
  //销毁
  SListDestory(&plist);
}
void test2()  //测试删除
{
  SLTNode* plist = NULL;  //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL；
  //头插
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPrint(plist);
  //在头部删除数据
  //SListPopFront(&plist);
  //SListPopFront(&plist);
  //SListPopFront(&plist);
  //SListPrint(plist);
  //在尾部删除数据
  //SListPopBack(&plist);
  //SListPopBack(&plist);
  //SListPopBack(&plist);
  //SListPrint(plist);
  //删除pos位置处的数据
  //SLTNode* pos = SListFind(plist, 1);
  //if (pos != NULL)
  //{
  //  SListErase(&plist, pos);
  //}
  //pos = SListFind(plist, 3);
  //if (pos != NULL)
  //{
  //  SListErase(&plist, pos);
  //}
  //SListPrint(plist);
  //pos = SListFind(plist, 2);
  //if (pos != NULL)
  //{
  //  SListErase(&plist, pos);
  //}
  //SListPrint(plist);
  //删除pos位置后的数据
  SLTNode* pos = SListFind(plist, 2);
  if (pos != NULL)
  {
    SListEraseAfter(&plist, pos);
  }
  SListPrint(plist);
  pos = SListFind(plist, 3);
  if (pos != NULL)
  {
    SListEraseAfter(&plist, pos);
  }
  SListPrint(plist);
  //销毁
  SListDestory(&plist);
}
void test3()  //测试查和改
{
  SLTNode* plist = NULL;  //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL；
  //头插
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPrint(plist);
  //查找并修改pos位置处的数据
  SLTNode* pos = SListFind(plist, 3);
  if (pos != NULL)
  {
    SListModify(plist, pos, 30);
  }
  SListPrint(plist);
  pos = SListFind(plist, 1);
  if (pos != NULL)
  {
    SListModify(plist, pos, 10);
  }
  SListPrint(plist);
  //销毁
  SListDestory(&plist);
}
int main()
{
  //test1();  //测试插入
  //test2();  //测试删除
  test3();  //测试查和改
}


文章标签：
C语言
关键词：
数据结构c语言
C语言数据结构
数据结构单链表
C语言单链表
C语言增删查改
野猪佩奇`
目录
相关文章
ephemerals__
|
17天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
91 9
ephemerals__
|
16天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
58 16
ephemerals__
|
16天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
65 8
ephemerals__
|
18天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
45 4
ephemerals__
|
20天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
50 3
aliyun1622584902-46568
|
20天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
aliyun1622584902-46568
32 2
ephemerals__
|
18天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
38 0
這～悸ベ雨落憂殇
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
46 0
7fa6b5ui5pmtk
|
5月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
31 2
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
45 2

热门文章

最新文章

  • 1
    《C语言及程序设计》实践参考——改造链表
  • 2
    C语言中的逗号操作符
  • 3
    C语言连接MySQL数据库
  • 4
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 5
    C语言预处理之二-----宏定义那点事儿
  • 6
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    四则运算表达式求值程序(C语言版)
  • 10
    带你实现初阶扫雷小游戏—【C语言】
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    98
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    243
  • 3
    数据结构（九）---并查集
    72
  • 4
    【数据结构与算法 11，高并发系统基础篇
    41
  • 5
    JavaScript 中实现常见数据结构：栈、队列与树
    78
  • 6
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    42
  • 7
    顺序表的实现（迈入数据结构的大门）（2）
    39
  • 8
    顺序表的实现（迈入数据结构的大门）（1）
    32
  • 9
    每个程序员都必须掌握的8种数据结构，retrofit教程
    35
  • 10
    scala中常见数据结构的用法
    47

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问