数据结构中的基本结构分析

数据结构

  • 一般将数据结构分为两大类：线性结构 和 非线性结构 。

    线性数据结构有 线性表、栈、队列、串、数组和文件；非线性数据结构有 树和图。

线性表

  • * 线性表的数据结构是 n 个数据元素的有限序列：

  $\left( {{{\rm{a}}_1},{a_2} \cdots {a_n}} \right)$
* n 为线性表的长度（$n \ge 0$）, `n=0` 的表称为空表。

  • 数据元素呈线性关系。必存在唯一的一个称为 “第一个” 的数据元素；必须在唯一的一个称为 “最后一个” 的元素；除第一个元素外，每个元素都有唯一的一个先驱元素，除最后一个元素外，每个元素都有且只有一个后继元素。

  • 所有数据元素在同一个线性表中必须是相同的数据类型。

  • 线性表按照其存储结构可以分为 顺序表 和 链表 。

    用顺序存储结构存储的线性表称为 顺序表 。

    用链式存储结构存储的线性表称为 链表 。

  • 将线性表中的数据元素依次存储在某个区域中，所形成的表称为 顺序表 。一维数组就是用顺序方式存储的线性表。

Terwer...大约 2 分钟后端开发JavaSE线性表元素结构存储称为数据数据结构datadata-structurestructure
LinkedList源代码深入剖析

集合框架中的接口

  • 除了类集接口之外，类集也是用 Comparator ， Iterator 和 ListIterator 接口。

  • 简单地说， Comparator 接口定义了两个对象如何比较；Iterator 和 ListIterator 接口枚举类集中的对象。

  • 为了在他们的使用中提供最大的灵活性，类集接口允许对一些方法进行选择。可选择的方法使得使用者可以更改类集中的内容。支持这些方法额类集被称为可修改的（modifiable）。不允许修改其内容的类集被称为不可修改的（unmodifiable）。如果对一个不可修改发类集使用这些方法，将引发一个 UnsupportedOperationException 异常。 所有内置的类集都是可修改的 。

  • 调用 add()​​​ 方法可以将对象加入类集，注意 add() 带一个 Object 类的参数。因为 Object 是所有类的超类，所以任何类型的对象都可以被存储在一个类集中。然而原始类型 不行 。例如，一个类集不能直接存储类型 int ，char ， double 等的值。如果想存储这些对象，也可以使用原始类型包装器。

    可以调用 addAll()​​​ 方法将一个类集的全部内容增加到另一个类集中。

  • 可以通过调用 remove()​​​ 方法将一个对象删除。为了删除一组对象，可以调用 removeAll()​​​ 方法。调用 retainAll()​​​ 方法可以将除了一组指定的元素之外的所有元素删除。为了清空类集，可以调用 clear()​​​ 方法。

  • 通过调用 contains()​​​ 方法可以确定一个类集中是否包含了一个指定的对象。

  • 为了确定一个类集是否包含了另一个类集的全部元素，可以调用 contsinsAll()​​ 方法。

  • 当一个类集是空的时候，可以通过调用 isEmpty()​​ 方法来予以确定。

  • 调用 size()​​ 方法可以获得类集中当前元素的个数。

  • ​toArray()​ 方法返回一个数组，这个数组包含了存储在调用类集中的元素。通过再类集合数组之间提供一条路径，可以充分利用这两者的优点。

  • 一个更加重要的方法是 iterator()​ ，该方法对类集返回一个迭代程序。当使用一个类集框架时，迭代程序对于成功的编程来说是至关重要的。

  • ​Collection​ ：集合层次中的根接口，JDK 没有提供这个接口的直接实现类。

  • ​Set​ ：不能包含重复的元素。SortedSet​ 是一个按照升序排列元素的 Set​ 。

  • ​List​ ：是一个有序的集合，可以包含重复的元素。提供了按照索引访问的方式。

  • ​Map​ ：包含了 key-value 对。Map 不能包含重复的 key 。SortedMap​ 是一个按照升序排列 key 的 Map​ 。

Terwer...大约 9 分钟后端开发JavaSE方法元素调用集合javalinkedlistcollection
ArrayList深入分析

基本方法

使用由 toString()​ 方法提供的默认的转换显示类集的内容，toString()​ 方法是从 AbstractCollection()​ 继承下来的。对于例子来说足够，但是通常情况下会重写此方法。

 public class ArrayListTest1 {
   public static void main(String[] args) {
     ArrayList arrayList = new ArrayList();
     arrayList.add("hello");
     arrayList.add("world");
     arrayList.add("world");
     arrayList.add("welcome");
 ​
     String s1 = (String) arrayList.get(0);
     String s2 = (String) arrayList.get(1);
     String s3 = (String) arrayList.get(2);
     String s4 = (String) arrayList.get(3);
 ​
     System.out.println(s1);
     System.out.println(s2);
     System.out.println(s3);
     System.out.println(s4);
 ​
     System.out.println("-------------");
     for (int i = 0; i < arrayList.size(); i++) {
       System.out.println(arrayList.get(i));
     }
 ​
     // arrayList.clear();
     // System.out.println(arrayList.size());
     // System.out.println(arrayList.isEmpty());
 ​
     arrayList.remove(0);
 ​
     System.out.println("-------------");
     for (int i = 0; i < arrayList.size(); i++) {
       System.out.println(arrayList.get(i));
     }
 ​
     arrayList.remove("welcome");
     System.out.println("-------------");
     for (int i = 0; i < arrayList.size(); i++) {
       System.out.println(arrayList.get(i));
     }
 ​
     System.out.println("-----------------");
 ​
     arrayList.add("aaa");
     arrayList.add("bbb");
 ​
     System.out.println(arrayList.indexOf("world"));
     System.out.println(arrayList.lastIndexOf("world"));
     System.out.println(arrayList.indexOf("aaa"));
   }
 }
Terwer...大约 5 分钟后端开发JavaSE结果包装操作转换基本arraylistdeepanalysis
常用的Java开发IDE

IDE（Integrated Development Environment），集成开发环境。

  1. NetBeans。https://netbeans.org

  2. JBuilder。

  3. IntelliJ IDEA

    https://www.jetbrains.com/idea/

  4. Eclipse

    中科大 eclipse 镜像使用帮助：http://mirrors.ustc.edu.cn/help/eclipse.html#id1

    Eclipse helios 下载：https://www.eclipse.org/downloads/packages/release/helios/r

    百度网盘下载链接: https://pan.baidu.com/s/1NoeSBflyGAzqR1hEUT0bTw 请发邮件至 youweics@163.com 获取提取码

  5. MyEclipse

    MyEclipse8.6 下载地址：链接: https://pan.baidu.com/s/1XABCEUwg6NLNThgniAA1mQ 请发邮件至 youweics@163.com 获取提取码

Terwer...小于 1 分钟后端开发JavaSE集成开发环境中科大镜像eclipsejavaideajavase
常量与Java集合框架简介

  1. 对于 Java 中的常量的命名规则：所有字母的单词都是大写，如果有多个单词，那马使用下划线 _​ 连接。

    ​public static final int AGE_OF_PERSION = 20;​

  2. Java Collection

    ​

    ​

    ​

    ​

    ​

    ​

    ​

    ​

    ​

Terwer...小于 1 分钟后端开发JavaSE常量命名规则javajavase集合collection
Java数组的查找方式及二分查找

  1. 数组查找

    public class ArraySearchTest {
    public static void main(String[] args) {
        int[] a = new int[]{1, 5, 6, 7, 10, 3, 9};
        int value = 9;

        int result = search(a, 9);

        if (result > 0) {
            System.out.println("找到了，索引为" + result);
        } else {
            System.out.println("未找到");
        }
    }

    public static int search(int[] array, int value) {
        int index = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                index = i;
                break;
            }
        }
        return index;
    }
}

  2. 二分查找（Binary Search）：待查找的数组必须有序

    1,2,3,4,5,6,7,8,9

    10

    public static int binarySearch(int[] array, int value) {
        int left = 0;
        int right = array.length - 1;
        int middle;

        while (left <= right) {
            middle = (left + right) / 2;

            for (int k = 0; k < array.length; k++) {
                System.out.print(array[k]);
                if (k == middle) {
                    System.out.print("#");
                }
                System.out.print(" ");
            }

            System.out.println();

            if (array[middle] == value) {
                return middle;
            }

            if (value > array[middle]) {
                left = middle + 1;
            }

            if (value < array[middle]) {
                right = middle - 1;
            }
        }

        return -1;
    }

    效果

    1 2 3 4 5
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9# 
找到了，索引为8

  3. 随机生成50个数字（整数），每个数字的范围是[10,50]，统计每个数字出现的次数以及出现次数最多的数字与它的个数 ，最后将每个数字及其出现次数打印出来，如果某个数字出现次数为 0，则不要打印它。打印时按照数字的升序排列。

    import java.util.Random;

/**
 * @name: WorkTest
 * @author: terwer
 * @date: 2022-10-19 00:10
 **/
public class WorkTest {
    public static void main(String[] args) {
        int[] nums = new int[50];

        Random random = new Random();
        for (int i = 0; i < nums.length; i++) {
            nums[i] = 10 + random.nextInt(50 - 10 + 1);
        }


        for (int j = 10; j <= 50; j++) {
            int count = 0;
            for (int m = 0; m < nums.length; m++) {
                if (nums[m] == j) {
                    count++;
                }
            }

            if (count > 0) {
                System.out.println(j + "出现的次数：" + count);
            }
        }


//        for (int k = 0; k < nums.length; k++) {
//            System.out.println(nums[k]);
//        }
    }
}

    更好的实现：

    import java.util.Random;

/**
 * @name: WorkTest
 * @author: terwer
 * @date: 2022-10-19 00:10
 **/
public class WorkTest2 {
    public static void main(String[] args) {
        int[] count = new int[41];

        Random random = new Random();
        for (int i = 0; i < 50; i++) {
            int number = 10 + random.nextInt(50 - 10 + 1);
            System.out.println(number);
            count[number - 10]++;
        }


        for (int j = 0; j < count.length; j++) {
            if (count[j] == 0) {
                continue;
            }

            System.out.println((10 + j) + "出现的次数：" + count[j]);
        }

        int max = count[0];
        int maxNum = 10;
        for (int k = 0; k < count.length; k++) {
            if (max < count[k]) {
                max = count[k];
            }

            if (max == count[k]) {
                maxNum = k + 10;
                System.out.println(maxNum);
            }
        }
        System.out.println("最大的数字出现的次数：" + max);
    }
}
Terwer...大约 2 分钟后端开发JavaSE查找数组二分必须有序二分查找searchbinary-search
冒泡排序、交换排序与快速排序

  1. 冒泡排序

    思路：

    比如：3，5，6，2，4，7

    结果：2，3，4，5，6，7

    public class BubbleSort {
    public static void main(String[] args) {
        int[] a = new int[]{3, 5, 6, 2, 4, 7};

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();

        bubbleSort(a);

        System.out.println();
        System.out.println("-------------------");

        for (int j = 0; j < a.length; j++) {
            System.out.print(a[j] + " ");
        }
    }

    public static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            System.out.println("第" + (i) + "次比较");

            for (int j = 0; j < a.length - i - 1; j++) {
                System.out.println("第" + (j) + "个数与第" + (j + 1) + "个数比较");
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    System.out.println("交换大小");
                }
            }

            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k] + " ");
            }
            System.out.println();
            System.out.println("====================");
        }
    }
}

    结果

    3 5 6 2 4 7 
第0次比较
第0个数与第1个数比较
第1个数与第2个数比较
第2个数与第3个数比较
交换大小
第3个数与第4个数比较
交换大小
第4个数与第5个数比较
3 5 2 4 6 7 
====================
第1次比较
第0个数与第1个数比较
第1个数与第2个数比较
交换大小
第2个数与第3个数比较
交换大小
第3个数与第4个数比较
3 2 4 5 6 7 
====================
第2次比较
第0个数与第1个数比较
交换大小
第1个数与第2个数比较
第2个数与第3个数比较
2 3 4 5 6 7 
====================
第3次比较
第0个数与第1个数比较
第1个数与第2个数比较
2 3 4 5 6 7 
====================
第4次比较
第0个数与第1个数比较
2 3 4 5 6 7 
====================

-------------------
2 3 4 5 6 7

    动画

    ​https://visualgo.net/zh/sorting?slide=6-5​​

    简记

  2. 交换排序

    所谓交换，是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。交换排序本文介绍两种，冒泡排序（bubble sort）和快速排序。

  3. 快速排序

    假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个 10 个数进行排序。首先在这个序列中随便找一个数作为基准数。选取第一个数 6 作为基准数。在这个序列中,将所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排列： 3 1 2 5 4 6 9 7 10 8 在初始状态下，数字 6 在序列的第 1 位。我们的目标是将 6 挪到序列中间的某个位置，假设这个位置是 k。现在就需要寻找这个 k，并且以第 k 位为分界点，左边的数都小于等于 6，右边的数都大于等于 6。

    快速排序

    方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换他们。这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i”和“哨兵 j”。刚开始的时候让哨兵 i 指向序列的最左边（即 i=1），指向数字 6。让哨兵 j 指向序列的最右边（即=10），指向数字。

    ​​

    首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先出动，这一点非常重要（请自己想一想为什么）。哨兵 j 一步一步地向左挪动（即 j–），直到找到一个小于 6 的数停下来。接下来哨兵 i 再一步一步向右挪动（即 i++），直到找到一个数大于 6 的数停下来。最后哨兵 j 停在了数字 5 面前，哨兵 i 停在了数字 7 面前。

    ​
    现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列如下：6 1 2 5 9 3 4 7 10 8

    ​

    ​

    ​
    到此，第一次交换结束。接下来开始哨兵 j 继续向左挪动（再友情提醒，每次必须是哨兵 j 先出发）。他发现了 4（比基准数 6 要小，满足要求）之后停了下来。哨兵 i 也继续向右挪动的，他发现了 9（比基准数 6 要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

    6 1 2 5 4 3 9 7 10 8

    ​

    第二次交换结束，“探测”继续。哨兵 j 继续向左挪动，他发现了 3（比基准数 6 要小，满足要求）之后又停了下来。哨兵 i 继续向右移动，糟啦！此时哨兵 i 和哨兵 j 相遇了，哨兵 i 和哨兵 j 都走到 3 面前。说明此时“探测”结束。我们将基准数 6 和 3 进行交换。交换之后的序列如下：

    3 1 2 5 4 6 9 7 10 8

    ​

    ​

    ​
    ​
    到此第一轮“探测”真正结束。此时以基准数 6 为分界点，6 左边的数都小于等于 6，6 右边的数都大于等于 6。回顾一下刚才的过程，其实哨兵 j 的使命就是要找小于基准数的数，而哨兵 i 的使命就是要找大于基准数的数，直到 i 和 j 碰头为止。
    OK，解释完毕。现在基准数 6 已经归位，它正好处在序列的第 6 位。此时我们已经将原来的序列，以 6 为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为 6 左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理 6 左边和右边的序列即可。现在先来处理 6 左边的序列现吧。

    左边的序列是“3 1 2 5 4”。请将这个序列以 3 为基准数进行调整，使得 3 左边的数都小于等于 3，3 右边的数都大于等于 3。好了开始动笔吧

    如果你模拟的没有错，调整完毕之后的序列的顺序应该是：

    2 1 3 5 4

    OK，现在 3 已经归位。接下来需要处理 3 左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以 2 为基准数进行调整，处理完毕之后的序列为“1 2”，到此 2 已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：

    1 2 3 4 5 6 9 7 10 8

    对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下

    1 2 3 4 5 6 7 8 9 10
    到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

    
import java.util.Arrays;

/**
 * @name: QuickSort
 * @author: terwer
 * @date: 2022-10-19 00:01
 **/

public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {11, 24, 5, 32, 50, 34, 54, 76};
        System.out.println("快速排序前:" + Arrays.toString(nums));
        quickSort(nums, 0, nums.length - 1);
        System.out.println("快速排序后:" + Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start > end) return;
        int i, j, base;
        i = start;
        j = end;
        base = nums[start];
        while (i < j) {
            while (i < j && nums[j] >= base) j--;
            while (i < j && nums[i] <= base) i++;
            if (i < j) {
                swap(nums, i, j);
            }
        }
        swap(nums, start, i);
        quickSort(nums, start, j - 1);
        quickSort(nums, j + 1, end);
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
Terwer...大约 7 分钟后端开发JavaSE序列个数哨兵比较交换冒泡排序交换排序快速排序bubble-sortquick-sort
包装类与数组

  1. 包装类（Wrapper Class）。

    针对原生数据类型的包装。 包装类（8 个）都位于 java.lang​ 包下。

    java 中的 8 个包装类分别是：Byte，Short，Integer，Long，Float，Double，Character，Boolean。

    他们的使用方式都是一样的，可以实现原生数据类型和包装类额双向转换。

  2. 数组（Array）：相同类型 数据的集合叫做数组。

  3. 如何定义数组：

    type[] 变量名 = new type[数组中元素的个数 ];

    按照下列方式定义长度为 10 的数组：

    int[] a = new int[10]; // 或者
int a[] = new int[10];

  4. 数组中的元素索引是从 0 开始的。对于数组来说，最大的索引 == 数组的长度 - 1 。

  5. 定义数组的第三种方式：

    type[] 变量名 = new type[]{逗号分隔的初始化值列表}

  6. Java 中的每个数组都有一个 length 属性，他表示数组的长度。

    length 属性是 public，final，int 的。数组长度一旦确定，就不能改变大小。

Terwer...大约 3 分钟后端开发JavaSE数组包装二维使用定义类classarray
Java_SE之String类及其源代码剖析

字符串特性

  1. ​String​​ 是常量，其对象一旦创建就无法改变。
  2. 当使用 +​​​ 拼接字符串时，会生成新的 String​​​ 对象，而不是向原有的 String​​​ 对象追加内容。

查看字节码

javap

javap -c com.terwergreen.str.StringNewTest
Terwer...大约 3 分钟后端开发JavaSE对象字符串字节特性常量string
Java_SE之Object类详解

相等性的比较（==）

  • 对于原生数据类型，比较的是左右两边的值是否相等
  • 对于引用类型来说，比较的是左右两边的引用是否指向同一个对象，或者说左右两边的引用地址是否相同。

java.lang.Object 类

java.lang 包在使用时无需显式导入，编译时由编译器帮助我们导入。

API（Application Programming Interface）

应用编程接口。

toString

当打印引用时，实际上会打印引入所指对象的 toString() 方法的返回值。因为每个类都直接或者间接的继承自 Object ，而 Object 类中定义了 toString() 方法，因此，每个类都有 toString() 这个方法。

Terwer...大约 3 分钟后端开发JavaSE引用进制比较左右两边对象
2
3
4
5
默认页脚
Copyright © 2023 Terwer