JAVA数据结构期末DemoCode

题目一：顺序表_删除x~y间值

问题描述：已知线性表采用顺序存储结构SeqList，编写算法删除值在x~y之间的所有结点：

SeqDelTest.java

package top.kfufys.demo01;

/**
 * @project: JavaDemo
 * @author kfufys
 * @date 2024/12/27 20:07
 * @description: 测试删除指定范围内的元素
 * @version: 1.0
 */

public class SeqDelTest {
    public static void main(String[] args) {
        // 创建一个容量为10的顺序表
        top.kfufys.demo01.SeqList list = new SeqList(10);

        // 添加测试数据
        list.add(1);
        list.add(5);
        list.add(10);
        list.add(15);
        list.add(20);
        list.add(25);

        // 打印原始列表
        System.out.println("Original list: " + list);

        // 定义删除范围
        int x = 10;
        int y = 20;

        // 调用方法删除范围内的元素
        list.removeInRange(x, y);

        // 打印删除元素后的列表
        System.out.println("List after removing elements in range " + x + " to " + y + ": " + list);
    }
}

SeqList.java

package top.kfufys.demo01;

/**
 * SeqList类代表一个顺序表，即一个线性数据结构
 * 它允许在列表的末尾添加元素，并在指定范围内删除元素
 */
public class SeqList {
    // data数组存储顺序表中的元素
    private int[] data;
    // size变量记录当前顺序表中元素的数量
    private int size;

    /**
     * 构造一个指定容量的顺序表
     * 
     * @param capacity 顺序表的初始容量
     */
    public SeqList(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }

    /**
     * 向顺序表中添加一个元素如果顺序表已满，则先调整大小
     * 
     * @param value 要添加的元素值
     */
    public void add(int value) {
        if (size == data.length) {
            resize();
        }
        data[size++] = value;
    }

    /**
     * 从顺序表中删除指定范围内的所有元素
     * 
     * @param x 范围的起始值（包含）
     * @param y 范围的结束值（包含）
     * @throws IllegalArgumentException 如果x大于y
     */
    public void removeInRange(int x, int y) {
        if (x > y) {
            throw new IllegalArgumentException("x should not be greater than y");
        }

        int newSize = 0;
        for (int i = 0; i < size; i++) {
            if (data[i] < x || data[i] > y) {
                data[newSize++] = data[i];
            }
        }
        size = newSize;
    }

    /**
     * 返回顺序表中元素的数量
     * 
     * @return 顺序表的大小
     */
    public int size() {
        return size;
    }

    /**
     * 获取顺序表中指定位置的元素
     * 
     * @param index 元素的索引
     * @return 指定位置的元素值
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        return data[index];
    }

    /**
     * 调整顺序表的大小，当顺序表满时自动调用
     * 它会创建一个更大（当前长度的两倍）的新数组，并将原数组的内容复制到新数组中
     */
    private void resize() {
        int[] newData = new int[data.length * 2];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    /**
     * 重写toString方法，以便于顺序表的字符串表示
     * 
     * @return 顺序表的字符串表示
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

运行结果展示：

题目二：顺序栈实现_进制转换

问题描述：已知栈使用顺序存储结构Seqstack，编写算法conversion实现进制转换：

ConversionTest.java

package top.kfufys.demo02;

/**
 * @project JavaDemo
 * @author kfufys
 * @date 2024/12/27 20:30
 * @description 已知栈使用顺序存储结构`Seqstack`，编写算法`conversion`实现进制转换
 * @version 1.0
 */
public class ConversionTest {
    public static void main(String[] args) {
        // 定义要转换的十进制数
        int number = 228;

        // 定义要转换到的进制为2（二进制）
        int base = 2;
        // 调用Conversion类的conversion方法进行进制转换，并打印结果
        System.out.println("十进制 " + number + " 转换为 " + base + " 进制: " + Conversion.conversion(number, base));

        // 将进制更改为8（八进制）
        base = 8;
        // 调用Conversion类的conversion方法进行进制转换，并打印结果
        System.out.println("十进制 " + number + " 转换为 " + base + " 进制: " + Conversion.conversion(number, base));

        // 将进制更改为16（十六进制）
        base = 16;
        // 调用Conversion类的conversion方法进行进制转换，并打印结果
        System.out.println("十进制 " + number + " 转换为 " + base + " 进制: " + Conversion.conversion(number, base));
    }
}

Conversion.java

package top.kfufys.demo02;

/**
 * 十进制转二进制、八进制、十六进制
 */
public class Conversion {
    /**
     * 将十进制数转换为指定进制的字符串表示。
     *
     * @param number 要转换的十进制数
     * @param base   要转换到的进制（例如，2表示二进制，8表示八进制，16表示十六进制）
     * @return 转换后的字符串表示
     */
    public static String conversion(int number, int base) {
        // 检查进制是否在有效范围内（2到16之间）
        if (base < 2 || base > 16) {
            throw new IllegalArgumentException("进制必须在2到16之间");
        }

        // 创建一个顺序栈来存储转换过程中的余数
        SeqStack<Character> stack = new SeqStack<>();
        // 定义一个字符串，包含所有可能的字符（0-9, A-F）
        String digits = "0123456789ABCDEF";

        // 使用do-while循环进行进制转换
        do {
            // 计算当前数字除以目标进制的余数
            int remainder = number % base;
            // 将余数对应的字符压入栈中
            stack.push(digits.charAt(remainder));
            // 更新数字为除以目标进制后的商
            number /= base;
        } while (number > 0);

        // 创建一个StringBuilder对象来构建最终的转换结果
        StringBuilder result = new StringBuilder();
        // 从栈中弹出所有字符并添加到StringBuilder中
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        // 返回转换后的字符串表示
        return result.toString();
    }
}

SeqStack.java

package top.kfufys.demo02;

import java.util.EmptyStackException;

/**
 * 顺序栈 (SeqStack) 的实现，使用泛型 T 来存储元素。
 */
public class SeqStack<T> {
    // 默认容量大小
    private static final int DEFAULT_CAPACITY = 10;

    // 存储栈元素的数组
    private T[] elements;

    // 栈顶指针，初始值为 -1 表示空栈
    private int top;

    /**
     * 构造函数，初始化一个默认容量的顺序栈。
     */
    @SuppressWarnings("unchecked")
    public SeqStack() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        top = -1;
    }

    /**
     * 检查栈是否为空。
     *
     * @return 如果栈为空返回 true，否则返回 false。
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 将元素压入栈中。如果栈已满，则自动扩展容量。
     *
     * @param item 要压入栈中的元素。
     */
    public void push(T item) {
        if (top == elements.length - 1) {
            resize(elements.length * 2); // 当栈满时，将容量扩大一倍
        }
        elements[++top] = item; // 将元素添加到栈顶，并更新栈顶指针
    }

    /**
     * 弹出栈顶元素。如果栈为空，则抛出 EmptyStackException。
     *
     * @return 栈顶元素。
     * @throws EmptyStackException 如果栈为空。
     */
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = elements[top]; // 获取栈顶元素
        elements[top--] = null; // 更新栈顶指针并避免对象游离
        if (top > 0 && top == elements.length / 4) {
            resize(elements.length / 2); // 当栈容量超过四分之一且非空时，将容量减半
        }
        return item;
    }

    /**
     * 查看栈顶元素但不弹出。如果栈为空，则抛出 EmptyStackException。
     *
     * @return 栈顶元素。
     * @throws EmptyStackException 如果栈为空。
     */
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements[top];
    }

    /**
     * 调整栈的容量。
     *
     * @param newCapacity 新的容量大小。
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        T[] newElements = (T[]) new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, top + 1); // 复制现有元素到新数组
        elements = newElements; // 更新引用
    }
}

运行结果展示：

题目三：顺序表_删除最小值结点

问题描述：已知线性表采用顺序存储结构SeqList，编写算法，删除值最小的结点：

TestSeqList.java

package top.kfufys.demo03;

/**
 * @project: JavaDemo
 * @author kfufys
 * @data 2024/12/27 21:00
 * @description: 顺序表_删除最小值结点
 * @version 1.0
 */
public class TestSeqList {
    public static void main(String[] args) {
        // 创建一个顺序表对象
        SeqList seqList = new SeqList();
        // 添加一些元素到顺序表中
        seqList.add(5);
        seqList.add(3);
        seqList.add(8);
        seqList.add(1);
        seqList.add(7);
        // 打印删除最小元素之前的顺序表内容
        System.out.println("删除最小元素之前：");
        seqList.printList();
        // 删除顺序表中的最小元素
        seqList.removeMin();
        // 打印删除最小元素之后的顺序表内容
        System.out.println("删除最小元素之后：");
        seqList.printList();
    }
}

SeqList.java

package top.kfufys.demo03;

/**
 * SeqList类代表一个顺序表，即一个线性数据结构
 * 它允许在列表的末尾添加元素，并在指定范围内删除元素
 */
public class SeqList {
    // data数组存储顺序表中的元素
    private int[] data;
    // size变量记录当前顺序表中元素的数量
    private int size;

    /**
     * 构造一个指定容量的顺序表
     */
    public SeqList() {
        this.data = new int[10]; // 初始化默认容量为10
        this.size = 0;
    }

    /**
     * 向顺序表中添加一个元素如果顺序表已满，则先调整大小
     *
     * @param value 要添加的元素值
     */
    public void add(int value) {
        if (size == data.length) {
            resize();
        }
        data[size++] = value;
    }

    /**
     * 从顺序表中删除指定范围内的所有元素
     *
     * @param x 范围的起始值（包含）
     * @param y 范围的结束值（包含）
     * @throws IllegalArgumentException 如果x大于y
     */
    public void removeInRange(int x, int y) {
        if (x > y) {
            throw new IllegalArgumentException("x should not be greater than y");
        }

        int newSize = 0;
        for (int i = 0; i < size; i++) {
            if (data[i] < x || data[i] > y) {
                data[newSize++] = data[i];
            }
        }
        size = newSize;
    }

    /**
     * 返回顺序表中元素的数量
     *
     * @return 顺序表的大小
     */
    public int size() {
        return size;
    }

    /**
     * 获取顺序表中指定位置的元素
     *
     * @param index 元素的索引
     * @return 指定位置的元素值
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        return data[index];
    }

    /**
     * 调整顺序表的大小，当顺序表满时自动调用
     * 它会创建一个更大（当前长度的两倍）的新数组，并将原数组的内容复制到新数组中
     */
    private void resize() {
        int[] newData = new int[data.length * 2];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    /**
     * 重写toString方法，以便于顺序表的字符串表示
     *
     * @return 顺序表的字符串表示
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * 删除顺序表中值最小的结点
     */
    public void removeMin() {
        if (size == 0) {
            return; // 如果顺序表为空，直接返回
        }

        int minIndex = 0; // 记录最小值的索引
        int minValue = data[0]; // 记录最小值

        // 遍历顺序表，找到最小值及其索引
        for (int i = 1; i < size; i++) {
            if (data[i] < minValue) {
                minValue = data[i]; // 更新最小值
                minIndex = i; // 更新最小值的索引
            }
        }

        // 删除最小值
        remove(minIndex);
    }

    /**
     * 删除指定索引的元素
     *
     * @param index 要删除的元素的索引
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引: " + index + ", 大小: " + size);
        }
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1]; // 将后续元素向前移动
        }
        data[--size] = 0; // 更新元素数量并避免对象游离
    }

    /**
     * 打印顺序表中的所有元素
     */
    public void printList() {
        System.out.println(this.toString()); // 使用重写的toString方法打印顺序表
    }
}

运行结果展示：

题目四：稀疏矩阵转置

问题描述：编写算法TransMatrix实现稀疏矩阵的转置：

SparseMatrixTransposeTest.java

package top.kfufys.demo04;

/**
 * @author kfufys
 * @version 1.0
 * @project: JavaDemo
 * @date 2024/12/27 21:15
 * @description: 该类用于演示如何对稀疏矩阵进行转置操作，稀疏矩阵是一种特殊的数据结构，主要用于减少存储空间和提高计算效率
 */
public class SparseMatrixTransposeTest {
    /**
     * 主函数入口
     *
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 初始化稀疏矩阵，以三元组形式表示非零元素的位置和值
        Triple[] matrix = {
                new Triple(0, 1, 1),
                new Triple(0, 3, 2),
                new Triple(1, 2, 3),
                new Triple(2, 3, 4)
        };
        // 打印原始稀疏矩阵
        System.out.println("Original Sparse Matrix:");
        TransMatrix.printMatrix(matrix);
        // 执行稀疏矩阵的转置操作
        Triple[] transposedMatrix = TransMatrix.transpose(matrix);
        // 打印转置后的稀疏矩阵
        System.out.println("Transposed Sparse Matrix:");
        TransMatrix.printMatrix(transposedMatrix);
    }
}

Triple.java

package top.kfufys.demo04;

/**
 * Triple 类用于表示一个三元组，主要用于存储矩阵元素的行位置、列位置和值。
 */
public class Triple {
    // 表示矩阵元素的行位置
    int row;
    // 表示矩阵元素的列位置
    int col;
    // 表示矩阵元素的值
    int value;

    /**
     * 构造一个新的 Triple 实例。
     *
     * @param row   矩阵元素的行位置
     * @param col   矩阵元素的列位置
     * @param value 矩阵元素的值
     */
    public Triple(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }
}

TransMatrix.java

package top.kfufys.demo04;

import top.kfufys.demo04.Triple;

/**
 * TransMatrix类提供了矩阵转置的功能，特别适用于稀疏矩阵。
 * 稀疏矩阵是指大部分元素为零的矩阵。通过使用Triple数组表示矩阵，
 * 可以有效地存储和操作这些矩阵。
 */
public class TransMatrix {

    /**
     * 对稀疏矩阵进行转置。
     *
     * @param matrix 代表原始矩阵的Triple数组，每个Triple对象包含行索引、列索引和值。
     * @return 转置后的矩阵，以Triple数组形式返回。
     */
    public static Triple[] transpose(Triple[] matrix) {
        // 确定矩阵的列数（即转置后矩阵的行数）
        int numCols = 0;
        for (Triple triple : matrix) {
            if (triple.col > numCols) {
                numCols = triple.col;
            }
        }
        numCols++; // 列索引从0开始，因此需要加1

        // 初始化结果矩阵和辅助数组
        Triple[] result = new Triple[matrix.length]; // 存储转置后的矩阵
        int[] colSizes = new int[numCols];           // 统计每列的元素个数
        int[] colIndices = new int[numCols];         // 记录每列元素在转置矩阵中的起始位置

        // 统计每列的元素个数
        for (Triple triple : matrix) {
            colSizes[triple.col]++; // 每遇到一个元素，对应列的计数加1
        }

        // 计算每列元素在转置矩阵中的起始位置
        colIndices[0] = 0; // 第一列的起始位置总是0
        for (int i = 1; i < numCols; i++) {
            colIndices[i] = colIndices[i - 1] + colSizes[i - 1];
            // 当前列的起始位置等于前一列的起始位置加上前一列的元素个数
        }

        // 生成转置矩阵
        for (Triple triple : matrix) {
            int index = colIndices[triple.col]; // 获取当前列的起始位置
            result[index] = new Triple(triple.col, triple.row, triple.value);
            // 创建新的Triple对象，交换行列索引，并赋值给结果数组
            colIndices[triple.col]++; // 更新当前列的起始位置
        }

        return result;
    }

    /**
     * 打印矩阵。
     *
     * @param matrix 要打印的矩阵，以Triple数组形式表示。
     */
    public static void printMatrix(Triple[] matrix) {
        for (Triple triple : matrix) {
            System.out.println(triple.row + " " + triple.col + " " + triple.value);
            // 打印每一行的行索引、列索引和值
        }
    }
}

运行结果展示：

题目五：递归建立二叉树

问题描述：编写算法，使用递归方式建立二叉树：

BinaryTreeBuilder.java

package top.kfufys.demo05;

/**
 * @author kfufys
 * @version 1.0
 * @project: JavaDemo
 * @date 2024/12/27 21:40
 * @description 二叉树构建和遍历的主类
 */
public class BinaryTreeBuilder {

    /**
     * 主方法，程序入口
     *
     * @param args 命令行参数（本程序未使用）
     */
    public static void main(String[] args) {
        // 调用 BinaryTree 类中的静态方法 buildTree() 构建二叉树，并将根节点赋值给 root 变量
        TreeNode root = BinaryTree.buildTree();

        // 打印提示信息，表示接下来将进行中序遍历
        System.out.println("构建的二叉树的中序遍历结果:");

        // 调用 BinaryTree 类中的静态方法 inorderTraversal() 对二叉树进行中序遍历并打印结果
        BinaryTree.inorderTraversal(root);
    }
}

TreeNode.java

package top.kfufys.demo05;

/**
 * 二叉树节点类，表示二叉树中的一个节点
 */
public class TreeNode {

    /**
     * 节点存储的值
     */
    int val;

    /**
     * 指向左子节点的引用
     */
    TreeNode left;

    /**
     * 指向右子节点的引用
     */
    TreeNode right;

    /**
     * 构造函数，用于初始化一个新的二叉树节点
     *
     * @param val 节点的值
     */
    public TreeNode(int val) {
        // 初始化节点的值
        this.val = val;
        // 初始化左右子节点为 null，表示当前节点没有子节点
        this.left = null;
        this.right = null;
    }
}

BinaryTree.java

package top.kfufys.demo05;

import java.util.Scanner;

/**
 * 二叉树类，包含构建二叉树和中序遍历的方法
 */
public class BinaryTree {
    private static Scanner scanner = new Scanner(System.in);

    /**
     * 构建二叉树的方法
     *
     * @return 返回构建好的二叉树的根节点
     */
    public static TreeNode buildTree() {
        // 提示用户输入节点值，并读取输入
        System.out.print("请输入节点值（输入 -1 表示空节点）: ");
        int value = getValidInput();

        // 如果输入值为 -1，表示该节点为空，返回 null
        if (value == -1) {
            return null;
        }

        // 否则，创建一个新的 TreeNode 节点并初始化其值
        TreeNode root = new TreeNode(value);

        // 递归构建左子树
        System.out.print("请输入节点 " + value + " 的左子节点值（输入 -1 表示空节点）: ");
        root.left = buildTree();

        // 递归构建右子树
        System.out.print("请输入节点 " + value + " 的右子节点值（输入 -1 表示空节点）: ");
        root.right = buildTree();

        return root;
    }

    private static int getValidInput() {
        while (!scanner.hasNextInt()) {
            System.out.println("输入错误，请输入有效的整数。");
            scanner.next(); // 清除错误输入
        }
        return scanner.nextInt();
    }

    /**
     * 中序遍历二叉树的方法
     *
     * @param root 二叉树的根节点
     */
    public static void inorderTraversal(TreeNode root) {
        // 如果当前节点为空，直接返回
        if (root == null) {
            return;
        }

        // 递归遍历左子树
        inorderTraversal(root.left);

        // 访问当前节点，打印节点值
        System.out.print(root.val + " ");

        // 递归遍历右子树
        inorderTraversal(root.right);
    }
}

运行结果展示：

---

- - Done - -