• 【数据结构初阶】双向带头循环链表原来是纸老虎,结构复杂,操作简单


    目录

    0.结构体定义

    1.初始化

    2.尾插

    3.打印

    4.头插

    5.任意位置插入前面位置

    6.尾删

    7.头删

    8.链表长度

    9.任意位置删除当前位置

    10. 销毁


     

     

    双向带头循环链表:结构复杂,操作简单

    0.结构体定义

    这里方便浏览,特地没有将int类型重命名为TLDateType 

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #pragma once
    3. #include
    4. #include
    5. #include
    6. #include
    7. struct ListNode
    8. {
    9. int val;
    10. struct ListNode* prev;
    11. struct ListNode* next;
    12. };

    1.初始化

    1. 带头需要初始化一个哨兵位头结点
    2. 传二级指针
    3. 初始化自己的prev和next都指向自己
    1. void ListInit(struct ListNode** pphead)
    2. {
    3. struct ListNode* Guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    4. if (Guard == NULL)
    5. {
    6. perror("ListInit");
    7. return;
    8. }
    9. *pphead = Guard;
    10. Guard->next = Guard;
    11. Guard->prev = Guard;
    12. }

    2.尾插

    1. 一级指针
    2. 直接prev找尾
    3. 即是无首元结点,也可(头结点自环)
    1. struct ListNode* BuyListNode(int x)
    2. {
    3. struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    4. if (newnode == NULL)
    5. {
    6. perror("BuySListNode");
    7. return NULL;
    8. }
    9. newnode->val = x;
    10. newnode->prev = NULL;
    11. newnode->next = NULL;
    12. return newnode;
    13. }
    14. void ListPushBack(struct ListNode* phead,int x)
    15. {
    16. assert(phead);
    17. struct ListNode* newnode = BuyListNode(x);
    18. struct ListNode* tail = phead->prev;
    19. newnode->next = phead;
    20. phead->prev = newnode;
    21. tail->next = newnode;
    22. newnode->prev = tail;
    23. }

    3.打印

    1. 可assert断言(建议单链表不用断言)---头结点
    2. 起始条件cur=phead->next;
    3. 循环终止条件cur==phead
    1. void ListPrint(struct ListNode* phead)
    2. {
    3. assert(phead);
    4. struct ListNode* cur = phead->next;
    5. while (cur != phead)
    6. {
    7. printf("%d->", cur->val);
    8. cur = cur->next;
    9. }
    10. printf("NULL\n");
    11. }

    4.头插

    1. 一级指针
    2. 即是无首元结点,也可(头结点自环)
    1. void ListPushFront(struct ListNode* phead,int x)
    2. {
    3. assert(phead);
    4. struct ListNode* newnode = BuyListNode(x);
    5. struct ListNode* next = phead->next;
    6. newnode->next = next;
    7. next->prev = newnode;
    8. phead->next = newnode;
    9. newnode->prev = phead;
    10. }

    5.任意位置插入前面位置

    1. 因为有prev,前插不同phead
    2. 尾插,头插就用ListInsert传不同pos参数
    3. 如果pos传phead,就相当于于是尾插
    4. 如果pos传phead->next,就相当于于是头插
    1. void ListInsert(struct ListNode* pos, int x)
    2. {
    3. assert(pos);
    4. struct ListNode* newnode = BuyListNode(x);
    5. struct ListNode* prev = pos->prev;
    6. prev->next = newnode;
    7. newnode->prev = prev;
    8. newnode->next = pos;
    9. pos->prev = newnode;
    10. }
    11. 头插:ListNode(phead->next,x);
    12. 尾插:ListNode(phead,x);

    6.尾删

    1. 不为空,!ListEmpty(plhead)
    2. prev,tail,phead
    1. bool ListEmpty(struct ListNode* phead)
    2. {
    3. return phead->next == phead;
    4. }
    5. void ListPopBack(struct ListNode* phead)
    6. {
    7. assert(phead);
    8. assert(!ListEmpty(phead));
    9. struct ListNode* tail = phead->prev;
    10. struct ListNode* prev = tail->prev;
    11. prev->next = phead;
    12. phead->prev = prev;
    13. free(tail);
    14. tail = NULL;
    15. }

    7.头删

    1. 不为空,!ListEmpty(plhead)
    2. phead,first,second
    1. void ListPopFront(struct ListNode* phead)
    2. {
    3. assert(phead);
    4. assert(!ListEmpty(phead));
    5. struct ListNode* first = phead->next;
    6. struct ListNode* second = first->next;
    7. phead->next = second;
    8. second->prev = phead;
    9. free(first);
    10. first = NULL;
    11. }

    8.链表长度

    1. 起始条件:cur=phead->next
    2. 终止条件:cur!=phead;

    1. size_t ListSize(struct ListNode* phead)
    2. {
    3. size_t size = 0;
    4. struct ListNode* cur = phead->next;
    5. while (cur != phead)
    6. {
    7. ++size;
    8. cur = cur->next;
    9. }
    10. return size;
    11. }

    9.任意位置删除当前位置

    1. 不为空,!ListEmpty(plhead)
    2. 尾删,头删就用ListErase传不同pos参数
    3. 如果pos传phead->prev,就是尾删
    4. 如果pos传phead->next,就是头删
    1. void ListErase(struct ListNode* pos)
    2. {
    3. assert(pos);
    4. struct ListNode* prev = pos->prev;
    5. struct ListNode* next = pos->next;
    6. prev->next = next;
    7. next->prev = prev;
    8. free(pos);
    9. pos = NULL;
    10. }

    10. 销毁

    1. 看是否保留哨兵头,来传一级或二级指针
    2. 先保留哨兵头作为判断循环条件,最后决定是否释放哨兵头
    1. void ListDestory(struct ListNode** pphead)
    2. {
    3. assert(pphead);
    4. struct ListNode* cur = (*pphead)->next;
    5. while (cur != *pphead)
    6. {
    7. struct ListNode* next = cur->next;
    8. free(cur);
    9. cur = next;
    10. }
    11. free(*pphead);
    12. *pphead = NULL;
    13. }

    制作不易,敬请三连

  • 相关阅读:
    ARMday03(寄存器读写、栈、程序状态寄存器、软中断和异常、混合编程)
    东方博宜OJ——1163 - 相加之和最大,并给出它们的起始位置
    lua调用C/C++的函数,十分钟快速掌握
    嵌入式软件架构设计-模块化
    计算机毕业设计之java+ssm的鲜活农产品销售系统
    QCC3071与QCC3072有什么区别?
    取消注册Single Sign-on 域中的另一台vCenter
    STM32单片机酒精检测防酒驾系统酒精报警器
    行业洞察 | AI贩卖的焦虑,我们该买单吗?
    STM32学习笔记:USART
  • 原文地址:https://blog.csdn.net/qq_64428099/article/details/126121133