【C数据结构】无头非循环单向链表_SList

以你之姓@ 2024-03-16 20:09 35阅读 0赞

**目录**

无头非循环单向链表LinkedList

【1】链表概念

【2】链表分类

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

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

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

【3.3】无头单向非循环链表开辟节点空间

【3.4】无头单向非循环链表销毁

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

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

【3.7】 无头单向非循环链表在pos位置插

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

【3.9】 无头单向非循环链表尾删

【3.10】 无头单向非循环链表在pos位置删除

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

【3.12】 无头单向非循环链表修改

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

【2.14】 无头单向非循环链表大小

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

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

## 无头非循环单向链表LinkedList ##

## 【1】链表概念 ##

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

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

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

![1850e281d9af4578ba5077757fba5b15.png][]

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

## 【2】链表分类 ##

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

![d07f1897a5be4f5b90dbfaab9b18a035.png][]

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

![5c8d4f116b0d4657ac717f07f1161c87.png][]

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

![7c333704faa642e48cd55b314b78c720.png][]

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

![eb30fd04954d4835bd29e42eec191e59.png][]

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

**每个元素本身由两部分组成:**

*  存储数据的区域，称为“数据域"；
 *  指向直接后继的指针，称为“指针域”。

这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

由于每个结点中只包含一个指针域，生成的链表又被称为单链表。

![567a2b24c4ce44c8b8d462ca3b2d9f31.png][]

![45d13a440e24440aa0c74944c460c017.png][]

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

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

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <assert.h>
    
    /* 无头单向非循环链表数据结构 */
    typedef int SLTDataType;
    typedef struct SingleListNode{
        SLTDataType _data;              // 节点存储的数据.
        struct SingleListNode* _next;   // 节点中存储指向下一个节点的指针.
    }SListNode;
    
    /* 无头单向非循环链表开辟新节点接口 */
    SListNode* BuySingleListNode(SLTDataType val);
    
    /* 无头单向非循环链表销毁节点接口 */
    void SingleListDestory(SListNode** ppHead)
    
    /* 无头单向非循环链表初始化函数接口 */
    void SingleListInit(SListNode** ppHead);
    
    /* 无头单向非循环链表头插函数接口 */
    void SingleListPushFront(SListNode** ppHead, SLTDataType val);
    
    /* 无头单向非循环链表尾插函数接口 */
    void SingleListPushBack(SListNode** ppHead, SLTDataType val);
    
    /* 无头单向非循环链表指定位置插函数接口 */
    void SingleListInsert(SListNode** ppHead, SListNode* pPos ,SLTDataType val);
    
    /* 无头单向非循环链表头删函数接口 */
    void SingleListPopFront(SListNode** ppHead);
    
    /* 无头单向非循环链表尾删函数接口 */
    void SingleListPopBack(SListNode** ppHead);
    
    /* 无头单向非循环链表指定位置删函数接口 */
    void SingleListErase(SListNode** ppHead, SListNode* pPos);
    
    /* 无头单向非循环链表查找函数接口 */
    SListNode* SingleListFind(SListNode** ppHead, SListNode* pPos);
    
    /* 无头单向非循环链表修改函数接口 */
    void SingleListModification(SListNode** ppHead, SLTDataType ModifiSource, SLTDataType ModifiTarget);
    
    /* 无头单向非循环链表大小函数接口 */
    size_t SingleListSize(SListNode** ppHead);
    
    /* 无头单向非循环链表判空函数接口 */
    bool SingleListEmpty(SListNode** ppHead);
    
    /* 无头单向非循环链表打印函数接口 */
    void SingleListPrint(SListNode** ppHead);

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

/* 无头单向非循环链表初始化函数接口 */
    void SingleListInit(SListNode** ppHead){
        // 断言保护指针传参.
        assert(ppHead);
    
        (*ppHead)->_data = 0;
        (*ppHead)->_next = NULL;
    }

### 【3.3】无头单向非循环链表开辟节点空间 ###

开辟节点空间就是直接开辟一个节点空间，这里直接使用malloc这个函数就可以开辟了，开辟是主要返回的指针不能是空指针，所以要进行判断一下。

/* 无头单向非循环链表开辟新节点接口 */
    SListNode* BuySingleListNode(SLTDataType val) {
        // 开辟新的节点空间. 
        SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
        // 检测节点是否开辟成功.
        if(newNode == NULL) {
            perror("BuySingleListNode malloc fail!");
            exit(-1);
        }
    
        // 节点开辟成功，初始化节点状态，并返回节点.
        newNode->_data = val;
        newNode->_next = NULL;
        return newNode;
    }

### 【3.4】无头单向非循环链表销毁 ###

// 无头非循环单链表 - 内存销毁
    void SingleListDestory(SListNode** ppHead)
    {
        // 断言：保证指针变量是有效不为NULL的指针。
        assert(pSList);
    
        SListNode* pCur = *ppHead;
        while (pCur != NULL)
        {
            SListNode* pDel = pCur;
            pCur = pCur->next;
    
            free(pDel);
            pDel = NULL;
        }
    
        // 头指针指向NULL 
        *pSList->next = NULL;
        *pSList->data = 0;
        free(*pSList);
        *pSList = NULL;
    }

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

头插只需要将原来头结点中的指针域给新插入元素的指针域，然后再将新结点的地址给原来头结点的指针域即可。

![622b2a5ac044423981bd95d05d4b6ca1.png][]

/* 无头单向非循环链表头插函数接口 */
    void SingleListPushFront(SListNode** ppHead, SLTDataType val){
        // 断言保护指针传参.
        assert(ppHead);
    
        // 开辟新的节点.
        SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
         // 检测节点是否开辟成功.
        if(newNode == NULL){
            perror("SingleListPushFront malloc fail!");
            exit(-1);
        }
    
        // 为新节点赋值:
        newNode->_data = val;
        // 头插节点，进行链接：
        newNode->_next = *ppHead;
        *ppHead = newNode; 
    }

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

**尾插的话可能会分为两种情况：**

*  1、链表中有节点了
 *  2、链表中没有节点

![c5d35a08c2664f75865e5769cc263b95.png][]

/* 无头单向非循环链表尾插函数接口 */
    void SingleListPushBack(SListNode** ppHead, SLTDataType val){
        // 断言保护指针传参.
        assert(ppHead);
        // 开辟新的节点准备尾插.
        SListNode* newNode = BuySingleListNode(val);
        // 尾插分为两种情况：
        // 1、如果链表为空链表，那么新开的节点就是第一个节点.
        // 2、如果链表不为空链表，那么需要找到最后一个节点尾插到后面.
        SListNode* pTail = *ppHead;
        if(*ppHead == NULL){ // 空链表.
            pTail = newNode;
            *ppHead = pTail;
            return;
        }
    
        // 程序走到这里说明不是一个空链表,找到最后一个节点，插入数据.
        while(pTail->_next != NULL){
            pTail = pTail->_next;
        }
        // 尾插.
        pTail->_next = newNode;
    }

### 【3.7】 无头单向非循环链表在pos位置插 ###

对于单链表来说，在pos前插入数据是比较麻烦的，要找到pos之前的上一个数据，那就要从头进行便利了。

当然还有一种情况就是pos的位置正好在第一个节点的位置上，这时候可以直接头插入

*  **第一种情况：**

![c3e0df9ca2da4904b73d9639750ed5cf.png][]

*  **第二种情况：**

![cfb8ff2ea8e342f1a38b13b86d108709.png][]

/* 无头单向非循环链表指定位置插函数接口 */
    void SingleListInsert(SListNode** ppHead, SListNode* pPos ,SLTDataType val){
        // 断言保护指针传参.
        assert(ppHead);
        assert(pPos != NULL);
    
        // 指定位置插入有两种情况：
        // 1、pPos位置是头的位置，这时候只需要调用头插函数.
        // 2、pPos位置不是头的位置，这时候需要找到pPos的前一个节点，在pPos的前一个节点和pPos中间插入节点.
        if(pPos == *ppHead){
            SingleListPushFront(ppHead, val);
        }
        else { // 第二种情况.
            // 找到pPos的上一个节点.
            SListNode* pPrev = *ppHead;
            while(pPrev->_next != pPos){
                pPrev = pPrev->_next;
                // 防止外部给的指针是错的，找到NULL，说明没有要找的节点.
                assert(pPrev);
            }
    
            // 走到这里说明已经找到了pPos的上一个节点，新建节点，插入到中间. 
            SListNode* newNode = BuySingleListNode(val);
            pPrev->_next = newNode;
            newNode->_next = pPos;
            // newNode这个指针已经用完，把他指向空.
            newNode = NULL;   
        }
    }

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

链表在删除数据的时候要注意释放内存 先找一个指针保存一下pList的位置， pList指向下一个节点，free到之前pList指向的位置，还要注意的就是要注意如果链表空了就不能删除啦，否则就是引用NULL指针了。

![f951066e85cc470a90d42fa328c85dba.png][]

/* 无头单向非循环链表头删函数接口 */
    void SingleListPopFront(SListNode** ppHead){
        // 断言保护指针传参.
        assert(ppHead);
    
        // 检查链表是否是空链表.
        // 检查链表是否是空链表.
        if(SingleListEmpty(ppHead)) {
            printf("SingleList Empty!\n");
            return NULL;
        }
    
        // 保存头节点指针，对其进行删除，将ppHead指向下一个节点.
        SListNode* pDel = *ppHead;
        *ppHead = (*ppHead)->_next;
    
        // 释放节点.
        free(pDel);
        pDel = NULL;
    }

### 【3.9】 无头单向非循环链表尾删 ###

尾删的时候要注意1个节点的时候需要直接将这个节点free掉，如果是多个节点需要采用图序的方式进行删除 有两种解法。

*  **第一种解法：**

![50495dff4dfd4cf48a5e97cf6bfdbc4a.png][]

/* 无头单向非循环链表尾删函数接口 */
    void SingleListPopBack(SListNode** ppHead){
        // 断言保护指针传参.
        assert(ppHead);
        assert(*ppHead);
    
        // 尾删分为两种情况考虑：
        // 1、链表中只有一个节点.
        // 2、链表中有多个节点.
        if((*ppHead)->_next == NULL){   // 删除链表中的最后一个节点.
            free(*ppHead);
            *ppHead = NULL;
            return;
        }
    
        // 程序走到这里说明链表中有多个节点.
        // 需要找到最后一个节点和最后一个节点的上一个节点.
        SListNode* pTail = *ppHead;
        SListNode* pPrev = NULL;
        while (pTail->_next != NULL){
            pPrev = pTail;
            pTail = pTail->_next;
        }
        // 找到了对应的节点释放掉pTail节点，将pPrev节点的_next指向NULL.
        free(pTail);
        pTail = NULL;
    
        pPrev->_next = NULL;
    }

*  **第二种解法：**

![81d5cf4c33c7497ca83dd63bb3c19fa6.png][]

// 单链表尾删 - 函数声明
    void SListPopBack(SListNode** ppHead)
    {
        //  因为ppHead拿的是pList的地址，所以一定不为空。
        assert(ppHead);
        assert(*ppHead != NULL);
    
        // 尾删要分为：
        // 1个节点和多个节点
        if ((*ppHead)->next == NULL)
        {
            free(*ppHead);
            *ppHead = NULL;
        }
        else
        {
            // 寻找尾巴上的节点。
            SListNode* tail = *(ppHead);
            while (tail->next->next != NULL)
            {
                tail = tail->next;
            }
    
            // 程序走到这里说明找到了尾巴上的那个节点。
            free(tail->next);
            tail->next = NULL;
        }
    }

### 【3.10】 无头单向非循环链表在pos位置删除 ###

在pos位置删除实际和上面的代码本质有点相似！

*  **第一种情况：**

![cdd592aebfc948aa9f5960e72cc59fe9.png][]

*  **第二种情况：**

![a2546644290b43288cb35fe2ab224de6.png][]

/* 无头单向非循环链表指定位置删函数接口 */
    void SingleListErase(SListNode** ppHead, SListNode* pPos){
        //  因为ppHead拿的是pList的地址，所以一定不为空。
        assert(ppHead);
        assert(pPos);   // pos的位置不能为空。
    
        // 检查链表是否是空链表.
        if(SingleListEmpty(ppHead)) {
            printf("SingleList Empty!\n");
            return;
        }
    
        // 判断如果只有一个节点的时候,调用头删函数
        if (pPos == *ppHead)
            SingleListPopFront(ppHead);
        else
        {
            // 移动到pos的前一个位置。
            SListNode* prev = *ppHead;
            while (prev->_next != pPos)
            {
                prev = prev->_next;
    
                // 如果prev一直在往前走，走到空的位置，说明所有的节点中都没有要删除的数据。
                assert(prev);
            }
    
            // 程序跑到这里说明已经找到了要删除的数据。
            SListNode* pTemp = pPos;
            prev->_next = pPos->_next;
            free(pTemp);
            pTemp = NULL;
        }
    }

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

查找的函数比较简单不解释：

当然查找其实还可以充当一些别的功能，比如：修改、某个位置插入、某个位置删除

/* 无头单向非循环链表查找函数接口 */
    SListNode* SingleListFind(SListNode** ppHead, SLTDataType val){
        // 断言保护指针传参.
        assert(ppHead);
    
        // 检查链表是否是空链表.
        if(SingleListEmpty(ppHead)) {
            printf("SingleList Empty!\n");
            return NULL;
        }
        // 遍历查找和Val相同的值.
        SListNode* pCur = *ppHead;
        while(pCur != NULL){
            if(pCur->_data == val)
                return pCur;
            pCur = pCur->_next;
        }
    
        // 在上面循环中如果为找打val值的节点，说明没有该节点，返回NULL节点.
        return NULL;
    }

### 【3.12】 无头单向非循环链表修改 ###

/* 无头单向非循环链表修改函数接口 */
    void SingleListModification(SListNode** ppHead, SLTDataType ModifiSource, SLTDataType ModifiTarget){
        // 断言保护指针传参.
        assert(ppHead);
        // 查找节点.
        SListNode* finNode = SingleListFind(ppHead, ModifiSource);
        if(finNode != NULL){
            finNode->_data = ModifiTarget;
        }
    }

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

/* 无头单向非循环链表打印函数接口 */
    void SingleListPrint(SListNode** ppHead){
        // 断言保护指针传参.
        assert(ppHead);
    
        // 检查链表是否是空链表.
        if(SingleListEmpty(ppHead)) {
            printf("SingleList Empty!\n");
            return;
        }
        // 这里不要动pHead这个指针，因为这个指针一动就找不到链表的头的位置了。
        SListNode* pCur = *ppHead;
        printf("Head->");
        // 循环到NULL指针.
        while(pCur != NULL) {
            printf("%d->", pCur->_data);
            pCur = pCur->_next;
        }
        printf("NULL\n");
    }

### 【2.14】 无头单向非循环链表大小 ###

/* 无头单向非循环链表大小函数接口 */
    size_t SingleListSize(SListNode** ppHead){
        // 断言保护指针传参.
        assert(ppHead);
    
        // 遍历计数.
        SListNode* pCur = *ppHead;
        size_t count = 0;
        // 循环到NULL指针.
        while(pCur != NULL) {
            ++count;
            pCur = pCur->_next;
        }
        
        return count;
    }

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

/* 无头单向非循环链表判空函数接口 */
    bool SingleListEmpty(SListNode** ppHead){
         // 断言保护指针传参.
        assert(ppHead);
    
        // 如果对ppHead二级指针解引用，指向的是NULL，说明没有节点了.
        return (*ppHead) == NULL;
    }

[1850e281d9af4578ba5077757fba5b15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/77bab0c495fd4a288ad2e610b6d2a116.png
[d07f1897a5be4f5b90dbfaab9b18a035.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/88ff7cddf1984ccb8ee87d1d4d19bc3c.png
[5c8d4f116b0d4657ac717f07f1161c87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e1045e4516364cdbbcfdfdf8b5290bd3.png
[7c333704faa642e48cd55b314b78c720.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a1bc1c03c5874383801ad2875a37ba3b.png
[eb30fd04954d4835bd29e42eec191e59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c301cd08c6b84604b98ad221ec7ed9df.png
[567a2b24c4ce44c8b8d462ca3b2d9f31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/37f20afa015243f78e01726d3e1b3f4d.png
[45d13a440e24440aa0c74944c460c017.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9278cf90572e470e844c8d4f5c111c56.png
[622b2a5ac044423981bd95d05d4b6ca1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/93c392d4e8aa46b5aa6cdf0c666b8e9e.png
[c5d35a08c2664f75865e5769cc263b95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/821c30020c1447e8939a634d4c1826e0.png
[c3e0df9ca2da4904b73d9639750ed5cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b566f359c66b4fc9be43efea66988384.png
[cfb8ff2ea8e342f1a38b13b86d108709.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4001d908537d421585f1cbe2abdfd824.png
[f951066e85cc470a90d42fa328c85dba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/51b821d7f8844e98a4f4ebb2446df817.png
[50495dff4dfd4cf48a5e97cf6bfdbc4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/aa255d92f702458d938530163dff5c2b.png
[81d5cf4c33c7497ca83dd63bb3c19fa6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bd4e7e9560f9455c9d2e9c753ac8f161.png
[cdd592aebfc948aa9f5960e72cc59fe9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2f0f2668c8a8468caec979e74f101dc1.png
[a2546644290b43288cb35fe2ab224de6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5ae523b673824e29ab72c5cceeb51b3a.png