【数据结构】线性表之《无头单链表》超详细实现

单链表

前言：在前一章节成功实现了顺序表后，对数据结构的理解已经初具雏形，但这只是启蒙阶段，接下来我们将进入链表的探索学习。链表作为数据结构的另一种形式，不仅仅是简单的表述，它承载了更多的内涵和抽象思维，有助于深入理解数据在计算机科学中的精髓。

一.链表的概念及结构

概念：链表是一种物理存储结构上

非连续、非顺序

的存储结构，数据元素的逻辑顺序是通过链表
中的

指针链接

次序实现的。

typedefint SLLDataType;//增强程序的可维护性typedefstructSLLNode{
    SLLDataType data;//数据域structSLLNode* next;//指针域}SLLNode;

在这里插入图片描述
实际中要实现的链表结构非常多样（2^3=8中）。

单向，双向。
带头，不带头。
循环，非循环。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
在这里插入图片描述

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

二.顺序表与链表的区别与联系

顺序表

：

优点

：空间连续，支持随机访问。

缺点

：如果空间不够要增容，增容会付出一定的性能消耗，其次可能存在一定的空间浪费；头部或者中部左右的插入，删除效率低——>O(N)。

链表

：

优点

：任意位置的插入删除的时间复杂度为O(1)；没有增容消耗，按需申请节点空间，但是不用了记得直接释放。

缺点

：以节点为单位存储，不支持随机访问。

三.单链表的实现

1.创建单链表

链表由节点组成，每个节点要存放

数据

与

下一个节点的地址

（为了找到下一个节点）。由于存放的是不同类型的数据，所以定义一个结构体，成员则有：数据域，指针域。

单链表：指向该节点的指针。

typedefint SLLDataType;//增强程序的可维护性typedefstructSLLNode//单链表节点{
    SLLDataType data;//数据域structSLLNode* next;//指针域}SLLNode;
SLLNode* plist;//单链表

2.初始化单链表

注意：以下函数中的参数

phead

对应

plist

；

pphead

对应

&plist

。

为什么这么做呢？
答：

值传递

与

地址传递

的问题。

无需改变链表的话（比如：打印链表，查找数据等…），只需传入值。
需要改变链表的话（头插，头删等…），需要传入地址。
即使 plist 是一级指针，但是传参时仍会创建 phead 存放 plist 。本质依旧是传值。

在这里插入图片描述

一般初始化我们都习惯赋值为0，即单链表plist（*pphead）赋值为NULL。

voidSLLInit(SLLNode** pphead){assert(pphead);//断言*pphead =NULL;}

3.购买节点

由于头插，尾插，按位置插入链表，都要先准备一个节点。为了减少代码的重复，直接对其进行封装，创建新节点的时候直接调用该接口就行。

SLLNode*BuyNode(SLLDataType x){
    SLLNode* newNode =(SLLNode*)malloc(sizeof(SLLNode));//申请节点空间if(newNode ==NULL)//申请失败{perror("malloc fail");exit(1);}//申请成功
    newNode->data = x;
    newNode->next =NULL;return newNode;//返回新节点}

4.打印单链表

定义一个指针指向单链表，利用NULL这一结束条件，循环遍历打印即可，较为简单。

voidSLLPrint(SLLNode* phead){
    SLLNode* cur = phead;//定位单链表的头节点while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;//更新为下一节点}printf("NULL\n");}

5.插入操作

1.头插

头插思想：创建新节点，新节点的指针域指向单链表的头节点（实际上就是单链表），再更新单链表的头节点指向新节点。

voidSLLPushFront(SLLNode** pphead, SLLDataType x){assert(pphead);
    SLLNode* newNode =BuyNode(x);//购买节点
    newNode->next =*pphead;//新节点头插*pphead = newNode;//更新单链表的头节点}

2.尾插

尾插思想

当单链表为NULL：单链表的头指针指向新节点。
当单链表不为NULL：找到尾节点，尾节点的指针域指向新节点。

voidSLLPushBack(SLLNode** pphead, SLLDataType x){assert(pphead);
    SLLNode* newNode =BuyNode(x);//购买节点if(*pphead ==NULL)//单链表为空{*pphead = newNode;//更新单链表的头节点}else//单链表不为空{
        SLLNode* tail =*pphead;//寻找尾节点while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newNode;//尾节点，链接新节点}}

3.给定位置之前插入

思路：

当给定的位置恰好是头节点的地址时，直接调用头插。
否则要寻找 pos 指向的节点的前一个节点，新节点的指针域指向 pos 指向的节点，前一个节点的指针域指向新节点。

voidSLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x){assert(pphead);assert(pos);if(pos ==*pphead)//pos是头节点的地址{SLLPushFront(pphead, x);//直接头插}else{
        SLLNode* newNode =BuyNode(x);//购买节点
        SLLNode* prev =*pphead;//定位pos前一个节点while(prev->next != pos){
            prev = prev->next;}//插入操作
        newNode->next = pos; 
        prev->next = newNode;}}

6.删除操作

1.头删

思路：

当单链表为NULL：无需操作。
当单链表不为NULL：先保存头节点的下一个节点的指针，再释放头指针，最后更新头节点为保存的哪个头节点。

voidSLLPopFront(SLLNode** pphead){assert(pphead);//单链表为空if(*pphead ==NULL){return;//无需释放，直接退出}else{
        SLLNode* cur =(*pphead)->next;//定位头节点的下一个节点free(*pphead);//释放头节点*pphead = cur;//更新单链表的头节点}}

2.尾删

思路略复杂：

当单链表为NULL：无需操作。
当单链表只有一个节点：释放头节点，将头指针置为NULL。
当单链表有多个节点：先找到尾节点的前一个节点并保存，释放尾节点，将保存的节点的指针域置为NULL。

voidSLLPopBack(SLLNode** pphead){assert(pphead);//单链表为空if(*pphead ==NULL){return;//无需释放，直接退出}//单链表只有一个节点elseif((*pphead)->next ==NULL)//注意：加上括号{free(*pphead);//释放头节点*pphead =NULL;//单链表置为NULL}//单链表有多个节点else{
        SLLNode* prev =NULL;//定位尾节点前一个节点
        SLLNode* tail =*pphead;//定位尾节点while(tail->next !=NULL){
            prev = tail;
            tail = tail->next;}free(tail);//释放尾节点
        tail =NULL;//置为NULL，预防野指针
        prev->next =NULL;//变为尾节点后置为NULL}}

3.删除给定位置的结点

思路：

当待删除的节点为头节点时，直接调用头删即可。
否则保存待删除的节点的前一个节点，将该节点的指针域指向待删除的节点的下一个节点，最后释放待删除的节点即可。

voidSLLErase(SLLNode** pphead, SLLNode* pos){assert(pphead);assert(pos);if(pos ==*pphead)//pos是头节点的地址{SLLPopFront(pphead);//直接头删}else{
        SLLNode* prev =*pphead;//定位pos前一个节点while(prev->next != pos){
            prev = prev->next;}
        prev->next = pos->next;//删除过程free(pos);//释放节点
        pos =NULL;//置为NULL，预防野指针}}

7.查找数据

思路：循环遍历单链表即可，找到返回地址，未找到返回NULL。

SLLNode*SLLFind(SLLNode* phead, SLLDataType x){
    SLLNode* cur = phead;//定位值为x的节点while(cur !=NULL)//遍历单链表{if(cur->data == x){return cur;//找到了，返回节点的地址}
        cur = cur->next;}returnNULL;//找不到，返回NULL}

8.修改数据

思路：直接通过SLLFind函数得到地址，在该处修改即可，较为简单，同时SLLErase与SLLInsert函数都要通过SLLFind函数得到地址。

voidSLLModify(SLLNode** pphead, SLLNode* pos, SLLDataType x){assert(pphead);assert(pos);//防止对NULL解引用导致程序崩溃
    pos->data = x;//直接修改就行了}

9.求单链表长度

思路：利用头指针，向后循环遍历直到不为空即可。

intSLLLength(SLLNode* phead){int len =0;
    SLLNode* cur = phead;while(cur !=NULL){
        cur = cur->next;
        len++;}return len;}

10.清空单链表

思路：这里不像顺序表一样，顺序表只需释放一个指针arr（连续开辟的空间），而单链表物理上是不连续的，需要释放每一个节点，循环遍历单链表即可。

voidSLLClear(SLLNode** pphead){assert(pphead);//从头开始逐个释放
    SLLNode* cur =*pphead;while(cur !=NULL){*pphead = cur->next;free(cur);
        cur =*pphead;}}

11.销毁单链表

思路：自认为销毁与清空单链表没有太大区别

voidSLLDestory(SLLNode** pphead){assert(pphead);SLLClear(pphead);//与清空单链表无区别}

四.模块化源代码

1.SingleLinkList.h

//#pragma once 防止头文件被重复包含，导致效率下降#ifndef__SINGLELINKLIST_H__#define__SINGLELINKLIST_H__#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLLDataType;//增强程序的可维护性typedefstructSLLNode{
    SLLDataType data;//数据域structSLLNode* next;//指针域}SLLNode;voidSLLInit(SLLNode** pphead);//初始化单链表（需要修改单链表，传地址）
SLLNode*BuyNode(SLLDataType x);//购买节点voidSLLPrint(SLLNode* phead);//打印单链表（无需修改单链表，传值）voidSLLPushBack(SLLNode** pphead, SLLDataType x);//尾插（同理，传地址）voidSLLPushFront(SLLNode** pphead, SLLDataType x);//头插voidSLLPopBack(SLLNode** pphead);//尾删voidSLLPopFront(SLLNode** pphead);//头删
SLLNode*SLLFind(SLLNode* phead, SLLDataType x);//查找voidSLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x);//插入：通过《SLLFind函数》找到pos，在pos前插入xvoidSLLErase(SLLNode** pphead, SLLNode* pos);//删除：通过《SLLFind函数》找到pos，删除pos位置的值voidSLLModify(SLLNode** pphead, SLLNode* pos, SLLDataType x);//修改：通过《SLLFind函数》找到pos，修改pos位置的值intSLLLength(SLLNode* phead);//求单链表的长度voidSLLClear(SLLNode** pphead);//清空单链表voidSLLDestory(SLLNode** pphead);//销毁单链表#endif

2.SingleLinkList.c

#define_CRT_SECURE_NO_WARNINGS1#include"SingleLinkList.h"voidSLLInit(SLLNode** pphead){assert(pphead);//断言*pphead =NULL;}
SLLNode*BuyNode(SLLDataType x){
    SLLNode* newNode =(SLLNode*)malloc(sizeof(SLLNode));//申请节点空间if(newNode ==NULL)//申请失败{perror("malloc fail");exit(1);}//申请成功
    newNode->data = x;
    newNode->next =NULL;return newNode;//返回新节点}voidSLLPrint(SLLNode* phead){
    SLLNode* cur = phead;//定位单链表的头节点while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;//更新为下一节点}printf("NULL\n");}voidSLLPushBack(SLLNode** pphead, SLLDataType x){assert(pphead);
    SLLNode* newNode =BuyNode(x);//购买节点if(*pphead ==NULL)//单链表为空{*pphead = newNode;//更新单链表的头节点}else//单链表不为空{
        SLLNode* tail =*pphead;//寻找尾节点while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newNode;//尾节点，链接新节点}}voidSLLPushFront(SLLNode** pphead, SLLDataType x){assert(pphead);
    SLLNode* newNode =BuyNode(x);//购买节点
    newNode->next =*pphead;//新节点头插*pphead = newNode;//更新单链表的头节点}voidSLLPopBack(SLLNode** pphead){assert(pphead);//单链表为空if(*pphead ==NULL){return;//无需释放，直接退出}//单链表只有一个节点elseif((*pphead)->next ==NULL)//注意：加上括号{free(*pphead);//释放头节点*pphead =NULL;//单链表置为NULL}//单链表有多个节点else{
        SLLNode* prev =NULL;//定位尾节点前一个节点
        SLLNode* tail =*pphead;//定位尾节点while(tail->next !=NULL){
            prev = tail;
            tail = tail->next;}free(tail);//释放尾节点
        tail =NULL;//置为NULL，预防野指针
        prev->next =NULL;//变为尾节点后置为NULL}}voidSLLPopFront(SLLNode** pphead){assert(pphead);//单链表为空if(*pphead ==NULL){return;//无需释放，直接退出}else{
        SLLNode* cur =(*pphead)->next;//定位头节点的下一个节点free(*pphead);//释放头节点*pphead = cur;//更新单链表的头节点}}
SLLNode*SLLFind(SLLNode* phead, SLLDataType x){
    SLLNode* cur = phead;//定位值为x的节点while(cur !=NULL)//遍历单链表{if(cur->data == x){return cur;//找到了，返回节点的地址}
        cur = cur->next;}returnNULL;//找不到，返回NULL}voidSLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x){assert(pphead);assert(pos);if(pos ==*pphead)//pos是头节点的地址{SLLPushFront(pphead, x);//直接头插}else{
        SLLNode* newNode =BuyNode(x);//购买节点
        SLLNode* prev =*pphead;//定位pos前一个节点while(prev->next != pos){
            prev = prev->next;}//插入操作
        newNode->next = pos; 
        prev->next = newNode;}}voidSLLErase(SLLNode** pphead, SLLNode* pos){assert(pphead);if(pos ==*pphead)//pos是头节点的地址{SLLPopFront(pphead);//直接头删}else{
        SLLNode* prev =*pphead;//定位pos前一个节点while(prev->next != pos){
            prev = prev->next;}
        prev->next = pos->next;//删除过程free(pos);//释放节点
        pos =NULL;//置为NULL，预防野指针}}voidSLLModify(SLLNode** pphead, SLLNode* pos, SLLDataType x){assert(pphead);assert(pos);//防止对NULL解引用导致程序崩溃
    pos->data = x;//直接修改就行了}intSLLLength(SLLNode* phead){int len =0;
    SLLNode* cur = phead;while(cur !=NULL){
        cur = cur->next;
        len++;}return len;}voidSLLClear(SLLNode** pphead){assert(pphead);//从头开始逐个释放
    SLLNode* cur =*pphead;while(cur !=NULL){*pphead = cur->next;free(cur);
        cur =*pphead;}}voidSLLDestory(SLLNode** pphead){assert(pphead);SLLClear(pphead);//与清空单链表无区别}

3.test.c

#define_CRT_SECURE_NO_WARNINGS1#include"SingleLinkList.h"enum//匿名枚举{
    EXIT,
    PUSHBACK,
    PUSHFRONT,
    POPBACK,
    POPFRONT,
    INSERT,
    ERASE,
    FIND,
    MODIFY,
    PRINT,
    LENGTH,
    CLEAR
};voidMenu(){printf("*************单链表************\n");printf("****1.尾插           2.头插****\n");printf("****3.尾删           4.头删****\n");printf("****5.插入           6.删除****\n");printf("****7.查找           8.修改****\n");printf("****9.打印          10.长度****\n");printf("***11.清空           0.退出****\n");printf("*******************************\n");}intmain(){
    SLLNode* plist;SLLInit(&plist);int select =0;//操作选项
    SLLDataType value;//接收值
    SLLDataType value1;//接收值
    SLLNode* pos =NULL;//接收指针do{Menu();printf("请输入您的操作：");scanf("%d",&select);switch(select){case EXIT:printf("退出单链表!\n");break;case PUSHBACK:printf("请输入您要尾插的值(输入-1代表结束)：");while((scanf("%d",&value), value !=-1))//逗号表达式{SLLPushBack(&plist, value);}break;case PUSHFRONT:printf("请输入您要头插的值(输入-1代表结束)：");do{scanf("%d",&value);if(value !=-1){SLLPushFront(&plist, value);}}while(value !=-1);break;case POPBACK:SLLPopBack(&plist);break;case POPFRONT:SLLPopFront(&plist);break;case INSERT:printf("请输入您要插入到《何值前面》以及《插入的值》：");scanf("%d %d",&value1,&value);
            pos =SLLFind(plist, value1);if(pos !=NULL){SLLInsert(&plist, pos, value);}else{printf("该值不存在，无法插入!\n");}break;case ERASE:printf("请输入您要删除的值：");scanf("%d",&value);
            pos =SLLFind(plist, value);if(pos !=NULL){SLLErase(&plist, pos);}else{printf("该值不存在，无法删除!\n");}break;case FIND:printf("请输入您要查找的值：");scanf("%d",&value);
            pos =SLLFind(plist, value);if(pos ==NULL){printf("您要查找的值不存在!\n");}else{printf("您要查找的值存在!\n");}break;case MODIFY:printf("请输入您要《要修改的值》以及《修改后的值》：");scanf("%d %d",&value1,&value);
            pos =SLLFind(plist, value1);if(pos !=NULL){SLLModify(&plist, pos, value);}else{printf("该值不存在，无法修改!\n");}break;case PRINT:SLLPrint(plist);break;case LENGTH:printf("单链表的长度：%d\n",SLLLength(plist));break;case CLEAR:SLLClear(&plist);break;}}while(select);SLLDestory(&plist);//记得最后要销毁，防止内存泄漏return0;}

五.链表必做OJ题

反转单链表
链表的中间结点
合并两个有序链表
判断链表是否有环？
求环形链表的入口点？

以后还会更新其余的链表：带头，循环，双链等等组合的链表。

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！

标签：数据结构 c语言开发语言

本文转载自: https://blog.csdn.net/2203_76003626/article/details/139725477
版权归原作者 清风~徐~来 所有，如有侵权，请联系我们删除。