【Go数据结构】数组 Array

数组 Array

元素在内存中连续存放。每个元素占用内存相同，可通过下标算出元素位置快速访问

优点：访问快 O(1)
缺点：增加、删除元素需要移动大量元素，慢 O(N)
场景：快速访问元素，很少插入和删除元素

基本实现：

ADT:
    线性表List
Data:
    线性表的数据对象集合为{a1,a2,...,an},每个元素类型为DataType。除了第一个无前驱，最后一个无后继，
    其他每个元素都有一个字节前驱和直接后继结点。数据元素间关系一对一。
Operation:
    InitList(*L);//初始线性表,创建空表
    ClearList(*L);//清空线性表数据
    ListEmpty(L);//判断列表是否为空
    ListLength(L);//获取线性表的长度
    GetElem(L,i,* e);//获取指定位置的元素，返回在指针元素中
    LocateElem(L,e);//查找元素在线性表中的位置
    ListInsert(*L,i,e);//向线性表中指定位置插入元素
    ListDelete(*L, i, *e);//删除指定位置处的元素

优化：

添加一个字段，记录长度。
再添加一个字段，记录剩余长度。动态扩容，每次2倍。

实现细节

一定注意传入的index不能越界。

数组越界

数组越界：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
    	arr[i] = 0;
    	printf("hello world\n");
    }
    return 0;
}

a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址

那么 a[3]=0 就相当于 i=0

GO的实现：

package my_array

import (
	"errors"
	"fmt"
)


type Array struct {
	data   []int
	newData []int
	length int
	free int
}

//为数组初始化内存
func NewArray(capacity int) *Array {
	if capacity == 0 {
		return nil
	}
	return &Array{
		data:   make([]int, capacity, capacity),
		length: 0,
		free:capacity,
	}
}

func (this *Array) Len() int {
	return this.length
}

func (this *Array) Free() int   {
	return this.free
}

//判断索引是否越界
func (this *Array) isIndexOutOfRange(index int) bool {
	if index >= this.Len() {
		return true
	}
	return false
}

//通过索引查找数组，索引范围[0,n-1]
func (this *Array) Find(index int) (int, error) {
	if this.isIndexOutOfRange(index) {
		return 0, errors.New("out of index range")
	}
	return this.data[index], nil
}

func (this *Array)kuoRong()  {
	this.newData = make([]int,2*this.length)
	this.free = this.length

	for k,v :=range this.data  {
		this.newData[k] = v
	}
	this.data = make([]int,2*this.length)
	this.data = this.newData
}

//插入数值到索引index上
func (this *Array) Insert(index int, v int) error {
	if this.free == 0 {
		this.kuoRong()
		//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++
	this.free--
	return nil
}

//插入到尾端
func (this *Array) InsertToTail(v int) error {
	return this.Insert(this.Len(), v)
}

//删除索引index上的值
func (this *Array) Delete(index int) (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 := 0; i < this.Len(); i++ {
		format += fmt.Sprintf("|%+v", this.data[i])
	}
	fmt.Println(format)
}

测试：

package my_array

import (
   "fmt"
   "testing"
)

func TestInsert(t *testing.T) {
   capacity := 10
   arr := NewArray(int(capacity))
   for i := 0; i < capacity*20 +1; i++ {
      err := arr.Insert(int(i), i+1)
      if nil != err {
         t.Fatal(err.Error())
      }
   }
   arr.Print()

   len := arr.length
   fmt.Println(len)

   fmt.Println(arr.Free())
   // cap(arr.data)

   arr.Insert(int(6), 999)
   arr.Print()

   arr.InsertToTail(666)
   arr.Print()
}

func TestDelete(t *testing.T) {
   capacity := 10
   arr := NewArray(int(capacity))
   for i := 0; i < capacity; i++ {
      err := arr.Insert(int(i), i+1)
      if nil != err {
         t.Fatal(err.Error())
      }
   }
   arr.Print()

   for i := 9; i >= 0; i-- {
      _, err := arr.Delete(int(i))
      if nil != err {
         t.Fatal(err)
      }
      arr.Print()
   }
}

func TestFind(t *testing.T) {
   capacity := 10
   arr := NewArray(int(capacity))
   for i := 0; i < capacity; i++ {
      err := arr.Insert(int(i), i+1)
      if nil != err {
         t.Fatal(err.Error())
      }
   }
   arr.Print()

   t.Log(arr.Find(0))
   t.Log(arr.Find(9))
   t.Log(arr.Find(11))
}

【Go数据结构】数组 Array

数组 Array

数组越界

GO的实现：

推荐阅读