【数据结构】手撕单链表

目录

一，链表的概念及结构

二，接口实现

        1，单链表的创建

        2，接口函数

        3，动态创立新结点

        4，打印

        5，头插

        6，头删

        7，尾插

        8，尾删

        9，查找

        10，单链表在pos位置之后插入x

        11，单链表删除pos位置之后的值

        12，销毁

三，源代码

LKList.h

LKList.c

四，总结

一，链表的概念及结构

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

 

 

 而在数据结构中：

注意：

1，从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

 2，现实中的结点一般都是从堆上申请出来的

 3，从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续；

 实际中链表的结构非常多样，今天我们来写一下单链表，此表一会其他的自然水到渠成！

二，接口实现

        1，单链表的创建

//无头 + 单向 + 非循环链表增删查改实现
typedef int LKLDataType;
typedef struct LinKedListNode
{LKLDataType data;struct LinKedListNode* next;
}LKLNode;

首先创建一个结构体表示单链表，data是存储的值，LKLDataType是储存的值的数据类型，next是结点----指向下一个；

这里的LKLDataType是int的重命名，也可以说是数据类型的重命名，这样统一化方便后续更改；

        2，接口函数

// 动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 头删
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾删
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 销毁
void LKLDestroy(LKLNode** plist);

 这是以上要实现的接口函数；

        3，动态创立新结点

//动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x)
{LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode));newnode->data = x;newnode->next = NULL;return newnode;
}

后面创立新节点时直接调用此函数，一定要向堆区申请空间，这样函数结束空间会保留不会被回收；

        4，打印

//打印
void LKLPrint(LKLNode* phead)
{assert(phead);LKLNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}

打印也就是打印data的值，用cur=phead然后每次打印完都让cur走向下一个直到为空结束；

        5，头插

//头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{assert(phead);LKLNode* newnode = BuyLKLNode(x);newnode->next = *phead;*phead = newnode;
}

先断言一下，既然插入数据那就要申请一个新节点，然后令新节点的next指向phead然后再令phead指向新节点；

        6，头删

//头删
void LKLNodeBackFront(LKLNode** phead)
{assert(phead);//为空assert(*phead);//非空LKLNode* newnode = (*phead)->next;free(*phead);*phead = newnode;
}

还是先断言，有人会问为什么要断言两次？其实很好判断，哪个需要解引用那个就需要断言；

令一个变量newnode等于头结点的下一个，在释放头结点，在令头结点指向newnode即可；

        7，尾插

//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{assert(phead);assert(*phead);LKLNode* newnode= BuyLKLNode(x);LKLNode* cur = *phead;//为空if (*phead == NULL){*phead = newnode;}//非空else{while (cur->next){cur = cur->next;}cur->next = newnode;}
}

还是先断言判断，然后要插入一个新的数据先申请一个新结点，如果头结点为空则直接让头结点指向新结点即可，如果头结点不为空，则需要找到next为空的结点，这里用一个循环搞定，然后再直接让next为空的结点指向新节点即可；

        8，尾删

//尾删
void LKLNodePopBack(LKLNode** phead)
{assert(phead);//为空assert(*phead);//一个if ((*phead)->next==NULL){free(*phead);*phead = NULL;}//两个及以上else{LKLNode* tail = *phead;/*LKLNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}free(prev->next);prev->next = NULL;*/while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

还是先断言一下，然后这里有两种情况，链表只有一个结点，两个以上结点的时候；

当链表只有一个结点也就是头结点，直接头删即可；

两个以上结点的时候，我这里有两种解决方案；

方案一常规法：先用循环找到next为空的结点，并且在循环里保留上一个结点prev，然后释放next为空的结点再让prev的next指向空即可；

方案二：不需要标记上一个结点，直接原地判断，判断结点的next的next是否为空，否则继续向后推进，是则释放结点的next然后再令自己的next指向空也就相当于变成了尾结点；

        9，查找

// 单链表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{assert(phead);LKLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}return NULL;
}

老样子先断言一下，然后直接用循环遍历链表找到data是x的值然后返回此结点即可；

        10，单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{assert(pos);LKLNode* newnode= BuyLKLNode(x);LKLNode* cur = pos;newnode->next = cur->next;cur->next = newnode;
}

先断言，要插入数据先申请一个新结点，然后令新结点的next指向pos的next，再返回来让pos的next指向新结点；

        11，单链表删除pos位置之后的值

// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{assert(pos);assert(pos->next);LKLNode* cur = pos;LKLNode* newnode = cur->next->next;free(cur->next);cur->next = newnode;
}

要删除值首先要确保得有值，所以开始断言；

先定义一个变量newnode指向pos的next的next，然后再释放pos的next，再令pos指向newnode以达到删除之后的效果；

        12，销毁

// 单链表的销毁
void LKLDestroy(LKLNode** phead)
{assert(phead);assert(*phead);LKLNode* cur = *phead;LKLNode* next = NULL;while (cur){next = cur->next;free(cur);cur = next;}
}

老样子那个需要解引用那个就先断言一下，然后用循环遍历，先标记下一个结点，然后释放自己，再让自己指向标记的结点直到为空结束；

三，源代码

LKList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//无头 + 单向 + 非循环链表增删查改实现
typedef int LKLDataType;
typedef struct LinKedListNode
{LKLDataType data;struct LinKedListNode* next;
}LKLNode;// 动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 头删
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾删
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 销毁
void LKLDestroy(LKLNode** plist);

LKList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"LKList.h"//动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x)
{LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode));newnode->data = x;newnode->next = NULL;return newnode;
}
//头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{assert(phead);LKLNode* newnode = BuyLKLNode(x);newnode->next = *phead;*phead = newnode;
}
//头删
void LKLNodeBackFront(LKLNode** phead)
{assert(phead);//为空assert(*phead);//非空LKLNode* newnode = (*phead)->next;free(*phead);*phead = newnode;
}
//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{assert(phead);assert(*phead);LKLNode* newnode= BuyLKLNode(x);LKLNode* cur = *phead;//为空if (*phead == NULL){*phead = newnode;}//非空else{while (cur->next){cur = cur->next;}cur->next = newnode;}
}
//尾删
void LKLNodePopBack(LKLNode** phead)
{assert(phead);//为空assert(*phead);//一个if ((*phead)->next==NULL){free(*phead);*phead = NULL;}//两个及以上else{LKLNode* tail = *phead;/*LKLNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}free(prev->next);prev->next = NULL;*/while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
// 单链表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{assert(phead);LKLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}return NULL;
}
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{assert(pos);LKLNode* newnode= BuyLKLNode(x);LKLNode* cur = pos;newnode->next = cur->next;cur->next = newnode;
}
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{assert(pos);assert(pos->next);LKLNode* cur = pos;LKLNode* newnode = cur->next->next;free(cur->next);cur->next = newnode;
}// 单链表的销毁
void LKLDestroy(LKLNode** phead)
{assert(phead);assert(*phead);LKLNode* cur = *phead;LKLNode* next = NULL;while (cur){next = cur->next;free(cur);cur = next;}
}
//打印
void LKLPrint(LKLNode* phead)
{assert(phead);LKLNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}

四，总结

做数据结构的题目画图很重要，小伙伴们刚开始喜欢用脑子去构图想象，但遇到复杂的情况会紊乱的，画图最为可观方便，可以培养一个良好的画图习惯；

如有不足之处欢迎来补充交流！

完结。。。

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

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

相关文章

ELK安装、部署、调试（六） logstash的安装和配置

ELK安装、部署、调试（六） logstash的安装和配置

1.介绍 Logstash是具有实时流水线能力的开源的数据收集引擎。Logstash可以动态统一不同来源的数据&#xff0c;并将数据标准化到您选择的目标输出。它提供了大量插件&#xff0c;可帮助我们解析&#xff0c;丰富&#xff0c;转换和缓冲任何类型的数据。 管道&#xff08;Logs…
阅读更多...
2023年高教社杯 国赛数学建模思路 - 案例：感知机原理剖析及实现

2023年高教社杯 国赛数学建模思路 - 案例：感知机原理剖析及实现

文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法&#xff0c;其…
阅读更多...
LeetCode239.滑动窗口最大值

LeetCode239.滑动窗口最大值

看到这道题我就有印象&#xff0c; 我在剑指offer里面做过这道题&#xff0c;我记得当时用的是优先队列&#xff0c;然后我脑子里一下子就有了想法&#xff0c;拿优先队列作为窗口&#xff0c;每往右移动一步&#xff0c;把左边的数remove掉&#xff0c;把右边的数add进来&…
阅读更多...
Mysql-索引查询相关

Mysql-索引查询相关

一、单表查询 1.1 二级索引为null 不论是普通的二级索引&#xff0c;还是唯一二级索引&#xff0c;它们的索引列对包含 NULL 值的数量并不限制&#xff0c;所以我们采用key IS NULL 这种形式的搜索条件最多只能使用 ref 的访问方法&#xff0c;而不是 const 的访问方法 1.2 c…
阅读更多...
MySQL函数和约束

MySQL函数和约束

MySQL常见函数 字符串常见函数 # concat : 字符串拼接 select concat(Hello , MySQL); # lower : 全部转小写 SELECT LOWER(Hello); # upper : 全部转大写 SELECT UPPER(hello); # lpad : 左填充 SELECT LPAD(hello,10,0); # rpad : 右填充 SELECT RPAD(hello,10,0); # trim…
阅读更多...
关于一个git的更新使用流程

关于一个git的更新使用流程

1.第一步使用git bash 使用git bash命令来进行操作&#xff08;当然我是个人比较喜欢用这种方法的&#xff09; 2. 第二步&#xff1a;连接 3.第三步&#xff1a;进入 4.第四步&#xff1a;查看分支 5.第五步&#xff1a;切换分支 将本地文件更新后之后进行提交 6.第六步&am…
阅读更多...
【VUE】数字动态变化到目标值-vue-count-to

【VUE】数字动态变化到目标值-vue-count-to

vue-count-to是一个Vue组件&#xff0c;用于实现数字动画效果。它可以用于显示从一个数字到另一个数字的过渡动画。 插件名&#xff1a;vue-count-to 官方仓库地址&#xff1a;GitHub - PanJiaChen/vue-countTo: Its a vue component that will count to a target number at a…
阅读更多...
Leetcode.100 相同的树

Leetcode.100 相同的树

给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 代码如下&#xff1a;…
阅读更多...
前端（十六）——微信小程序语音转文字，文字转语音功能的实现

前端（十六）——微信小程序语音转文字，文字转语音功能的实现

&#x1f60a;博主&#xff1a;小猫娃来啦 &#x1f60a;文章核心&#xff1a;微信小程序语音转文字&#xff0c;文字转语音功能的实现 文章目录 资源下载链接最关键的问题控制台报错30003语音转文字文字转语音效果图应用场景作用和优势实现思路 资源下载链接 CSDN资源下载&am…
阅读更多...
【QT】信号和槽（15）

【QT】信号和槽（15）

前面的内容说了很多不同的控件如何使用&#xff0c;今天来看下QT的核心&#xff0c;信号与槽&#xff08;Signals and slots&#xff09;&#xff01; 简单理解一下&#xff0c;就是我们的信号与槽连接上了之后&#xff0c;发射一个信号给到槽&#xff0c;槽函数接收到了这个信…
阅读更多...
uniapp 实现切换tab锚点定位到指定位置

uniapp 实现切换tab锚点定位到指定位置

1.主要使用uniapp scroll-view 组件的scroll-into-view属性实现功能 2.代码如下 <scroll-view:scroll-into-view"intoView"><u-tabsclass"tabs-list"change"tabChange":list"tabList"></u-tabs><view id"1&…
阅读更多...
Java实现根据按图搜索商品数据，按图搜索获取1688商品详情数据，1688拍立淘接口，1688API接口封装方法

Java实现根据按图搜索商品数据，按图搜索获取1688商品详情数据，1688拍立淘接口，1688API接口封装方法

要通过按图搜索1688的API获取商品详情跨境属性数据&#xff0c;您可以使用1688开放平台提供的接口来实现。以下是一种使用Java编程语言实现的示例&#xff0c;展示如何通过1688开放平台API获取商品详情属性数据接口&#xff1a; 首先&#xff0c;确保您已注册成为1688开放平台…
阅读更多...
探索Java集合框架—数据结构、ArrayList集合

探索Java集合框架—数据结构、ArrayList集合

一、背景介绍 Java集合的使用相信大家都已经非常得心应手&#xff0c;但是我们怎么做到知其然&#xff0c;更知其所以然这种出神入化的境界呢&#xff1f;我们揭开集合框架底层神秘面纱来一探究竟 目录 一、背景介绍 二、思路&方案 数据结构是什么&#xff1f; 数据结…
阅读更多...
...(电工操作证)考试题库完整版及答案选择题- 电工试题

...(电工操作证)考试题库完整版及答案选择题- 电工试题

阅读更多...
linux————ELK（日志收集系统集群）

linux————ELK（日志收集系统集群）

目录 一、为什么要使用ELK 二、ELK作用 二、组件 一、elasticsearch 特点 二、logstash 工作过程 INPUT&#xff08;输入&#xff09; FILETER(过滤) OUTPUTS&#xff08;输出&#xff09; 三、kibana 三、架构类型 ELK ELKK ELFK ELFKK EFK 四、构建ELk集群…
阅读更多...
Apache的简单介绍（LAMP架构+搭建Discuz论坛）

Apache的简单介绍（LAMP架构+搭建Discuz论坛）

文章目录 1.Apache概述1.1什么是apache1.2 apache的功能及特性1.2.1功能1.2.2特性 1.3 MPM 工作模式1.3.1 prefork模式1.3.2 worker模式1.3.3 event模式 2.LAMP概述2.1 LAMP的组成2.2 LAMP各组件的主要作用2.3 LAMP的工作过程2.4CGI和FastCGI 3.搭建Discuz论坛所需4.编译安装Ap…
阅读更多...
Mysql中explain执行计划信息中字段详解

Mysql中explain执行计划信息中字段详解

Mysql中explain执行计划信息中字段详解 1. 获取执行计划2. 字段含义2.1 id2.2 select_type2.3 table2.4 partitions2.5 type2.6 possible_keys2.7 key2.8 ley_len2.9 ref2.10 rows2.11 extra 1. 获取执行计划 explain select * from t5; --或 desc select * from t5;2. 字段含…
阅读更多...
滑动窗口实例1（长度最小的子数组）

滑动窗口实例1（长度最小的子数组）

题目&#xff1a; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 示例 1&#xff1a; …
阅读更多...
zookeeper 3.8.1安装和入门使用

zookeeper 3.8.1安装和入门使用

1、zookeeper环境搭建&#xff08;Windows单机版&#xff09; 1.1、 前提 必须安装jdk 1.8&#xff0c;配置jdk环境变量&#xff0c;步骤略 1.2、安装zookeeper 地址&#xff1a;https://zookeeper.apache.org/ 1.2.1、选择releases版本 1.2.2、下载安装包并解压 1.2.3、配…
阅读更多...
前端文件、图片直传OOS、分片上传、el-upload上传（vue+elementUI）

前端文件、图片直传OOS、分片上传、el-upload上传（vue+elementUI）

前言&#xff1a;基于天翼云的面相对象存储(Object-Oriented Storage&#xff0c;OOS),实现小文件的直接上传&#xff0c;大文件的分片上传。 开发文档地址&#xff1a;网址 上传之前的相关操作&#xff1a;注册账户&#xff0c;创建 AccessKeyId 和 AccessSecretKey之后&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023