现代农业建设 乡网站,北京免费建网站,快速建设企业门户网站,建手机网站一年费用前言
块状链表是介于链表和数组之间的数据结构#xff0c;能够在 O ( n ) O(\sqrt{n}) O(n )时间内完成插入、删除、访问操作。
数据结构如图所示。假设最大容量为 n n n, 则它有一个长度为 s n s\sqrt{n} sn 的链表。链表中每个结点是一个长度为 2 n 2 \times \sqrt{…前言
块状链表是介于链表和数组之间的数据结构能够在 O ( n ) O(\sqrt{n}) O(n )时间内完成插入、删除、访问操作。
数据结构如图所示。假设最大容量为 n n n, 则它有一个长度为 s n s\sqrt{n} sn 的链表。链表中每个结点是一个长度为 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 (fmtmath
)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.sizepos1 {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[jthis.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.sizepos {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.sizepos {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.sizepos {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()
