菜鸟窝-数据结构与算法之稀疏数组

---

categories:

• 数据结构与算法
  tags:
• 算法引入，稀疏数组
  title: 数据结构与算法之稀疏数组
  date:

---

数据结构与算法

• 数据结构是组织（包括存储、处理等）数据的方式，是算法的基础

• 程序=数据结构+算法；数据结构分为线性和非线性

• 五子棋问题、约瑟夫问题等都离不开数据结构与算法

• 常用算法案例：修路问题、最短路径、汉诺塔、八皇后等问题

稀疏数组

• 一个数组中大部分元素为0或者为同一个值的数组，可以用稀疏表示

• 处理方法:

  1、记录数组几行几列，多少不同的值

  2、将不同值的元素的行列值记录在小规模数组达到缩小程序规模的目的

• 二维数组转稀疏数组的思路：遍历原始数组，得到有效数据个数sum->创建行sum+1列3的稀疏数组sparseArr->数据存入->写入磁盘
• 稀疏数组转二维数组：读取文件，根据第一行的数据创建数组，读取几行后的数据，并赋给原始的二维数组

row	col	val

1. 稀疏数组的实现：

package com.atguigu;

import java.io.*;
public class sparseArray {
    public static void main(String[] args) {
        //创建原始二维数组
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 2;
        //输出显示原始二维数组
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        //定义sum来计数数组中有多少不同的数据
        int sum=0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //二维转稀疏
        int sparseArr[][] = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        int count=0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        //得到稀疏数组并输出
        System.out.println("稀疏数组");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
        //保存文件到磁盘
        try {
            System.out.println("保存稀疏数组为map.data");
            File f = new File("d:\\ym\\map.data");
            FileOutputStream fos = new FileOutputStream(f);//字符输出流写入
            OutputStreamWriter osw = new OutputStreamWriter(fos,"utf-8");//字节输出流写入
            System.out.println("写入中");
            for (int i = 0; i < sparseArr.length; i++) {
                osw.write(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ",");
            }
            osw.close();
            fos.close();
            System.out.println("写入成功");
            System.out.println("读取中");
            FileInputStream fis = new FileInputStream(f);//字符输入流读取
            InputStreamReader isr = new InputStreamReader(fis,"utf-8");//字节输入流读取
            StringBuffer sb = new StringBuffer();
            while (isr.ready()) {
                sb.append((char)isr.read());
            }
            isr.close();
            fis.close();
            System.out.println("读取成功");
            String ss = sb.toString();
            String[] sb1 = sb.toString().split(",");
            System.out.printf("从磁盘读取的字符串为：\n%s\n", ss);//格式化输出
            //恢复稀疏数组
            int s=0;
            int[][] sparseArr1 = new int[sb1.length/3][3];
            sparseArr1[0][0] = Integer.parseInt(sb1[0]);
            sparseArr1[0][1] = Integer.parseInt(sb1[1]);
            sparseArr1[0][2] = Integer.parseInt(sb1[2]);
            for(int i = 3; i < sb1.length; i += 3) {
                s++;
                sparseArr1[s][0] = Integer.parseInt(sb1[i]);
                sparseArr1[s][1] = Integer.parseInt(sb1[i+1]);
                sparseArr1[s][2] = Integer.parseInt(sb1[i+2]);
            }
            System.out.println("还原后的稀疏数组为：");
            for(int i = 0; i < sparseArr1.length; i++) {
                System.out.printf("%d\t%d\t%d\n", sparseArr1[i][0], sparseArr1[i][1], sparseArr1[i][2]);
            }
            //稀疏转二维
            int row = sparseArr1[0][0];
            int col = sparseArr1[0][1];
            int[][] chessArr2 = new int[row][col];
            for (int i = 1; i < sparseArr1.length; i++) {
                chessArr2[sparseArr1[i][0]][sparseArr1[i][1]] = sparseArr1[i][2];
            }
            for (int[] rw : chessArr2) {
                for (int data : rw) {
                    System.out.print(data + "\t");
                }
                System.out.println();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

菜鸟窝