[数据结构与算法]链表的实现

首先我们要先有一个结构体

?
typedef int SLTDateType;//这样是为了方便修改数据类型

typedef struct SListNode
{
    SLTDataType data;      //存储数据
    struct SListNode* next;//储存下一个节点的指针，链表就是通过此互相链接起来的
}SLTNode;                  //将该结构体进行重命名

struct SListNode
{
    //...
    //...
}SLTNode;
//这里还需要区分的是，如果前面没有typedef，那么这里的SLTNode就相当于一个结构体变量

?

有了结构体之后我们应该创建一个链表，只需要一个结构体指针就够了

STNode* plist = NULL;

新节点的创建

思路：

1. 开辟一块新空间

2. 把值放进这块新空间里面去

3. 返回

那么我们实现出来会是这样子的

SLTNode* BuyListNode(SLTDateType x)
{
    SLTNode* newnode = ((SLTNode*)malloc(sizeof(SLTNode)));
    
    newnode->data = x;
    
    return newnode;
}

当然除了主体框架之外还有一些小细节需要留意，如

1. 是否开辟成功

2. 新节点还存放了一个指针，该指针需要先初始化

SLTNode* SListBuyList(SLTDateType x)
{
    SLTNode* newnode = ((SLTNode*)malloc(sizeof(SLTNode)));
    if(newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);//开辟失败就结束程序
    }
    newnode->data = x;
    newnode->next = NULL;
    
    return newnode;
}

打印

1. 遍历链表

2. 将每个节点的存放的值打印出来

tip：这里我们就需要看到函数传参的问题了，到底要传一级指针还是二级指针呢？

A：

如果我们不需要改变指针的值，就传一级指针（如打印，查找）

如果我们需要改变指针的值，就传二级指针（如删除，插入，销毁）

void Print(SLTNode* phead)
{
    //遍历链表，这是一个非常重要的操作
    SLTNode* cur = phead;
    while(cur)
    {
        cur = cur->next;
        printf("%d->", cur->data);
        //在这里还需要注意一点，访问结构体的元素应该写成cur->data,不能单纯写data
    }
    printf("NULL\n");
    //末尾加了NULL能告诉我们链表最后的指针指向空
}

尾插

1. 开辟新节点

2. 找到链表尾部

3. 将新节点插入到链表尾部

void SListPushBack(SLTNode** pphead)
{
    //开辟新节点，用newnode接收
    SListNode* newnode = BuyListNode(x);
    
    //找到链表尾部，也就是我们前面写的遍历链表
    STListNode* tail = *pphead;
    while(tail->next)//当tail->next == NULL时，那么tail就是最后一个节点了
    {
        tail = tail->next;
    }
    
    //将新节点插入到链表尾部
    tail->next = newnode;
    
    //从这里开始我们将会学习怎么将节点链接起来
    //思路是这样的，就是把每个节点的尾都赋上我们想要的值
    //tail->next = newnode的意思就是tail的下个节点指向newnode
    //那么newnode的下一个节点呢？
    //在SListBuyList中我们已将其置空
}

当然这样函数还遗漏了一些小问题

比如

函数传参如果传来了一个空指针？

链表本身就为空？

针对上述问题我们只需要做出两步修改

1. 断言避免空指针

2. 判断链表是否为空

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    
    SLTNode* newnode = BuyListNode(x);
    if((*pphead) == NULL)
    {
        return newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while(tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾删

1. 找到尾部

2. 将尾部的节点销毁，并将指向尾部节点的指针置空

void SListPopBakc(SLTNode** pphead)
{
    //找到尾部，这个操作我们已经讲过两遍了哦
    SLTNode* tail = *pphead;
    while(tail->next)
    {
        tail = tail->next;
    }
    
    //销毁，置空
    free(tail);
    tail = NULL;
}

不过尾删并没有我们上面写的那么简单，上面的程序至少存在以上问题：

1. 传参的时候可能会接收到空指针（尾插的时候已有提及）

2. 如果链表为空呢？

3. 我们将尾节点删除之后，指向尾节点的指针不是存放在上一个节点中嘛？这不就造成野指针了嘛？

解决方法：

根据第3点我们可以知道，尾节点销毁之后还需要将指向它的指针置空，不然就会造成野指针，而这个指针存放在上一个节点中，所以我们需要记录好上一个节点，然后在销毁之后，将尾节点置空之外，还要将指向它的指针也置空

这里还需要注意，前面的讨论是建立在至少有两个节点的情况下的，那如果只有一个节点呢？如果一个节点都没有呢？

我们可以知道，如果只有一个节点，那只需要将它本身置空就好，并没有上一个节点存放它的地址（这里尚且不讨论带哨兵位头节点的情况）

如果一个节点都没有，那我们直接加断言避免程序进行尾删操作就好了

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);//但凡接收指针最好都要加上断言，易于我们查找错误，接下来函数实现将不再赘述
    assert(*pphead != NULL);
    
    if((*pphead)->next == NULL) //只有一个节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else	//有一个以上节点
    {
        //找尾并记录前一个节点
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;
        while(tail->next)
        {
            prev = tail;
            //prev->next = tail;这里不能认为既然tail是prev的前一个就可以这么写，因为prev是空指针，这样会造成非法访问
            //tail将会变成它的下一个节点，那么只需要在这之前让prev = tail就好了，也就相当于记录下了tail的前一个节点
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        
        prev->next = NULL;
        
        
        //这里还有第二种解法
        SLTNode* tail = *pphead;
        while(tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

这里是第二种方法的图示 ????????

其实啊，置空之后节点的指针置空的问题很简单

你只要让每个节点存放的指针都有所指向就行了

就像第一种方法，你让tail置空了

但是它上一个节点存放的指针却没有了指向，那么就也需要置空

所以说第一种方法的tail = NULL可要可不要，只要前一个节点存放的指针置空就好了，建议各位读者还是要画图才能理解得更深

第二种方法需要有所指向的也只有 tail->next

头插

1. 断言避免空指针（这个我相信大家已经很清楚了，断言是一种很好的习惯喔）

2. 创建一个新节点

3. 将新节点插入到头节点前面

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x); 
    //前面的我们已经基本都会了，这里我们来看看如何插入
    //前面讲过，其实插入就是让各个节点存放的指针都有所指向就好了
    newnode->next = *pphead;//让原头节点链接到新节点的后面
    *pphead = newnode;//因为newnode是插在头部的嘛，所以它自然会变成新的头节点
}

头删

1. 断言避免空指针

2. 判断链表是否为空（这一步跟尾插是一样的）

3. 将头节点销毁并置空

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead != NULL);
    free(*pphead);
    *pphead = NULL;
}

不过这里写完我们会发现一个问题：就是没有新的头节点了

那么我们需要把下一个节点先记录起来，然后最后再让它做新的头节点

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead != NULL);
    SLTNode* Next = (*pphead)->next;
    free(*pphead);
    *pphead = NULL;
    *pphead = Next;//当然这两步也可以直接合并起来
}

因此，尾删的时候需要记录上一个节点，头删的时候需要记录下一个节点，这是由单向非循环链表的特性所决定的，我们如果销毁了该节点，就很难找到该节点的上一个或下一个节点，因此将其记录下来是一个很好的方式

我们再回顾一下记录上一个节点的方法，不断重复才能深刻掌握

SLTNode* Prev = NULL;
while(tail->next)
{ ? ?
    Prev = tail; ? ?
    tail = tail->next;
}

读者也可在阅读时上机亲自实现这些函数，实践才能出真知，并且体验到编程的魅力

在节点pos后进行插入

1. 断言避免空指针

2. 创建一个新节点

3. 将新节点链接到pos的后面（还记得链接的关键是什么吗？让每个节点都有所指向）

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
    assert(pos && pphead);
    SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
    pos->next = newnode;
}

我们在这里仔细观察一下，可以总结出一个结论

其实链接就是：让每个节点存放的指针有所指向

这里的pos->next和newnode->next不就是每个节点存放的指针嘛

其实更具体地说，应该是改动的那些节点存放的指针有所指向

所以只要抓住这个点，链接这方面就会变得非常简单

所以再回头看看前面链接的步骤，会不会有不一样的收获呢？

在节点pos前进行插入

1. 断言避免空指针

2. 创建新节点

3. 找到pos的前一个节点

4. 链接

????????

void SListInsert(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posPrev = *pphead;
    while(posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    //找到之后就会跳出循环，我们就可以进行链接
    //哪些节点存放的指针需要有所指向呢？分别是newnode->next和posPrev->next
    newnode->next = pos;
    posPrev->next = newnode;
}

细心的朋友可能会发现，我们这里考虑的情况仍然不全面

在前面其他函数的实现中，我们可以看到大抵可以分为三种情况：

1. 链表为空

2. 链表只有一个节点

3. 链表有一个以上节点

这里因为已经有一个pos节点，故我们不需要考虑第一种情况

而只有一个节点的话，那么这一个节点就是pos

void SListInsert(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    if((*pphead) == pos)
    {
        newnode->next = pos;
        *pphead = newnode;//让newnode做新的头节点
        //如果头节点需要改变，就需要这一步，像尾插尾删等都是不需要的
    }
    else
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next = pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

所以说，我们以后在实现完自己的程序之后，一定要想想是否已经考虑到所有情况，有无遗漏

这是程序设计的一个关键点

并且在上述函数的实现中，我们可以看到有很多类似的地方，比如

1. 接收指针时记得断言

2. 链接就是让每个节点存放的指针都有所指向

3. 头插头删的时候还要记得改变头节点

4. 如果在节点删除后，需要操作节点前或后的位置，可以将其记录下来

5. 要尽量考虑到链表如果为空，链表只有一个节点这种情况

并且，在学习数据结构的过程中，画图给我们更加直观的感受

查找并返回节点

1. 断言避免空指针

2. 遍历链表

3. 判断，如果里面的元素是我们需要的就返回

4. 不是就继续遍历

void SListFind(SLTNode* phead, SLTDataType x)
{
    assert(phead);
    SLTNode* cur = phead;
    if(cur->data == x)
    {
        return cur;
    }
    else
    {
        cur = cur->next;
    }
    return NULL;
}

这里不需要改变指针的值，就不需要传二级指针哦

删除pos节点

1. 断言避免空空指针

2. 链接

3. 若链表只有一个节点则直接删除

4. 若链表有一个以上节点则需要记录前一个节点

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    if((*pphead) == pos)//只有一个节点，那也就是头节点，那我们就还需要改变一下头节点的值
    {
        *pphead = NULL;
        free(pos);
        pos = NULL;
    }
    else
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next != pos)
        {
			posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

?

所以我们需要加个if判断一下

但是可能还会有一种情况，就如果我们删除的就是头节点，那么头节点就需要改变了

所以我们需要加个if判断一下

else
{
    if((*pphead) == pos)//诶这里我们会发现这一句跟前面链表只有一个值是一样的啊
    {
        *pphead = pos->next;//而且如果当链表里只有一个节点，那么pos->next不就是NULL嘛，那么我们就可以直接将其合并起来
        free(pos);
        pos = NULL;
    }
}

通过以上，我们可以得到最终的函数

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    if((*pphead) == pos)//当删除的是首尾的元素的时候，只有一个节点或有一个以上节点的情况相同
    {
        *pphead = pos->next;
        free(pos);
        pos = NULL:
    }
    else//删除的不是头节点
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

删除pos的后一个节点

1. 断言避免空指针

2. 找到pos的后一个节点

3. 链接

4. 删除

void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    //找到pos的后一个节点
    SLTNode* Next = pos->next;
    //链接
    pos->next = Next->next;
    //删除
    free(Next);
    Next = NULL;
}

销毁链表

1. 断言避免空指针

2. 遍历链表，逐个销毁并置空

void SListDestory(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;
    while(cur)
    {
        free(cur);
        cur = NULL;
        cur = cur->next;
    }
    *pphead = NULL;
}

注意，上面这种写法是错的，因为你已经将节点释放掉了，还给操作系统了

这块空间就不属于用户了，再去进行访问 cur->next就会出阿信非法访问的问题

前面我们在总结的第四点也有所提及

?所以我们只需要提前将其记录下来

while(cur)
{
    SLTNode* Next = cur->next;
    free(cur);
    cur = NULL;
    cur = Next;
}

到这里，单向不带哨兵位链表的基本操作我们就都能实现

读者也可以试着利用删除pos节点去实现头删和尾删

还有利用插入pos节点前后的函数去实现头插和尾插

在学习数据结构的过程中，我们要特别注意画图

画图能带给我们更加直观的感受

目录

新节点的创建

打印

尾插

尾删

头插

头删

在节点pos前进行插入

查找并返回节点

删除pos节点

删除pos的后一个节点

销毁链表