当前位置: 首页 > news >正文

块状链表实现BigString大字符串操作(golang)

前言

块状链表是介于链表和数组之间的数据结构,能够在 O ( n ) O(\sqrt{n}) O(n )时间内完成插入、删除、访问操作。

数据结构如图所示。假设最大容量为 n n n, 则它有一个长度为 s = n s=\sqrt{n} s=n 的链表。链表中每个结点是一个长度为 2 × n 2 \times \sqrt{n} 2×n 的数组。

参考:https://oi-wiki.org/ds/block-list/
在这里插入图片描述
实现时,有两个细节需要注意:

  • 初始时,只有一个链表结点。随着数据越来越多,当某个结点内数组装满后,将分裂成两个结点。

  • 删除数据后,如果数据所在结点为空,则需要删除结点(链表首元结点不用删除)。

本文以BigString为例进行实现。

实现

使用golang实现如下字符串功能:

  • Append(str) 向字符串尾部添加一个字符串
  • Size() 获取字符串长度
  • Insert(index, char) 向字符串某个位置插入一个字符
  • Erase(index) 删除某个位置的字符
  • At(index) 获了某个位置的字符
  • Set(index, char) 设置某个位置的字符
package mainimport ("fmt""math"
)type _Node struct {next *_Nodesize intdata []rune
}type BigString struct {head    *_Node // 没有哨兵,直接就是首元结点size    int    // 字符串大小bukSize int    // 分组大小maxSize int    // 最大字符大小
}func NewBigString(maxLen int) *BigString {if maxLen < 10 {maxLen = 10}// 计算分段长度s := int(math.Sqrt(float64(maxLen)))return &BigString{head:    &_Node{nil, 0, make([]rune, 2*s)},size:    0,bukSize: s,maxSize: maxLen,}
}func (this *BigString) String() string {var str stringfor node := this.head; node != nil; node = node.next {for i := 0; i < node.size; i++ {str += string(node.data[i])}}return str
}/*
*
在尾部插入字符
*/
func (this *BigString) Append(chars string) {for _, char := range chars {this.Insert(this.size, rune(char))}
}/*
*
在尾部插入字符
*/
func (this *BigString) Size() int {return this.size
}/*
*
在指定位置插入字符
*/
func (this *BigString) Insert(index int, char rune) {if this.size < this.maxSize && index >= 0 && index <= this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos+1 {insertPos := index - pos - 1 // 0 1 2 3 4 | 5 6 7   , index = 6,for j := node.size; j > insertPos; j-- {node.data[j] = node.data[j-1]}node.data[insertPos] = charnode.size++// 结点分裂开if node.size == len(node.data) {node2 := &_Node{node.next, this.bukSize, make([]rune, 2*this.bukSize)}for j := 0; j < this.bukSize; j++ {node2.data[j] = node.data[j+this.bukSize]}node.size -= this.bukSizenode.next = node2}break}pos += node.size}this.size++}
}/*
*
删除指定位置字符
*/
func (this *BigString) Erase(index int) {if index >= 0 && index < this.size {pos := -1var pre *_Node = nilfor node := this.head; node != nil; node = node.next {if index <= node.size+pos {deletePos := index - pos - 1for j := deletePos + 1; j < node.size; j++ {node.data[j-1] = node.data[j]}node.size--// 清理空结点if node.size == 0 {if node != this.head {pre.next = pre.next.next}}break}pos += node.sizepre = node}this.size--}
}/*
*
获取指定位置字符
*/
func (this *BigString) At(index int) rune {if index >= 0 && index < this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos {atPos := index - pos - 1return node.data[atPos]}pos += node.size}}return 0
}/*
*
设置指定位置字符
*/
func (this *BigString) Set(index int, char rune) {if index >= 0 && index < this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos {atPos := index - pos - 1node.data[atPos] = charbreak}pos += node.size}}
}

测试

测试结果与测试代码如下。结果表明实现是正确的。

在这里插入图片描述

str := NewBigString(225)// 测试 Append, Insert, Stringfmt.Println("【测试 Append, Insert, String】")str.Append("hello world! my name is cloudea. this is my first big string implementation!\n")str.Append("世界 你好! 我的我名字是克劳迪亚。这是我的第一个大字符串实现哦!\n")fmt.Println(str)str.Insert(0, '*')str.Insert(78, '#')fmt.Println(str)for i := 0; i < 40; i++ {str.Insert(100, '$')}fmt.Println(str)// 测试Erasefmt.Println("【测试 Erase】")for i := 0; i < 40; i++ {str.Erase(100)}fmt.Println(str)// 测试测试At 和 Setfmt.Println("【测试At 和 Set】")str.Set(99, '你')str.Set(100, '呀')str.Set(101, 'd')str.Set(102, '二')str.Set(103, '个')for i := 0; i < str.Size(); i++ {fmt.Print(string(str.At(i)))}fmt.Println()

相关文章:

块状链表实现BigString大字符串操作(golang)

前言 块状链表是介于链表和数组之间的数据结构&#xff0c;能够在 O ( n ) O(\sqrt{n}) O(n ​)时间内完成插入、删除、访问操作。 数据结构如图所示。假设最大容量为 n n n, 则它有一个长度为 s n s\sqrt{n} sn ​的链表。链表中每个结点是一个长度为 2 n 2 \times \sqrt{…...

项目问题记录(持续更新)

1.在 yarn install的时候报 error achrinza/node-ipc9.2.2: The engine "node" is incompatible with this module. Expected version "8 || 10 || 12 || 14 || 16 || 17". Got "20.1.0" error Found incompatible module.需要执行 yarn config…...

Linux的进程

目录 一、进程占用的内存资源 二、进程的系统环境 三、进程一直在切换 四、父进程和子进程 五、进程状态 六、查看进程 1.ps -ef 列出所有进程 2.ps -lax 列出所有进程 3.ps aux列出所有进程 4.树形列出所有进程 七、作业&#xff08;用来查看管理进程&#xff09; …...

与其焦虑被 AI 取代或猜测前端是否已死, 不如看看 vertical-align 扎实你的基础!!!

与其焦虑被 AI 取代或猜测前端是否已死, 不如看看 vertical-align 扎实你的基础!!! vertical-align 设置 display 值为 inline, inline-block 和 table-cell 的元素竖直对齐方式. 从 line-height: normal 究竟是多高说起 我们先来看一段代码, 分析一下为什么第二行的行高, 也就…...

路由、交换机、集线器、DNS服务器、广域网/局域网、端口、MTU

前言&#xff1a;网络名词术语解析(自行阅读扫盲)&#xff0c;推荐大家去读户根勤的《网络是怎样连接的》 路由(route)&#xff1a; 数据包从源地址到目的地址所经过的路径&#xff0c;由一系列路由节点组成。某个路由节点为数据包选择投递方向的选路过程。 路由器工作原理 路…...

在全志V851S开发板上进行屏幕触摸适配

1.修改屏幕驱动 从ft6236 &#xff08;删掉&#xff0c;不要保留&#xff09;&#xff0c;改为下面的 路径&#xff1a;/home/wells/tina-v853-open/tina-v853-open/device/config/chips/v851s/configs/lizard/board.dts&#xff08;注意路径&#xff0c;要设置为自己的实际路…...

字符串拷贝时的内存重叠问题

字符串拷贝时的内存重叠问题 1.什么是内存重叠 拷贝的目的地址在源地址的范围内&#xff0c;有重叠。 如在写程序的过程中&#xff0c;我们用到的strcpy这个拷贝函数&#xff0c;在这个函数中我们定义一个目的地址&#xff0c;一个源地址&#xff0c;在拷贝的过程中如果内存重…...

告别PPT手残党!这6款AI神器,让你秒变PPT王者!

如果你是一个PPT手残党&#xff0c;每每制作PPT总是让你焦头烂额&#xff0c;那么你一定需要这篇幽默拉风的推广文案&#xff01; 我向你保证&#xff0c;这篇文案将帮助你发现6款AI自动生成PPT的神器&#xff0c;让你告别PPT手残党的身份&#xff0c;成为一名PPT王者。 无论…...

JVM配置与优化

参考&#xff1a; JVM内存分区及作用&#xff08;JDK8&#xff09; https://blog.csdn.net/BigBug_500/article/details/104734957 java 进程占用系统内存过高分析 https://blog.csdn.net/fxh13579/article/details/104754340 Java之jvm和线程的内存 https://blog.csdn.ne…...

电力系统储能调峰、调频模型研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

C++基础之类、对象一(类的定义,作用域、this指针)

目录 面向对象的编程 类的引入 简介 类的定义 简介 访问限定符 命名规则 封装 简介 类的作用域 类的大小及存储模型 this指针 简介 面向对象的编程 C与C语言不同&#xff0c;C是面向对象的编程&#xff0c;那么什么是面向对象的编程呢&#xff1f; C语言编程&#xff0c;规定…...

javaScript---设计模式-封装与对象

目录 1、封装对象时的设计模式 2、基本结构与应用示例 2.1 工厂模式 2.2 建造者模式 2.3 单例模式 封装的目的&#xff1a;①定义变量不会污染外部&#xff1b;②能作为一个模块调用&#xff1b;③遵循开闭原则。 好的封装&#xff08;不可见、留接口&#xff09;&#xff1a;①…...

【消息中间件】kafka高性能设计之内存池

文章目录 前言实现创建内存池分配内存释放内存 总结 前言 Kafka的内存池是一个用于管理内存分配的缓存区域。它通过在内存上保留一块固定大小的内存池&#xff0c;用于分配消息缓存、批处理缓存等对象&#xff0c;以减少频繁调用内存分配函数的开销。 Kafka内存池的实现利用了…...

创建型模式——单例(singleton)

1. 模式说明 单例模式保证类只有一个实例&#xff1b;创建一个对象&#xff0c;当你创建第二个对象的时候&#xff0c;此时你获取到的是已经创建过的对象&#xff0c;而不是一个新的对象&#xff1b; 1.1 使用场景 共享资源的访问权限&#xff1b;任务的管理类&#xff1b;数…...

算法:迷宫问题

描述 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&#xff1a; int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只能横着走或…...

聊聊并发编程的12种业务场景

前言 并发编程是一项非常重要的技术&#xff0c;无论在面试&#xff0c;还是工作中出现的频率非常高。 并发编程说白了就是多线程编程&#xff0c;但多线程一定比单线程效率更高&#xff1f; 答&#xff1a;不一定&#xff0c;要看具体业务场景。 毕竟如果使用了多线程&…...

MySQL执行顺序

MySQL执行顺序 MySQL语句的执行顺序也是在面试过程中经常问到的问题&#xff0c;并且熟悉执行顺序也有助于SQL语句的编写。 SELECT FROM JOIN ON WHERE GROUP BY HAVING ORDER BY LIMIT执行顺序如下&#xff1a; FROM ON JOIN WHERE GROUP BY # (开始使用别名) SUM # SUM等…...

引领真无线耳机未来趋势,NANK南卡OE骨传导真无线耳机惊艳亮相

传统的蓝牙耳机存在很多问题&#xff0c;例如续航时间短、长期佩戴耳朵会不舒服&#xff0c;甚至影响听力等等。为了解决这些问题&#xff0c;在骨传导领域深耕十多年的南卡品牌推出了这款真无线骨传导耳机——NANK南卡 OE。 NANK南卡OE即将正式上线&#xff0c;这一消息一经宣…...

5款写作神器,帮助你写出5w+爆款文案,好用到哭

我不允许还有文案小白、新手博主不知道这5款写作利器&#xff01; 每次一写文案就头秃的新媒体工作者&#xff0c;赶紧看过来吧&#xff01;这5款好用到爆的写作神器&#xff0c;喝一杯咖啡的时间就能完成写作。 我和同事都是用它们&#xff0c;出了很多的爆款&#xff0c;现…...

相交链表问题

给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结果后&…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...