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

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

2023-04-18 106
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 基于结点的数据结构——链表（单链表&&双向循环链表）| 附完整源码 | 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语言
数据结构链表
花想云
目录
相关文章
ephemerals__
|
27天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
123 9
ephemerals__
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
ephemerals__
|
26天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
87 8
ephemerals__
|
29天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
42 0
pqo7bvdsfj67q
|
C语言
c语言打字母游戏源码
c语言打字母游戏源码
pqo7bvdsfj67q
136 0
白子寰
|
2月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
36 3
LuckiBit
|
2天前
|
存储 缓存 算法
【C语言】内存管理函数详细讲解
在C语言编程中，内存管理是至关重要的。动态内存分配函数允许程序在运行时请求和释放内存，这对于处理不确定大小的数据结构至关重要。以下是C语言内存管理函数的详细讲解，包括每个函数的功能、标准格式、示例代码、代码解释及其输出。
LuckiBit
24 6
Skyund
|
19天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
31 6
ephemerals__
|
2月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
43 10
c的前世今生
|
1月前
|
存储 算法 程序员
C语言：库函数
C语言的库函数是预定义的函数，用于执行常见的编程任务，如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作，提高开发效率。C标准库提供了丰富的函数，满足各种需求。
c的前世今生
33 1