Golang数据结构 - 1 - 数组

作者: vouv | 来源:发表于2019-06-18 22:34 被阅读0次

     ___      .______      .______          ___   ____    ____ 
    /   \     |   _  \     |   _  \        /   \  \   \  /   / 
   /  ^  \    |  |_)  |    |  |_)  |      /  ^  \  \   \/   /  
  /  /_\  \   |      /     |      /      /  /_\  \  \_    _/   
 /  _____  \  |  |\  \----.|  |\  \----./  _____  \   |  |     
/__/     \__\ | _| `._____|| _| `._____/__/     \__\  |__|

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。
在这里我们将用Go语言中的切片特性来实现数组的基本操作。

根据下标实现随机访问

计算机会给每个内存单元分配一个地址，然后通过这个地址来访问内存中的数据，访问数组中的元素时候，会根据如下寻址公式来访问：

$a[i]\_address = base\_address + i * data\_type\_size$

其中 $a[i]\_address$ 表示a[i]的地址， $base\_address$ 表示计算机分配的数组的地址， $data\_type\_size$ 表示数组中每个元素的大小，如果数据类型是整型int，那么 $data\_type\_size$ 就等于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