前言：
对于链表，上一篇的单链表解决了顺序表的一部分缺陷，但并没有彻底的解决顺序表的问题，比如在进行单链表尾插尾删的时候还是需要进行遍历找尾，并没有达到全部的O(1)，并且在头插的时候还要分情况来考虑，比如传入为空指针和不是空指针时候还要分情况考虑，对于指针的改变还要传二级指针，这对于一部分人来说并不熟悉，所以！！！今天看完这篇文章，掌握带双向循环数据表，让我们不再害怕链表的增删插改😎😎
💞 💞 欢迎来到小马学习代码博客！！！！
思维导图：
目录
～带头双向循环链表我们不要被他的结构图所吓到，只要我么深入理解他的原理，你会发现它的代码实现起来比单链表还要简单。
1.2.1 对于带头双向循环链表，要知道它的结构是比较复杂的，但是他的代码实现是比较简单的，所以，对于代码实现前，我想先讲述一下带头双向循环链表：对于带头双向循环链表我们先一步步理解，👉带头的意思就是在插入之前我们先初始化一个结构体，他并不是用来存储数据，而是保证链表有一个头节点，就可以减少讨论（当传入指针为空时，当传入指针不为空时），👉双向是指我们的结构体中存量结构体指针，一个是指向下一个，另一个是指向他的前一个，这样就保证在寻找的时候找不到前一个的位置。 👉循环是指在尾节点我们并不让他指向空指针，而是让他指向头节点，而头节点的前一个也不让他指向空指针，而是让他指向尾节点，这样就会达成一个循环的作用，他的好处就是在于我们们寻找尾节点的时候就不用遍历了，而是通过找头节点的前一个就能找到尾节点，从而达到时间复杂度为O(1)来完成尾插和尾删！
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>💖 这里是害怕有的小伙伴有的头文件并不知道^ _ ^ 。
LTNode* ListInit() //返回结构体指针
{
LTNode*guard=(LTNode*)malloc(sizeof(LTNode)); //这里就像定义一个哨兵，也就是头节点，就不用再担心头节点是不是NULL了
if(guard==NULL) //确保能够正常扩容
{
perror("ListNodeInit");
}
guard->next=guard; //头节点的下一个先指向自己
guard->prev=guard; //头节点的上一个也先指向自己
return guard;
}void ListNodePrint(LTNode* phead)
{
assert(phead); //保证传入的不是空指针
LTNode* cur =phead->next; //定一个结构体指针进行遍历打印
printf("guard<=>"); //这里是为了打印效果好看一点
while(cur!=phead)
{
printf("%d<=>",cur->data);
cur=cur->next;
}
printf("\n");
}LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode=(LTNode*)malloc(sizeof(ListNode)); //节点申请空间
if(newnode==NULL)
{
perror("BuyListNode");
}
newnode->data=x; //节点所带的值
newnode->prev=NULL;
newnode->next=NULL;
return newnode;
}bool ListEmpty(LTNode*phead)
{
assert(phead);
return phead->next==phead; //如果头和头的下一个指向同一个则返回真，证明只有一个哨兵
}void ListDestroy(LTNode*phead)
{
LTNode*cur=phead->next; //定义一个结构体指针进行遍历销毁
while(cur!=phead)
{
LTNode*next=cur->next;
free(cur);
cur=next;
}
free(phead); //最后释放头节点
}void ListPushFront(LTNode*phead,LTDataType x)
{
assert(phead);
LTNode* newnode=BuyListNode(x); //先定义一个节点进行头插
newnode->next=phead->next; //这里要考虑顺序问题，不然很容易出错，先让定义的next指向哨兵的下一个，然后哨兵下一个的prev指向我们新的节点
//然后让我们我们哨兵的next指向新节点，新节点的prev指向哨兵， 这里如果不理解的可以画一下图
//或者我么先定义一个节点把哨兵的下一个进行保存这里就不用考虑先后顺序了，大家可以试一试
phead->next->prev=newnode;
phead->next=newnode;
newnode->prev=phead;
}void ListPushBack(LTNode*phead,LTDataType x)
{
assert(phead);
LTNode* newnode=BuyListNode(x); //定义一个新节点
LTNode* tail=phead->prev; //找到尾节点
tail->next=newnode; //然后就是交换结构体里面的next prev指向的位置来实现插入。头插我已经讲述过程了，主要是大家尝试一下画画图
newnode->prev=tail;
newnode->next=phead;
phead->prev=newnode;
}void ListPopFront(LTNode*phead)
{
assert(phead);
assert(!ListEmpty(phead)); //这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
LTNode*first=phead->next; //定义一个first指向哨兵的next
LTNode* second=first->next; //在定义一个second指向first的next
phead->next=second;
second->prev=phead;
free(first); //把first删除后进行free
first=NULL; //first指针指向空，防止出现野指针
}void ListPopBack(LTNode*phead)
{
assert(phead);
assert(!ListEmpty(phead));//这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
LTNode*tail=phead->prev;
tail->prev->next=phead;
phead->prev=tail->prev;
free(tail);
tail=NULL;
}void ListInsert(LTNode*pos,LTDataType x)
{
assert(pos); //保证传入的pos位不是空指针
LTNode*prev=pos->prev; //找到pos位的前一位
LTNode*newnode=BuyListNode(x); //定义一个新节点进行插入
pos->prev=newnode;
newnode->next=pos;
prev->next=newnode;
newnode->prev=prev;
}void ListErase(LTNode*pos)
{
LTNode*prev=pos->prev;//找到pos位的前一个
LTNode*next=pos->next; //找到pos的后一个
prev->next=next;
next->prev=prev;
free(pos); //释放pos
}LTNode* ListNodeFind(LTNode*phead,LTDataType x) //查找后返回指针，如果找到返回找的到的结构体指针，没有找到返回空指针
{
assert(phead);
LTNode* cur=phead->next; //定义一个结构体指针进行遍历寻找
while(cur!=phead)
{
if(cur->data==x)
{
return cur; //找到后返回的指针
}
cur=cur->next;
}
return NULL;
}#ifndef List_hpp #define List_hpp #include <stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode { struct ListNode*next; struct ListNode*prev; LTDataType data; }LTNode; LTNode* ListInit(); LTNode* BuyListNode(LTDataType x); void ListPushBack(LTNode*phead,LTDataType x); void ListNodePrint(LTNode* phead); void ListPushFront(LTNode*phead,LTDataType x); void ListPopBack(LTNode*phead); bool ListEmpty(LTNode*phead); void ListPopFront(LTNode*phead); size_t ListSize(LTNode*phead); LTNode* ListNodeFind(LTNode*phead,LTDataType x); void ListInsert(LTNode*pos,LTDataType x); void ListErase(LTNode*pos); void ListDestroy(LTNode*phead); #endif /* List_hpp */
#include "List.hpp" LTNode* ListInit() { LTNode*guard=(LTNode*)malloc(sizeof(LTNode)); //这里就像定义一个哨兵，也就是头节点，就不用再担心头节点是不是NULL了 if(guard==NULL) //确保能够正常扩容 { perror("ListNodeInit"); } guard->next=guard; //头节点的下一个先指向自己 guard->prev=guard; //头节点的上一个也先指向自己 return guard; } LTNode* BuyListNode(LTDataType x) { LTNode* newnode=(LTNode*)malloc(sizeof(ListNode)); //节点申请空间 if(newnode==NULL) { perror("BuyListNode"); } newnode->data=x; //节点所带的值 newnode->prev=NULL; newnode->next=NULL; return newnode; } void ListNodePrint(LTNode* phead) { assert(phead); //保证传入的不是空指针 LTNode* cur =phead->next; //定一个结构体指针进行遍历打印 printf("guard<=>"); //这里是为了打印效果好看一点 while(cur!=phead) { printf("%d<=>",cur->data); cur=cur->next; } printf("\n"); } void ListPushBack(LTNode*phead,LTDataType x) { assert(phead); LTNode* newnode=BuyListNode(x); //定义一个新节点 LTNode* tail=phead->prev; //找到尾节点 tail->next=newnode; //然后就是交换结构体里面的next prev指向的位置来实现插入。头插我已经讲述过程了，主要是大家尝试一下画画图 newnode->prev=tail; newnode->next=phead; phead->prev=newnode; } void ListPushFront(LTNode*phead,LTDataType x) { assert(phead); LTNode* newnode=BuyListNode(x); //先定义一个节点进行头插 newnode->next=phead->next; //这里要考虑顺序问题，不然很容易出错，先让定义的next指向哨兵的下一个，然后哨兵下一个的prev指向我们新的节点 //然后让我们我们哨兵的next指向新节点，新节点的prev指向哨兵， 这里如果不理解的可以画一下图 //或者我么先定义一个节点把哨兵的下一个进行保存这里就不用考虑先后顺序了，大家可以试一试 phead->next->prev=newnode; phead->next=newnode; newnode->prev=phead; } bool ListEmpty(LTNode*phead) { assert(phead); return phead->next==phead; //如果头和头的下一个指向同一个则返回真，证明只有一个哨兵 } void ListPopBack(LTNode*phead) { assert(phead); assert(!ListEmpty(phead));//这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错 LTNode*tail=phead->prev; tail->prev->next=phead; phead->prev=tail->prev; free(tail); tail=NULL; } void ListPopFront(LTNode*phead) { assert(phead); assert(!ListEmpty(phead)); //这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错 LTNode*first=phead->next; //定义一个first指向哨兵的next LTNode* second=first->next; //在定义一个second指向first的next phead->next=second; second->prev=phead; free(first); //把first删除后进行free first=NULL; //first指针指向空，防止出现野指针 } size_t ListSize(LTNode*phead) { assert(phead); LTNode*cur=phead->next; size_t n=0; while(cur!=phead) { ++n; cur=cur->next; } return n; } LTNode* ListNodeFind(LTNode*phead,LTDataType x) //查找后返回指针，如果找到返回找的到的结构体指针，没有找到返回空指针 { assert(phead); LTNode* cur=phead->next; //定义一个结构体指针进行遍历寻找 while(cur!=phead) { if(cur->data==x) { return cur; //找到后返回的指针 } cur=cur->next; } return NULL; } void ListInsert(LTNode*pos,LTDataType x) { assert(pos); //保证传入的pos位不是空指针 LTNode*prev=pos->prev; //找到pos位的前一位 LTNode*newnode=BuyListNode(x); //定义一个新节点进行插入 pos->prev=newnode; newnode->next=pos; prev->next=newnode; newnode->prev=prev; } void ListErase(LTNode*pos) { LTNode*prev=pos->prev;//找到pos位的前一个 LTNode*next=pos->next; //找到pos的后一个 prev->next=next; next->prev=prev; free(pos); //释放pos } void ListDestroy(LTNode*phead) { LTNode*cur=phead->next; //定义一个结构体指针进行遍历销毁 while(cur!=phead) { LTNode*next=cur->next; free(cur); cur=next; } free(phead); //最后释放头节点 }
#include "List.hpp" void test1() { LTNode* plist=ListInit(); ListPushBack(plist,1); ListPushBack(plist,2); ListPushBack(plist,3); ListPushBack(plist,4); ListPushBack(plist,5); ListPopBack(plist); ListPopBack(plist); ListNodePrint(plist); ListDestroy(plist); plist=NULL; } void test2() { LTNode* plist=ListInit(); ListPushFront(plist,1); ListPushFront(plist,2); ListPushFront(plist,3); ListPushFront(plist,4); ListPushFront(plist,5); ListPopFront(plist); ListPopFront(plist); size_t ret=ListSize(plist); printf("%zu\n",ret); ListNodePrint(plist); } int main() { test1(); test2(); return 0; }
对于带头双向循环链表的实现我还是那句话，不要害怕！！！他只是结构体比较复杂，但是代码实现它确比较容易的，它不像顺序表那样要考虑是否要扩容，也不需要像单链表那样要考虑传入是否为空指针，所以他的实现还是比较容易的，而本文对于他的所有实现，我想小马应该写的很详细啦，如果有不懂的可以私信问我或者直接在评论区中问我啦！！
再者，其实思考一下，双向循环链表pos插入删除时，当我们pos等于phead时，你会发现他就像尾插和尾删，发现就不需要我们写的那么复杂啦，只需要调用一下pos函数，使pos指向phead就行啦，这里我给大家讲一个思路，对于他的实现，大家下去可以尝试一下
最后的最后，小马码文不易，如果觉得文章有帮助的话，就多多支持小马啦！！！！
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我遵循了教程http://gettingstartedwithchef.com/,第1章。我的运行list是"run_list":["recipe[apt]","recipe[phpap]"]我的phpapRecipe默认Recipeinclude_recipe"apache2"include_recipe"build-essential"include_recipe"openssl"include_recipe"mysql::client"include_recipe"mysql::server"include_recipe"php"include_recipe"php::modul
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
相信很多人在录制视频的时候都会遇到各种各样的问题，比如录制的视频没有声音。屏幕录制为什么没声音？今天小编就和大家分享一下如何录制音画同步视频的具体操作方法。如果你有录制的视频没有声音，你可以试试这个方法。 一、检查是否打开电脑系统声音相信很多小伙伴在录制视频后会发现录制的视频没有声音，屏幕录制为什么没声音？如果当时没有打开音频录制，则录制好的视频是没有声音的。因此，建议在录制前进行检查。屏幕上没有声音，很可能是因为你的电脑系统的声音被禁止了。您只需打开电脑系统的声音，即可录制音频和图画同步视频。操作方法：步骤1：点击电脑屏幕右下侧的“小喇叭”图案，在上方的选项中，选择“声音”。 步骤2：在“声
首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有， 也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加
最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
Transformers开始在视频识别领域的“猪突猛进”，各种改进和魔改层出不穷。由此作者将开启VideoTransformer系列的讲解，本篇主要介绍了FBAI团队的TimeSformer，这也是第一篇使用纯Transformer结构在视频识别上的文章。如果觉得有用，就请点赞、收藏、关注！paper:https://arxiv.org/abs/2102.05095code(offical):https://github.com/facebookresearch/TimeSformeraccept:ICML2021author:FacebookAI一、前言Transformers(VIT)在图
您将如何构建一个简单的Sinatra应用程序？我正在制作，我希望该应用具有以下功能:“应用程序”更像是一个包含所有信息的管理仪表板。然后另一个应用程序将通过REST访问信息。我还没有创建仪表板，只是从数据库中获取东西session和身份验证(尚未实现)您可以上传图片，其他应用可以显示这些图片我已经使用RSpec创建了一个测试文件通过Prawn生成报告目前的设置是这样的:app.rbtest_app.rb因为我实际上只有应用程序和测试文件。到目前为止，我已经将Datamapper用于ORM，将SQLite用于数据库。这是我的第一个Ruby/Sinatra项目，所以欢迎任何和所有建议-我应
RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)