一、数据结构的基本算法

1. 定义

数据结构是指一组数据元素及其相互关系的集合，旨在高效地组织和存储数据以便进行高效的访问和修改。

2. 基本概念

• 数据：在计算机中表示信息的符号或数字。
• 数据元素：数据的基本单位，可以是原子数据（如整数、字符）或复杂数据（如结构体）。
• 数据结构的类型：
  • 线性数据结构：数据元素之间存在一对一的关系，例如数组、链表、栈和队列。
  • 非线性数据结构：数据元素之间存在多对多的关系，例如树和图。

3. 常见的数据结构

• 数组：一组相同类型的数据元素，按照顺序存储，可以通过索引快速访问。
• 链表：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
• 栈：一种后进先出（LIFO）的数据结构，支持插入和删除操作。
• 队列：一种先进先出（FIFO）的数据结构，支持在一端插入数据，在另一端删除数据。
• 树：由节点组成的层次结构，常用于表示具有父子关系的数据。
• 图：由节点和边组成的非线性数据结构，用于表示复杂关系。

4. 操作

常见的基本操作包括：

• 插入：向数据结构中添加数据。
• 删除：从数据结构中移除数据。
• 查找：根据某种条件查找特定的数据。
• 遍历：按一定顺序访问数据结构中的所有元素。

5. 应用

数据结构在计算机程序设计中扮演重要角色，常用于：

• 数据存储与管理
• 算法实现（如搜索和排序算法）
• 数据库系统
• 操作系统

6. 选择数据结构

选择合适的数据结构取决于以下因素：

• 数据的类型和数量
• 需要的操作类型（如频繁插入、删除或查找）
• 资源限制（如内存和处理时间）

二、线性表

1. 线性表概述

• 定义：线性表是一种线性结构，表中的每个元素都有一个唯一的前驱和后继（除了第一个和最后一个元素），元素之间的关系是线性的。
• 类型：
  • 顺序表：使用一块连续的内存空间来存储线性表元素。
  • 链表：使用不连续的存储空间，通过指针连接各个元素。

2. 顺序表（Array List）

顺序表的特点是支持随机访问，但在插入和删除时可能需要移动元素。

    import java.util.Arrays;

    class SequentialList {
        private int[] data;
        private int size;
        private int capacity;

        public SequentialList(int capacity) {
            this.capacity = capacity;
            this.data = new int[capacity];
            this.size = 0;
        }

        public void add(int value) {
            if (size == capacity) {
                throw new IllegalStateException("List is full");
            }
            data[size++] = value;
        }

        public void remove(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("Index out of bounds");
            }
            for (int i = index; i < size - 1; i++) {
                data[i] = data[i + 1];
            }
            size--;
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("Index out of bounds");
            }
            return data[index];
        }

        public int size() {
            return size;
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOf(data, size));
        }
    }

3. 链表

链表的特点是插入和删除操作效率高，但不支持随机访问。

3.1 单链表

每个节点包含数据和指向下一个节点的指针。

    class Node {
        int data;
        Node next;

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

    class SinglyLinkedList {
        private Node head;

        public void add(int value) {
            Node newNode = new Node(value);
            if (head == null) {
                head = newNode;
            } else {
                Node current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }

        public void remove(int value) {
            if (head == null) return;

            if (head.data == value) {
                head = head.next;
                return;
            }

            Node current = head;
            while (current.next != null) {
                if (current.next.data == value) {
                    current.next = current.next.next;
                    return;
                }
                current = current.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node current = head;
            while (current != null) {
                sb.append(current.data).append(" -> ");
                current = current.next;
            }
            sb.append("null");
            return sb.toString();
        }
    }

3.2 双链表

每个节点包含数据、指向下一个节点和前一个节点的指针。

    class DNode {
        int data;
        DNode next;
        DNode prev;

        DNode(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    class DoublyLinkedList {
        private DNode head;

        public void add(int value) {
            DNode newNode = new DNode(value);
            if (head == null) {
                head = newNode;
            } else {
                DNode current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
                newNode.prev = current;
            }
        }

        public void remove(int value) {
            if (head == null) return;

            if (head.data == value) {
                head = head.next;
                if (head != null) head.prev = null;
                return;
            }

            DNode current = head;
            while (current != null) {
                if (current.data == value) {
                    if (current.next != null) {
                        current.next.prev = current.prev;
                    }
                    if (current.prev != null) {
                        current.prev.next = current.next;
                    }
                    return;
                }
                current = current.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            DNode current = head;
            while (current != null) {
                sb.append(current.data).append(" <-> ");
                current = current.next;
            }
            sb.append("null");
            return sb.toString();
        }
    }

总结

• 顺序表适合频繁访问元素的场景，但在插入和删除时效率较低。
• 单链表适合频繁插入和删除的场景，但不支持快速随机访问。
• 双链表在单链表的基础上增加了前驱指针，支持双向遍历。

这些结构各有特点，选择合适的数据结构能有效提升程序的性能和效率。

三、栈和队列

1. 栈（Stack）

定义：栈是一种后进先出（LIFO，Last In First Out）的数据结构。最后插入的元素最先被移除。

import java.util.EmptyStackException;

class Stack {
    private int[] data;
    private int top;
    private int capacity;

    public Stack(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.top = -1; // 栈顶指针，初始为空
    }

    public void push(int value) {
        if (top == capacity - 1) {
            throw new StackOverflowError("Stack is full");
        }
        data[++top] = value; // 增加栈顶指针，并插入新值
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data[top--]; // 返回栈顶元素，并降低栈顶指针
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data[top]; // 返回栈顶元素但不移除它
    }

    public boolean isEmpty() {
        return top == -1; // 检查栈是否为空
    }
}

解释：

• push(int value)：向栈中插入元素。
• pop()：从栈中移除并返回栈顶元素。
• peek()：查看栈顶元素而不移除。
• isEmpty()：检查栈是否为空。

2. 队列（Queue）

定义：队列是一种先进先出（FIFO，First In First Out）的数据结构。最先插入的元素最先被移除。

import java.util.NoSuchElementException;

class Queue {
    private int[] data;
    private int front;
    private int rear;
    private int capacity;
    private int size;

    public Queue(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    public void enqueue(int value) {
        if (size == capacity) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % capacity; // 循环队列实现
        data[rear] = value;
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int value = data[front];
        front = (front + 1) % capacity; // 循环队列实现
        size--;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return data[front]; // 返回队首元素但不移除
    }

    public boolean isEmpty() {
        return size == 0; // 检查队列是否为空
    }
}

解释：

• enqueue(int value)：将元素添加到队列的尾部。
• dequeue()：从队列的前面移除并返回元素。
• peek()：查看队首元素而不移除。
• isEmpty()：检查队列是否为空。

3. 递归（Recursion）

定义：递归是一种解决问题的方法，其中一个函数调用自身来解决问题。通常用于解决可以被分解为更小的同类问题的情况。

示例实现：计算阶乘。

class Factorial {
    public static int factorial(int n) {
        if (n == 0) { // 基本情况
            return 1;
        }
        return n * factorial(n - 1); // 递归调用
    }
}

解释：

• factorial(int n)：计算整数 n 的阶乘。
• 基本情况：当 n 为 0 时，返回 1（0 的阶乘定义为 1）。
• 递归情况：返回 n 乘以 n-1 的阶乘。

总结

• 栈：用于管理需要后进先出操作的数据，例如函数调用管理、表达式求值等。
• 队列：用于管理需要先进先出操作的数据，例如任务调度、消息传递等。
• 递归：解决问题的强大工具，可以简化代码，但需要注意基本情况和递归深度，以防止栈溢出。

        这些数据结构和概念在计算机科学和编程中具有广泛的应用，理解它们的实现和特性有助于更好地设计和优化程序。

四、树

1. 树的基本概念

• 定义：树是一种分层的数据结构，由节点（Node）组成，节点之间存在父子关系。一个树由一个根节点（Root）和若干子节点构成。
• 节点：树的基本组成单位，包含数据和指向子节点的指针。
• 边：连接两个节点的链接。
• 高度：树的高度是从根到叶子节点的最长路径上的边数。
• 叶子节点：没有子节点的节点。
• 内部节点：至少有一个子节点的节点。
• 子树：某个节点的所有后代节点和该节点本身组成的树。

2. 二叉树

二叉树是树的一种特殊形式，每个节点最多有两个子节点，通常称为左子节点和右子节点。

2.1 二叉树的节点类

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

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

2.2 二叉树的实现

class BinaryTree {
    private TreeNode root;

    public BinaryTree() {
        this.root = null;
    }

    // 插入节点
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode node, int value) {
        if (node == null) {
            node = new TreeNode(value);
            return node;
        }
        if (value < node.data) {
            node.left = insertRec(node.left, value);
        } else if (value > node.data) {
            node.right = insertRec(node.right, value);
        }
        return node;
    }

    // 前序遍历
    public void preOrder() {
        preOrderRec(root);
    }

    private void preOrderRec(TreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderRec(node.left);
            preOrderRec(node.right);
        }
    }

    // 中序遍历
    public void inOrder() {
        inOrderRec(root);
    }

    private void inOrderRec(TreeNode node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.print(node.data + " ");
            inOrderRec(node.right);
        }
    }

    // 后序遍历
    public void postOrder() {
        postOrderRec(root);
    }

    private void postOrderRec(TreeNode node) {
        if (node != null) {
            postOrderRec(node.left);
            postOrderRec(node.right);
            System.out.print(node.data + " ");
        }
    }
}

3. 二叉搜索树（BST）

二叉搜索树是二叉树的一种特殊形式，具有以下性质：

• 对于每个节点，左子树的值小于该节点的值，右子树的值大于该节点的值。

4. 树的遍历方式

• 前序遍历（Pre-order Traversal）：根 -> 左 -> 右
• 中序遍历（In-order Traversal）：左 -> 根 -> 右
• 后序遍历（Post-order Traversal）：左 -> 右 -> 根

5. 其他树类型

• 平衡树：如 AVL 树和红黑树，旨在保持树的高度尽可能小，以确保高效的搜索、插入和删除操作。
• N叉树：每个节点可以有 N 个子节点的树，常用于表示多层级的数据结构，如文件系统。
• Trie：一种树形结构，主要用于字符串查找，例如自动补全和拼写检查。

6. 示例：构建和遍历二叉树

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("前序遍历:");
        tree.preOrder();

        System.out.println("\n中序遍历:");
        tree.inOrder();

        System.out.println("\n后序遍历:");
        tree.postOrder();
    }
}

总结

树是一种非常重要的数据结构，适合于表示具有层次关系的数据。理解树的基本概念和实现对于算法设计和数据处理具有重要意义。通过对不同类型的树的理解，程序员可以更有效地选择合适的数据结构来解决特定的问题。

五、图

1. 图的基本概念

• 定义：图由一组节点（顶点）和一组连接这些节点的边构成。图可以表示许多现实世界的问题，如社交网络、道路网络等。
• 顶点：图中的基本单位，代表对象。
• 边：连接两个顶点的线，表示它们之间的关系。
• 有向图：边有方向，即边从一个顶点指向另一个顶点。
• 无向图：边没有方向，即连接的两个顶点是对称的。
• 加权图：边有权重，用于表示两个顶点之间的距离或成本。
• 无权图：边没有权重。

2. 图的表示方式

2.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个二维数组，用于表示图的连接情况。如果存在一条边连接顶点 iii 和顶点 jjj，则 matrix[i][j] 为 1（或边的权重），否则为 0。

class GraphAdjacencyMatrix {
    private int[][] matrix;
    private int vertices;

    public GraphAdjacencyMatrix(int size) {
        vertices = size;
        matrix = new int[size][size];
    }

    public void addEdge(int source, int destination) {
        matrix[source][destination] = 1; // 有向图
        // matrix[destination][source] = 1; // 无向图
    }

    public void display() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

2.2 邻接链表（Adjacency List）

邻接链表使用链表来表示每个顶点的邻接边，更加节省空间，特别是对于稀疏图。

import java.util.LinkedList;

class GraphAdjacencyList {
    private LinkedList<Integer>[] adjacencyList;
    private int vertices;

    public GraphAdjacencyList(int size) {
        vertices = size;
        adjacencyList = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination); // 有向图
        // adjacencyList[destination].add(source); // 无向图
    }

    public void display() {
        for (int i = 0; i < vertices; i++) {
            System.out.print(i + ": ");
            for (int neighbor : adjacencyList[i]) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

3. 图的基本操作

• 添加边：在图中连接两个顶点。
• 删除边：移除连接两个顶点的边。
• 遍历图：通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历图。

3.1 深度优先搜索（DFS）

class GraphDFS {
    private boolean[] visited;

    public void dfs(int vertex, GraphAdjacencyList graph) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int neighbor : graph.adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph);
            }
        }
    }
}

3.2 广度优先搜索（BFS）

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

class GraphBFS {
    public void bfs(int startVertex, GraphAdjacencyList graph) {
        boolean[] visited = new boolean[graph.vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int neighbor : graph.adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

4. 图的应用

• 最短路径算法：如 Dijkstra 算法和 Bellman-Ford 算法，用于计算从一个顶点到其他顶点的最短路径。
• 最小生成树：如 Prim 算法和 Kruskal 算法，用于找到连接所有顶点的最小边权重和的树。
• 网络流：用于解决网络中最大流的问题。

5. 示例：构建和遍历图

public class Main {
    public static void main(String[] args) {
        GraphAdjacencyList graph = new GraphAdjacencyList(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        System.out.println("图的邻接链表表示：");
        graph.display();

        System.out.println("深度优先遍历：");
        GraphDFS dfs = new GraphDFS();
        dfs.visited = new boolean[5]; // 初始化访问状态
        dfs.dfs(0, graph);

        System.out.println("\n广度优先遍历：");
        GraphBFS bfs = new GraphBFS();
        bfs.bfs(0, graph);
    }
}

总结

图是一种灵活的数据结构，能够有效地表示复杂的关系。掌握图的基本概念、表示方法和遍历方式对于解决各种算法问题至关重要。通过以上实现，可以帮助你理解图的工作原理和应用场景。

六、排序

1. 排序的基本概念

• 定义：排序是将一组元素按特定顺序（如升序或降序）排列的过程。
• 稳定性：排序算法是否保留相同元素的相对顺序。稳定的排序算法在排序后，相同元素的相对位置不变。
• 时间复杂度：排序算法执行所需的时间，通常用大O表示法描述。
• 空间复杂度：排序算法所需的额外空间。

2. 排序算法分类

2.1 冒泡排序（Bubble Sort）

冒泡排序是一种简单的交换排序算法，通过重复交换相邻的元素，将最大的元素“冒泡”到序列的末尾。

实现：

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

2.2 选择排序（Selection Sort）

选择排序通过每次选择未排序部分的最小（或最大）元素，将其放到已排序部分的末尾。

实现：

public class SelectionSort {
    public static void selectionSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }
}

2.3 插入排序（Insertion Sort）

插入排序通过构建已排序部分，并逐步将新元素插入到已排序部分的正确位置。

实现：

public class InsertionSort {
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
}

2.4 合并排序（Merge Sort）

合并排序是一种分治法算法，将数组分为两部分，分别排序后再合并。

实现：

public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return; // 基本情况
        }
        int mid = array.length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        System.arraycopy(array, 0, left, 0, mid);
        System.arraycopy(array, mid, right, 0, array.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(array, left, right);
    }

    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        while (i < left.length) {
            array[k++] = left[i++];
        }
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }
}

2.5 快速排序（Quick Sort）

快速排序也是一种分治法算法，选择一个“基准”元素，通过分区将数组分为两部分，递归排序。

实现：

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;
    }
}

3. 其他排序算法

• 希尔排序（Shell Sort）：插入排序的优化，通过分组进行排序。
• 堆排序（Heap Sort）：利用堆数据结构进行排序，时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)。
• 基数排序（Radix Sort）：非比较型排序，通过按位比较进行排序，适合特定数据类型。

4. 排序的应用

排序在许多算法和应用中扮演着重要角色，例如：

• 数据分析和处理
• 搜索算法的优化
• 任务调度
• 数据压缩和加密

5. 示例：调用排序算法

public class Main {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        // 冒泡排序
        BubbleSort.bubbleSort(array);
        System.out.println("冒泡排序后的数组:");
        printArray(array);

        // 选择排序
        int[] array2 = {64, 34, 25, 12, 22, 11, 90};
        SelectionSort.selectionSort(array2);
        System.out.println("选择排序后的数组:");
        printArray(array2);

        // 插入排序
        int[] array3 = {64, 34, 25, 12, 22, 11, 90};
        InsertionSort.insertionSort(array3);
        System.out.println("插入排序后的数组:");
        printArray(array3);

        // 合并排序
        int[] array4 = {64, 34, 25, 12, 22, 11, 90};
        MergeSort.mergeSort(array4);
        System.out.println("合并排序后的数组:");
        printArray(array4);

        // 快速排序
        int[] array5 = {64, 34, 25, 12, 22, 11, 90};
        QuickSort.quickSort(array5, 0, array5.length - 1);
        System.out.println("快速排序后的数组:");
        printArray(array5);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

总结

排序是计算机科学中的基本操作，理解各种排序算法的实现及其时间复杂度、稳定性等特性对于编写高效的程序非常重要。选择合适的排序算法能够提高程序的性能和效率。通过以上示例，可以清楚地看到各种排序算法的实现和使用方式。

七、查找

1. 线性查找（Linear Search）

线性查找是一种简单的查找方法，逐个检查每个元素，直到找到目标元素或遍历完所有元素。

实现：

public class LinearSearch {
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // 返回目标元素的索引
            }
        }
        return -1; // 未找到
    }
}

解析：

• 时间复杂度：O(n)，最坏情况下需要检查所有元素。
• 空间复杂度：O(1)，不需要额外空间。
• 适用于小型或无序数据集。

2. 二分查找（Binary Search）

二分查找是一种高效的查找方法，适用于有序数组。它通过反复将搜索范围减半来查找目标元素。

实现：

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

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出

            if (array[mid] == target) {
                return mid; // 返回目标元素的索引
            } else if (array[mid] < target) {
                left = mid + 1; // 在右半部分继续查找
            } else {
                right = mid - 1; // 在左半部分继续查找
            }
        }
        return -1; // 未找到
    }
}

解析：

• 时间复杂度：O(log n)，每次将搜索范围减半。
• 空间复杂度：O(1)，不需要额外空间。
• 适用于大规模的有序数据集。

3. 插值查找（Interpolation Search）

插值查找是一种改进的二分查找，适用于均匀分布的有序数组。它根据目标元素与数组最小值和最大值的比例估算位置。

实现：

public class InterpolationSearch {
    public static int interpolationSearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high && target >= array[low] && target <= array[high]) {
            if (low == high) {
                if (array[low] == target) {
                    return low; // 找到
                }
                return -1; // 未找到
            }

            int pos = low + (target - array[low]) * (high - low) / (array[high] - array[low]);
            if (array[pos] == target) {
                return pos; // 找到
            } else if (array[pos] < target) {
                low = pos + 1; // 在右侧查找
            } else {
                high = pos - 1; // 在左侧查找
            }
        }
        return -1; // 未找到
    }
}

解析：

• 时间复杂度：平均情况 O(log log n)，最坏情况下 O(n)，当元素分布不均匀时。
• 空间复杂度：O(1)，不需要额外空间。
• 适用于均匀分布的有序数组。

4. 跳表查找（Skip List）

跳表是一种随机化的数据结构，允许快速查找。它通过多级链表来跳过不必要的元素。

实现（简化版）：

import java.util.Random;

class SkipListNode {
    int value;
    SkipListNode[] forward;

    SkipListNode(int level, int value) {
        this.value = value;
        forward = new SkipListNode[level + 1];
    }
}

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private SkipListNode header;
    private int level;
    private Random random;

    public SkipList() {
        header = new SkipListNode(MAX_LEVEL, Integer.MIN_VALUE);
        level = 0;
        random = new Random();
    }

    public void insert(int value) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = header;

        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        current = current.forward[0];
        if (current == null || current.value != value) {
            int newLevel = randomLevel();
            if (newLevel > level) {
                for (int i = level + 1; i <= newLevel; i++) {
                    update[i] = header;
                }
                level = newLevel;
            }

            SkipListNode newNode = new SkipListNode(newLevel, value);
            for (int i = 0; i <= newLevel; i++) {
                newNode.forward[i] = update[i].forward[i];
                update[i].forward[i] = newNode;
            }
        }
    }

    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextBoolean()) {
            lvl++;
        }
        return lvl;
    }

    public boolean search(int value) {
        SkipListNode current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == value;
    }
}

解析：

• 时间复杂度：O(log n) 平均情况下，O(n) 最坏情况下。
• 空间复杂度：O(n)，每个元素可能需要多条指针。
• 跳表是高效的查找结构，具有平衡树的优点。

5. 哈希查找（Hash Search）

哈希查找使用哈希表结构来实现快速查找，通过将键映射到索引位置来查找元素。

实现：

import java.util.HashMap;

public class HashSearch {
    private HashMap<Integer, String> map;

    public HashSearch() {
        map = new HashMap<>();
    }

    public void insert(int key, String value) {
        map.put(key, value);
    }

    public String search(int key) {
        return map.getOrDefault(key, null); // 返回对应值或 null
    }
}

解析：

• 时间复杂度：O(1) 平均情况下，O(n) 最坏情况下（哈希冲突）。
• 空间复杂度：O(n)，需要额外空间来存储哈希表。
• 适用于需要频繁查找的场景。

6. 示例：调用查找算法

public class Main {
    public static void main(String[] args) {
        // 线性查找
        int[] array = {10, 20, 30, 40, 50};
        int target = 30;
        System.out.println("线性查找结果: " + LinearSearch.linearSearch(array, target));

        // 二分查找
        int[] sortedArray = {10, 20, 30, 40, 50};
        System.out.println("二分查找结果: " + BinarySearch.binarySearch(sortedArray, target));

        // 插值查找
        int[] uniformSortedArray = {10, 20, 30, 40, 50};
        System.out.println("插值查找结果: " + InterpolationSearch.interpolationSearch(uniformSortedArray, target));

        // 跳表查找
        SkipList skipList = new SkipList();
        skipList.insert(10);
        skipList.insert(20);
        skipList.insert(30);
        System.out.println("跳表查找结果: " + skipList.search(30));

        // 哈希查找
        HashSearch hashSearch = new HashSearch();
        hashSearch.insert(1, "One");
        hashSearch.insert(2, "Two");
        System.out.println("哈希查找结果: " + hashSearch.search(1));
    }
}

总结

查找方法在数据结构中扮演着重要角色，不同的查找方法适用于不同的数据结构和场景。理解这些查找方法及其优缺点，能够帮助开发者选择最合适的查找方式，以提高程序的性能和效率

八、哈希表

哈希表（Hash Table）是一种常用的数据结构，用于快速查找、插入和删除操作。其主要特点是通过将键映射到数组的索引来实现高效的查找。以下是关于哈希表的详细内容，包括其基本概念、实现、常见操作、冲突解决方法以及Java中的示例代码。

1. 哈希表的基本概念

• 定义：哈希表是一种将键（Key）映射到值（Value）的数据结构，它使用哈希函数将键转换为数组索引，以便快速访问对应的值。
• 哈希函数：一个将键转换为数组索引的函数。好的哈希函数应该能够均匀分布键，减少冲突。
• 冲突：当两个不同的键被哈希到相同的索引时，称为冲突。哈希表需要有效地处理冲突以确保性能。
• 负载因子：哈希表中元素的数量与数组大小的比例。通常，负载因子越高，发生冲突的可能性越大。

2. 哈希表的实现

2.1 哈希表的基本结构

class HashNode<K, V> {
    K key;
    V value;
    HashNode<K, V> next; // 链表用于解决冲突

    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class HashTable<K, V> {
    private HashNode<K, V>[] table; // 哈希表数组
    private int capacity; // 数组的大小
    private int size; // 哈希表中元素的数量

    public HashTable(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.table = new HashNode[capacity];
    }

    // 哈希函数
    private int hashFunction(K key) {
        return key.hashCode() % capacity; // 计算哈希值并取模
    }

    // 插入元素
    public void put(K key, V value) {
        int index = hashFunction(key);
        HashNode<K, V> newNode = new HashNode<>(key, value);

        if (table[index] == null) {
            table[index] = newNode; // 没有冲突，直接插入
        } else {
            // 处理冲突，使用链表
            HashNode<K, V> current = table[index];
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value; // 更新值
                    return;
                }
                current = current.next;
            }
            // 如果没有找到相同的键，将新节点添加到链表的头部
            newNode.next = table[index];
            table[index] = newNode;
        }
        size++;
    }

    // 查找元素
    public V get(K key) {
        int index = hashFunction(key);
        HashNode<K, V> current = table[index];

        while (current != null) {
            if (current.key.equals(key)) {
                return current.value; // 找到返回值
            }
            current = current.next;
        }
        return null; // 未找到
    }

    // 删除元素
    public void remove(K key) {
        int index = hashFunction(key);
        HashNode<K, V> current = table[index];
        HashNode<K, V> previous = null;

        while (current != null) {
            if (current.key.equals(key)) {
                if (previous == null) {
                    // 删除的是头节点
                    table[index] = current.next;
                } else {
                    previous.next = current.next; // 连接前一个节点和下一个节点
                }
                size--;
                return;
            }
            previous = current;
            current = current.next;
        }
    }

    // 返回哈希表的大小
    public int size() {
        return size;
    }

    // 判断哈希表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

3. 哈希表的基本操作

3.1 插入操作（put）

• 描述：通过计算键的哈希值，将键值对插入哈希表。如果发生冲突，使用链表将新的节点添加到相应的索引中。
• 复杂度：O(1) 平均情况下，O(n) 最坏情况下（所有元素都发生冲突）。

3.2 查找操作（get）

• 描述：计算键的哈希值，通过索引访问对应的链表，查找相应的键并返回值。
• 复杂度：O(1) 平均情况下，O(n) 最坏情况下（链表中的所有元素都需要检查）。

3.3 删除操作（remove）

• 描述：计算键的哈希值，查找对应的链表，找到后将节点从链表中移除。
• 复杂度：O(1) 平均情况下，O(n) 最坏情况下（所有元素都发生冲突）。

4. 处理冲突的方法

• 链地址法：使用链表存储同一索引的多个元素（如上面实现所示）。
• 开放地址法：在数组中查找下一个可用位置，常见策略有线性探测、二次探测和双重哈希。

5. 优化与扩展

• 动态扩容：当负载因子超过某个阈值时，增加哈希表的大小并重新哈希所有元素。
• 自定义哈希函数：可以根据具体需求自定义哈希函数，以减少冲突。
• 使用Java内置的哈希表类：Java 提供了 HashMap 类，内置处理冲突和动态扩容，适合大多数场景。

6. 示例：使用哈希表

public class Main {
    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>(10);

        // 插入元素
        hashTable.put("Alice", 25);
        hashTable.put("Bob", 30);
        hashTable.put("Charlie", 35);

        // 查找元素
        System.out.println("Alice's age: " + hashTable.get("Alice")); // 输出 25
        System.out.println("Bob's age: " + hashTable.get("Bob")); // 输出 30

        // 删除元素
        hashTable.remove("Bob");
        System.out.println("Bob's age after removal: " + hashTable.get("Bob")); // 输出 null

        // 检查哈希表大小
        System.out.println("Size of hash table: " + hashTable.size()); // 输出 2

        // 检查是否为空
        System.out.println("Is hash table empty? " + hashTable.isEmpty()); // 输出 false
    }
}

总结

哈希表是一种强大的数据结构，能够以高效的方式实现查找、插入和删除操作。理解哈希表的实现、操作和冲突处理方法是掌握数据结构与算法的重要部分。通过使用哈希表，我们可以在许多应用场景中提高性能和效率。使用Java内置的HashMap类，能够更方便地实现哈希表的功能，同时享受更好的性能和稳定性。