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

手把手教你实现链表—单链表（数据结构C语言实现3）

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

本节目标

1.链表表示和实现（单链表+双向链表）

2.链表的常见OJ题

3.顺序表和链表的区别和联系


链表表示和实现（单链表+双向链表）

顺序表的问题及思考问题：


中间/头部的插入删除，时间复杂度为O(N)

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

链表的概念

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


逻辑结构

image.png

想必大家看的都是链表的逻辑结构，其实真实并不存在连接两个链表的箭头，为了更好理解罢了。箭头代表前面的节点存了，后面节点的指针。

物理结构

物理结构就是真正的结构，便于初学者学习!

image.png

是不是突然对链表有了更深刻的理解！


单链表的实现

// 1、无头+单向+非循环链表增删查改实现
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

链表节点创建

链表的创建也是用结构体创建。


//类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType date;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;
// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
   newnode->date = x;
   newnode->next = NULL;
   return newnode;
}
// 打印
void SListPrint(SLTNode* phead)
{
   while (phead != NULL)
   {
    printf("%d ", phead->date);
    phead = phead->next;
   }
   printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
   if (*pphead == NULL)
   {
    *pphead = BuySListNode(x);
   }
   else
   {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = BuySListNode(x);
   }
}
//头插接口测试
void TestSList2()
{
   SLTNode* plist = NULL;
   SListPushFront(&plist, 1);
   SListPushFront(&plist, 2);
   SListPushFront(&plist, 3);
   SListPushFront(&plist, 4);
   SListPushFront(&plist, 5);
   SListPushFront(&plist, 6);
   SListPrint(plist);
}

image.png


//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
   if (!*pphead)
   {
    *pphead= BuySListNode(x);
   }
   else
   {
    SLTNode* first = BuySListNode(x);
    first->next = *pphead;
    *pphead = first;
   }
}
//头插接口测试
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
}

image.png

//头删
void SListPopFront(SLTNode** pphead)
{
  if (!*pphead)
  {
  return;
  } 
  else
  {
  *pphead = (*pphead)->next;
  }
}
//头删接口测试
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
}

image.png

//尾删
void SListPopBack(SLTNode** pphead)
{
  //1头结点为空
  //2只有一个节点
  //3多个节点
  if (*pphead == NULL)
  {
  return;
  }
  else if ((*pphead)->next ==NULL)
  {
  *pphead = NULL;
  free(*pphead);
  }
  else
  {
  SLTNode* tail = *pphead;
  SLTNode* ret = *pphead;
  while (tail->next)
  {
    ret = tail;
    tail = tail->next;
  }
  tail = NULL;
  ret->next = NULL;
  free(tail);
  }
}
//尾删接口测试
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPrint(plist);
}

image.png


//查找节点x位置并返回节点位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  if (phead == NULL)  //节点为空
  {
  return NULL;
  }
  else
  {
  SLTNode *ret= phead;
  while (ret) 
  {
    if (ret->date == x)    //找到了
    {
    return ret;
    }
    ret = ret->next;
  }
  return NULL;           //找不到
  }
}
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
  return;
  }
  else if(*pphead==pos)
  {
  *pphead = newnode;
  newnode->next = pos;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = newnode;
  newnode->next = pos;
  }
}
//任意位置查找插入测试
void TestSList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist,3);
  if (pos)
  {
  SListInsert(&plist,pos,0);
  }
  SListPrint(plist);
}

image.png

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  if (*pphead==NULL)
  {
  return;
  }
  else if (*pphead == pos)
  {
  *pphead = NULL;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = pos->next;
  pos = NULL;
  free(pos);
  }
}
//任意位置修改接口测试
void TestList6()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPushBack(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
  SListErase(&plist, pos);
  }
  SListPrint(plist);
}

image.png

文章标签：
C语言
存储
关键词：
数据结构c语言
数据结构链表
链表c语言
C语言数据结构
数据结构单链表
bug郭
目录
相关文章
ephemerals__
|
25天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
116 9
龙大吉
|
3天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
22 5
ephemerals__
|
24天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
62 16
ephemerals__
|
24天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
80 8
ephemerals__
|
26天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
51 4
ephemerals__
|
28天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
60 3
肾透侧视攻城狮
|
28天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
22 2
肾透侧视攻城狮
|
28天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
32 2
ephemerals__
|
26天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
41 0
白子寰
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
白子寰
24 0