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

简介: 【数据结构】单链表的增删查改(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();  //测试查和改
}


相关文章
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
91 1
|
3月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
80 4
|
3月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
63 4
|
2天前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
20天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
机器学习/深度学习 人工智能 C语言
C语言简单实现14个例题(谭浩强第四版)
版权声明:转载请注明出处:http://blog.csdn.net/dajitui2024 https://blog.csdn.net/dajitui2024/article/details/79396241 1、仅供学习交流参考。
1175 0
|
1月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
62 23
|
1月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
66 15