当前位置: 首页 > news >正文

数据结构 1-2 线性表的链式存储-链表

1 原理

顺序表的缺点:

  • 插入和删除移动大量元素
  • 数组的大小不好控制
  • 占用一大段连续的存储空间,造成很多碎片

链表规避了上述顺序表缺点

逻辑上相邻的两个元素在物理位置上不相邻

头结点

L:头指针

头指针:链表中第一个结点的存储位置,用来标识单链表。

头结点:在单链表第一个结点之前附加的一个结点,为了操作上的方便。

   若链表有头结点,则头指针永远指向头结点,不论链表是否为空,头指针均不为空,头指针是链表的必须元素,他标识一个链表。头结点是为了操作的方便而设立的,其数据域一般为空,或者存放链表的长度。有头结点后,对在第一结点前插入和删除第一结点的操作就统一了,不需要频繁 重置头指针。但头结点不是必须的。

 优缺点

优点:

  • 插入和删除操作不需要移动元素,只需要修改指针
  • 不需要大量的连续存储空间

缺点:

  • 单链表附加指针域,也存在浪费存储空间的缺点
  • 查找操作时需要从表头开始遍历,依次查找,不能随机存取

2 表示

2.1 定义

typedef int ElemType ;typedef struct LNode{ //单链表结点类型ElemType  data; //数据域struct LNode* next;//指针域
}LNode, *LinkList;

2.2 新建链表

2.2.1 头插法新建链表

void list_head_insert(LinkList &L)
{ElemType x;LNode *s;L= (LinkList)malloc(sizeof(LNode));//申请头节点空间L->next = NULL;scanf("%d",&x);while(x!=9999){s= (LinkList)malloc(sizeof(LNode));//申请节点空间s->data = x;s->next = L->next;//指向原本第一个节点L->next = s; //头结点的nextscanf("%d",&x);}
}
 2.2.2 尾插法新建链表

void list_tail_insert(LinkList &L)
{L= (LinkList)malloc(sizeof(LNode));//申请头节点空间ElemType x;LNode *s, *r = L;//s是用来指向新节点,r始终指向链表尾部L->next = NULL;scanf("%d", &x);while(x!=9999){s = (LinkList) malloc(sizeof(LNode));s->data=x;r->next = s;r=s;scanf("%d", &x);}r->next=NULL;//让为节点的next=NULL}

 2.3 打印链表

void print_list(LinkList L)
{L = L->next;while(L != NULL){printf("%3d",L->data);L =L->next;}printf("\n");
}

2.4 查找

2.4.1 按位置查找

头节点代表第0个位置

 

//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int i = 0;if(SearchPos < 0){return NULL;}while(L && i < SearchPos){L = L->next;i++;}return L;
}
2.4.2 按值查找

//按值 查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{while(L){if(L->data ==SearchVal){return L;}else{L =L->next;}}return NULL;}

 2.5 插入

插入情况 

 

bool ListFrontInsert(LinkList L, int InsertPose, ElemType InsertValue)
{LinkList  p = GetElem(L, InsertPose-1);if(p == NULL){return false;}LinkList q ;q =(LinkList)malloc(sizeof(LNode));q->data = InsertValue;q->next = p->next;p->next = q;return true;}

2.6 删除

删除注意的点:

  • 需要释放删除节点的空间
  • 需要判断删除的位置是否存在

​​​​​​​

void dele_elem(ListLink L, int pos) {if (pos <0) {return ;}ListLink r,q; //q用来存储要删除的节点r = find_elem(L, pos -1);if (NULL == r) {return;}q=r->next;if (q==NULL){return;}r->next = q->next;//断链free(q);q = NULL;//防止野指针
}

引用:要不要对变量进行赋值,如果不用不加引用,若要加引用

相关文章:

数据结构 1-2 线性表的链式存储-链表

1 原理 顺序表的缺点&#xff1a; 插入和删除移动大量元素数组的大小不好控制占用一大段连续的存储空间&#xff0c;造成很多碎片 链表规避了上述顺序表缺点 逻辑上相邻的两个元素在物理位置上不相邻 头结点 L&#xff1a;头指针 头指针&#xff1a;链表中第一个结点的存储…...

ArcGIS Pro进行坡度与坡向分析

在地理信息系统中&#xff0c;坡度分析是一项至关重要的空间分析方法&#xff0c;旨在精确计算地表或地形的坡度&#xff0c;为地形特征识别、土地资源规划、环境保护、灾害预警等领域提供科学依据。本文将详细介绍如何利用ArcGIS Pro这一强大的地理信息系统软件&#xff0c;进…...

My first Android application

界面元素组成&#xff1a; 功能代码&#xff1a; /*实现功能&#xff1a;当输入内容后&#xff0c;欢迎文本发生相应改变&#xff0c;并清除掉文本域内容当未输入任何内容时&#xff0c;弹出提示文本以警告用户*/val greetingText findViewById<TextView>(R.id.printer)…...

ZLMediaKi集群设置

要在集群环境中部署 ZLMediaKit&#xff0c;您可以按照以下步骤进行操作。ZLMediaKit 是一个高性能的流媒体服务器&#xff0c;支持 RTMP、RTSP、HLS 等协议。以下是一个详细的集群部署方案&#xff1a; ### 1. 环境准备 - **服务器**&#xff1a;准备多台服务器&#xff0c;…...

Docker基础实践与应用举例

Docker 是一个轻量级容器化平台&#xff0c;通过将应用及其依赖打包到容器中&#xff0c;实现快速部署和环境一致性。以下是 Docker 的实践与应用场景举例&#xff0c;结合具体操作步骤&#xff1a; 一、基础实践 1. 快速启动一个容器 # 运行一个Nginx容器&#xff0c;映射宿…...

Innovus中快速获取timing path逻辑深度的golden脚本

在实际项目中我们经常会遇到一条timing path级数特别多&#xff0c;可能是一两页都翻不完。此时&#xff0c;我们大都需要手工去数这条path上到底有哪些是设计本身的逻辑&#xff0c;哪些是PR工具插入的buffer和inverter。 数字IC后端手把手培训教程 | Clock Gating相关clock …...

百度AI图片助手,免费AI去水印、画质修复、画面延展以及局部替换

最近&#xff0c;要是你常用百度图片&#xff0c;可能已经发现了它新添的一个超实用功能——百度AI图片助手。但很多朋友不知道它的入口地址&#xff0c;我们今天给大家分享一下。 这个功能的出现&#xff0c;在图片编辑修改方面带来了极大便利&#xff0c;它涵盖了AI去水印、…...

【前端】Axios AJAX Fetch

不定期更新&#xff0c;建议关注收藏点赞。 目录 AxiosAJAXCORS 允许跨域请求 Fetch Axios axios 是一个基于 Promise 的 JavaScript HTTP 客户端&#xff0c;用于浏览器和 Node.js 中发送 HTTP 请求。它提供了一个简单的 API 来发起请求&#xff0c;并处理请求的结果。axios …...

测试面试题:以一个登录窗口为例,设计一下登录界面测试的思路和方法

在测试登录窗口时,可以从 表单测试、 逻辑判断和 业务流程三个方面设计测试思路和方法。以下是一个详细的测试方案: 1. 表单测试 表单测试主要关注输入框、按钮等UI元素的正确性和用户体验。 测试点: 输入框测试 用户名和密码输入框是否正常显示。输入框是否支持预期的字符类…...

Android之图片保存相册及分享图片

文章目录 前言一、效果图二、实现步骤1.引入依赖库2.二维码生成3.布局转图片保存或者分享 总结 前言 其实现在很多分享都是我们自定义的&#xff0c;更多的是在界面加了很多东西&#xff0c;然后把整个界面转成图片保存相册和分享&#xff0c;而且现在分享都不需要第三方&…...

EX_25/2/24

写一个三角形类&#xff0c;拥有私有成员 a,b,c 三条边 写好构造函数初始化 abc 以及 abc 的set get 接口 再写一个等腰三角形类&#xff0c;继承自三角形类 1&#xff1a;写好构造函数&#xff0c;初始化三条边 2&#xff1a;要求无论如何&#xff0c;等腰三角形类对象&#x…...

ElasticSearch公共方法封装

业务场景 1、RestClientBuilder初始化&#xff08;同时支持单机与集群&#xff09; 2、发送ES查询请求公共方法封装&#xff08;支持sql、kql、代理访问、集群访问、鉴权支持&#xff09; 3、判断ES索引是否存在&#xff08;/_cat/indices/${indexName}&#xff09; 4、判断ES…...

JVM之JVM的组成

Java 虚拟机&#xff08;JVM&#xff09;是 Java 程序的运行核心&#xff0c;它主要由类加载系统、运行时数据区、执行引擎和本地方法接口这几个关键部分组成。 类加载系统&#xff08;Class Loading System&#xff09; 类加载系统负责在程序运行时动态地将 Java 类加载到 J…...

贪心算法

int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮&#xff0c;准备去和看守仓库的猫做交易&#xff0c;因为仓库里有小老鼠喜欢吃的五香豆&#xff0c;第i个房间有J[i] 磅的五香豆&#xf…...

Linux下安装中文输入法总结

Linux下安装中文输入法总结_linux 微软拼音-CSDN博客文章浏览阅读4.2w次&#xff0c;点赞21次&#xff0c;收藏92次。众所周知&#xff0c;fcitx和ibus是两款很好用的Linux中文输入法框架。下面来说一下其安装方法以及会踩的坑。首先fcitx和ibus是不能共存的&#xff0c;两者只…...

人工智能(AI):科技新纪元的领航者

摘要 人工智能&#xff08;AI&#xff09;作为当今科技领域最具变革性的力量之一&#xff0c;正以惊人的速度重塑着我们的世界。本文旨在全面且专业地介绍人工智能&#xff0c;涵盖其定义、发展历程、关键技术、应用领域、面临的挑战以及未来展望等方面&#xff0c;以期为读者…...

c3p0、Druid连接池+工具类 Apache-DbUtils (详解!!!)

数据库连接池是在应用程序启动时创建一定数量的数据库连接&#xff0c;并将这些连接存储在池中。当应用程序需要与数据库通信时&#xff0c;它可以向池中请求一个连接&#xff0c;使用完后将连接归还给池&#xff0c;而不是关闭连接。这样可以减少创建和关闭连接的开销&#xf…...

鸿蒙开发深入浅出03(封装通用LazyForEach实现懒加载)

鸿蒙开发深入浅出03&#xff08;封装通用LazyForEach实现懒加载&#xff09; 1、效果展示2、ets/models/BasicDataSource.ets3、ets/models/HomeData.ets4、ets/api/home.ets5、ets/pages/Home.ets6、ets/views/Home/SwiperLayout.ets7、后端代码 1、效果展示 2、ets/models/Ba…...

AWS - Redshift - 外部表读取 Parquet 文件中 timestamp 类型的数据

问题&#xff1a; 通过 Redshift Spectrum 功能可以读取 S3 中的文件&#xff0c;当读取 Parquet 文件时&#xff0c;如果列格式设置为 timestamp&#xff0c; 通过 psql 客户端读取会出现以下错误&#xff1a; testdb# select * from myspectrum_schema_0219.test_ns; ERROR…...

Ubuntu20.04之VNC的安装使用与常见问题

Ubuntu20.04之VNC的安装与使用 安装图形桌面选择安装gnome桌面选择安装xface桌面 VNC-Server安装配置开机自启 VNC Clientroot用户无法登入问题临时方案永久方案 安装图形桌面 Ubuntu20.04主流的图形桌面有gnome和xface两种&#xff0c;两种桌面的安装方式我都会写&#xff0c…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...