栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

尚硅谷01 数据结构与算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

尚硅谷01 数据结构与算法

数据结构与算法的关系

几个实际编程中遇到的问题

要想写出优秀的算法,首先应该能读懂别人写好的算法。

将生活中遇到的实际问题,使用程序来解决

线性结构和非线性结构

线性结构和非线性结构的关系:
数据结构:线性结构 + 非线性结构
线性结构:数据元素之间是 一对一 的关系
非线性结构:数据元素之间是 一对多 或 多对多 的关系
线性结构的存储方式:顺序存储 + 链式存储
顺序存储:数据存储在一片连续的地址空间中
链式存储:数据的存储空间可能并不连续。元素节点中存储的是「数据元素」和「相邻元素的地址信息」
常见的线性结构:数组、链表(两种不同的存储方式)、栈、队列
非线性结构:树、图、(集合)、二维数组、多维数组、广义表

1. 线性结构

2. 非线性结构

一、稀疏数组
1. 应用场景

普通的二维数组记录数据时,可能存放大量的无效数据,导致存储空间的浪费

2. 基本介绍

稀疏数组的应用背景:二维数组中存放大量的无效数据时,可使用稀疏数组

稀疏数组的处理方法:

  1. 记录数组一共有 几行几列、有多少个有效数据(第一行)
  2. 将有效数据的 行、列、值 存储到数组中(其余行)

二维数组和稀疏数组的对应关系图:

第一行:数组信息
其余行:有效数据信息

3. 案例

有大量的无效数据0

4. 分析

二维数组如何转换为稀疏数组:
需要知道
稀疏数组的行:有效数据的个数+1
稀疏数组的列:3
有效数据的个数:设置一个计数器,通过遍历来获取
有效数据的信息:通过遍历数组来获取

稀疏数组如何转换为二维数组:
根据稀疏数组的第一行:创建二维数组
遍历稀疏数组:然后为二维数组赋值

最终保存到磁盘即可(IO)

整体思路:

5. 代码实现:






6. 课后题:

7. 完整代码
package com.SparseArray_01;


import java.io.*;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class SparseArray {
    public static void main(String[] args) {
        
        // 1. 创建一个二维数组,并存储数据
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[3][4] = 1;
        chessArr1[3][3] = 2;
        // 2. 输出二维数组中的数组
        System.out.println("二维数组的内容:");
        for(int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                System.out.print(chessArr1[i][j] + "t");
            }
            System.out.println();
        }
        // 3. 将二维数组转换为稀疏数组
        int sum = 0;    // 记录有效数据的个数
        for(int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //稀疏数组
        int sparseArray[][] = new int[sum+1][3];
        sparseArray[0][0] = 11;
        sparseArray[0][1] = 11;
        sparseArray[0][2] = sum;
        //填充有效数据
        int count = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = chessArr1[i][j];
                }
            }
        }
        // 4. 输出稀疏数组中的数据
        System.out.println("稀疏数组如下图所示:");
        for (int i = 0; i < sparseArray.length; i++) {
            System.out.print(sparseArray[i][0] + "t" + sparseArray[i][1] + "t" + sparseArray[i][2] + "n");
        }
        // 5. 将稀疏数组的数据转为二维数组
        int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        // 6. 输出二维数组中的数据
        System.out.println("稀疏数据转为二维数组后,如下图所示:");
        for (int i = 0; i < chessArr2.length; i++) {
            for (int j = 0; j < chessArr2[i].length; j++) {
                System.out.print(chessArr2[i][j] + "t");
            }
            System.out.println();
        }
        // 7. 将稀疏数组写入到 map.txt 文件中
        PrintWriter pw = null;
        try {
            pw = new PrintWriter("D:/map.txt");
            StringBuffer stringBuffer = new StringBuffer();
            for (int i = 0; i < sparseArray.length; i++) {
                for (int j = 0; j < sparseArray[i].length; j++) {
                    stringBuffer.append(sparseArray[i][j] + "t");
                }
                stringBuffer.append("n");
            }
            pw.println(stringBuffer);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }finally {
            pw.close();
        }
        // 8. 将稀疏数组从 map.txt 文件中读取出来
        try {
            List lines = Files.readAllLines(Paths.get("D:/map.txt"), StandardCharsets.UTF_8);
            // 这里lines集合,最后一行是空行,需要省去
            for (int i = 0; i < lines.size()-1; i++) {
                // 这里在分割时要注意,如果使用" "来分割的话,会将t也存入到数组中,这里我们只想将字符串存入到数组中
                String[] s = lines.get(i).split("t");
                for (int j = 0; j < s.length; j++) {
                    sparseArray[i][j] = Integer.parseInt(s[j]);
                }
            }
        } catch (IOException ioException) {
            ioException.printStackTrace();
        }
        // 9. 从文件中读出稀疏数组的结果,打印在控制台
        System.out.println("从文件中读出稀疏数组的结果:");
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.print(sparseArray[i][j] + "t");
            }
            System.out.println();
        }
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970210.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号