【C数据结构】带头单向非循环链表_HList

蔚落 2024-03-16 20:10 61阅读 0赞

**目录**

带头单向非循环链表\_HList

【1】链表概念

【2】链表分类

【3】有头单向非循环链表

【3.1】非循环链表数据结构与接口定义

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

【3.3】带头单向非循环链表释放空间

【3.4】带头单向非循环链表创建节点

【3.5】带头单向非循环链表头插

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

【3.7】带头单向非循环链表头删

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

【3.9】带头单向非循环链表指定位置插入

【3.10】带头单向非循环链表指定位置删除

【3.11】带头单向非循环链表打印

【3.12】带头单向非循环链表查找

【3.13】带头单向非循环链表修改

【3.14】带头单向非循环链表获取大小

【3.15】带头单向非循环链表判断空

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

## 带头单向非循环链表\_HList ##

## 【1】链表概念 ##

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

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

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

![ab23abad62a742efaf16142528a26494.png][]

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

## 【2】链表分类 ##

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

![e0d421bafdaf42a9ab8a215715b0fa8d.png][]

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

![5f42be701dde4a919ab962d13e299841.png][]

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

![04eb0bcf505d460a8aabb6a75435bbf7.png][]

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

![5b7bbdbdc2f5454c9c7274748444b0b1.png][]

## 【3】有头单向非循环链表 ##

**头结点：**有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

**首元结点：**链表中第一个元素所在的结点，它是头结点后边的第一个结点。

**头指针：**永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

![ae539bf3c1f04a4784cc225ade5eaaf0.png][]

### 【3.1】非循环链表数据结构与接口定义 ###

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

#pragma once 
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <assert.h>
    
    // 带头单链表：数据结构.
    typedef int HSListDataType;
    typedef struct HSList
    {
        HSListDataType _data;
        struct HSList* _next;
    }HSList;
    
    typedef struct HSListHead
    {
        size_t _size;
        struct HSList* _next;
    }HSListHead;
    
    
    // 带头单链表：初始化.
    void HSListInit(HSListHead* pHead);
    
    // 带头单链表：释放内存空间.
    void HSListDestory(HSListHead* pHead);
    
    // 带头单链表：创建节点.
    HSList* HSListBuyNewNode(HSListDataType val);
    
    // 带头单链表：头插.
    void HSListPushFront(HSListHead* pHead, HSListDataType val);
    
    // 带头单链表：尾插.
    void HSListPushBrack(HSListHead* pHead, HSListDataType val);
    
    // 带头单链表：头删.
    void HSListPopFront(HSListHead* pHead);
    
    // 带头单链表：尾删.
    void HSListPopBrack(HSListHead* pHead);
    
    // 带头单链表：指定位置插.
    void HSListInsert(HSListHead* pHead, HSList* pos, HSListDataType val);
    
    // 带头单链表：指定位置删.
    void HSListErase(HSListHead* pHead, HSList* pos);
    
    // 带头单链表：打印.
    void HSListPrint(HSListHead* pHead);
    
    // 带头单链表：查找.
    HSList* HSListFind(HSListHead* pHead, HSListDataType val);
    
    // 带头单链表：修改.
    void HSListModified(HSListHead* pHead, HSList* pos, HSListDataType val);
    
    // 带头单链表：大小.
    size_t HSListSize(HSListHead* pHead);
    
    // 带头单链表：大小.
    bool HSListEmpty(HSListHead* pHead);

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

// 带头单链表：初始化.
    void HSListInit(HSListHead* pHead) {
        assert(pHead);
    
        pHead->_next = NULL;
        pHead->_size = 0;
    }

### 【3.3】带头单向非循环链表释放空间 ###

// 带头单链表：释放内存空间.
    void HSListDestory(HSListHead* pHead) {
        assert(pHead);
    
        HSList* curNode = pHead->_next;
        while (NULL != curNode) {
            HSList* delNode = curNode;
            curNode = curNode->_next;
    
            free(delNode);
            delNode = NULL;
        }
        pHead->_size = 0;
    }

### 【3.4】带头单向非循环链表创建节点 ###

// 带头单链表：创建节点.
    HSList* HSListBuyNewNode(HSListDataType val) {
        // 创建节点.
        HSList* newNode = (HSList*)malloc(sizeof(HSList));
        if (NULL == newNode)
        {
            perror("malloc fail!");
            exit(-1);
        }
    
        // 节点开辟成功，返回新的节点.
        newNode->_data = val;
        newNode->_next = NULL;
        return newNode;
    }

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

// 带头单链表：头插.
    void HSListPushFront(HSListHead* pHead, HSListDataType val) {
        assert(pHead);
        
        // 开启新的节点.
        HSList* newNode = HSListBuyNewNode(val);
        // 链接.
        newNode->_next = pHead->_next;
        pHead->_next = newNode;
        // 记录节点个数.
        ++pHead->_size;
    }

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

// 带头单链表：尾插.
    void HSListPushBrack(HSListHead* pHead, HSListDataType val) {
        assert(pHead);
    
        // 判断链表中有没有节点.
        if (NULL == pHead->_next)
            HSListPushFront(pHead, val);
        else {
            // 找到最后一个节点，进行尾插链接.
            HSList* tailNode = pHead->_next;
            while (NULL != tailNode->_next)
                tailNode = tailNode->_next;
    
            // 开启新的节点.
            tailNode->_next = HSListBuyNewNode(val);
            // 记录节点个数.
            ++pHead->_size;
        }
    }

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

// 带头单链表：头删.
    void HSListPopFront(HSListHead* pHead) {
        assert(pHead);
    
        if (HSListEmpty(pHead))
            return;
        else {
            // 找到最后一个节点进行删除.
            HSList* delNode = pHead->_next;
            pHead->_next = delNode->_next;
    
            free(delNode);
            delNode = NULL;
            // 记录节点个数.
            --pHead->_size;
        }
    }

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

// 带头单链表：尾删.
    void HSListPopBrack(HSListHead* pHead) {
        assert(pHead);
    
        if (HSListEmpty(pHead)) 
            return;
        else {
            HSList* prevNode = pHead->_next;
            if (NULL == prevNode->_next)
                HSListPopFront(pHead);
            else {
                HSList* delNode = prevNode->_next;
                while (NULL != delNode->_next) {
                    prevNode = delNode;
                    delNode = delNode->_next;
                }
                free(delNode);
                delNode = NULL;
                prevNode->_next = NULL;
    
                // 记录节点个数.
                --pHead->_size;
            }
        }
    }

### 【3.9】带头单向非循环链表指定位置插入 ###

// 带头单链表：指定位置插.
    void HSListInsert(HSListHead* pHead, HSList* pos, HSListDataType val) {
        assert(pHead);
        assert(pos);
    
        if (pHead->_next == pos) {
            HSListPushFront(pHead, val);
        }
        else {
            // 找到pos的上一个节点，并且链接起来.
            HSList* prevNode = pHead->_next;
            while (prevNode->_next != pos) {
                prevNode = prevNode->_next;
                if (prevNode == NULL)
                {
                    printf("未找到要插入的位置！");
                    exit(-1);
                }
            }
    
            // 创建节点，并且插入进去.
            HSList* newNode = HSListBuyNewNode(val);
            newNode->_next = pos;
            prevNode->_next = newNode;
            // 记录节点个数.
            ++pHead->_size;
        }
    }

### 【3.10】带头单向非循环链表指定位置删除 ###

// 带头单链表：指定位置删.
    void HSListErase(HSListHead* pHead, HSList* pos) {
        assert(pHead);
        assert(pos);
    
        // 判断是否是空链表.
        if (HSListEmpty(pHead))
            return;
        else {
            if (pHead->_next == pos) {
                HSListPopFront(pHead);
            }
            else {
                // 找到pos的上一个节点，并且链接起来.
                HSList* prevNode = pHead->_next;
                while (prevNode->_next != pos) {
                    prevNode = prevNode->_next;
                    if (prevNode == NULL)
                    {
                        printf("未找到要删除的位置！");
                        exit(-1);
                    }
                }
    
                // 删除pos节点.
                HSList* delNode = pos;
                prevNode->_next = pos->_next;
                free(delNode);
                delNode = NULL;
                // 记录节点个数.
                ++pHead->_size;
            }
        }
    
    }

### 【3.11】带头单向非循环链表打印 ###

// 带头单链表：打印.
    void HSListPrint(HSListHead* pHead) {
        assert(pHead);
    
        printf("Head->");
        HSList* pCurrent = pHead->_next;
        while (pCurrent != NULL) {
            printf("%d->", pCurrent->_data);
            pCurrent = pCurrent->_next;
        }
        printf("NULL\n");
    }

### 【3.12】带头单向非循环链表查找 ###

// 带头单链表：查找.
    HSList* HSListFind(HSListHead* pHead, HSListDataType val) {
        assert(pHead);
    
        HSList* curNode = pHead->_next;
        while (curNode != NULL) {
            if (curNode->_data == val)
                return curNode;
    
            curNode = curNode->_next;
        }
    
        return NULL;
    }

### 【3.13】带头单向非循环链表修改 ###

// 带头单链表：修改.
    void HSListModified(HSListHead* pHead, HSList* pos, HSListDataType val) {
        assert(pHead);
        assert(pos);
    
        pos->_data = val;
    }

### 【3.14】带头单向非循环链表获取大小 ###

// 带头单链表：大小.
    size_t HSListSize(HSListHead* pHead){
        assert(pHead);
        return pHead->_size;
    }

### 【3.15】带头单向非循环链表判断空 ###

// 带头单链表：空.
    bool HSListEmpty(HSListHead* pHead) {
        assert(pHead);
        return pHead->_size == 0;
    }

[ab23abad62a742efaf16142528a26494.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3106540f155947db8850f1b9ea9b30d9.png
[e0d421bafdaf42a9ab8a215715b0fa8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6c30ded48dea4f178d84da11d5f3196b.png
[5f42be701dde4a919ab962d13e299841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c78543df34bd49f195dc98cc734aa2c5.png
[04eb0bcf505d460a8aabb6a75435bbf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/36bfe88897874f21a7b7dbeb6ce592e0.png
[5b7bbdbdc2f5454c9c7274748444b0b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2bad957cb9814a00ba7c984c9749cb31.png
[ae539bf3c1f04a4784cc225ade5eaaf0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/01424cee451d441e83861307c4f34b28.png