【数据结构】_不带头非循环单向链表

目录

1. 链表的概念及结构

2. 链表的分类

3. 单链表的实现

3.1 SList.h头文件

3.2 SList.c源文件

3.3 Test_SList.c测试文件

关于线性表，已介绍顺序表，详见下文：

【数据结构】_顺序表-CSDN博客

本文介绍链表；

基于顺序表的特点，思考改善方案：

按需申请释放空间，不再将数据存储于连续的一整块空间中，而是需要一个数据开辟一个小空间。为了方便访问数据，首先创建一个头指针（头结点）指向存放第一个数据的内存位置处，而在该位置处，除了存储该数据本身，再分配一块空间用于存放下一个数据的地址，直至某位置存放的下一个位置的指针为空则数据截止。

同时，这种存储方式也有效地提高了插入删除数据时的效率，无需再大量挪动数据。

这种数据结构就称为链表。

1. 链表的概念及结构

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

链表在逻辑上是连续的，在物理上不是连续的；

2. 链表的分类

单向和双向：

带头和不带头：

循环和非循环：

最常用的链表结构是：无头单向非循环链表 和 带头双向循环链表：

3. 单链表的实现

3.1 SList.h头文件

#pragma once
#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);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTCreatNode(SLTDataType x);
SLTNode* SLTFind(SLTNode* phead, 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* pos);
// 销毁
void SLTDestory(SLTNode** pphead);

3.2 SList.c源文件

#include"SList.h"
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d-> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* SLTCreatNode(SLTDataType x) {SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL) {perror("malloc fail\n");exit(1);}newNode->data = x;newNode->next = NULL;return newNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newNode = SLTCreatNode(x);// 空链表if (*pphead == NULL) {*pphead = newNode;}else {// 非空链表SLTNode* curNode = *pphead;while (curNode->next) {curNode = curNode->next;}curNode->next = newNode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newNode = SLTCreatNode(x);newNode->next = *pphead;// 令新结点为链表的头结点*pphead = newNode;
}
void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);// 链表只有一个结点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}// 链表有多个结点else {SLTNode* tailPrevNode = *pphead;SLTNode* tailNode = *pphead;while (tailNode->next) {tailPrevNode = tailNode;tailNode = tailNode->next;}free(tailNode);tailNode = NULL;tailPrevNode->next = NULL;}
}
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* secNode = (*pphead)->next;free(*pphead);*pphead = secNode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* curNode = phead;while (curNode) {if (curNode->data == x) {return curNode;}curNode = curNode->next;}return NULL;
}
// 在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead && *pphead && pos);SLTNode* newNode = SLTCreatNode(x);if (pos == *pphead) {// 调用头插方法SLTPushFront(pphead, x);}else {SLTNode* posPrevNode = *pphead;while (posPrevNode->next != pos) {posPrevNode = posPrevNode->next;}posPrevNode->next = newNode;newNode->next = pos;}
}
// 在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newNode = SLTCreatNode(x);SLTNode* posAfterNode = pos->next;pos->next = newNode;newNode->next = posAfterNode;
}
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead && *pphead && pos);if (*pphead == pos) {// 调用头删方法SLTPopFront(pphead);}else {SLTNode* posPrevNode = *pphead;while (posPrevNode->next != pos) {posPrevNode = posPrevNode->next;}posPrevNode->next = pos->next;free(pos);pos = NULL;}
}
// 删除pos后的结点
void SLTEraseAfter(SLTNode* pos) {assert(pos && pos->next);SLTNode* posAfterNode = pos->next;pos->next = posAfterNode->next;free(posAfterNode);posAfterNode = NULL;
}
// 销毁
void SLTDestory(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* curNode = *pphead;while (curNode) {SLTNode* curNextNode= curNode->next;free(curNode);curNode = NULL;}*pphead = NULL;
}

3.3 Test_SList.c测试文件

#include"SList.h"
void Test11() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTDestory(&plist);SLTPrint(plist);
}
void Test10() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* aimNode1 = SLTFind(plist, 3);SLTEraseAfter(aimNode1);SLTPrint(plist);SLTNode* aimNode2 = SLTFind(plist, 1);SLTEraseAfter(aimNode2);SLTPrint(plist);
}
void Test9() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* aimNode1 = SLTFind(plist, 3);SLTErase(&plist, aimNode1);SLTPrint(plist);SLTNode* aimNode2 = SLTFind(plist, 1);SLTErase(&plist, aimNode2);SLTPrint(plist);
}
void Test8() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* aimNode1 = SLTFind(plist, 3);SLTInsertAfter(aimNode1, 85);SLTPrint(plist);SLTNode* aimNode2 = SLTFind(plist, 1);SLTInsertAfter(aimNode2, 97);SLTPrint(plist);
}
void Test7(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* aimNode1 = SLTFind(plist, 3);SLTInsert(&plist, aimNode1, 85);SLTPrint(plist);SLTNode* aimNode2 = SLTFind(plist, 1);SLTInsert(&plist, aimNode2, 97);SLTPrint(plist);
}
void Test6() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);// SLTNode* aimNode = SLTFind(plist, 3);SLTNode* aimNode = SLTFind(plist, 6);if (aimNode == NULL)printf("Find nothing\n");elseprintf("Find successfully\n");
}
void Test5() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);
}
void Test4() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}
void Test3() {SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);
}
void Test2() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}void Test1() {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);
}
int main() {//Test1();//Test2();//Test3();//Test4();//Test5();//Test6();//Test7();//Test8();//Test9();//Test10();Test11();return 0;
}

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

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

相关文章

算法刷题笔记——图论篇

算法刷题笔记——图论篇

这里写目录标题 理论基础图的基本概念图的种类度 连通性连通图强连通图连通分量强连通分量 图的构造邻接矩阵邻接表 图的遍历方式 深度优先搜索理论基础dfs 与 bfs 区别dfs 搜索过程深搜三部曲所有可达路径广度优先搜索理论基础广搜的使用场景广搜的过程 岛屿数量孤岛的总面积沉…
阅读更多...
“AI视觉贴装系统：智能贴装，精准无忧

“AI视觉贴装系统：智能贴装，精准无忧

嘿&#xff0c;朋友们&#xff01;今天我要跟你们聊聊一个特别厉害的技术——AI视觉贴装系统。这可不是普通的贴装设备&#xff0c;它可是融合了人工智能、计算机视觉和自动化控制等前沿科技的“智能贴装大师”。有了它&#xff0c;那些繁琐、复杂的贴装工作变得轻松又精准。来…
阅读更多...
vim如何设置显示空白符

vim如何设置显示空白符

:set list 显示空白符 示例&#xff1a; :set nolist 不显示空白符 示例&#xff1a; &#xff08;vim如何使设置显示空白符永久生效&#xff1a;vim如何使相关设置永久生效-CSDN博客&#xff09;
阅读更多...
Flutter android debug 编译报错问题。插件编译报错

Flutter android debug 编译报错问题。插件编译报错

下面相关内容 都以 Mac 电脑为例子。 一、问题 起因&#xff1a;&#xff08;更新 Android studio 2024.2.2.13、 Flutter SDK 3.27.2&#xff09; 最近 2025年 1 月 左右&#xff0c;我更新了 Android studio 和 Flutter SDK 再运行就会出现下面的问题。当然 下面的提示只是其…
阅读更多...
AI导航工具我开源了利用node爬取了几百条数据

AI导航工具我开源了利用node爬取了几百条数据

序言 别因今天的懒惰&#xff0c;让明天的您后悔。输出文章的本意并不是为了得到赞美&#xff0c;而是为了让自己能够学会总结思考&#xff1b;当然&#xff0c;如果有幸能够给到你一点点灵感或者思考&#xff0c;那么我这篇文章的意义将无限放大。 背景 随着AI的发展市面上…
阅读更多...
Android Studio打包APK

Android Studio打包APK

1.导出APK安装包 如果是首次打包&#xff0c;Create new 单击蓝色对话框右边文件夹&#x1f4c2;图标 &#xff0c;选择密钥保存路径&#xff0c;然后在下方File name对话框中填写您想要名称&#xff0c;再点击OK回到密钥创建对话框。 在此对话框中填写密码&#xff08;Passwo…
阅读更多...
ssh密钥登录GitHub时一直提示“Error: Permission denied (publickey)”

ssh密钥登录GitHub时一直提示“Error: Permission denied (publickey)”

起因 环境&#xff1a;Windows10 背景&#xff1a;之前就是按照官方说明创建个rsa密钥&#xff0c;在git后台添加上&#xff0c;就行了&#xff0c;近期怎么添加怎么失败&#xff0c;总是“Error: Permission denied (publickey)”的提示&#xff01; 尝试 各种尝试&#xf…
阅读更多...
【玩转全栈】----Django连接MySQL

【玩转全栈】----Django连接MySQL

阅前先赞&#xff0c;养好习惯&#xff01; 目录 1、ORM框架介绍 选择建议 2、安装mysqlclient 3、创建数据库 4、修改settings&#xff0c;连接数据库 5、对数据库进行操作 创建表 删除表 添加数据 删除数据 修改&#xff08;更新&#xff09;数据&#xff1a; 获取数据 1、OR…
阅读更多...
软件质量与测试报告5-压力测试 JMeter 与 Badboy

软件质量与测试报告5-压力测试 JMeter 与 Badboy

A&#xff0e;百度搜索引擎压力测试 通过在Badboy下执行如下的测试场景来生成压力测试的脚本&#xff1a; a) 在Badboy的地址栏里面输入www.baidu.com&#xff0c;回车&#xff1b; b) 在右下区域打开的百度的主页上输入搜索关键字JMeter&#xff0c;回车&#xff1b; c) 在…
阅读更多...
vim如何显示行号

vim如何显示行号

:set nu 显示行号 :set nonu 不显示行号 &#xff08;vim如何使设置显示行号永久生效&#xff1a;vim如何使相关设置永久生效-CSDN博客&#xff09;
阅读更多...
Python Typing: 实战应用指南

Python Typing: 实战应用指南

文章目录 1. 什么是 Python Typing&#xff1f;2. 实战案例&#xff1a;构建一个用户管理系统2.1 项目描述2.2 代码实现 3. 类型检查工具&#xff1a;MyPy4. 常见的 typing 用法5. 总结 在 Python 中&#xff0c;静态类型检查越来越受到开发者的重视。typing 模块提供了一种方式…
阅读更多...
Linux的基本指令（上）

Linux的基本指令（上）

1.ls指令 语法&#xff1a;ls [选项] [目录或文件] 功能&#xff1a;对于⽬录&#xff0c;该命令列出该⽬录下的所有⼦⽬录与⽂件。对于⽂件&#xff0c;将列出⽂件名以及其他信息。 常用选项&#xff1a; -a 列出⽬录下的所有⽂件&#xff0c;包括以 . 开头的隐含⽂件。 -d 将…
阅读更多...
【数据分享】1929-2024年全球站点的逐日平均能见度（Shp\Excel\免费获取）

【数据分享】1929-2024年全球站点的逐日平均能见度（Shp\Excel\免费获取）

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff01;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2024年全球气象站点…
阅读更多...
算法每日双题精讲 —— 二分查找（山脉数组的峰顶索引，寻找峰值）

算法每日双题精讲 —— 二分查找（山脉数组的峰顶索引，寻找峰值）

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 别再犹豫了&#xff01;快来订阅我们的算法每日双题精讲专栏&#xff0c;一起踏上算法学习的精彩之旅吧&#x1f4aa; 在算法的…
阅读更多...
macOS如何进入 Application Support 目录（cd: string not in pwd: Application）

macOS如何进入 Application Support 目录（cd: string not in pwd: Application）

错误信息 cd: string not in pwd: Application 表示在当前目录下找不到名为 Application Support 的目录。可能的原因如下&#xff1a; 拼写错误或路径错误&#xff1a;确保你输入的目录名称正确。目录名称是区分大小写的&#xff0c;因此请确保使用正确的大小写。正确的目录名…
阅读更多...
如何为64位LabVIEW配置正确的驱动程序

如何为64位LabVIEW配置正确的驱动程序

在安装 64位 LabVIEW 后&#xff0c;确保驱动程序正确配置是关键。如果您首先安装了 32位 LabVIEW 和相关驱动&#xff0c;然后安装了 64位 LabVIEW&#xff0c;需要确保为 64位 LabVIEW 安装和配置适当的驱动程序&#xff0c;才能正常访问硬件设备。以下是详细步骤&#xff1a…
阅读更多...
《Memory Barriers a Hardware View for Software Hackers》阅读笔记

《Memory Barriers a Hardware View for Software Hackers》阅读笔记

CPU 设计者引入内存屏障&#xff08;memory barriers&#xff09;是为了应对在多处理器系统&#xff08;SMP&#xff09;中&#xff0c;内存引用重排序可能导致的同步问题。尽管重排序可以提高性能&#xff0c;但在某些情况下&#xff08;如同步原语&#xff09;&#xff0c;正…
阅读更多...
ES设置证书和创建用户，kibana连接es

ES设置证书和创建用户，kibana连接es

1、启动好es 2、进入es容器 docker exec -it es /bin/bash 3、生成ca证书 ./bin/elasticsearch-certutil ca 注&#xff1a;两个红方框位置直接回车 4、生成cert证书 ./bin/elasticsearch-certutil cert --ca elastic-stack-ca.p12 注&#xff1a;前两个红框直接回车&am…
阅读更多...
【安当产品应用案例100集】034-安当KSP支持密评中存储数据的机密性和完整性

【安当产品应用案例100集】034-安当KSP支持密评中存储数据的机密性和完整性

安当KSP是一套获得国密证书的专业的密钥管理系统。KSP的系统功能扩展图示如下&#xff1a; 我们知道商用密码应用安全性评估中&#xff0c;需要确保存储的数据不被篡改、删除或者破坏&#xff0c;必须采用合适的安全方案来确保存储数据的机密性和完整性。KSP能否满足这个需求呢…
阅读更多...
STM32项目分享：智能厨房安全检测系统

STM32项目分享：智能厨房安全检测系统

目录 一、前言 二、项目简介 1.功能详解 2.主要器件 三、原理图设计 四、PCB硬件设计 PCB图 五、程序设计 六、实验效果 七、资料内容 项目分享 一、前言 项目成品图片&#xff1a; 哔哩哔哩视频链接&#xff1a; STM32智能厨房安全检测系统 &#xff08;资料分…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023