02_数据结构与算法之数组

ゝ一世哀愁。 2022-09-10 11:27 159阅读 0赞

## 1、什么是数组 ##

数组（Array）是**有限**个**相同类型**的变量所组成的**有序**集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。  
![在这里插入图片描述][02664da391d347d099f060a3fce934f3.png]  
数组下标从零开始(Why)

## 2、存储原理 ##

数组用一组**连续的内存空间**来存储一组具有**相同类型**的数据  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]  
(模拟内存存储)  
灰色格子：被使用的内存  
橙色格子：空闲的内存  
红色格子：数组占用的内存  
数组可以根据下标随机访问数据  
比如一个整型数据 int\[\] 长度为5  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_14_color_FFFFFF_t_70_g_se_x_16]  
假设首地址是：1000  
int是4字节（32位）,实际内存存储是位  
随机元素寻址  
a\[i\]\_address=a\[0\]\_address+i\*4  
该公式解释了三个方面

*  连续性分配
 *  相同的类型
 *  下标从0开始

## 3、操作 ##

#### 1）读取元素 ####

根据下标读取元素的方式叫作随机读取

int n=nums[2]

#### 2）更新元素 ####

nums[3]= 10;

注意不要数组越界  
读取和更新都可以随机访问，时间复杂度为**O(1)**

#### 3）插入元素 ####

有三种情况：

*  **尾部插入**  
    在数据的实际元素数量小于数组长度的情况下：  
    直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作  
    ![在这里插入图片描述][3707ac8094224ecba6435a0944519af5.png]
 *  **中间插入**  
    在数据的实际元素数量小于数组长度的情况下：  
    由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]
 *  **超范围插入**  
    假如现在有一个数组，已经装满了元素，这时还想插入一个新元素，或者插入位置是越界的  
    这时就要对原数组进行扩容：可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]

int[] numsNew=new int[nums.length*2]; 
    System.arraycopy(nums,0,numsNew,0,nums.length); // 原数组就丢掉了，资源浪费 
    nums=numsNew;

#### 4) 删除元素 ####

数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。

for(int i=p;i<nums.length;i++){  
    	nums[i-1]=nums[i]; 
    }

**完整代码：**

public class ArrayDemo { 
        int[] nums = new int[8];
    
        public ArrayDemo() { 
            nums[0] = 3;
            nums[1] = 1;
            nums[2] = 2;
            nums[3] = 5;
            nums[4] = 4;
            nums[5] = 9;
        }
    
        //读取元素
        public int get(int i) { 
            return nums[i];
        }
    
        //更新元素
        public void update(int i, int n) { 
            nums[i] = n;
        }
    
        //插入元素: 尾部插入
        public void insertTail(int n) { 
            nums[6] = n;
        }
    
        //插入元素: 中间插入
        public void insertMiddle(int p, int n) { 
            for (int i = nums.length-1; i >= p-1; i--) { 
                //能取得值
                if (nums[i] != 0) { 
                     nums[i+1]=nums[i];
                }
            }
            nums[p-1]=n;
        }
    
        /** * 旧数组复制到新数组 */
        public void resize(){ 
            int[] numsNew=new int[nums.length*2];
            System.arraycopy(nums,0,numsNew,0,nums.length);
            nums=numsNew;
        }
    
        //插入元素: 超范围插入
        public void insertOutOfBounds(int p,int n){ 
            //数组扩容
            resize();
            nums[p-1]=n;
        }
        
        //删除元素
        public void deleteMiddle(int p){ 
            for(int i=p;i<nums.length;i++){ 
                nums[i-1]=nums[i];
            }
        }
        
        //遍历元素
        public void display() { 
            for (int n : nums) { 
                System.out.println(n);
            }
        }
        
        //倒叙遍历
        public void display2() { 
            for (int i = nums.length - 1; i >= 0; i--) { 
                System.out.println(nums[i]);
            }
        }
        
        //测试方法
        public static void main(String[] args) { 
            ArrayDemo demo = new ArrayDemo();
            demo.deleteMiddle(3);
            demo.display();
        }
    }

## 4. 时间复杂度 ##

**读取和更新**都是随机访问，所以是**O(1)**  
**插入**数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起来插入操作的时间复杂度是**O(n)**。  
**删除**操作，只涉及元素的移动，时间复杂度也是**O(n)**

## 5. 优缺点 ##

**优点：**  
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素

**缺点：**

1.  **插入和删除**元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响**效率**。 (ArrayList)
2.  申请的空间必须是**连续**的，也就是说即使有空间也可能因为没有足够的连续空间而创建失败
3.  如果超出范围，需要重新申请内存进行存储，原**空间**就**浪费**了

**tips:**

*  数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。
 *  数据结构和算法的可视化网站：[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html][https_www.cs.usfca.edu_galles_visualization_Algorithms.html]

以下是网站小栗子：可以动态查看栈的push、pop过程。  
同样，也可以查看排序过程，是个学算法比较实用的网址。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[02664da391d347d099f060a3fce934f3.png]: /images/20220829/c146ebb66483491483e7a0907e3ba331.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7cd02e4517f34de8b8b5621d53cafab8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/da582e532ecf439990435eb3dff24591.png
[3707ac8094224ecba6435a0944519af5.png]: /images/20220829/89aaf9399aaa4630a045528ce00baf5a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/72b853bd0b924f188a1dcc624196d5d3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/570e424a55994404bf35b9ebd2794666.png
[https_www.cs.usfca.edu_galles_visualization_Algorithms.html]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/1f969a7dfd9041d487743f6203a61607.png