当前位置： 首页 > news >正文

数据结构——单链表专题

news 2025/7/6 3:31:34

目录

    • 1. 链表的概念及结构
    • 2. 实现单链表
      • 初始化
      • 尾插
      • 头插
      • 尾删
      • 头删
      • 查找
      • 在指定位置之前插入数据
      • 在指定位置之后插入数据
      • 删除指定位之前的节点
      • 删除指定位置之后pos节点
      • 销毁链表
    • 3. 完整代码
      • test.c
      • SList.h
    • 4. 链表的分类

1. 链表的概念及结构

在顺序表中存在一定的问题：

  1. 顺序表的中间/头部插入、删除需要挪动数据
  2. 扩容存在性能的消耗
  3. 会有空间的浪费

而链表是独立的节点组成

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

链表、顺序表都是线性表

逻辑结构一定是线性的
物理结构不一定是线性的

在这里插入图片描述

图中指针变量plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向第二个节点时，只需要修改plist保存的内容为0x0012FFA0

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

链表是由一个一个的节点组成的
一个节点由两部分组成：要存储的数据+指针

int a = 1;
int* pa = &a;

节点结构的定义

struct SListNode{
int data;
struct SListNode* next;
}

在这里插入图片描述

链表结构体的打印方式：

在这里插入图片描述

补充说明：

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

2. 实现单链表

初始化

typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{SLTDataType data;//节点数据struct SListNode* next;//指针变量保存下一个节点的地址
}SLTNode;

尾插

//公共部分，开辟一个新的节点
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}

在这里插入图片描述

在这里插入图片描述

头插

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

在这里插入图片描述

尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}

在这里插入图片描述

头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}

在这里插入图片描述

查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}

在这里插入图片描述

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}

在这里插入图片描述

在指定位置之后插入数据

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

在这里插入图片描述

删除指定位之前的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}

在这里插入图片描述

删除指定位置之后pos节点

//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}}

在这里插入图片描述

销毁链表

//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

在这里插入图片描述

3. 完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <stdio.h>//void SlistTest1()
//{
//	//一般不会这样去创建链表，这里只是为了给大家展示链表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;//定一个指针指向第一个节点
//	SLTPrint(plist);
//}void SlistTest2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void SlistTest3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//头删SLTPopFront(&plist);SLTPrint(plist);//查找SLTNode* FindRet = SLTFind(&plist, 0);if (FindRet){printf("找到了\n");}else {printf("未找到\n");}SLTInsert(&plist, FindRet, 100);SLTPrint(plist);SLTInsertAfter(FindRet, 200);SLTPrint(plist);//删除指定位置的节点SLTErase(&plist, FindRet);SLTPrint(plist);//销毁节点SListDesTory(&plist);
}int main()
{SlistTest3();//SlistTest2();//SlistTest1();return 0;
}

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <assert.h>//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除指定位之前的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

SList.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//链表的打印
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** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除指定位置之前pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//销毁链表
void SListDesTory(SLTNode** pphead);

4. 链表的分类

链表的结构非常多样，一下情况组合组合起来就有8种链表结构：

在这里插入图片描述
链表说明：

在这里插入图片描述

在单链表中，“头结点”的“头”和“带头”链表是两个概念
单链表中提到的“头结点”指的是第一个有效的节点
“带头”链表里的“头”指的是无效的节点

虽然链表的种类非常之多，但是使用比较多的只有两种：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）

http://www.lryc.cn/news/301611.html

相关文章：

  • Linux：开源世界的王者
  • ⭐北邮复试刷题103. 二叉树的锯齿形层序遍历 (力扣每日一题)
  • 文件上传漏洞--Upload-labs--Pass07--点绕过
  • MySQL高级特性篇(1)-JSON数据类型的应用
  • 如何用Qt实现一个无标题栏、半透明、置顶（悬浮）的窗口
  • ViT: transformer在图像领域的应用
  • Sora 的工作原理（及其意义）
  • Java学习笔记2024/2/16
  • XLNet做文本分类
  • Swift 5.9 新 @Observable 对象在 SwiftUI 使用中的陷阱与解决
  • 分享一个学英语的网站
  • 【动态规划】【C++算法】2742. 给墙壁刷油漆
  • 【后端高频面试题--设计模式上篇】
  • P3141 [USACO16FEB] Fenced In P题解
  • Android Compose 一个音视频APP——Magic Music Player
  • Nginx实战：安装搭建
  • Qt之条件变量QWaitCondition详解(从使用到原理分析全)
  • OpenSource - 一站式自动化运维及自动化部署平台
  • 【后端高频面试题--设计模式下篇】
  • 这才是大学生该做的副业，别再痴迷于游戏了！
  • Ubuntu20.04 安装jekyll
  • AWK语言
  • 精通Nmap：网络扫描与安全的终极武器
  • Java 学习和实践笔记（11）
  • 开发实体类
  • 人工智能学习与实训笔记（十五）：Scikit-learn库的基础与使用
  • 插值与拟合算法介绍
  • 下一代Windows系统曝光：基于GPT-4V，Agent跨应用调度，代号UFO
  • 二.自定义头文件
  • 【AIGC】Stable Diffusion之模型微调工具