单链表的实现(数据结构)

一. 单链表的实现

我们在上一篇中简单的认识了链表的组成和结构,并打印出链表,那么今天就来具体实现一下单链表对于数据增加、删减、插入等。

接下来就是我们在链表中对于数据的增、删、插的实现,对于我们的链表来说在任何地方增加数据都需要来申请一个新的结点,首先呢,SLDatatype是我们更改int类型的名称之后得来的,SL是结构体的名称,我们先申请一个结构体大小的新结点node,然后再将新结点中的x的值赋给data,再让新结点的next指向NULL,申请新结点的函数写好之后我们就来写关于数据的增、删、插等,所以我们直接先来完成申请新结点的代码:

SLDatatype* SLBuyNode(SLDatatype x)
{SL* node = (SL*)malloc(sizeof(SL));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}

 尾插

//尾插函数
void SLPuchBack(SL** pphead, SLDatatype x)
{//申请新结点//*pphead-->&plistSL* newnode = SLBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//尾结点-->新结点SL* pcur = *pphead;//找尾结点while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}}
void SLTest01()
{SL* plist = NULL;SLPuchBack(&plist, 1);SLprintf(plist);SLPuchBack(&plist, 2);SLPuchBack(&plist, 3);SLprintf(plist);
}int main()
{SLTest01();return 0;
}

在实现让任何代码之前,我们都因该将思路理清楚,尾插该注意什么,怎么去是实现?首先一定是要找到最后一个结点,pphead是我们的头结点,我们一贯会将pphead赋给一个新的指针pcur,使用while循环找到最后一个结点,但是如果while里面是pcur的那我们不就直接跳出循环,那我们还怎么找最后一个结点呢?所以我们不如使用while(pcur->next),也就是当我们pcur指向3的时候我们的next刚好指向的是NULL,停止了循环,刚好pcur还指向尾结点,然后我们在将newnode赋值给我们的最后一个结点。在上面的代码中我们要注意的一点是SLPuchBack函数中传入的是形参,这个时候我们要使用传值调用,因为如果使用传值调用的话,形参的改变并不影响实参,所以在测试函数SLTest01中传入的是&plist,然而plist本身就是一个指针,所以我们在SLPuchBack中要使用二级指针即**pphead。

 头插:对于头插就简单很多,我们只需要申请一个新的结点,然后将结点与原本的头结点连接,在让pphead指向现在新的结点。

//头插函数
void SLPuchFront(SL** pphead, SLDatatype x)
{assert(pphead);SL* newnode = SLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾删:对于尾删我们并不能简单的将最后一个结点删除,因为这样会让前面一个指针变成野指针,可以把最后一个结点前面的结点的next指向NULL,然后将最后一个结点释放掉。

//尾删函数
void SLPopBack(SL** pphead)
{assert(pphead && *pphead);//假如原本只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SL* pcur = *pphead;SL* front = NULL;while (pcur->next){front = pcur;pcur = pcur->next;}front->next = NULL;free(pcur);pcur = NULL;}

头删: 

//头删函数
void SLPopFront(SL** pphead)
{assert(pphead && *pphead);SL* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;
}

 在指定位置之前插入数据

void SLInsertFront(SL** pphead, SL* pos, SLDatatype x)
{assert(pphead && pos);SL* newnode = SLBuyNode(x);SL* pcur = *pphead;if (pos == *pphead){newnode->next = pos;*pphead = newnode;}else{while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}}

 在指定位置之后插入数据

void SLInsertAfert(SL* pos, SLDatatype x)
{assert(pos);SL* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode; 
}

 删除pos结点

void SLErase(SL** pphead, SL* pos)
{assert(pphead && *pphead);assert(pos);SL* pcur = *pphead;if (pos == *pphead){SLPopFront(pphead);}else{while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}

 删除pos之后的结点

void SLEraseAfert(SL* pos)
{assert(pos&&pos->next);SL* deal = pos->next;pos->next = pos->next->next;free(deal);deal = NULL;
}

 销毁链表

void SLDestroy(SL** pphead)
{SL* pcur = *pphead;while (pcur){SL* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

上面关于链表的指定位置插入、删除等算法,我们要注意的就是在我们更改链表中的数据的时候,要更改的这个数据会影响其他的数据吗?如果影响我们应该怎么做,提前设置好几个指针变量还是其他的办法,寻找某一个结点的时候while循环的条件是什么,这些我们都要注意,上面已经给出较为详细的代码,大家可以参考,另外就是注意free指针之后一定要将其置为空指针NULL,单链表完成之后我们就要拿一些算法题来练手,如何使用单链表来完成一些算法题。

二. 算法题

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

这个题目是移除链表元素,我们有两个思路一个就是利用我们原本的单链表对指定位置的结点进行删除,还有就是创建一个新的链表然后将符合的元素移到新的链表中,我们可以来实现第二中思路: 创建一个新链表,遍历原链表,将不等于给定值  val  的节点依次添加到新链表中。
 
1. 创建新链表的哑节点(dummy node):
- 目的是简化操作,避免处理新链表头节点为空的特殊情况。
- 例如,可以创建一个值为  0  的哑节点,将其  next  指针初始化为  null 。
2. 遍历原链表:
- 从原链表的头节点  head  开始遍历。
- 检查当前节点的值是否等于  val 。
- 如果不等于  val ,则将该节点添加到新链表中。
3. 添加节点到新链表:
- 将原链表中不等于  val  的节点的  next  指针指向新链表的末尾节点的  next 。
- 更新新链表的末尾节点为该节点。
4. 返回新链表的头节点:
 - 新链表的头节点为哑节点的  next 。
 通过以上步骤,就可以使用创建新链表的方法删除原链表中所有值为  val  的节点,并返回新的头节点。

 

#include <stdio.h>
#include <stdlib.h>struct ListNode {int val;struct ListNode* next;
};struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* dummy = createNode(0);struct ListNode* curr = dummy;while (head) {if (head->val!= val) {curr->next = head;curr = curr->next;}head = head->next;}curr->next = NULL;return dummy->next;
}void printList(struct ListNode* head) {while (head) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}void freeList(struct ListNode* head) {struct ListNode* temp;while (head) {temp = head;head = head->next;free(temp);}
}
int main() {// 创建链表 1->2->6->3->4->5->6struct ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(6);head->next->next->next = createNode(3);head->next->next->next->next = createNode(4);head->next->next->next->next->next = createNode(5);head->next->next->next->next->next->next = createNode(6);int val = 6;struct ListNode* newHead = removeElements(head, val);printList(newHead);freeList(newHead);return 0;
}

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

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

相关文章

Golang | Leetcode Golang题解之第540题有序数组中的单一元素

题目&#xff1a; 题解&#xff1a; func singleNonDuplicate(nums []int) int {low, high : 0, len(nums)-1for low < high {mid : low (high-low)/2mid - mid & 1if nums[mid] nums[mid1] {low mid 2} else {high mid}}return nums[low] }

算法: 链表题目练习

文章目录 链表题目练习两数相加两两交换链表中的节点重排链表合并 K 个升序链表K 个一组翻转链表 总结 链表题目练习 两数相加 坑: 两个链表都遍历完后,可能需要进位. class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 l1;ListNode…

深入Pillow:处理图像下载中的意外挑战

在当今数字化时代&#xff0c;获取和处理图像数据已经成为了许多应用程序的核心功能。从社交媒体到电子商务&#xff0c;图像的获取和处理对于用户体验至关重要。下载图片不仅能够丰富我们的内容&#xff0c;还能够通过分析图像数据为我们的应用提供更多价值。然而&#xff0c;…

零基础Java第十三期:继承与多态(一)

目录 一、继承 1.1. 继承的目的 1.2. 继承的概念 1.3. 继承的语法 1.4. 父类的访问 1.5. 继承中的重载与重写 1.6. 子类的构造方法 1.7. 再谈初始化 一、继承 1.1. 继承的目的 我们来定义一个Dog和Cat的类&#xff1a; public class Dog {public int age;public Strin…

【ONLYOFFICE文档】8.2版本测评

文章目录 引言ONLYOFFICE 产品简介PDF编辑器新功能1.协作编辑 PDF&#xff0c;让团队合作更高效2.为 PDF 表单添加签名3.改进的简洁界面4.性能优化&#xff1a;更快、更高效的体验 文档编辑器中的新功能域代码功能&#xff1a;自动更新文档中的动态数据协作功能&#xff1a;轻松…

【JAVA】java 企业微信信息推送

前言 JAVA中 将信息 推送到企业微信 // 企微消息推送messageprivate String getMessage(String name, String problemType, String pushResults, Long orderId,java.util.Date submitTime, java.util.Date payTime) {String message "对接方&#xff1a;<font color\…

【RK3588 Linux 5.x 内核编程】-GPIO设备驱动与点亮LED

GPIO设备驱动与点亮LED 文章目录 GPIO设备驱动与点亮LED1、Linux中的GPIO介绍2、GPIO库和工具3、Linux内核GPIO操作步骤3.1 验证GPIO3.2 请求GPIO3.3 导出GPIO到sysfs(可选)3.4 设置GPIO为输入/输出3.5 更改GPIO的电平(值)3.6 读取GPIO的值(电平)3.7 释放GPIO4、GPIO驱动…

金华迪加 现场大屏互动系统 mobile.do.php 任意文件上传漏洞复现

0x01 产品简介 金华迪加现场大屏互动系统是一种集成了先进技术和创意设计的互动展示解决方案,旨在通过大屏幕和多种交互方式,为观众提供沉浸式的互动体验。该系统广泛应用于各类活动、展览、会议等场合,能够显著提升现场氛围和参与者的体验感。 0x02 漏洞概述 金华迪加 现…

[VUE]框架网页开发1 本地开发环境安装

前言 其实你不要看我的文章比较长&#xff0c;但是他就是很长&#xff01;步骤其实很简单&#xff0c;主要是为新手加了很多解释&#xff01; 步骤一&#xff1a;下载并安装 Node.js 访问 Node.js 官网&#xff1a; Node.js — Download Node.js 下载 Windows 64 位版本&…

[signal] void QComboBox::currentTextChanged(const QString text)

[signal] void QComboBox::currentTextChanged(const QString &text) This signal is sent whenever currentText changes. The new value is passed as text. This function was introduced in Qt 5.0. Note: Notifier signal for property currentText. 属性currentText的…

Unity中实现伤害飘字或者提示飘字效果(DoTween实现版本)

&#xff01;&#xff01;&#xff01;在实现以下效果之前&#xff0c;一定要往项目中导入DoTween插件。 一、搭建测试场景 1、在场景中新建一个带有Text组件的游戏物体A&#xff0c;并把这个游戏物体A中Text组件的Color属性中alpha值为0&#xff0c;让文字在场景中隐藏。 …

掌握PyQt5图形界面化工具及绑定爬虫程序

PyQT5——图形化界面 文章目录 PyQT5——图形化界面集成化图形界面工具为什么使用 \$ProjectFileDir$?示例场景其他 Varaiablespyuic参数解释整体含义示例使用PyQt5和pyuic 创建pyqt5的程序创建一个窗口app.exec\_()和sys.exit(app.exec_())的区别1. app.exec_()2. sys.exit(a…

从零开始在本地服务器上安装OnlyOffice并进行跨地域协同编辑文件

文章目录 前言1. 安装Docker2. 本地安装部署ONLYOFFICE3. 安装cpolar内网穿透4. 固定OnlyOffice公网地址 前言 本篇文章讲解如何使用Docker在本地Linux服务器上安装ONLYOFFICE&#xff0c;并结合cpolar内网穿透实现公网访问本地部署的文档编辑器与远程协作。 Community Editi…

20241102在荣品PRO-RK3566开发板的预置Android13下适配宸芯的数传模块CX6603N

20241102在荣品PRO-RK3566开发板的预置Android13下适配宸芯的数传模块CX6603N 2024/11/2 18:04 在WIN10使用程序&#xff1a;ViewLink-4.0.7_0708-windows-x64.exe 在荣品PRO-RK3566开发板的预置Android13下使用&#xff1a;ViewLink-2023_12_21-release-0.2.6.apk adb install…

智能AI合同审查系统如何优化合同风险管理的案例解读

在合同管理和合规性要求日趋严格的法律行业&#xff0c;智能合同审查系统能够大幅提升合同数据管理的效率和准确性。法律行业中&#xff0c;合同涉及金额、产品参数和条款细节较多&#xff0c;同时对合规性有极高的要求。特别是在高度受监管的行业&#xff08;如金融、医疗、制…

C++《list的模拟实现》

在上一篇C《list》专题当中我们了解了STL当中list类当中的各个成员函数该如何使用&#xff0c;接下来在本篇当中我们将试着模拟实现list&#xff0c;在本篇当中我们将通过模拟实现list过程中深入理解list迭代器和之前学习的vector和string迭代器的不同&#xff0c;接下来就开始…

Vue学习之路17----事件

可以自定义事件让子组件向父组件传值 1.使用emit 2.使用props 3.使用mitt 其实mitt和第一种方法类似&#xff0c;都用emitt事件&#xff0c;但是mitt不局限于父子之间通信&#xff0c;他可以在任意2个组件之间通信&#xff0c; 虽然需要安装&#xff0c;但mitt很小&#xff…

网络安全认证的证书有哪些?

在网络安全领域&#xff0c;专业认证不仅是个人技术能力的象征&#xff0c;也是职业发展的重要推动力。随着网络安全威胁的日益严峻&#xff0c;对网络安全专业人才的需求也在不断增长。本文将介绍一些网络安全认证的证书&#xff0c;帮助有志于从事网络安全行业的人士了解并选…

D59【python 接口自动化学习】- python基础之异常

day59 捕获异常常见问题 学习日期&#xff1a;20241105 学习目标&#xff1a;异常 -- 75 避坑指南&#xff1a;编写捕获异常程序时经常出现的问题 学习笔记&#xff1a; 捕获位置设置不当 设置范围不当 捕获处理设置不当 嵌套try-except语法错误 总结 位置&#xff0c;范围…

yelp数据集上试验SVD,SVDPP,PMF,NMF 推荐算法

SVD、SVD、PMF 和 NMF 是几种常见的推荐算法&#xff0c;它们主要用于协同过滤和矩阵分解方法来生成个性化推荐。下面是对每种算法的简要介绍&#xff1a; 1. SVD&#xff08;Singular Value Decomposition&#xff09; 用途&#xff1a;SVD 是一种矩阵分解技术&#xff0c;通…