数据结构学习——无头+单向+非循环链表增删查改实现

链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的
在这里插入图片描述
注意：

  1. 链式结构在逻辑上是连续的，但是在物理上不一定连续
  2. 在链表实现过程中，结点一般都是从堆一个一个申请出来的
  3. 从堆上申请的空间，是按照系统来分配的，两次申请的空间可能连续的，也可能不是连续的

链表的分类

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

  1. 单向或者双向
    在这里插入图片描述
    在这里插入图片描述

  2. 带头或者不带头
    在这里插入图片描述
    在这里插入图片描述

  3. 循环或者不循环
    在这里插入图片描述
    在实际使用中，我们最常用这两种结构：
    无头单向非循环链表：
    在这里插入图片描述
    带头双向循环链表：
    在这里插入图片描述
    今天我们学习单链表的实现

单链表实现思路：

尾插：

void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}SLNode* newnode = CreateNode(x);tail->next = newnode;}
}

请添加图片描述
头插：

void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}

请添加图片描述
尾删：

void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//方法1：/*SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*///方法2：SLNode* tail = *pphead;SLNode* prev = NULL;while (tail != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

请添加图片描述
头删：

void SLTPopFront(SLNode** pphead)
{assert(*pphead);//方法1：/*SLNode* tmp = *pphead;*pphead = tmp->next;free(tmp);tmp = NULL;*///方法2：/*SLNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);*///错误：//SLNode* tmp = *pphead;//free(tmp);//*pphead = (*pphead)->next;//这里先free(tmp)会导致*pphead后面存放的数据无法拿取，造成内存泄露//方法3：SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;
}

请添加图片描述
在pos的前面插入：

SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* newnode = CreateNode(x);newnode->next = pos;prev->next = newnode;}
}

请添加图片描述
删除pos位置：

void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);//不允许链表为空assert(pos);//pos必需为有效节点if (*pphead == pos){SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}	
}

请添加图片描述

单链表实现代码：

SList.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLNDataType;typedef struct SListNode
{int val;struct SListNode* next;
}SLNode;//打印
void SLTPrint(SLNode* phead);//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);//尾删
void SLTPopBack(SLNode** pphead);
//头删
void SLTPopFront(SLNode** pphead);SLNode* SLTFind(SLNode* phead, SLNDataType x);// 在pos的前面插入
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);// 删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos);// 后面插入 后面删除
void SLTInsertAfter(SLNode* pos, SLNDataType x);
void SLTEraseAfter(SLNode* pos);// 前面插入
void SLTInsertHead(SLNode* pos, SLNDataType x);//销毁
void SLTDestroy(SLNode** pphead);

SList.c：

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void SLTPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d ->", cur->val);cur = cur->next;}printf("NULL");
}SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next  = NULL;return newnode;
}void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}SLNode* newnode = CreateNode(x);tail->next = newnode;}
}void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//方法1：/*SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*///方法2：SLNode* tail = *pphead;SLNode* prev = NULL;while (tail != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}void SLTPopFront(SLNode** pphead)
{assert(*pphead);//方法1：/*SLNode* tmp = *pphead;*pphead = tmp->next;free(tmp);tmp = NULL;*///方法2：/*SLNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);*///错误：//SLNode* tmp = *pphead;//free(tmp);//*pphead = (*pphead)->next;//这里先free(tmp)会导致*pphead后面存放的数据无法拿取，造成内存泄露//方法3：SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;
}SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev){if (prev->next != pos){prev = prev->next;}else{SLNode* newnode = CreateNode(x);newnode->next = pos;prev->next = newnode;}}while (prev->next != pos){prev = prev->next;}SLNode* newnode = CreateNode(x);newnode->next = pos;prev->next = newnode;}
}void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);//不允许链表为空assert(pos);//pos必需为有效节点if (*pphead == pos){SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}	
}void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->next = pos->next;pos->next = newnode;newnode->val = x;
}void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}void SLTInsertHead(SLNode* pos, SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->val = pos->val;newnode->next = pos->next;pos->val = x;pos->next = newnode;
}void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* tmp = cur->next ;free(cur);cur = tmp;}	*pphead = NULL;	
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void TestSLT1()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPrint(plist);printf("\n");SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");}void TestSLT2()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);printf("\n");SLTPopBack(&plist);SLTPopBack(&plist);SLTPopBack(&plist);SLTPrint(plist);
}void TestSLT3()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);printf("\n");SLTPopFront(&plist);SLTPopFront(&plist);SLTPrint(plist);printf("\n");SLNode* pos = SLTFind(plist, 4);SLTInsert(&plist, pos, 30);SLTInsert(&plist, pos, 40);SLTPrint(plist);printf("\n");}void TestSLT4()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);printf("\n");SLNode* pos = SLTFind(plist, 2);SLTErase(&plist, pos);SLTPrint(plist);printf("\n");pos = SLTFind(plist, 3);SLTInsertAfter(pos, 5);SLTPrint(plist);printf("\n");pos = SLTFind(plist, 1);SLTEraseAfter(pos);SLTPrint(plist);printf("\n");SLTDestroy(&plist);
}void TestSLT5()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);printf("\n");SLNode* pos = SLTFind(plist, 2);SLTInsertHead(pos, 20);SLTPrint(plist);printf("\n");SLTDestroy(&plist);
}int main()
{TestSLT5();return 0;
}

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

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

相关文章

轻松赚钱，精彩生活：上班族副业赚钱新攻略大揭秘！

轻松赚钱，精彩生活：上班族副业赚钱新攻略大揭秘！

薪水总是捉襟见肘&#xff0c;每月账单总让人倍感压力。你是否曾在静谧的夜晚&#xff0c;躺在床上&#xff0c;思索如何为家庭多赚一分钱&#xff1f;其实&#xff0c;你并不孤单。在这个充满机遇与挑战的时代&#xff0c;越来越多的人开始寻找副业&#xff0c;以期望让生活更…
阅读更多...
使用easyYapi生成文档

使用easyYapi生成文档

easyYapi生成文档 背景1.安装配置1.1 介绍1.2 安装1.3 配置1.3.1 Export Postman1.3.2 Export Yapi1.3.3 Export Markdown1.3.4 Export Api1.3.6 常见问题补充 2. java注释规范2.1 接口注释规范2.2 出入参注释规范 3. 特定化支持3.1 必填校验3.2 忽略导出3.3 返回不一致3.4 设置…
阅读更多...
PL/SQL的词法单元

PL/SQL的词法单元

目录 字符集 标识符 分隔符 注释 oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 PL/SQL块中的每一条语句都必须以分号结束。 一个SQL语句可以跨多行&#xff0c;但分号表示该语句的结束:一行中也可以有多条 SQL语句&…
阅读更多...
spring boot3自定义注解+拦截器+Redis实现高并发接口限流

spring boot3自定义注解+拦截器+Redis实现高并发接口限流

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途 目录 写在前面 内容简介 实现思路 实现步骤 1.自定义限流注解 2.编写限流拦截器 3.注册拦截器 4.接口限流测试 写在前…
阅读更多...
2024最新Win系统下VSCode下载安装与配置C/C++教程

2024最新Win系统下VSCode下载安装与配置C/C++教程

2024最新Win系统下VSCode下载安装与配置C/C教程 文章目录 2024最新Win系统下VSCode下载安装与配置C/C教程1、下载安装VSCode2、安装运行时环境GCGC的环境配置 3、安装VSCode插件4、配置程序调试环境4.1确定文件存储路径4.2新建文件夹【.vscode】4.3在.vscode文件夹里新建四个配…
阅读更多...
yarn按包的时候报错 ../../../package.json: No license field

yarn按包的时候报错 ../../../package.json: No license field

运行 yarn config list 然后运行 yarn config set strict-ssl false 之后yarn就成功了
阅读更多...
Canal配置

Canal配置

注&#xff1a;开发环境服务器&#xff1a;172.16.8.35 用develop用户登录。 进入canal安装目录&#xff1a;cd /home/devops/canal/deployer/conf 复制dst_vehicle目录&#xff0c;重命名为自己服务的数据库名 cp -r dst_vehicle/ dst_bill 进入dst_bill目录&#xff0c;删…
阅读更多...
docker网段冲突导致主机连接不上

docker网段冲突导致主机连接不上

前提&#xff1a;windows电脑链接liunx服务器&#xff0c;liunx服务器里面起了docker。 场景&#xff1a;在liunx服务器里面&#xff0c;用docker-compose up -d启动容器过程中&#xff0c;终止了windows服务器连接liunx服务器 可能原因&#xff1a;1.docker自身的网卡网段与连…
阅读更多...
Ubuntu20.04更换镜像源------最简单的教程

Ubuntu20.04更换镜像源------最简单的教程

本教程适用于&#xff1a;Ubuntu22.04 操作流程 打开终端&#xff0c;运行以下命令&#xff1a; sudo sed -i "shttp://.*archive.ubuntu.comhttps://mirrors.tuna.tsinghua.edu.cng" /etc/apt/sources.list 运行后即完成更改。 如果找不到22.04的镜像&#xff…
阅读更多...
机器学习——元学习

机器学习——元学习

元学习&#xff08;Meta Learning&#xff09;是一种机器学习方法&#xff0c;旨在使模型能够学习如何学习。它涉及到在学习过程中自动化地学习和优化学习算法或模型的能力。元学习的目标是使模型能够从有限的训练样本中快速适应新任务或新环境。 在传统的机器学习中&#xff…
阅读更多...
ffmpeg实现媒体流解码

ffmpeg实现媒体流解码

ffmpeg Version : 5.14 本期主要讲解怎么将MP4媒体流的视频解码为yuv，音频解码为pcm数据；在此之前我们要先了解解复用和复用的概念； 解复用：像mp4是由音频和视频组成的（其他内容流除外）；将MP4的流拆分成视频流（h264或h265等）和音频流（AAC或mp3等）； 复用：就是将音频…
阅读更多...
QT控件之显示控件

QT控件之显示控件

Qt Designer显示窗口部件提供的面板中&#xff0c;提供了10种显示小部件 &#xff08;1&#xff09; Label标签 &#xff08;2&#xff09; Text Browser文本浏览器 &#xff08;3&#xff09; Graphics View图形视图 &#xff08;4&#xff09; Calendar Widget日历 &…
阅读更多...
银行监管报送系统介绍（十二）：非居民金融账户涉税信息报送

银行监管报送系统介绍（十二）：非居民金融账户涉税信息报送

国家税务总局、财政部、中国人民银行、中国银行业监督管理委员会、中国证券监督管理委员会、国家金融监督管理总局2017年5月9日发布、2017年7月1日起施行的《非居民金融账户涉税信息尽职调查管理办法》。 一、《管理办法》出台的背景是什么&#xff1f; 　　受二十国集团&…
阅读更多...
快速幂算法在Java中的应用

快速幂算法在Java中的应用

引言&#xff1a; 在计算机科学和算法领域中&#xff0c;快速幂算法是一种用于高效计算幂运算的技术。在实际编程中&#xff0c;特别是在处理大数幂运算时&#xff0c;快速幂算法能够显著提高计算效率。本文将介绍如何在Java中实现快速幂算法&#xff0c;并给出一些示例代码和应…
阅读更多...
计算机组成原理 — 指令系统

计算机组成原理 — 指令系统

指令系统 指令系统指令的概述指令的格式指令的字长取决于 操作数类型和操作种类操作数的类型数据在存储器中的存放方式操作类型 寻址方式指令寻址数据寻址立即寻址直接寻址隐含寻址间接寻址寄存器寻址寄存器间接寻址基址寻址变址寻址堆栈寻址 RISC 和 CISC 技术RISC 即精简指令…
阅读更多...
工业无线网关在汽车制造企业的应用效果和价值-天拓四方

工业无线网关在汽车制造企业的应用效果和价值-天拓四方

随着智能制造的快速发展&#xff0c;工业无线网关作为关键通信设备&#xff0c;在提升生产效率、优化生产流程、实现设备间的互联互通等方面发挥着越来越重要的作用。以下是一个关于工业无线网关在智能制造行业应用的具体案例&#xff0c;展示了其在实际生产中的应用效果和价值…
阅读更多...
Linux系统使用Docker部署Portainer结合内网穿透实现远程管理容器和镜像

Linux系统使用Docker部署Portainer结合内网穿透实现远程管理容器和镜像

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
vue2高德地图选点

vue2高德地图选点

<template><el-dialog :title"!dataForm.id ? 新建 : isDetail ? 详情 : 编辑" :close-on-click-modal"false" :visible.sync"show" class"rv-dialog rv-dialog_center" lock-scroll width"74%" :before-close&q…
阅读更多...
windows上打开redis服务闪退问题处理

windows上打开redis服务闪退问题处理

方法1&#xff1a;在windows上面打开redis服务时&#xff0c;弹窗闪退可能是6379端口占用&#xff0c;可以用以下命令查看&#xff1a; netstat -aon | findstr 6379 如果端口被占用可以用这个命令解决&#xff1a; taskkill /f /pid 进程号 方法2&#xff1a; 可以使用…
阅读更多...
利用python搭建临时文件传输服务

利用python搭建临时文件传输服务

场景 如果想从一台服务器上传输文件又多种方法&#xff0c;其中常见的是利用scp进行传输&#xff0c;但是需要知道服务器的账号密码才能进行传输&#xff0c;但有时候我们并不知道账号密码&#xff0c;这个时候我们就可以通过python -m SimpleHTTPServer 命令进行传输文件 启…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023