三、可变长数组
因为数组大小是固定的,当数据元素特别多时,固定的数组无法储存这么多的值,所以可变长数组出现了,这也是一种数据结构。在 Golang
语言中,可变长数组被内置在语言里面:切片 slice
。
type slice struct {
array unsafe.Pointer
len int
cap int
}
- 指向底层数组的指针。(
Golang
语言是没有操作原始内存的指针的,所以unsafe
包提供相关的对内存指针的操作,一般情况下非专业人员勿用) - 切片的真正长度,也就是实际元素占用的大小。
- 切片的容量,底层固定数组的长度。
每次可以初始化一个固定容量的切片,切片内部维护一个固定大小的数组。当 append
新元素时,固定大小的数组不够时会自动扩容,如:
package main
import "fmt"
func main() {
// 创建一个容量为2的切片
array := make([]int, 0, 2)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
// 虽然 append 但是没有赋予原来的变量 array
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
fmt.Println("-------")
// 赋予回原来的变量
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1, 1, 1, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1, 1, 1, 1, 1, 1, 1, 1, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
}
1、实现可变长数组
这里会使用切片的部分功能来代替数组,虽然切片本身是可变长数组,但是我们不会用到它的 append
功能,只把它当数组用。
package main
import "sync"
// Array 定义可变常数组
type Array struct {
array []int //固定大小得数组,用切片来进行
len int
cap int
lock sync.Mutex
}
// 1.初始化数组
func make(len, cap int) *Array {
s := new(Array)
if len > cap {
panic("len large than cap")
}
//把切片当数组使用
array := make([]int, cap, cap)
//元数据
s.array = array
s.cap = cap
s.len = 0
return s
}
// Append 2.添加数组 方法(可以有指针类型,也有值类型)
func (a *Array) Append(element int) {
//并发锁
a.lock.Lock()
defer a.lock.Unlock()
//大小与容量相等,无为之进行多余增加
if a.len == a.cap {
//没有容量,那进行扩容吧
newCap := 2 * a.len
if a.cap == 0 {
newCap = 1
}
newArray := make([]int, newCap, newCap)
//newArray 将老数组的数据移动到新数组上
for k, v := range a.array {
newArray[k] = v
}
//替换数组
a.array = newArray
a.cap = newCap
}
//将元素放入新数组
a.array[a.len] = element
//并且长度+1
a.len += 1
}
// 1.3获取指定下表的元素
// Get 获取某个下标的元素
func (a *Array) Get(index int) int {
//讨论越界
if a.len == 0 || index >= a.len {
panic("index over len")
}
return a.array[index]
}
//1.4获取真实长度和容量
//Len 返回真实长度
func (a *Array)Len()int {
return a.len
}
//Cap 返回容量
func (a *Array)Cap() int{
return a.cap
}
func main() {
}
解释如下:
1.对于添加元素:
首先添加一个元素到可变长数组里,会加锁,这样会保证并发安全。然后将值放在数组里:a.array[a.len] = element
,然后 len + 1
,表示真实大小又多了一个。
当真实大小 len = cap
时,表明位置都用完了,没有多余的空间放新值,那么会创建一个固定大小 2*len
的新数组来替换老数组:a.array = newArray
,当然容量也会变大:a.cap = newCap
。如果一开始设置的容量 cap = 0
,那么新的容量会是从 1 开始。
添加元素中,耗时主要在老数组中的数据移动到新数组,时间复杂度为:O(n)
。当然,如果容量够的情况下,时间复杂度会变为:O(1)
。
补充添加多个元素:
// AppendMany 增加多个元素
func (a *Array) AppendMany(element ...int) {
for _, v := range element {
a.Append(v)
}
}
原文地址:https://blog.csdn.net/zhangzhongyanting/article/details/130559604
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_11103.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!