再回首数据结构—数组(Golang实现)

栏目: Go · 发布时间: 5年前

内容简介:数组为线性数据结构,通常编程语言都有自带了数组数据类型结构,数组存放的是有个相同数据类型的数据集;为什么称数组为线性数据结构:因为数组在内存中是连续存储的数据结构,数组中每个元素最多只有左右两个方向有相邻的元素;数组中的每个元素都有一个索引(或称下标)标识,这个索引在编程语言中通常都是从0开始,通过索引可访问到数组中对应的元素;数组的数据结构如下所示:

数组为线性数据结构,通常编程语言都有自带了数组数据类型结构,数组存放的是有个相同数据类型的数据集;

为什么称数组为线性数据结构:因为数组在内存中是连续存储的数据结构,数组中每个元素最多只有左右两个方向有相邻的元素;数组中的每个元素都有一个索引(或称下标)标识,这个索引在编程语言中通常都是从0开始,通过索引可访问到数组中对应的元素;数组的数据结构如下所示:

再回首数据结构—数组(Golang实现)

数组的优势

从上文中我们知道数组在内存中是 连续存储 的也就是说数组中元素在内存块为连续,此时我们利用此特性 通过索引快速访问 数据元素;因此也称数组支持 随机访问

下面我们通过一个示例来说明数组的随机访问特性;

Go 中定义一个长度为7的数组:

var array [7] int

此时我们可以通过索引随机访问数组中元素如:array[5]即可访问到数组中的第六个元素,这背后又是怎样的呢,上面我们说过数组在内存中的存储结构是连续的上面我们定义的数组结构如下所示:

再回首数据结构—数组(Golang实现)

此处假设该数组内存空间首地址为:000,由于该数据类型为int因此每个数据元素占4个字节,所以上面定义7个长度数组占用的内存地址为:000~024连续的地址空间;所以通过下面的计算公式即可实现数组的随机访问,比如访问数组中第五个元素内存地址的计算公式如下:

所访问元素内存地址=数组首地址 + index * 数据类型大小

array[5]内存地址 = 000 + 5 * 4

所以数组的优势为: 1、简单;2、支持随机访问,通过索引随机访问时间复杂度为O(1)

数组插入与删除

数组的插入与删除其实并不高效,由于数组存储是连续的内存空间,所以我们在对数组进行操作时都需要去 维护这个连续性 ,因此也就牺牲了一些效率,当插入或删除数组中元素时数组中元素都需要大量移动如下图所示:

再回首数据结构—数组(Golang实现)

在索引为3的位置插入g,需把索引3~n元素后移一位

再回首数据结构—数组(Golang实现)

删除数组索引为1的元素,需把索引2~n元素前移一位

因此数组的 插入、删除平均时间复杂度 为: O(n) ,这里说的是平均复杂度是因为还有例外情况,比如在数组末尾插入元素、删除数组末尾元素这些情况时间复杂度为O(1);

每种编程语言中都存在数组,数组其实还分为 静态数组动态数组 ;静态数组是指数组创建后存储空间固定不变的、而动态数组为在使用数组过程中当存储空间不足时可动态扩容;下面为使用Golang实现的动态数组封装,动态数组的 扩容、缩容 需要注意扩容的大小与缩容的零界点,此处可能会影响到数组性能;

type Array struct {
    data []interface{}
    size int
  }

  func NewArray(capacity int) *Array {
    array := new(Array)
    array.data = make([]interface{}, capacity)
    array.size = 0
    return array
  }

  func NewDefaultArray() *Array {
    return NewArray(10)
  }

  /**
  获取元素个数
   */
  func (a *Array) Size() int {
    return a.size
  }

  /**
  获取容量大小
   */
  func (a *Array) Capacity() int {
    return len(a.data)
  }

  /**
  是否为空
   */
  func (a *Array) IsEmpty() bool {
    return a.size == 0
  }

  /**
  往数组末尾添加元素
   */
  func (a *Array) AddLast(e interface{}) error {
    return a.Add(a.size, e)
  }

  /**
  清空数组
   */
  func (a *Array) Clear() {
    a.data = make([]interface{}, a.size)
    a.size = 0
  }

  /**
  往第一个位置添加元素
   */
  func (a *Array) AddFirst(e interface{}) error {
    return a.Add(0, e)
  }

  /**
  往指定索引添加元素
   */
  func (a *Array) Add(index int, e interface{}) error {
if index < 0 || index > a.size {
    return errors.New("Add failed, Require index >= 0 and index< size")
}

if a.size == len(a.data) {
    a.resize(2 * len(a.data))
}

for i := a.size - 1; i >= index; i-- {
    a.data[i+1] = a.data[i]
}
a.data[index] = e
a.size++
return nil
  }

  /**
  更新指定位置元素
   */
  func (a *Array) Update(index int, e interface{}) error {
    if index < 0 || index > a.size {
        return errors.New("update failed, Require index >= 0 and index< size")
    }
    a.data[index] = e
    return nil
  }

  /**
  获取指定位置元素
   */
  func (a *Array) FindElement(index int) interface{} {
    if index < 0 || index > a.size {
        return errors.New("update failed, Require index >= 0 and index< size")
    }
    return a.data[index]
  }

  /**
  删除数组指定索引位置的元素,返回删除的元素
   */
  func (a *Array) Remove(index int) (e interface{}) {
    if index < 0 || index > a.size {
        return errors.New("remove failed, Require index >= 0 and index< size")
    }
    e = a.data[index]
    for i := index + 1; i < a.size; i++ {
        a.data[i-1] = a.data[i]
    }
    a.size--
    //删除元素后数组缩小一位,将该位置元素置nil
    a.data[a.size] = nil
    return
  }

  /**
  删除数组首个元素
   */
  func (a *Array) RemoveFirst() (e interface{}) {
    return a.Remove(0)
  }

  /**
  数组扩容
   */
  func (a *Array) resize(newCapacity int) {
    newData := make([]interface{}, newCapacity)
    for i := 0; i < a.size; i++ {
        newData[i] = a.data[i]
    }
    a.data = newData
  }

参考资料: https://zh.wikipedia.org/wiki/%E6%95%B0%E7%BB%84


以上所述就是小编给大家介绍的《再回首数据结构—数组(Golang实现)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

统计自然语言处理

统计自然语言处理

宗成庆 / 清华大学出版社 / 2008-5 / 66.00元

内容简介 本书全面介绍了统计自然语言处理的基本概念、理论方法和最新研究进展,内容包括形式语言与自动机及其在自然语言处理中的应用、语言模型、隐马尔可夫模型、语料库技术、汉语自动分词与词性标注、句法分析、词义消歧、统计机器翻译、语音翻译、文本分类、信息检索与问答系统、自动文摘和信息抽取、口语信息处理与人机对话系统等,既有对基础知识和理论模型的介绍,也有对相关问题的研究背景、实现方法和技术现状的详......一起来看看 《统计自然语言处理》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具