数据结构——静态链表
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ÿ…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
