再回首数据结构—数组(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实现)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

数字乌托邦

数字乌托邦

[美]弗雷德·特纳 / 张行舟、王芳、叶富华、余倩 / 译言·东西文库/电子工业出版社 / 2013-5-1 / 49.80元

20世纪60年代早期,在美国大众眼中,计算机只是冷战中冰冷的机器,然而到了90年代互联网到来之时,计算机却呈现出一个截然不同的世界——它们模拟出了一个数字乌托邦般的协同体,而这正是曾经最反对冷战的嬉皮士们的共同愿景。 本书正是探索这次非同寻常,且颇具讽刺意味的变革的第一本书。作者挖掘出那些在旧金山湾区的先驱者——斯图尔特·布兰德和他的“全球网络”鲜为人知的故事。1968年到1998年期间,通......一起来看看 《数字乌托邦》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

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

html转js在线工具