美文网首页
Golang数据结构 - 1 - 数组

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函数向切片添加任意元素，给数组添加元素主要有两种方式：

  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
}

在数组中任意位置添加或删除元素

这里我们通过两种方式实现在数组中任意位置添加或删除元素：

  1. Insert方法，在数组任意位置插入元素
  2. 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

相关文章

  • Golang数据结构 - 1 - 数组

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

  • Golang数组与切片

    Golang数组与切片 数组的声明 Golang中的数组属于静态数组，不允许动态扩展 Golang中数组会默认初始...

  • Go-Array

    golang初始化数组 golang中数组为值类型 方式1：指定数组长度 方式2：自行推断数组长度 方式3：指定索...

  • array

    数组是golang中最常用的一种数据结构,数组就是同一类型数据的有序集合 定义一个数组 格式: var name ...

  • 星媛面试-进大厂必备--Go语言十问（已上岸，贡献给学弟学妹）

    一，golang语言的数组与切片的区别 答：数组是一个固定长度的基本数据结构类型，slice是基于数组实现的一种长...

  • golang数组append切片添加与删除

    golang数组append切片添加 golang数组删除元素 1.从开头位置删除 2.从中间位置删除 3.从尾部删除

  • ArrayList、LinkedList、Vector的区别

    1.从存储数据结构分析 ArrayList：数组 Vector：数组 LinkedList：双向链表数组：(数组属...

  • Golang 数据结构到底是怎么回事？gdb调一调？

    “ 不仅限于语法，使用gdb，dlv工具更深层的剖析golang的数据结构” Golang数据结构 变量：有意义的...

  • 数据结构：数组

    00数据结构与算法分析：大纲01数据结构：数组02数据结构：链表03数据结构：栈03数据结构：队列 数组 数组是一...

  • 5. Disruptor 高性能解析

    1. 数据结构-内存预加载机制 数据结构层面：使用环形结构、数组、内存预加载RingBuffer使用数组Objec...

网友评论

      本文标题：Golang数据结构 - 1 - 数组

      本文链接：https://www.haomeiwen.com/subject/ictcqctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Golang数据结构 - 1 - 数组|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！