【Java】—— 数据结构与集合源码：数据结构概述与线性表、二叉树

🕗 发布于 2024-10-09 08:23 数据结构

1. 数据结构剖析

我们举一个形象的例子来理解数据结构的作用：

战场：程序运行所需的软件、硬件环境

敌人：项目或模块的功能需求

指挥官：编写程序的程序员

士兵和装备：一行一行的代码

战术和策略：数据结构

上图：没有战术，打仗事倍功半

上图：有战术，打仗事半功倍

总结：简单来说，数据结构，就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度、减少内存占用的空间。

具体研究对象如下：

1.1 研究对象一：数据间逻辑关系

数据的逻辑结构指反映数据元素之间的逻辑关系，而与数据的存储无关，是独立于计算机的。

集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系。集合元素之间没有逻辑关系。
线性结构：数据结构中的元素存在一对一的相互关系。比如：排队。结构中必须存在唯一的首元素和唯一的尾元素。体现为：一维数组、链表、栈、队列
树形结构：数据结构中的元素存在一对多的相互关系。比如：家谱、文件系统、组织架构
图形结构：数据结构中的元素存在多对多的相互关系。比如：全国铁路网、地铁图

2. 一维数组

2.1 数组的特点

在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。

//只声明了类型和长度
数据类型[] 数组名称 = new 数据类型[数组长度];

//声明了类型，初始化赋值，大小由元素个数决定
数据类型[] 数组名称 = {数组元素1，数组元素2，......}

例如：整型数组

例如：对象数组

物理结构特点：
- 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
- 不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢。
- 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。

3. 链表

3.1 链表的特点

逻辑结构：线性结构

物理结构：不要求连续的存储空间

存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

常见的链表结构有如下的形式：

3.2 自定义链表

3.2.1 自定义单向链表

/*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性：
    一个属性：是存储的数据。
    另一个属性：是下一个节点的内存地址。
 */
public class Node {

    // 存储的数据
    Object data;

    // 下一个节点的内存地址
    Node next;

    public Node(){

    }

    public Node(Object data, Node next){
        this.data = data;
        this.next = next;
    }
}

/*
链表类(单向链表)
 */
public class Link<E> {

    // 头节点
    Node header;

    private int size = 0;

    public int size(){
        return size;
    }

    // 向链表中添加元素的方法（向末尾添加）
    public void add(E data){
    //public void add(Object data){
        // 创建一个新的节点对象
        // 让之前单链表的末尾节点next指向新节点对象。
        // 有可能这个元素是第一个，也可能是第二个，也可能是第三个。
        if(header == null){
            // 说明还没有节点。
            // new一个新的节点对象，作为头节点对象。
            // 这个时候的头节点既是一个头节点，又是一个末尾节点。
            header = new Node(data, null);
        }else {
            // 说明头不是空！
            // 头节点已经存在了！
            // 找出当前末尾节点，让当前末尾节点的next是新节点。
            Node currentLastNode = findLast(header);
            currentLastNode.next = new Node(data, null);
        }
        size++;
    }

    /**
     * 专门查找末尾节点的方法。
     */
    private Node findLast(Node node) {
        if(node.next == null) {
            // 如果一个节点的next是null
            // 说明这个节点就是末尾节点。
            return node;
        }
        // 程序能够到这里说明：node不是末尾节点。
        return findLast(node.next); // 递归算法！
    }

    /*// 删除链表中某个数据的方法
    public void remove(Object obj){
        //略
    }

    // 修改链表中某个数据的方法
    public void modify(Object newObj){
        //略
    }

    // 查找链表中某个元素的方法。
    public int find(Object obj){
        //略
    }*/
}

3.2.2 自定义双向链表

/*
双向链表中的节点。
 */
public class Node<E> {
    Node prev;
    E data;
    Node next;

    Node(Node prev, E data, Node next) {
        this.prev = prev;
        this.data = data;
        this.next = next;
    }
}

/**
 * 链表类(双向链表)
 * @author 尚硅谷-宋红康
 * @create 15:05
 */
public class MyLinkedList<E> implements Iterable<E>{
    private Node first;  //链表的首元素
    private Node last;   //链表的尾元素
    private int total;

    public void add(E e){
        Node newNode = new Node(last, e, null);

        if(first == null){
            first = newNode;
        }else{
            last.next = newNode;
        }
        last = newNode;
        total++;
    }

    public int size(){
        return total;
    }

    public void delete(Object obj){
        Node find = findNode(obj);
        if(find != null){
            if(find.prev != null){
                find.prev.next = find.next;
            }else{
                first = find.next;
            }
            if(find.next != null){
                find.next.prev = find.prev;
            }else{
                last = find.prev;
            }

            find.prev = null;
            find.next = null;
            find.data = null;

            total--;
        }
    }

    private Node findNode(Object obj){
        Node node = first;
        Node find = null;

        if(obj == null){
            while(node != null){
                if(node.data == null){
                    find = node;
                    break;
                }
                node = node.next;
            }
        }else{
            while(node != null){
                if(obj.equals(node.data)){
                    find = node;
                    break;
                }
                node = node.next;
            }
        }
        return find;
    }

    public boolean contains(Object obj){
        return findNode(obj) != null;
    }

    public void update(E old, E value){
        Node find = findNode(old);
        if(find != null){
            find.data = value;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E>{
        private Node<E> node = first;

        @Override
        public boolean hasNext() {
            return node!=null;
        }

        @Override
        public E next() {
            E value = node.data;
            node = node.next;
            return value;
        }
    }
}

自定义双链表测试：

public class MyLinkedListTest {
    public static void main(String[] args) {
        MyLinkedList<String> my = new MyLinkedList<>();
        my.add("hello");
        my.add("world");
        my.add(null);
        my.add(null);
        my.add("java");
        my.add("java");
        my.add("atguigu");

        System.out.println("一共有：" + my.size());
        System.out.println("所有元素：");
        for (String s : my) {
            System.out.println(s);
        }
        System.out.println("-------------------------------------");
        System.out.println("查找java,null,haha的结果：");
        System.out.println(my.contains("java"));
        System.out.println(my.contains(null));
        System.out.println(my.contains("haha"));

        System.out.println("-------------------------------------");
        System.out.println("替换java,null后：");
        my.update("java","JAVA");
        my.update(null,"songhk");
        System.out.println("所有元素：");
        for (String s : my) {
            System.out.println(s);
        }
        System.out.println("-------------------------------------");
        System.out.println("删除hello，JAVA,null，atguigu后：");
        my.delete("hello");
        my.delete("JAVA");
        my.delete(null);
        my.delete("atguigu");
        System.out.println("所有元素：");
        for (String s : my) {
            System.out.println(s);
        }
    }
}

4. 栈

4.1 栈的特点

栈（Stack）又称为堆栈或堆叠，是限制仅在表的一端进行插入和删除运算的线性表。
栈按照先进后出(FILO,first in last out)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。每次删除（退栈）的总是删除当前栈中最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

核心类库中的栈结构有Stack和LinkedList。
- Stack就是顺序栈，它是Vector的子类。
- LinkedList是链式栈。
体现栈结构的操作方法：
- peek()方法：查看栈顶元素，不弹出
- pop()方法：弹出栈
- push(E e)方法：压入栈
时间复杂度:
- 索引: O(n)
- 搜索: O(n)
- 插入: O(1)
- 移除: O(1)
图示：

4.2 Stack使用举例

public class TestStack {
    /*
    * 测试Stack
    * */
    @Test
    public void test1(){
        Stack<Integer> list = new Stack<>();
        list.push(1);
        list.push(2);
        list.push(3);

        System.out.println("list = " + list);

        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());

/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/

        while(!list.empty()){
            System.out.println("list.pop() =" + list.pop());
        }
    }

    /*
    * 测试LinkedList
    * */
    @Test
    public void test2(){
        LinkedList<Integer> list = new LinkedList<>();
        list.push(1);
        list.push(2);
        list.push(3);

        System.out.println("list = " + list);

        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());

/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/
        while(!list.isEmpty()){
            System.out.println("list.pop() =" + list.pop());
        }
    }
}

5. 队列

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

队列是逻辑结构，其物理结构可以是数组，也可以是链表。

队列的修改原则：队列的修改是依先进先出（FIFO）的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
图示：

6. 树与二叉树

6.1 树的理解

专有名词解释：

结点：树中的数据元素都称之为结点

根节点：最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说，每个结点都可以认为是其子树的根

父节点：结点的上层结点，如图中，结点K的父节点是E、结点L的父节点是G

子节点：节点的下层结点，如图中，节点E的子节点是K节点、节点G的子节点是L节点

兄弟节点：具有相同父节点的结点称为兄弟节点，图中F、G、H互为兄弟节点

结点的度数：每个结点所拥有的子树的个数称之为结点的度，如结点B的度为3

树叶：度数为0的结点，也叫作终端结点，图中D、K、F、L、H、I、J都是树叶

非终端节点（或分支节点）：树叶以外的节点，或度数不为0的节点。图中根、A、B、C、E、G都是

树的深度（或高度）：树中结点的最大层次数，图中树的深度为4

结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1

同代：在同一棵树中具有相同层数的节点

6.2 二叉树的基本概念

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

6.3 二叉树的遍历

前序遍历：中左右（根左右）

即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。
中序遍历：左中右（左根右）

即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。
后序遍历：左右中（左右根）

即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。

前序遍历：ABDHIECFG

中序遍历：HDIBEAFCG

后序遍历：HIDEBFGCA

6.4 经典二叉树

1、满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

2、完全二叉树：叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。

3、二叉排序/查找/搜索树：即为BST (binary search/sort tree)。满足如下性质：

（1）若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值；
（2）若它的右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序/查找/搜索树。

对二叉查找树进行中序遍历，得到有序集合。便于检索。

4、平衡二叉树：（Self-balancing binary search tree，AVL）首先是二叉排序树，此外具有以下性质：（1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1 （2）并且左右两个子树也都是一棵平衡二叉树（3）不要求非叶节点都有两个子结点

平衡二叉树的目的是为了减少二叉查找树的层次，提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。

6、红黑树：即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n)时间内做查找，插入和删除，这里的 n 是树中元素的数目。

红黑树的特性：

每个节点是红色或者黑色
根节点是黑色
每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）
每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍）

当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理，使得它继续满足以上的5个要求：

1、recolor ：将某个节点变红或变黑

2、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）

红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。

原文地址：https://blog.csdn.net/weixin_63106307/article/details/142772585

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：银从法律法规_17
下一篇：Electron构建桌面应用程序，服务于项目的自主学习记录(持续更新...

数据库表操作
自定义完整性指对某一具体关系数据库的约束条件，它反映某一具体应用所涉及的数据必须满足的语义要求。约束方法：规则、存储过程、触发器。
阅读更多2024-10-11
Matlab中实现数据共享
自定义了一个类，在类方法中需要缓存数据，以供其他方法或者实例共享数据，但是类的属性properties没有Static特性。把需要共享的数据封装在一个单独的类里。
阅读更多2024-10-11
Kind部署的K8s证书过期后的解决方案
重启可能会失败，多试几次就好了。
阅读更多2024-10-11
算法学习4
一个数组，选择其中一个数作为对照，把小于等于对照数的放在数组的左边，等于对照数的将其放在数组中间，大于对照数的放在右边；一个数组，选择其中一个数作为对照，把小于等于对照数的放在数组的左边，大于对照数的
阅读更多2024-10-11
idea2024 git merge 时丢失 Merge remote-tracking branch问题
Fast-forward 合并是导致提交丢失的常见原因。使用--no-ff选项可以强制 Git 生成合并提交。在 IntelliJ IDEA 中，你可以手动获取远程分支，通过命令行或修改 Git 配
阅读更多2024-10-11
杨中科 .netcore Linq 。一前期准备知识
调用运行结果。
阅读更多2024-10-11
掌握Razor语法：构建动态ASP.NET Core网页的基石
Razor 是 ASP.NET Core MVC 和 Razor Pages 中用于构建动态网页内容的一种模板引擎。它允许你将 HTML 标记与 C# 代码混合使用，以生成动态的网页。Razor 使得
阅读更多2024-10-11
【docker】存储之目录挂载和卷映射
这部分的内容还是挺重要的，对于我们防止数据的丢失有很大的帮助，最主要的就是两个命令的理解以及使用，大家下来自己在dcoker上敲敲命令即可！
阅读更多2024-10-11
春日技术解惑：Spring Boot课程答疑
所以产品在上线前必须反复测试，经过反复测试，修改，再测试，再修改，产品才能够不断完善。在整个系统测试中，根据需求文档和设计文档，逐一对功能进行检测并写好测试用例，有效避免残片缺陷，因为产品出现缺陷不仅
阅读更多2024-10-11
【JS】连续赋值考题
【JS】连续赋值考题
阅读更多2024-10-11