【数据结构原理与应用（Golang描述）】① 数组

                                                  .-.          .- 
                             .-,.--..-,.--.        \ \        / / 
                        __   |  .-. |  .-. |   __   \ \      / /  
                     .:--.'. | |  | | |  | |.:--.'.  \ \    / /   
                    / |   \ || |  | | |  | / |   \ |  \ \  / /    
                    `" __ | || |  '-| |  '-`" __ | |   \ `  /     
                     .'.''| || |    | |     .'.''| |    \  /      
                    / /   | || |    | |    / /   | |_   / /       
                    \ \._,\ '|_|    |_|    \ \._,\ '|`-' /        
                     `--'  `"               `--'  `" '..'   

Golang
Online Go tutorial

1.1 原理

数组（Array）是一种线性表数据结构，通过在内存中申请一组连续的存储空间，用于存储一系列具有相同类型的数据。

而除了数组，链表、栈、队列都是线性表结构。

根据下标实现随机访问

计算机会给每个内存单元分配一个地址，然后通过这个地址来访问内存中的数据，访问数组中的元素时候，会根据如下寻址公式来访问：

$$ a[i]\_address = base\_address i * data\_type\_size $$

其中 $a[i]\_address$ 表示a[i]的地址，$base\_address$ 表示计算机分配的数组的地址，$data\_type\_size$表示数组中每个元素的大小，如果数据类型是整型int，那么 $data\_type\_size$ 就等于4字节。

1.2 相关操作与分析

插入

如果需要将一个数据插入到数组的第k个位置，就需要将数组中k~n位置这部分的元素往后挪。

• 如果在数组末尾插入元素，就不需要移动数据，最好时间复杂度为 $O(1)$
• 如果在数组头部插入元素，就需要搬移整个数组，最坏时间复杂度为 $O(n)$
• 假设我们在数组的每个位置插入元素的概率是一样的，则平均时间复杂度为 $(1 2 ...n)/n = O(n)$

删除

与插入数据类似

• 最好情况时间复杂度为 $O(1)$
• 最坏情况时间复杂度为 $O(n)$
• 平均情况时间复杂度为 $O(n)$

1.3 思考

1. 为什么大多数编程语言中的数据要从0开始编号，而不是从1开始？
2. 数组与链表的区别？
3. 在编程中直接使用数组还是使用编程语言提供的容器类（如Java中的ArrayList、C STL中从Vector），容器类有哪些优劣呢？
4. *了解JVM中的标记清除垃圾回收算法原理与数组的关系？
5. *散列表的原理，散列表的查询时间复杂度？

1.4 LeetCode练习

1. 两数之和
2. 三数之和
3. 下一个排列
4. 螺旋矩阵

1.5 简单实现

package main

import "fmt"

type Array interface {
    Get(i int) interface{}
    Set(i int, element interface{})
    Len() int
    Remove(i int)
    Insert(i int, element interface{})

    // 辅助测试，打印
    Print()
}

type array struct {
    data []interface{}
}

func (a *array) Print() {
    fmt.Println(a.data)
}

func (a *array) Get(i int) interface{} {
    return a.data[i]
}

func (a *array) Set(i int, element interface{}) {
    a.data[i] = element
}

func (a *array) Len() int {
    return len(a.data)
}

func (a *array) Remove(i int) {
    for ; i < a.Len() - 1; i   {
        a.data[i] = a.data[i 1]
    }
    a.data = a.data[:a.Len()-1]
}

func (a *array) Insert(i int, element interface{}) {
    a.data = append(a.data, 0)
    for j:= a.Len()-1; j > i; j-- {
        a.data[j] = a.data[j-1]
    }
    a.data[i] = element
}

func NewArray(n int) Array {
    return &array{data: make([]interface{}, n)}
}

func main() {
    // 创建数组
    arr := NewArray(3)
    arr.Set(0, "hello")
    arr.Set(1, "world")

    fmt.Println(arr.Get(0))
    arr.Print()

    arr.Insert(0, "mike")
    arr.Print()

    arr.Remove(3)
    arr.Print()

}

到此这篇关于“【数据结构原理与应用（Golang描述）】① 数组”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
【数据结构原理与应用（Golang描述）】① 数组
Golang中interface内部构造与面试真题分析
数据结构和算法(Golang实现)(28)查找算法-AVL树
数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
学习golang开始前的准备工作
golang基础教程
Golang基础第五篇——golang的gRPC
golang 结构体断言_Golang中的reflect原理
golang 大数据平台_从数据仓库到大数据平台再到数据中台
11.深入理解切片(slice)