数组

发表于 | 分类于 | 阅读次数：

简述

有限个相同数据类型的元素按顺序排列的集合为数组。

数组的数据是连续的，有边界，其中的元素都有属于自己的索引值，即下标，通过这些下标就能定位到值。

示例：将 "the","monster","is","coming" 四个字符串放到数组中，找数组的下标为 0 和 3 保存的字符串。

Coding

  • 实现一个支持动态扩容的数组
  • 实现一个大小固定的有序数组，支持动态增、删、查操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package array

import (
	"errors"
	"fmt"
)

/**
* 1) 数组的插入、删除、按照下标随机访问操作；
* 2）数组中的数据是int类型的；
*
* Author: Rao
 */
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, value 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] = value
	this.length ++
	return nil
}

func (this *Array) InsertToTail(value int) error {
	return this.Insert(this.Len(), value)
}

// 删除索引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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package array

import (
	"testing"
)

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

	arr.Print()

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

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

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

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

func TestFind(t *testing.T) {
	capacity := 10
	arr := NewArray(uint(capacity))
	for i := 0; i < capacity; i++ {
		err := arr.Insert(uint(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))
}