C、C++常用数据结构:链表
文章目录
- 基本概念
- 链表的创建
- 链表结点定义
- 链表创建
- 链表遍历
- 链表释放
- 链表查找
- 链表删除
- 链表插入
- 测试用例
基本概念
参考:链表基础知识详解(非常详细简单易懂)-CSDN博客
- 链表是一种线性存储结构,链表在物理存储上是非连续的,数据元素的逻辑顺序通过链表中的指针链接
- 链表由一系列的结点组成,每个节点主要包含两个部分:数据域+指针域
- 数据域存放实际的数据;指针域存放下一个节点的地址(首地址)
- 链表分为单向链表和双向链表:单向链表由一个指针next,存放下一个节点的首地址;双向链表由next和previous,分别存放下一个节点和上一个节点的首地址
- 常见面试题:链表和数组的对比。链表的内存是不连续的,链表通过节点把离散的数据链接成一个表;而数组是通过开辟一段连续的内存来存储数据。数组成员和链表节点的数据类型可以是标准的C类型或者是用户自定义的类型。数组有起始地址和结束地址,链表没有明确的起始地址和结束地址,为了方便操作,可能会人为规定一个根节点(当然这是对于双向链表来说的,单向链表还是有头尾之分的)
以下代码只针对单链表
链表的创建
链表结点定义
// 定义一个链表节点结构体
typedef struct listNode
{int val;struct listNode *next;
} listNode;
链表创建
/*** 创建链表* 用到了二级指针要改变指针指向的值,传入指针要改变指针的指向(指针本身),传入二级指针*/
void listCreate(listNode **p_head, listNode *p_new)
{listNode *p_move = *p_head;if (*p_head == NULL){*p_head = p_new;}else{while (p_move->next != NULL){p_move = p_move->next;}p_move->next = p_new;p_new->next = NULL;}
}
链表遍历
/*** 遍历链表*/
void listPrint(listNode *head)
{if (head == NULL){cout << "list is NULL" << endl;return;}listNode *p = head;while (p != NULL){cout << p->val << " ";p = p->next;}cout << endl;
}
链表释放
/*** 释放链表*/
void listFree(listNode **head)
{listNode *p = *head;while (*head != NULL){p = *head;*head = (*head)->next;free(p);p = NULL; // 防止野指针}cout << "list free" << endl;
}
链表查找
/*** 链表查找*/
void listFind(listNode *head, int val)
{if (head == NULL)return;listNode *p = head;while (p != NULL){if (p->val == val){cout << "I find " << p->val;}p = p->next;}cout << endl;
}
链表删除
/*** 链表删除*/
void listDelete(listNode **head, int val)
{if (*head == NULL){return;}listNode *slow = NULL;listNode *fast = *head;while (fast != NULL){if (fast->val == val){if (fast == *head){*head = (*head)->next;free(fast);cout << "delete done" << endl;fast = *head;}else{slow->next = fast->next;free(fast);cout << "delete done" << endl;fast = slow->next;}}else{slow = fast;fast = fast->next;}}
}
链表插入
/*** 链表插入* 根据val值来判断插入位置(从小到大)*/
void listInsert(listNode **head, listNode *p_new)
{// 如果链表为空,则插入的结点为头结点if (*head == NULL){*head = p_new;p_new->next = NULL;return;}// 定义快慢指针listNode *slow = NULL;listNode *fast = *head;while (p_new->val >= fast->val && fast->next != NULL){slow = fast;fast = fast->next;}if (p_new->val < fast->val) // 如果找到了大于新结点val的结点,则新结点插入该结点左边{if (fast == *head){p_new->next = *head;*head = p_new;}else{p_new->next = slow->next;slow->next = p_new;}}else // 没有找到就插入右边{fast->next = p_new;p_new->next = NULL;}
}
测试用例
#include <iostream>
#include <vector>
#include <cstdio>using namespace std;// 定义一个链表节点结构体
typedef struct listNode
{int val;struct listNode *next;
} listNode;/*** 创建链表* 用到了二级指针要改变指针指向的值,传入指针要改变指针的指向(指针本身),传入二级指针*/
void listCreate(listNode **p_head, listNode *p_new)
{listNode *p_move = *p_head;if (*p_head == NULL){*p_head = p_new;}else{while (p_move->next != NULL){p_move = p_move->next;}p_move->next = p_new;p_new->next = NULL;}
}/*** 遍历链表*/
void listPrint(listNode *head)
{if (head == NULL){cout << "list is NULL" << endl;return;}listNode *p = head;while (p != NULL){cout << p->val << " ";p = p->next;}cout << endl;
}/*** 释放链表*/
void listFree(listNode **head)
{listNode *p = *head;while (*head != NULL){p = *head;*head = (*head)->next;free(p);p = NULL; // 防止野指针}cout << "list free" << endl;
}/*** 链表查找*/
void listFind(listNode *head, int val)
{if (head == NULL)return;listNode *p = head;while (p != NULL){if (p->val == val){cout << "I find " << p->val;}p = p->next;}cout << endl;
}/*** 链表删除*/
void listDelete(listNode **head, int val)
{if (*head == NULL){return;}listNode *slow = NULL;listNode *fast = *head;while (fast != NULL){if (fast->val == val){if (fast == *head){*head = (*head)->next;free(fast);cout << "delete done" << endl;fast = *head;}else{slow->next = fast->next;free(fast);cout << "delete done" << endl;fast = slow->next;}}else{slow = fast;fast = fast->next;}}
}/*** 链表插入* 根据val值来判断插入位置(从小到大)*/
void listInsert(listNode **head, listNode *p_new)
{// 如果链表为空,则插入的结点为头结点if (*head == NULL){*head = p_new;p_new->next = NULL;return;}// 定义快慢指针listNode *slow = NULL;listNode *fast = *head;while (p_new->val >= fast->val && fast->next != NULL){slow = fast;fast = fast->next;}if (p_new->val < fast->val) // 如果找到了大于新结点val的结点,则新结点插入该结点左边{if (fast == *head){p_new->next = *head;*head = p_new;}else{p_new->next = slow->next;slow->next = p_new;}}else // 没有找到就插入右边{fast->next = p_new;p_new->next = NULL;}
}int main(int argc, char const *argv[])
{listNode *head = NULL, *p_new = NULL;int num = 0;for (int i = 0; i < 10; i++){p_new = (listNode *)malloc(sizeof(listNode));p_new->val = i;listCreate(&head, p_new);}listPrint(head);listFind(head, 3);listDelete(&head, 3);listPrint(head);cout << "结点插入测试" << endl;listNode *p_insert = (listNode *)malloc(sizeof(listNode));p_insert->val = 3;listInsert(&head, p_insert);listPrint(head);listFree(&head);return 0;
}
相关文章:
C、C++常用数据结构:链表
文章目录 基本概念链表的创建链表结点定义链表创建 链表遍历链表释放链表查找链表删除链表插入测试用例 基本概念 参考:链表基础知识详解(非常详细简单易懂)-CSDN博客 链表是一种线性存储结构,链表在物理存储上是非连续的…...
【devops】devops-ansible之剧本变量使用
本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》:python零基础入门学习 《python运维脚本》: python运维脚本实践 《shell》:shell学习 《terraform》持续更新中:terraform_Aws学习零基础入门到最佳实战 《k8》从问题中去学习k8s 《docker学习》暂未更…...
《Linux从小白到高手》理论篇:一文概览常用Linux重要配置文件
List item 今天继续宅家,闲来无事接着写。本篇是《Linux从小白到高手》理论篇的最后一篇了。本篇集中介绍所有常用的Linux重要配置文件。 用这个命令可以查看配置文件所在的位置:如上图 locate "*.conf" "*.ini" "*.cfg&quo…...
采购管理流程:掌握最后阶段的关键要点
采购管理流程是企业运作中的核心职能之一,涵盖了获取商品和服务的一系列步骤,旨在以高效率和经济效益的方式进行。深入理解该流程的每个环节极为关键,特别是最后阶段,这可确保所有采购活动的圆满完成以及与供应商维持良好关系。 …...
cherry-markdown开源markdown组件详细使用教程
文章目录 前言开发定位目标调研技术方案前提工作量安排数据库表设计实现步骤1、引入依赖2、实现cherry-markdown的vue组件(修改上传接口路径)3、支持draw.io组件4、支持展示悬浮目录toc前端使用:编辑状态使用cherry-markdown的vue组件前端使用…...
Android SystemUI组件(10)禁用/重启锁屏流程分析
该系列文章总纲链接:专题分纲目录 Android SystemUI组件 本章关键点总结 & 说明: 说明:本章节持续迭代之前章节的思维导图,主要关注左侧上方锁屏分析部分 应用入口处理流程解读 即可。 在 Android 系统中,禁用锁屏…...
【Geeksend邮件营销】外贸邮件中的一些常用语
外贸邮件中的相关术语丰富多样,涉及邮件的开头、正文、结尾以及特定的商务用语。以下是一些常用的外贸邮件术语及其解释: 一、邮件开头用语 1、问候语: Dear [收件人姓名], Trust this email finds you well. How are you? …...
配置静态ip
背景:因业务需要需要将一台服务器从机房搬到实验室,机房是光纤,实验室是网线,需要重新配置下静态ip 确认网络配置文件(网上没找到,不清楚一下方法对不对) 先随便一个网口连接网线,执行 ifconfig -a 找到带“RUNNING”的(lo不是哈)----eno1 到/etc/sysconfig/network…...
[LeetCode] LCR170. 交易逆序对的总数
题目描述: 在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record,返回其中存在的「交易逆序对」总数。 示例 1: 输入:…...
大开眼界,原来指针还能这么玩?
文章目录 第一阶段:基础理解目标:内容:题目:答案解析: 第二阶段:指针与数组目标:内容:题目:答案解析: 第三阶段:指针与字符串目标:内容…...
揭秘选择知识产权管理系统的常见误区,避免踩坑
在当今知识经济时代,知识产权管理对于企业的发展至关重要。为了提高管理效率和效果,许多企业纷纷选择采用知识产权管理系统。然而,在选择过程中,存在着一些容易陷入的误区。 误区一:只关注功能,忽视用户体验…...
计算机组成原理之存储器的分类
1、按存储介质分类: 半导体存储器:使用半导体器件作为存储元件,如TTL和MOS存储器。这类存储器体积小、功耗低、存取时间短,但断电后数据会丢失。 磁表面存储器:使用磁性材料涂覆在金属或塑料基体表面作为存储介质&…...
Linux(不同版本系统包含Ubuntu)下安装mongodb详细教程
一、下载MongoDB 在MongoDB官网下载对应的MongoDB版本,可以点击以下链接快速跳转到下载页面: mongodb官网下载地址 注意选择和自己操作系统一致的platform,可以先查看自己的操作系统 查看操作系统详情 命令: uname -a 如图:操…...
如何扫描HTTP代理:步骤与注意事项
HTTP代理是一个复杂的过程,通常用于寻找可用的代理服务器,以便在网络中实现匿名或加速访问。虽然这个过程可以帮助用户找到适合的代理,但也需要注意合法性和道德问题。本文将介绍如何扫描HTTP代理,并提供一些建议和注意事项。 什…...
【分布式微服务云原生】gRPC与Dubbo:分布式服务通信框架的双雄对决
目录 引言gRPC:Google的高性能RPC框架gRPC通信流程图 Dubbo:阿里巴巴的微服务治理框架Dubbo服务治理流程图 表格:gRPC与Dubbo的比较结论呼吁行动Excel表格:gRPC与Dubbo特性总结 摘要 在构建分布式系统时,选择合适的服务…...
Python | Leetcode Python题解之第450题删除二叉搜索树中的节点
题目: 题解: class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:cur, curParent root, Nonewhile cur and cur.val ! key:curParent curcur cur.left if cur.val > key else cur.rightif cur i…...
[Linux]从零开始的网站搭建教程
一、谁适合本次教程 学习Linux已经有一阵子了,相信大家对LInux都有一定的认识。本次教程会教大家如何在Linux中搭建一个自己的网站并且实现内网访问。这里我们会演示在Windows中和在Linux中如何搭建自己的网站。当然,如果你没有Linux的基础,这…...
牛客——xay loves or与 __builtin_popcount的使用
xay loves or 题目描述 登录—专业IT笔试面试备考平台_牛客网 运行思路 题目要求我们计算有多少个正整数 yy 满足条件 x \text{ OR } y sx OR ys。这里的“OR”是指按位或运算。为了理解这个问题,我们需要考虑按位或运算的性质。 对于任意两个位 a_iai 和 b_…...
Docker学习和部署ry项目
文章目录 停止Docker重启设置开机自启执行docker ps命令,如果不报错,说明安装启动成功2.然后查看数据卷结果3.查看数据卷详情结果4.查看/var/lib/docker/volumes/html/_data目录可以看到与nginx的html目录内容一样,结果如下:5.进入…...
Linux中设置cd命令后直接显示当前目录下的所有文件
Linux中cd命令后默认是不显示该目录下的文件的,略微不方便。换个环境经常遇到需要重新设置的情况,网上已有很多发帖了,这里主要汇总下比较简单且常见的bash与csh下的设置方法。 实现的本质就是将"cd" 与 "ls"组合起来&am…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...
