1、线性表之数组-简介

  1. 1、数组-概述：
  2.     1-1、数组是一种连续存储线性结构[在内存中连续存储多个元素的结构，在内存中的分配也是连续的]，元素类型相同，大小相等。
  3.     1-2、数组可以是多维的，通过使用整型索引值来访问他们的元素，用来存储固定大小元素的线性表。
  4.     1-3、对于指定下标的查找，时间复杂度为O(1)；对于一般的插入删除操作， 涉及到数组元素的移动，其平均复杂度也为O(n)。
  6. 2、数组-优点
  7.     2-1、按照索引查询元素速度快
  8.     2-2、按照索引遍历数组方便
  10. 3、数组-缺点：
  11.     3-1、数组的大小固定后就无法扩容了
  12.     3-2、数组只能存储一种类型的数据
  13.     3-3、添加，删除的操作慢，因为要移动其他的元素(如果是添加删除末尾的话，那速度不慢)
  15. 4、数组-适用场景：
  16.     4-1、频繁查询，对存储空间要求不大，很少增加和删除的情况。
  18. 5、数组的常见应用：
  19.     5-1、ArrayList、LinkedList、Vector、
  21. 6、普通数据-举例Demo:
  22.     public static void main(String[] args) {
  23.       Integer[] integers = new Integer[10];
  24.       integers[0]=0;//王五
  25.       integers[1]=1;
  26.       integers[2]=2;
  27.     }

2.1、稀疏数组(SparseArray)

  1. 1、稀疏数组(SparseArray)-介绍：
  2.     1-1、当一个数组中大部分元素为0，或元素值为同一个时，可使用稀疏数组来保存该数组
  3.     1-2、处理方式：
  4.         1-2-1、记录数组一共有几行几列、有多少个不同的值。
  5.         1-2-2、把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
  6.     1-3、代码示例
  7.         第一行存储原始数据总行数，总列数，总的非0数据个数
  8.         接下来每一行都存储非0数 所在行，所在列，和具体值
  10.             rows  cols   n
  11.             r1    c1    val1
  12.             r2    c2    val2
  13.             .     .      .
  14.             .     .      .
  15.             rn    cn    valn

2.2、普通数组与稀疏数组互转

  1. public class SparseArray {
  2.     /**
  3.      * 稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO过程中提高效率等等。
  4.      * @param args
  5.      */
  6.     public static void main(String[] args) throws Exception {
  7.         /**
  8.          * 初始化二维数组
  9.          * <p>
  10.          *     0 0 0 0 0 0 0 0 0 0 0
  11.          *     0 0 1 0 0 0 0 0 0 0 0
  12.          *     0 0 0 0 2 0 0 0 0 0 0
  13.          *     0 0 0 0 0 0 0 0 0 0 0
  14.          *     0 0 0 0 0 0 0 0 0 0 0
  15.          *     0 0 0 0 0 0 0 0 0 0 0
  16.          *     0 0 0 0 0 0 0 0 0 0 0
  17.          *     0 0 0 0 0 0 0 0 0 0 0
  18.          *     0 0 0 0 0 0 0 0 0 0 0
  19.          *     0 0 0 0 0 0 0 0 0 0 0
  20.          *     0 0 0 0 0 0 0 0 0 0 0
  21.          * </p>
  22.          */
  23.         //初始化原数组,[row][col]
  24.         int[][] originalArray = new int[11][11];
  25.         originalArray[1][2] = 1;
  26.         originalArray[2][4] = 2;
  27.         for(int[] row : originalArray){
  28.             for(int item : row){
  29.                 System.out.printf("%d\t",item);
  30.             }
  31.             System.out.println();
  32.         }
  33.         System.out.println("---------> 二维数组转稀疏数组");
  34.         /**
  35.          * 稀疏数组
  36.          * <p>
  37.          *     11 11 2
  38.          *     1  2  1
  39.          *     2  4  2
  40.          * </p>
  41.          */
  42.         //得到非0数据数
  43.         int sum = 0;
  44.         for (int i = 0;i<originalArray.length;i++){
  45.             for(int j = 0;j<originalArray[i].length;j++){
  46.                 if(originalArray[i][j] != 0){
  47.                     sum++;
  48.                 }
  49.             }
  50.         }
  51.         //创建稀疏数组
  52.         int[][] sparseArray = new int[sum+1][3];
  53.         //给稀疏数组赋值
  54.         sparseArray[0][0] = 11;
  55.         sparseArray[0][1] = 11;
  56.         sparseArray[0][2] = sum;
  57.         //将非0的数放入稀疏数组
  58.         //count：标识第几个非0数
  59.         int count = 0;
  60.         for (int i = 0;i<11;i++){
  61.             for(int j = 0;j<11;j++){
  62.                 if(originalArray[i][j] != 0){
  63.                     count++;
  64.                     sparseArray[count][0] = i;
  65.                     sparseArray[count][1] = j;
  66.                     sparseArray[count][2] = originalArray[i][j];
  67.                 }
  68.             }
  69.         }
  70.         //遍历稀疏数组
  71.         for(int i = 0;i<sparseArray.length;i++){
  72.             System.out.printf("%d\t%d\t%d\t\n",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
  73.         }
  74.         System.out.println("----------->稀疏数组转回原始数组");
  75.         // 将稀疏数组存入磁盘（文件）
  76.         sparseArrayToIo(sparseArray);
  77.         //将稀疏数组 恢复成原始的二维数组
  78.         //先读取稀疏数组的第一行 根据第一行创建原始的二维数组 比如上面的chessArr2=int[11][11]
  79.         //读取稀疏数组后 几行的数据 并赋给原始的二维数组
  80.         int newArray[][]=new int[sparseArray[0][0]][sparseArray[0][1]];
  81.         for(int i=1;i<=count;i++){
  82.             newArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
  83.         }
  84.         System.out.println("打印读取出来的二维数组");
  85.         for(int i=0;i<newArray.length;i++) {
  86.             for (int j = 0; j < newArray[i].length; j++) {
  87.                 System.out.printf("%d\t", newArray[i][j]);
  88.             }
  89.             System.out.println();
  90.         }
  91.     }
  92.     /**
  93.      * 将稀疏数组存入磁盘（文件）
  94.      *
  95.      */
  96.     public static void sparseArrayToIo(int[][] sparseArray) throws Exception {
  97.         OutputStreamWriter ow = null;
  98.         String filePath = "D:\\IdeaSelfLearnSpace\\DataStructureStudy\\sparseArray.txt";
  99.         File file = new File(filePath);
  100.         try {
  101.             if(!file.exists()){
  102.                 file.createNewFile();
  103.             }
  104.             ow = new OutputStreamWriter(new FileOutputStream(filePath),"UTF-8");
  105.             //设置文件内容往后追加,默认为false
  106.             //bw = new BufferedWriter(new FileWriter(file, true));
  107.             //写入
  108.             for(int i =0; i < sparseArray.length; i++) {
  109.                 for(int j = 0; j < sparseArray[i].length; j++) {
  110.                     ow.write(sparseArray[i][j]+" ");
  111.                 }
  112.             }
  113.         } catch (IOException e) {
  114.             e.printStackTrace();
  115.         } finally {
  116.             //关闭流
  117.             try {
  118.                 if(ow != null){
  119.                     ow.flush();
  120.                     ow.close();
  121.                 }
  122.             } catch (IOException e) {
  123.                 e.printStackTrace();
  124.             }
  125.         }
  126.     }
  127. }

2.3、数组-相关问题-列举

  1. 1、为什么大多数编程语言中，数组要从0开始编号，而不是1开始呢？
  2.     1-1、答：-- 下标即为 偏移量(offset),
  3.         假设a代表数组首地址，a[0]=偏移量为0的位置，即首地址，那么a[k]=偏移量k个type_size的位置，
  4.             a[k]地址公式为：a[k]_address = base_address + k * type_size
  5.         假设数组从 1 开始计数，那我们计算数组元素，a[k] 的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size
  6.     1-2、问题总结：从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对CPU来说就是多了一次减法指令。