数组

目录

  • 数组
  • 线性表(Linear List)
  • 连续的内存空间和相同类型的数据
    • 低效的“插入”
    • 低效的删除
  • 警惕数组的访问越界问题
  • 容器能否完全代替数组?
  • 二维数组的内存寻址公式
  • Go语言代码示例

数组

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

线性表(Linear List)

  • 线性表就是数据排成像一条线一样的结构
  • 每个线性表上的数据最多只有前和后两个方向
  • 数组链表队列等都是线性表结构

与它相对应的概念是非线性表,比如二叉树等。非线性表指数据之间不是简单的前后关系

连续的内存空间和相同类型的数据

正因为这两个限制,它才具有“随机访问

数组是如何实现根据下标随机访问数组元素?

比如长度为10的int类型数组 int[] = new int[10]

计算机给数组a[10],分配一块连续的内存空间 1000 ~ 1039

其中内存块的首地址是 base_address = 1000

我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据

当计算机需要随机访问数组中的某个元素时,它会首先通过寻址公式。

来计算出该元素存储的内存地址

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中的每个元素的大小

面试题:数组和链表的区别?

数组支持随机访问,根据下标随机访问的时间复杂度为 O(1),二分查找的时间复杂度是 O(logn)
链表适合插入、删除,时间复杂度 O(1)

低效的“插入”

如果在数组的末尾插入元素,不需要移动数据,时间复杂度为 O(1)

在数组的开头插入元素,所有的数据都需要依次往后移动一位,最坏时间复杂度是 O(n)

因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+...+n)/n = O(n)

这里考虑一下,如果数组是有序的,在某个位置插入一个新的元素,就必须移动数据

但是数组中存储的数据并没有任何规律,数组只是作为一个存储数据的集合,在这种情况下

将插入一个新的元素,为了避免大规模的数据搬移,

可以直接将第k位的数据移动到数组元素的最后,把新的元素直接放入第k个位置

利用这种处理技巧,在特定情况下,在第k个位置插入一个元素的时间复杂度就会降为O(1),快排中使用

低效的删除

跟插入数据类似,如果我们要删除第k个位置的数据,为了内存的连续性,也要搬移数据

  • 如果删除数组末尾的数据,则最好情况时间复杂度为 O(1)
  • 如果删除数组开头的数据,则最坏情况时间复杂度为 O(n)
  • 平均情况时间复杂度为 O(n)

某些特殊场景下,不一定非得追求数组中数据的连续性。

如果我们将多次删除操作集中在一起执行,删除的效率会有所提高

例如,数组a[10]中存储了8个元素:a, b, c, d, e, f, g, h。现在要依次删除 a, b, c 三个元素

为了避免 d, e, f, g, h 这几个数据会被搬移三次,可以先记录下已经删除的数据

每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除

当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,

这样就大大减少了删除操作导致的数据搬移

这就是 JVM 标记清除垃圾回收算法的核心思想

数据结构和算法的魅力在于,很多时候并不是要去死记硬背某个数据结构或者算法,
而是要学习它背后的思想和处理技巧,这些东西才是最有价值的
不管在软件开发还是架构设计中,总能找到某些算法和数据结构的影子

警惕数组的访问越界问题

首先分析这段C语言代码的运行结果

int main(int argc, char* argv[1]) {
    int i = 0;
  int arr[3] = {0};
    for (; i <= 3; i++){
    arr[i] = 0;
    printf("hello world\n");
  }
  return 0;
}

数组大小为3,a[0], a[1], a[2],for 循环的结束条件错写为 i <= 3而非 i < 3,所以当 i=3 时,数组 a[3] 访问越界


Go语言本身就会越界检查,比如下面代码

就会抛出 invalid array index 3 (out of bounds for 3-element array)

    a := [3]int{1, 2, 3}
    a[3] = 10

容器能否完全代替数组?

针对数组类型,很多语言都提供了容器类,比如Java中的 ArrayList,C++ STL中的 vector

在项目开发中,什么时候适合用数组,什么时候适合用容器呢

  • 如果数据大小事先已知,并对数组的操作非常简单,可以直接使用数组

二维数组的内存寻址公式

对于m *n 的数组,a[i][j] (i < m, j < n)的地址为:

a[i][j]_address = base_address + (i*n +j)*type_size

Go语言代码示例

package main

import (
    "errors"
    "fmt"
)

/**
 * int类型数组的插入、删除、根据下标随机访问
 */

type Array struct {
    data   []int
    length uint
}

// 为数组初始化内存
func NewArray(capacity uint) *Array {
    if capacity == 0 {
        return nil
    }
    return &Array{
        data:   make([]int, capacity, capacity),
        length: 0,
    }
}

// 求数组长度
func (this *Array) Len() uint {
    return this.length
}

// 判断索引是否越界
func (this *Array) isIndexOutOfRange(index uint) bool {
    if index >= uint(cap(this.data)) {
        return true
    }
    return false
}

// 通过索引查找数组,索引范围[0, n-1]
func (this *Array) Find(index uint) (int, error) {
    if this.isIndexOutOfRange(index) {
        return 0, errors.New("out of index range")
    }
    return this.data[index], nil
}

// 插入数组到索引index上
func (this *Array) Insert(index uint, v int) error {
    if this.Len() == uint(cap(this.data)) {
        return errors.New("full array")
    }
    if index != this.length && this.isIndexOutOfRange(index) {
        return errors.New("out of index range")
    }
    for i := this.length; i > index; i-- {
        this.data[i] = this.data[i-1]
    }
    this.data[index] = v
    this.length++
    return nil
}

// 插入新元素到数组尾部
func (this *Array) InsertToTail(v int) error {
    return this.Insert(this.Len(), v)
}

// 删除索引index上的值
func (this *Array) Delete(index uint) (int, error) {
    if this.isIndexOutOfRange(index) {
        return 0, errors.New("out of index range")
    }
    v := this.data[index]
    for i := index; i < this.Len()-1; i++ {
        this.data[i] = this.data[i+1]
    }
    this.length--
    return v, nil
}

// 打印数组
func (this *Array) Print() {
    var format string
    for i := uint(0); i < this.Len(); i++ {
        format += fmt.Sprintf("|%+v", this.data[i])
    }
    fmt.Println(format)
}

测试示例

package main

import "testing"

func TestArray_Insert(t *testing.T) {
    capacity := 10
    arr := NewArray(uint(capacity))
    for i := 0; i < capacity-2; i++ {
        err := arr.Insert(uint(i), i+1)
        if nil != err {
            t.Fatal(err.Error())
        }
    }
    arr.Print() // |1|2|3|4|5|6|7|8

    arr.Insert(uint(6), 999)
    arr.Print() // |1|2|3|4|5|6|999|7|8

    arr.InsertToTail(666)
    arr.Print() // |1|2|3|4|5|6|999|7|8|666
}

func TestArray_Delete(t *testing.T) {
    capacity := 10
    arr := NewArray(uint(capacity))
    for i := 0; i < capacity; i++ {
        err := arr.Insert(uint(i), i+1)
        if nil != err {
            t.Fatal(err.Error())
        }
    }
    arr.Print()

    for i := 9; i >= 0; i-- {
        _, err := arr.Delete(uint(i))
        if nil != err {
            t.Fatal(err)
        }
        arr.Print()
    }
}

func TestArray_Find(t *testing.T) {
    capacity := 10
    arr := NewArray(uint(capacity))
    for i := 0; i < capacity; i++ {
        err := arr.Insert(uint(i), i+1)
        if nil != err {
            t.Fatal(err.Error())
        }
    }
    arr.Print()

    t.Log(arr.Find(0))  // 1 
    t.Log(arr.Find(9))  // 10 
    t.Log(arr.Find(11)) // 0 out of index range
}

运行结果

=== RUN   TestArray_Insert
|1|2|3|4|5|6|7|8
|1|2|3|4|5|6|999|7|8
|1|2|3|4|5|6|999|7|8|666
--- PASS: TestArray_Insert (0.00s)
=== RUN   TestArray_Delete
|1|2|3|4|5|6|7|8|9|10
|1|2|3|4|5|6|7|8|9
|1|2|3|4|5|6|7|8
|1|2|3|4|5|6|7
|1|2|3|4|5|6
|1|2|3|4|5
|1|2|3|4
|1|2|3
|1|2
|1

--- PASS: TestArray_Delete (0.00s)
=== RUN   TestArray_Find
|1|2|3|4|5|6|7|8|9|10
--- PASS: TestArray_Find (0.00s)
    array_test.go:54: 1 
    array_test.go:55: 10 
    array_test.go:56: 0 out of index range
PASS

你可能感兴趣的