数据结构——静态链表
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ÿ…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
