数据结构：线性表之-单向链表(无头)

目录

什么是单向链表

顺序表和链表的区别和联系

顺序表：

链表：

链表表示(单项)和实现

1.1 链表的概念及结构

1.2单链表(无头)的实现

所用文件

将有以下功能：

链表定义

创建新链表元素

尾插

头插

尾删

头删

查找-给一个节点的指针

改

pos位置之前插入

删除pos位置的值

成品展示

SList.h

SList.c

test.c

什么是单向链表

单向链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。每个节点只能访问它后面的节点，而不能访问前面的节点。

单向链表的特点：

  • 每个节点包含数据和指向下一个节点的指针。
  • 最后一个节点的指针指向空值（NULL），表示链表的结束。
  • 可以动态地添加或删除节点，链表的长度可以根据需要进行扩展或缩小。
  • 可以根据指针迅速插入或删除节点，而不需要移动其他节点。

单向链表相对于数组来说，具有一些优点和缺点：

  • 优点：插入和删除元素的时间复杂度为O(1)，不需要像数组一样进行元素的移动；链表长度可以动态调整，没有固定大小的限制。
  • 缺点：要访问特定位置的元素需要从头开始遍历，时间复杂度为O(n)；相比于数组，在使用额外的指针存储下一个节点的信息，会占用更多的内存空间。

由于单向链表的特点，它常常被用于需要频繁插入和删除元素的场景，或者在事先无法确定数据大小和数量的情况下使用。

顺序表和链表的区别和联系

顺序表：

优点：
空间连续、支持随机访问
缺点：

  1. 中间或前面部分的插入删除时间复杂度O(N)
  2. 2.增容的代价比较大。

链表：

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

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

链表表示(单项)和实现

1.1 链表的概念及结构

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

1.2单链表(无头)的实现

 

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

所用文件

定义三个文件：

  1. 头文件 SList.h
  2. 函数的实现SList.c
  3. 代码的测试test.c

将有以下功能：

//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

链表定义

定义链表基本结构

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

创建新链表元素

创建新元素用于插入原链表

SLTNode* BuySListNode(SLTDataType x)
{//开辟空间SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}

尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{//开辟空间SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//防止开始时节点为空*pphead = newnode;}else{//找尾节点SLTNode* tail = *pphead;//找到链表首元素while (tail->next != NULL){//检索到未节点tail = tail->next;}//插入tail->next = newnode;}
}

头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址传给pphead  //*pphead=&plist/*头插无需检查是否为空*/
}

尾删

void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一个节点free(*pphead);*pphead = NULL;}else{//2，有多个节点//将前一个链元素中存放的地址换为NULL，防止野指针/* 写法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}

头删

void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);//找到首位链表元素SLTNode* next = (*pphead)->next;//存储首元素存放下一个元素的地址free(*pphead);//释放首元素*pphead = next;//将第二位元素改为首元素
}

查找-给一个节点的指针

//无需更改元素，故传一级指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}//未找到指定元素，返回NULLreturn NULL;
}

改

改元素是建立再查找基础之上进行更改

void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{printf("修改成功:\n");//先找到相应元素，再进行更改SLTNode* ret = SListFind(phead, y);ret->data = x;
}

pos位置之前插入

任意位置之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos == *pphead)SListPushFront(pphead, x);else{ //任意位置之前插入SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值prev->next = newnode;//给前一个元素赋上下一元素地址newnode->next = pos;//给插入元素存放下一个元素的地址}
}

删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//头删else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev->next = pos->next;//释放posfree(pos);pos = NULL;}
}

成品展示

SList.h

#pragma once#include <stdlib.h>
#include <stdio.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include "SList.h"//打印
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur!=NULL){printf("%d->", cur->data);cur = cur->next;//存放下一个元素的地址}printf("NULL\n");
}//创建新链表元素
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);//dataif (*pphead == NULL){//防止开始时节点为空*pphead = newnode;}else{//找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){//存放新节点地址tail = tail->next;}tail->next = newnode;}
}//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址传给pphead  //*pphead=&plist/*头插无需检查是否为空*/
}//尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一个节点free(*pphead);*pphead = NULL;}else{//2，有多个节点//将前一个链元素中存放的地址换为NULL，防止野指针/* 写法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}//头删
void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找-给一个节点的指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}return NULL;
}//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{assert(phead);printf("修改成功:\n");SLTNode* ret = SListFind(phead, y);ret->data = x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos == *pphead)SListPushFront(pphead, x);else{ SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值prev->next = newnode;//给前一个元素赋上下一元素地址newnode->next = pos;//给插入元素存放下一个元素的地址}
}//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//头删else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev->next = pos->next;//释放posfree(pos);pos = NULL;}
}

test.c

test.c仅仅是用于测试代码，本文以弄懂单向链表为主，故不进行菜单制作
但改测试中也包含了对部分链表结构即原理进行了讲解，请耐心看完

#include "SList.h"
void TestSList1()
{	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));assert(n1);SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));assert(n2);SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));assert(n3);SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));assert(n4);n1->data=1;n2->data=2;n3->data=3;n4->data=4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;SListPrint(n1);
}void TestSList2()
{SLTNode* plist = NULL;//传的是plist指针的地址//如果直接传plist，将导致SLTNode* phead中//phead为临时拷贝，不影响实参SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改变无需传二级指针SListPushFront(&plist,0);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopBack(&plist);/*SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*//*SListPopBack(&plist);SListPrint(plist);*/
}void TestSList3()
{SLTNode* plist = NULL;//传的是plist指针的地址//如果直接传plist，将导致SLTNode* phead中//phead为临时拷贝，不影响实参SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改变无需传二级指针//查找SLTNode* ret = SListFind(plist, 3);if (ret){//返回值不为空则为找到printf("找到了\n");}SListPrint(plist);修改//SListAlter(plist, 20, 2);//SListPrint(plist);//插入SLTNode* pos = SListFind(plist, 3);//先要找到再进行更改if (pos){SListInsert(&plist, pos, 40);}SListPrint(plist);//删除pos = SListFind(plist, 2);//先要找到再进行删除if (pos){SListErase(&plist, pos);}SListPrint(plist);
}int main()
{TestSList3();return 0;
}

单向链表讲解完毕啦！创作不易，如果喜欢请留下个赞吧，感激不尽😊

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/126346.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

（二十二）大数据实战——Flume数据采集之故障转移案例实战

（二十二）大数据实战——Flume数据采集之故障转移案例实战

前言 本节内容我们完成Flume数据采集的故障转移案例&#xff0c;使用三台服务器&#xff0c;一台服务器负责采集nc数据&#xff0c;通过使用failover模式的Sink处理器完成监控数据的故障转移&#xff0c;使用Avro的方式完成flume之间采集数据的传输。整体架构如下&#xff1a;…
阅读更多...
OpenCV 01(图像加载与显示)

OpenCV 01(图像加载与显示)

一、机器视觉 现在说的机器视觉(Machine Vision)一般指计算机视觉(Computer Vision), 简单来说就是研究如何使机器看懂东西。就是是指用摄影机和电脑代替人眼对目标进行识别、跟踪和测量等机器视觉&#xff0c;并进一步做图形处理&#xff0c;使电脑处理成为更适合人眼观察或传…
阅读更多...
VS编译.cu文件源文件无法打开matrix.h和mex.h问题

VS编译.cu文件源文件无法打开matrix.h和mex.h问题

配置好cu和VS相关库文件后CUDA程序仍然报错&#xff1a;无法打开matrix.h和mex.h&#xff0c;解决办法&#xff1a; &#xff08;1&#xff09;这两个头文件是matlab中的&#xff0c;可能无法直接在VS中调用&#xff0c;可以通过添加外部依赖项的方法将matlab中的头文件的文件路…
阅读更多...
1600*C. Maximum Set

1600*C. Maximum Set

解析&#xff1a; 尽可能的增大集合内的数&#xff0c;所以倍数要尽可能的小&#xff0c;所以让最小的数不断乘 2&#xff0c;即可找到最大的数量。 所以&#xff0c;每次计算 k log2&#xff08; y / x &#xff09;,这样可得出最小的 x&#xff0c;乘多少个 2&#xff0c;能…
阅读更多...
VS Code断点调式Cesium

VS Code断点调式Cesium

1.在VS Code中安装Debugger for Firefox插件 2.下载安Firefox Developer Edition 3. 创建launch.json 编辑并保存launch.json {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information, vis…
阅读更多...
MJDK 如何实现压缩速率的 5 倍提升？

MJDK 如何实现压缩速率的 5 倍提升？

MJDK 是基于 OpenJDK 构建的美团 JDK 发行版。本文主要介绍 MJDK 是如何在保障 java.util.zip.* API 及压缩格式兼容性的前提下&#xff0c;实现压缩/解压缩速率提升 5-10 倍的效果。希望相关的经验能够帮助到更多的技术同学。 1 前言 数据压缩技术[1]因可有效降低数据存储及…
阅读更多...
strerror函数

strerror函数

目录 strerror 函数介绍&#xff1a; 举例&#xff1a; 使用案例&#xff1a; 优化&#xff1a; perror&#xff1a; strerror 函数介绍&#xff1a; 函数声明&#xff1a; char * strerror ( int errnum );头 文 件&#xff1a;#include <string.h>返 回 值&a…
阅读更多...
01_前端css编写的三种方式

01_前端css编写的三种方式

前言 CSS的引入方式共有三种&#xff1a;行内样式、内部样式表、外部样式表 一、内联式引入 用法&#xff1a; 在元素上直接通过style属性进行设置css样式设置 示例&#xff1a; <h1 style"color:red;">style属性的应用</h1> <p style"font-si…
阅读更多...
hive指定字段插入数据,包含了分区表和非分区表

hive指定字段插入数据,包含了分区表和非分区表

1、建表 语句如下&#xff1a; CREATE EXTERNAL TABLE ods_lineitem_full (l_shipdate date,l_orderkey bigint,l_linenumber int,l_partkey int,l_suppkey int,l_quantity decimal(15, 2),l_extendedprice decimal(15, 2),l_discount de…
阅读更多...
数据结构-第一期——数组（Python）

数据结构-第一期——数组（Python）

目录 00、前言&#xff1a; 01、一维数组 一维数组的定义和初始化 一维变长数组 一维正向遍历 一维反向遍历 一维数组的区间操作 竞赛小技巧&#xff1a;不用从a[0]开始&#xff0c;从a[1]开始 蓝桥杯真题练习1 读入一维数组 例题一 例题二​ 例题三 实战训…
阅读更多...
每日刷题|回溯法解决全排列问题第二弹之解决字符串、字母大小排列问题

每日刷题|回溯法解决全排列问题第二弹之解决字符串、字母大小排列问题

食用指南&#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识&#xff1a;回溯法经典问题之全排列 ♈️今日夜电波&#xff1a;带我去找夜生活—告五人 0:49 ━━━━━━️&#x1f49f;──────── 4:59 …
阅读更多...
安科瑞铁塔基站能耗监控解决方案

安科瑞铁塔基站能耗监控解决方案

安科瑞 华楠 1 背景概述 5G发展&#xff0c;基站先行。5G基站的选址建设&#xff0c;是保证5G信号覆盖的基础&#xff0c;因此5G基站建设是5G产业布局的一部分&#xff0c;也是5G成熟的基础。 2G、3G、4G均是低频段信号传输&#xff0c;宏基站几乎能应付所有的信号覆盖。但由…
阅读更多...
SpringMVC入门详细介绍

SpringMVC入门详细介绍

一. SpringMVC简介 Spring MVC是一个基于Java的实现了MVC设计模式的请求驱动类型的轻量级Web框架&#xff0c;通过把Model&#xff0c;View&#xff0c;Controller分离&#xff0c;将web层进行职责解耦&#xff0c;把复杂的web应用分成逻辑清晰的几部分&#xff0c;简化开发&a…
阅读更多...
ctfshow 反序列化

ctfshow 反序列化

PHP反序列化前置知识 序列化和反序列化 对象是不能在字节流中传输的&#xff0c;序列化就是把对象转化为字符串以便存储和传输&#xff0c;反序列化就是将字符串转化为对象 魔术方法 __construct() //构造&#xff0c;当对象new时调用 __wakeup() //执行unserialize()时&am…
阅读更多...
南方科技大学博士研究生奖助学金，深圳大学

南方科技大学博士研究生奖助学金，深圳大学

目录 南方科技大学 中南大学 南京大学 厦门大学 苏州大学 中南财经政法大学 深圳大学 南方科技大学 https://ocean.sustech.edu.cn/ocean/public/upload/download/3/2.pdf 南方科技大学的在读研究生&#xff0c;每人每年都会得到40000元的补助&#xff0c;这40000块钱分…
阅读更多...
【C++】继承基础知识一遍过

【C++】继承基础知识一遍过

目录 一&#xff0c;概念 二&#xff0c;继承定义 1. 继承格式 2. 访问限定符与继承方式的关系 3. 继承父类成员访问方式的变化 小结&#xff1a; 三. 父类与子类对象赋值转化 四&#xff0c;继承作用域 1.特点 2. 测试题 五&#xff0c;派生类不一样的默认成员函…
阅读更多...
用深度强化学习来玩Chrome小恐龙快跑

用深度强化学习来玩Chrome小恐龙快跑

目录 实机演示 代码实现 实机演示 用深度强化学习来玩Chrome小恐龙快跑 代码实现 import os import cv2 from pygame import RLEACCEL from pygame.image import load from pygame.sprite import Sprite, Group, collide_mask from pygame import Rect, init, time, display,…
阅读更多...
centos7手动配置jdk1.8环境与maven环境

centos7手动配置jdk1.8环境与maven环境

安装jdk1.8 链接&#xff1a;https://pan.baidu.com/s/1_P7jHzH4Lk2jcPWWD7pi4w 提取码&#xff1a;6kkm winscp软件上传压缩包到Linux中 解压 # 解压到/usr/local/java目录下 tar -zxvf jdk-8u381-linux-x64.tar.gz -C /usr/local/java配置环境变量 vi /etc/profile # 最后…
阅读更多...
听觉刺激期间的神经血管耦合：ERPs和fNIRS血流动力学

听觉刺激期间的神经血管耦合：ERPs和fNIRS血流动力学

导读 强度依赖性振幅变化(IDAP)已在事件相关电位(ERPs)中进行了广泛的研究&#xff0c;并与多种精神疾病相关联。本研究旨在探讨功能近红外光谱(fNIRS)在IDAP范式中的应用&#xff0c;该范式与ERPs相关&#xff0c;可以指示神经血管耦合的存在。两个实验分别有33和31名参与者。…
阅读更多...
【C#】C#调用进程打开一个exe程序

【C#】C#调用进程打开一个exe程序

文章目录 一、过程二、效果总结 一、过程 新建WinForm程序&#xff0c;并写入代码&#xff0c;明确要调用的程序的绝对路径&#xff08;或相对路径&#xff09;下的exe文件。 调用代码&#xff1a; 这里我调用的另一个程序的路径是&#xff1a; F:\WindowsFormsApplication2…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023