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

【数据结构】—C语言实现单链表（超详细！）

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

一、单链表介绍

单链表是什么？

       单链表是一种常见的数据结构，它由一个个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

单链表需要实现的基本功能？

       基本的操作为：增、删、查、改

       具体为：

  1. 插入元素：将新元素插入到链表的指定位置，可以是链表的头部、尾部或中间位置。
  2. 删除元素：从链表中删除指定位置的元素。
  3. 查找元素：根据给定的值，在链表中查找对应的元素，并返回其位置。
  4. 遍历链表：按顺序访问链表中的每个元素。
  5. 获取链表长度：获取链表中元素的个数。
  6. 判断链表是否为空：判断链表是否为空链表。
  1. 清空链表：删除链表中的所有元素，使其成为一个空链表。

单链表的基本结构是怎么样的？

       一张图让你理解

       注：此文实现的是没有带哨兵的单链表

      注意：最后一个节点的next指针指向的是NULL

二、总体思路

       如何实现？按照单链表的基本介绍以及功能来一步一步实现！首先实现什么？->节点！最基本的元素，没有节点之后的都实现不了。接着实现什么？接口！按照功能将每一个接口都写好，以此来保证后续所写功能的连续性。最后，按照接口将每一个功能都实现即可！注意在编写的过程中也要反复的比对接口，及时修改接口的传参或者地址的传递。

       对此节点定义如下：

      结构体定义

typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

int 型 data 用于储存数据，结构体指针型 next 用于指向下一个节点。

       接口函数定义

//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
// 找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

   重点：


       此为对本版本单链表的不断优化后得到的接口。其中* phead 存储的是结构体类型的地址，即：他是用于改变结构体内的数据而设置的，* pos也是同理。而重点在于**pphead，他存储的结构体指针的地址，他是用于改变结构体指针的，即改变的是结构体的地址。x则是用于传参，输入需要添加的数据。


       你可能有个疑问，在此处为什么要使用**pphead呢？


       注意看在用到**pphead的函数，其中大多都是插入以及删除的操作，仔细看操作，例如：在插入时指针为空，而申请了新的节点，再将节点的地址替换原来的指针。删除了最后一个节点，将节点制空。即将节点替换为NULL。因此，使用**pphead是有必要的。

三、具体每个接口函数的实现

      1、打印

void SLTPrint(SLTNode* phead)//打印全部节点
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

 2、申请新的节点

SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
}

   3、尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
  SLTNode* newnode = BuySListNode(x);
  //pphead空指针，对地址进行操作
  if(!*pphead)
  *pphead = newnode;
  else//不为空，以下为对结构体进行操作
  {
    SLTNode* dit = *pphead;
    while (dit->next)
    {
      dit = dit->next;
    }
    dit->next = newnode;
  }
}

4、头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
  SLTNode* newnode = BuySListNode(x);
  if (!*pphead)//加这个干啥？
  *pphead = newnode;
  else
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
}

5、尾删

void SLTPopBack(SLTNode** pphead)//尾删
{
  //判空
  assert(pphead);
  assert(*pphead);//空链表不能删
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//多个节点
  {
    SLTNode* tail = *pphead,*ftail=*pphead;
    while (tail->next != NULL)
    {
      ftail = tail;
      tail = tail->next;
    }
    free(ftail->next);
    ftail->next = NULL;
  }
}

 6、头删

void SLTPopFront(SLTNode** pphead)//头删
{
  assert(*pphead);//判空
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}

  7、找节点（用于后续的插入以及删除操作）

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
  //判空
  assert(phead);
  //遍历找值
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

8、基于第7小点在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    /*SLTNode* newnode=BuySListNode(x);
    newnode->next = pos;
    *pphead=newnode;*/
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* pre = *pphead;
    /*while (pre != NULL)
    {
      if (pre->next == pos)
      {
        SLTNode* newnode = BuySListNode(x);
        newnode->next = pos;
        pre->next = newnode;
      }
    }*/
    while (pre->next != pos)
    {
      pre = pre->next;
    }
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos;
    pre->next = newnode;
  }
}

  9、基于第7小点在pos以后插入x

void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
  assert(pos);
  SLTNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}1. vo

10、基于第7小点删除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)//在头
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* dit = *pphead;
    while (dit->next != pos)
    {
      dit = dit->next;
    }
    dit->next = pos->next;
    free(pos);
    //pos=NULL//此为形参无用
  }
}

 11、基于第7小点删除pos的后一个位置

void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
  assert(pos);
  assert(pos->next);//检查pos是否为尾结点
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
  next = NULL;
}

 12、销毁链表，释放空间

void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
2.

四、总体代码

1、头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
// 找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

2、主体函数文件

#include"SList.h"
SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
}
void SLTPrint(SLTNode* phead)//打印全部节点
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
  SLTNode* newnode = BuySListNode(x);
  //pphead空指针，对地址进行操作
  if(!*pphead)
  *pphead = newnode;
  else//不为空，以下为对结构体进行操作
  {
    SLTNode* dit = *pphead;
    while (dit->next)
    {
      dit = dit->next;
    }
    dit->next = newnode;
  }
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
  SLTNode* newnode = BuySListNode(x);
  if (!*pphead)//加这个干啥？
  *pphead = newnode;
  else
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
}
void SLTPopBack(SLTNode** pphead)//尾删
{
  //判空
  assert(pphead);
  assert(*pphead);//空链表不能删
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//多个节点
  {
    SLTNode* tail = *pphead,*ftail=*pphead;
    while (tail->next != NULL)
    {
      ftail = tail;
      tail = tail->next;
    }
    free(ftail->next);
    ftail->next = NULL;
  }
}
void SLTPopFront(SLTNode** pphead)//头删
{
  assert(*pphead);//判空
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
  //判空
  assert(phead);
  //遍历找值
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    /*SLTNode* newnode=BuySListNode(x);
    newnode->next = pos;
    *pphead=newnode;*/
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* pre = *pphead;
    /*while (pre != NULL)
    {
      if (pre->next == pos)
      {
        SLTNode* newnode = BuySListNode(x);
        newnode->next = pos;
        pre->next = newnode;
      }
    }*/
    while (pre->next != pos)
    {
      pre = pre->next;
    }
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos;
    pre->next = newnode;
  }
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
  assert(pos);
  SLTNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)//在头
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* dit = *pphead;
    while (dit->next != pos)
    {
      dit = dit->next;
    }
    dit->next = pos->next;
    free(pos);
    //pos=NULL//此为形参无用
  }
}
void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
  assert(pos);
  assert(pos->next);//检查pos是否为尾结点
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
  next = NULL;
}
void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

3、测试用例

#include"SList.h"
void text()
{
  SLTNode* plist = NULL;
  SLTPushFront(&plist, 10);
  SLTPushFront(&plist, 20);
  SLTPushFront(&plist, 30);
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTNode* p = SLTFind(plist, 10);//把找到的地址给p
  SLTInsert(&plist, p, 100);
  SLTPrint(plist);
  SLTInsertAfter(p, 200);
  SLTPrint(plist);
  SLTErase(&plist, p);
  SLTPrint(plist);
  SLTNode* pp = SLTFind(plist, 100);
  SLTEraseAfter(pp);
  SLTPrint(plist);
  SLTDestroy(&plist);
}
int main()
{
  text();
  return 0;
}

   测试结果：




               感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！




文章标签：
C语言
存储
测试技术
关键词：
C语言数据结构
数据结构c语言
数据结构单链表
C语言单链表
数据结构C语言单链表
慕斯(˘▽˘)っ
目录
相关文章
土木林森
|
18天前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
28 1
XIAZHI
|
26天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
42 4
XIAZHI
|
26天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
39 4
XIAZHI
|
26天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
36 4
XIAZHI
|
26天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
44 4
XIAZHI
|
26天前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
34 4
XIAZHI
|
26天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
32 4
龙大吉
|
19天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
42 5
土木林森
|
18天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
47 1
XIAZHI
|
26天前
|
存储 机器学习/深度学习 算法
【趣学C语言和数据结构100例】61-65
本文介绍了五个关于C语言和数据结构的经典问题及其实现方法，涵盖查找链表共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及特定条件下的链表排序。每个问题通过具体的算法设计，不仅展示了链表操作的灵活性，还强调了效率优化的重要性。通过这些问题的探讨，读者可以深入理解链表的基本操作和高级应用，提升解决实际问题的能力。
XIAZHI
44 4