数据结构：单链表的实现(C语言)

在这里插入图片描述

个人主页 ： 水月梦镜花
个人专栏 ： 《C语言》 《数据结构》

文章目录

  • 前言
  • 一、单链表实现思路和图解
    • 1.节点的定义(SListNode)
    • 2.申请一个节点(BuySListNode)
    • 3.单链表打印(SListPrint)
    • 4.单链表尾插(SListPushBack)
    • 5.单链表的头插(SListPushFront)
    • 6.单链表的尾删(SListPopBack)
    • 7.单链表头删(SListPopFront)
    • 8.单链表的查找(SListFind)
    • 9.单链表在pos位置之后插入x(SListInsertAfter)
    • 10.单链表删除在pos位置之后的值(SListEraseAfter)
    • 11.单链表的销毁(SListDestroy)
  • 二、代码实现
  • 总结

前言

本博客将要实现的无头单向不循环链表。

一、单链表实现思路和图解

1.节点的定义(SListNode)

我们将节点定义为如下结构：
在这里插入图片描述
其成员变量有data，next。

将int重命名为STLDataType，方便我们以后修改数据域的内容。

//无头单向不循环链表
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;

2.申请一个节点(BuySListNode)

动态申明一个空间，来放置数据。如下：
在这里插入图片描述
将data的内容置成形参x，next置NULL。

//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;retur

3.单链表打印(SListPrint)

循环遍历链表，直到尾节点。创建一个结构体指针变量cur，循环cur = cur->next，并打印cur->data的内容，直到cur == NULL。
在这里插入图片描述

//单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

4.单链表尾插(SListPushBack)

  • 如果链表不为NULL(链表中有元素)，要先遍历链表找到尾节点，在让尾节点指向新节点，完成尾插。
  • 如果链表为NULL(链表中没有元素)，此时应该直接让新节点等于头结点，完成尾插。(本链表是无哨兵位的)
  • 如果传入的头结点无效，直接判错。

在这里插入图片描述

在这里插入图片描述
当链表为NULL，我们就要修改头结点本身的内容，所以我们需要头结点的指针，而本文中头结点本身就是结构体指针，所以尾插函数参数我们需要二级指针。

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{assert(pplist);SListNode* newnode =  BuySListNode(x);if (*pplist != NULL){SListNode* cur = *pplist;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}else{*pplist = newnode;}
}

5.单链表的头插(SListPushFront)

对于头插而言，链表是否有元素并不重要，我们只需要让新节点的指向头结点，并将头结点等于新节点。

在这里插入图片描述
因为头插链表，一定会改变头结点的内容，所以我们头插函数的形参也是二级指针。

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}

6.单链表的尾删(SListPopBack)

  • 如果链表元素有两个及两以上，我们需要两个指针变量prev，next来找尾节点，循环prev = cur，cur = cur->next，使next指向尾节点，prev指向尾节点的前一个，free尾节点，prev指向的节点指向NULL。
  • 如果链表元素只有一个，直接free头结点，使头结点置NULL。
  • 如果链表没有元素，直接判错。

在这里插入图片描述

在这里插入图片描述
当链表元素只有一个时，此时尾删链表，要修改头结点的内容，尾删函数的形参需要二级指针。

//单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);//链表为NULLassert(*pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* cur = *pplist;SListNode* prev = NULL;while (cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;free(cur);}
}

7.单链表头删(SListPopFront)

我们需要一个结构体指针变量next，来保存头结点的下一个节点，然后free头结点，使头结点 = 指针变量next。

  • 如果链表没有元素，直接判错。

在这里插入图片描述

//单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;
}

8.单链表的查找(SListFind)

我们需要一个结构体指针变量cur，来遍历链表比较cur->data == x，如果相等，放回此时cur的内容(该节点的地址)。如果遍历完链表，并没有相等元素，放回NULL。

//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{SListNode* cur = plist;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

9.单链表在pos位置之后插入x(SListInsertAfter)

我们让newnode指向pos下一个的节点，pos指向newnode。

  • 如果我们先让pos指向newnode，newnode在指向pos的下一个节点，就会造成newnode指向自己，导致链表成环。
  • 该函数不会影响头结点的内容，所以函数的形参不用二级指针。

在这里插入图片描述


//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

10.单链表删除在pos位置之后的值(SListEraseAfter)

我们需要一个结构体指针变量next，记录pos下一个节点的地址，然后是pos指向next的下一个节点，接着free(next)。

  • 如果链表只有一个元素，我们不能调用该函数，否则会导致NULL指针的解引用。
  • 该函数不会改变头结点的内容，所以形参我们不用二级指针。

在这里插入图片描述


//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* next = pos->next;pos->next = next->next;free(next);
}

11.单链表的销毁(SListDestroy)

我们需要两个结构体指针prev，cur。先让prev = cur ，cur再指向下一个节点，free(prev)，重复上述操作，直到cur指向NULL。

在这里插入图片描述
需要我们在函数调用完后，自己对头结点置NULL。

//单链表的销毁
void SListDestroy(SListNode* plist)
{assert(plist);SListNode* cur = plist;while (cur != NULL){SListNode* prev = cur;cur = cur->next;free(prev);}
}

二、代码实现

//slist.h  文件#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//无头单向不循环链表
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;//申请一个节点
SListNode* BuySListNode(SLTDataType x);//单链表打印
void SListPrint(SListNode* plist);//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);//单链表的尾删
void SListPopBack(SListNode** pplist);//单链表头删
void SListPopFront(SListNode** pplist);//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x);//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos);//单链表的销毁
void SListDestroy(SListNode* plist);

//slist.c    文件#include "slist.h"//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{assert(pplist);SListNode* newnode =  BuySListNode(x);if (*pplist != NULL){SListNode* cur = *pplist;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}else{*pplist = newnode;}
}//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}//单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);//链表为NULLassert(*pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* cur = *pplist;SListNode* prev = NULL;while (cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;free(cur);}
}//单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;
}//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{SListNode* cur = plist;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* next = pos->next;pos->next = next->next;free(next);
}//单链表的销毁
void SListDestroy(SListNode* plist)
{assert(plist);SListNode* cur = plist;while (cur != NULL){SListNode* prev = cur;cur = cur->next;free(prev);}
}

总结

以上就是我对于无头单向不循环链表的实现！！！

在这里插入图片描述

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

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

相关文章

vue2-v-show和v-if有什么区别，使用场景分别是什么？

vue2-v-show和v-if有什么区别，使用场景分别是什么？

1、v-show和v-if的共同点 在vue中&#xff0c;v-if和v-show的作用效果是相同的&#xff08;不含v-else&#xff09;&#xff0c;都能控制元素在页面是否显示&#xff0c;在用法上也相同。 当表达式为true的时候&#xff0c;都会占据页面的位置 当表达式为false的时候&#xff…
阅读更多...
css3 hover border 流动效果

css3 hover border 流动效果

/* Hover 边线流动 */.hoverDrawLine {border: 0 !important;position: relative;border-radius: 5px;--border-color: #60daaa; } .hoverDrawLine::before, .hoverDrawLine::after {box-sizing: border-box;content: ;position: absolute;border: 2px solid transparent;borde…
阅读更多...
TCP的三次握手和四次挥手······详解

TCP的三次握手和四次挥手······详解

1、三次握手 三次握手是建立连接的过程 如图大致为三次握手的流程图&#xff1a; 当客户端对服务端发起连接时&#xff0c;会先发一个包连接请求数据&#xff0c;去询问能否建立连接&#xff0c;该数据包称为 “SYN”包 然后&#xff0c;如果对方同意连接&#xff0c;那么…
阅读更多...
九耶|阁瑞钛伦特 Java中，锁的实现方式

九耶|阁瑞钛伦特 Java中，锁的实现方式

在Java中&#xff0c;锁的实现方式有以下几种&#xff1a; 1. Synchronized关键字&#xff1a;使用synchronized关键字可以创建一个互斥锁&#xff0c;它可以保证同一时刻只有一个线程可以进入被synchronized关键字修饰的代码块或方法。 2. ReentrantLock类&#xff1a;Reentr…
阅读更多...
二叉树进阶版（C）

二叉树进阶版（C）

文章目录 1.树1.1概念1.2相关定义1.3 表示&#xff08;左孩子右兄弟&#xff09; 2.二叉树2.1概念2.2特殊的二叉树1. 满二叉树&#xff1a;2. 完全二叉树&#xff1a; 2.3二叉树的性质2.4练习 3.二叉树的存储结构1. 顺序存储2. 链式存储 4.完全二叉树的代码实现4.1堆的介绍1.堆…
阅读更多...
【雕爷学编程】Arduino动手做（184）---快餐盒盖，极低成本搭建机器人实验平台3

【雕爷学编程】Arduino动手做（184）---快餐盒盖，极低成本搭建机器人实验平台3

吃完快餐粥&#xff0c;除了粥的味道不错之外&#xff0c;我对个快餐盒的圆盖子产生了兴趣&#xff0c;能否做个极低成本的简易机器人呢&#xff1f;也许只需要二十元左右 知识点&#xff1a;轮子&#xff08;wheel&#xff09; 中国词语。是用不同材料制成的圆形滚动物体。简…
阅读更多...
Qt展示动态波形

Qt展示动态波形

Qt展示动态波形 需求描述成品展示实现难点Qt多线程 需求描述 接入串口&#xff0c;配置串口顺序进行接收数据&#xff1b;数据分成两个串口分别传入&#xff0c;使用多线程并发接入&#xff1b;时域数据有两个通道&#xff08;I&#xff0c;Q&#xff09;&#xff0c;分别以实…
阅读更多...
zookeeper入门学习

zookeeper入门学习

zookeeper入门学习 zookeeper应用场景 分布式协调组件 客户端第一次请求发给服务器2&#xff0c;将flag值修改为false&#xff0c;第二次请求被负载均衡到服务器1&#xff0c;访问到的flag也会是false 一旦有节点发生改变&#xff0c;就会通知所有监听方改变自己的值&#…
阅读更多...
【C++】类和对象-多态

【C++】类和对象-多态

1.多态的基本语法 代码 #include <iostream> using namespace std; /******************************************/ class Animal { public://speak函数就是虚函数//函数前面加上virtual关键字&#xff0c;变成虚函数&#xff0c;//那么编译器在编译的时候就不能确定函数…
阅读更多...
DevExpress WPF Tree List组件，让数据可视化程度更高！（二）

DevExpress WPF Tree List组件，让数据可视化程度更高！（二）

DevExpress WPF Tree List组件是一个功能齐全、数据感知的TreeView-ListView混合体&#xff0c;可以把数据信息显示为REE、GRID或两者的组合&#xff0c;在数据绑定或非绑定模式下&#xff0c;具有完整的数据编辑支持。 在上文中&#xff08;点击这里回顾DevExpress WPF Tree …
阅读更多...
中介者模式——协调多个对象之间的交互

中介者模式——协调多个对象之间的交互

1、简介 1.1、概述 如果在一个系统中对象之间的联系呈现为网状结构&#xff0c;如下图所示&#xff1a; 对象之间存在大量的多对多联系&#xff0c;将导致系统非常复杂&#xff0c;这些对象既会影响别的对象&#xff0c;也会被别的对象所影响&#xff0c;这些对象称为同事对…
阅读更多...
LeetCode--HOT100题（21）

LeetCode--HOT100题（21）

目录 题目描述&#xff1a;240. 搜索二维矩阵 II&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;240. 搜索二维矩阵 II&#xff08;中等&#xff09; 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&am…
阅读更多...
【雕爷学编程】MicroPython动手做（28）——物联网之Yeelight 2

【雕爷学编程】MicroPython动手做（28）——物联网之Yeelight 2

知识点&#xff1a;什么是掌控板&#xff1f; 掌控板是一块普及STEAM创客教育、人工智能教育、机器人编程教育的开源智能硬件。它集成ESP-32高性能双核芯片&#xff0c;支持WiFi和蓝牙双模通信&#xff0c;可作为物联网节点&#xff0c;实现物联网应用。同时掌控板上集成了OLED…
阅读更多...
【力扣】链表题目总结

【力扣】链表题目总结

文章目录 链表基础题型一、单链表翻转、反转、旋转1.反转链表2.反转链表II——反转部分链表3.旋转链表4.K个一组翻转链表5.反转偶数长度组的节点 二、删除单链表中的结点1.删除链表的结点2.删除未排序链表中的重复节点3.删除已排序链表中的重复元素I——重复元素只剩下一个4.删…
阅读更多...
分库分表概念、原理、拆分策略和实现技术讲解

分库分表概念、原理、拆分策略和实现技术讲解

文章目录 1.什么是分库分表2.分库分表拆分策略2.1 垂直拆分2.2 水平拆分 3.分库分表实现技术简介 1.什么是分库分表 分库分表的中心思想就是将数据分散存储&#xff0c;使得单一数据库/表的数据量变小来缓解单一数据库的性能问题&#xff0c;从而达到提升数据库性能的目的。 …
阅读更多...
Redis面试题2

Redis面试题2

Redis面试题-2 10、统计高并发网站每个网页每天的 UV 数据&#xff0c;结合Redis你会如何实现&#xff1f; 选用方案&#xff1a;HyperLogLog 如果统计 PV 那非常好办&#xff0c;给每个网页一个独立的 Redis 计数器就可以了&#xff0c;这个计数器的 key 后缀加上当天的日期…
阅读更多...
vue+element中如何设置单个el-date-picker开始时间和结束时间关联

vue+element中如何设置单个el-date-picker开始时间和结束时间关联

功能&#xff1a;选了开始时间&#xff0c;则结束时间只能选择开始时间之后的&#xff1b;选了结束时间&#xff0c;则开始时间只能选择结束时间之前的 重点是picker-options属性 图示&#xff1a; 代码展示: // body 内部<el-form-item><el-date-pickerv-model&qu…
阅读更多...
提高测试用例质量的6大注意事项

提高测试用例质量的6大注意事项

在软件测试中&#xff0c;经常会遇到测试用例设计不完整&#xff0c;用例没有完全覆盖需求等问题&#xff0c;这样往往容易造成测试工作效率低下&#xff0c;不能及时发现项目问题&#xff0c;无形中增加了项目风险。 因此提高测试用例质量&#xff0c;就显得尤为重要。一般来说…
阅读更多...
day50-springboot+ajax分页

day50-springboot+ajax分页

分页依赖&#xff1a; <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置&#xff1a; …
阅读更多...
Linux中提示No such file or directory解决方法

Linux中提示No such file or directory解决方法

说明&#xff1a; 在linux下&#xff0c;./xxx.sh执行shell脚本时会提示No such file or directory。但shell明明存在&#xff0c;为什么就是会提示这个呢&#xff1f; 这种其实是因为编码方式不对&#xff0c;如你在win下编辑sh&#xff0c;然后直接复制到linux下面 实现&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023