单链表(C语言实现)

简介: 单链表(C语言实现)

1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

我们之前讲解了顺序表,那么顺序表的缺点体现在哪呢?

1.顺序表空间不够时需要扩容,扩容(尤其是异地扩容)是有一定代价的,其次还可能存在一定的空间浪费

2.在头部或者中部插入或删除,需要挪动数据,效率低下

据此我们就提出了链表,可以按需申请空间,且不需要挪动数据,来对此缺点进行优化

下面我们就来进行正文单链表的讲解吧!

2.单链表的结构

单链表的结构包含了一个数据域和一个指针域,它的特点就是通过指针域的指针指向下一个结点的地址来达到链式存储

typedef int SLTDataType;//数据类型
typedef struct SListNode
{
  SLTDataType data;//数据
  struct SListNode* next;//指向下一个节点的指针
}SLTNode;

图示:

919975122ab5350b64a9bd7b86faa3b0.png

3.接口实现

3.1创建一个结点

单链表是由一个个独立的结点链接起来的,新增节点时就需要向内存申请一个结点空间

//创建一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)  //防止申请失败
  {
    perror("malloc fail");
    exit(-1);
  }
  //赋值
  newnode->data = x;
  newnode->next = NULL;
  //返回新节点
  return newnode;
}

这里用malloc申请空间,而不是用结构类型变量,是因为前者申请的空间是在堆区中开辟存放的,出了函数栈帧数据仍然存在,但是用结构类型变量,出了函数栈帧就销毁了,并不能存储数据

3.2创建一个单链表

创建一个单链表

//创建一个单链表
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  int x = 0;
  for (int i = 0; i < n; ++i)
  {
    //scanf("%d", &x); //手动输入
    //SLTNode* newnode = BuySLTNode(x);
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode; //创建头结点
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode; //变动ptail指针指向新节点
    }
  }
  ptail->next = NULL; //尾结点指空
  return phead;
}

3.3打印链表

遍历单链表将其数据域打印出来

//打印链表
void SLTPrint(SLTNode* phend)
{
  SLTNode* cur = phend;
  while (cur) //cur指针遍历到NULL就结束
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

3.4尾插

首先创建一个新结点,然后通过头结点向后遍历找到尾结点,最后将尾结点与新节点链接起来,这里还要考虑一种情况,如果链表为空就直接把新结点赋给头结点

//尾插
void SLTPushBack(SLTNode** pphend, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphend == NULL)
  {
    *pphend = newnode;
  }
  else
  {
    //找尾
    SLTNode* tail = *pphend;
    while (tail->next)
    {
      tail = tail->next;
    }
    //插入
    tail->next = newnode;
  }
}

这里有个问题就是为什么函数传参要用二级指针?

这是因为进行插入删除操作时,如果需要对头结点进行操作来改变头结点,就要改变头结点指针的指向,改变一级指针需要用二级指针来操作

7a7c3801f613e2e8e8c57120d118f3d3.png

3.5尾删

首先需要通过头结点向后遍历找到尾结点的前一个结点,然后释放掉尾结点,最后再将尾结点的上一个结点指空,这里需要断言处理链表为空的情况(为空不能删),还有只剩一个结点的情况,就直接释放掉头结点并将头指针置空(防止野指针)

//尾删
void SLTPopBack(SLTNode** pphend)
{
  assert(*pphend);
  //只剩一个头结点的情况
  if ((*pphend)->next == NULL)
  {
    free(*pphend);
    *pphend = NULL;
  }
  else
  {
    SLTNode* tail = *pphend;
    //找尾
    while (tail->next->next)
    {
      tail = tail->next;
    }
    //写法二:遍历找到尾结点并记录前一个结点的位置
    //SLLNode* pre = *pphead;
    //SLLNode* tail = *pphead;
    //找尾
    //while (tail->next != NULL)
    //{
      //pre = tail;
      //tail = tail->next;
    //}
    //释放
    free(tail->next);
    tail->next = NULL;
  }
}

3.6头插

首先创建一个新的结点,再将新结点与头结点链接,最后将头结点更新为新的结点即可

//头插
void SLTPushFront(SLTNode** pphend, SLTDataType x)
{
  //创建新节点
  SLTNode* newnode = BuySLTNode(x);
  //链接
  newnode->next = *pphend;
  //更新头结点
  *pphend = newnode;
}

3.7头删

先保存头结点的下一个结点的地址,再释放掉头结点,最后将头结点更新为新的结点即可,当然这里还要断言链表为空的情况(为空不能删),凡是进行删除的操作都要考虑一下是否有不能删的情况

//头删
void SLTPopFront(SLTNode** pphend)
{
    //断言链表为空
  assert(*pphend);
  //保存头结点的下一个结点的地址
  SLTNode* next = (*pphend)->next;
  //释放头结点
  free(*pphend);
  //更新头结点
  *pphend = next;
}

3.8查找结点位置

输入结点数值遍历并比较来查找该结点,找到了就返回结点位置,没找到或者链表为空就返回NULL。查找函数主要是配合后面的任意位置的插入删除操作的

//查找结点位置
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
      //遍历比较
    if (cur->data == x)
    {
        //找到就返回地址
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

3.9 任意位置之后插入

首先查找到目标位置(通过查找函数),并创建一个新的结点,再将新结点指向目标位置的下一个结点,最后将目标结点指向新结点,这里还需要断言一下没找到目标结点返回NULL的情况

//任意位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  //断言没找到的情况
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

3.10 任意位置之前插入

首先从头结点遍历找到目标结点的上一个结点,并创建一个新节点,然后将目标结点的上一个结点指向新结点,最后再将新节点指向目标结点,如果链表为空就复用头插,因为同时还需要改变头结点的位置,所以这里传二级指针,这里还需要断言链表不为空,但是pos为空的情况

//任意位置之前插入
void SLTInsert(SLTNode** pphend, SLTNode* pos, SLTDataType x)
{
    //断言链表不为空,但是pos为空的情况
  assert(pos);
  //头插
  if (*pphend == pos)
  {
    SLTPushFront(pphend, x);
  }
  else
  {
    SLTNode* prev = *pphend;
    //遍历找到目标结点的上一个结点
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    //链接
    prev->next = newnode;
    newnode->next = pos;
  }
}

3.11任意位置之后删除

首先记录目标位置的后一个位置的结点的地址(防止释放掉目标位置的后一个位置后地址丢失),然后释放掉目标位置的后一个位置,最后再将目标位置指向其后两个位置的结点,这里需要断言pos为空的情况,还要考虑只剩一个头结点其后面没有结点可删除的情况

//任意位置之后删除
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //只剩一个头结点
  if (pos->next == NULL)
  {
      perror("err");
    return;
  }
  else
  {
        //记录目标位置的后一个位置的结点的地址
    SLTNode* nextNode = pos->next;
    //链接
    pos->next = nextNode->next;
    free(nextNode);
    //nextNode为局部变量,可以不考虑置空
  }
}

3.12任意位置删除

首先遍历找到目标结点的上一个结点,然后将目标结点的上一个结点指向目标结点的下一个结点,最后释放掉目标结点即可,这里需要断言pos为空的情况和链表为空的情况(为空不能删),还需要注意如果来链表只剩一个头结点就可以直接复用头删,因为同时还需要改变头结点的位置所以这里传二级指针

//任意位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    //断言链表为空的情况
  assert(*pphead);
  assert(pos);
  //头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    //为什么无需置空?
    //pos是栈帧中局部变量
    //为什么必须free?
    //malloc出来的,堆区中存放数据,必须手动free还给操作系统
    //如果不free在用的时候就是野指针
  }
}

3.13销毁链表

因为链表中的元素不是连续存放的,所以销毁时只能逐个结点销毁,我们的方法是挨个儿结点遍历链表,并记录该节点下一个结点的位置(防止位置丢失),然后释放掉该节点并使用后一个节点的位置继续向后遍历销毁直到链表为空。最后一定要释放头指针,虽然链表已经释放完了,但是*pphead依然指向头结点的位置,就是野指针,所以必须置空

//销毁链表
void SLTDestroy(SLTNode** pphead)
{
    //断言指针为空
    assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
      //记录下一个结点的位置
    SLTNode* next = cur->next;
    //释放
    free(cur);
    //继续向后遍历
    cur = next;
  }
  *pphead = NULL;
}

单链表的介绍到这里就介绍结束了,期待大佬们的三连!

文章有写的不足或是错误的地方,欢迎私信或评论指出,我会在第一时间改正

目录
相关文章
|
7月前
|
存储 编译器 C语言
【数据结构】C语言实现单链表万字详解(附完整运行代码)
【数据结构】C语言实现单链表万字详解(附完整运行代码)
134 0
|
2月前
|
存储 C语言
C语言单链表实现
一个用C语言编写的简单学生信息管理系统,该系统具备信息输入、成绩计算、排序、删除、查找、修改、保存和读取文件等功能。
27 0
C语言单链表实现
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
633 6
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
3月前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
6月前
|
存储 人机交互 C语言
【C语言项目实战】使用单链表实现通讯录
【C语言项目实战】使用单链表实现通讯录
|
7月前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
7月前
|
C语言
C语言用头插法建立单链表
C语言用头插法建立单链表
31 0
|
7月前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
7月前
|
存储 C语言
C语言之单链表的实现以及链表的介绍
C语言之单链表的实现以及链表的介绍