织梦cms 学校网站模板,网站建设中的问题,建筑设计参考网站,电商网站后台报价前言#xff1a; 前面我们已经学习了单链表的结构及其功能特点#xff0c;也了解了单链表在实现一些功能时出现的一些缺点#xff0c;比如在删除某个节点前面一个节点时就需要再开一个变量来存放前面一个节点的信息#xff0c;这样就显得不灵活#xff0c;为了使链表实现功…前言 前面我们已经学习了单链表的结构及其功能特点也了解了单链表在实现一些功能时出现的一些缺点比如在删除某个节点前面一个节点时就需要再开一个变量来存放前面一个节点的信息这样就显得不灵活为了使链表实现功能更加灵活我给来介绍带头双向循环链表这种链表可以看成是单链表的升级版。 什么是带头双向循环链表 带头双向循环链表是一种常见的链表数据结构它是由若干个结点组成的链式数据结构每个结点包含两个指针分别指向前一个结点和后一个结点。与普通的单向链表只能单向遍历不同在双向循环链表中可以使用前后两个方向进行遍历。 带头双向循环链表的优点 带头链表意味着在链表头部添加一个空的头结点这个头结点不包含数据仅包含指向链表首尾结点的指针它主要作用是简化链表的操作。在插入、删除、查找等操作时可以直接从头结点开始操作无需特殊处理首尾结点。 双向循环意味着链表的每一个节点都可以随意的找到上一个节点以及下一个节点并且头节点的前驱指针指向尾节点尾节点的后驱指针指向头节点这样整个链表就形成了一个环状结构可以任意方向遍历整个链表。 由于带头双向循环链表具有链表的优点同时又兼具循环队列的特点因此在实际应用中被广泛使用。比如在实现 LRU 缓存淘汰算法、模拟双向队列等场景中都有使用。 代码实现
DList.h头文件
各种功能函数的声明以及数据的定义
#includestdio.h
#includestdlib.h
#includeassert.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);DList.c文件
各种功能函数的具体实现细节
#includeDList.h// 创建返回链表的头结点.
ListNode* ListCreate() {ListNode* NewList (ListNode*) malloc(sizeof(ListNode));if (NewList NULL) {perror(malloc: fail);}NewList-_data -1;NewList-_prev NewList;NewList-_next NewList;return NewList;
}//创造节点
static ListNode* CreatNode(LTDataType x) {ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL) {perror(malloc:fail);}newnode-_data x;newnode-_next newnode;newnode-_prev newnode;return newnode;
}// 双向链表销毁
void ListDestory(ListNode* phead) {assert(phead);ListNode* cur phead;cur cur-_next;while (cur!phead) {ListNode* temp cur-_next;cur-_prev-_next cur-_next;cur-_next-_prev cur-_prev;free(cur);cur temp;}free(cur);cur NULL;
}// 双向链表打印
void ListPrint(ListNode* phead) {assert(phead);ListNode* cur phead-_next;printf(%d, phead-_data);while (cur! phead) {printf( %d , cur-_data);cur cur-_next;}printf(%d\n, phead-_data);
}// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode CreatNode(x);ListNode* tail phead-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next phead;phead-_prev newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead) {assert(phead(phead-_next!phead));ListNode* tail phead-_prev;phead-_prev tail-_prev;tail-_prev-_next phead;free(tail);tail NULL;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode CreatNode(x);phead-_next-_prev newnode;newnode-_next phead-_next;newnode-_prev phead;phead-_next newnode;
}// 双向链表头删
void ListPopFront(ListNode* phead) {assert(phead(phead-_next!phead));ListNode* head phead-_next;phead-_next-_next-_prev phead;phead-_next phead-_next-_next;free(head);head NULL;
}// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {assert(phead (phead-_next ! phead));//ListNode* newnode CreatNode(x);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 CreatNode(x);pos-_prev-_next newnode;newnode-_prev pos-_prev;newnode-_next pos;pos-_prev newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {assert(pos(pos-_next!pos));ListNode* temp pos;pos-_prev-_next pos-_next;pos-_next-_prev pos-_prev;free(temp);temp NULL;
}test.c测试文件
分块测试各个部分的功能
#includeDList.hvoid test1()//测试尾插、尾删
{// 创建返回链表的头结点.ListNode* pheadNULL;phead ListCreate();ListPushBack(phead, 1);//尾插ListPushBack(phead, 2);ListPushBack(phead, 3);ListPrint(phead);printf(尾删\n);ListPopBack(phead);//尾删ListPrint(phead);printf(尾删\n);ListPopBack(phead);//尾删ListPrint(phead);//ListPopBack(phead);//ListPrint(phead);ListDestory(phead);//销毁链表
}void test2()//测试头插、头删
{// 创建返回链表的头结点.ListNode* phead NULL;phead ListCreate();ListPushFront(phead, 1);//头插头删ListPushFront(phead, 2);ListPushFront(phead, 3);ListPrint(phead);printf(头删\n);ListPopFront(phead);ListPrint(phead);printf(头删\n);ListPopFront(phead);//ListPopFront(phead);//ListPopFront(phead);//ListPopFront(phead);ListPrint(phead);ListDestory(phead);}
void test3()//测试查找随机位置插入随机位置删除
{// 创建返回链表的头结点.ListNode* phead NULL;phead ListCreate();//初始化链表数据 1 2 3 4 5ListPushFront(phead, 1);ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPushFront(phead, 5);ListPrint(phead);//ListNode* targetnode ListFind(phead, 5);ListNode* targetnode ListFind(phead, 4);if (targetnode NULL) {//没有找到printf(没有找到\n);}else {printf(找到%d了\n,targetnode-_data);/*ListErase(targetnode);printf(删除这个节点\n);*/ListInsert(targetnode, 10);//在目标节点前面插入printf(在这个节点插入一个数\n);ListPrint(phead);}ListNode* targetnode2 ListFind(phead, 4);if (targetnode2 NULL) {//没有找到printf(没有找到\n);}else {printf(找到%d了\n, targetnode2-_data);ListErase(targetnode);printf(删除这个节点\n);ListPrint(phead);}//ListPopFront(phead);//ListPrint(phead);ListDestory(phead);phead NULL;
}int main() {test1();//test2();//test3();return 0;
}test1运行结果 test2运行结果 test3运行结果
