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

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

2023-05-29 88
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单链表单链表的优点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语言，数据结构的博客，撒花！















































文章标签：
C语言
存储
关键词：
数据结构链表
数据结构单链表
数据结构线性表
数据结构图
数据结构线性表链表
游客cxwjr657j6vg2
目录
相关文章
weixin_836869520
|
7天前
|
算法 Java
Java数据结构与算法：双向链表
Java数据结构与算法：双向链表
weixin_836869520
10 0
weixin_836869520
|
7天前
|
算法 Java
Java数据结构与算法：循环链表
Java数据结构与算法：循环链表
weixin_836869520
7 0
倔强的石头_
|
7天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点（图文详解）
【数据结构与算法 刷题系列】求带环链表的入环节点（图文详解）
倔强的石头_
13 0
倔强的石头_
|
7天前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环（图文详解）
【数据结构与算法 刷题系列】判断链表是否有环（图文详解）
倔强的石头_
12 0
倔强的石头_
|
7天前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
倔强的石头_
11 0
倔强的石头_
|
7天前
|
算法
【数据结构与算法 经典例题】随机链表的复制（图文详解）
【数据结构与算法 经典例题】随机链表的复制（图文详解）
倔强的石头_
11 0
倔强的石头_
|
7天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构（图文详解）
【数据结构与算法 经典例题】链表的回文结构（图文详解）
倔强的石头_
15 0
倔强的石头_
|
7天前
|
算法
【数据结构与算法 经典例题】反转链表(图文详解)
【数据结构与算法 经典例题】反转链表(图文详解)
倔强的石头_
11 0
倔强的石头_
|
7天前
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
倔强的石头_
14 0
倔强的石头_
|
7天前
|
算法 C语言
【数据结构与算法 经典例题】相交链表求交点
【数据结构与算法 经典例题】相交链表求交点
倔强的石头_
10 0