一篇解单链表(0基础看)(C语言)《数据结构与算法》

简介: 一篇解单链表(0基础看)(C语言)《数据结构与算法》

链表


1. 链表的概念及结构


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


image.png


2. 链表的分类


2.1. 单向或者双向


image.png


image.png


1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。


3. 效果展示图


image.png


4. 接口实现


本篇幅是无头+单向+非循环链表增删查改实现,下一篇就是带头+双向+循环链表的实现哈。


对于接口的实现我们首先是要知道要实现什么,本文是对于链表的基本使用,让大家初步了解链表,所以就只实现顺序表的增删查改,还有特定位置前插入和删除特定位置值等当然代码也不一定要作者这么写,这里只是提供一种思路,废话不多说,看代码。  


有什么不懂的欢迎到评论区交流哈,当然也可以私信作者。


4.01. 本文章要实现的接口


image.png


image.png


image.png


image.png


image.png


image.png


image.png


image.png


image.png


image.png


image.png


5. 源代码


5.1. test.c

#include"SList.h"
int main()
{
  //直接初始化next为NULL就可以了
  SListNode* plist = NULL;
  //头插 1 2
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 6);
  SListPrint(&plist);
  //尾插 3 4 5
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(&plist);
  //头删一个数
  SListPopFront(&plist);
  SListPrint(&plist);
  //尾删两个个数
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPrint(&plist);
  //找 3 4 1
  SListFind(&plist, 3);
  SListFind(&plist, 4);
  SListFind(&plist, 1);
  //在 1 前面插入 8
  SListNode* pos=SListFind(&plist, 1);
  SListInsert(&plist, pos, 8);
  SListPrint(&plist);
  //删除 2  3
  pos = SListFind(&plist, 2);
  SListErase(&plist, pos);
  SListPrint(&plist);
  pos = SListFind(&plist, 3);
  SListErase(&plist, pos);
  SListPrint(&plist);
  //销毁链表
  SListDestory(&plist);
  return 0;
}


5.2. SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType date;
  struct SListNode* next;
}SListNode;
//销毁
void SListDestory(SListNode** pphead);
//打印
void SListPrint(SListNode** pphead);
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
//查找某个值
SListNode* SListFind(SListNode** pphead, SLTDateType x);
//头插
void SListPushBack(SListNode** pphead,SLTDateType x);
//尾插
void SListPushFront(SListNode** pphead, SLTDateType x);
//头删
void SListPopFront(SListNode** pphead);
//尾删
void SListPopBack(SListNode** pphead);
//在pos位置之前插入某个值
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
//删除pos位置的值
void SListErase(SListNode** pphead,SListNode* pos);
//找到某个值并改变为某个值


5.3. SList.c

#include"SList.h"
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  (newnode)->next = NULL;
  newnode->date = x;
  return newnode;
}
//头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
  SListNode* newnode=BuySListNode(x);
  if (!(*pphead))
  {
    *pphead = newnode;
  }
  else
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
}
//打印
void SListPrint(SListNode** pphead)
{
  SListNode* cur = *pphead;
  while (cur)
  {
    //注意这里打印的 -> 和下面的 NULL 只是为了打印出来更像是链表
    printf("%d->", cur->date);
    cur = cur->next;
  }
  printf("NULL\n");
}
//尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
  SListNode* tail = *pphead;
  SListNode* newnode=BuySListNode(x);
  if (!tail)
  {
    tail = newnode;
  }
  else
  {
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
//头删
void SListPopFront(SListNode** pphead)
{
  assert(*pphead);
  SListNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
//尾删
void SListPopBack(SListNode** pphead)
{
  assert(*pphead);
  SListNode* tail = *pphead;
  SListNode* prev = *pphead;
  if (prev->next == NULL)  //一个节点的时候
  {
    //注意这里free是*pphead
    free(*pphead);
    *pphead = NULL;
    return;
  }
  else
  {
    //多个节点的时候(此时最少两个节点)
    tail = tail->next;
    while (tail->next)
    {
      tail = tail->next;
      prev = prev->next;
    }
    //这里只需要free最后面的一个空间
    free(tail);
    tail = NULL;
    prev->next = NULL;
  }
}
//查找某个值
SListNode* SListFind(SListNode** pphead, SLTDateType x)
{
  assert(*pphead);
  SListNode* cur = *pphead;
  while (cur != NULL)
  {
    if (cur->date == x)
    {
      printf("找到啦!\n");
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  printf("没有找到此值\n");
  return NULL;
}
//在pos位置之前插入某个值
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else 
  {
    SListNode* prev = *pphead;
    SListNode* newnode = BuySListNode(x);
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}
//删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(*pphead);
  if (pos == *pphead)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
//销毁
void SListDestory(SListNode** pphead)
{
  assert(*pphead);
  SListNode* pos = *pphead;
  SListNode* cur = *pphead;
  while (pos->next == NULL)
  {
    if (cur->next != NULL)
    {
      cur = cur->next;
    }
    else
    {
      free(cur);
      cur = NULL;
      cur = *pphead;
    }
  }
  free(pos);
  pos = NULL;
}


今天的内容就到这里了哈!!!

要是认为作者有一点帮助你的话!

就来一个点赞加关注吧!!!当然订阅是更是求之不得!

赠人玫瑰,手有余香=。=!

最后的最后感谢大家的观看!!!

你们的支持是作者写作的最大动力!!!

下期见哈!!!

相关文章
|
10月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
405 1
|
10月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
146 4
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
100 0
|
6月前
|
存储 监控 算法
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
103 5
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
7月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
110 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
9月前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
10月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
276 5
|
10月前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
277 2