【数据结构】线性表之单链表(讲解实现——带动图理解)(2)

简介: 单链表单链表的优点1.头部和中间插入或删除数据效率高,无需挪动。2.按照需求申请释放空间,无需担心空间不够用。单链表的缺点1.不可以进行下标随机访问。2.复杂度是O(n)3.反向遍历困难单链表是线性表的一种,单链表是链式存储的线性表,不同于单链表,链表在内存空间中不连续,而是由结构体内的next指针下一条数据进行链接🧐
  • 头结点不为空或插入结点就是头结点指向的结点,找到pos前一个结点进行插入
  • 1c6dcf3c65454e689b63ad328a53f082.gif

单链表删除函数

头删

从头部删除数据,将头结点位置删除,将头结点的下一个位置指向头结点

void LLPopFront(LinkedList** PPhead)
{
  assert(PPhead);
  assert(*PPhead);
  LinkedList* temp = (*PPhead)->next;
  free(*PPhead);      //释放掉删除的结点
  *PPhead = temp;
}

210a89364dad45bca1f4d3ef05a7e98a.gif

尾删

void LLPopBack(LinkedList** PPhead)
{
  assert(PPhead);
  assert(*PPhead);
  if ((*PPhead)->next == NULL)
  {
    *PPhead = NULL;
  }
  else
  {
    LinkedList* tail = *PPhead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
  • 如果头结点为空,不能进行删除。
  • 如果头结点下一个为空,直接进行删除
  • 如果头结点和头结点的下一个都不为空,删除下一个结点为空的结点,那就需要找到头结点下一个结点的下一个结点为空的结点


2ed1d394fabf4ecdb159afb64a3e46d4.gif

指定结点后删除

后面的数据依次向前移动

void SListEraseAfter(LinkedList* pos)
{
  if (pos == NULL)
  {
    printf("没发现此数据");
    return;
  }
  if (pos->next == NULL)
  {
    printf("链表后面已经为空了\n");
    return;
  }
  LinkedList* temp = pos->next;
  pos->next = pos->next->next;
  free(temp);
}
  • 如果pos为空或pos->next为空则提示并返回


086fd2673a2b47a3bdeb7bb808bd941d.gif

指定结点删除

删除指定结点,将指定结点的next连接到指定结点前面的next结点,然后释放指定的结点

void SListErase(LinkedList**PPhead,LinkedList* pos)
{
  assert(pos);
  assert(PPhead);
  assert(*PPhead);
  if (pos == *PPhead)
  {
    LLPopFront(PPhead);
    return;
  }
  LinkedList* cur = *PPhead;
  while (cur->next != pos)
  {
    cur = cur->next;
  }
  cur->next = cur->next->next;
  free(pos);
}
  • 头结点指针指向的结点等于pos,复用尾插函数


19e24b827d1248d58c2d8a6205bfea86.gif

销毁单链表

将每个结点依次释放。最后将头结点制空。

void SListDestroy(LinkedList** PPhead)
{
  assert(*PPhead);
  if (*PPhead == NULL)
  {
    printf("已经是空链表了\n");
    return;
  }
  while ((*PPhead)->next != NULL)
  {
    LinkedList* tep = (*PPhead)->next;
    (*PPhead)->next = (*PPhead)->next->next;
    free(tep);
  }
  free(*PPhead);
  *PPhead = NULL;
}

d8114d763d1a4325af3d871038d99251.gif

文件分类

🌞🌞为了使代码更有阅读性,我们不建议把所有函数写在一个文件里,所以这里分成三个文件,模块化管理

test.c

测试文件

#include "LinkedList.h"
int main()
{
  LinkedList *Phead = NULL;
  LLPushFront(&Phead, 8);
  LLPushBack(&Phead,2);
  LLPushBack(&Phead,3);
  LLPushBack(&Phead,4);
  LLPushBack(&Phead,5);
  //LLPopBack(&Phead);
  //LLPopFront(&Phead);
  //LLPopBack(&Phead);
  //LLPopFront(&Phead);
  //LLPopFront(&Phead);
  LinkedList* temp = LListFind(Phead, 3);
  SListInsertAfter(temp,88);
  temp = LListFind(Phead, 4);
  SListEraseAfter(temp);
  temp = LListFind(Phead, 4);
  SListInsertFront(&Phead,temp, 99);
  printLL(Phead);
  temp = LListFind(Phead, 99);
  SListErase(&Phead, temp);
  SListDestroy(&Phead);
}

LinkedList.c

将所有单链表需要的函数封装在此文件下⭐

#include "LinkedList.h"
LinkedList* BuyNewNode(LLDataType x)
{
  LinkedList* ret = (LinkedList*)malloc(sizeof(LinkedList));
  if (ret == NULL)
  {
    perror("Malloc:");
    return NULL;
  }
  ret->data = x;
  ret->next = NULL;
  return ret;
}
void LLPushBack(LinkedList** PPhead, LLDataType x)
{
  assert(PPhead);
  LinkedList* NewNode = BuyNewNode(x);
  if (*PPhead == NULL)
  {
    *PPhead = NewNode;
  }
  else
  {
    LinkedList* tail = *PPhead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = NewNode;
  }
}
void LLPushFront(LinkedList** PPhead, LLDataType x)
{
  assert(PPhead);
  LinkedList* NewNode = BuyNewNode(x);
  if (*PPhead == NULL)
  {
    *PPhead = NewNode;
  }
  else
  {
    NewNode->next = *PPhead;
    *PPhead = NewNode;
  }
}
void LLPopBack(LinkedList** PPhead)
{
  assert(PPhead);
  assert(*PPhead);
  if ((*PPhead)->next == NULL)
  {
    *PPhead = NULL;
  }
  else
  {
    LinkedList* tail = *PPhead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
void LLPopFront(LinkedList** PPhead)
{
  assert(PPhead);
  assert(*PPhead);
  LinkedList* temp = (*PPhead)->next;
  free(*PPhead);
  *PPhead = temp;
}
void printLL(LinkedList* Phead)
{
  while (Phead!=NULL)
  {
    printf("%d->", Phead->data);
    Phead = Phead->next;
  }
  printf("NULL");
}
LinkedList* LListFind(LinkedList* phead, LLDataType x)
{
  assert(phead);
  LinkedList *ret = phead;
  while (ret->data != x)
  {
    if (ret == NULL)
    {
      return NULL;
    }
    ret = ret->next;
  }
  return ret;
}
void SListInsertAfter(LinkedList* pos, LLDataType x)
{
  assert(pos);
  LinkedList *newnode = BuyNewNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SListInsertFront(LinkedList** PPhead, LinkedList* pos, LLDataType x)
{
  assert(pos);
  assert(PPhead);
  if (*PPhead == NULL||*PPhead==pos)
  {
    LLPushFront(PPhead, x);
  }
  else
  {
    LinkedList* cur = *PPhead;
    while (cur->next != pos)
    {
      cur = cur->next;
    }
    LinkedList* newnode = BuyNewNode(x);
    newnode->next = cur->next;
    cur->next = newnode;
  }
}
void SListEraseAfter(LinkedList* pos)
{
  if (pos == NULL)
  {
    printf("没发现此数据");
    return;
  }
  if (pos->next == NULL)
  {
    printf("链表后面已经为空了\n");
    return;
  }
  LinkedList* temp = pos->next;
  pos->next = pos->next->next;
  free(temp);
}
void SListErase(LinkedList**PPhead,LinkedList* pos)
{
  assert(pos);
  assert(PPhead);
  assert(*PPhead);
  if (pos == *PPhead)
  {
    LLPopFront(PPhead);
    return;
  }
  LinkedList* cur = *PPhead;
  while (cur->next != pos)
  {
    cur = cur->next;
  }
  cur->next = cur->next->next;
  free(pos);
}
//void SListDestroy(LinkedList** Phead)
//{
//  assert(Phead);
//  if (*Phead == NULL)
//  {
//    printf("已经是空链表了");
//    return;
//  }
//  while ((*Phead) != NULL)
//  {
//    LinkedList* temp = *Phead;
//    *Phead = (*Phead)->next;
//    free(temp);
//  }
//}
void SListDestroy(LinkedList** PPhead)
{
  assert(*PPhead);
  if (*PPhead == NULL)
  {
    printf("已经是空链表了\n");
    return;
  }
  while ((*PPhead)->next != NULL)
  {
    LinkedList* tep = (*PPhead)->next;
    (*PPhead)->next = (*PPhead)->next->next;
    free(tep);
  }
  free(*PPhead);
  *PPhead = NULL;
}

LinkedList.h

将主程序所需要的函数全部在头文件中声明,增加代码阅读性⭐

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int LLDataType;
typedef struct LinkedList
{
  LLDataType data;
  struct LinkedList* next;
}LinkedList;
void printLL(LinkedList* Phead);
void LLPushBack(LinkedList** PPhead, LLDataType x);
void LLPushFront(LinkedList** PPhead, LLDataType x);
void LLPopBack(LinkedList** PPhead);
void LLPopFront(LinkedList** PPhead);
LinkedList* LListFind(LinkedList* phead, LLDataType x);
void SListInsertAfter(LinkedList* pos, LLDataType x);
void SListEraseAfter(LinkedList* pos);
void SListDestroy(LinkedList** Phead);
void SListInsertFront(LinkedList** Phead, LinkedList* pos, LLDataType x);
void SListErase(LinkedList** PPhead, LinkedList* pos);

撒花

这就是实现单链表的全部内容了,创作不易,还请各位小伙伴多多点赞👍关注收藏⭐,以后也会更新各种关于c语言,数据结构的博客,撒花!















































相关文章
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
28天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
54 4
|
29天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
28天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
41 0
|
29天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
24 0
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表