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

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

2023-04-18 105
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 基于结点的数据结构——链表（单链表&&双向循环链表）| 附完整源码 | 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语言数据结构
花想云
目录
相关文章
Codelinghu
|
19天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
Codelinghu
52 1
ephemerals__
|
1天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
10 3
java冯坚持
|
20天前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
18 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
那年春天
|
1天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念，通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中，理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
那年春天
5 1
白子寰
|
14天前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
19 1
Dylaniou
|
16天前
|
Java C++ 索引
让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表，适合频繁的插入和删除操作，但按索引访问元素效率较低。`ArrayList` 基于动态数组，支持快速随机访问，但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口，`LinkedList` 还额外实现了 `Deque` 接口，提供了更多队列操作。
Dylaniou
19 3
杀死一只知更鸟debug
|
2月前
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
26 1
java数据结构，线性表链式存储（单链表）的实现
石小浪♪
|
21天前
|
存储 C语言
C语言单链表实现
一个用C语言编写的简单学生信息管理系统，该系统具备信息输入、成绩计算、排序、删除、查找、修改、保存和读取文件等功能。
石小浪♪
19 0
C语言单链表实现
努力学习的小廉
|
23天前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
21 2
徐霞客320
|
25天前
|
存储
数据结构2——单链表
数据结构2——单链表
徐霞客320
30 1

热门文章

最新文章

  • 1
    数据结构复习笔记(6)
  • 2
    Hadoop-No.13之数据源系统以及数据结构
  • 3
    数据结构~在页面上渲染树型结构
  • 4
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 5
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 6
    数据结构学习笔记【持续更新】
  • 7
    基于OHCI的USB主机 —— UFI数据结构2
  • 8
    R语言学习笔记（一）数据结构
  • 9
    算法导论第十四章 数据结构的扩张
  • 10
    初学python数据结构-切片
  • 1
    【数据结构】深入浅出理解链表中二级指针的应用
    99
  • 2
    线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
    74
  • 3
    【链表】还不会用C++实现链表？一文教会你各种链表的实现
    256
  • 4
    【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
    129
  • 5
    链表的实现（文末附完整代码）
    48
  • 6
    C++链表解析：从基础原理到高级应用，全面掌握链表的使用
    510
  • 7
    【数据结构算法（二）】链表总结
    45
  • 8
    《剑指offer》——合并两个排序的链表
    50
  • 9
    《剑指offer》——从尾到头打印链表
    44
  • 10
    【移除链表元素】LeetCode第203题讲解
    50

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月