【C数据结构】带头双向循环链表_HDList

迈不过友情╰ 2024-03-16 20:10 80阅读 0赞

**目录**

带头双向循环链表\_HDList

【1】链表概念

【2】链表分类

【3】带头双向循环链表

【3.1】带头双向循环链表数据结构与接口定义

【3.2】带头双向循环链表初始化

【3.3】带头双向循环链表开辟节点空间

【3.4】带头双向循环链表销毁

【3.5】带头双向循环链表头插

【3.6】带头双向循环链表尾插

【3.7】 带头双向循环链表头删

【3.8】 带头双向循环链表尾删

【3.9】带头双向循环链表在pos位置插

【3.10】带头双向循环链表在pos位置删

【3.11】 无头单向非循环链表查找

【3.12】 无头单向非循环链表返回大小

【3.13】 无头单向非循环链表打印

【3.14】 无头单向非循环链表判空

--------------------

## 带头双向循环链表\_HDList ##

## 【1】链表概念 ##

**概念：**链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表是指逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置。

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。

![d67e6f0715444c058605005c9b7347dd.png][]

如图所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

## **【2】链表分类** ##

*  **单向或者双向链表**

![7faf591f2af64de2af046c2fc19a2cf4.png][]

*  **带头或不带头链表**

![b7619049916b44e581a313e6328ad695.png][]

*  **循环非循环链表**

![15e0ebde0c4d46a38b33200d2312c6db.png][]

*  **虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：**

![d5570df5e1ba498b88ed0c2a7ca2adbb.png][]

## 【3】带头双向循环链表 ##

**双向链表特点：**

*  每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
 *  相对于单向链表, 必然占用内存空间更大一些.
 *  既可以从头遍历到尾, 又可以从尾遍历到头

**双向链表的定义:**

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

下图为双向链表的结构图。

![ece5f30045ff4792badf0d487a33252e.png][]

### 【3.1】带头双向循环链表数据结构与接口定义 ###

链表中存放的不是基本数据类型，需要用结构体实现自定义：

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    
    // 双向带头循环链表中数据元素的构成
    typedef int DHLDataType;
    typedef struct DHListNode
    {
        DHLDataType data; // 数据存储区、
        struct DHListNode* prev;    // 记录上一个节点。
        struct DHListNode* next;    // 记录下一个节点。
    }DHListNode;
    
    // 双向带头循环链表 - 初始化函数声明。
    DHListNode* DHListInit();
    
    // 双向带头循环链表 - 开辟节点函数声明。
    DHListNode* BuyDHListNode(DHLDataType val);
    
    // 双向带头循环链表 - 内存销毁函数声明。
    void DHListDestory(DHListNode* pHead);
    
    // 双向带头循环链表 - 尾插函数声明。
    void DHListPushBack(DHListNode* pHead, DHLDataType val);
    
    // 双向带头循环链表 - 头插函数声明。
    void DHListPushFront(DHListNode* pHead, DHLDataType val);
    
    // 双向带头循环链表 - 尾删函数声明。
    void DHListPopBack(DHListNode* pHead);
    
    // 双向带头循环链表 - 头删函数声明。
    void DHListPopFront(DHListNode* pHead);
    
    // 双向带头循环链表 - 在任意位置前插函数声明。
    void DHListInsert(DHListNode* pos, DHLDataType val);
    
    // 双向带头循环链表 - 在任意位置前删函数声明。
    void DHListErase(DHListNode* pos);
    
    // 双向带头循环链表 - 打印函数声明。
    void DHListPrint(DHListNode* pHead);
    
    // 双向带头循环链表 - 判断链表是否为空函声明。
    bool DHListEmpty(DHListNode* pHead);
    
    // 双向带头循环链表 - 统计节点个数空函数声明。
    size_t DHListSize(DHListNode* pHead);
    
    // 双向带头循环链表 - 查找节点函数声明。
    DHListNode* DHListFind(DHListNode* pHead, DHLDataType val);

### 【3.2】带头双向循环链表初始化 ###

![e6568633104c4cf38f5bd51404345c89.png][]

// 双向带头循环链表 - 初始化函数。
    DHListNode* DHListInit()
    {
        DHListNode* newNode = (DHListNode*)malloc(sizeof(DHListNode));
        // 判断是否开辟内存空间成功。
        if (newNode == NULL)
        {
            perror("ListInit malloc fail!");
            exit(-1);
        }
    
        // 程序走到这里说明开辟空间成功了。
        newNode->prev = newNode;
        newNode->next = newNode;
        newNode->data = 0;
        return newNode;
    }

### 【3.3】带头双向循环链表开辟节点空间 ###

// 双向带头循环链表 - 开辟节点函数。
    DHListNode* BuyDHListNode(DHLDataType val)
    {
        DHListNode* newNode = (DHListNode*)malloc(sizeof(DHListNode));
        // 判断是否开辟内存空间成功。
        if (newNode == NULL)
        {
            perror("ListInit malloc fail!");
            exit(-1);
        }
    
        // 程序走到这里说明开辟空间成功了。
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->data = val;
        return newNode;
    
    }

### 【3.4】带头双向循环链表销毁 ###

// 双向带头循环链表 - 内存销毁函数声明。
    void DHListDestory(DHListNode* pHead)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
    
        // 遍历一个一个的进行销毁。
        DHListNode* pBegin = pHead->next;
        while (pBegin != pHead)
        {
            DHListNode* next = pBegin->next;
            free(pBegin);
            pBegin = NULL;
    
            // 迭代
            pBegin = next;
        }
    
        // 其实这里是无效的，因为传递的是一级指针，外部调用完进行置NULL；
        pHead = NULL;
    }

### 【3.5】带头双向循环链表头插 ###

![d4e536570e0f49f9927dae017d37d864.png][]

// 双向带头循环链表 - 头插函数。
    void DHListPushFront(DHListNode* pHead, DHLDataType val)
    {   
        // 断言保护形参指针不为空。
        assert(pHead);
    
        /*
        // 开辟新的节点空间。
        DHListNode* newNode = BuyDHListNode(val);
    
        // 链接链表 - 指针交换。
        DHListNode* next = pHead->next;
    
        pHead->next = newNode;
        newNode->prev = pHead;
    
        newNode->next = next;
        next->prev = newNode;
        */
    
        DHListInsert(pHead->next, val);
    }

### 【3.6】带头双向循环链表尾插 ###

![5bc807450d5a4b86b4bc4d58dda9a261.png][]

// 双向带头循环链表 - 尾插函数。
    void DHListPushBack(DHListNode* pHead, DHLDataType val)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
    
        /*
        // 开辟新的节点空间。
        DHListNode* newNode = BuyDHListNode(val);
    
        // 链接链表 - 指针交换。
        DHListNode* pTail = pHead->prev;
        pTail->next = newNode;
    
        newNode->next = pHead;
        newNode->prev = pTail;
    
        pHead->prev = newNode;
        */
    
        DHListInsert(pHead, val);
    }

### 【3.7】 带头双向循环链表头删 ###

![eb374acf582d40928b3ef733fab3ba27.png][]

// 双向带头循环链表 - 头删函数。
    void DHListPopFront(DHListNode* pHead)
    {
        // 断言保护形参指针不为空，判断链表不为空。
        assert(pHead);
        assert(!DHListEmpty(pHead));
    
        /*
        DHListNode* pFirst = pHead->next;
        DHListNode* pSecond = pFirst->next;
    
        // 修改链接。
        pHead->next = pSecond;
        pSecond->prev = pHead;
        // 释放掉保留的最后一个节点。
        free(pFirst);
        pFirst = NULL;
        */
    
        DHListErase(pHead->next);
    }

### 【3.8】 带头双向循环链表尾删 ###

![654a512b1e6c42f693eb3ccfed13bb44.png][]

// 双向带头循环链表 - 尾删函数。
    void DHListPopBack(DHListNode* pHead)
    {
        // 断言保护形参指针不为空，判断链表不为空。
        assert(pHead);
        assert(!DHListEmpty(pHead));
    
        /*
        DHListNode* pTail = pHead->prev;
        DHListNode* pFirst = pTail->prev;
    
        // 修改链接。
        pHead->prev = pFirst;
        pFirst->next = pHead;
        // 释放掉保留的最后一个节点。
        free(pTail);
        pTail = NULL;
        */
    
        DHListErase(pHead->prev);
    }

### 【3.9】带头双向循环链表在pos位置插 ###

![1b2f9c4b1a1f4d6c86c38bd709875974.png][]

// 双向带头循环链表 - 在任意位置前插函数声明。
    void DHListInsert(DHListNode* pos, DHLDataType val)
    {
        // 断言保护形参指针不为空。
        assert(pos);
    
        // 定位置和开辟新节点。
        DHListNode* prev = pos->prev;
        DHListNode* newNode = BuyDHListNode(val);
    
        // 链接
        prev->next = newNode;
    
        newNode->prev = prev;
        newNode->next = pos;
    
        pos->prev = newNode;
    
    }

### 【3.10】带头双向循环链表在pos位置删 ###

![f6616b8235174d1e8d6d6939c981b3ac.png][]

// 双向带头循环链表 - 在任意位置前删函数声明。
    void DHListErase(DHListNode* pos)
    {
        // 断言保护形参指针不为空。
        assert(pos);
    
        // 定位置
        DHListNode* prev = pos->prev;
        DHListNode* next = pos->next;
    
        // 链接
        prev->next = next;
        next->prev = prev;
        //销毁pos节点
        free(pos);
        pos = NULL;
    }

### 【3.11】 无头单向非循环链表查找 ###

// 双向带头循环链表 - 查找节点函数。
    DHListNode* DHListFind(DHListNode* pHead, DHLDataType val)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
    
        // 遍历所有节点统计大小
        DHListNode* pBegin = pHead->next;
        while (pBegin != pHead)
        {
            if (pBegin->data == val)
            {
                return pBegin;
            }
    
            pBegin = pBegin->next;
        }
        // 返回NULL
        return NULL;
    }

### 【3.12】 无头单向非循环链表返回大小 ###

// 双向带头循环链表 - 统计节点个数空函数。
    size_t DHListSize(DHListNode* pHead)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
    
        // 遍历所有节点统计大小
        DHListNode* pBegin = pHead->next;
        size_t count = 0;
        while (pBegin != pHead)
        {
            count++;
            pBegin = pBegin->next;
        }
        // 返回个数
        return count;
    }

### 【3.13】 无头单向非循环链表打印 ###

// 双向带头循环链表 - 打印函数。
    void DHListPrint(DHListNode* pHead)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
        // 打印一个头作为标志。
        printf("pHead");
    
        // 遍历节点打印数据
        DHListNode* pBegin = pHead->next;
        while (pBegin != pHead)
        {
            printf("<-%d->",pBegin->data);
            pBegin = pBegin->next;
        
        }
        printf("pHead");
        printf("\n");
    }

### 【3.14】 无头单向非循环链表判空 ###

// 双向带头循环链表 - 判断链表是否为空函数。
    bool DHListEmpty(DHListNode* pHead)
    {
        // 断言保护形参指针不为空。
        assert(pHead);
    
        // 判断链表是不是NULL链表。
        return pHead->next == pHead;
    }

[d67e6f0715444c058605005c9b7347dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6d62e36a72ad4e0897f1c9382d1c06df.png
[7faf591f2af64de2af046c2fc19a2cf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e3c0b103270243c8b7f72d81ab9ed85b.png
[b7619049916b44e581a313e6328ad695.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8e4a00c346fe4fd09d585c4f929f494e.png
[15e0ebde0c4d46a38b33200d2312c6db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3210ca45e903492f9bd51865abb67ce4.png
[d5570df5e1ba498b88ed0c2a7ca2adbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c15045a16bc846de93677ee657a69917.png
[ece5f30045ff4792badf0d487a33252e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/17078e39aa694f2daf370548b510049b.png
[e6568633104c4cf38f5bd51404345c89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8f43fd4034bb4cf0820e2747fbb6fc31.png
[d4e536570e0f49f9927dae017d37d864.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/228b19ce3cc5482e9b59d194946cc5c9.png
[5bc807450d5a4b86b4bc4d58dda9a261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f7a760417c994dd1b373d9383fce21c6.png
[eb374acf582d40928b3ef733fab3ba27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9126d5898dc540b4a6bc3792c7dc8f15.png
[654a512b1e6c42f693eb3ccfed13bb44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f02a162b55e044b8a6db42d9885aa28f.png
[1b2f9c4b1a1f4d6c86c38bd709875974.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6a63c66ccf8a4fad9479d9ecd92a31e7.png
[f6616b8235174d1e8d6d6939c981b3ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b81f9a6158f34f35a6a3a987b24e8572.png