当前位置: 首页> 娱乐> 八卦 > 【数据结构】线性表之《无头单链表》超详细实现

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

时间:2025/7/11 14:01:37来源:https://blog.csdn.net/2203_76003626/article/details/139725477 浏览次数:0次

单链表

  • 一.链表的概念及结构
  • 二.顺序表与链表的区别与联系
  • 三.单链表的实现
    • 1.创建单链表
    • 2.初始化单链表
    • 3.购买节点
    • 4.打印单链表
    • 5.插入操作
      • 1.头插
      • 2.尾插
      • 3.给定位置之前插入
    • 6.删除操作
      • 1.头删
      • 2.尾删
      • 3.删除给定位置的结点
    • 7.查找数据
    • 8.修改数据
    • 9.求单链表长度
    • 10.清空单链表
    • 11.销毁单链表
  • 四.模块化源代码
    • 1.SingleLinkList.h
    • 2.SingleLinkList.c
    • 3.test.c
  • 五.链表必做OJ题

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

一.链表的概念及结构

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

typedef int SLLDataType; //增强程序的可维护性typedef struct SLLNode
{SLLDataType data;     //数据域struct SLLNode* next; //指针域
}SLLNode;

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

  1. 单向,双向。
  2. 带头,不带头。
  3. 循环,非循环。

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

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结
    构的子结构,如哈希桶图的邻接表等等。另外这种结构在笔试面试中出现很多。

  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都
    是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带
    来很多优势,实现反而简单了,后面我们代码实现了就知道了。

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

顺序表
优点:空间连续,支持随机访问。
缺点:如果空间不够要增容,增容会付出一定的性能消耗,其次可能存在一定的空间浪费;头部或者中部左右的插入 ,删除效率低——>O(N)。

链表
优点:任意位置的插入删除的时间复杂度为O(1);没有增容消耗,按需申请节点空间,但是不用了记得直接释放。
缺点:以节点为单位存储,不支持随机访问。

三.单链表的实现

1.创建单链表

链表由节点组成,每个节点要存放数据下一个节点的地址(为了找到下一个节点)。由于存放的是不同类型的数据,所以定义一个结构体,成员则有:数据域,指针域。

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

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

2.初始化单链表

注意:以下函数中的参数 phead 对应 plistpphead 对应 &plist

为什么这么做呢?
答:值传递地址传递的问题。

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

在这里插入图片描述

一般初始化我们都习惯赋值为0,即单链表plist(*pphead)赋值为NULL。

void SLLInit(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这一结束条件,循环遍历打印即可,较为简单。

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

5.插入操作

1.头插

头插思想:创建新节点,新节点的指针域指向单链表的头节点(实际上就是单链表),再更新单链表的头节点指向新节点。

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

2.尾插

尾插思想

  1. 当单链表为NULL:单链表的头指针指向新节点。
  2. 当单链表不为NULL:找到尾节点,尾节点的指针域指向新节点。
void SLLPushBack(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.给定位置之前插入

思路:

  1. 当给定的位置恰好是头节点的地址时,直接调用头插。
  2. 否则要寻找 pos 指向的节点的前一个节点,新节点的指针域指向 pos 指向的节点,前一个节点的指针域指向新节点。
void SLLInsert(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.头删

思路:

  1. 当单链表为NULL:无需操作。
  2. 当单链表不为NULL:先保存头节点的下一个节点的指针,再释放头指针,最后更新头节点为保存的哪个头节点。
void SLLPopFront(SLLNode** pphead)
{assert(pphead);//单链表为空if (*pphead == NULL){return; //无需释放,直接退出}else{SLLNode* cur = (*pphead)->next; //定位头节点的下一个节点free(*pphead); //释放头节点*pphead = cur; //更新单链表的头节点}
}

2.尾删

思路略复杂:

  1. 当单链表为NULL:无需操作。
  2. 当单链表只有一个节点:释放头节点,将头指针置为NULL。
  3. 当单链表有多个节点:先找到尾节点的前一个节点并保存,释放尾节点,将保存的节点的指针域置为NULL。
void SLLPopBack(SLLNode** pphead)
{assert(pphead);//单链表为空if (*pphead == NULL){return; //无需释放,直接退出}//单链表只有一个节点else if ((*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.删除给定位置的结点

思路:

  1. 当待删除的节点为头节点时,直接调用头删即可。
  2. 否则保存待删除的节点的前一个节点,将该节点的指针域指向待删除的节点的下一个节点,最后释放待删除的节点即可。
void SLLErase(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;}return NULL; //找不到,返回NULL
}

8.修改数据

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

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

9.求单链表长度

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

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

10.清空单链表

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

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

11.销毁单链表

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

void SLLDestory(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>typedef int SLLDataType; //增强程序的可维护性typedef struct SLLNode
{SLLDataType data;     //数据域struct SLLNode* next; //指针域
}SLLNode;void SLLInit(SLLNode** pphead);//初始化单链表(需要修改单链表,传地址)SLLNode* BuyNode(SLLDataType x);//购买节点void SLLPrint(SLLNode* phead);//打印单链表(无需修改单链表,传值)void SLLPushBack(SLLNode** pphead, SLLDataType x);//尾插(同理,传地址)void SLLPushFront(SLLNode** pphead, SLLDataType x);//头插void SLLPopBack(SLLNode** pphead);//尾删void SLLPopFront(SLLNode** pphead);//头删SLLNode* SLLFind(SLLNode* phead, SLLDataType x);//查找void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x);//插入:通过《SLLFind函数》找到pos,在pos前插入xvoid SLLErase(SLLNode** pphead, SLLNode* pos);//删除:通过《SLLFind函数》找到pos,删除pos位置的值void SLLModify(SLLNode** pphead, SLLNode* pos, SLLDataType x);//修改:通过《SLLFind函数》找到pos,修改pos位置的值int SLLLength(SLLNode* phead);//求单链表的长度void SLLClear(SLLNode** pphead);//清空单链表void SLLDestory(SLLNode** pphead);//销毁单链表#endif

2.SingleLinkList.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SingleLinkList.h"void SLLInit(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; //返回新节点
}void SLLPrint(SLLNode* phead)
{SLLNode* cur = phead; //定位单链表的头节点while (cur != NULL){printf("%d->", cur->data);cur = cur->next; //更新为下一节点}printf("NULL\n");
}void SLLPushBack(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; //尾节点,链接新节点}
}void SLLPushFront(SLLNode** pphead, SLLDataType x)
{assert(pphead);SLLNode* newNode = BuyNode(x); //购买节点newNode->next = *pphead; //新节点头插*pphead = newNode; //更新单链表的头节点
}void SLLPopBack(SLLNode** pphead)
{assert(pphead);//单链表为空if (*pphead == NULL){return; //无需释放,直接退出}//单链表只有一个节点else if ((*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}
}void SLLPopFront(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;}return NULL; //找不到,返回NULL
}void SLLInsert(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; }
}void SLLErase(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,预防野指针}
}void SLLModify(SLLNode** pphead, SLLNode* pos, SLLDataType x)
{assert(pphead);assert(pos); //防止对NULL解引用导致程序崩溃pos->data = x; //直接修改就行了
}int SLLLength(SLLNode* phead)
{int len = 0;SLLNode* cur = phead;while (cur != NULL){cur = cur->next;len++;}return len;
}void SLLClear(SLLNode** pphead)
{assert(pphead);//从头开始逐个释放SLLNode* cur = *pphead;while (cur != NULL){*pphead = cur->next;free(cur);cur = *pphead;}
}void SLLDestory(SLLNode** pphead)
{assert(pphead);SLLClear(pphead); //与清空单链表无区别
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SingleLinkList.h"enum //匿名枚举
{EXIT,PUSHBACK,PUSHFRONT,POPBACK,POPFRONT,INSERT,ERASE,FIND,MODIFY,PRINT,LENGTH,CLEAR
};void Menu()
{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");
}int main()
{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);int ret = SLLFind(plist, value);if (ret == -1){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); //记得最后要销毁,防止内存泄漏return 0;
}

五.链表必做OJ题

  1. 反转单链表
  2. 链表的中间结点
  3. 合并两个有序链表
  4. 判断链表是否有环?
  5. 求环形链表的入口点?

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

创作不易,如果能帮到你的话能赏个三连吗?感谢啦!!!

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: