【数据结构】详解链表(二)——带头双向循环链表

简介: 【数据结构】详解链表(二)——带头双向循环链表

作者:一个喜欢猫咪的的程序员

专栏:《数据结构》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

目录

带头双向循环链表

List.h

List.c

Test.c


带头双向循环链表


本篇我们来介绍一个结构比较复杂的链表——带头双向循环链表

它的结构看上去十分复杂但代码实现这个链表确实很简单的。

如果对其中函数实现思想不太懂的话可以看看我的另外一篇博客:

http://t.csdn.cn/47qGs

http://t.csdn.cn/47qGs


List.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDateType;
typedef struct ListNode
{
  struct ListNode* prev;
  LTDateType date;
  struct ListNode* next;
}LTNode;
LTNode* BuyListNode(LTDateType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDateType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDateType x);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDateType x);
void LTInsert(LTNode* pos, LTDateType x);
void LTErase(LTNode* pos);
bool LTEmpty(LTNode*phead);
size_t LTSize(LTNode* phead);
void LTDestroy(LTNode* phead);


List.c

#include"List.h"
LTNode* BuyListNode(LTDateType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->date = x;
  node->next = NULL;
  node->prev = NULL;
  return node;
}
LTNode* LTInit()
{
  LTNode*phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void LTPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  /*LTNode* newnode = BuyListNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  phead->prev = newnode;
  newnode->next = phead;*/
  LTInsert(phead, x);
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  /*LTNode* tail = phead->prev;
  LTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);*/
  LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDateType x)
{
  /*LTNode* newnode = BuyListNode(x);
  LTNode* cur = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = cur;
  cur->prev = newnode;*/
  LTInsert(phead->next, x);
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
    printf("%d->", cur->date);
    cur = cur->next;
  }
  printf("\n");
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  //LTNode* first = phead->next;
  //LTNode* second = first->next;
  //phead->next = second;
  //second->prev = phead;
  //free(first);
  LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->date == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}
void LTInsert(LTNode* pos, LTDateType x)
{
  assert(pos);
  LTNode* newnode = BuyListNode(x);
  LTNode* front = pos->prev;
  front->next = newnode;
  newnode->prev = front;
  pos->prev = newnode;
  newnode->next = pos;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  prev->next = next;
  next->prev = prev;
}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead == phead->next;
}
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 LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
  //phead = NULL;
}

Test.c

#include"List.h"
void test1()
{
  LTNode* phead = LTInit();
  LTPushBack(phead,1);
  LTPushBack(phead, 2);
  LTPushBack(phead, 3);
  LTPushBack(phead, 4);
  LTPrint(phead);
  LTPopBack(phead);
  //LTPopBack(phead);
  //LTPopBack(phead);
  /*LTPopBack(phead);*/
  LTPrint(phead);
  LTPushFront(phead,10);
  LTPrint(phead);
  LTPopFront(phead);
  LTPrint(phead);
}
void test2()
{
  LTNode* phead = LTInit();
  LTPushBack(phead, 1);
  LTPushBack(phead, 2);
  LTPushBack(phead, 3);
  LTPushBack(phead, 4);
  LTPrint(phead);
  LTNode* pos = LTFind(phead, 3);
  if (pos)
  {
    pos->date = pos->date * 10;
    LTPrint(phead);
  }
  LTPushFront(phead, 10);
  LTPrint(phead);
}
int main()
{
  test2();
  return 0;
}
相关文章
|
3月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
86 4
|
24天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
24天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
88 25
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
46 5
|
2月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
103 5
|
3月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
180 4
|
3月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
75 0
|
3月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
134 0