AI 助理
备案控制台
开发者社区 云计算 文章 正文

基于结点的数据结构——链表（单链表&&双向循环链表）| 附完整源码 | C语言版（下）

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

0.png

正文

4. 带头双向循环链表的实现


带头双向循环链表看似结构复杂，其实在写代码时你会感到很轻松。其关键就在于它的头结点不一般。此处的头结点不存储有效数据。

111.png


4.1结点结构的定义


typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;//指向前一个结点
  struct ListNode* next;//指向后一个结点
}LTNode;

既然是双向循环链表，那就得要求每个结点既保存下一个结点的地址，又要保存上一个结点的地址。结构中，prev指向前一个结点，next指向后一个结点。


4.2函数接口的实现


//申请一个结点
LTNode* BuyListNode(LTDataType data);
//初始化头结点
LTNode* LTInit();
//释放申请的内存
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType data);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType data);
//头删
void LTPopFront(LTNode* phead);
//查找data
LTNode* LTFind(LTNode* phead, LTDataType data);
//在pos位置前插入
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data);
//删除pos位置
void LTErase(LTNode* phead, LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//统计链表中数据的个数
size_t LTSize(LTNode* phead);
//打印链表存储的数据
void LTPrint(LTNode* phead);

同样的，由于代码过长，为了避免影响阅读体验，我将完整源码置于文章末尾。带头双向循环链表的各个函数实现都比不带头的单链表简单很多。因此学会了之前单链表的实现，双向链表的实现自然轻松无比。这里就不做赘述。


5.两种链表的差异


①尾插与尾删的时间复杂度


对于单链表而言，尾插与尾删都是它的劣势。因为计算机无法直接访问到链表的尾结点，必须遍历完整个链表才能找到尾结点。所以单链表的尾插与尾删都为O(N)。


对于带头双向循环链表，找尾是极其方便的，因为尾结点就在头结点的前一个，可以一步就访问到。所以，带头双向循环链表的尾插与尾删都为O(1)。


②头插与头删的时间复杂度


两种链表头插与头删都为O(1)。对于链表这种数据结构而言，头插与头删都是其优势。上一章中提到顺序表的尾插与尾删效率极高，但是头插与头删却比较劣势。而链表正好相反，头插与头删效率很高。因此面对不同的场景，要学会使用合适的数据结构。


③函数形参为何一个是二级指针，一个是一级指针？


单链表，我们需要对phead的值做修改。那么就得利用phead的指针。而phead本身就是一个指针，所以函数的形参为pphead的二级指针。

双向循环链表，并不需要对phead做修改，而只是需要访问它prev和next所指向的结点，所以只用一级指针即可。


完整源码


无头单向非循环链表


SList.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
//申请一个结点
SLTNode* BuySLTNode(SLTDataType data);
//创建一个链表，包含数据为0~n
SLTNode* CreateSList(int n);
//释放内存
void SLTDestroy(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType data);
//尾删
void SLTPopBack(SLTNode** pphead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType data);
//头删
void SLTPopFront(SLTNode** pphead);
//查找data的结点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType data);
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data);
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType data);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//打印链表内容
void SLTPrint(SLTNode* phead);


SList.c


#define _CRT_SECURE_NO_DEPRECATE 1
#include"SList.h"
SLTNode* BuySLTNode(SLTDataType data)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  //检查是否申请成功
  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //对newNode进行初始化
  newNode->data = data;
  newNode->next = NULL;
  //返回申请成功的结点
  return newNode;
}
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL;
  SLTNode* ptail = NULL;
  for (int i = 0; i < n; i++)
  {
    SLTNode* newNode = BuySLTNode(i);
    //若为第一个插入，则分情况处理
    if (phead == NULL)
    {
      phead = ptail = newNode;
    }
    else
    {
      ptail->next = newNode;
      ptail = newNode;
    }
  }
  return phead;
}
void SLTDestroy(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* cur = *pphead;
  //cur判断何时结束
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
void SLTPushBack(SLTNode** pphead, SLTDataType data)
{
  SLTNode* newNode = BuySLTNode(data);
  //若为第一次插入，则分情况处理
  if (*pphead==NULL)
  {
    *pphead = newNode;
    return;
  }
  //找尾
  SLTNode* tail = *pphead;
  while(tail->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾插
  tail->next = newNode;
}
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //分情况处理
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //找尾
  SLTNode* tail = *pphead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾删
  free(tail->next);
  tail->next = NULL;
}
void SLTPushFront(SLTNode** pphead, SLTDataType data)
{
  SLTNode* newNode = BuySLTNode(data);
  //进行头插
  newNode->next = *pphead;
  *pphead = newNode;
}
void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  //进行头删
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
SLTNode* SLTFind(SLTNode** pphead, SLTDataType data)
{
  assert(*pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    //找到了，返回cur
    if (cur->data == data)
    {
      return cur;
    }
    cur = cur->next;
  }
  //没找到，返回NULL
  return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data)
{
  assert(pos);
  SLTNode* newNode = BuySLTNode(data);
  //若pos恰好是phead，相当于进行头插
  if (pos == *pphead)
  {
    SLTPushFront(pphead, data);
    return;
  }
  //找pos前一个指针
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //找到了，进行插入
  prev->next = newNode;
  newNode->next = pos;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType data)
{
  assert(pos);
  SLTNode* newNode = BuySLTNode(data);
  SLTNode* next = pos->next;
  pos->next = newNode;
  newNode->next = next;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  //若pos恰好就是phead，则相当于头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
    return;
  }
  //找pos前一个结点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //找到了，进行删除
  prev->next = pos->next;
  free(pos);
  pos = NULL;
}
void SLTPrint(SLTNode* phead)
{
  assert(phead);
  SLTNode* cur = phead;
  //cur控制何时结束
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}


test.c


#define _CRT_SECURE_NO_DEPRECATE 1
#include"SList.h"
void test()
{
  SLTNode* phead = CreateSList(10);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPrint(phead);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPrint(phead);
  SLTNode* pos = SLTFind(&phead, 3);
  SLTInsert(&phead, pos, 300);
  SLTInsertAfter(pos, 30);
  SLTPrint(phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPrint(phead);
  SLTDestroy(&phead);
}
int main()
{
  test();
  return 0;
}


带头双向循环链表


List.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;//指向前一个结点
  struct ListNode* next;//指向后一个结点
}LTNode;
//申请一个结点
LTNode* BuyListNode(LTDataType data);
//初始化头结点
LTNode* LTInit();
//释放申请的内存
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType data);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType data);
//头删
void LTPopFront(LTNode* phead);
//查找data
LTNode* LTFind(LTNode* phead, LTDataType data);
//在pos位置前插入
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data);
//删除pos位置
void LTErase(LTNode* phead, LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//统计链表中数据的个数
size_t LTSize(LTNode* phead);
//打印链表存储的数据
void LTPrint(LTNode* phead);


List.c


#define _CRT_SECURE_NO_DEPRECATE 1
#include"List.h"
LTNode* BuyListNode(LTDataType data)
{
  LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = NULL;
  return newNode;
}
LTNode* LTInit()
{
  LTNode* phead = BuyListNode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}
void LTPushBack(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  LTNode* tail = phead->prev;
  newNode->next = phead;
  newNode->prev = tail;
  tail->next = newNode;
  phead->prev = newNode;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  tail->prev->next = phead;
  phead->prev = tail->prev;
  free(tail);
}
void LTPushFront(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  newNode->next = phead->next;
  phead->next->prev = newNode;
  phead->next = newNode;
  newNode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* cur = phead->next;
  phead->next = cur->next;
  cur->next->prev = phead;
  free(cur);
}
LTNode* LTFind(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data==data)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  pos->prev->next = newNode;
  newNode->prev = pos->prev;
  newNode->next = pos;
  pos->prev = newNode;
}
void LTErase(LTNode* phead,LTNode* pos)
{
  assert(phead);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  if (phead->next == phead)
  {
    return true;
  }
  return false;
}
size_t LTSize(LTNode* phead)
{
  assert(phead);
  size_t size = 0;
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}


test.c


#define _CRT_SECURE_NO_DEPRECATE 1
#include"List.h"
void test()
{
  LTNode* phead = LTInit();
  LTPushBack(phead, 2);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPrint(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPrint(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPrint(phead);
  LTNode* pos = LTFind(phead, 2);
  LTInsert(phead, pos, 200);
  LTInsert(phead, pos, 200);
  LTInsert(phead, pos, 200);
  LTPrint(phead);
  LTErase(phead, pos);
  LTPrint(phead);
  LTDestroy(phead);
}
int main()
{
  test();
  return 0;
}


文章标签：
存储
关键词：
数据结构源码
C语言数据结构
数据结构链表
数据结构c语言
C语言链表
花想云
目录
相关文章
啦啦啦191
|
19天前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架，涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口，逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变，包括数组+链表+红黑树优化，以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例，展示集合框架的应用价值，助你全面掌握相关知识，轻松应对面试与开发需求。
啦啦啦191
76 3
ephemerals__
|
3月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现（附源码）
在深入探讨了AVL树的原理和实现后，我们不难发现，这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题，还通过其独特的平衡机制，确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
ephemerals__
243 19
ephemerals__
|
3月前
|
数据库 C++
【数据结构进阶】红黑树超详解 + 实现（附源码）
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树，通过节点着色（红/黑）和特定规则，确保树的高度接近平衡，从而实现高效的插入、删除和查找操作。相比AVL树，红黑树允许一定程度的不平衡，减少了旋转调整次数，提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整（变色与旋转）、查找逻辑以及合法性检查，并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用，其设计兼顾效率与复杂性的平衡。
ephemerals__
414 3
Cyan_RA9
|
4月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
135 29
Cyan_RA9
|
4月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
184 25
羑悻的小杀马特
|
4月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
124 13
羑悻的小杀马特
|
5月前
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
83 13
RossyYan
|
5月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
268 5
三三是该溜子
|
6月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
140 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
RossyYan
|
5月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定（头歌实践教学平台习题）【合集】
本内容介绍了编写一个判断素数的子函数的任务，涵盖循环控制与跳转语句、算术运算符（%）、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码，测试说明提供了输入输出示例，最后给出通关代码和测试结果。 任务核心：编写判断素数的子函数并在主函数中调用，涉及循环结构和条件判断。
RossyYan
296 23