本文介绍: 因为数组大小是固定的,当数据元素特别多时,固定的数组无法储存这么多的值,所以可变数组出现了,这也是一种数据结构这里使用切片的部分功能来代替数组,虽然切片本身是可变长数组,但是我们不会用到它的。首先添加一个元素到可变长数组里,会加锁,这样会保证并发安全。每次可以初始化一个固定容量的切片,切片内部维护一个固定大小的数组。时,表明位置都用完了,没有多余的空间放新值,那么会创建一个固定大小。实现一个简单得,存放整数的,可变长得数组版本。,那么新的容量会是从 1 开始。功能,只把它当数组用。

三、可变长数组

因为数组大小是固定的,当数据元素特别多时,固定的数组无法储存这么多的值,所以可变长数组出现了,这也是一种数据结构。在 Golang语言中,可变长数组被内置在语言里面:切片 slice

slice 是对底层数组的抽象控制。它是一个结构体:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
  1. 指向底层数组的指针。( Golang 语言是没有操作原始内存指针的,所以 unsafe 包提供相关的对内存指针操作,一般情况下非专业人员勿用)
  2. 切片的真正长度,也就是实际元素占用的大小。
  3. 切片的容量,底层固定数组的长度

每次可以初始化一个固定容量的切片,切片内部维护一个固定大小的数组。当 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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注