Java图解宝典:轻松掌握数据结构与算法图解精髓

引言
数据结构与算法是计算机科学中的基础,对于理解和设计高效的软件至关重要。Java作为一门流行的编程语言,拥有丰富的数据结构和算法实现。本文旨在通过图解的方式,帮助读者轻松掌握Java中的数据结构与算法精髓。
数据结构
线性表
线性表是一种基本的线性数据结构,它包含一系列元素,这些元素按照线性顺序排列。Java中,
ArrayList
和
LinkedList
是最常用的线性表实现。
ArrayList
import java.util.ArrayList;

public class ArrayListExample {
public static void main(String[] args) {
ArrayList numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
System.out.println(numbers);
}
}
LinkedList
import java.util.LinkedList;

public class LinkedListExample {
public static void main(String[] args) {
LinkedList numbers = new LinkedList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
System.out.println(numbers);
}
}
栈和队列
栈是一种后进先出(LIFO)的数据结构,而队列是一种先进先出(FIFO)的数据结构。
栈
import java.util.Stack;

public class StackExample {
public static void main(String[] args) {
Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
}
}
队列
import java.util.Queue;
import java.util.LinkedList;

public class QueueExample {
public static void main(String[] args) {
Queue queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.poll());
}
}
串、数组和广义表
串是由字符组成的序列,数组是一种基本的数据结构,可以存储多个元素。广义表是数组的扩展,可以包含其他数据结构。
串
public class StringExample {
public static void main(String[] args) {
String text = “Hello, World!”;
System.out.println(text);
}
}
数组
public class ArrayExample {
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[2]);
}
}
树
树是一种非线性数据结构,由节点组成,每个节点有零个或多个子节点。
二叉树
class Node {
int value;
Node left;
Node right;

Node(int value) {
this.value = value;
}
}

public class BinaryTreeExample {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.println(root.left.value);
}
}
图
图是一种复杂的数据结构,由节点和边组成。
图的表示
import java.util.HashMap;
import java.util.Map;

public class GraphExample {
public static void main(String[] args) {
Map> graph = new HashMap<>();
graph.put(1, new ArrayList<>(Arrays.asList(2, 3)));
graph.put(2, new ArrayList<>(Arrays.asList(4)));
graph.put(3, new ArrayList<>(Arrays.asList(4)));
graph.put(4, new ArrayList<>());

System.out.println(graph.get(1));
}
}
算法
排序算法
排序算法用于将一组数据按照特定的顺序排列。
冒泡排序
public class BubbleSortExample {
public static void main(String[] args) {
int[] numbers = {5, 3, 8, 4, 2};
for (int i = 0; i < numbers.length - 1; i++) { for (int j = 0; j < numbers.length - 1 - i; j++) { if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(numbers));
}
}
查找算法
查找算法用于在数据结构中找到特定元素。
线性查找
public class LinearSearchExample {
public static void main(String[] args) {
int[] numbers = {1, 3, 5, 7, 9};
int target = 5;
int index = -1;
for (int i = 0; i < numbers.length; i++) { if (numbers[i] == target) { index = i; break; } } System.out.println("Index of " + target + ": " + index); } } 递归算法 递归算法是一种直接或间接调用自身的算法。 斐波那契数列 public class FibonacciExample { public static void main(String[] args) { int n = 10; System.out.println(fibonacci(n)); } public static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } } 动态规划 动态规划是一种将复杂问题分解为更小、更简单问题的方法。 最长公共子序列 public class LongestCommonSubsequenceExample { public static void main(String[] args) { String s1 = "AGGTAB"; String s2 = "GXTXAYB"; int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } System.out.println("Length of LCS: " + dp[s1.length()][s2.length()]); } } 图算法 图算法用于在图数据结构上执行特定任务。 深度优先搜索(DFS) public class DFSExample { public static void main(String[] args) { Map> graph = new HashMap<>();
graph.put(1, new ArrayList<>(Arrays.asList(2, 3)));
graph.put(2, new ArrayList<>(Arrays.asList(4)));
graph.put(3, new ArrayList<>(Arrays.asList(4)));
graph.put(4, new ArrayList<>());

int start = 1;
boolean[] visited = new boolean[graph.size()];
dfs(graph, start, visited);
}

public static void dfs(Map> graph, int node, boolean[] visited) {
visited[node] = true;
System.out.println(node);

for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
}
贪心算法
贪心算法是一种在每一步选择中都采取当前最优解的算法。
最小生成树(Prim算法)
public class PrimExample {
public static void main(String[] args) {
// 假设图的数据和边的权重
int[][] graph = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};

// Prim算法实现
int[] minKey = new int[graph.length];
boolean[] inMST = new boolean[graph.length];
for (int i = 0; i < graph.length; i++) { minKey[i] = Integer.MAX_VALUE; } minKey[0] = 0; for (int i = 0; i < graph.length - 1; i++) { // 选择最小边 int u = -1; for (int v = 0; v < graph.length; v++) { if (!inMST[v] && minKey[v] < Integer.MAX_VALUE) { if (u == -1 || minKey[v] < minKey[u]) { u = v; } } } // 添加边到最小生成树 inMST[u] = true; for (int v = 0; v < graph.length; v++) { if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < minKey[v]) { minKey[v] = graph[u][v]; } } } // 打印最小生成树 for (int i = 1; i < graph.length; i++) { if (minKey[i] != Integer.MAX_VALUE) { System.out.println("Edge between " + i + " and " + (i - 1) + " with weight " + minKey[i]); } } } } 分治算法 分治算法将问题分解为更小的子问题,递归求解子问题,然后合并结果。 快速排序 public class QuickSortExample { public static void main(String[] args) { int[] numbers = {5, 3, 8, 4, 2}; quickSort(numbers, 0, numbers.length - 1); System.out.println(Arrays.toString(numbers)); } public static void quickSort(int[] numbers, int left, int right) { if (left < right) { int pivotIndex = partition(numbers, left, right); quickSort(numbers, left, pivotIndex - 1); quickSort(numbers, pivotIndex + 1, right); } } public static int partition(int[] numbers, int left, int right) { int pivot = numbers[right]; int i = left - 1; for (int j = left; j < right; j++) { if (numbers[j] <= pivot) { i++; int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } } int temp = numbers[i + 1]; numbers[i + 1] = numbers[right]; numbers[right] = temp; return i + 1; } } 回溯算法 回溯算法通过尝试所有可能的解决方案来找到问题的解。 0-1背包问题 public class KnapsackExample { public static void main(String[] args) { int[] weights = {1, 3, 4}; int[] values = {1, 4, 5}; int capacity = 5; System.out.println("Maximum value in knapsack = " + knapsack(values, weights, capacity)); } public static int knapsack(int[] values, int[] weights, int capacity) { return knapsackHelper(values, weights, capacity, 0); } private static int knapsackHelper(int[] values, int[] weights, int capacity, int n) { if (n == values.length) { return 0; } if (capacity <= 0) { return 0; } if (weights[n] > capacity) {
return knapsackHelper(values, weights, capacity, n + 1);
}
return Math.max(values[n] + knapsackHelper(values, weights, capacity – weights[n], n + 1),
knapsackHelper(values, weights, capacity, n + 1));
}
}
结论
通过本文的图解,读者可以更好地理解Java中的数据结构与算法。掌握这些基础知识和技能,将有助于提高编程能力和解决复杂问题的能力。