数据结构与算法

cccs7 Lv5
  2023-01-05 13:21:22 2023-01-05 13:21 Created   2023-06-29 23:12:05 2023-06-29 23:12 Updated      1.5k Words  6 Mins  

数据结构与算法

Java 描述的 数据结构

韩顺平 - 数据结构与算法（Java 描述） https://www.bilibili.com/video/BV1E4411H73v/?p=11&share_source=copy_web&vd_source=72700974488313ca2dbc27bc0ae377e9


数据结构和算法概述

数据结构和算法的关系

  • 数据 data 结构 structure 是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以写出更好的代码。
  • 要学习好数据结构 就要多多考虑如何将生活中的问题用程序去解决
  • 程序 = 数据结构 + 算法
  • 数据结构是算法的基础，换言之，想要学好算法，需要把数据结构学好

线性结构和非线性结构

数据结构包括 ： 线性结构和非线性结构


线性结构

  • 线性结构作为最常用的数据结构，其特点是 数据元素之间存在一对一的 线性关系
  • 线性结构有两种不同的存储结构，即 顺序存储结构（数组） 和 链式存储结构。 顺序存储的线性表称为顺序表，顺序表中的 **存储元素是连续 ** 的
  • 链式存储的线性表称为链表，链表中的 存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
  • 线性结构常见的有 ： 数组、队列、链表和栈

非线性结构

非线性结构包括 ： 二维数组、多维数组、广义表、树、图


数据结构

稀疏数组和队列

稀疏数组

基本介绍

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


稀疏数组的处理方法
  1. 记录数组 **一共有几行几列，有多少个不同的 ** 值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而 缩小程序 的规模

image-20230112225954562
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package com.cs7eric.sparsearray;

public class SparseArray {
    public 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;
        System.out.println("原始的二维数组~~");
        int[][] chessArr2 = chessArr1;
        int count = chessArr1.length;

        int i;
        int i;
        int var7;
        int var8;
        for(i = 0; i < count; ++i) {
            int[] row = chessArr2[i];
            int[] var9 = row;
            var8 = row.length;

            for(var7 = 0; var7 < var8; ++var7) {
                i = var9[var7];
                System.out.printf("%d\t", i);
            }

            System.out.println();
        }

        int sum = 0;

        for(i = 0; i < 11; ++i) {
            for(count = 0; count < 11; ++count) {
                if (chessArr1[i][count] != 0) {
                    ++sum;
                }
            }
        }

        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        count = 0;

        int i;
        for(i = 0; i < 11; ++i) {
            for(i = 0; i < 11; ++i) {
                if (chessArr1[i][i] != 0) {
                    ++count;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = i;
                    sparseArr[count][2] = chessArr1[i][i];
                }
            }
        }

        System.out.println();
        System.out.println("得到稀疏数组为~~~~");

        for(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 = new int[sparseArr[0][0]][sparseArr[0][1]];

        for(i = 1; i < sparseArr.length; ++i) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        System.out.println();
        System.out.println("恢复后的二维数组");
        int[][] var18 = chessArr2;
        var8 = chessArr2.length;

        for(var7 = 0; var7 < var8; ++var7) {
            int[] row = var18[var7];
            int[] var13 = row;
            int var12 = row.length;

            for(int var11 = 0; var11 < var12; ++var11) {
                int data = var13[var11];
                System.out.printf("%d\t", data);
            }

            System.out.println();
        }

    }
}


队列

基本介绍
  • 队列是一个 有序列表，可以是 数组或者 链表 来实现
  • 遵循 先入先出 的原则。即 ： 先存入队列的数据，要先取出。后存入的要后取出

image-20230112231102044
数组模拟队列思路
  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 maxSize 是该队列的最大容量
  • 因为 队列的输出、输入 是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会 随着数据输出而改变，而 rear 则是随着数据输入而改变。如图所示
image-20230112231905837
  • 当我们将数据存入 队列时 称为 addQueue，addQueue 的处理需要有两个步骤，思路分析：
    1. 将尾指针往后移 ： rear + 1 ，当 front == rear 为 空
    2. 若 尾指针 rear 小于 队列的最大下标 maxSize - 1，则 将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize - 1 队列满

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package com.cs7eric.repo.queue;


/**
 * 用数组模拟队列
 *
 * @author cs7eric
 * @date 2023/02/03
 */
public class ArrayQueueDemo {

    public static void main(String[] args) {

        ArrayQueue arrayQueue = new ArrayQueue(2);
        arrayQueue.add(1);
        arrayQueue.add(2);
        arrayQueue.list();
        System.out.println(arrayQueue.isFull());
        System.out.println(arrayQueue.isEmpty());
        System.out.println(arrayQueue.head());
    }
}
/**
 * 用数组模拟队列  - 编写一个 ArrayQueue 类
 *
 * @author cs7eric
 * @date 2023/02/03
 */
class ArrayQueue{

    /**
     * 数组的最大容量
     */
    private int maxSize;

    /**
     *  队列头指针
     */
    private int front;

    /**
     * 队列 尾指针
     */
    private int rear;

    /**
     *  该数组用于存放数据
     */
    private int[] array;

    // 创建队列
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        array = new int[maxSize];
        front = -1;  // 指向队列头部的前一个位置
        rear = -1; // 指向队列尾
    }

    /**
     * 判空
     *
     * @return boolean
     */
    public boolean isEmpty(){

        return rear == front ;
    }

    /**
     * 判断队列是否是满的
     *
     * @return boolean
     */
    public boolean isFull(){

        return rear == maxSize - 1;
    }

    /**
     * 添加数据
     *
     * @param elem  待添加的元素
     */
    public void add(int elem){

        if (isFull())    return;
        array[++rear] = elem;
    }

    /**
     * 得到 队列元素
     *
     * @return int
     */
    public int get(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return array[++front];
    }

    /**
     *  遍历所有数据
     */
    public void list(){

        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        for (int iterator : array){
            System.out.println(iterator);
        }
    }

    /**
     * 查看 队列head 元素
     *
     * @return int
     */
    public int head(){

        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return array[front+1];
    }
}
  • Title: 数据结构与算法
  • Author: cccs7
  • Created at: 2023-01-05 13:21:22
  • Updated at: 2023-06-29 23:12:05
  • Link: https://blog.cccs7.icu/2023/01/05/数据结构/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
数据结构与算法
  1. 数据结构和算法概述
    1. 数据结构和算法的关系
    2. 线性结构和非线性结构
      1. 线性结构
      2. 非线性结构
  2. 数据结构
    1. 稀疏数组和队列
      1. 稀疏数组
        1. 基本介绍
          1. 稀疏数组的处理方法
          2. 代码实现
      2. 队列
        1. 基本介绍
        2. 数组模拟队列思路
          1. 代码实现