【数据结构】单链表的实现

一、链表的特性

1、概念

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

单链表的图解：

单链表中，每一个节点存储一个数据和一个指向下一个节点的指针，为了方便观察，添加了虚拟的箭头。

单链表中传入的实参是结构体头指针，当使用头插头删等接口时，需要改变头指针，所以要传入二级指针。

但是修改头指针指向的next指针或者date值时，传值也行。

2、单链表的优缺点

优点：

头插头删时间复杂度O(1)

逐个申请、释放空间，没有空间浪费

缺点：

结构简单，通常作为其他数据结构的子结构

中部、尾部插入删除需要遍历

不支持随机访问

需要额外的空间用于存储指针

二、SList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SLTNode
{
    struct SLTNode* next;
    SLTDateType date;
}SLTNode;
void SListPrint(SLTNode* phead);//打印
SLTNode* BuySListNode(SLTDateType x);//malloc一个新节点
void SListDestroy(SLTNode** pphead);//销毁
void SListPushFront(SLTNode** pphead,SLTDateType x);//头插
void SListPopFront(SLTNode** pphead);//头删
void SListPushBack(SLTNode** pphead, SLTDateType x);//尾插
void SListPopBack(SLTNode** pphead);//尾删
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找，找到返回结构体地址，反之返回NULL
void SListInsert(SLTNode** pphead, SLTNode* pos,SLTDateType x);//在结构体指针pos前一个节点插入
void SlistEarse(SLTNode** pphead, SLTNode* pos);//删除结构体指针pos指向的节点
void SListInsertAfter(SLTNode* pos, SLTDateType x);//在结构体指针pos后一个节点插入
void SListEarseAfter(SLTNode* pos);//删除结构体指针pos后一个节点后一个节点插入
void SListEarseAfter(SLTNode* pos);//删除结构体指针pos后一个节点

三、Slist.c

1、单链表的打印

void SListPrint(SLTNode* phead)//打印
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

循环遍历

2、malloc一个新节点

SLTNode* BuySListNode(SLTDateType x)//malloc一个新节点
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail:\n");
        return NULL;
    }
    newnode->date = x;
    newnode->next = NULL;
    return newnode;
}

3、单链表的销毁

void SListDestroy(SLTNode** pphead)//销毁
{
    assert(pphead);
    SLTNode* cur = *pphead;
    while (cur)
    {
        SLTNode* next = cur->next;
        free(cur);
        cur=next;
    }
    *pphead = NULL;
}

迭代释放链表节点

4、单链表的头插、头删

void SListPushFront(SLTNode** pphead, SLTDateType x)//头插
{
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}
void SListPopFront(SLTNode** pphead)//头删
{
    assert(pphead&& *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

单链表的优势就是头插、头删

对于头删，除了要断言二级指针外，还要断一下二级指针所指向的一级指针是否为空，如果为空，说明该链表没有元素，需要报断言错误。

5、单链表的尾插、尾删

void SListPushBack(SLTNode** pphead, SLTDateType x)//尾插
{
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    if (*pphead == NULL)//分别讨论*pphead是否为空的情况
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}
void SListPopBack(SLTNode** pphead)//尾删
{
    assert(pphead&&*pphead);//*pphead不能为空
    if ((*pphead)->next == NULL)//分别讨论仅剩一个节点和多节点的情况
    {
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

尾插时，需要分类讨论链表是否为空的情况

尾删时，*pphead不能为空。同样需要分开讨论仅剩一个头结点或剩余多个节点的情况，再循环找到tail的prev，进行尾删操作。

6、单链表的查找（修改）

SLTNode* SListFind(SLTNode* phead, SLTDateType x)//查找，找到返回结构体地址，反之返回NULL
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

查找，找到返回结构体地址，反之返回NULL

查找函数是配和后方pos节点插入、删除函数使用

7、在pos之前插入、删除pos节点

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)//在结构体指针pos前一个节点插入
{
    assert(pphead&&pos);
    if ((*pphead)==pos)
    {
        SListPushFront(pphead, x);//头插
    }
    else
    {
        SLTNode* newnode = BuySListNode(x);
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
            assert(prev);//pos不在链表中.prev为空，还没有找到pos，说明pos传错了
        }
        newnode->next = pos;
        prev->next = newnode;
    }
}

void SlistEarse(SLTNode** pphead, SLTNode* pos)//删除结构体指针pos指向的节点
{
    assert(pphead && pos && *pphead);
    if (pos == *pphead)//要判断pos是不是头结点
    {
        *pphead = (* pphead)->next;
        free(pos);//pos需要在外部置空    
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);//pos需要在外部置空
    }
}

分类讨论pos是否是头节点

对非头结点的插入，注意在循环中断言prev，防止pos传错，导致循环停不下来。

此接口不实用，因为单链表找前一个节点不好找，算法效率低

8、pos后一个位置插入、删除

void SListInsertAfter(SLTNode* pos, SLTDateType x)//在结构体指针pos后一个节点插入
{
    assert(pos);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}
void SListEarseAfter(SLTNode* pos)//删除结构体指针pos后一个节点
{
    assert(pos&&pos->next);
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
    next = NULL;
}

四、pos之前插入、删除pos节点的巧妙解法

1、pos之前插入一个节点

在pos之后插入一个节点，将pos指向的值拷贝给newnode，再将pos->date改成需要插入的那个数据即可。

2、删除pos节点

将pos和pos->next的值交换，free（pos->next）

需要讨论尾删的情况