数据结构 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 原理 顺序表的缺点: 插入和删除移动大量元素数组的大小不好控制占用一大段连续的存储空间,造成很多碎片 链表规避了上述顺序表缺点 逻辑上相邻的两个元素在物理位置上不相邻 头结点 L:头指针 头指针:链表中第一个结点的存储…...
ArcGIS Pro进行坡度与坡向分析
在地理信息系统中,坡度分析是一项至关重要的空间分析方法,旨在精确计算地表或地形的坡度,为地形特征识别、土地资源规划、环境保护、灾害预警等领域提供科学依据。本文将详细介绍如何利用ArcGIS Pro这一强大的地理信息系统软件,进…...
My first Android application
界面元素组成: 功能代码: /*实现功能:当输入内容后,欢迎文本发生相应改变,并清除掉文本域内容当未输入任何内容时,弹出提示文本以警告用户*/val greetingText findViewById<TextView>(R.id.printer)…...
ZLMediaKi集群设置
要在集群环境中部署 ZLMediaKit,您可以按照以下步骤进行操作。ZLMediaKit 是一个高性能的流媒体服务器,支持 RTMP、RTSP、HLS 等协议。以下是一个详细的集群部署方案: ### 1. 环境准备 - **服务器**:准备多台服务器,…...
Docker基础实践与应用举例
Docker 是一个轻量级容器化平台,通过将应用及其依赖打包到容器中,实现快速部署和环境一致性。以下是 Docker 的实践与应用场景举例,结合具体操作步骤: 一、基础实践 1. 快速启动一个容器 # 运行一个Nginx容器,映射宿…...
Innovus中快速获取timing path逻辑深度的golden脚本
在实际项目中我们经常会遇到一条timing path级数特别多,可能是一两页都翻不完。此时,我们大都需要手工去数这条path上到底有哪些是设计本身的逻辑,哪些是PR工具插入的buffer和inverter。 数字IC后端手把手培训教程 | Clock Gating相关clock …...
百度AI图片助手,免费AI去水印、画质修复、画面延展以及局部替换
最近,要是你常用百度图片,可能已经发现了它新添的一个超实用功能——百度AI图片助手。但很多朋友不知道它的入口地址,我们今天给大家分享一下。 这个功能的出现,在图片编辑修改方面带来了极大便利,它涵盖了AI去水印、…...
【前端】Axios AJAX Fetch
不定期更新,建议关注收藏点赞。 目录 AxiosAJAXCORS 允许跨域请求 Fetch Axios axios 是一个基于 Promise 的 JavaScript HTTP 客户端,用于浏览器和 Node.js 中发送 HTTP 请求。它提供了一个简单的 API 来发起请求,并处理请求的结果。axios …...
测试面试题:以一个登录窗口为例,设计一下登录界面测试的思路和方法
在测试登录窗口时,可以从 表单测试、 逻辑判断和 业务流程三个方面设计测试思路和方法。以下是一个详细的测试方案: 1. 表单测试 表单测试主要关注输入框、按钮等UI元素的正确性和用户体验。 测试点: 输入框测试 用户名和密码输入框是否正常显示。输入框是否支持预期的字符类…...
Android之图片保存相册及分享图片
文章目录 前言一、效果图二、实现步骤1.引入依赖库2.二维码生成3.布局转图片保存或者分享 总结 前言 其实现在很多分享都是我们自定义的,更多的是在界面加了很多东西,然后把整个界面转成图片保存相册和分享,而且现在分享都不需要第三方&…...
EX_25/2/24
写一个三角形类,拥有私有成员 a,b,c 三条边 写好构造函数初始化 abc 以及 abc 的set get 接口 再写一个等腰三角形类,继承自三角形类 1:写好构造函数,初始化三条边 2:要求无论如何,等腰三角形类对象&#x…...
ElasticSearch公共方法封装
业务场景 1、RestClientBuilder初始化(同时支持单机与集群) 2、发送ES查询请求公共方法封装(支持sql、kql、代理访问、集群访问、鉴权支持) 3、判断ES索引是否存在(/_cat/indices/${indexName}) 4、判断ES…...
JVM之JVM的组成
Java 虚拟机(JVM)是 Java 程序的运行核心,它主要由类加载系统、运行时数据区、执行引擎和本地方法接口这几个关键部分组成。 类加载系统(Class Loading System) 类加载系统负责在程序运行时动态地将 Java 类加载到 J…...
贪心算法
int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆,第i个房间有J[i] 磅的五香豆…...
Linux下安装中文输入法总结
Linux下安装中文输入法总结_linux 微软拼音-CSDN博客文章浏览阅读4.2w次,点赞21次,收藏92次。众所周知,fcitx和ibus是两款很好用的Linux中文输入法框架。下面来说一下其安装方法以及会踩的坑。首先fcitx和ibus是不能共存的,两者只…...
人工智能(AI):科技新纪元的领航者
摘要 人工智能(AI)作为当今科技领域最具变革性的力量之一,正以惊人的速度重塑着我们的世界。本文旨在全面且专业地介绍人工智能,涵盖其定义、发展历程、关键技术、应用领域、面临的挑战以及未来展望等方面,以期为读者…...
c3p0、Druid连接池+工具类 Apache-DbUtils (详解!!!)
数据库连接池是在应用程序启动时创建一定数量的数据库连接,并将这些连接存储在池中。当应用程序需要与数据库通信时,它可以向池中请求一个连接,使用完后将连接归还给池,而不是关闭连接。这样可以减少创建和关闭连接的开销…...
鸿蒙开发深入浅出03(封装通用LazyForEach实现懒加载)
鸿蒙开发深入浅出03(封装通用LazyForEach实现懒加载) 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 类型的数据
问题: 通过 Redshift Spectrum 功能可以读取 S3 中的文件,当读取 Parquet 文件时,如果列格式设置为 timestamp, 通过 psql 客户端读取会出现以下错误: 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两种,两种桌面的安装方式我都会写,…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
