01数组

数据结构(二)之数组结构

如需转载, 请咨询作者, 并且注明出处.有任何问题, 可以关注我的微博: coderwhy, 或者添加我的微信: 372623326 几乎所有的编程语言都原生支持数组类型，因...

https://www.jianshu.com/p/9521594710d7

一、数组理论知识

1. 定义：数组是一种由相同类型的元素组成的数据集合，这些元素按照一定的顺序排列，并且可以通过索引（下标）来访问。

2. 下标访问：数组中的元素可以通过下标来访问，下标通常从0开始递增。这是因为数组在内存中是一段连续的存储空间，每个元素占据固定大小的内存单元。通过计算偏移量（索引 * 单个元素大小），可以快速定位数组中的任意元素。

3. 内存存储：数组在内存中是连续存储的，即数组的各个元素依次存储在相邻的内存单元中。这种存储方式使得通过下标访问元素的时间复杂度为O(1)，即具有很高的访问效率。

4. 数组的特点包括：
• 元素类型相同。
• 连续存储，可以通过下标快速访问。
• 大小固定，无法动态扩展。

5. 动态数组：
• 问题：动态数组是什么？它与静态数组有何区别？
• 解答：动态数组是一种可以动态增长和缩小的数组，与静态数组不同的是，它的大小可以根据需要动态调整，通常通过重新分配内存来实现。
• 数组在大多数编程语言中的大小固定，无法动态扩展的原因主要是因为数组在内存中是一段连续的存储空间，这段空间在创建数组时就已经确定了大小。当我们创建一个数组时，计算机会为它分配一段连续的内存空间来存储元素。这段内存空间的大小是在数组创建时确定的，通常是根据数组的类型和长度计算得出的。因此，一旦数组被创建，它的大小就固定了，无法直接在原来的内存空间上进行扩展。
• 要想扩展数组，通常需要进行以下操作：分配一块新的内存空间，大小比原数组大。将原数组中的元素复制到新的内存空间中。释放原数组所占用的内存空间。

二、数组的优缺点

• 问题：数组有哪些优点和缺点？

• 解答：数组的优点包括：
• 快速访问：通过下标可以快速访问任意位置的元素。
• 简单高效：数组的存储和访问操作都非常简单高效。

• 缺点包括：
• 大小固定：无法动态扩展，可能导致内存浪费或需要重新分配更大的空间。
• 插入和删除元素效率低：需要移动其他元素，效率较低。

• 在大多数编程语言中，数组的内存空间是一段连续的存储空间，每个元素占据固定大小的内存。当我们在数组中删除或插入元素时，如果要保持数组的顺序不变，就需要移动元素。
1. 删除元素：
• 如果要删除数组中的某个元素，那么这个元素之后的所有元素都需要向前移动一个位置，以填补被删除元素的空缺。这是因为数组的内存空间是连续的，删除一个元素会造成后续元素的位置变化，为了保持数组的连续性和顺序不变，需要移动元素。
2. 插入元素：
• 如果要在数组中插入一个元素，那么插入位置之后的所有元素都需要向后移动一个位置，为新元素腾出空间。同样地，为了保持数组的连续性和顺序不变，需要移动元素。

三、JS中的数组

四、数组手写&算法&刷题

• 数组手写汇总

/**
 * 基本数组结构
 */
class BasicArray {
    constructor() {
        this.length = 0;
        this.data = {};
    }

    /**
     * 末尾增加元素
     * @param {*} item 
     */
    add(item) {
        this.data[this.length] = item;
        this.length++;
    }

    /**
     * 任意位置插入元素
     * @param {*} index 
     * @param {*} item 
     */
    insert(index, item) {
        if (index < 0) index = 0;
        if (index > this.length) index = this.length;
        // 从最后一个开始移动，让出i的位置
        if (index >= 0 && index <= this.length) {
            for (let i = this.length; i > index; i--) {
                this.data[i] = this.data[i - 1];
            }
            this.data[index] = item;
        } 
        this.length++;
    }

    /**
     * 删除指定位置元素
     * @param {*} index 
     * @returns 
     */
    delete(index) {
        const deleted = this.data[index];
        // 用i后面的元素覆盖之前的元素
        for (let i = index; i < this.length - 1; i++) {
            this.data[i] = this.data[i + 1];
        }
        delete this.data[this.length - 1];
        this.length--;
        return deleted;
    }

    /**
     * 更新元素
     * @param {*} index 
     * @param {*} item 
     */
    update(index, item) {
        this.data[index] = item;
    }

    /**
     * 获取数组长度
     * @returns 
     */
    getLength() {
        return this.length;
    }

    /**
     * 获取元素
     * @param {*} index 
     * @returns 
     */
    get(index) {
        return this.data[index];
    }

    /**
     * 打印
     */
    print() {
        const result = [];
        for (let i = 0; i < this.length; i++) {
            result.push(this.data[i]);
        }
        console.log(result);
    }
}



// // 基本数组使用示例
// const myArray = new BasicArray();
// myArray.insert(0, 'a');
// myArray.insert(1, 'b');
// myArray.insert(2, 'c');
// myArray.print(); // ['a', 'b', 'c']

// myArray.update(1, 'x');
// myArray.print(); // ['a', 'x', 'c']

// myArray.delete(0);
// myArray.print(); // ['x', 'c']

// console.log(myArray.getLength()); // 2

module.exports = BasicArray;