手撸golang 根本数据结构与算法 数组
缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
数组
数组是一种线性数据结构,数据按顺序存储在内存的间断空间内。每个数据的内存地址（在内存上的地位）都能够通过数组下标算出，咱们也就能够借此间接拜访指标数据（这叫作“随机拜访”）。拜访数据时应用的是随机拜访（通过下标可计算出内存地址），所以须要的运行工夫仅为恒定的O(1)。但另一方面，想要向数组中增加新数据时，必须把指标地位前面的数据一个个移开。所以，如果在数组头部增加数据，就须要O(n)的工夫。删除操作同理。摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)指标
- golang自带数组和slice, 但操作方法不够OO, 本练习拟创立更OO的数组接口和办法
设计
- IArray: 定义数组的接口
- IArrayIterator: 定义数组的迭代器
- tCustomArray: 数组的OO封装, 实现IArray接口
- tArrayIterator: 数组迭代器, 实现IArrayIterator接口
单元测试
array_test.go
package data_structureimport ( "learning/gooop/data_structure/array" "testing")func Test_Array(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } } it := array.NewArray() t.Log(it.String()) fnAssertTrue(it.String() == "[]", "expecting []") it.Append(1) t.Log(it.String()) fnAssertTrue(it.String() == "[1]", "expecting [1]") e := it.Remove(0) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[]", "expecting []") e = it.Insert(0, 1) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[1]", "expecting [1]") e = it.Insert(0, 0) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[0,1]", "expecting [0,1]") e = it.Insert(2, 2) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[0,1,2]", "expecting [0,1,2]") e = it.Set(0, 10) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[10,1,2]", "expecting [10,1,2]") e = it.Set(2, 20) t.Log(it.String()) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it.String() == "[10,1,20]", "expecting [10,1,20]") e,x := it.Get(0) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(x == 10, "expecting 10") e,x = it.Get(2) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(x == 20, "expecting 20") e,_ = it.Get(3) fnAssertTrue(e != nil, "expecting e != nil") e,_ = it.Get(-1) fnAssertTrue(e != nil, "expecting e != nil")}测试输入
$ go test -v array_test.go === RUN Test_Array array_test.go:16: [] array_test.go:20: [1] array_test.go:24: [] array_test.go:29: [1] array_test.go:34: [0,1] array_test.go:39: [0,1,2] array_test.go:44: [10,1,2] array_test.go:49: [10,1,20]--- PASS: Test_Array (0.00s)PASSok command-line-arguments 0.002sIArray.go
定义数组的接口
package arraytype IArray interface { Size() int IsEmpty() bool IsNotEmpty() bool Get(i int) (error,interface{}) Set(i int, it interface{}) error Append(it interface{}) Remove(i int) error Insert(i int, it interface{}) error Iterator() IArrayIterator String() string}IArrayIterator.go
定义数组的迭代器
package arraytype IArrayIterator interface { More() bool Next() (error,interface{})}tCustomArray.go
数组的OO封装, 实现IArray接口
package arrayimport ( "errors" "fmt" "strings")type tCustomArray struct { items []interface{} size int}var gIndexOutofBoundsError = errors.New("index out of bounds")func NewArray() IArray { return &tCustomArray{ items: make([]interface{}, 0), size: 0, }}func (me *tCustomArray) Size() int { return me.size}func (me *tCustomArray) IsEmpty() bool { return me.size <= 0}func (me *tCustomArray) IsNotEmpty() bool { return !me.IsEmpty()}func (me *tCustomArray) Get(i int) (error,interface{}) { if i >= me.size || i < 0 { return gIndexOutofBoundsError, nil } return nil, me.items[i]}func (me *tCustomArray) Set(i int, it interface{}) error { if i >= me.size || i < 0 { return gIndexOutofBoundsError } me.items[i] = it return nil}func (me *tCustomArray) Append(it interface{}) { me.items = append(me.items, it) me.size++}func (me *tCustomArray) Remove(i int) error { if i >= me.size || i < 0 { return gIndexOutofBoundsError } me.items = append(me.items[:i], me.items[i+1:]...) me.size-- return nil}func (me *tCustomArray) Insert(i int, it interface{}) error { if i > me.size || i < 0 { return gIndexOutofBoundsError } newItems := make([]interface{}, 0) newItems = append(newItems, me.items[:i]...) newItems = append(newItems, it) newItems = append(newItems, me.items[i:]...) me.items = newItems me.size++ return nil}func (me *tCustomArray) Iterator() IArrayIterator { return newArrayIterator(me.items)}func (me *tCustomArray) String() string { ss := make([]string, me.size) for i,it := range me.items { ss[i] = fmt.Sprintf("%v", it) } return fmt.Sprintf("[%s]", strings.Join(ss, ","))}tArrayIterator.go
数组迭代器, 实现IArrayIterator接口
package arraytype tArrayIterator struct { items []interface{} count int pos int}func newArrayIterator(items []interface{}) IArrayIterator { size := len(items) copy := make([]interface{}, size) for i,it := range items { copy[i] = it } return &tArrayIterator{ items: copy, count: size, pos: 0, }}func (me *tArrayIterator) More() bool { return me.pos < me.count}func (me *tArrayIterator) Next() (error,interface{}) { if me.pos >= me.count { return gIndexOutofBoundsError, nil } n := me.pos me.pos++ return nil, me.items[n]}(end)