网站导航
> 文章列表 > 手撕数据结构—双向循环带头链表

手撕数据结构—双向循环带头链表

网友: 文章列表 2024-03-21 16:20:55

手撕数据结构—双向循环带头链表

对于双向循环带头链表，需要注意：不存在NULL，只管链接就可

双向链表的节点(结构体)创建

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;

双向链表的节点新增

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode::Malloc");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}

双向链表的初始化

LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

双向链表的打印

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=head=>");while (cur!=phead){printf("%d=>",cur->data);cur = cur->next;}printf("\\n");
}

双向链表的尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

双向链表的头插

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

双向链表的在第pos节点之前插入

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

双向链表的尾删

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}

双向链表的头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}

双向链表的删除pos节点

  1. 实际上这个也非常简单，只需要把pos节点的前一个节点和之后的节点给找到，只需要去改动一下链接关系。

  1. 然后在这边的话只需要传一级指针，当然穿二级指针的话也是没有问题的，这样子的话，你就可以在函数内部去置空，但是我们为了保持接口风格的统一，还是传一级指针。这样子的话其实也影响不大，对于pos指针的置空我只需要在函数外头手头置空，道理一样。

void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}

双向链表的根据数值查找节点

  1. 这个实际上跟之前的打印有点类似，反正都是先去遍历一下链表，然后去看一下当前节点的数值与我要查找的数值是不是一样的。

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (x == cur->data){return cur;}cur = cur->next;}return NULL;
}

双向链表的销毁

  1. 在销毁双向链表的时候，最好是从哨兵位头结点的下一个节点作为起点，因为哨兵位头结点我后面是有用的，我要做为结束的标志。然后最后再把哨兵位头结点还给操作系统。

  1. 然后在这边的话会发现所有的函数操作全部都是传的是一级指针，因为对于现在的双向循环带头链表，各种操作改来改去的话，都是改变结构体成员指针的指向的位置，因此我只要传一级指针，也就是结构体指针就已经可以了。

  1. 至于有些释放完后置空的操作，虽然在传一级指针的情况之下，在函数内部无法完成（因为就算我在函数里面置空，那也是对形式参数指针置空，形参的改变不会影响实参，函数外面的“正品”还没有被置空呢，因此这时候其实也不麻烦，只需要我手动的在函数外头置空就OK了）。

  1. 然后再回顾一下之前的无头单向非循环链表，这个的话由于各种操作不可避免的需要在函数内部去改变phead所指向的位置，那么这个时候我就需要传入指针的地址，也就是二级指针。

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* n = cur->next;while (cur != phead){free(cur);cur = n;n = n->next;}free(phead);
}

双向带头循环链表的所有操作汇总

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <assert.h>
#include <stdlib.h>//双向链表的节点(结构体)创建
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;//双向链表的节点新增
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode::Malloc");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}//双向链表的初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}//双向链表的打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=head=>");while (cur!=phead){printf("%d=>",cur->data);cur = cur->next;}printf("\\n");
}//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}//双向链表的在第pos节点之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}//双向链表的尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}//双向链表的头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}//双向链表的删除pos节点
void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}//双向链表的根据数值查找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (x == cur->data){return cur;}cur = cur->next;}return NULL;
}//双向链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* n = cur->next;while (cur != phead){free(cur);cur = n;n = n->next;}free(phead);
}void menu()
{printf("*    List Table    *\\n");printf("1. 双向链表的尾插(LTPushBack)\\n");printf("2. 双向链表的头插(LTPushFront)\\n");printf("3. 双向链表的在第pos节点之前(输入数值)插入(LTInsert)\\n");printf("4. 双向链表的尾删(LTPopBack)\\n");printf("5. 双向链表的头删(LTPopFront)\\n");printf("6. 双向链表的删除pos节点(LTErase)\\n");printf("7. 双向链表的打印\\n");printf("\\n");printf("请输入(按0退出)：");
}void HoldAndClear()
{printf("按任意键退出.....");getchar();getchar();
}int main()
{LTNode* phead = LTInit();int input = 0;int num = 0;int value = 0;do{system("cls");menu();scanf("%d", &input);switch (input){case 1:scanf("%d", &num);LTPushBack(phead, num);HoldAndClear();break;case 2:scanf("%d", &num);LTPushFront(phead, num);HoldAndClear();break;case 3:LTPrint(phead);scanf("%d %d", &value, &num);LTInsert(LTFind(phead, value), num);HoldAndClear();break;case 4:LTPopBack(phead);HoldAndClear();break;case 5:LTPopFront(phead);HoldAndClear();break;case 6:LTPrint(phead);scanf("%d", &value);LTErase(LTFind(phead, value), num);HoldAndClear();break;case 7:LTPrint(phead);HoldAndClear();break;case 0:printf("退出成功\\n");break;default:printf("重新输入\\n");break;}} while (input);return 0;
}

网络标签：

相关问题