c++ 非空指针写入访问权限冲突_数据结构·链表（C实现）

深藏阁楼爱情的钟 2023-01-08 01:18 106阅读 0赞

1、前言

《数据结构》是每个程序猿都应该掌握的“必修课”，是一门研究“计算机如何存储、数组数据方式”的学科。它虽不及其他招式花哨、但却总能在关键时刻成为”必杀技”，给人致命一击。熟练掌握《数据结构》，能够间接、明显地提升你的编码技能与思维；同时，还能加速定位问题、解决问题的能力。“数据结构”中常见的类型有：数组、链表、栈、队列、图、树、堆和散列表。

![94134678d5778e643480c4041ceb4dab.png][]

▲ 数据结构中常见数据类型

不同的数据结构类型均有自己独特的数据存储方式，以及优缺点。在擅长的方面，能够大显神威，发挥出光与热；而在不足面，则显得捉襟见肘，毫无缚鸡之力。这也正是学习《数据结构》的必要性与重要性。你永远不希望看到在数组中进行大量的随机插入与删除数据操作，那将是一场噩梦与浩劫。

2、链表

链表在数据结构中的角色，举足轻重，同时也是使用较为广泛的一种基础数据结构。任何一款C编写的成熟开源软件，必定会用到“链表”，或许单链表、双链表、单循环链表、双循环链表等。它是一种线性表，所谓线性表（linear list），即n个具有相同特性的数据元素的有限序列。即：

L = （a1，a2，a3，a4， a5， · · ·， an）

其中L表示线性表的名称。而该线性表L中的所有数据元素的集合（这里有n个）称为“线性表长度”。若n为0， 则表示“空表”。若线性表L非空，则ai称为线性表L的第i个元素。下标索引i称为元素ai的位序；元素a1~ai-1称为ai的前驱，其中ai-1是ai的直接前驱；ai+1~an是ai的后继，其中ai+1是直接后继。第一个元素（a1）没有前驱,最后一个元素没有后继(an)。

线性表的存储方式有两种，分别是顺序存储与链式存储。顺序存储方式，线性表L种的n个元素按照其逻辑顺序依次存储在内存地址连续的单元中。而链式存储，则其逻辑上顺序的元素，存储到内存单元中后，其地址可以是连续，也可以是随机的。在这里，我们主攻线性表的链式存储。链式存储相较于顺序存储，主要有两方面优势：  
（1）. 数据的删除与插入极其便利，仅需移动指针的指向即可。具有高效率的重排节点（数据项）的能力。

（2）. 不需预先分配空间大小；调整链表中的节点顺序方便。

但是链表也有缺点、极限，比如它不擅长删除、获取、访问指定序号的元素，换言之，快速访问链表中的任意节点（数据项）是它的短板。每一次的操作，都需要从头（头结点）进行变量，知道链表的尾节点的指针域为空为止。在特性方面，它和数组互补。

2.1 链表的定义

在《算法：C语言实现》一书的3.3章节，对链表作了以下的定义：

链表是一个空表，或是一个指向节点的链接，且这个节点包含一个元素和一个指向链表的链接。

![ecca6f6e40cc2f594fc5fd16f7333d40.png][]

也就是说，链表中的节点，包括两部分，一部分是存储数据（数据域），另外一部分是存储指针（指针域），该指针用于指向相同元素类型的下一个节点。最为简单的链表是单向链表，简称“单链表”，即该节点中，除了数据域外，仅有一条指向直接后继元素的指针。上图中的节点定义就是单链表。

链表使用结构体来封装表示。如下：

typedef int INT;
    typedef struct node{
         
        struct node *next; //指针域
        INT data;          //数据域
    }SingleLinkerList;

之前看到有网友咨询为什么 struct node结构体声明内部的指针next不可以换为变量定义呢？即：

typedef int INT;
    typedef struct node{
         
        struct node next;  //指针变量
        INT data;          //数据域
    }SingleLinkerList;

这是因为对于struct node结构体类型的声明，在next位置处，该结构还未声明完成，因此struct node在这个位置是一个“不完整类型”，即暂时不能确定大小的类型。详情可参考《不完整类型》。所以next在这里必须是指针类型，因为指针类型的大小是可以确认的，32位处理器平台上面是4字节，64位上面8字节。

单链表的节点类型以及声明，接下来就是如何使用这个节点类型去创建一个不为空的单链表。对于单链表，常见的操作是：

创建一个单链表、获取该单链表的长度、获取指定位置的元素、删除单链表中指定元素、删除整个单链表、定位操作、输出操作以及指定位置插入元素等。

2.1.2 创建一个单链表

对于链表节点中的“数据域”，它可以是一个简单的基础数据类型（char、 int、float、double等），也可以任何有意义的复杂数据类型（指针、其他类型的结构体、枚举、共用体等）。本次示例的链表，节点中的“数据域”用来表示一个班级的学生基本信息，如：姓名、性别、年龄、班级、家庭住址。因为事先不知道一个班级会有多少学生，因此这里无法使用结构体数组类型。StudentInfo 结构体数据类型用于表示一位学生的基本属性信息。下面链表的所有操作均以StudentInfo和 SingleLinkerList作为基础数据类型。

typedef int INT;
    
    typedef struct Student
    {
         
        char cName[20];         //姓名
        char cGender;           //性别
        INT  iAge;              //年龄
        INT  iClass;            //班级
        char cAddress[20];      //住址
    }StudentInfo;
    
    typedef struct node{
         
        struct node *next;          //指针域
        StudentInfo strStuInfo;     //数据域
    }SingleLinkerList;

基于简易原则，这里创建指定数量的链表节点。createSingleLinkList

根据参数 iStudentNum 的大小，创建指定数量的节点。由一个头结点（哑元节点）来指向这个链表。通过访问这个头结点，可以遍历操作创建的指定链表。

![493745f03d5ed3c371b574ae5db39e3f.png][]

▲ 创建待头结点的单链表

/*
     * fn:      createSingleLinkList
     * desc:    创建一个带头结点的单链表
     * date:    2020/11/25/23:30:13
     * author:  lixiaogang5
    */
    SingleLinkerList *createSingleLinkList(const INT *iStudentNum)
    {
         
        //创建一个带头节点的单链表
        SingleLinkerList *pHead = NULL, *pData = NULL, *pNext = NULL;
        pHead = pNext = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
        assert(pHead);
    
        pHead->next = NULL;
        memset(&pHead->strStuInfo, 0x00, sizeof(pHead->strStuInfo));
        for(unsigned i = 0; i < *iStudentNum; i++)
        {
         
            pData = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
            assert(pData);
            char buf[20] = {
         0};
            snprintf(buf, sizeof(buf), "name_%d", i);
            strncpy(pData->strStuInfo.cName, buf, strlen(buf));
    
            pData->strStuInfo.cGender = (i % 2)?'M':'G';
            pData->strStuInfo.iAge = 20 + i;
            pData->strStuInfo.iClass = i;
    
            memset(buf, 0x00, sizeof(buf));
            snprintf(buf, sizeof(buf), "address_%d", i);
            strncpy(pData->strStuInfo.cAddress, buf, strlen(buf));
    
            //移动指针，使其指向新创建的节点
            pNext->next = pData;
            pNext = pData;
        }
    
        pNext->next = NULL;
        return pHead;
    }

**2.1.3 遍历访问带头结点的单链表**

TraverseOutPut 函数遍历访问指定的带头结点的单链表。根据头结点中的指针域的值，进行条件判，当不为空的时候，继续遍历访问下一个结点；若为空，则结束访问。

/*
     * fn:      TraverseOutPut
     * desc:    遍历输出带头结点的单链表
     * date:    2020/11/25/23:34:42
     * author:  lixiaogang5
    */
    void *TraverseOutPut(const SingleLinkerList *pSingleLinkeList)
    {
         
        assert(pSingleLinkeList);
        const SingleLinkerList *pHead = pSingleLinkeList->next;
        while(pHead)
        {
         
            printf("name: [%s], gender:[%c], age:[%d], class:[%d], address:[%s]n",
                   pHead->strStuInfo.cName, pHead->strStuInfo.cGender, pHead->strStuInfo.iAge,
                   pHead->strStuInfo.iClass, pHead->strStuInfo.cAddress);
            pHead = pHead->next;
        }
    }

L用于表示该单链表，其中第一个结点，即为头结点。头结点中的数据项一般为空，也可以填充数据，通常情况下，可以将该链表的长度实时更新到这个结点中的数据成员里面。它仅用来唯一标识、指向一个链表。首先定义一个临时的指针pHead，指向单链表的头结点，若头结点中存在直接后继结点（则表示链表不为空），则遍历打印该直接后继结点；同时移动临时指针，使其指向该直接后继结点；接着判断该直接后继结点的指针域是否为空，若不为空，则继续上面的过程。

![012b9bfd602c18ff719b8a5533541d43.png][]

遍历访问带头结点的单链表

本示例中:

第一个结点的数据项中其内容分别是：

name\_0，'G'，20，0，address\_0

第二个结点的数据项中其内容分别是：

name\_1， 'M'，21,1，address\_1

以此类推。

**2.1.4 获取带头结点的单链表的长度**

获取单链表的长度，即遍历统计该单链表中（除头结点外）所有的结点数量。若除了头结点外，无其他结点，则该链表长度为0，反之则统计其结点个数。其遍历过程与2.1.3节的规则相同。

/*
     * fn:      GetLengthOfSingleLinkList
     * desc:    获取带节点的单链表长度
     * date:    2020/11/25/23:40:16
     * author:  lixiaogang5
    */
    INT GetLengthOfSingleLinkList(const SingleLinkerList *pSingleLinkeList)
    {
         
        assert(pSingleLinkeList);
        INT iNodeNum = 0;
        const SingleLinkerList *pHead = pSingleLinkeList;
        while(pHead->next)
        {
         
            iNodeNum++;
            pHead = pHead->next;
        }
    
        return iNodeNum;
    }

![012b9bfd602c18ff719b8a5533541d43.png][]

获取带头结点链表的长度

**2.1.5 链表指定位置插入新结点**

带头结点的链表中，在指定位置处插入结点时候；需要先判断该指定位置是否合理有效。然后定义一个临时的指针指向该链表中的头结点，同时定义一个临时变量用于表示访问的节点数。当且仅当指向头结点的指针存在直接后继（即非空链表）结点时，并且结点索引小于指定位置时候，才一直向下遍历，同时更新指针指向。

这时候可能出现两种情况：

（1）指定插入位置刚好是该链表中的最后一个节点处。

![87bf42dbbde2e59701f11dcf403f4c62.png][]

▲ 指定插入结点位置，位于链表尾部

若是这种情况，则直接将最后一个节点的指针域指向新创建的 pNewStudentInfo节点中，然后将新结点pNewStudentInfo中的指针域置为空（NULL）。

（2）指定位置处于链表的（除链表头和尾部）的中间某个位置

此情况是最为常见，这时候，需要将指向头结点的临时指针遍历指向待插入结点位置iIndex的前一个结点位置处（即iIndex-1）。

![360a76998fffa17efa02a3ae476d4893.png][]

▲ 指定插入结点位置，位于链表中间某位置处

/*
     * fn:      SpecifiesWhereToInsertData
     * desc:    在带头节点单链表的指定位置插入一个新节点
     * date:    2020/11/25/23:46:10
     * author:  lixiaogang5
    */
    void SpecifiesWhereToInsertData(const INT *iIndex, const StudentInfo *pOneStuInfo, SingleLinkerList *pHeadLinkeList)
    {
         
        assert(pHeadLinkeList || iIndex || pOneStuInfo || *iIndex >= 1);
    
        INT iLocation = 0;
        SingleLinkerList *pHead = pHeadLinkeList;
    
        //若指定位置超过了链表的长度范围,则不允许插入.
        assert(*iIndex <= GetLengthOfSingleLinkList(pHeadLinkeList));
    
        while(pHead && iLocation <= *iIndex - 1) pHead = pHead->next, iLocation++;
    
        SingleLinkerList *pNewStudentInfo = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
        assert(pNewStudentInfo);
        strncpy(pNewStudentInfo->strStuInfo.cName, pOneStuInfo->cName, sizeof(pNewStudentInfo->strStuInfo.cName));
        pNewStudentInfo->strStuInfo.cGender = pOneStuInfo->cGender;
        pNewStudentInfo->strStuInfo.iAge    = pOneStuInfo->iAge;
        pNewStudentInfo->strStuInfo.iClass  = pOneStuInfo->iClass;
        strncpy(pNewStudentInfo->strStuInfo.cAddress, pOneStuInfo->cAddress, sizeof(pNewStudentInfo->strStuInfo.cAddress));
    
        //若为尾节点位置, 则将新节点数据追加到链表末尾.
        if(!pHead){
         
            pHead->next = pNewStudentInfo;
            pNewStudentInfo->next = NULL;
        }
    
        pNewStudentInfo->next = pHead->next;
        pHead->next = pNewStudentInfo;
    }

**2.1.6 删除链表中指定位置的结点**

根据参数（iIndex）指定位置，首先进行合法性判断。删除某个结点需要用到两个指针变量，一个用以指向待删除结点，该指针保存了待删除结点的直接后继结点的地址，这样不至于删除结点后，该结点之后的其他结点地址丢失。另外一个是指向待删除结点的直接前驱结点。

![fe840041c1c318cdace4e99a9d498bd2.png][]

▲ 删除链表指定位置结点

/*
     * fn:      DeleteLinkedListEle
     * desc:    删除链表中指定位置的元素
     * date:    2020/11/26/02:30:01
     * author:  lixiaogang5
    */
    void DeleteLinkedListEle(const INT *iIndex, SingleLinkerList *pHeadLinkedList)
    {
         
        assert(iIndex || pHeadLinkedList || *iIndex > 1);
    
        INT iLocation = 0;
        SingleLinkerList *pHead = pHeadLinkedList, *pTemp = NULL;
        while(pHead->next && iLocation < (*iIndex-1))
        {
         
            pHead = pHead->next;
            iLocation++;
        }
    
        //待删除结点超过表的长度.
        if(!pHead->next)
        {
         
            printf("err.");
        }
    
        //pTemp指向待删除的结点(iIndex)
        pTemp = pHead->next;
        //pTemp临时指针已经保存待删除结点的直接后继结点地址, 所以pHead->next = pTemp->next;
        pHead->next = pTemp->next;
        //释放待删除结点所占用的内存空间.
        free(pTemp);
        pTemp = NULL;
    }

以上几个操作的完整代码如下：

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int INT;
    
    typedef struct Student
    {
         
        char cName[20];         //姓名
        char cGender;           //性别
        INT  iAge;              //年龄
        INT  iClass;            //班级
        char cAddress[20];      //住址
    }StudentInfo;
    
    typedef struct node{
         
        struct node *next;          //指针域
        StudentInfo strStuInfo;     //数据域
    }SingleLinkerList;
    
    /*
     * fn:      createSingleLinkList
     * desc:    创建一个带头结点的单链表
     * date:    2020/11/25/23:30:13
     * author:  lixiaogang5
    */
    SingleLinkerList *createSingleLinkList(const INT *iStudentNum)
    {
         
        //创建一个带头节点的单链表
        SingleLinkerList *pHead = NULL, *pData = NULL, *pNext = NULL;
        pHead = pNext = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
        assert(pHead);
    
        pHead->next = NULL;
        memset(&pHead->strStuInfo, 0x00, sizeof(pHead->strStuInfo));
        for(unsigned i = 0; i < *iStudentNum; i++)
        {
         
            pData = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
            assert(pData);
            char buf[20] = {
         0};
            snprintf(buf, sizeof(buf), "name_%d", i);
            strncpy(pData->strStuInfo.cName, buf, strlen(buf));
    
            pData->strStuInfo.cGender = (i % 2)?'M':'G';
            pData->strStuInfo.iAge = 20 + i;
            pData->strStuInfo.iClass = i;
    
            memset(buf, 0x00, sizeof(buf));
            snprintf(buf, sizeof(buf), "address_%d", i);
            strncpy(pData->strStuInfo.cAddress, buf, strlen(buf));
    
            //
            pNext->next = pData;
            pNext = pData;
        }
    
        pNext->next = NULL;
        return pHead;
    }
    
    
    /*
     * fn:      TraverseOutPut
     * desc:    遍历输出带头结点的单链表
     * date:    2020/11/25/23:34:42
     * author:  lixiaogang5
    */
    void *TraverseOutPut(const SingleLinkerList *pSingleLinkeList)
    {
         
        puts("------------------------------------------------------------------------------");
        assert(pSingleLinkeList);
        const SingleLinkerList *pHead = pSingleLinkeList->next;
        while(pHead)
        {
         
            printf("name: [%s], gender:[%c], age:[%d], class:[%d], address:[%s]n",
                   pHead->strStuInfo.cName, pHead->strStuInfo.cGender, pHead->strStuInfo.iAge,
                   pHead->strStuInfo.iClass, pHead->strStuInfo.cAddress);
            pHead = pHead->next;
        }
    }
    
    /*
     * fn:      GetLengthOfSingleLinkList
     * desc:    获取带节点的单链表长度
     * date:    2020/11/25/23:40:16
     * author:  lixiaogang5
    */
    INT GetLengthOfSingleLinkList(const SingleLinkerList *pSingleLinkeList)
    {
         
        assert(pSingleLinkeList);
        INT iNodeNum = 0;
        const SingleLinkerList *pHead = pSingleLinkeList;
        while(pHead->next)
        {
         
            iNodeNum++;
            pHead = pHead->next;
        }
    
        return iNodeNum;
    }
    
    /*
     * fn:      SpecifiesWhereToInsertData
     * desc:    在带头节点单链表的指定位置插入一个新节点
     * date:    2020/11/25/23:46:10
     * author:  lixiaogang5
    */
    void SpecifiesWhereToInsertData(const INT *iIndex, const StudentInfo *pOneStuInfo, SingleLinkerList *pHeadLinkeList)
    {
         
        assert(pHeadLinkeList || iIndex || pOneStuInfo || *iIndex >= 1);
    
        INT iLocation = 0;
        SingleLinkerList *pHead = pHeadLinkeList;
    
        //若指定位置超过了链表的长度范围,则不允许插入.
        assert(*iIndex <= GetLengthOfSingleLinkList(pHeadLinkeList));
    
        while(pHead && iLocation <= *iIndex - 1) pHead = pHead->next, iLocation++;
    
        SingleLinkerList *pNewStudentInfo = (SingleLinkerList *)calloc(1, sizeof(SingleLinkerList));
        assert(pNewStudentInfo);
        strncpy(pNewStudentInfo->strStuInfo.cName, pOneStuInfo->cName, sizeof(pNewStudentInfo->strStuInfo.cName));
        pNewStudentInfo->strStuInfo.cGender = pOneStuInfo->cGender;
        pNewStudentInfo->strStuInfo.iAge    = pOneStuInfo->iAge;
        pNewStudentInfo->strStuInfo.iClass  = pOneStuInfo->iClass;
        strncpy(pNewStudentInfo->strStuInfo.cAddress, pOneStuInfo->cAddress, sizeof(pNewStudentInfo->strStuInfo.cAddress));
    
        //若为尾节点位置, 则将新节点数据追加到链表末尾.
        if(!pHead){
         
            pHead->next = pNewStudentInfo;
            pNewStudentInfo->next = NULL;
        }
    
        pNewStudentInfo->next = pHead->next;
        pHead->next = pNewStudentInfo;
    }
    
    /*
     * fn:      DeleteLinkedListEle
     * desc:    删除链表中指定位置的元素
     * date:    2020/11/26/02:30:01
     * author:  lixiaogang5
    */
    void DeleteLinkedListEle(const INT *iIndex, SingleLinkerList *pHeadLinkedList)
    {
         
        assert(iIndex || pHeadLinkedList || *iIndex > 1);
    
        INT iLocation = 0;
        SingleLinkerList *pHead = pHeadLinkedList, *pTemp = NULL;
        while(pHead->next && iLocation < (*iIndex-1))
        {
         
            pHead = pHead->next;
            iLocation++;
        }
    
        //待删除结点超过表的长度.
        if(!pHead->next)
        {
         
            printf("err.");
        }
    
        //pTemp指向待删除的结点(iIndex)
        pTemp = pHead->next;
        //pTemp临时指针已经保存待删除结点的直接后继结点地址, 所以pHead->next = pTemp->next;
        pHead->next = pTemp->next;
        //释放待删除结点所占用的内存空间.
        free(pTemp);
        pTemp = NULL;
    }
    
    int main()
    {
         
        INT iStuNum = 5;
        SingleLinkerList *pLinkeListed = NULL;
        //1. 创建带头节点的单链表
        pLinkeListed = createSingleLinkList(&iStuNum);
    
        //2. 遍历打印链表
        TraverseOutPut(pLinkeListed);
    
        //3. 获取带节点的单链表长度(头结点不计算在内)
        printf("iNodeNum:%dn", GetLengthOfSingleLinkList(pLinkeListed));
    
        //4. 在带头节点单链表的指定位置插入一个新节点
        INT iIndex = 5;
        StudentInfo struOneStuInfo;
        strncpy(struOneStuInfo.cName, "lixiaogang5", sizeof(struOneStuInfo.cName));
        struOneStuInfo.cGender = 'M';
        struOneStuInfo.iAge = 27;
        struOneStuInfo.iClass = 666;
        strncpy(struOneStuInfo.cAddress, "guizhousheng", sizeof(struOneStuInfo.cAddress));
    
        SpecifiesWhereToInsertData(&iIndex, &struOneStuInfo, pLinkeListed);
        //4.1 遍历打印链表
        TraverseOutPut(pLinkeListed);
    
        //5. 删除指定位置的结点
        iIndex = 2;
        DeleteLinkedListEle(&iIndex, pLinkeListed);
        //5.1 遍历打印链表
        TraverseOutPut(pLinkeListed);
        return 0;
    }

该示例代码中，实现了带头结点的链表的创建、遍历、获取链表长度、指定位置插入结点和指定位置删除结点等。其运行结果如下：

![2e67414129759e8a3b3ff990b5e6c542.png][]

▲ 示例代码运行结果

[94134678d5778e643480c4041ceb4dab.png]: /images/20221119/efe05243bf4b46a196928a0c4633a8d7.png
[ecca6f6e40cc2f594fc5fd16f7333d40.png]: /images/20221119/e5c9df3e091342129166142057517196.png
[493745f03d5ed3c371b574ae5db39e3f.png]: /images/20221119/acd5116595304fe78fe52508ce8f09fc.png
[012b9bfd602c18ff719b8a5533541d43.png]: /images/20221119/1e1fe3c9571345689054cba9e66e7832.png
[87bf42dbbde2e59701f11dcf403f4c62.png]: /images/20221119/2b3c708deffc4147ae52f169cb6cb290.png
[360a76998fffa17efa02a3ae476d4893.png]: /images/20221119/ced425b1bed3492e92c22e67730b7030.png
[fe840041c1c318cdace4e99a9d498bd2.png]: /images/20221119/ced3b80dc60b4fc2a7ebab761f1445c3.png
[2e67414129759e8a3b3ff990b5e6c542.png]: /images/20221119/1686fa9821e54272a8adeec9e4a99353.png