数据结构与算法(java版)

数据结构与算法

数据结构和算法概述

数据结构和算法的关系

数据data结构(structure)是一门研究组织数据方式的学科,有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。

要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决。

程序=数据结构+算法

数据结构是算法的基础,换言之,想要学好算法,需要把数据结构学到位。

线性结构

线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系

线性结构有两种不同的存储结构,即顺序存储结构(数组和链式存储结构(链表)。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的

链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息

线性结构常见的有:数组、队列、链表和栈

稀疏数组

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。

记录数组一共有几行几列,有多少个不同的值

把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

二维数组转换成稀疏数组

思路:

遍历原始的二维数组,得到有效数据的个数sum
根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
将二维数组的有效数据数据存入到稀疏数组

稀疏数组转换成原始的二维数组思路

先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的chessArr2=int[11[11】
在读取稀疏数组后几行的数据,并赋给原始的二维数组即可.

代码实现

创建二维数组

//稀疏数组
public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0:没有棋子,1:黑子,2:蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        //输出原始的二维数组
        for (int[] row : chessArr1){
            for (int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}
增强for循环

for(数据类型 变量名 :遍历的目标){ //数据类型 变量名:声明一个变量用来接收遍历目标遍历后的元素

}

如果是实现了Iterable接口的对象或者是数组对象都可以使用增强for循环。

普通for循环可以没有遍历的目标,而增强for循环一定要有遍历的目标

printf()函数

Java中的printf()方法是类似于C语言的printf()风格的一种格式化输出功能。printf()并不使用重载的 “+” 操作符(C没有重载)来连接引号内的字符串或者字符串变量,而是使用特殊的占位符来表示数据将来的位置。而且它将插入格式化字符串的参数,按照顺序以逗号隔开,在字符串后面顺次排列。
这些占位符在Java中被称为 格式修饰符
%d表示是一个整数

\t是补全当前字符串长度到8的整数倍,最少1个最多8个空格

public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0:没有棋子,1:黑子,2:蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        //输出原始的二维数组
        System.out.println("原始的二维数组");
        for (int[] row : chessArr1){
            for (int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        /**
         * 二维数组转换成稀疏数组
         *   遍历原始的二维数组,得到有效数据的个数sum
         *   根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
         *   将二维数组的有效数据数据存入到稀疏数组
         */
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; 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;  //count用于记录第几个非0数据
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println();
        System.out.println("转换为稀疏数组如下:");
        for (int i = 0;i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
        }
        System.out.println();

        /**
         * 稀疏数组转换成原始的二维数组思路
         * 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的chessArr2=int[11[11】
         * 在读取稀疏数组后几行的数据,并赋给原始的二维数组即可.
         */
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++){
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println();
        System.out.println("恢复后的二维数组");
        for (int[] row : chessArr2){
            for (int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}

课后练习

要求:
1)在前面的基础上,将稀疏数组保存到磁盘上,比如map.data
2)恢复原来的数组时,读取map.data进行恢复

代码实现

思路:

使用FileOutputStream将稀疏数组写入chess.text文件

循环遍历稀疏数组
如果是当前行的第三个元素,直接写入数据值。
如果不是第三个元素,以逗号结尾的形式写入数据值,以便后续读取时可以通过逗号进行分割。
String.valueOf(a) 将整数 a 转换为字符串。

使用 BufferedReader 从 chess.text 文件中逐行读取数据。

稀疏矩阵的第一行包含稀疏数组的行数和列数,从中获取行数 row 和列数 col,并初始化 chessArray2 数组。

System.out.println("把稀疏数组保存到文件中.....");
        //使用FileOutputStream将稀疏数组写入chess.text文件
        FileOutputStream fileOutputStream = new FileOutputStream(new File("chess.text"));
        /**
         * 循环遍历稀疏数组
         * 如果是当前行的第三个元素,直接写入数据值。
         * 如果不是第三个元素,以逗号结尾的形式写入数据值,以便后续读取时可以通过逗号进行分割。
         * String.valueOf(a) 将整数 a 转换为字符串。
         */
        for (int i = 0; i< sparseArr.length;i++){
            for (int j = 0;j< sparseArr[0].length;j++){
                int a = sparseArr[i][j];
                if(j == 2){
                    fileOutputStream.write((String.valueOf(a)).getBytes());
                }else {
                    fileOutputStream.write((String.valueOf(a)+",").getBytes());
                }
            }
            fileOutputStream.write("\n".getBytes());
        }
        System.out.println("-----读取文件中的稀疏数组并恢复为原来的数组-------");

        //使用 BufferedReader 从 chess.text 文件中逐行读取数据。
        BufferedReader bufferedReader = new BufferedReader(new FileReader("chess.text"));
        String line = null;
        int c = 0;
        String row = null;
        String col = null;

        //第一行(稀疏矩阵的第一行)包含稀疏数组的行数和列数,从中获取行数 row 和列数 col,并初始化 chessArray2 数组。
        int[][] chessArray2 = null;
        while((line = bufferedReader.readLine())!= null){
            c++;
            if(c==1){//稀疏矩阵的第一行
                String[] array = line.split(",");//以,为分割读取文件
                row = array[0];
                col = array[1];
                chessArray2 = new int[Integer.parseInt(row)][Integer.parseInt(col)];
            }else {
                String[] array = line.split(",");
                String row2 = array[0];
                String col2 = array[1];
                String val2 = array[2];
                chessArray2[Integer.parseInt(val2)][Integer.parseInt(col2)] = Integer.parseInt(val2);
            }
        }
        for (int[] r:chessArray2){
            for (int item:r){
                System.out.printf("%d\t",item);
            }
            System.out.println();
        }
        fileOutputStream.close();

队列

队列是一个有序列表,可以用数组(顺序存储)或是链表(链式存储)来实现

遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出

使用数组实现队列

public class ArrayQueue {
    public static void main(String[] args) {
        //测试
        //创建队列
        ArrayQueue1 arrayQueue1 = new ArrayQueue1(6);
        char key = ' ';     //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列中取出数据");
            System.out.println("h(head): 查看队列头数据");
            key = scanner.next().charAt(0);     //接收一个字符
            switch (key) {
                case 's':
                    arrayQueue1.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    arrayQueue1.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue1.getQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':   //查看队列头的数据
                    try {
                        int res = arrayQueue1.headQueue();
                        System.out.printf("队列头的数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

//使用数组模拟队列,编写一个ArrayQueue类
class ArrayQueue1 {
    private int maxSize;    //表示数组的最大容量
    private int front;  //队列头
    private int rear;   //队列尾
    private int[] arr; //存放数据,模拟队列

    //创建队列的构造器
    public ArrayQueue1(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;     //指向队列头部,指向队列头的前一个位置
        rear = -1;      //指向队列尾的数据,队列的最后一个数据
    }
    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }
    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    //添加数据到队列
    public void addQueue(int n) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列已满,不能添加数据");
            return;
        }
        rear++;     //让rear后移一位
        arr[rear] = n;
    }
    //获取队列的数据,出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            //抛出异常
            throw new RuntimeException("队列为空,不能取出数据");
        }
        front++;    //front后移
        return arr[front];
    }
    //显示队列的所有数据
    public void showQueue() {
        //遍历
        if (isEmpty()) {
            System.out.println("队列为空,没有数据~~");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }
    //显示队列的头数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空没有数据");
        }
        return arr[front+1];
    }
}

非线性结构

二维数组,多维数组,广义表,树结构,图结构
此笔记参考的尚硅谷的数据结构与算法课程

热门相关:脑洞大爆炸   我的妻子   新书   与你相恋的小时光   我姐姐是一个夜话作家