单链表

简单实现一下单链表

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;

typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);

// 四大操作
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
void SListPopBack(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLTDataType x);

// 在pos的前面插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);

// 删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);

SList.c

#include "SList.h"

void SListPrint(SLTNode* phead) {
    SLTNode* cur = phead;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL");
}

SLTNode* BuySListNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}

void SListPushBack(SLTNode** pphead, SLTDataType x) {
    SLTNode* newnode = BuySListNode(x);

    if (*pphead == NULL) {
        *pphead = newnode;
    }
    else {
        SLTNode* tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;
        }

        tail->next = newnode;
    }
}

void SListPushFront(SLTNode** pphead, SLTDataType x) {
    SLTNode* newnode = BuySListNode(x);

    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopFront(SLTNode** pphead) {
    SLTNode* next = (*pphead)->next;
    free(*pphead);

    *pphead = next;
}

void SListPopBack(SLTNode** pphead) {
    // 1、空
    // 2、一个节点
    // 3、一个以上的节点

    if ((*pphead) == NULL) {
        return;
    }
    else if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    }
    else {
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;

        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }

        free(tail);
        prev->next = NULL;
    }
}

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

        cur = cur->next;
    }

    return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    if (pos = *pphead) {
        SListPushFront(pphead, x);
    }
    else {
        SLTNode* newnode = BuySListNode(x);
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }

        prev->next = newnode;
        newnode->next = pos;
    }
}

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

        prev->next = pos->next;
        free(pos);
    }
}

在这个函数中，先释放节点，然后将指针置空的原因是为了防止内存泄漏和避免悬挂指针（dangling pointers）问题。

考虑以下情况：

1. 直接将指针置空：

   *pphead = NULL;
   

   如果先将指针置空，然后再释放内存，那么无法再访问这个内存地址，也就无法释放它，从而导致内存泄漏。

2. 先释放内存，然后置空指针：

   free(tail);
   prev->next = NULL;
   

   这种方式先释放了内存，确保没有内存泄漏。然后再将指针置空，这样可以避免悬挂指针问题。如果先将指针置空，再释放内存，那么prev指针仍然指向已经释放的内存地址，这会导致悬挂指针问题。

Test.c

#include "SList.h"

void TestSList1()
{
    SLTNode* plist = NULL;
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPushFront(&plist, 0);
    SListPrint(plist);

    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPrint(plist);

    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPrint(plist);
}

void TestSList2()
{
    SLTNode* plist = NULL;
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPrint(plist);

    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPrint(plist);
}

void TestSList3()
{
    SLTNode* plist = NULL;
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPrint(plist);

    // 想在3的前面插入一个30
    SLTNode* pos = SListFind(plist, 1);
    if (pos)
    {
        SListInsert(&plist, pos, 10);
    }
    SListPrint(plist);

    pos = SListFind(plist, 3);
    if (pos)
    {
        SListInsert(&plist, pos, 30);
    }
    SListPrint(plist);
}

void TestSList4()
{
    SLTNode* plist = NULL;
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPrint(plist);

    SLTNode* pos = SListFind(plist, 1);
    if (pos)
    {
        SListErase(&plist, pos);
    }
    SListPrint(plist);

    pos = SListFind(plist, 4);
    if (pos)
    {
        SListErase(&plist, pos);
    }
    SListPrint(plist);

    pos = SListFind(plist, 3);
    if (pos)
    {
        SListErase(&plist, pos);
    }
    SListPrint(plist);

    pos = SListFind(plist, 2);
    if (pos)
    {
        SListErase(&plist, pos);
    }
    SListPrint(plist);
}


int main()
{
    TestSList1();

    return 0;
}