C++ 单链表

sasorit 2022-05-23 我要评论

简介：

线性表的顺序存储结构有一个缺点就是插入和删除时需要移动大量元素，这会耗费许多时间。能不能想办法解决呢？
干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，让每一个元素都知道它下一个元素的位置在哪里。
线性表链式存储结构：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。
链表是由一个个结点链结成的。
结点包括数据域和指针域两部分，数据域用来存储数据元素的信息，指针域用来存储下一个结点的地址。

接下来实现一个无头单向非循环链表。

单链表结构的定义

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data;        //数据
    struct SListNode* next;        //指向下一个结点的指针
}SLTNode;

单链表打印

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

将指向链表的指针plist做参数传给函数，遍历一遍链表并输出每个结点数据域的内容。

动态申请一个结点

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    return node;
}

用malloc动态开辟一个结点，如果node为NULL说明开辟失败，退出程序。否则将结点node的数据域赋值为x，指针域赋值为NULL。

单链表尾插

如果单链表为空，开辟一个新结点用指针指向它即可；如果链表不为空，需要开辟一个新结点，然后找到链表的最后一个结点，让最后一个结点的指针域存放新结点的地址。

有一个链表，为链表尾插一个新结点：

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);        //plist地址一定不为NULL，进行断言
    if (*pphead == NULL)    //链表为空
    {
        SLTNode* newnode = BuySListNode(x);
        *pphead = newnode;
    }
    else           //链表不为空
    {        
        SLTNode* tail = *pphead;
        while (tail->next)        //找到最后一个结点
            tail = tail->next;
        SLTNode* newnode = BuySListNode(x);
        tail->next = newnode;
    }
}

单链表尾删

如果链表只有一个结点，把这个结点free掉即可。如果链表有多个结点，找到链表的尾结点和尾结点的前一个结点，让尾结点的前一个结点的指针域指向NULL，free掉尾结点。

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);        //断言pphead
    assert(*pphead);    //当链表为空时说明没有结点，没法进行删除操作，所以*pphead不能为NULL
    if ((*pphead)->next == NULL)    //只有一个结点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else                //多个结点
    {
        SLTNode* tail = *pphead;    //tail表示为节点
        SLTNode* prev = NULL;        //prev表示尾结点的前一个结点
        while (tail->next)        //找到尾结点和尾结点的前一个结点
        {
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL;
        free(tail);
        tail = NULL;
    }
}

单链表头插

申请一个新结点，让新结点的指针域存放头结点的地址，原来指向头结点的指针plist指向新结点，新结点就变成了新的头结点。

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

单链表头删

用一个指针指向头结点的下一个结点，把头结点的空间释放掉，指向头结点的指针指向头结点的下一个结点。头结点的下一个结点就变成了新的头结点。同时要考虑链表为空时不能删除，进行相应的断言。

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    SLTNode* next = (*pphead)->next;    //指针next记录头结点的下一个结点
    free(*pphead);
    *pphead = next;
}

求单链表长度

int SListSize(SLTNode* phead)
{
    int size = 0;
    SLTNode* cur = phead;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

单链表查找

遍历一遍单链表，如果某一结点数据域内容与要查找内容相同，返回该结点。遍历完没有找到，返回NULL。

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

单链表在pos位置插入

在pos位置插入，如果pos这个位置是头结点，和头插的逻辑是一样的，可以调用之前写过的头插函数。
如果这个位置是除头结点外的任意一个结点，我们需要申请一个新结点，并且记录pos结点的前一个结点，让新结点的指针域存放pos的地址，让pos前一个结点的指针域存放新结点的地址，把它们链结起来。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);        //指向头结点指针的地址不能为NULL，进行断言
    assert(pos);        //插入位置pos不能为NULL进行断言
    if (pos == *pphead)        //要插入的位置pos和头结点是一个位置
    {
        SListPushFront(pphead, x);
    }
    else                //pos不是头结点
    {
        SLTNode* prev = *pphead;    //prev用来找到pos位置的前一个结点
        while (prev->next != pos)
            prev = prev->next;
        SLTNode* newnode = BuySListNode(x);        //申请一个新结点
        newnode->next = pos;        //把新结点链结
        prev->next = newnode;
    }
}

单链表在pos后面位置插入

申请一个新结点，让新结点的指针域存放pos结点下一个结点的地址，pos结点的指针域存放新结点的地址。

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

单链表删除pos位置

如果pos位置是头结点，删除逻辑和头删相同，调用头删函数即可。
如果是除头结点外的其它结点，找到pos的前一个结点，让这个结点的指针域指向pos的下一个结点。把pos结点空间释放。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);    //pphead不能为空，链表不能为空进行断言
    assert(pos);            //pos不能为空
    if (pos == *pphead)        //要删除的位置pos是头结点
    {
        SListPopFront(pphead);
    }
    else                    //不是头结点
    {
        SLTNode* prev = *pphead;    //prev指针用来找到pos结点的前一个结点
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

单链表删除pos的下一个结点

记录下pos的下一个结点，pos结点指针域指向pos下一个结点指针域指向的结点，释放掉pos的下一个结点。

void SListEraseAfter(SLTNode* pos)
{
    //pos不能为空，不能为尾结点，因为尾结点的下一个是NULL，什么也删除不了
    assert(pos && pos->next);    
    SLTNode* next = pos->next;        //next指针指向pos下一个结点
    pos->next = next->next;
    free(next);
    next = NULL;
}

判断单链表是否为空

bool SListEmpty(SLTNode* phead)
{
    return phead == NULL;
}

头文件

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

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data;        //数据
    struct SListNode* next;        //指向下一个结点的指针
}SLTNode;

//打印
void SListPrint(SLTNode* phead);
//新节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//长度
int SListSize(SLTNode* phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//pos位置后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
//删除pos后面位置
void SListEraseAfter(SLTNode* pos);
//判空
bool SListEmpty(SLTNode* phead);

源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

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

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    return node;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);        //plist地址一定不为NULL，进行断言
    if (*pphead == NULL)    //链表为空
    {
        SLTNode* newnode = BuySListNode(x);
        *pphead = newnode;
    }
    else           //链表不为空
    {        
        SLTNode* tail = *pphead;
        while (tail->next)
            tail = tail->next;
        SLTNode* newnode = BuySListNode(x);
        tail->next = newnode;
    }
}

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);        //断言pphead
    assert(*pphead);    //当链表为空时说明没有结点，没法进行删除操作，所以*pphead不能为NULL
    if ((*pphead)->next == NULL)    //只有一个结点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else                //多个结点
    {
        SLTNode* tail = *pphead;    //tail表示为节点
        SLTNode* prev = NULL;        //prev表示尾结点的前一个结点
        while (tail->next)        //找到尾结点和尾结点的前一个结点
        {
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL;
        free(tail);
        tail = NULL;
    }
}

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

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

int SListSize(SLTNode* phead)
{
    int size = 0;
    SLTNode* cur = phead;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

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

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);        //指向头结点指针的地址不能为NULL，进行断言
    assert(pos);        //插入位置pos不能为NULL进行断言
    if (pos == *pphead)        //要插入的位置pos和头结点是一个位置
    {
        SListPushFront(pphead, x);
    }
    else                //pos不是头结点
    {
        SLTNode* prev = *pphead;    //prev用来找到pos位置的前一个结点
        while (prev->next != pos)
            prev = prev->next;
        SLTNode* newnode = BuySListNode(x);        //申请一个新结点
        newnode->next = pos;        //把新结点链结
        prev->next = newnode;
    }
}

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

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);    //pphead不能为空，链表不能为空进行断言
    assert(pos);            //pos不能为空
    if (pos == *pphead)        //要删除的位置pos是头结点
    {
        SListPopFront(pphead);
    }
    else                    //不是头结点
    {
        SLTNode* prev = *pphead;    //prev指针用来找到pos结点的前一个结点
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListEraseAfter(SLTNode* pos)
{
    //pos不能为空，不能为尾结点，因为尾结点的下一个是NULL，什么也删除不了
    assert(pos && pos->next);    
    SLTNode* next = pos->next;        //next指针指向pos下一个结点
    pos->next = next->next;
    free(next);
    next = NULL;
}

bool SListEmpty(SLTNode* phead)
{
    return phead == NULL;
}