Golang数据结构 - 1 - 数组

数组

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。

在这里我们将用 Go 语言中的切片特性来实现数组的基本操作。

数组类型定义

我们首先定义数组类型为 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 函数向切片添加任意元素，给数组添加元素主要有两种方式：

1. 添加元素到数组末尾，这里通过Push方法实现
2. 添加元素到数组开头，这里通过Uushift方法实现

在数组末尾添加元素实现

// 向末尾添加元素
func (arr *Array)Push(e... Element) {
    *arr = append(*arr, e...)
}

在数组开头添加元素实现

// 向头部添加元素
func (arr *Array) Unshift(e... Element) {
    *arr = append(e, *arr...)
}

删除数组中的元素

我们可以借助Go语言中切片取值删除数组中的元素主要有两种方式

1. 删除数组末尾元素
2. 删除数组开头元素

删除数组末尾元素实现

// 删除末尾元素
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)
    }
}

过滤器

过滤器方法接收一个函数作为参数，对数组的元素逐个执行，函数的返回值为 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
}

完整代码示例

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 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
    }))
}

运行结果

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]

Process finished with exit code 0