手撸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.002s

IArray.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)