数据结构与算法 — 数组常见 *** 作【基于Golang语言实现】

数组 数组的特征

数组的特征

在计算机语言中数组是非常重要的集合类型，大部分计算机语言中数组具有如下三个基本特性：
一致性：数组只能保存相同数据类型元素，元素的数据类型可以是任何相同的数据类型。
有序性：数组中的元素是有序的，通过下标访问。
不可变性：数组一旦初始化，则长度（数组中元素的个数）不可变。
数组的前两个特征很好理解，这里重点说一下 不可变性 ，这个特性会导致在使用不同编程语言实现数组的基本 *** 作时，会有很大的差异性；

本文将着重讲数一下Java语言和Golang语言对于数组的基本 *** 作实现的差异性，同时可加深对语言的理解。

Java语言的实现代码：

public class MyArray {
    private int[] array;
    /**
     * 为什么要维护一个长度size，因为数组一旦初始化，其长度不可变，即array.length的值始终不变，
     * 所以需要使用一个size维护数组里面实际【可用】元素的个数，可用主要体现在删除元素的 *** 作上，
     * 如果删除的是最后位置上的元素，因为最后一个元素的位置无法再往左移，所以只需要size--即可，即维护的元素个数少一个即可。但数组中实际上还是存在最后一个元素的。
     */
    private int size;

    public MyArray(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }

    public void insertElement(int element, int index) {
        if (index < 0 || index > size) { //不能是 index>size -1，因为在第一次插入时，size=0，size-1=-1，-1
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        if(size >= array.length){ //当size=array.length时，数组已满，可扩容；当size>array.length必须要扩容
            resizeArrayCapacity();
        }
        for (int i = size - 1; i >= index; i--) { //i = size - 1的前提是size= index中"="的讲解，如果只是">"，则index位置的元素没有往后移动
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }

    public int deletedElement(int index){
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        int deletedElement = array[index];

        for(int i= index; i < size -1; i++){ //当index == size -1时，即删除最后一位元素时，不用往左移动元素，只需size--即可；需要深刻理解size的意义。如果想要真正的实现删除功能，需要考虑size
            array[i] = array[i+1];
        }
        size --;
        return deletedElement;
    }

    public void showElement() {
        for (int i = 0; i < size; i++) {
            System.out.println(array[i]);
        }
    }

    public void resizeArrayCapacity(){
        int[] newArray = new int[2*array.length];
        for(int i = 0; i < array.length; i++){
            newArray[i] = array[i];
        }
        array = newArray; //newArray能赋给array的原因是array和newArray只是变量名，它们的类型是一样的（int）型，变量存放的是指向的int数组的地址。
    }

    public static void main(String[] args) {
        MyArray myArray = new MyArray(5);
        myArray.insertElement(3, 0);
        myArray.insertElement(7, 1);
        myArray.insertElement(9, 2);
        myArray.insertElement(5, 3);
        myArray.insertElement(6, 1);
//        myArray.insertElement(8, 2);
        myArray.deletedElement(4);
        myArray.showElement();
    }
}

Golang语言的实现：

使用数组实现代码：

package main

import (
	"errors"
	"fmt"
)

var Array [5]int
var Size int

func InsertElement(element int, index int) error {
	if index < 0 || index > Size {
		return errors.New("超出数组实际元素范围！")
	}
	if Size >= len(Array) {
		ResizeArrayCapacity()
	}

	for i := Size - 1; i >= index; i-- {
		Array[i+1] = Array[i]
	}
	Array[index] = element
	Size++
	return nil
}

func DeletedElement(index int) (deletedElement int, err error) {
	if index < 0 || index >= Size {
		return -1, errors.New("超出数组实际元素范围！")
	}
	deletedElement = Array[index]
	for i := index; i < Size-1; i++ {
		Array[i] = Array[i+1]
	}
	Size--
	return deletedElement, nil
}

func ShowElement() {
	for i := 0; i < Size; i++ {
		fmt.Println("第 ", i+1, " 个元素： ", Array[i])
	}
}

func ResizeArrayCapacity() {
	newArray := [2*len(Array)]int{}
	for i := 0; i < len(Array); i++ {
		newArray[i] = Array[i]
	}
	Array = newArray
	fmt.Println()
}

func main() {
	Size = 0
	InsertElement(3, 0)
	InsertElement(7, 1)
	InsertElement(9, 2)
	InsertElement(5, 3)
	InsertElement(6, 1)
	InsertElement(8, 2)
	//DeletedElement(1)
	ShowElement()
}

在Golang语言中使用数组的实现在编译前会报错：

错误的意思是不能使用newArray给Array赋值，为什么Java语言中可以，而Golang语言中就不行了呢？
主要是因为newArray和Array两个变量的类型不一致导致的，特别需要注意的是Golang数组的长度也是数组类型的一部分，所以不同长度的数组赋值会发生编译错误。 Array的类型是[5]int 、 newArray的类型是[10]int 。

解决办法是使用切片，Golang语言的切片来实现数组的功能，使用 make() 函数构造切片。

make( []Type, size, cap )

其中 Type 是指切片的元素类型，size 指的是为这个类型分配多少个元素，cap 为预分配的元素数量，这个值设定后不影响 size，只是能提前分配空间，降低多次分配空间造成的性能问题。

使用切片的实现：

package main

import (
	"errors"
	"fmt"
)

var Array []int
var Size int

func InsertElement(element int, index int) error {
	if index < 0 || index > Size {
		return errors.New("超出数组实际元素范围！")
	}
	if Size >= len(Array) {
		ResizeArrayCapacity()
	}

	for i := Size - 1; i >= index; i-- {
		Array[i+1] = Array[i]
	}
	Array[index] = element
	Size++
	return nil
}

func DeletedElement(index int) (deletedElement int, err error) {
	if index < 0 || index >= Size {
		return -1, errors.New("超出数组实际元素范围！")
	}
	deletedElement = Array[index]
	for i := index; i < Size-1; i++ {
		Array[i] = Array[i+1]
	}
	Size--
	return deletedElement, nil
}

func ShowElement() {
	for i := 0; i < Size; i++ {
		fmt.Println("第 ", i+1, " 个元素： ", Array[i])
	}
}

func ResizeArrayCapacity() {
	newArray := make([]int, 2*len(Array), 2*(len(Array)))
	for i := 0; i < len(Array); i++ {
		newArray[i] = Array[i]
	}
	Array = newArray
}

func main() {
	Array = make([]int, 5, 5)
	Size = 0
	InsertElement(3, 0)
	InsertElement(7, 1)
	InsertElement(9, 2)
	InsertElement(5, 3)
	InsertElement(6, 1)
	InsertElement(8, 2)
	//DeletedElement(1)
	ShowElement()
}