线性结构：数组

朴灿烈づ我的快乐病毒、 2022-11-03 11:49 6阅读 0赞

### 目录 ###

*  第一章 稀疏数组介绍
 *  第二章 稀疏数组实现
 *  第三章 可变数组介绍
 *  第四章 可变数组实现

--------------------

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 稀疏数组介绍 #

当一个**二维数组**中大部分元素为０时，可以使用**稀疏数组**来保存该数组的信息，通过减少原数组中0的个数，以达到减小原数组的大小，具体处理方法如下：

1.  建立一个全新的二维数组，第一行存储原数组的行数、列数以及非零元素个数，其中，非零元素个数用于确定**存储数组数据**的行数。
2.  我们只需要循环遍历原数组，遇到非零元素将其加入到稀疏数组第二部分的**存储数组数据**区即可。

![e17560e86f71669e9d19b0ad5e6f0560.png][]

# 第二章 稀疏数组实现 #

**实现代码：**

public class SparseArray { 
        /** * 打印二维数组的信息 * * @param message 提示信息 * @param array 二维数组 */
        public void showArray(String message, int[][] array) { 
            System.out.println(message + "：");
            for (int[] row : array) { 
                for (int col : row) { 
                    System.out.printf("%d\t", col);
                }
                System.out.println();
            }
            System.out.println();
        }
    
        /** * 创建测试的二维数组 * * @return 二维数组 */
        public int[][] createArray() { 
            int testArray[][] = new int[10][10];
            testArray[1][1] = 1;
            testArray[1][2] = 2;
            testArray[2][3] = 3;
            return testArray;
        }
    
        /** * 原数组转换为稀疏数组 * * @param array 原数组 * @return 稀疏数组 */
        public int[][] toSparseArray(int[][] array) { 
            //获取原数组的行数
            int rows = array.length;
            //获取原数组的列数
            int cols = array[0].length;
            //获取非零元素个数
            int sum = 0;
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (array[i][j] != 0) { 
                        sum++;
                    }
                }
            }
            //创建一个稀疏数组
            int sparseArray[][] = new int[1 + sum][3];
            //第一部分信息赋值
            sparseArray[0][0] = rows;
            sparseArray[0][1] = cols;
            sparseArray[0][2] = sum;
            //第二部分数据赋值
            int count = 0;
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (array[i][j] != 0) { 
                        count++;
                        sparseArray[count][0] = i;
                        sparseArray[count][1] = j;
                        sparseArray[count][2] = array[i][j];
                    }
                }
            }
            //返回一个稀疏数组
            return sparseArray;
        }
    
        /** * 稀疏数组转换为原数组 * * @param sparseArray 稀疏数组 * @return 原数组 */
        public int[][] toOriginalArray(int[][] sparseArray) { 
            //获取原数组的行数
            int rows = sparseArray[0][0];
            //获取原数组的列数
            int cols = sparseArray[0][1];
            //恢复原数组的数据
            int testArray[][] = new int[rows][cols];
            for (int i = 1; i < sparseArray.length; i++) { 
                int row = sparseArray[i][0];
                int col = sparseArray[i][1];
                int val = sparseArray[i][2];
                testArray[row][col] = val;
            }
            //返回一个原数组
            return testArray;
        }
    }

**测试代码：**

public class SparseArrayTest { 
        public static void main(String[] args) { 
            SparseArray sa = new SparseArray();
    
            //创建一个测试二维数组
            int[][] testArray = sa.createArray();
            sa.showArray("创建一个测试二维数组", testArray);
    
            //原数组转换为稀疏数组
            int[][] sparseArray = sa.toSparseArray(testArray);
            sa.showArray("原数组转换为稀疏数组", sparseArray);
    
            //稀疏数组转换为原数组
            testArray = sa.toOriginalArray(sparseArray);
            sa.showArray("稀疏数组转换为原数组", testArray);
        }
    }

**运行效果：**

创建一个测试二维数组：
    0	0	0	0	0	0	0	0	0	0	
    0	1	2	0	0	0	0	0	0	0	
    0	0	0	3	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    
    原数组转换为稀疏数组：
    10	10	3	
    1	1	1	
    1	2	2	
    2	3	3	
    
    稀疏数组转换为原数组：
    0	0	0	0	0	0	0	0	0	0	
    0	1	2	0	0	0	0	0	0	0	
    0	0	0	3	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0

# 第三章 可变数组介绍 #

*  添加元素时：添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我  
    们这里创建一个是原数组两倍容量的新数组存储元素。

![07f6ce831d3c359a0ae858654db65c1f.png][]

*  移除元素时：移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存  
    空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。

![8d657f690bb12950db4529289a2387d1.png][]

# 第四章 可变数组实现 #

**实现代码：**

public class VariableArray<T> { 
        private T[] elements;                           //存储元素的数组
        private int size;                               //存储元素的个数
    
        public VariableArray(int capacity) { 
            this.elements = (T[]) new Object[capacity]; //初始化数组
            this.size = 0;                              //初始化长度
        }
    
        //获取数组当前大小
        public int size() { 
            return size;
        }
    
        //判断数组是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //检查下标是否合法
        public void checkIndex(int index) { 
            if (index < 0 || (size - 1) < index) { 
                throw new IndexOutOfBoundsException("数组下标越界异常，请检查数组的下标！");
            }
        }
    
        //获取指定位置元素
        public T get(int i) { 
            //下标检查
            checkIndex(i);
            //返回元素
            return elements[i];
        }
    
        //向数组中添加元素
        public void add(T t) { 
            //动态扩容
            if (size == elements.length) { 
                resize(2 * elements.length);
            }
            //添加元素
            elements[size++] = t;
        }
    
        //指定位置添加元素
        public void add(int i, T t) { 
            //下标检查
            checkIndex(i);
            //动态扩容
            if (size == elements.length) { 
                resize(2 * elements.length);
            }
            //元素后移
            for (int index = size; index > i; index--) { 
                elements[index] = elements[index - 1];
            }
            //添加元素
            elements[i] = t;
            //个数加一
            size++;
        }
    
        //删除指定位置元素
        public T remove(int i) { 
            //下标检查
            checkIndex(i);
            //记录元素
            T current = elements[i];
            //元素前移
            for (int index = i; index < size - 1; index++) { 
                elements[index] = elements[index + 1];
            }
            //个数减一
            size--;
            //动态缩容
            if (size < elements.length / 4) { 
                resize(elements.length / 2);
            }
            //返回元素
            return current;
        }
    
        //正向查找t元素第一次出现的位置
        public int indexOf(T t) { 
            for (int i = 0; i < size; i++) { 
                if (elements[i].equals(t)) { 
                    return i;
                }
            }
            return -1;
        }
    
        //反向查找t元素第一次出现的位置
        public int lastIndexOf(T t) { 
            for (int i = size - 1; i > -1; i--) { 
                if (elements[i].equals(t)) { 
                    return size - 1 - i;
                }
            }
            return -1;
        }
    
        //扩容缩容核心代码
        public void resize(int newCapacity) { 
            //定义一个临时数组，指向原来的数组
            T[] temp = elements;
            //创建一个新数组
            elements = (T[]) new Object[newCapacity];
            //把原来数组元素拷贝到新数组中即可
            for (int i = 0; i < size; i++) { 
                elements[i] = temp[i];
            }
        }
    }

**测试代码：**

public class VariableArrayTest { 
        public static void main(String[] args) { 
            VariableArray<String> va = new VariableArray<>(4);
    
            va.add("张三");
            va.add("李四");
            va.add("王五");
            va.add("赵六");
    
            System.out.println("====================");
            for (int i = 0; i < va.size(); i++) { 
                System.out.println(va.get(i));
            }
            System.out.println("====================");
            System.out.println(va.indexOf("张三"));
            System.out.println(va.indexOf("李四"));
            System.out.println(va.indexOf("王五"));
            System.out.println(va.indexOf("赵六"));
            System.out.println("====================");
            System.out.println(va.lastIndexOf("张三"));
            System.out.println(va.lastIndexOf("李四"));
            System.out.println(va.lastIndexOf("王五"));
            System.out.println(va.lastIndexOf("赵六"));
            System.out.println("====================");
            va.remove(3);
            va.remove(2);
            va.remove(1);
            va.remove(0);
            System.out.println(va.size());
        }
    }

**运行效果：**

====================
    张三
    李四
    王五
    赵六
    ====================
    0
    1
    2
    3
    ====================
    3
    2
    1
    0
    ====================
    0

[e17560e86f71669e9d19b0ad5e6f0560.png]: /images/20221024/29ae1bf8c5af4b5a93ac2ae37b76faae.png
[07f6ce831d3c359a0ae858654db65c1f.png]: /images/20221024/ca69c97dccd34593814e0ee11e245204.png
[8d657f690bb12950db4529289a2387d1.png]: /images/20221024/3e5cbe5ee4d14c39887a189f6754da0c.png