C语言实现基础数据结构——链表_c语言链表实现

目录

链表

链表示意图

链表的特点

链表的分类

单链表

链表实现前置须知

主要实现功能

链表数据的打印（遍历链表）

链表的头部插入

链表的尾部插入

链表的头部删除

链表的尾部删除

查找链表中的数据

在指定位置之前插入数据

在指定位置之后插入数据

删除指定位置的节点

销毁链表

项目文件

双链表

主要实现功能

双向链表初始化

双向链表的打印

判断链表是否为空

双向链表的尾部插入

双向链表的头部插入

双向链表的尾部删除

双向链表的头部删除

双向链表的数据查找

双向链表中指定位置数据插入

删除双向链表指定位置数据

双向链表的销毁

项目文件

小练习

---

链表

链表是线性表中的其中一种结构，链表在物理存储结构上是非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在链表中，每一个存储空间都是独立申请的（需要添加数据时申请），也被称为节点（结点）

链表节点有两个组成部分：

1. 当前节点需要保存的数据
2. 保存的节点的位置

//单链表结构体定义
//定义需要存储的数据类型
typedef int SListDataType;
 
//链表节点结构体定义
typedef struct SListNode
{
    SListDataType data;//存储数据
    struct SListNode* next;//结构体指针指向后一个结构体（节点）
}SLN;
 
//双向链表结构体定义
//定义存储的数据类型
typedef int DlistDataType;
 
//链表节点结构体定义
typedef struct DlistNode
{
    DlistDataType data;//存储数据
    struct DlistNode* pprev;//结构体指针指向前一个节点
    struct DListNode* next;//结构体指针指向后一个节点
}DLN;

链表示意图

以单链表为例

链表的特点

1. 链式结构在逻辑上是连续的，在物理结构上不一定连续
2. 节点⼀般是从堆上申请的
3. 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

链表的分类

单链表

链表实现前置须知

链表实现时需要熟悉的三个NULL：

1. 函数形参中的二级指针pphead为NULL：说明未正确传入链表首节点地址
2. 头指针phead为NULL：说明链表中还未创建节点。链表还未创建节点则代表头指针phead中的值为NULL，而phead本身也是指针变量，有着自己的地址，将该地址给二级指针时二级指针则不为空（pphead = &phead）
3. 节点指针域为NULL：说明当前节点为最后一个节点

主要实现功能

//链表数据的打印（遍历链表）
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除 
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找链表中的数据 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据 
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点 
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据 
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点 
void SLTEraseAfter(SLTNode* pos);
//销毁链表 
void SListDesTroy(SLTNode** pphead);

链表数据的打印（遍历链表）

//链表数据的打印（遍历链表）
void SLNPrint(SLN* phead)
{
    SLN* pstart = phead;//定义一个临时结构体指针变量，直接使用phead遍历会使最后找不到链表的开始处
    //使用while循环遍历
    //结束条件是pstart不为空指针，因为pstart在遍历的过程中会被更新为当前结构体的下一个结构体地址
    //一旦pstart存储为最后一个节点中存储地址的部分的NULL值则退出循环
    while (pstart)
    {
        printf("%d->", pstart->data);
        pstart = pstart->next;
    }
    printf("NULL\n");
}

链表的头部插入

//开辟新空间，用于存储需要插入的新数据
SLN* applySpace(SListDataType x)
{
    SLN* phead = (SLN*)malloc(sizeof(SLN));
    assert(phead);
    phead->data = x;
    //开辟的新空间中，存储下一个节点地址的部分要置为空，防止野指针
    phead->next = NULL;
 
    return phead;
}
 
//链表的头部插入
void SLNPushFront(SLN** pphead, SListDataType x)
{
    assert(pphead);
    SLN* newnode = applySpace(x);
 
    //将形参指向的链表的第一个节点的地址给新开辟的节点中的存储下一个节点地址部分
    newnode->next = *pphead;
    *pphead = newnode;//将初始的第一个节点中存储下一个节点的部分存储新开辟的节点的地址
}

链表的尾部插入

void SLNPushBack(SLN** pphead, SListDataType x)
{
    assert(pphead);
 
    //开辟新空间
    SLN* newnode = applySpace(x);
    //如果新开辟的空间为链表的第一个节点，则将新节点作为首节点
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //尾部插入的前提是先找到最后一个节点
    //因为最后一个节点中存储下一个节点地址的部分为NULL，故可以遍历链表直到找到该部分为NULL为止
    SLN* pmove = *pphead;//防止丢失链表的第一个节点
    //使用next作为终止条件，而不是pmove为终止条件，当pmove为终止条件时，即pmove = NULL，
    while (pmove->next)
    {
        pmove = pmove->next;
    }
 
    pmove->next = newnode;
}

链表的头部删除

//链表的头部删除
void SLNPopFront(SLN** pphead)
{
    assert(pphead);
 
    //判断链表是否为空链表
    //如果为空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }
 
    SLN* BlocktoFree = *pphead;
    //如果链表不为空时，执行删除操作
 
    //释放完空间后首节点需要改变
    *pphead = (*pphead)->next;
    //删除节点需要释放开辟的内存空间
    free(BlocktoFree);
}

链表的尾部删除

//链表的尾部删除void SLNPopBack(SLN** pphead)
{
    assert(pphead);
 
    //删除之前需要判断链表是不是空链表
    //如果是空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }
 
    //如果链表只有一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    
    //如果链表不为空且有多个节点时，执行删除操作
    //先找到尾结点
    SLN* p_end = *pphead;
    SLN* pprev = p_end;
    while (p_end->next)
    {
        pprev = p_end;
        p_end = p_end->next;
    }
    //将倒数第二个节点的存储下一个节点地址的部分置为空
    pprev->next = NULL;
    //释放尾结点的空间
    free(p_end);
    p_end = NULL;
}

查找链表中的数据

//查找链表中的数据
SLN* SLNFind(SLN* phead, SListDataType x)
{
    assert(phead);
 
    SLN* pcur = phead;
    //遍历链表数据
    while (pcur)
    {
        //找到数据返回数据所在节点的地址
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    //未找到数据返回空指针
    return NULL;
}

在指定位置之前插入数据

//在指定位置之前（在指定位置）插入数据
void SLNInsert(SLN** pphead, SLN* pos, SListDataType x)
{
    assert(pphead);
    //插入的位置不可以为空，否则插入无效
    assert(pos);
    //插入的链表不能为空，否则不存在pos所指向的位置
    assert(*pphead);
 
    //开辟空间
    //在指定位置之前插入数据时，需要考虑该位置是不是头结点
    //如果需要插入的位置为头结点的位置，则相当于是头部插入操作
    if (pos == *pphead)
    {
        SLNPushFront(pphead, x);
        return;
    }
    //如果需要插入的位置不是头结点位置，则进行后续插入操作
    SLN* newnode = applySpace(x);
    SLN* pprev = *pphead;
    //遍历链表找到pos指向的位置
    while (pprev->next != pos)
    {
        pprev = pprev->next;
    }
    //更改前一节点指针的存储下一节点位置部分的地址为新节点的地址
    pprev->next = newnode;
    //更改新节点的存储下一节点部分的地址为pos
    newnode->next = pos;
    //上述两步可以交换执行顺序
}

在指定位置之后插入数据

//在指定位置之后插⼊数据 
void SLNInsertAfter(SLN* pos, SListDataType x)
{
    assert(pos);
 
    //指定位置之后插入数据时注意节点连接顺序
    SLN* newnode = applySpace(x);
 
    //将新节点中的存储下一节点地址的部分赋值为pos后一节点的地址
    newnode->next = pos->next;
    //将pos节点中的存储下一节点地址的部分赋值为新节点的地址
    pos->next = newnode;
    //上述两步不可以交换执行顺序
}

删除指定位置的节点

//删除指定位置的节点
void SLNEraseAfter(SLN* pos)
{
    assert(pos);
 
    //如果pos之后的节点为空，则不执行删除操作
    if (pos->next == NULL)
    {
        return;
    }
 
    SLN* BlockToFree = pos->next;
    //如果pos之后的节点不为空，执行删除操作
    //将pos节点的存储下一个节点地址的部分更改为待删除节点的后一个节点地址
    pos->next = pos->next->next;
    free(BlockToFree);
    BlockToFree = NULL;
}

销毁链表

//销毁链表 
void SLNDesTroy(SLN** pphead)
{
    assert(pphead);
 
    SLN* pcur = *pphead;
    //循环销毁链表
    while (pcur)
    {
        SLN* BlockToFree = pcur;
        pcur = pcur->next;
        free(BlockToFree);
    }
    *pphead = NULL;
}

项目文件

测试文件

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SList.h"
 
void generate_test()
{
    //为链表添加数据需要向内存申请空间，因为不存在扩容问题，故直接使用malloc/calloc即可
    SLN* node1 = (SLN*)malloc(sizeof(SLN));//为第一个节点申请空间
    assert(node1);
    SLN* node2 = (SLN*)malloc(sizeof(SLN));//为第二个节点申请空间
    assert(node2);
    SLN* node3 = (SLN*)malloc(sizeof(SLN));//为第三个节点申请空间
    assert(node3);
    SLN* node4 = (SLN*)malloc(sizeof(SLN));//为第四个节点申请空间
    assert(node4);
 
    //在各节点的数据存储部分存入数据
    node1->data = 1;
    node2->data = 2;
    node3->data = 3;
    node4->data = 4;
 
    SLN* phead = node1;//使用一个指针指向第一个节点的地址
    node1->next = node2;//存入第二个节点申请的空间的地址
    node2->next = node3;//存入第三个节点申请的空间的地址
    node3->next = node4;//存入第四个节点申请的空间的地址
    node4->next = NULL;//最后一个节点中存储地址的部分置为空防止野指针
 
    SLNPrint(phead);
    SLNPushFront(&phead, 5);
    SLNPushFront(&phead, 6);
    SLNPushFront(&phead, 7);
    SLNPrint(phead);
    SLNPushBack(&phead, 8);
    SLNPrint(phead);
    SLNPopFront(&phead);
    SLNPrint(phead);
    SLNPopBack(&phead);
    SLNPrint(phead);
    SLN* ret = SLNFind(phead, 4);
    //if (ret)
    //{
    //    printf("找到了");
    //}
    //else
    //{
    //    printf("未找到");
    //}
 
    SLNInsert(&phead, ret, 9);
    SLNPrint(phead);
 
    ret = SLNFind(phead, 6);
    SLNInsert(&phead, ret, 10);
    SLNPrint(phead);
    SLNInsertAfter(ret, 11);
    SLNPrint(phead);
 
    ret = SLNFind(phead, 4);
    SLNInsertAfter(ret, 12);
    SLNPrint(phead);
 
    ret = SLNFind(phead, 12);
    SLNErase(&phead, ret);
    SLNPrint(phead);
 
    ret = SLNFind(phead, 3);
    SLNEraseAfter(ret);
    SLNPrint(phead);
 
    SLNDesTroy(&phead);
    SLNPrint(phead);
}
 
int main()
{
    generate_test();
 
    return 0;
}

头文件

#pragma once
 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
//定义需要存储的数据类型
typedef int SListDataType;
 
//链表节点结构体定义
typedef struct SListNode
{
    SListDataType data;//存储数据
    struct SListNode* next;//结构体指针指向下一个结构体
}SLN;
 
 
//链表数据的打印（遍历链表）
void SLNPrint(SLN* phead);
//头部插⼊删除/尾部插⼊删除 
SLN* applySpace(SListDataType x);
void SLNPushBack(SLN** pphead, SListDataType x);
void SLNPushFront(SLN** pphead, SListDataType x);
void SLNPopBack(SLN** pphead);
void SLNPopFront(SLN** pphead);
//查找链表中的数据 
SLN* SLNFind(SLN* phead, SListDataType x);
//在指定位置之前插⼊数据 
void SLNInsert(SLN** pphead, SLN* pos, SListDataType x);
//删除pos节点 
void SLNErase(SLN** pphead, SLN* pos);
//在指定位置之后插⼊数据 
void SLNInsertAfter(SLN* pos, SListDataType x);
//删除pos之后的节点 
void SLNEraseAfter(SLN* pos);
//销毁链表 
void SLNDesTroy(SLN** pphead);

实现文件

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SList.h"
 
//链表数据的打印（遍历链表）
void SLNPrint(SLN* phead)
{
    SLN* pstart = phead;//定义一个临时结构体指针变量，直接使用phead遍历会使最后找不到链表的开始处
    //使用while循环遍历
    //结束条件是pstart不为空指针，因为pstart在遍历的过程中会被更新为当前结构体的下一个结构体地址
    //一旦pstart存储为最后一个节点中存储地址的部分的NULL值则退出循环
    while (pstart)
    {
        printf("%d->", pstart->data);
        pstart = pstart->next;
    }
    printf("NULL\n");
}
 
//开辟新空间，用于存储需要插入的新数据，包括链表为空的情况
SLN* applySpace(SListDataType x)
{
    SLN* phead = (SLN*)malloc(sizeof(SLN));
    assert(phead);
    phead->data = x;
    //开辟的新空间中，存储下一个节点地址的部分要置为空，防止野指针
    phead->next = NULL;
 
    return phead;
}
 
//链表的头部插入
void SLNPushFront(SLN** pphead, SListDataType x)
{
    assert(pphead);
    SLN* newnode = applySpace(x);
 
    //将形参指向的链表的第一个节点的地址给新开辟的节点中的存储下一个节点地址部分
    newnode->next = *pphead;
    *pphead = newnode;//在初始的第一个节点中存储下一个节点的部分中存储新开辟的节点的地址
}
 
//链表的尾部插入
void SLNPushBack(SLN** pphead, SListDataType x)
{
    assert(pphead);
 
    //开辟新空间
    SLN* newnode = applySpace(x);
    //如果新开辟的空间为链表的第一个节点，则将新节点作为首节点
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //尾部插入的前提是先找到最后一个节点
    //因为最后一个节点中存储下一个节点地址的部分为NULL，故可以遍历链表直到找到该部分为NULL为止
    SLN* pmove = *pphead;//防止丢失链表的第一个节点
    //使用next作为终止条件，而不是pmove为终止条件，当pmove为终止条件时，即pmove = NULL，会使循环多进行一次
    while (pmove->next)
    {
        pmove = pmove->next;
    }
 
    pmove->next = newnode;
}
 
//链表的头部删除
void SLNPopFront(SLN** pphead)
{
    assert(pphead);
 
    //判断链表是否为空链表
    //如果为空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }
 
    SLN* BlocktoFree = *pphead;
    //如果链表不为空时，执行删除操作
 
    //释放完空间后首节点需要改变
    *pphead = (*pphead)->next;
    //删除节点需要释放开辟的内存空间
    //不可free(*pphead)，因为*pphead已经指向了下一个节点，此时free会把下一个节点释放
    free(BlocktoFree);
    BlocktoFree = NULL;
}
 
//链表的尾部删除
void SLNPopBack(SLN** pphead)
{
    assert(pphead);
 
    //删除之前需要判断链表是不是空链表
    //如果是空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }
 
    //如果链表只有一个节点时，则没有前一节点，直接释放空间即可
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    
    //如果链表不为空且有多个节点时，执行删除操作
    //先找到尾结点
    SLN* p_end = *pphead;
    SLN* pprev = p_end;
    while (p_end->next)
    {
        pprev = p_end;//找到倒数第二个节点位置
        p_end = p_end->next;//将尾指针指向最后一个节点
    }
    //将倒数第二个节点的存储下一个节点地址的部分置为空
    pprev->next = NULL;
    //释放尾结点的空间
    free(p_end);
    p_end = NULL;
}
 
//查找链表中的数据
SLN* SLNFind(SLN* phead, SListDataType x)
{
    assert(phead);
 
    SLN* pcur = phead;
    //遍历链表数据
    while (pcur)
    {
        //找到数据返回数据所在节点的地址
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    //未找到数据返回空指针
    return NULL;
}
 
//在指定位置之前（在指定位置）插入数据
void SLNInsert(SLN** pphead, SLN* pos, SListDataType x)
{
    assert(pphead);
    //插入的位置不可以为空，否则插入无效
    assert(pos);
    //插入的链表不能为空，否则不存在pos所指向的位置并且确保pos不是野指针
    assert(*pphead);
 
    //开辟空间
    //在指定位置之前插入数据时，需要考虑该位置是不是头结点
    //如果需要插入的位置为头结点的位置，则相当于是头部插入操作
    if (pos == *pphead)
    {
        SLNPushFront(pphead, x);
        return;
    }
    //如果需要插入的位置不是头结点位置，则进行后续插入操作
    SLN* newnode = applySpace(x);
    SLN* pprev = *pphead;
    //遍历链表找到pos指向的位置
    while (pprev->next != pos)
    {
        pprev = pprev->next;
    }
    //更改前一节点指针的存储下一节点位置部分的地址为新节点的地址
    pprev->next = newnode;
    //更改新节点的存储下一节点部分的地址为pos
    newnode->next = pos;
    //上述两步可以交换执行顺序
}
 
//在指定位置之后插⼊数据 
void SLNInsertAfter(SLN* pos, SListDataType x)
{
    assert(pos);
 
    //指定位置之后插入数据时注意节点连接顺序
    SLN* newnode = applySpace(x);
 
    //将新节点中的存储下一节点地址的部分赋值为pos后一节点的地址
    newnode->next = pos->next;
    //将pos节点中的存储下一节点地址的部分赋值为新节点的地址
    pos->next = newnode;
    //上述两步不可以交换执行顺序
}
 
//删除指定位置的节点 
void SLNErase(SLN** pphead, SLN* pos)
{
    assert(pphead);
    assert(pos);
    //确保链表不为空
    assert(*pphead);
 
    //如果需要删除的节点是头结点，则执行头部删除操作
    if (pos == *pphead)
    {
        SLNPopFront(pphead);
        return;
    }
    //如果删除的节点不是头结点，则执行后续操作
    //遍历链表找到pos位置之前的一个节点
    SLN* pprev = *pphead;
    while (pprev->next != pos)
    {
        pprev = pprev->next;
    }
 
    pprev->next = pprev->next->next;
 
    //释放pos位置空间
    free(pos);
    pos = NULL;
}
 
//删除pos之后的节点 
void SLNEraseAfter(SLN* pos)
{
    assert(pos);
 
    //如果pos之后的节点为空，则不执行删除操作
    if (pos->next == NULL)
    {
        return;
    }
 
    SLN* BlockToFree = pos->next;
    //如果pos之后的节点不为空，执行删除操作
    //将pos节点的存储下一个节点地址的部分更改为待删除节点的后一个节点地址
    pos->next = pos->next->next;
    free(BlockToFree);
    BlockToFree = NULL;
}
 
//销毁链表 
void SLNDesTroy(SLN** pphead)
{
    assert(pphead);
 
    SLN* pcur = *pphead;
    //循环销毁链表
    while (pcur)
    {
        SLN* BlockToFree = pcur;
        pcur = pcur->next;
        free(BlockToFree);
    }
    *pphead = NULL;
}

双链表

双向链表：即带头双向循环链表

在双向链表中，存在头结点，即默认有一个节点，但是该节点中不存储有效数据，只存储指向上一个节点和下一个节点的地址