做网站需要准备什么材料,网站做推广团队,如何做网站左侧导航条,要怎么做网站动图#x1f493; 博客主页#xff1a;江池俊的博客⏩ 收录专栏#xff1a;数据结构探索#x1f449;专栏推荐#xff1a;✅cpolar ✅C语言进阶之路#x1f4bb;代码仓库#xff1a;江池俊的代码仓库#x1f525;编译环境#xff1a;Visual Studio 2022#x1f389;欢迎大… 博客主页江池俊的博客⏩ 收录专栏数据结构探索专栏推荐✅cpolar ✅C语言进阶之路代码仓库江池俊的代码仓库编译环境Visual Studio 2022欢迎大家点赞评论收藏⭐ 文章目录 一、带头循环双向链表的概念及结构二、使用带头双向循环链表的优势及注意事项三、带头双向链表的创建✨3.1 准备工作✨✨3.2 创建返回链表的头结点✨✨3.3 双向链表销毁✨✨3.4 双向链表打印✨✨3.5 双向链表尾插✨✨3.6 双向链表尾删✨✨3.7 双向链表头插✨✨3.8 双向链表头删✨✨3.9 双向链表查找✨✨3.10 双向链表在pos的前面进行插入✨✨3.11 双向链表删除pos位置的节点✨ 四、源代码4.1 List.h 文件4.2 List.c 文件4.3 Test.c 文件4.4 测试结果 双向循环链表是一种复杂的数据结构它结合了双向链表和循环链表的优点。与单向链表相比双向链表可以双向遍历而循环链表则可以在尾部链接到头部形成一个闭环。这种数据结构在某些应用场景下非常有用比如事件处理、图形界面、内存管理等。 一、带头循环双向链表的概念及结构
双向循环链表是一种特殊类型的链表它由一系列节点组成每个节点包含一个数据域和两个指针域。其中一个指针指向下一个节点另一个指针指向前一个节点。在双向循环链表中首节点的前一个节点是尾节点尾节点的下一个节点是首节点形成一个闭环。 二、使用带头双向循环链表的优势及注意事项
【优势】
高效遍历由于带头双向循环链表可以双向遍历因此可以在O(1)时间内访问任何节点。内存高效与双向链表相比带头双向循环链表不需要额外的内存来存储头部节点。插入和删除操作高效在带头双向循环链表中插入和删除节点时只需调整指针即可无需移动大量数据。
【注意事项】
初始化在创建带头双向循环链表时需要正确初始化所有节点的指针。异常处理在进行插入、删除等操作时需要处理指针异常情况如空指针或无效指针。内存管理在使用带头双向循环链表时需要正确管理内存避免内存泄漏或野指针。
三、带头双向链表的创建
✨3.1 准备工作✨
将代码分成三个文件可以提高代码的可读性、可维护性和可重用性。具体来说三个文件可以分别关注以下方面
配置文件用于存储应用程序的配置信息如数据库连接信息、应用程序名称、应用程序版本等。该文件可以在应用程序的整个生命周期内进行维护和管理并且可以轻松地与其他开发人员共享。模块文件用于存储应用程序的各个模块如用户管理、订单管理、产品管理等。每个模块都可以单独维护和测试并且可以在不同的应用程序中重复使用。这有助于降低代码冗余和提高代码的可重用性。入口文件用于定义应用程序的入口如路由、请求处理等。该文件可以控制应用程序的整个流程并且可以轻松地与其他开发人员共享。
通过将代码分成三个文件可以更好地组织代码结构使其更加清晰和易于维护。同时这也使得代码更易于测试和调试并且可以更好地支持代码重构和优化。 #pragma once#include stdio.h
#include stdlib.h
#include assert.h// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data; //节点存储的数据元素struct ListNode* next; //指向前驱节点struct ListNode* prev; //指向后继节点
}ListNode; //双链表结构//几大接口
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);✨3.2 创建返回链表的头结点✨ 动态申请一个节点作为双向链表的头节点。并将头节点的 prev 指向自己next也指向自己表明这是一个双向链表且链表为空。 // 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* head (ListNode*)malloc(sizeof(ListNode));if (head NULL){perror(ListCreate -- malloc);return;}head-data -1;head-prev head;head-next head;return head;
}✨3.3 双向链表销毁✨ 从链表的第二个节点开始逐个释放链表中的节点直到回到头节点并释放头节点的内存空间。这样做可以确保链表中的所有节点都被正确释放防止内存泄漏。 // 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next; }free(pHead);printf(双链表销毁成功\n);
}✨3.4 双向链表打印✨
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;printf(哨兵位 -- );while (cur ! pHead){printf(%d -- , cur-data);cur cur-next;}printf(哨兵位\n);
}✨3.5 双向链表尾插✨ 在进行插入节点之前无论是头插还是尾插都需要申请一个新的节点于是可以把此步骤成一个函数减少代码的冗余。 //申请一个节点
ListNode* CreateLTNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(CreateLTNode -- malloc);return;}newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}首先创建一个新的节点newnode并将数据x存储在其中。将newnode的prev指针指向当前链表的第一个节点pHead的前一个节点即pHead-prev。将newnode的next指针指向当前链表的第一个节点pHead。将当前链表的第一个节点pHead的前一个节点的next指针指向新节点newnode。将当前链表的第一个节点pHead的prev指针指向新节点newnode。 通过以上步骤新节点被插入到双向链表的尾部并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中并且不会破坏链表的结构。 // 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode CreateLTNode(x);//pHead pHead-prev newnodenewnode-prev pHead-prev; newnode-next pHead;pHead-prev-next newnode;pHead-prev newnode;
}✨3.6 双向链表尾删✨ 首先获取链表的最后一个节点tail它应该是头节点pHead的前一个节点即pHead-prev。接着获取最后一个节点的前一个节点tailPrev。将头节点pHead的prev指针指向最后一个节点的前一个节点tailPrev从而将最后一个节点从链表中间删除。将最后一个节点的前一个节点的next指针指向头节点pHead从而将头节点和最后一个节点连接起来。最后释放最后一个节点的内存空间。 // 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-next!pHead);//链表不能为空ListNode* tail pHead-prev;ListNode* tailPrev tail-prev;// pHead tailPrev tailpHead-prev tailPrev;tailPrev-next pHead;free(tail);
}✨3.7 双向链表头插✨ 首先创建一个新的节点newnode并将数据x存储在其中。将新节点的prev指针指向当前链表的第一个节点pHead。将新节点的next指针指向当前链表的第一个节点的下一个节点即pHead-next。将当前链表的第一个节点的next指针指向新节点newnode。将当前链表的第一个节点的下一个节点的prev指针指向新节点newnode。 通过以上步骤新节点被插入到双向链表的头部并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中并且不会破坏链表的结构。 // 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode CreateLTNode(x);ListNode* rear pHead-next;pHead-next newnode;newnode-prev pHead;newnode-next rear;rear-prev newnode;
}✨3.8 双向链表头删✨ 首先获取链表的第一个节点cur它应该是头节点pHead的下一个节点即pHead-next。将头节点的next指针指向第一个节点的下一个节点从而将第一个节点从链表中间删除。将第一个节点的下一个节点的prev指针指向头节点pHead从而将头节点和第一个节点连接起来。最后释放第一个节点的内存空间。 // 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead);ListNode* cur pHead-next;pHead-next cur-next;cur-next-prev pHead;free(cur);
}✨3.9 双向链表查找✨ 首先从链表的第二个节点开始即pHead-next遍历链表的每个节点。对于每个节点检查其存储的数据是否与要查找的数据x相等。如果找到了匹配的节点则返回该节点。如果遍历完整个链表都没有找到匹配的节点则返回空指针NULL。 // 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;//如果没找到返回空
}✨3.10 双向链表在pos的前面进行插入✨ 首先创建一个新的节点newnode并将数据x存储在其中。获取要插入位置的前一个节点_prev。将前一个节点的next指针指向新节点newnode。将新节点的prev指针指向前一个节点_prev。将新节点的next指针指向当前节点pos。将当前节点的prev指针指向新节点newnode。 通过以上步骤新节点被插入到指定位置的前面并且链表中的其他节点仍然保持其原始顺序和链接关系。这样做可以确保新节点被正确地添加到链表中并且不会破坏链表的结构。 // 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode CreateLTNode(x);ListNode* _prev pos-prev;// _prev newnode pos_prev-next newnode;newnode-prev _prev;newnode-next pos;pos-prev newnode;
}✨3.11 双向链表删除pos位置的节点✨ 首先确保要删除的节点pos不是空指针。获取要删除节点的前一个节点_prev和后一个节点rear。将前一个节点的next指针指向后一个节点从而将要删除的节点从链表中间删除。将后一个节点的prev指针指向前一个节点从而将前一个节点和后一个节点连接起来。释放要删除的节点的内存空间。 // 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* _prev pos-prev;ListNode* rear pos-next;_prev-next rear;rear-prev _prev;free(pos);
}四、源代码
4.1 List.h 文件
#pragma once#include stdio.h
#include stdlib.h
#include assert.h// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data; //节点存储的数据元素struct ListNode* next; //指向前驱节点struct ListNode* prev; //指向后继节点
}ListNode; //双链表结构// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);4.2 List.c 文件
#define _CRT_SECURE_NO_WARNINGS 1#include List.h//申请一个节点
ListNode* CreateLTNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(CreateLTNode -- malloc);return;}newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* head (ListNode*)malloc(sizeof(ListNode));if (head NULL){perror(ListCreate -- malloc);return;}head-data -1;head-prev head;head-next head;return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next; }free(pHead);printf(双链表销毁成功\n);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;printf(哨兵位 -- );while (cur ! pHead){printf(%d -- , cur-data);cur cur-next;}printf(哨兵位\n);
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode CreateLTNode(x);//pHead pHead-prev newnodenewnode-prev pHead-prev; newnode-next pHead;pHead-prev-next newnode;pHead-prev newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-next!pHead);//链表不能为空ListNode* tail pHead-prev;ListNode* tailPrev tail-prev;// pHead tailPrev tailpHead-prev tailPrev;tailPrev-next pHead;free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode CreateLTNode(x);ListNode* rear pHead-next;pHead-next newnode;newnode-prev pHead;newnode-next rear;rear-prev newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead);ListNode* cur pHead-next;pHead-next cur-next;cur-next-prev pHead;free(cur);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;//如果没找到返回空
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode CreateLTNode(x);ListNode* _prev pos-prev;// _prev newnode pos_prev-next newnode;newnode-prev _prev;newnode-next pos;pos-prev newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* _prev pos-prev;ListNode* rear pos-next;_prev-next rear;rear-prev _prev;free(pos);
}4.3 Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1#include List.hvoid Test1()
{ListNode* plist ListCreate();//尾插1、2、3ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPrint(plist);//头插5、4ListPushFront(plist, 5);ListPushFront(plist, 4);ListPrint(plist);//查找元素3找到返回节点地址没找到返回空ListNode* pos ListFind(plist, 3);if (pos){printf(找到了\n);}else{printf(没找到\n);}//在3前面插入30ListInsert(pos, 30);ListPrint(plist); //删除3if (pos){ListErase(pos);pos NULL;}ListPrint(plist);//尾删两次ListPopBack(plist);ListPopBack(plist);ListPrint(plist);//头删两次ListPopFront(plist);ListPopFront(plist);ListPrint(plist);//销毁链表ListDestory(plist);plist NULL;
}int main()
{Test1();return 0;
}4.4 测试结果
