提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

单循环链表-带头双向循环链表的实现

2023-02-18 16:46:38 时间

  带头双向循环链表

  前言

  对于链表来说，不只有单链表这一个品种；

  链表有很多种形态

  按方向分：单向、双向

  按带不带头：带头、不带头

  按循环：循环、不循环

  1、单向或则双向：

  2、带头或者不带头：

  3、循环或者不循环：

  组合排列一下的话，链表一共有8种形态！！！

  今天我们就来学习一下结构最复杂的带头双向循环链表！！！；

  虽然名字听上去比较复杂单循环链表，但是实现起来比单链表（全名：不带头、不循环、单向链表）更加简单，也不需要过多考虑特殊情况；

  两种链表的比较：（上面是单链表，下面是带头双向循环链表）

  结构分析

  首先链表的头节点是不存储有效数据的（该节点被称为哨兵位），其次我们只需要知道改头节点的指针就能找到整个链表单循环链表，并且便于对整个链表进行维护；

  当然既然是双向的嘛，那节点一定有个指针域指向前一个节点，另一个指针域指向后一个节点；

  那么我们的单个节点的数据结构就是：

  现在我们定义了一个plist指针用来维护整个链表，根据上面说的plist就应该用来存储哨兵位的头节点的指针，那么如何表示链表为NULL的情况？

  链表为空：

  就是:

  head->next=head;

  head->prev=head;

  链表的基本操作实现 创建节点

   ListNode* ListCreate(LTDataType x)

    {
        ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
        if (!NewNode)
            exit(-1);
        NewNode->val = x;
        NewNode->prev = NULL;
        NewNode->next = NULL;
        return NewNode;
    }

  我们在创建节点的时候就一起将数据域初始化，方标后续操作；

  初始化链表

   void InitDummyHead(ListNode* pHead)

    {
        assert(pHead);
        pHead->prev = pHead;
        pHead->next = pHead;
    }

  链表销毁

   // 双向链表销毁

    void ListDestory(ListNode* pHead)
    {
        assert(pHead);
        ListNode* cur = pHead->next;
        ListNode* next = NULL;
        while (cur!=pHead)
        {
            next = cur->next;
            free(cur);
            cur = next;
        }
        free(cur);
    }

  实现思路：

  打印链表

  除了哨兵位的节点存到是无效数据不打印外，其他节点的数据都要打印：

   // 双向链表打印

    void ListPrint(ListNode* pHead)
    {
        assert(pHead);
        ListNode* cur = pHead->next;
        while (cur != pHead)
        {
            ListNode* next = cur->next;
            printf("%d->",cur->val);
            cur = next;
        }
        printf("NULL\n");
    }

  链表尾插

  该链表的尾插，比单链表的尾插简单太多了，不用遍历找尾：

   // 双向链表尾插

    void ListPushBack(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        ListNode* NewNode = ListCreate(x);
        ListNode* tail = pHead->prev;
        tail->next = NewNode;
        NewNode->prev = tail;
        pHead->prev = NewNode;
        NewNode->next = pHead;
    }

  链表尾删

  由于是循环的，哨兵位的前一个节点就是尾节点，同时尾节点的前一个节点我们也不用遍历，可以很轻松的拿到：

   // 双向链表尾删

    void ListPopBack(ListNode* pHead)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//判空
        ListNode* tail = pHead->prev;
        ListNode* prev = tail->prev;
        ListNode* next = pHead;
        free(tail);
        prev->next = next;
        next->prev = prev;
    }

  链表头插

   // 双向链表头插

    void ListPushFront(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        ListNode* prev = pHead;
        ListNode* cur = pHead->next;
        ListNode* NewNode = ListCreate(x);
        prev->next = NewNode;
        NewNode->prev = prev;
        NewNode->next = cur;
        cur->prev = NewNode;
    }

  链表头删

   // 双向链表头删

    void ListPopFront(ListNode* pHead)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//判空
        ListNode* prev = pHead;
        ListNode* cur = pHead->next;
        ListNode* next = cur->next;
        free(cur);
        prev->next = next;
        next->prev = prev;
    }

  链表查找

   // 双向链表查找

    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
        ListNode* cur = pHead->next;
        while (cur != pHead)
        {
            if (cur->val == x)
                return cur;
            else
                cur = cur->next;
        }
        return NULL;
    }

  链表pos位置前面插入

   // 双向链表在pos的前面进行插入

    void ListInsert(ListNode* pos, LTDataType x)
    {
        assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
        ListNode* NewNode = ListCreate(x);
        ListNode* prev = pos->prev;
        NewNode->next = pos;
        pos->prev = NewNode;
        prev->next = NewNode;
        NewNode->prev = prev;
    }

  删除pos位置

   // 双向链表删除pos位置的节点

    void ListErase(ListNode* pos)
    {
        assert(pos);//由于参数限制，我们无法判断表是否为NULL；
        ListNode* prev = pos->prev;
        ListNode* next = pos->next;
        free(pos);
        prev->next = next;
        next->prev = prev;
    }

  链表判空

   //判断链表是否为NULL

    bool is_Empty(ListNode* pHead)
    {
        assert(pHead);
        return pHead == pHead->prev;
    }

  代码复用

  我们上面既然实现了在pos位置之前插入和删除pos位置的数据；

  那么：

   ListInsert(plist,x);//相当于尾插

    ListInsert(plist->next, x);//相当于头插
    ListErase(plist->next);//相当于头删
    ListErase(plist->prev);//相当于尾删;

  那么实际上我们只要实现、这两个接口就能快速实现出带头双向循环链表了；

  总代码及头文件

  头文件的包含：

   #pragma once

    #include
    #include
    #include
    #include
    // 带头+双向+循环链表增删查改实现
    typedef int LTDataType;
    typedef struct ListNode
    {
        LTDataType val;
        struct ListNode* next;
        struct ListNode* prev;
    }ListNode;
    // 创建返回链表的头结点.
    ListNode* ListCreate(LTDataType x);
    //初始化哨兵位的头节点;
    void InitDummyHead(ListNode* pHead);
    // 双向链表销毁
    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);
    //判断链表是否为NULL
    bool is_Empty(ListNode* pHead);

  功能代码实现：

   #include"DList.h"

    ListNode* ListCreate(LTDataType x)
    {
        ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
        if (!NewNode)
            exit(-1);
        NewNode->val = x;
        NewNode->prev = NULL;
        NewNode->next = NULL;
        return NewNode;
    }
    void InitDummyHead(ListNode* pHead)
    {
        assert(pHead);
        pHead->prev = pHead;
        pHead->next = pHead;
    }
    // 双向链表销毁
    void ListDestory(ListNode* pHead)
    {
        assert(pHead);
        ListNode* cur = pHead->next;
        ListNode* next = NULL;
        while (cur!=pHead)
        {
            next = cur->next;
            free(cur);
            cur = next;
        }
        free(cur);
    }
    // 双向链表打印
    void ListPrint(ListNode* pHead)
    {
        assert(pHead);
        ListNode* cur = pHead->next;
        while (cur != pHead)
        {
            ListNode* next = cur->next;
            printf("%d->",cur->val);
            cur = next;
        }
        printf("NULL\n");
    }
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        /*ListNode* NewNode = ListCreate(x);
        ListNode* tail = pHead->prev;
        tail->next = NewNode;
        NewNode->prev = tail;
        pHead->prev = NewNode;
        NewNode->next = pHead;*/
        ListInsert(pHead,x);//函数复用
    }
    // 双向链表尾删
    void ListPopBack(ListNode* pHead)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//判空
        /*ListNode* tail = pHead->prev;
        ListNode* prev = tail->prev;
        ListNode* next = pHead;
        free(tail);
        prev->next = next;
        next->prev = prev;*/
        ListErase(pHead->prev);//函数复用
    }
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        /*ListNode* prev = pHead;
        ListNode* cur = pHead->next;
        ListNode* NewNode = ListCreate(x);
        prev->next = NewNode;
        NewNode->prev = prev;
        NewNode->next = cur;
        cur->prev = NewNode;*/
        ListInsert(pHead->next,x);//函数复用
    }
    // 双向链表头删
    void ListPopFront(ListNode* pHead)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//判空
        /*ListNode* prev = pHead;
        ListNode* cur = pHead->next;
        ListNode* next = cur->next;
        free(cur);
        prev->next = next;
        next->prev = prev;*/
        ListErase(pHead->next);//函数复用
    }
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
        ListNode* cur = pHead->next;
        while (cur != pHead)
        {
            if (cur->val == x)
                return cur;
            else
                cur = cur->next;
        }
        return NULL;
    }
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
        assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
        ListNode* NewNode = ListCreate(x);
        ListNode* prev = pos->prev;
        NewNode->next = pos;
        pos->prev = NewNode;
        prev->next = NewNode;
        NewNode->prev = prev;
    }
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
        assert(pos);//由于参数限制，我们无法判断表是否为NULL；
        ListNode* prev = pos->prev;
        ListNode* next = pos->next;
        free(pos);
        prev->next = next;
        next->prev = prev;
    }
    //判断链表是否为NULL
    bool is_Empty(ListNode* pHead)
    {
        assert(pHead);
        return pHead == pHead->prev;
    }

本文共 1085 个字数,平均阅读时长 ≈ 3分钟

相关文章