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

数据结构2——单链表

news 来源：原创 2024/9/28 2:29:23

在数据结构1——顺序表（C语言版）中，我们已经了解了顺序表的使用和实现，总结一下顺序表的优点：

①尾插尾删效率足够快；

②下标的随机访问和修改也足够方便。

可除此之外顺序表也确实存在着不足：

①头部和中部的插入删除效率都不高（时间复杂度为O(N)）；

②扩容需要申请新空间，拷贝数据，释放旧空间，有一定的消耗；

③扩容可能存在空间浪费（我们的扩容函数是2倍增长，比如：当前容量是100，我需要再插入3个数据，按照我的2倍扩容机制就会扩容到200，这时就会浪费了97个数据的空间）。

了解了顺序表的不足，下面我们就来学习一下链表，看一看链表能不能解决顺序表的不足。

目录

1.链表

1.1链表的概念及结构

1.2 链表的分类

2.无头单链表的实现

1. 节点

2.遍历链表

3.动态增加新节点

4.查找（修改）

5.插入

5.1 尾插

5.2 头插

5.3 在pos之前插入x

5.4 在pos之后插入x 

6.删除

6.1 尾删

6.2 头删

6.3 删除pos位置

6.4 删除pos的后一个位置

7.测试（仅测试一个）

源代码

SList.h

SList.c

test.c

1.链表

为了避免像顺序表那样插入数据时造成扩容浪费，那我就边插入边扩容行不行呢？只要插入一个新数据我就开一块空间存一个。那么问题来了，如果这么搞，这些数据就不连续了啊，那还怎么像顺序表那样成为一个表结构呢？~~~~~~对！不要忘了指针，我们可以用指针把这写不连续的空间串起来啊！

1.1链表的概念及结构

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

也就是说，链表并不像顺序表那样在物理空间上是连续存储的，链表的每一个单位里存的不仅仅有数据域，还存的有指针域，我们把每一个这样的单位称为节点。

如图：

1.2 链表的分类

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

①单向或者双向

②带头或者不带头 

③循环或者非循环

④最常用的两个

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。

2.带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

2.无头单链表的实现

1. 节点

经过上面的分析我们得知，链表的主要结构为节点，所以我们先用结构体定义节点：

//定义节点
typedef int SLTDataType;//typedef节点的数据域typedef struct SListNode
{SLTDataType data;//定义节点的数据域struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;

2.遍历链表

//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;//定义当前节点//while (cur != NULL)//等于空就结束while (cur){printf("%d->", cur->data);cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点}printf("NULL\n");
}

3.动态增加新节点

//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);//malloc为空直接退出}newnode->data = x;newnode->next = NULL;return newnode;
}

4.查找（修改）

//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

5.插入

5.1 尾插

//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//改变结构体的指针，所以要用到指针的指针*pphead = newnode;}else{SLTNode* tail = *pphead;//定义尾节点while (tail->next != NULL)//只有尾节点的next指针为空{tail = tail->next;}//改变结构体，只需用到结构体的指针即可tail->next = newnode;}
}

5.2 头插

//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

5.3 在pos之前插入x

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

5.4 在pos之后插入x 

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;
}

6.删除

6.1 尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//1、空assert(*pphead);//2、一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else//3、一个以上节点   找尾{SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}
}

6.2 头删

//头删函数实现
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

6.3 删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(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;}
}

6.4 删除pos的后一个位置

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查pos是否为尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

7.测试（仅测试一个）

int main() 
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);return 0;
}

*源代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义节点
typedef int SLTDataType;//typedef节点的数据域typedef struct SListNode
{SLTDataType data;//定义节点的数据域struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;//遍历链表函数声明
void SLTPrint(SLTNode* phead);//增加新节点函数声明
SLTNode* BuySListNode(SLTDataType x);//尾插函数声明
void SLTPushBack(SLTNode** phead, SLTDataType x);
//头插函数声明
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删函数声明
void SLTPopBack(SLTNode** pphead);
//头删函数声明
void SLTPopFront(SLTNode** pphead);//查找下标pos函数声明
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter( SLTNode* pos, SLTDataType x);//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;//定义当前节点//while (cur != NULL)//等于空就结束while (cur){printf("%d->", cur->data);cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点}printf("NULL\n");
}//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);//malloc为空直接退出}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//改变结构体的指针，所以要用到指针的指针*pphead = newnode;}else{SLTNode* tail = *pphead;//定义尾节点while (tail->next != NULL)//只有尾节点的next指针为空{tail = tail->next;}//改变结构体，只需用到结构体的指针即可tail->next = newnode;}
}
//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删函数声明
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//1、空assert(*pphead);//2、一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else//3、一个以上节点   找尾{SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}
}
//头删函数实现
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;
}//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(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;}
}//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查pos是否为尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"int main() 
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);return 0;
}

相关文章：

  • 【C++】类型转换
  • 人工智能开发实时语音识别系统应用
  • USB2.0主机设备检测过程以及信号分析
  • 【算法业务】互联网风控业务中的拒绝推断场景算法应用分享（涉及半监督算法、异常检测、变分自编码、样本权重自适应调整、迁移学习等）
  • 2024年项目经理不能错过的开源项目管理系统大盘点：全面指南
  • 使用 Docker 部署 RStudio 的终极教程
  • 智算中心动环监控：构建高效、安全的数字基础设施@卓振思众
  • 51单片机-红外遥控器（NEC标准）-实验（红外遥控及调速电机）
  • Techub专访顾荣辉教授：解密CertiK的安全战略路线
  • 如何搭建适合自己的数据中台？六步法
  • 以串口接口为例介绍关于BSP底层架构开发的迭代过程
  • 足球预测模型理论:足球数据分析——XGBoost算法实战
  • Navicat数据库管理工具实现Excel、CSV文件导入到MySQL数据库
  • C#中NModbus4中常用的方法
  • 设计模式之装饰模式（Decorator）
  • [译] 理解数组在 PHP 内部的实现（给PHP开发者的PHP源码-第四部分）
  • Computed property XXX was assigned to but it has no setter
  •  D - 粉碎叛乱F - 其他起义
  • ES6语法详解(一)
  • JavaScript函数式编程（一）
  • JavaScript设计模式与开发实践系列之策略模式
  • Java面向对象及其三大特征
  • Node + FFmpeg 实现Canvas动画导出视频
  • PHP的Ev教程三(Periodic watcher)
  • Three.js 再探 - 写一个跳一跳极简版游戏
  • vue：响应原理
  • webpack+react项目初体验——记录我的webpack环境配置
  • 从零到一：用Phaser.js写意地开发小游戏（Chapter 3 - 加载游戏资源）
  • 基于axios的vue插件，让http请求更简单
  • 基于Volley网络库实现加载多种网络图片（包括GIF动态图片、圆形图片、普通图片）...
  • 前嗅ForeSpider采集配置界面介绍
  • 适配mpvue平台的的微信小程序日历组件mpvue-calendar
  • 数组大概知多少
  • 一份游戏开发学习路线
  • Java性能优化之JVM GC（垃圾回收机制）
  • TPG领衔财团投资轻奢珠宝品牌APM Monaco
  • ​经​纬​恒​润​二​面​​三​七​互​娱​一​面​​元​象​二​面​
  • # Spring Cloud Alibaba Nacos_配置中心与服务发现（四）
  • # 数据结构
  • ## 临床数据 两两比较 加显著性boxplot加显著性
  • （3）llvm ir转换过程
  • （4）logging（日志模块）
  • （C语言）输入自定义个数的整数，打印出最大值和最小值
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • （react踩过的坑）antd 如何同时获取一个select 的value和 label值
  • （二）Eureka服务搭建，服务注册，服务发现
  • (分布式缓存)Redis分片集群
  • （附源码）c#+winform实现远程开机（广域网可用）
  • （附源码）spring boot火车票售卖系统 毕业设计 211004
  • （论文阅读26/100）Weakly-supervised learning with convolutional neural networks
  • (算法)硬币问题
  • （一）Thymeleaf用法——Thymeleaf简介
  • (转)Mysql的优化设置
  • (转)关于多人操作数据的处理策略
  • （转载）Linux网络编程入门