初阶数据结构学习记录——넷 单链表（2）

目录

1、Find

2、插入pos之后

3、插入pos之前

4、删除pos之后

5、删除pos

6、销毁

7、test.c

---

接着上一篇写。

pos位置左右的操作

这一篇要写的功能如下

SLTNode* SListFind(SLTNode* phead, SLTDataType x);
 
//单链表在pos位置之后插入x
SLTNode* SListInsertAfter(SLTNode* pos, SLTDataType x);
//在pos之前插入x
SLTNode* SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表删除pos位置之后的值
SLTNode* SListEraseAfter(SLTNode* pos);
//删除pos位置
SLTNode* SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x);

1、Find

好吧，看到这个就想起了OPPO。

find这个功能是为了要删除pos位置时，能够找到pos位置是哪个节点。直接上代码

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

传过来的phead头，都要再建一个局部变量存储它，不能动phead。

2、插入pos之后

重点是pos的操作。pos是已经经过find后找到的节点位置，所以删除这个位置之后我们直接使用pos即可。

SLTNode* SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

根据上面的查找功能，如果遍历所有也没找到，返回一个NULL，那么pos就是NULL。那么也就没必要再插入了，所以断言一下。不过还有一个问题，为什么这里没用二级指针？在之前的尾插函数里，头节点的指针地址传了过来，然后用一个同类型的指针指向它，我们可以用它来连接下一个节点。假设用的是一级指针，那么也就是把头节点的内容传了过来，比如NULL，那么函数里面局部变量tail接收后插入数据，但原本函数外的节点并没有连接上新节点，所以要用二级指针。而这里，pos得到之后，我们要做的是改变结构体里面的成员——结构体指针指向的数据，所以我们只需要一个结构体指针即可改变结构体里面的成员。那么也就不需要二级指针。简而言之，二级指针是为了改变一级指针存储的内容，而用一级指针可以改变另一个一级指针指向哪里，但是要拿到数据就需要二级指针。

3、插入pos之前

想插入之前就比较麻烦。遍历到pos位置之后，我们需要一个指针跟在后面，这样也就能指向pos之前的节点了。如果是pos位置为第一个，那就是头插。但是尾插是不存在的，pos即使是最后 i 一个位置，也不是尾插，尾插则是pos已经越界了，所以只考虑头插即可，同样也要断言。

SLTNode* SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pos);
    if (*pphead == pos)
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        SLTNode* newnode = BuySLTNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

4、删除pos之后

关于删除功能，pos从头到尾，特别情况只有尾，如果pos是尾，那么后面就是NULL，那就不用操作。如果free掉pos之后的节点，然后pos->next = pos->next->next，连接再往后一个可行吗？这里会存在野指针。free之后，pos->next指向的空间已经回归内存，那么pos->next->next也就不知道访问到哪里去了，整个程序就会错误。所以我们删除之前先定义一个结构体来存一下pos->next，通过这个定义的结构体来进行操作。

SLTNode* SListEraseAfter(SLTNode* pos)
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLTNode* next = pos->next;
        pos->next = next->next;
        free(next);
    }
}

5、删除pos

会出现头删。

SLTNode* SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pos);
    assert(*pphead);
    if (*pphead == pos)
    {
        SLTPopFront(pphead);
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

6、销毁

其实和删除有些相同，都需要注意野指针问题

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

7、test.c

void TestSList5()
{
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPushBack(&plist, 5);
    SLTPrint(plist);
 
    SLTNode* p = SLTFind(plist, 3);
    SLTInsertAfter(p, 30);
 
    //p = SLTFind(plist, 300);
    //SLTInsertAfter(p, 30);
 
    p = SLTFind(plist, 2);
    SLTInsert(&plist, p, 20);
 
    /*if (p)
    {
        SLTInsertAfter(p, 30);
        printf("ҵ\n");
    }
    else
    {
        printf("Ҳ\n");
    }*/
 
    SLTPrint(plist);
}
 
void TestSList6()
{
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPushBack(&plist, 5);
    SLTPrint(plist);
 
    SLTNode* p = SLTFind(plist, 3);
    SLTEraseAfter(p);
    SLTPrint(plist);
 
    p = SLTFind(plist, 3);
    SLTErase(&plist, p);
    p = NULL;
    SLTPrint(plist);
 
    SLTDestroy(&plist);
 
    SLTPrint(plist);
}

结束。