数据结构——静态链表
1.定义:
(1)单链表:各个结点散落在内存中的各个角落,每个结点有指向下一个节点的指针(下一个结点在内存 中的地址);
(2)静态链表:用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间,各个结点集中安置,包括了——数据元素and下一个结点的数组下标(游标)
其中数组下标为0的结点充当"头结点"
游标为-1表示已经到达表尾
若每个数据元素为4B,每个游标为4B,则每个结点共8B;假设起始地址为addr,则数据下标为2的存放地址为:addr+8*2
注意: 数组下标——物理顺序,位序——逻辑顺序; 优点:增、删操作不需要大量移动元素;
缺点:不能随机存取,只能从头结点开始依次往后查找,容量固定不变!
2.静态链表用代码表示:
也可以这样:

也等同于:

注意:SLinkList a 强调a是静态链表;struct Node a 强调a是一个Node型数组;
3.静态链表基本操作的实现
(1)初始化静态链表:把a[0]的next设为-1
void InitList(StaticLinkedList *list) {
list->head = -1; // 设置头节点的next为-1表示空链表
list->size = 0;
// 初始化所有节点为未使用状态,通常将next设置为下一个节点的索引表示空闲
for (int i = 0; i < MAXSIZE - 1; i++) {
list->nodes[i].next = i + 1;
}
list->nodes[MAXSIZE - 1].next = -1; // 最后一个节点的next设置为-1
}
(2)查找某个位序(不是数组下标,位序是各个结点在逻辑上的顺序)的结点:从头结点出发挨个往后遍历结点,时间复杂度O=(n)
Index FindByPosition(StaticLinkedList *list, int position) {
if (position < 0 || position >= list->size) {
return -1; // 位序无效
}
int curPosition = 0;
Index currentIndex = list->head;
while (currentIndex != -1 && curPosition < position) {
currentIndex = list->nodes[currentIndex].next;
curPosition++;
}
return currentIndex;
}
(3)在位序为i上插入结点:① 找到一个空的结点,存入数据元素;② 从头结点出发找到位序为i-1的结点;③修改新结点的next;④ 修改i-1号结点的next;
void Insert(StaticLinkedList *list, ElementType element, int position) {
if (position < 0 || position > list->size) {
return; // 位序无效
}
// 找到一个空闲节点用于插入新元素
Index newNodeIndex = list->nodes[0].next;
if (newNodeIndex != -1) { // 确保还有空闲节点
list->nodes[0].next = list->nodes[newNodeIndex].next;
list->nodes[newNodeIndex].data = element; // 存储数据
if (position == 0) { // 如果是在头部插入
list->nodes[newNodeIndex].next = list->head; // 新节点指向原头节点
list->head = newNodeIndex; // 头节点更新为新节点
} else {
Index prevNodeIndex = FindByPosition(list, position - 1); // 找到前一个节点
list->nodes[newNodeIndex].next = list->nodes[prevNodeIndex].next; // 新节点指向前节点的下一节点
list->nodes[prevNodeIndex].next = newNodeIndex; // 前节点指向新节点
}
list->size++;
}
}
(4)删除某个结点:① 从头结点出发找到前驱结点;② 修改前驱节点的游标;③ 被删除节点next设为-2;
4.学习总结:
静态链表使用数组模拟链表,每个元素包含数据和游标(下一个节点的索引)。
初始化时需设置一个头节点,并将所有节点串联起来作为一个空闲节点列表。
查找时需要遍历链表直到达到指定位置。这个操作的时间复杂度为O(n)。
插入操作包括寻找空闲节点、连接与前一个节点以及更新链表大小。
静态链表的操作相较于动态链表来说更为复杂,但是在没有动态内存分配的环境下很有用。
在实践中,应用静态链表需要仔细管理空闲节点列表,避免内存的浪费和碎片化。
静态链表虽然不如动态链表灵活,但在某些限制内存的场景下可能非常有用。
相关文章:
数据结构——静态链表
1.定义: (1)单链表:各个结点散落在内存中的各个角落,每个结点有指向下一个节点的指针(下一个结点在内存 中的地址); (2)静态链表:用数组的方式来描述线性表的链式存储结构: 分配一…...
C++ 知识列表【图】
举例C的设计模式和智能指针 当谈到 C 的设计模式时,以下是一些常见的设计模式: 工厂模式(Factory Pattern):用于创建对象的模式,隐藏了对象的具体实现细节,只暴露一个公共接口来创建对象。 单例…...
系统登录的时候的密码如何做到以加密的形式进行登录【java.security包下的api】工具类。
/** description: 将普通的publicKey转化得到一个RSAPublicKey* author: zkw* date: 2024/1/24 16:17* param: publicKey 普通的publicKey* return: RSAPublicKey 得到一个新的RSAPublicKey**/public static RSAPublicKey getPublicKey(String publicKey) throws NoSuchAlgorit…...
java基础学习: 什么是泛型的类型擦除
文章目录 一、什么是泛型2、泛型编译前和编译后对比3、泛型的优点(1)提高了代码的复用性和可读性(2)提高了代码的安全性 二、泛型的定义1、泛型类2、泛型接口3、泛型方法 三、泛型通配符1、?和T有什么区别2、通配符的分…...
Vue+OpenLayers7入门到实战:在地图上添加缩放控件、比例尺控件和鼠标经纬度位置显示控件
返回《Vue+OpenLayers7》专栏目录:Vue+OpenLayers7 前言 本章主要介绍如何使用OpenLayers7在地图上添加地图缩放控件,比例尺显示控件和鼠标经纬度位置展示控件这三个Control控件。 二、依赖和使用 "ol": "7.5.2"使用npm安装依赖npm install ol@7.5.…...
极简生活|可以慢慢变富的8个习惯
哈喽,大家好啊,我是雷工! 巴菲特巴老爷子曾经多次指出: 大多数投资者的问题就在于不愿意慢慢变富。 可是大多数人都急于一夜暴富,于是乎那么多的追涨杀跌,不断上演,越急功近利反而越损失惨重。 …...
MySQL基础(一)
学习数据库的目的: 实现数据持久化到本地。使用完整的管理系统统一管理,可以实现结构化查询,方便管理。 一、数据库概述 数据库(DataBase) 为了方便数据的存储和管理,它将数据按照特定的 规则存储在磁盘…...
【Linux编译器-gcc/g++使用】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 设计样例,先见一下 方案一: 方案二: 在企业里面一般维护软件的源代码的话,要维护几份? 方案一&…...
SQL提示与索引终章
✨博客主页:小小恶斯法克的博客 🎈该系列文章专栏:重拾MySQL-进阶篇 📜 感谢大家的关注! ❤️ 可以关注黑马IT,进行学习 目录 🚀SQL提示 🚀覆盖索引 🚀前缀索引 &…...
基于OpenSSL的SSL/TLS加密套件全解析
概述 SSL/TLS握手时,客户端与服务端协商加密套件是很重要的一个步骤,协商出加密套件后才能继续完成后续的握手和加密通信。而现在SSL/TLS协议通信的实现,基本都是通过OpenSSL开源库,本文章就主要介绍下加密套件的含义以及如何在O…...
01-echarts如何绘制三维折线图
echarts如何绘制三维折线图 一、相关依赖包1、下载依赖2、引入依赖 二、创建图表盒子1、创建盒子2、定义数据3、编写方法1、初始化盒子2、设置配置项3、修改数据格式4、设置颜色数组4、设置name数组5、设置线三维和点三维6、添加配置项7、设置图表自适应 4、调用方法 三、整体代…...
Linux-共享内存
文章目录 前言一、system V共享内存申请共享内存挂载共享内存删除共享内存挂载删除共享内存 二、示例代码三.运行效果 前言 在这之前我们已经学习了两种进程间通信方式:匿名管道和命名管道。 从我们之前的学习已经知道,想让多个进程间进行通信就需要让他…...
深入分析 Linux 网络丢包问题
热门IT课程【视频教程】-华为/思科/红帽/oraclehttps://xmws-it.blog.csdn.net/article/details/134398330 所谓丢包,是指在网络数据的收发过程中,由于种种原因,数据包还没传输到应用程序中,就被丢弃了。这些被丢弃包的数量&#…...
web安全学习笔记【08】——算法1
思维导图在最后 #知识点: 1、Web常规-系统&中间件&数据库&源码等 2、Web其他-前后端&软件&Docker&分配站等 3、Web拓展-CDN&WAF&OSS&反向&负载均衡等 ----------------------------------- 1、APP架构-封装&原生态&…...
2024最新版Python 3.12.1安装使用指南
2024最新版Python 3.12.1安装使用指南 Installation and Configuration Guide to the latest version Python 3.12.1 in 2024 By Jackson Python编程语言,已经成为全球最受欢迎的编程语言之一;它简单易学易用,以标准库和功能强大且广泛外挂…...
Oracle 经典练习题 50 题
文章目录 一 CreateTable二 练习题1 查询"01"课程比"02"课程成绩高的学生的信息及课程分数2 查询"01"课程比"02"课程成绩低的学生的信息及课程分数3 查询平均成绩大于等于60分的同学的学生编号和学生姓名和平均成绩4 查询平均成绩小于…...
PyTorch的衍生资源
PyTorch作为深度学习领域的一个重要框架,自2016年首次发布以来经历了显著的发展。以下是PyTorch发展过程中的几个关键里程碑事件: 2016年: PyTorch于2016年首次发布,作为一个基于动态计算图的开源机器学习库,它提供了自…...
开源项目Git Commit规范与ChangeLog
一,conventional commit(约定式提交) Conventional Commits 是一种用于给提交信息增加人机可读含义的规范。它提供了一组用于创建清晰的提交历史的简单规则。 1.1 作用 自动化生成 CHANGELOG基于提交类型,自动决定语义化的版本变更向项目相关合作开发…...
【原理图PCB专题】OrCAD Capture CIS关闭开始界面
17.4版本 在打开OrCAD Capture CIS时会发现打开Start Page页面,那么如何将他关闭再也不看这个界面呢? 在窗口中输入SetOptionBool EnableStartPage 0 回车 重启软件后就再也不会弹出Start Page页面 如果没有发现Command Window那么将菜单栏view->C…...
【Linux】Ubuntu的gnome切换KDE Plasma
文章目录 安装KDE Plasma桌面环境添加软件源并更新apt安装kubuntu-desktop(作者没有成功)aptitude安装kubuntu-desktop多次aptitude install(特别重要特别重要)其他kde软件包 卸载gnome桌面 Ubuntu自带的桌面环境是gnomeÿ…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
