一篇解双链表(0基础看)(C语言)《数据结构与算法》

简介: 一篇解双链表(0基础看)(C语言)《数据结构与算法》

上文我们讲到了链表最重要的两个分类,一个是单向不带头不循环,本篇文章就讲另一个重要的带头双向循环链表哈,废话不多说,直接看代码。


带头双向循环链表


1. 概念


image.png


带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都

是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带

来很多优势,实现反而简单了,后面我们代码实现了就知道了。

这里我们来慢慢揭晓上文说到的实现更简单,以及单链表的缺点。缺点就直接说了,我们可以很直观得发现单链表的两个很大的缺点,一个是尾插尾删等都是需要遍历也就是说时间复杂度是O(N),但是双链表对应的都是O(1),效率之高。另一个缺点就是单链表不能找到自己的上一个节点,这都是很大的缺陷。然后我们接着看双链表实现的优势。  


2. 效果展示图


image.png


3. 接口实现


还是老话,对于接口的实现我们首先是要知道要实现什么,本文是对于双链表的基本使用,所以就只实现顺序表的增删查改,还有特定位置前插入删除特定位置值等当然代码也不一定要作者这么写,这里只是提供一种思路,废话不多说,看代码。  


3.01. 本文章要实现的接口


image.png


image.png


这是命名是ListNode是与c++对应的,大家也可以和单链表SListNode对应取名DListnode,但是作者为了养成一个好的习惯就取名为了ListNode哈。


3.03. 双链表的初始化


image.png



注意这里初始化是自己指向自己,因为是循环,然后本篇文章不用二级指针(不用传地址),这里就用了一个返回值。


3.04. 打印链表


image.png


3.05. 动态申请一个节点


image.png


image.png


image.png


image.png


image.png


image.png

image.png


image.png


image.png


总结

我们可以发现对于带头双向循环链表的实现不需要像单链表那样要去判断没有或者有一个节点的情况,结构非常之完美,可以利用头结点进行各种变化,实现也非常简单,而且也不用传地址。


这里要再解释一下为什么可以不传地址,因为我们的头没有改变,不需要改变头,这个改变指的是我们一开始传的参数plist,他是一直指向我们的头的,是指向没有变,内容可以改变,也就是说plist的前驱prev和后继next的指向和date是可以变的,这个理解很重要!


4. 源代码


test.c

#include"List.h"
int main()
{
  printf("初始化\n");
  ListNode* plist = ListInit();
  printf("头插 1 2 3 并打印\n");
  ListPushFront(plist, 1);
  ListPushFront(plist, 2);
  ListPushFront(plist, 3);
  ListPrint(plist);
  printf("尾插4 5 6 并打印\n");
  ListPushBack(plist, 4);
  ListPushBack(plist, 5);
  ListPushBack(plist, 6);
  ListPrint(plist);
  printf("头删并打印\n");
  ListPopFront(plist);
  ListPrint(plist);
  printf("尾删并打印\n");
  ListPopBack(plist);
  ListPrint(plist);
  printf("1前插入3并打印\n");
  ListNode* pos = ListFind(plist, 1);
  ListInsert(plist, pos, 3);
  ListPrint(plist);
  printf("2前插入8并打印\n");
  pos = ListFind(plist, 2);
  ListInsert(plist, pos, 8);
  ListPrint(plist);
  printf("删除4并打印\n");
  pos = ListFind(plist, 4);
  ListErase(plist, pos);
  ListPrint(plist);
  printf("把1改成9并打印\n");
  ListChange(plist, 1, 9);
  ListPrint(plist);
  printf("销毁链表\n");
  ListDestory(plist);
  return 0;
}


List.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ListDateType;
typedef struct ListNode
{
  struct ListNode* prev;
  struct ListNode* next;
  ListDateType date;
}ListNode;
//增删查改
//初始化
ListNode* ListInit();
//销毁
void ListDestory(ListNode* phead);
//得到一个节点
ListNode* BuyListNode(ListDateType x);
//打印
void ListPrint(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, ListDateType x);
//尾插
void ListPushBack(ListNode* phead, ListDateType x);
//头删
void ListPopFront(ListNode* phead);
//尾删
void ListPopBack(ListNode* phead);
//查某个值,返回地址
ListNode* ListFind(ListNode* phead, ListDateType x);
//改某个值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination);
//某个位置前插入数据
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//删除某个位置数据
void ListErase(ListNode* phead, ListNode* pos);


List.c


#include"List.h"
//初始化
ListNode* ListInit()
{
  ListNode* phead = BuyListNode(0);
  phead->prev = phead;
  phead->next = phead;
  phead->date = 0;
  return phead;
}
//得到一个节点
ListNode* BuyListNode(ListDateType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  newnode->prev = NULL;
  newnode->next = NULL;
  newnode->date = x;
  return newnode;
}
//头插
void ListPushFront(ListNode* phead, ListDateType x)
{
  assert(phead);
  ListNode* newnode = BuyListNode(x);
  ListNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = first;
  first->prev = newnode;
}
//尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
  assert(phead);
  ListNode* tail = phead->prev;
  ListNode* newnode = BuyListNode(x);
  phead->prev = newnode;
  newnode->next=phead;
  tail->next = newnode;
  newnode->prev = tail;
}
//打印
void ListPrint(ListNode* phead)
{
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->date);
    cur = cur->next;
  }
  printf("\n");
}
//头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  //别把头删了
  assert(phead->next != phead);
  ListNode* first = phead->next;
  phead->next = first->next;
  first->next->prev = phead;
  free(first);
  first = NULL;
}
//尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  //别把头删了
  assert(phead->next != phead);
  ListNode* tail = phead->prev;
  ListNode* prev = tail->prev;
  prev->next = phead;
  phead->prev = prev;
  free(tail);
  tail = NULL;
}
//查某个值,返回地址
ListNode* ListFind(ListNode* phead, ListDateType x) 
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->date == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}
//某个位置前插入数据   
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
  assert(phead);
  ListNode* newnode = BuyListNode(x);
  ListNode* prev = pos->prev;
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
//删除某个位置数据
void ListErase(ListNode* phead, ListNode* pos)
{
  assert(phead);
  //别把头删了
  assert(phead->next != phead);
  ListNode* prev = pos->prev;
  ListNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
  pos = NULL;
}
//改某个值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination)
{
  assert(phead);
  ListNode* pos = ListFind(phead, source);
  pos->date = destination;
}
//销毁
void ListDestory(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  ListNode* tail = cur->next;
  while (tail != phead)
  {
    free(cur);
    cur = NULL;
    cur = tail;
    tail = tail->next;
  }
  free(cur);
  cur = NULL;
  if (cur != tail)
  {
    free(tail);
    tail = NULL;
  }
}

今天的内容就到这里了哈!!!

要是认为作者有一点帮助你的话!

就来一个点赞加关注吧!!!当然订阅是更是求之不得!

赠人玫瑰,手有余香=。=!

最后的最后感谢大家的观看!!!

你们的支持是作者写作的最大动力!!!

下期见哈!!!

相关文章
|
10月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
405 1
|
10月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
146 4
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
100 0
|
6月前
|
存储 监控 算法
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
103 5
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
7月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
110 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
9月前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
10月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
276 5
|
10月前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
277 2

热门文章

最新文章