Golang数据结构 - 1 - 数组
2019-06-18 本文已影响0人
vouv
___ .______ .______ ___ ____ ____
/ \ | _ \ | _ \ / \ \ \ / /
/ ^ \ | |_) | | |_) | / ^ \ \ \/ /
/ /_\ \ | / | / / /_\ \ \_ _/
/ _____ \ | |\ \----.| |\ \----./ _____ \ | |
/__/ \__\ | _| `._____|| _| `._____/__/ \__\ |__|
几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。
在这里我们将用Go语言中的切片特性来实现数组的基本操作。
根据下标实现随机访问
计算机会给每个内存单元分配一个地址，然后通过这个地址来访问内存中的数据，访问数组中的元素时候，会根据如下寻址公式来访问：
其中 表示a[i]的地址，
表示计算机分配的数组的地址，
表示数组中每个元素的大小，如果数据类型是整型int，那么
就等于4字节。
数组类型定义
我们首先定义数组类型为Array, 同时定义数组中元素类型为Element。代码如下
// 数组定义
type Element interface {}
type Array []Element
创建数组
使用Go语言创建切片数组很简单，代码如下
arr := Array{1,2,3,4,5} // 1
arr := make(Array, 5) // 2
数组遍历
我们可以使用Go中for循环于range语法对数组进行遍历，代码如下
for i, v := range arr {
fmt.Printf("arr[%d]=%v\n",i, v)
}
添加元素
我们可以借助Go语言中append函数向切片添加任意元素，给数组添加元素主要有两种方式：
- 添加元素到数组末尾，这里通过Push方法实现
- 添加元素到数组开头，这里通过Uushift方法实现
在数组末尾添加元素实现
// 向末尾添加元素
func (arr *Array)Push(e... Element) {
*arr = append(*arr, e...)
}
在数组开头添加元素实现
// 向头部添加元素
func (arr *Array) Unshift(e... Element) {
*arr = append(e, *arr...)
}
删除数组中的元素
我们可以借助Go语言中切片取值删除数组中的元素主要有两种方式
- 删除数组末尾元素
- 删除数组开头元素
删除数组末尾元素实现
// 删除末尾元素
func (arr *Array) Pop() Element {
n := len(*arr)
if n == 0 {
return nil
}
// 获取末尾元素
v := (*arr)[n-1]
// 切片修改
*arr = (*arr)[:n-1]
return v
}
删除数组开头元素实现
// 删除数组开头元素
func (arr *Array) Shift() Element {
n := len(*arr)
if n == 0 {
return nil
}
// 获取第一个元素
v := (*arr)[0]
// 修改切片
*arr = (*arr)[1:]
return v
}
在数组中任意位置添加或删除元素
这里我们通过两种方式实现在数组中任意位置添加或删除元素：
- Insert方法，在数组任意位置插入元素
- Remove方法，删除数组任意位置的元素
在数组任意位置添加元素实现
// 任意位置插入元素
func (arr *Array) Insert(i int, e ...Element) {
n := len(*arr)
if i > n-1 {
return
}
// 构造需要插入元素的切片
inserts := Array{}
inserts = append(inserts, e...)
// 重新构造切片数组
result := Array{}
result = append(result, (*arr)[:i]...)
result = append(result, inserts...)
result = append(result, (*arr)[i:]...)
*arr = result
}
在数组任意位置删除元素实现
// 删除任意位置元素
func (arr *Array) Remove(i int) {
n := len(*arr)
if i > n-1 {
return
}
*arr = append((*arr)[:i], (*arr)[i+1:]...)
}
数组合并
// 数组合并
func (arr *Array) Concat(next Array) {
*arr = append(*arr, next...)
}
迭代器函数
迭代器通过遍历数组中元素并执行传入函数来实现数组的迭代
// 迭代器
func (arr *Array) ForEach(f func(e Element)) {
for _, v := range *arr {
f(v)
}
}
过滤器
过滤器方法接收一个函数作为参数，对数组的元素逐个执行，函数的返回值为bool，将决定是否保留元素，最终返回过滤函数筛选的值。
// 过滤器
func (arr *Array) Filter(f func(element Element) bool) Array {
result := Array{}
for _, v := range *arr {
if f(v) {
result = append(result, v)
}
}
return result
}
排序
这里实现了一个简单的快排
// 排序
func (arr *Array) Sort(cmp func(a, b Element) int) {
ln := len(*arr)
if ln < 2 {
return
}
p := (*arr)[0]
i, j := 1, ln-1
for {
for i < j && cmp((*arr)[i], p) < 0 {
i++
}
for cmp((*arr)[j], p) > 0 {
j--
}
if i >= j {
break
}
(*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
}
// 交换
(*arr)[0], (*arr)[j] = (*arr)[j], (*arr)[0]
left := (*arr)[:j]
left.Sort(cmp)
right := (*arr)[j+1:]
right.Sort(cmp)
*arr = append(append(left, p), right...)
}
搜索
这里实现了一个根据元素值搜索索引位置的方法
// 搜索
func (arr *Array) IndexOf(e Element) int {
for i, v := range *arr {
if v == e {
return i
}
}
return -1
}
完整代码示例
package main
import (
"fmt"
)
// 数组定义
type Element interface{}
type Array []Element
// 向末尾添加元素
func (arr *Array) Push(e ...Element) {
*arr = append(*arr, e...)
}
// 向头部添加元素
func (arr *Array) Unshift(e ...Element) {
*arr = append(e, *arr...)
}
// 删除末尾元素
func (arr *Array) Pop() Element {
n := len(*arr)
if n == 0 {
return nil
}
// 获取末尾元素
v := (*arr)[n-1]
// 切片修改
*arr = (*arr)[:n-1]
return v
}
// 删除数组开头元素
func (arr *Array) Shift() Element {
n := len(*arr)
if n == 0 {
return nil
}
// 获取第一个元素
v := (*arr)[0]
// 修改切片
*arr = (*arr)[1:]
return v
}
// 任意位置插入元素
func (arr *Array) Insert(i int, e ...Element) {
n := len(*arr)
if i > n-1 {
return
}
// 构造需要插入元素的切片
inserts := Array{}
inserts = append(inserts, e...)
// 重新构造切片数组
result := Array{}
result = append(result, (*arr)[:i]...)
result = append(result, inserts...)
result = append(result, (*arr)[i:]...)
*arr = result
}
// 删除任意位置元素
func (arr *Array) Remove(i int) {
n := len(*arr)
if i > n-1 {
return
}
*arr = append((*arr)[:i], (*arr)[i+1:]...)
}
// 数组合并
func (arr *Array) Concat(next Array) {
*arr = append(*arr, next...)
}
// 迭代器
func (arr *Array) ForEach(f func(e Element)) {
for _, v := range *arr {
f(v)
}
}
// 过滤器
func (arr *Array) Filter(f func(element Element) bool) Array {
result := Array{}
for _, v := range *arr {
if f(v) {
result = append(result, v)
}
}
return result
}
// 排序
func (arr *Array) Sort(cmp func(a, b Element) int) {
ln := len(*arr)
if ln < 2 {
return
}
p := (*arr)[0]
i, j := 1, ln-1
for {
for i < j && cmp((*arr)[i], p) < 0 {
i++
}
for cmp((*arr)[j], p) > 0 {
j--
}
if i >= j {
break
}
(*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
}
// 交换
(*arr)[0], (*arr)[j] = (*arr)[j], (*arr)[0]
left := (*arr)[:j]
left.Sort(cmp)
right := (*arr)[j+1:]
right.Sort(cmp)
*arr = append(append(left, p), right...)
}
// 搜索
func (arr *Array) IndexOf(e Element) int {
for i, v := range *arr {
if v == e {
return i
}
}
return -1
}
func main() {
//arr := Array{1,2,3,4,5}
arr := make(Array, 0)
arr.Unshift(1, 2)
for i, v := range arr {
fmt.Printf("arr[%d]=%v\n", i, v)
}
fmt.Println("Origin:", arr)
arr.Unshift(0)
fmt.Println("Unshift(0):", arr)
arr.Push(6)
fmt.Println("Push(6):", arr)
fmt.Println("Pop()", arr.Pop(), ":", arr)
fmt.Println("Shift()", arr.Shift(), ":", arr)
arr.Insert(1, 9, 8, 7)
fmt.Println("Insert 9,8,7 at index=1:", arr)
arr.Remove(4)
fmt.Println("Remove index=1:", arr)
arr.Concat(Array{5, 6, 7, 8})
fmt.Println("Concat:", arr)
fmt.Println("ForEach:")
arr.ForEach(func(e Element) {
fmt.Println("element:", e)
})
fmt.Println("Filter %2 == 1:")
fmt.Println(arr.Filter(func(e Element) bool {
return e.(int)%2 == 1
}))
fmt.Println("Origin:", arr)
fmt.Println("Sort:")
arr.Sort(func(a, b Element) int {
return a.(int) - b.(int)
})
fmt.Println(arr)
fmt.Println("Index of 6:", arr.IndexOf(6))
}
运行结果
arr[0]=1
arr[1]=2
Origin: [1 2]
Unshift(0): [0 1 2]
Push(6): [0 1 2 6]
Pop() 6 : [0 1 2]
Shift() 0 : [1 2]
Insert 9,8,7 at index=1: [1 9 8 7 2]
Remove index=1: [1 9 8 7]
Concat: [1 9 8 7 5 6 7 8]
ForEach:
element: 1
element: 9
element: 8
element: 7
element: 5
element: 6
element: 7
element: 8
Filter %2 == 1:
[1 9 7 5 7]
Origin: [1 9 8 7 5 6 7 8]
Sort:
[1 5 6 7 7 8 8 9]
Index of 6: 2
Process finished with exit code 0
