当前位置: 首页 > 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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...