数据结构与算法

数据结构

10个数据结构：数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）、散列表（Hash Table）、二叉树（Binary Tree）、堆（Heap）、跳表（Skip List）、图（Graph）、树（Tree）

数组（Array）

数组是固定大小的元素集合，可以通过索引访问。

public class ArrayExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};

        // 访问数组元素
        System.out.println(arr[0]);  // 输出：1
        
        // 修改数组元素
        arr[1] = 20;
        
        // 遍历数组
        for (int element : arr) {
            System.out.println(element);
        }
    }
}

链表

链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListExample {
    Node head;
    
    // 添加元素到链表
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }
    
    // 打印链表
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
    
    public static void main(String[] args) {
        LinkedListExample list = new LinkedListExample();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList();  // 输出：1 2 3
    }
}

栈（Stack）

栈是一种后进先出（LIFO）的数据结构。

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 出栈
        System.out.println(stack.pop());  // 输出：3
        System.out.println(stack.pop());  // 输出：2

        // 查看栈顶元素
        System.out.println(stack.peek());  // 输出：1
    }
}

队列（Queue）

队列是一种先进先出（FIFO）的数据结构。

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 入队
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // 出队
        System.out.println(queue.poll());  // 输出：1
        System.out.println(queue.poll());  // 输出：2

        // 查看队首元素
        System.out.println(queue.peek());  // 输出：3
    }
}

散列表（Hash Table）

散列表通过键值对存储数据，具有快速的查找、插入和删除操作。

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 添加键值对
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        
        // 查找键值
        System.out.println(map.get("a"));  // 输出：1
        
        // 删除键值对
        map.remove("b");
        
        // 遍历散列表
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

二叉树（Binary Tree）

二叉树是每个节点最多有两个子节点的数据结构。

class TreeNode {
    int data;
    TreeNode left, right;
    
    TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTreeExample {
    TreeNode root;
    
    // 添加节点
    public void add(int data) {
        root = addRecursive(root, data);
    }
    
    private TreeNode addRecursive(TreeNode node, int data) {
        if (node == null) {
            return new TreeNode(data);
        }
        if (data < node.data) {
            node.left = addRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = addRecursive(node.right, data);
        }
        return node;
    }
    
    // 打印二叉树（中序遍历）
    public void printInOrder(TreeNode node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.print(node.data + " ");
            printInOrder(node.right);
        }
    }
    
    public static void main(String[] args) {
        BinaryTreeExample tree = new BinaryTreeExample();
        tree.add(5);
        tree.add(3);
        tree.add(7);
        tree.printInOrder(tree.root);  // 输出：3 5 7
    }
}

堆（Heap）

堆是一种完全二叉树，满足特定的堆性质（最大堆或最小堆）。

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        // 添加元素
        maxHeap.add(3);
        maxHeap.add(5);
        maxHeap.add(1);
        
        // 取出最大元素
        System.out.println(maxHeap.poll());  // 输出：5
        
        // 遍历堆
        for (int num : maxHeap) {
            System.out.println(num);
        }
    }
}

跳表（Skip List）

跳表是一种数据结构，支持快速查找、插入和删除。

class Node {
    int value;
    Node[] next;
    
    Node(int value, int level) {
        this.value = value;
        next = new Node[level + 1];
    }
}

public class SkipListExample {
    private static final int MAX_LEVEL = 4;
    private Node head = new Node(-1, MAX_LEVEL);
    
    // 插入元素
    public void insert(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node current = head;
        
        for (int i = MAX_LEVEL; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].value < value) {
                current = current.next[i];
            }
            update[i] = current;
        }
        
        int level = randomLevel();
        Node newNode = new Node(value, level);
        
        for (int i = 0; i <= level; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }
    
    private int randomLevel() {
        int level = 0;
        while (Math.random() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }
    
    // 打印跳表
    public void printList() {
        Node node = head.next[0];
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next[0];
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        SkipListExample list = new SkipListExample();
        list.insert(3);
        list.insert(6);
        list.insert(7);
        list.insert(9);
        list.insert(12);
        list.printList();  // 输出：3 6 7 9 12
    }
}

图（Graph）

图由顶点和边组成，可以是有向图或无向图。

import java.util.*;

public class GraphExample {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();
    
    // 添加边
    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.get(src).add(dest);
    }
    
    // 打印图
    public void printGraph() {
        for (int src : adjList.keySet()) {
            System.out.print(src + " -> ");
            for (int dest : adjList.get(src)) {
                System.out.print(dest + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        GraphExample graph = new GraphExample();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        graph.printGraph();
    }
}

树（Tree）

树用于存储字符串集合，支持高效的前缀查询。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

public class TrieExample {
    private TrieNode root = new TrieNode();
    
    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }
    
    // 查找单词
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
    
    // 打印Trie树（中序遍历）
    public void printTrie(TrieNode node, String prefix) {
        if (node.isEndOfWord) {
            System.out.println(prefix);
        }
        for (char c = 'a'; c <= 'z'; c++) {
            int index = c - 'a';
            if (node.children[index] != null) {
                printTrie(node.children[index], prefix + c);
            }
        }
    }
    
    public static void main(String[] args) {
        TrieExample trie = new TrieExample();
        trie.insert("hello");
        trie.insert("helium");
        trie.insert("world");
        
        System.out.println(trie.search("hello"));  // 输出：true
        System.out.println(trie.search("helix"));  // 输出：false
        
        trie.printTrie(trie.root, "");  // 输出：hello helium world
    }
}

算法

10个算法：递归（Recursion）、排序（Sorting）、二分查找（Binary Search）、搜索（Search）、哈希算法（Hash Algorithm）、贪心算法（Greedy Algorithm）、分治算法（Divide and Conquer）、回溯算法（Backtracking）、动态规划（Dynamic Programming）、字符串匹配算法（String Matching Algorithm）

递归（Recursion）

递归是一种解决问题的方法，通过将问题分解为更小的子问题来求解。

public class RecursionExample {
    // 计算阶乘
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));  // 输出：120
    }
}

排序（Sorting）

常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。这里以快速排序为例。

public class QuickSort {
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }
    
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }
    
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        quickSort(array, 0, array.length - 1);
        for (int num : array) {
            System.out.print(num + " ");
        }
        // 输出：1 5 7 8 9 10
    }
}

二分查找（Binary Search）

二分查找是一种在有序数组中查找某一特定元素的搜索算法。

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == x) {
                return mid;
            }
            if (arr[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;  // 未找到元素
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int result = binarySearch(arr, 10);
        System.out.println(result);  // 输出：3
    }
}

搜索（Search）

搜索算法用于查找数据结构中的特定元素。这里以深度优先搜索（DFS）为例。

import java.util.*;

public class DepthFirstSearchExample {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();
    
    // 添加边
    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.get(src).add(dest);
    }
    
    // 深度优先搜索
    public void DFS(int start) {
        Set<Integer> visited = new HashSet<>();
        DFSUtil(start, visited);
    }
    
    private void DFSUtil(int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        for (int neighbor : adjList.getOrDefault(vertex, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                DFSUtil(neighbor, visited);
            }
        }
    }
    
    public static void main(String[] args) {
        DepthFirstSearchExample graph = new DepthFirstSearchExample();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        graph.DFS(2);  // 输出：2 0 1 3
    }
}

哈希算法（Hashing）

哈希算法将数据映射到固定大小的哈希表中。

import java.util.HashMap;

public class HashingExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 插入键值对
        map.put("key1", 1);
        map.put("key2", 2);
        
        // 访问值
        System.out.println(map.get("key1"));  // 输出：1
        
        // 删除键值对
        map.remove("key2");
        
        // 遍历哈希表
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

贪心算法（Greedy Algorithm）

贪心算法在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的。

import java.util.Arrays;
import java.util.Comparator;

public class GreedyAlgorithmExample {
    static class Item {
        int value, weight;
        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }
    }
    
    // 分数背包问题
    public static double fractionalKnapsack(int W, Item[] items) {
        Arrays.sort(items, new Comparator<Item>() {
            public int compare(Item a, Item b) {
                double r1 = (double) a.value / a.weight;
                double r2 = (double) b.value / b.weight;
                return Double.compare(r2, r1);
            }
        });
        
        int currentWeight = 0;
        double finalValue = 0.0;
        
        for (Item item : items) {
            if (currentWeight + item.weight <= W) {
                currentWeight += item.weight;
                finalValue += item.value;
            } else {
                int remain = W - currentWeight;
                finalValue += item.value * ((double) remain / item.weight);
                break;
            }
        }
        
        return finalValue;
    }

    public static void main(String[] args) {
        Item[] items = { new Item(60, 10), new Item(100, 20), new Item(120, 30) };
        int W = 50;
        System.out.println(fractionalKnapsack(W, items));  // 输出：240.0
    }
}

分治算法（Divide and Conquer）

分治算法将问题分成较小的子问题，递归地解决每个子问题，然后合并结果。

public class MergeSortExample {
    // 归并排序
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
    
    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[n2];
        System.arraycopy(arr, l, L, 0, n1);
        System.arraycopy(arr, m + 1, R, 0, n2);
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

回溯算法（Backtracking）

回溯算法通过构建所有可能的解来解决问题，一旦发现某个解无法达到目标，就回溯到上一步。

public class BacktrackingExample {
    private int N;
    private int[][] board;

    public BacktrackingExample(int N) {
        this.N = N;
        board = new int[N][N];
    }

    // 检查是否可以在board[row][col]放置皇后
    private boolean isSafe(int row, int col) {
        // 检查列
        for (int i = 0; i < col; i++) {
            if (board[row][i] == 1) {
                return false;
            }
        }

        // 检查左上对角线
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // 检查右上对角线
        for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    // 回溯法解决N皇后问题
    private boolean solveNQueens(int col) {
        if (col >= N) {
            return true; // 所有皇后都放置成功
        }
        for (int i = 0; i < N; i++) {
            if (isSafe(i, col)) {
                board[i][col] = 1; // 放置皇后
                if (solveNQueens(col + 1)) {
                    return true;
                }
                board[i][col] = 0; // 回溯
            }
        }
        return false;
    }

    // 打印棋盘
    private void printBoard() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] == 1 ? "Q " : ". ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int N = 8;
        BacktrackingExample solver = new BacktrackingExample(N);
        if (solver.solveNQueens(0)) {
            solver.printBoard();
        } else {
            System.out.println("No solution exists");
        }
    }
}

动态规划（Dynamic Programming）

动态规划（Dynamic Programming，简称DP）是一种将复杂问题分解成更小的子问题来解决的技术。通过存储子问题的解来避免重复计算，从而提高效率。下面以经典的动态规划问题“最长公共子序列（LCS）”为例。

public class LCSExample {
    // 计算两个字符串的最长公共子序列长度
    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else 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]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";
        System.out.println("Length of LCS is " + lcs(s1, s2));  // 输出：4
    }
}

字符串匹配算法（String Matching Algorithm）

字符串匹配算法用于在给定文本中找到子字符串（模式）的所有出现位置。KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它利用部分匹配表来加速搜索过程。

public class KMPExample {
    // 计算部分匹配表（LPS数组）
    public static int[] computeLPSArray(String pattern) {
        int n = pattern.length();
        int[] lps = new int[n];
        int length = 0;  // 最长相同前缀后缀的长度
        int i = 1;
        lps[0] = 0;  // lps[0]总是0

        while (i < n) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP搜索算法
    public static void KMPsearch(String text, String pattern) {
        int m = text.length();
        int n = pattern.length();
        int[] lps = computeLPSArray(pattern);
        int i = 0;  // text的索引
        int j = 0;  // pattern的索引

        while (i < m) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == n) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < m && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String text = "ababcabcabababd";
        String pattern = "ababd";
        KMPsearch(text, pattern);  // 输出：Pattern found at index 10
    }
}

基础算法

排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序、希尔排序、基数排序等。 搜索算法：线性搜索、二分搜索、插值搜索、斐波那契搜索、深度优先搜索(DFS)、广度优先搜索(BFS)等。

数据结构算法

链表算法：插入、删除、反转链表、检测循环链表等。 栈和队列算法：栈的压栈、弹栈操作，队列的入队、出队操作等。 树算法：二叉树、AVL树、红黑树、B树、B+树等的插入、删除、搜索等。 图算法：图的遍历（DFS、BFS）、最短路径算法（Dijkstra、Floyd-Warshall、Bellman-Ford）、最小生成树算法（Prim、Kruskal）等。

动态规划

背包问题 最长公共子序列（LCS） 最短路径问题（如Floyd-Warshall算法也可以看作是一种动态规划） 0-1背包问题 矩阵链乘法

贪心算法

活动选择问题 分数背包问题 哈夫曼编码 最小生成树Prim算法也可以看作是一种贪心算法

回溯算法

八皇后问题 图的着色问题 旅行商问题（TSP）

分治算法

归并排序 快速排序 大整数乘法 二分搜索

分支限界法

整数规划 旅行商问题（TSP）的另一种解法

字符串算法

KMP（Knuth-Morris-Pratt）字符串匹配算法 Rabin-Karp字符串搜索算法 Boyer-Moore字符串搜索算法 正则表达式匹配

计算几何算法

点在多边形内判断 凸包算法（如Graham扫描法） 最近点对问题 碰撞检测

加密与解密算法

对称加密算法：DES、AES等 非对称加密算法：RSA、ECC等 哈希算法：MD5、SHA-1、SHA-256等

图像处理算法

边缘检测（如Canny边缘检测） 滤波算法（如高斯滤波、中值滤波） 形态学操作（如腐蚀、膨胀）

机器学习算法

线性回归 逻辑回归 决策树 随机森林 支持向量机（SVM） 神经网络（包括深度学习）