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

数据结构 03（线性：单链表）

web 2025/9/4 12:11:26

目录

概念与结构

链表的打印

实现单链表

创造头文件

申请空间

尾插功能

头插功能

尾删功能

头删功能

在任意结点前插入

在任意节点后插入

在任意结点前与后删除

销毁

单链表整体实现

SList.h

SList.c

概念与结构

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

结点：与顺序表不同的是，链表里的每节都是独立申请下来的空间，我们称之为“结点/结点。结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

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

链表的打印

那么我们该怎么打印链表呢？和遍历数组一样，使用循环来解决。

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

实现单链表

创造头文件

创建一个头文件，在里面创建和声明所需要的头文件、函数和单链表结构。如下：

​
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;//定义数据类型方便改代码//以下是单链表的基本结构
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//以下是对所写函数的声明，所有接下来都会写到
void SLTPrint(SLTNode* phead);
SLTNode* SLTBuyNode(SLTDataType x);
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);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);​

申请空间

那么怎么申请空间呢？函数需要接受需要存储的数据，接下来写申请空间的函数，如下：

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//申请空间if (newnode == NULL)          //检查有没有申请成功{perror("malloc fail!");exit(1);}newnode->data = x;            //储存需要存的数据newnode->next = NULL;return newnode;               //把空间返回回去
}

尾插功能

在main函数创建一个头结点，比如 SLTNode* phead = NULL; 这些功能函数传参基本是传头结点。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{                                        //使用二级指针是因为要修改ppheadassert(pphead);                      //检查指针SLTNode* newnode = SLTBuyNode(x);    //申请空间if (*pphead == NULL)                 //头结点为空的情况{*pphead = newnode;}else                                 //已经有结点的情况{SLTNode* ptail = *pphead;while (ptail->next)              //寻找最后一个结点{ptail = ptail->next;}ptail->next = newnode;}
}

头插功能

头插功能就很简单了改变头文件的地址就好。

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

尾删功能

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL)  //头结点就是尾结点的情况{free(*pphead);*pphead = NULL;}else                          //用循环找最后一个结点{SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}

头删功能

头删很简单，把原本头结点的下一个结点改变为头结点就好。

SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{SLTNode* pcur = pphead;while (pcur){if (pcur->data == x){return pcur;}}return NULL;
}

在任意结点前插入

和尾插操作类似。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);if (*pphead == pos)                       //在头结点前就是头插{SLTPushFront(pphead, x);}else                                      //找到pos结点，把newnode插到两个结点中间{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

在任意节点后插入

这就很简单了，直接插到pos结点和pos的next结点中间就好了。

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

在任意结点前与后删除

了解前面的操作后，这个操作就很简单了，原理都很相同。

前：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);if (pos == *pphead){SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

后：

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* nextnode = pos->next;pos->next = nextnode->next;free(nextnode);nextnode = NULL;
}

销毁

销毁要用循环一个一个结点的销毁。如下：

void SLTDestroy(SLTNode** 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
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
SLTNode* SLTBuyNode(SLTDataType x);
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);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{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 && *pphead);SLTNode* nextnode = (*pphead)->next;free(*pphead);*pphead = nextnode;
}SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{SLTNode* pcur = pphead;while (pcur){if (pcur->data == x){return pcur;}}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);if (pos == *pphead){SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* nextnode = pos->next;pos->next = nextnode->next;free(nextnode);nextnode = NULL;
}void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

http://www.xdnf.cn/news/19322.html

相关文章：

  • web渗透之RCE漏洞
  • Java中使用JSONUtil处理JSON数据：从前端到后端的完美转换
  • [Mysql数据库] 知识点总结7
  • 06.《STP 基础原理与配置详解》
  • DFS 回溯 【各种题型+对应LeetCode习题练习】
  • 突发，支付宝发布公告
  • 一体化步进伺服电机在汽车线束焊接设备中的应用案例
  • LZ4 解压工具（WPF / .NET 8）说明书
  • 【金仓数据库产品体验官】KingbaseES-ORACLE兼容版快速体验
  • 深入理解drv_spi.c后，完全正向亲手移植rt-thread的drv_spi.c驱动 (基于stm32h750 artpi）
  • Java函数式编程之【流（Stream）性能优化】
  • WPF和WinFrom区别
  • 计算机毕设 java 阿歹果园养鸡场管理系统 基于 SSM 框架的果园养鸡场全流程管理系统设计与实现 Java+MySQL 的养殖生产与进销存一体化平台开发
  • 汽车专卖店管理系统的设计与实现（代码+数据库+LW）
  • Langflow核心技术学习笔记
  • 探索 XGBoost 与 LightGBM 的差异：哪个更适合你的项目？
  • 基于TCN-BiLSTM-SelfAttention神经网络的多输入单输出回归预测【MATLAB】
  • 力扣（LeetCode) ——645. 错误的集合（C语言）
  • 整体设计 的语言设计：通用模型语言的标准模板语言的规格模式语言（搜狗汪仔答问）
  • GooglePlay提审问题记录
  • 国家统计局数据分析01——机器学习
  • wpf之附加属性
  • Odoo与Django 的区别是什么？
  • ADFS 和 OAuth 的区别
  • 龙迅#LT7641GX适用于四路HDMI2.1/DP/TPYE-C转HDMI2.1混切应用,分辨率高达8K60HZ!
  • 线性表和顺序表
  • 数据存储——数据库
  • 安卓开发---SimpleAdapter
  • ansible的playbook练习题
  • shell学习（二）