企业网站管理系统设计与实现,深圳软件系统开发,主机屋 建网站教程,4399影视在线观看免费高清双向循环链表特点
**双向链接#xff1a;**每个节点都包含两个指针#xff0c;一个指向前一个节点#xff08;前驱节点#xff09;#xff0c;另一个指向后一个节点#xff08;后继节点#xff09;。这种双向连接使得在链表中可以轻松地在两个方向上遍历节点。
**循环…双向循环链表特点
**双向链接**每个节点都包含两个指针一个指向前一个节点前驱节点另一个指向后一个节点后继节点。这种双向连接使得在链表中可以轻松地在两个方向上遍历节点。
**循环性质**最后一个节点的后继节点指向第一个节点形成一个环状结构。这意味着可以无限循环遍历链表因为没有真正的末尾。
**灵活性**由于双向链接可以方便地在链表中插入、删除和移动节点而不需要像单链表那样需要迭代查找前一个节点。
**前向和后向遍历**可以从任何节点开始向前或向后遍历整个链表。这对于需要双向遍历的情况非常有用例如在双向队列deque或编辑器中。
**常见应用**双向循环链表常用于实现循环队列、双向队列、LRU最近最少使用缓存算法、文本编辑器的撤销和重做功能等。
哨兵位
数据结构中的哨兵位通常指的是一种特殊的元素或节点它在数据结构中扮演了特殊的角色通常用于简化算法的实现、边界情况的处理或者提高性能。哨兵位并不包含实际的数据其主要作用是占据一个特定的位置以便更容易处理数据结构的边界情况。
C语言代码实现
声明文件
#pragma once
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* BuyListNode(LTDataType x);
LTNode* ListInit(); //双向链表初始化
void LTPrint(LTNode* phead); //Print void ListPushBack(LTNode* phead, LTDataType x); //尾插
void ListPopBack(LTNode* phead); //尾删void ListPushFront(LTNode* phead, LTDataType x); //头插
void ListPopFront(LTNode* phead); //头删LTNode* LTFind(LTNode* phead, LTDataType x); //查找void LTInsert(LTNode* pos, LTDataType x); //在pos之前插入x
void LTErase(LTNode* pos); //删除pos位置的数据bool LTEmpty(LTNode* phead); //判断双向链表是否为空
size_t LTSize(LTNode* phead); //长度
void LTDestroy(LTNode* phead); //销毁链表实现文件
#include List.hLTNode* BuyListNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode)); if (node NULL) {perror(malloc fail...);return -1;}node-data x;node-next NULL;node-prev NULL;return node;
}LTNode* ListInit()
{LTNode* phead BuyListNode(-1);phead-next phead; phead-prev phead;return phead;
}void LTPrint(LTNode* phead) // Print double-link list
{assert(phead); // ensure phead is not empty LTNode* cur phead-next;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; newnode-next phead; newnode-prev tail;tail-next newnode; phead-prev newnode; }void ListPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead); LTNode* tail phead-prev;LTNode* tailPrev tail-prev;tailPrev-next phead;phead-prev tailPrev;free(tail);
}void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode; newnode-prev phead;
}void ListPopFront(LTNode* phead) // head deletion
{assert(phead);assert(phead-next ! phead);LTNode* cur phead-next; LTNode* cur_next cur-next;phead-next cur_next;cur_next-prev phead;free(cur); //freeing this node
}LTNode* LTFind(LTNode* phead, LTDataType x) //Find the position of data x
{assert(phead);LTNode* cur phead-next;while (cur-next ! phead){if (cur-data x) //find{return cur; //return the datas node}cur cur-next; //if not find, pointer pointing to the next node}return; //not find
}void LTInsert(LTNode* pos, LTDataType x) //在pos之前插入x
{assert(pos);LTNode* newnode BuyListNode(x); //new node that data is xLTNode* prev pos-prev;newnode-prev prev;newnode-next pos;prev-next newnode;pos-prev newnode;
}void LTErase(LTNode* pos) //删除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);//if (phead-next phead)//{// return true;//}//else//{// return false;//}return phead-next phead;
}size_t LTSize(LTNode* phead) //长度
{assert(phead);size_t counter 0;LTNode* cur phead;while (cur ! phead){counter;cur cur-next;}return counter;
}void LTDestroy(LTNode* phead) //销毁链表
{assert(phead);LTNode* cur phead;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);phead NULL; //这里置空不起作用}测试代码
#include List.hvoid ListTest_1()
{LTNode* phead ListInit();ListPushBack(phead, 10);ListPushBack(phead, 20);ListPushBack(phead, 30);ListPushBack(phead, 40);LTPrint(phead); //Print double-link listLTNode* pos LTFind(phead,30); //Find the position of data if (pos-data 30){printf(找到了);}else{printf(没找到);}LTInsert(pos, 100);//ListPopBack(phead);//ListPopBack(phead);//ListPopBack(phead);//ListPopFront(phead); //ListPopFront(phead);//ListPopFront(phead);//ListPopFront(phead);LTErase(pos);LTPrint(phead);
}int main()
{ListTest_1();return 0;
}
