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

简介: 基于结点的数据结构——链表(单链表&&双向循环链表)| 附完整源码 | 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;
}


目录
打赏
0
0
0
0
1
分享
相关文章
|
8月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
767 9
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
131 3
|
4月前
|
【数据结构进阶】红黑树超详解 + 实现(附源码)
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树,通过节点着色(红/黑)和特定规则,确保树的高度接近平衡,从而实现高效的插入、删除和查找操作。相比AVL树,红黑树允许一定程度的不平衡,减少了旋转调整次数,提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整(变色与旋转)、查找逻辑以及合法性检查,并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用,其设计兼顾效率与复杂性的平衡。
571 3
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
324 19
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
2274 6
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
197 5
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
86 1
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
307 7
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
304 8
|
8月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
557 8
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问