数组的随机访问

什么是数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来储存一组具有相同类型的数据

这其中有几个比较重要的关键字：线性表，连续的，相同类型

什么是线性表呢

顾名思义，线性表就是数据排成一条线一样的结构。每一个线性表上的数据都只有前后两个方向，数组，链表，队列，栈都是线性表

为什么是连续并且要相同的类型呢

其实就是因为有这两个限制，才让数组有了随机访问的特性，但是也会有弊端，这两个限制让数组很多的操作变得很低效，如果想给数组中添加元素，或者删除元素，为了保护数组的连续性，我们需要做大量的数据搬移工作

随机访问

我们这里简单的说一下数组的随机访问的实现原理（寻址公式）

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。在我画的这个图中，计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。

在数组申明的时候，计算机会给每个元素分配一个地址，并且数组中的每一个元素的类型都一样，那么只要我们知道了首地址和访问下标，我们就能很快的通过计算来找到对应的地址。下面的公式就是数组的寻址公式：

1	a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。这个公式非常简单，我就不多做解释了。

为什么数组的下标需要从零开始

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：

1	a[k]_address = base_address + k * type_size

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：

1	a[k]_address = base_address + (k-1)*type_size

我们会发现，当从1开始时，计算机会多做一个减法操作，数组作为一个非常基础的数据结构，通过下表来随机访问又是其最基础的特性，那么它的效率优化就要尽可能的做到最好。

容器

这里的所说的容器并不是docker这种，而是值得是数组的包装类，类似java中的ArrayList，golang中的切片，他们都是对数组进行了二次封装

使用这种容器的时候因为其对数组进行了很多封装，所以你在使用的时候不用太过于关注底层的逻辑。

golang实现容器

package _5_array

import (
	"errors"
	"fmt"
)

/**
 * 1) 数组的插入、删除、按照下标随机访问操作；
 * 2）数组中的数据是int类型的；
 *
 * Author: leo
 */
type Array struct {
	data   []int
	length uint
}
//为数组初始化内存
func NewArray(capacity uint) *Array {
	if capacity == 0 {
		return nil
	}
	return &Array{
		data:   make([]int, capacity, capacity),
		length: 0,
	}
}
func (this *Array) Len() uint {
	return this.length
}
//判断索引是否越界
func (this *Array) isIndexOutOfRange(index uint) bool {
	if index >= uint(cap(this.data)) {
		return true
	}
	return false
}
//通过索引查找数组，索引范围[0,n-1]
func (this *Array) Find(index uint) (int, error) {
	if this.isIndexOutOfRange(index) {
		return 0, errors.New("out of index range")
	}
	return this.data[index], nil
}
//插入数值到索引index上
func (this *Array) Insert(index uint, v int) error {
	if this.Len() == uint(cap(this.data)) {
		return errors.New("full array")
	}
	if index != this.length && this.isIndexOutOfRange(index) {
		return errors.New("out of index range")
	}

	for i := this.length; i > index; i-- {
		this.data[i] = this.data[i-1]
	}
	this.data[index] = v
	this.length++
	return nil
}
func (this *Array) InsertToTail(v int) error {
	return this.Insert(this.Len(), v)
}

//删除索引index上的值
func (this *Array) Delete(index uint) (int, error) {
	if this.isIndexOutOfRange(index) {
		return 0, errors.New("out of index range")
	}
	v := this.data[index]
	for i := index; i < this.Len()-1; i++ {
		this.data[i] = this.data[i+1]
	}
	this.length--
	return v, nil
}

//打印数列
func (this *Array) Print() {
	var format string
	for i := uint(0); i < this.Len(); i++ {
		format += fmt.Sprintf("|%+v", this.data[i])
	}
	fmt.Println(format)
}