2
手撸golang 基本数据结构与算法 数组
source link: https://studygolang.com/articles/33335
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
手撸golang 基本数据结构与算法 数组
缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉;宫崎修一)
本系列笔记拟采用golang练习之
数组
数组是一种线性数据结构, 数据按顺序存储在内存的连续空间内。 每个数据的内存地址(在内存上的位置)都可以通过数组下标算出, 我们也就可以借此直接访问目标数据(这叫作“随机访问”)。 访问数据时使用的是随机访问(通过下标可计算出内存地址), 所以需要的运行时间仅为恒定的O(1)。 但另一方面,想要向数组中添加新数据时,必须把目标位置后面的数据一个个移开。 所以,如果在数组头部添加数据,就需要O(n)的时间。 删除操作同理。 摘自 <<我的第一本算法书>>(【日】石田保辉;宫崎修一)
目标
- golang自带数组和slice, 但操作方法不够OO, 本练习拟创建更OO的数组接口和方法
设计
- IArray: 定义数组的接口
- IArrayIterator: 定义数组的迭代器
- tCustomArray: 数组的OO封装, 实现IArray接口
- tArrayIterator: 数组迭代器, 实现IArrayIterator接口
单元测试
array_test.go
package data_structure import ( "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) PASS ok command-line-arguments 0.002s
IArray.go
定义数组的接口
package array type 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 array type IArrayIterator interface { More() bool Next() (error,interface{}) }
tCustomArray.go
数组的OO封装, 实现IArray接口
package array import ( "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 array type 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)
有疑问加站长微信联系(非本文作者)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK