【落羽的落羽 数据结构篇】单链表

一、链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，链表由一个个节点(node)组成，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。
链表的节点通常是一个结构体变量，每一个节点都是独立的空间，它们在内存中的地址不一定是连续的。而把他们串联在一起的便是结构体中的指针。第一个节点的指针成员指向第二个节点，第二个节点的指针成员指向第三个节点……最后一个节点的指针成员是空指针：

struct SListNode
{
    int data; //存储的数据
    stuct SListNode* next; //指针变量用于保存下一个节点的地址
};

也就是说，链表是一种逻辑上线性，物理（地址）上非线性的数据结构。

链表也包括很多种，如单链表、双向链表等等，今天我们学习单链表。

二、单链表

1. 结构

顾名思义，单链表就是单向的链表，节点之间是单向指向的：
每一个节点的结构是：

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

一般来说，节点是一个一个申请的，初始化时也需要一个一个来

2. 创建一个单链表并初始化

SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));

node1->data = 11;
node2->data = 22;
node3->data = 33;
node4->data = 44;

node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;

SLTNode* plist = node1;

像这样，一个单链表的雏形就出现了，plist是它的首节点地址。后续对单链表进行修改时，要利用plist。

下面的功能，都用函数来实现，涉及修改链表的函数要传递plist的地址，即二级指针。

3. 申请一个新节点

在往链表插入一个新数据x前，我们首先要向操作系统申请一个节点用来存储这个数据x，节点的指针成员先置为NULL，返回申请好的新节点的地址。

SLTNode* SLTBuyNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail!");
        exit(1); //申请空间失败则返回1
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

测试：

4. 尾部插入数据

这个函数有两个参数：指向链表首节点的指针的地址、要插入的新数据。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL) //若链表为空，则phead直接指向newnode节点
    {
        *pphead = newnode;
    }
    else //链表不为空，则找到尾结点，将尾结点和newnode节点连接起来
    {
        SLTNode* ptail = *pphead;
        while (ptail->next != NULL)
        {
            ptail = ptail->next;
        }
        ptail->next = newnode;
    }
}

测试：

5. 头部插入数据

头部插入数据，要让新节点的指针成员指向原来的第一个节点，新节点成为链表的第一个节点

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

测试：

6. 尾部删除数据

void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead); //若*pphead为空，则链表为空，无节点可删
    if ((*pphead)->next == NULL) //若链表只有一个节点，则free后置为NULL
    {
        free(*pphead);
        *pphead = NULL;
    }
    else //若链表不止一个节点，则找尾节点。尾结点的前一个节点的指针成员置为NULL，尾结点free后置为NULL
    {
        SLTNode* prev = NULL;
        SLTNode* ptail = *pphead;
        while (ptail->next != NULL)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        prev->next = NULL;
        free(ptail);
        ptail = NULL;
    }
}

测试：

7. 头部删除数据

先将首节点的指针成员保存在next中，将首节点free掉后，next就是首节点地址了。

void SLTPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

测试：

8. 指定节点之前插入数据

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead && pos);
    if (*pphead == pos) //如果pos就是首节点，则直接执行刚才的头部插入数据函数
    {
        SLTPushFront(pphead, x);
    }
    else //如果pos不是首节点，先找pos节点，将新节点插入到pos和pos前一个节点之间
    {
        SLTNode* newnode = SLTBuyNode(x);
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        newnode->next = pos;
        prev->next = newnode;
    }
}

测试：

9. 指定节点之后插入数据

上一条在指定节点之前插入数据，由于要找pos的上一个节点，因此还要传参首节点。而这一条在指定节点之后插入数据，pos节点自己就能找到下一个节点，就不需要传参首节点了。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

测试：

10. 删除指定节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    if (*pphead == pos) //若pos就是首节点，则执行头部删除数据操作
    {
        SLTPopFront(pphead);
    }
    else //若pos不是首节点，则找pos的前一个节点，将pos的前后连接起来，pos节点free后置为NULL
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

测试：

11. 删除指定位置之后的节点

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

测试：

12. 销毁链表

遍历整个链表，将每个节点free，最后将首节点置为NULL

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

测试：

以上就是单链表及其基础操作

本篇完，感谢阅读