IT评测·应用市场-qidao123.com技术社区

标题: 8876行详解数据结构,从入门到入坟 [打印本页]

作者: 盛世宏图    时间: 2025-4-8 13:09
标题: 8876行详解数据结构,从入门到入坟
数据结构详解

目次

1. 数据结构概述

1.1 什么是数据结构

数据结构是计算机存储、构造数据的方式,它形貌了数据元素之间的逻辑关系。好的数据结构计划可以提高步伐的运行服从,降低资源斲丧。
1.2 数据结构的重要性


1.3 数据结构分类

2. 基本数据结构

2.1 数组(Array)

2.1.1 数组的基本概念

数组是最底子的数据结构,它是一块连续的内存空间,用来存储相同范例的数据。
想象一下:

2.1.2 数组的特点

2.1.3 数组的基本操作

  1. // 方式1:指定大小
  2. int[] arr1 = new int[5];
  3. // 方式2:直接初始化
  4. int[] arr2 = {1, 2, 3, 4, 5};
  5. // 方式3:先声明后初始化
  6. int[] arr3;
  7. arr3 = new int[]{1, 2, 3};
复制代码
  1. // 读取元素
  2. int first = arr[0];    // 获取第一个元素
  3. int last = arr[arr.length - 1];  // 获取最后一个元素
  4. // 修改元素
  5. arr[0] = 10;  // 修改第一个元素
复制代码
  1. // 方式1:for循环
  2. for (int i = 0; i < arr.length; i++) {
  3.     System.out.println(arr[i]);
  4. }
  5. // 方式2:增强for循环
  6. for (int num : arr) {
  7.     System.out.println(num);
  8. }
  9. // 方式3:Arrays工具类
  10. Arrays.stream(arr).forEach(System.out::println);
复制代码
  1. // 线性查找
  2. public static int linearSearch(int[] arr, int target) {
  3.     for (int i = 0; i < arr.length; i++) {
  4.         if (arr[i] == target) {
  5.             return i;
  6.         }
  7.     }
  8.     return -1;  // 未找到
  9. }
  10. // 二分查找(要求数组有序)
  11. public static int binarySearch(int[] arr, int target) {
  12.     int left = 0;
  13.     int right = arr.length - 1;
  14.    
  15.     while (left <= right) {
  16.         int mid = left + (right - left) / 2;
  17.         if (arr[mid] == target) {
  18.             return mid;
  19.         } else if (arr[mid] < target) {
  20.             left = mid + 1;
  21.         } else {
  22.             right = mid - 1;
  23.         }
  24.     }
  25.     return -1;  // 未找到
  26. }
复制代码
2.1.4 数组的常见问题

  1. int[] arr = new int[5];
  2. arr[5] = 10;  // ArrayIndexOutOfBoundsException
复制代码
  1. int[] arr = null;
  2. arr[0] = 10;  // NullPointerException
复制代码
  1. // 方式1:System.arraycopy
  2. int[] source = {1, 2, 3, 4, 5};
  3. int[] dest = new int[5];
  4. System.arraycopy(source, 0, dest, 0, source.length);
  5. // 方式2:Arrays.copyOf
  6. int[] copy = Arrays.copyOf(source, source.length);
  7. // 方式3:clone方法
  8. int[] clone = source.clone();
复制代码
2.1.5 多维数组

  1. // 创建二维数组
  2. int[][] matrix = new int[3][4];  // 3行4列
  3. // 初始化二维数组
  4. int[][] grid = {
  5.     {1, 2, 3},
  6.     {4, 5, 6},
  7.     {7, 8, 9}
  8. };
  9. // 访问元素
  10. int value = grid[1][2];  // 访问第2行第3列的元素
复制代码
  1. // 创建不规则数组
  2. int[][] irregular = new int[3][];
  3. irregular[0] = new int[3];  // 第一行3个元素
  4. irregular[1] = new int[4];  // 第二行4个元素
  5. irregular[2] = new int[2];  // 第三行2个元素
复制代码
2.1.6 数组的优缺点

优点:
缺点:
2.1.7 数组的应用场景

2.2 链表(Linked List)

2.2.1 链表的基本概念

链表是一种线性数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
想象一下:

2.2.2 链表的特点

2.2.3 链表的范例

2.2.4 链表的基本操作

  1. // 单链表节点
  2. class Node<T> {
  3.     T data;           // 数据
  4.     Node<T> next;     // 指向下一个节点的指针
  5.    
  6.     Node(T data) {
  7.         this.data = data;
  8.         this.next = null;
  9.     }
  10. }
  11. // 双链表节点
  12. class DoublyNode<T> {
  13.     T data;                  // 数据
  14.     DoublyNode<T> prev;      // 指向前一个节点的指针
  15.     DoublyNode<T> next;      // 指向下一个节点的指针
  16.    
  17.     DoublyNode(T data) {
  18.         this.data = data;
  19.         this.prev = null;
  20.         this.next = null;
  21.     }
  22. }
复制代码
  1. // 在单链表头部插入节点
  2. public void insertAtHead(T data) {
  3.     Node<T> newNode = new Node<>(data);
  4.     newNode.next = head;
  5.     head = newNode;
  6.     size++;
  7. }
  8. // 在单链表尾部插入节点
  9. public void insertAtTail(T data) {
  10.     Node<T> newNode = new Node<>(data);
  11.     if (head == null) {
  12.         head = newNode;
  13.     } else {
  14.         Node<T> current = head;
  15.         while (current.next != null) {
  16.             current = current.next;
  17.         }
  18.         current.next = newNode;
  19.     }
  20.     size++;
  21. }
  22. // 在单链表指定位置插入节点
  23. public void insertAtPosition(T data, int position) {
  24.     if (position < 0 || position > size) {
  25.         throw new IllegalArgumentException("Position is invalid");
  26.     }
  27.    
  28.     if (position == 0) {
  29.         insertAtHead(data);
  30.         return;
  31.     }
  32.    
  33.     Node<T> newNode = new Node<>(data);
  34.     Node<T> current = head;
  35.     for (int i = 0; i < position - 1; i++) {
  36.         current = current.next;
  37.     }
  38.     newNode.next = current.next;
  39.     current.next = newNode;
  40.     size++;
  41. }
复制代码
  1. // 删除单链表头部节点
  2. public T deleteFromHead() {
  3.     if (head == null) {
  4.         throw new NoSuchElementException("List is empty");
  5.     }
  6.     T data = head.data;
  7.     head = head.next;
  8.     size--;
  9.     return data;
  10. }
  11. // 删除单链表尾部节点
  12. public T deleteFromTail() {
  13.     if (head == null) {
  14.         throw new NoSuchElementException("List is empty");
  15.     }
  16.    
  17.     if (head.next == null) {
  18.         T data = head.data;
  19.         head = null;
  20.         size--;
  21.         return data;
  22.     }
  23.    
  24.     Node<T> current = head;
  25.     while (current.next.next != null) {
  26.         current = current.next;
  27.     }
  28.     T data = current.next.data;
  29.     current.next = null;
  30.     size--;
  31.     return data;
  32. }
  33. // 删除单链表指定位置的节点
  34. public T deleteFromPosition(int position) {
  35.     if (position < 0 || position >= size) {
  36.         throw new IllegalArgumentException("Position is invalid");
  37.     }
  38.    
  39.     if (position == 0) {
  40.         return deleteFromHead();
  41.     }
  42.    
  43.     Node<T> current = head;
  44.     for (int i = 0; i < position - 1; i++) {
  45.         current = current.next;
  46.     }
  47.     T data = current.next.data;
  48.     current.next = current.next.next;
  49.     size--;
  50.     return data;
  51. }
复制代码
  1. // 在单链表中查找元素
  2. public int find(T data) {
  3.     Node<T> current = head;
  4.     int position = 0;
  5.    
  6.     while (current != null) {
  7.         if (current.data.equals(data)) {
  8.             return position;
  9.         }
  10.         current = current.next;
  11.         position++;
  12.     }
  13.    
  14.     return -1;  // 未找到
  15. }
  16. // 获取单链表指定位置的元素
  17. public T get(int position) {
  18.     if (position < 0 || position >= size) {
  19.         throw new IllegalArgumentException("Position is invalid");
  20.     }
  21.    
  22.     Node<T> current = head;
  23.     for (int i = 0; i < position; i++) {
  24.         current = current.next;
  25.     }
  26.    
  27.     return current.data;
  28. }
复制代码
  1. // 遍历单链表
  2. public void traverse() {
  3.     Node<T> current = head;
  4.     while (current != null) {
  5.         System.out.print(current.data + " -> ");
  6.         current = current.next;
  7.     }
  8.     System.out.println("null");
  9. }
  10. // 递归遍历单链表
  11. public void traverseRecursive(Node<T> node) {
  12.     if (node == null) {
  13.         System.out.println("null");
  14.         return;
  15.     }
  16.     System.out.print(node.data + " -> ");
  17.     traverseRecursive(node.next);
  18. }
复制代码
2.2.5 链表的常见问题

  1. // 使用快慢指针检测单链表中的环
  2. public boolean hasCycle() {
  3.     if (head == null || head.next == null) {
  4.         return false;
  5.     }
  6.    
  7.     Node<T> slow = head;
  8.     Node<T> fast = head;
  9.    
  10.     while (fast != null && fast.next != null) {
  11.         slow = slow.next;
  12.         fast = fast.next.next;
  13.         
  14.         if (slow == fast) {
  15.             return true;  // 发现环
  16.         }
  17.     }
  18.    
  19.     return false;  // 无环
  20. }
复制代码
  1. // 反转单链表
  2. public void reverse() {
  3.     Node<T> prev = null;
  4.     Node<T> current = head;
  5.     Node<T> next = null;
  6.    
  7.     while (current != null) {
  8.         next = current.next;  // 保存下一个节点
  9.         current.next = prev;  // 反转指针
  10.         prev = current;       // 移动prev指针
  11.         current = next;       // 移动current指针
  12.     }
  13.    
  14.     head = prev;  // 更新头节点
  15. }
  16. // 递归反转单链表
  17. public Node<T> reverseRecursive(Node<T> current) {
  18.     if (current == null || current.next == null) {
  19.         return current;
  20.     }
  21.    
  22.     Node<T> rest = reverseRecursive(current.next);
  23.     current.next.next = current;
  24.     current.next = null;
  25.    
  26.     return rest;
  27. }
复制代码
  1. // 合并两个有序单链表
  2. public static <T extends Comparable<T>> Node<T> mergeSortedLists(Node<T> list1, Node<T> list2) {
  3.     Node<T> dummy = new Node<>(null);
  4.     Node<T> current = dummy;
  5.    
  6.     while (list1 != null && list2 != null) {
  7.         if (list1.data.compareTo(list2.data) <= 0) {
  8.             current.next = list1;
  9.             list1 = list1.next;
  10.         } else {
  11.             current.next = list2;
  12.             list2 = list2.next;
  13.         }
  14.         current = current.next;
  15.     }
  16.    
  17.     if (list1 != null) {
  18.         current.next = list1;
  19.     }
  20.    
  21.     if (list2 != null) {
  22.         current.next = list2;
  23.     }
  24.    
  25.     return dummy.next;
  26. }
复制代码
  1. // 使用快慢指针找到单链表的中间节点
  2. public Node<T> findMiddle() {
  3.     if (head == null) {
  4.         return null;
  5.     }
  6.    
  7.     Node<T> slow = head;
  8.     Node<T> fast = head;
  9.    
  10.     while (fast != null && fast.next != null) {
  11.         slow = slow.next;
  12.         fast = fast.next.next;
  13.     }
  14.    
  15.     return slow;
  16. }
复制代码
2.2.6 链表的优缺点

优点:
缺点:
2.2.7 链表的应用场景

2.3 栈(Stack)

栈是一种特殊的线性数据结构,它遵循"后进先出"(LIFO, Last In First Out)的原则。可以将其想象为一个垂直堆叠的盘子,你只能从顶部添加或移除盘子。
2.3.1 栈的特点

2.3.2 栈的基本操作

2.3.3 栈的实现方式

  1. public class ArrayStack<T> {
  2.     private T[] elements;
  3.     private int size;
  4.    
  5.     @SuppressWarnings("unchecked")
  6.     public ArrayStack(int capacity) {
  7.         elements = (T[]) new Object[capacity];
  8.         size = 0;
  9.     }
  10.    
  11.     public void push(T element) {
  12.         if (size == elements.length) {
  13.             resize();
  14.         }
  15.         elements[size++] = element;
  16.     }
  17.    
  18.     public T pop() {
  19.         if (isEmpty()) {
  20.             throw new IllegalStateException("栈为空");
  21.         }
  22.         T element = elements[--size];
  23.         elements[size] = null;
  24.         return element;
  25.     }
  26.    
  27.     public T peek() {
  28.         if (isEmpty()) {
  29.             throw new IllegalStateException("栈为空");
  30.         }
  31.         return elements[size - 1];
  32.     }
  33.    
  34.     public boolean isEmpty() {
  35.         return size == 0;
  36.     }
  37.    
  38.     private void resize() {
  39.         T[] newElements = (T[]) new Object[elements.length * 2];
  40.         System.arraycopy(elements, 0, newElements, 0, size);
  41.         elements = newElements;
  42.     }
  43. }
复制代码
  1. public class LinkedStack<T> {
  2.     private Node<T> top;
  3.     private int size;
  4.    
  5.     private static class Node<T> {
  6.         T data;
  7.         Node<T> next;
  8.         
  9.         Node(T data) {
  10.             this.data = data;
  11.         }
  12.     }
  13.    
  14.     public void push(T element) {
  15.         Node<T> newNode = new Node<>(element);
  16.         newNode.next = top;
  17.         top = newNode;
  18.         size++;
  19.     }
  20.    
  21.     public T pop() {
  22.         if (isEmpty()) {
  23.             throw new IllegalStateException("栈为空");
  24.         }
  25.         T element = top.data;
  26.         top = top.next;
  27.         size--;
  28.         return element;
  29.     }
  30.    
  31.     public T peek() {
  32.         if (isEmpty()) {
  33.             throw new IllegalStateException("栈为空");
  34.         }
  35.         return top.data;
  36.     }
  37.    
  38.     public boolean isEmpty() {
  39.         return top == null;
  40.     }
  41. }
复制代码
2.3.4 栈的应用场景

  1. public int evaluateExpression(String expression) {
  2.     Stack<Integer> operands = new Stack<>();
  3.     Stack<Character> operators = new Stack<>();
  4.    
  5.     for (char c : expression.toCharArray()) {
  6.         if (Character.isDigit(c)) {
  7.             operands.push(c - '0');
  8.         } else if (c == '(') {
  9.             operators.push(c);
  10.         } else if (c == ')') {
  11.             while (!operators.isEmpty() && operators.peek() != '(') {
  12.                 operands.push(calculate(operators.pop(), operands.pop(), operands.pop()));
  13.             }
  14.             operators.pop();
  15.         } else if (isOperator(c)) {
  16.             while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
  17.                 operands.push(calculate(operators.pop(), operands.pop(), operands.pop()));
  18.             }
  19.             operators.push(c);
  20.         }
  21.     }
  22.    
  23.     while (!operators.isEmpty()) {
  24.         operands.push(calculate(operators.pop(), operands.pop(), operands.pop()));
  25.     }
  26.    
  27.     return operands.pop();
  28. }
复制代码
  1. public boolean isBalanced(String expression) {
  2.     Stack<Character> stack = new Stack<>();
  3.    
  4.     for (char c : expression.toCharArray()) {
  5.         if (c == '(' || c == '[' || c == '{') {
  6.             stack.push(c);
  7.         } else if (c == ')' || c == ']' || c == '}') {
  8.             if (stack.isEmpty()) {
  9.                 return false;
  10.             }
  11.             char open = stack.pop();
  12.             if (!isMatching(open, c)) {
  13.                 return false;
  14.             }
  15.         }
  16.     }
  17.    
  18.     return stack.isEmpty();
  19. }
复制代码
  1. public class BrowserHistory {
  2.     private Stack<String> backStack;
  3.     private Stack<String> forwardStack;
  4.     private String currentPage;
  5.    
  6.     public BrowserHistory(String homepage) {
  7.         backStack = new Stack<>();
  8.         forwardStack = new Stack<>();
  9.         currentPage = homepage;
  10.     }
  11.    
  12.     public void visit(String url) {
  13.         backStack.push(currentPage);
  14.         currentPage = url;
  15.         forwardStack.clear();
  16.     }
  17.    
  18.     public String back() {
  19.         if (backStack.isEmpty()) {
  20.             return currentPage;
  21.         }
  22.         forwardStack.push(currentPage);
  23.         currentPage = backStack.pop();
  24.         return currentPage;
  25.     }
  26.    
  27.     public String forward() {
  28.         if (forwardStack.isEmpty()) {
  29.             return currentPage;
  30.         }
  31.         backStack.push(currentPage);
  32.         currentPage = forwardStack.pop();
  33.         return currentPage;
  34.     }
  35. }
复制代码
2.3.5 高级应用

  1. public class MinStack {
  2.     private Stack<Integer> mainStack;
  3.     private Stack<Integer> minStack;
  4.    
  5.     public MinStack() {
  6.         mainStack = new Stack<>();
  7.         minStack = new Stack<>();
  8.     }
  9.    
  10.     public void push(int x) {
  11.         mainStack.push(x);
  12.         if (minStack.isEmpty() || x <= minStack.peek()) {
  13.             minStack.push(x);
  14.         }
  15.     }
  16.    
  17.     public void pop() {
  18.         if (mainStack.pop().equals(minStack.peek())) {
  19.             minStack.pop();
  20.         }
  21.     }
  22.    
  23.     public int top() {
  24.         return mainStack.peek();
  25.     }
  26.    
  27.     public int getMin() {
  28.         return minStack.peek();
  29.     }
  30. }
复制代码
  1. public class StackQueue<T> {
  2.     private Stack<T> stack1;
  3.     private Stack<T> stack2;
  4.    
  5.     public StackQueue() {
  6.         stack1 = new Stack<>();
  7.         stack2 = new Stack<>();
  8.     }
  9.    
  10.     public void enqueue(T element) {
  11.         stack1.push(element);
  12.     }
  13.    
  14.     public T dequeue() {
  15.         if (stack2.isEmpty()) {
  16.             while (!stack1.isEmpty()) {
  17.                 stack2.push(stack1.pop());
  18.             }
  19.         }
  20.         return stack2.pop();
  21.     }
  22. }
复制代码
2.3.6 性能分析

2.3.7 注意事项

2.4 队列(Queue)

队列是一种特殊的线性数据结构,它遵循"先进先出"(FIFO, First In First Out)的原则。可以将其想象为列队买票,先到的人先买票,后到的人后买票。
2.4.1 队列的特点

2.4.2 队列的基本操作

2.4.3 队列的范例

  1. public class ArrayQueue<T> {
  2.     private T[] elements;
  3.     private int front;
  4.     private int rear;
  5.     private int size;
  6.    
  7.     @SuppressWarnings("unchecked")
  8.     public ArrayQueue(int capacity) {
  9.         elements = (T[]) new Object[capacity];
  10.         front = 0;
  11.         rear = -1;
  12.         size = 0;
  13.     }
  14.    
  15.     public void enqueue(T element) {
  16.         if (size == elements.length) {
  17.             resize();
  18.         }
  19.         rear = (rear + 1) % elements.length;
  20.         elements[rear] = element;
  21.         size++;
  22.     }
  23.    
  24.     public T dequeue() {
  25.         if (isEmpty()) {
  26.             throw new IllegalStateException("队列为空");
  27.         }
  28.         T element = elements[front];
  29.         elements[front] = null;
  30.         front = (front + 1) % elements.length;
  31.         size--;
  32.         return element;
  33.     }
  34.    
  35.     public T peek() {
  36.         if (isEmpty()) {
  37.             throw new IllegalStateException("队列为空");
  38.         }
  39.         return elements[front];
  40.     }
  41.    
  42.     public boolean isEmpty() {
  43.         return size == 0;
  44.     }
  45.    
  46.     private void resize() {
  47.         T[] newElements = (T[]) new Object[elements.length * 2];
  48.         for (int i = 0; i < size; i++) {
  49.             newElements[i] = elements[(front + i) % elements.length];
  50.         }
  51.         elements = newElements;
  52.         front = 0;
  53.         rear = size - 1;
  54.     }
  55. }
复制代码
  1. public class CircularQueue<T> {
  2.     private T[] elements;
  3.     private int front;
  4.     private int rear;
  5.     private int size;
  6.    
  7.     @SuppressWarnings("unchecked")
  8.     public CircularQueue(int capacity) {
  9.         elements = (T[]) new Object[capacity];
  10.         front = rear = 0;
  11.         size = 0;
  12.     }
  13.    
  14.     public void enqueue(T element) {
  15.         if (isFull()) {
  16.             resize();
  17.         }
  18.         elements[rear] = element;
  19.         rear = (rear + 1) % elements.length;
  20.         size++;
  21.     }
  22.    
  23.     public T dequeue() {
  24.         if (isEmpty()) {
  25.             throw new IllegalStateException("队列为空");
  26.         }
  27.         T element = elements[front];
  28.         elements[front] = null;
  29.         front = (front + 1) % elements.length;
  30.         size--;
  31.         return element;
  32.     }
  33.    
  34.     public boolean isEmpty() {
  35.         return size == 0;
  36.     }
  37.    
  38.     public boolean isFull() {
  39.         return size == elements.length;
  40.     }
  41.    
  42.     private void resize() {
  43.         T[] newElements = (T[]) new Object[elements.length * 2];
  44.         for (int i = 0; i < size; i++) {
  45.             newElements[i] = elements[(front + i) % elements.length];
  46.         }
  47.         elements = newElements;
  48.         front = 0;
  49.         rear = size;
  50.     }
  51. }
复制代码
  1. public class Deque<T> {
  2.     private Node<T> front;
  3.     private Node<T> rear;
  4.     private int size;
  5.    
  6.     private static class Node<T> {
  7.         T data;
  8.         Node<T> prev;
  9.         Node<T> next;
  10.         
  11.         Node(T data) {
  12.             this.data = data;
  13.         }
  14.     }
  15.    
  16.     public void addFirst(T element) {
  17.         Node<T> newNode = new Node<>(element);
  18.         if (isEmpty()) {
  19.             front = rear = newNode;
  20.         } else {
  21.             newNode.next = front;
  22.             front.prev = newNode;
  23.             front = newNode;
  24.         }
  25.         size++;
  26.     }
  27.    
  28.     public void addLast(T element) {
  29.         Node<T> newNode = new Node<>(element);
  30.         if (isEmpty()) {
  31.             front = rear = newNode;
  32.         } else {
  33.             newNode.prev = rear;
  34.             rear.next = newNode;
  35.             rear = newNode;
  36.         }
  37.         size++;
  38.     }
  39.    
  40.     public T removeFirst() {
  41.         if (isEmpty()) {
  42.             throw new IllegalStateException("队列为空");
  43.         }
  44.         T element = front.data;
  45.         front = front.next;
  46.         if (front == null) {
  47.             rear = null;
  48.         } else {
  49.             front.prev = null;
  50.         }
  51.         size--;
  52.         return element;
  53.     }
  54.    
  55.     public T removeLast() {
  56.         if (isEmpty()) {
  57.             throw new IllegalStateException("队列为空");
  58.         }
  59.         T element = rear.data;
  60.         rear = rear.prev;
  61.         if (rear == null) {
  62.             front = null;
  63.         } else {
  64.             rear.next = null;
  65.         }
  66.         size--;
  67.         return element;
  68.     }
  69.    
  70.     public boolean isEmpty() {
  71.         return size == 0;
  72.     }
  73. }
复制代码
  1. public class PriorityQueue<T extends Comparable<T>> {
  2.     private ArrayList<T> heap;
  3.    
  4.     public PriorityQueue() {
  5.         heap = new ArrayList<>();
  6.     }
  7.    
  8.     public void enqueue(T element) {
  9.         heap.add(element);
  10.         heapifyUp(heap.size() - 1);
  11.     }
  12.    
  13.     public T dequeue() {
  14.         if (isEmpty()) {
  15.             throw new IllegalStateException("队列为空");
  16.         }
  17.         
  18.         T root = heap.get(0);
  19.         T lastElement = heap.remove(heap.size() - 1);
  20.         
  21.         if (!heap.isEmpty()) {
  22.             heap.set(0, lastElement);
  23.             heapifyDown(0);
  24.         }
  25.         
  26.         return root;
  27.     }
  28.    
  29.     private void heapifyUp(int index) {
  30.         int parent = (index - 1) / 2;
  31.         
  32.         while (index > 0 && heap.get(parent).compareTo(heap.get(index)) > 0) {
  33.             swap(parent, index);
  34.             index = parent;
  35.             parent = (index - 1) / 2;
  36.         }
  37.     }
  38.    
  39.     private void heapifyDown(int index) {
  40.         int minIndex = index;
  41.         int leftChild = 2 * index + 1;
  42.         int rightChild = 2 * index + 2;
  43.         
  44.         if (leftChild < heap.size() && heap.get(leftChild).compareTo(heap.get(minIndex)) < 0) {
  45.             minIndex = leftChild;
  46.         }
  47.         
  48.         if (rightChild < heap.size() && heap.get(rightChild).compareTo(heap.get(minIndex)) < 0) {
  49.             minIndex = rightChild;
  50.         }
  51.         
  52.         if (minIndex != index) {
  53.             swap(index, minIndex);
  54.             heapifyDown(minIndex);
  55.         }
  56.     }
  57.    
  58.     private void swap(int i, int j) {
  59.         T temp = heap.get(i);
  60.         heap.set(i, heap.get(j));
  61.         heap.set(j, temp);
  62.     }
  63.    
  64.     public boolean isEmpty() {
  65.         return heap.isEmpty();
  66.     }
  67. }
复制代码
2.4.4 队列的应用场景

  1. public class MessageQueue<T> {
  2.     private Queue<T> queue;
  3.     private final int capacity;
  4.    
  5.     public MessageQueue(int capacity) {
  6.         this.queue = new LinkedList<>();
  7.         this.capacity = capacity;
  8.     }
  9.    
  10.     public synchronized void send(T message) throws InterruptedException {
  11.         while (queue.size() == capacity) {
  12.             wait();  // 队列满时等待
  13.         }
  14.         queue.offer(message);
  15.         notifyAll();  // 通知等待的消费者
  16.     }
  17.    
  18.     public synchronized T receive() throws InterruptedException {
  19.         while (queue.isEmpty()) {
  20.             wait();  // 队列空时等待
  21.         }
  22.         T message = queue.poll();
  23.         notifyAll();  // 通知等待的生产者
  24.         return message;
  25.     }
  26. }
复制代码
  1. public class BufferQueue<T> {
  2.     private CircularQueue<T> buffer;
  3.     private final int capacity;
  4.    
  5.     public BufferQueue(int capacity) {
  6.         this.buffer = new CircularQueue<>(capacity);
  7.         this.capacity = capacity;
  8.     }
  9.    
  10.     public void write(T data) throws InterruptedException {
  11.         synchronized (buffer) {
  12.             while (buffer.isFull()) {
  13.                 buffer.wait();
  14.             }
  15.             buffer.enqueue(data);
  16.             buffer.notifyAll();
  17.         }
  18.     }
  19.    
  20.     public T read() throws InterruptedException {
  21.         synchronized (buffer) {
  22.             while (buffer.isEmpty()) {
  23.                 buffer.wait();
  24.             }
  25.             T data = buffer.dequeue();
  26.             buffer.notifyAll();
  27.             return data;
  28.         }
  29.     }
  30. }
复制代码
  1. public void bfs(Graph graph, int start) {
  2.     boolean[] visited = new boolean[graph.getVertexCount()];
  3.     Queue<Integer> queue = new LinkedList<>();
  4.    
  5.     visited[start] = true;
  6.     queue.offer(start);
  7.    
  8.     while (!queue.isEmpty()) {
  9.         int vertex = queue.poll();
  10.         System.out.print(vertex + " ");
  11.         
  12.         for (int neighbor : graph.getNeighbors(vertex)) {
  13.             if (!visited[neighbor]) {
  14.                 visited[neighbor] = true;
  15.                 queue.offer(neighbor);
  16.             }
  17.         }
  18.     }
  19. }
复制代码
2.4.5 队列的性能分析

2.4.6 注意事项

3. 高级数据结构

3.1 树(Tree)

3.1.0 通俗明确树

想象一下家属族谱或者公司的构造架构图,这就是树的一个很好的例子:

树的特点:

生活中的树结构例子:
3.1.1 基本概念

树是一种非线性数据结构,由节点和边组成,具有以下特点:
3.1.2 树的范例

3.1.3 树的遍历方式

  1. // 前序遍历(根-左-右)
  2. public void preorder(Node node) {
  3.     if (node != null) {
  4.         System.out.print(node.data + " ");
  5.         preorder(node.left);
  6.         preorder(node.right);
  7.     }
  8. }
  9. // 中序遍历(左-根-右)
  10. public void inorder(Node node) {
  11.     if (node != null) {
  12.         inorder(node.left);
  13.         System.out.print(node.data + " ");
  14.         inorder(node.right);
  15.     }
  16. }
  17. // 后序遍历(左-右-根)
  18. public void postorder(Node node) {
  19.     if (node != null) {
  20.         postorder(node.left);
  21.         postorder(node.right);
  22.         System.out.print(node.data + " ");
  23.     }
  24. }
复制代码
  1. public void levelOrder(Node root) {
  2.     if (root == null) return;
  3.    
  4.     Queue<Node> queue = new LinkedList<>();
  5.     queue.offer(root);
  6.    
  7.     while (!queue.isEmpty()) {
  8.         Node node = queue.poll();
  9.         System.out.print(node.data + " ");
  10.         
  11.         if (node.left != null) {
  12.             queue.offer(node.left);
  13.         }
  14.         if (node.right != null) {
  15.             queue.offer(node.right);
  16.         }
  17.     }
  18. }
复制代码
3.1.4 树的基本操作

  1. public void insert(int data) {
  2.     root = insertRec(root, data);
  3. }
  4. private Node insertRec(Node node, int data) {
  5.     if (node == null) {
  6.         return new Node(data);
  7.     }
  8.    
  9.     if (data < node.data) {
  10.         node.left = insertRec(node.left, data);
  11.     } else if (data > node.data) {
  12.         node.right = insertRec(node.right, data);
  13.     }
  14.    
  15.     return node;
  16. }
复制代码
  1. public void delete(int data) {
  2.     root = deleteRec(root, data);
  3. }
  4. private Node deleteRec(Node node, int data) {
  5.     if (node == null) return null;
  6.    
  7.     if (data < node.data) {
  8.         node.left = deleteRec(node.left, data);
  9.     } else if (data > node.data) {
  10.         node.right = deleteRec(node.right, data);
  11.     } else {
  12.         // 找到要删除的节点
  13.         if (node.left == null) {
  14.             return node.right;
  15.         } else if (node.right == null) {
  16.             return node.left;
  17.         }
  18.         
  19.         // 有两个子节点的情况
  20.         node.data = minValue(node.right);
  21.         node.right = deleteRec(node.right, node.data);
  22.     }
  23.    
  24.     return node;
  25. }
  26. private int minValue(Node node) {
  27.     int minv = node.data;
  28.     while (node.left != null) {
  29.         minv = node.left.data;
  30.         node = node.left;
  31.     }
  32.     return minv;
  33. }
复制代码
  1. public Node search(int data) {
  2.     return searchRec(root, data);
  3. }
  4. private Node searchRec(Node node, int data) {
  5.     if (node == null || node.data == data) {
  6.         return node;
  7.     }
  8.    
  9.     if (data < node.data) {
  10.         return searchRec(node.left, data);
  11.     }
  12.    
  13.     return searchRec(node.right, data);
  14. }
复制代码
3.1.5 树的常见问题

  1. public int height(Node node) {
  2.     if (node == null) return 0;
  3.     return Math.max(height(node.left), height(node.right)) + 1;
  4. }
复制代码
  1. public boolean isBalanced(Node node) {
  2.     if (node == null) return true;
  3.    
  4.     int leftHeight = height(node.left);
  5.     int rightHeight = height(node.right);
  6.    
  7.     return Math.abs(leftHeight - rightHeight) <= 1
  8.            && isBalanced(node.left)
  9.            && isBalanced(node.right);
  10. }
复制代码
  1. public boolean isBST(Node node) {
  2.     return isBSTUtil(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
  3. }
  4. private boolean isBSTUtil(Node node, int min, int max) {
  5.     if (node == null) return true;
  6.    
  7.     if (node.data < min || node.data > max) return false;
  8.    
  9.     return isBSTUtil(node.left, min, node.data - 1)
  10.            && isBSTUtil(node.right, node.data + 1, max);
  11. }
复制代码
  1. public Node findLCA(Node root, int n1, int n2) {
  2.     if (root == null) return null;
  3.    
  4.     if (root.data == n1 || root.data == n2) {
  5.         return root;
  6.     }
  7.    
  8.     Node left = findLCA(root.left, n1, n2);
  9.     Node right = findLCA(root.right, n1, n2);
  10.    
  11.     if (left != null && right != null) {
  12.         return root;
  13.     }
  14.    
  15.     return left != null ? left : right;
  16. }
复制代码
3.1.6 树的应用场景

3.2 图(Graph)

3.2.1 基本概念

3.2.2 图的表示方法

3.2.3 图的遍历算法

3.2.4 图的最短路径算法

3.2.5 图的其他重要算法

3.2.6 图的应用场景

3.2.7 图的优缺点

3.3 堆(Heap)

3.3.1 基本概念

3.3.2 最大堆实现

  1. public class MaxHeap<T extends Comparable<T>> {
  2.     private ArrayList<T> heap;
  3.    
  4.     public MaxHeap() {
  5.         heap = new ArrayList<>();
  6.     }
  7.    
  8.     private int parent(int i) {
  9.         return (i - 1) / 2;
  10.     }
  11.    
  12.     private int leftChild(int i) {
  13.         return 2 * i + 1;
  14.     }
  15.    
  16.     private int rightChild(int i) {
  17.         return 2 * i + 2;
  18.     }
  19.    
  20.     private void swap(int i, int j) {
  21.         T temp = heap.get(i);
  22.         heap.set(i, heap.get(j));
  23.         heap.set(j, temp);
  24.     }
  25.    
  26.     // 向上调整(上浮)
  27.     private void heapifyUp(int i) {
  28.         while (i > 0 && heap.get(parent(i)).compareTo(heap.get(i)) < 0) {
  29.             swap(parent(i), i);
  30.             i = parent(i);
  31.         }
  32.     }
  33.    
  34.     // 向下调整(下沉)
  35.     private void heapifyDown(int i) {
  36.         int maxIndex = i;
  37.         int left = leftChild(i);
  38.         int right = rightChild(i);
  39.         
  40.         if (left < heap.size() && heap.get(left).compareTo(heap.get(maxIndex)) > 0) {
  41.             maxIndex = left;
  42.         }
  43.         
  44.         if (right < heap.size() && heap.get(right).compareTo(heap.get(maxIndex)) > 0) {
  45.             maxIndex = right;
  46.         }
  47.         
  48.         if (i != maxIndex) {
  49.             swap(i, maxIndex);
  50.             heapifyDown(maxIndex);
  51.         }
  52.     }
  53.    
  54.     // 插入元素
  55.     public void insert(T value) {
  56.         heap.add(value);
  57.         heapifyUp(heap.size() - 1);
  58.     }
  59.    
  60.     // 删除最大元素
  61.     public T extractMax() {
  62.         if (heap.isEmpty()) {
  63.             throw new IllegalStateException("堆为空");
  64.         }
  65.         
  66.         T max = heap.get(0);
  67.         heap.set(0, heap.get(heap.size() - 1));
  68.         heap.remove(heap.size() - 1);
  69.         
  70.         if (!heap.isEmpty()) {
  71.             heapifyDown(0);
  72.         }
  73.         
  74.         return max;
  75.     }
  76.    
  77.     // 获取最大元素但不删除
  78.     public T getMax() {
  79.         if (heap.isEmpty()) {
  80.             throw new IllegalStateException("堆为空");
  81.         }
  82.         return heap.get(0);
  83.     }
  84.    
  85.     // 获取堆的大小
  86.     public int size() {
  87.         return heap.size();
  88.     }
  89.    
  90.     // 检查堆是否为空
  91.     public boolean isEmpty() {
  92.         return heap.isEmpty();
  93.     }
  94.    
  95.     // 将数组转换为堆
  96.     public static <T extends Comparable<T>> MaxHeap<T> heapify(T[] array) {
  97.         MaxHeap<T> heap = new MaxHeap<>();
  98.         for (T element : array) {
  99.             heap.insert(element);
  100.         }
  101.         return heap;
  102.     }
  103.    
  104.     // 更高效的堆化方法
  105.     public static <T extends Comparable<T>> MaxHeap<T> buildHeap(T[] array) {
  106.         MaxHeap<T> heap = new MaxHeap<>();
  107.         heap.heap = new ArrayList<>(Arrays.asList(array));
  108.         
  109.         // 从最后一个非叶子节点开始向下调整
  110.         for (int i = heap.heap.size() / 2 - 1; i >= 0; i--) {
  111.             heap.heapifyDown(i);
  112.         }
  113.         
  114.         return heap;
  115.     }
  116. }
复制代码
3.3.3 最小堆实现

  1. public class MinHeap<T extends Comparable<T>> {
  2.     private ArrayList<T> heap;
  3.    
  4.     public MinHeap() {
  5.         heap = new ArrayList<>();
  6.     }
  7.    
  8.     private int parent(int i) {
  9.         return (i - 1) / 2;
  10.     }
  11.    
  12.     private int leftChild(int i) {
  13.         return 2 * i + 1;
  14.     }
  15.    
  16.     private int rightChild(int i) {
  17.         return 2 * i + 2;
  18.     }
  19.    
  20.     private void swap(int i, int j) {
  21.         T temp = heap.get(i);
  22.         heap.set(i, heap.get(j));
  23.         heap.set(j, temp);
  24.     }
  25.    
  26.     // 向上调整(上浮)
  27.     private void heapifyUp(int i) {
  28.         while (i > 0 && heap.get(parent(i)).compareTo(heap.get(i)) > 0) {
  29.             swap(parent(i), i);
  30.             i = parent(i);
  31.         }
  32.     }
  33.    
  34.     // 向下调整(下沉)
  35.     private void heapifyDown(int i) {
  36.         int minIndex = i;
  37.         int left = leftChild(i);
  38.         int right = rightChild(i);
  39.         
  40.         if (left < heap.size() && heap.get(left).compareTo(heap.get(minIndex)) < 0) {
  41.             minIndex = left;
  42.         }
  43.         
  44.         if (right < heap.size() && heap.get(right).compareTo(heap.get(minIndex)) < 0) {
  45.             minIndex = right;
  46.         }
  47.         
  48.         if (i != minIndex) {
  49.             swap(i, minIndex);
  50.             heapifyDown(minIndex);
  51.         }
  52.     }
  53.    
  54.     // 插入元素
  55.     public void insert(T value) {
  56.         heap.add(value);
  57.         heapifyUp(heap.size() - 1);
  58.     }
  59.    
  60.     // 删除最小元素
  61.     public T extractMin() {
  62.         if (heap.isEmpty()) {
  63.             throw new IllegalStateException("堆为空");
  64.         }
  65.         
  66.         T min = heap.get(0);
  67.         heap.set(0, heap.get(heap.size() - 1));
  68.         heap.remove(heap.size() - 1);
  69.         
  70.         if (!heap.isEmpty()) {
  71.             heapifyDown(0);
  72.         }
  73.         
  74.         return min;
  75.     }
  76.    
  77.     // 获取最小元素但不删除
  78.     public T getMin() {
  79.         if (heap.isEmpty()) {
  80.             throw new IllegalStateException("堆为空");
  81.         }
  82.         return heap.get(0);
  83.     }
  84.    
  85.     // 获取堆的大小
  86.     public int size() {
  87.         return heap.size();
  88.     }
  89.    
  90.     // 检查堆是否为空
  91.     public boolean isEmpty() {
  92.         return heap.isEmpty();
  93.     }
  94.    
  95.     // 将数组转换为堆
  96.     public static <T extends Comparable<T>> MinHeap<T> heapify(T[] array) {
  97.         MinHeap<T> heap = new MinHeap<>();
  98.         for (T element : array) {
  99.             heap.insert(element);
  100.         }
  101.         return heap;
  102.     }
  103.    
  104.     // 更高效的堆化方法
  105.     public static <T extends Comparable<T>> MinHeap<T> buildHeap(T[] array) {
  106.         MinHeap<T> heap = new MinHeap<>();
  107.         heap.heap = new ArrayList<>(Arrays.asList(array));
  108.         
  109.         // 从最后一个非叶子节点开始向下调整
  110.         for (int i = heap.heap.size() / 2 - 1; i >= 0; i--) {
  111.             heap.heapifyDown(i);
  112.         }
  113.         
  114.         return heap;
  115.     }
  116. }
复制代码
3.3.4 堆的应用场景

3.3.5 堆的优缺点

3.3.6 堆与其他数据结构的比较

3.3.7 堆的变种

3.4 散列表(Hash Table)

3.4.1 基本概念

3.4.2 冲突处理策略

3.4.3 实现示例

  1. public class HashTable<K, V> {
  2.     private class Entry<K, V> {
  3.         K key;
  4.         V value;
  5.         Entry<K, V> next;
  6.         
  7.         Entry(K key, V value) {
  8.             this.key = key;
  9.             this.value = value;
  10.             this.next = null;
  11.         }
  12.     }
  13.    
  14.     private Entry<K, V>[] table;
  15.     private int size;
  16.     private static final int DEFAULT_CAPACITY = 16;
  17.     private static final float LOAD_FACTOR = 0.75f;
  18.    
  19.     @SuppressWarnings("unchecked")
  20.     public HashTable() {
  21.         table = new Entry[DEFAULT_CAPACITY];
  22.         size = 0;
  23.     }
  24.    
  25.     private int hash(K key) {
  26.         return Math.abs(key.hashCode() % table.length);
  27.     }
  28.    
  29.     public void put(K key, V value) {
  30.         int index = hash(key);
  31.         
  32.         if (table[index] == null) {
  33.             table[index] = new Entry<>(key, value);
  34.             size++;
  35.         } else {
  36.             Entry<K, V> entry = table[index];
  37.             while (entry != null) {
  38.                 if (entry.key.equals(key)) {
  39.                     entry.value = value;
  40.                     return;
  41.                 }
  42.                 entry = entry.next;
  43.             }
  44.             Entry<K, V> newEntry = new Entry<>(key, value);
  45.             newEntry.next = table[index];
  46.             table[index] = newEntry;
  47.             size++;
  48.         }
  49.         
  50.         if (size >= table.length * LOAD_FACTOR) {
  51.             resize();
  52.         }
  53.     }
  54.    
  55.     public V get(K key) {
  56.         int index = hash(key);
  57.         Entry<K, V> entry = table[index];
  58.         
  59.         while (entry != null) {
  60.             if (entry.key.equals(key)) {
  61.                 return entry.value;
  62.             }
  63.             entry = entry.next;
  64.         }
  65.         
  66.         return null;
  67.     }
  68.    
  69.     public void remove(K key) {
  70.         int index = hash(key);
  71.         Entry<K, V> entry = table[index];
  72.         Entry<K, V> prev = null;
  73.         
  74.         while (entry != null) {
  75.             if (entry.key.equals(key)) {
  76.                 if (prev == null) {
  77.                     table[index] = entry.next;
  78.                 } else {
  79.                     prev.next = entry.next;
  80.                 }
  81.                 size--;
  82.                 return;
  83.             }
  84.             prev = entry;
  85.             entry = entry.next;
  86.         }
  87.     }
  88.    
  89.     @SuppressWarnings("unchecked")
  90.     private void resize() {
  91.         Entry<K, V>[] oldTable = table;
  92.         table = new Entry[table.length * 2];
  93.         size = 0;
  94.         
  95.         for (Entry<K, V> entry : oldTable) {
  96.             while (entry != null) {
  97.                 put(entry.key, entry.value);
  98.                 entry = entry.next;
  99.             }
  100.         }
  101.     }
  102. }
复制代码
3.4.4 开放寻址法实现示例

  1. public class OpenAddressingHashTable<K, V> {
  2.     private static final int DEFAULT_CAPACITY = 16;
  3.     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  4.     private static final Object DELETED = new Object();
  5.    
  6.     private K[] keys;
  7.     private V[] values;
  8.     private int size;
  9.     private float loadFactor;
  10.    
  11.     @SuppressWarnings("unchecked")
  12.     public OpenAddressingHashTable() {
  13.         keys = (K[]) new Object[DEFAULT_CAPACITY];
  14.         values = (V[]) new Object[DEFAULT_CAPACITY];
  15.         size = 0;
  16.         loadFactor = DEFAULT_LOAD_FACTOR;
  17.     }
  18.    
  19.     @SuppressWarnings("unchecked")
  20.     public OpenAddressingHashTable(int initialCapacity, float loadFactor) {
  21.         keys = (K[]) new Object[initialCapacity];
  22.         values = (V[]) new Object[initialCapacity];
  23.         size = 0;
  24.         this.loadFactor = loadFactor;
  25.     }
  26.    
  27.     // 哈希函数
  28.     private int hash(K key) {
  29.         if (key == null) return 0;
  30.         int h = key.hashCode();
  31.         return (h & 0x7FFFFFFF) % keys.length;
  32.     }
  33.    
  34.     // 线性探测
  35.     private int probe(int index, int i) {
  36.         return (index + i) % keys.length;
  37.     }
  38.    
  39.     // 插入或更新键值对
  40.     public void put(K key, V value) {
  41.         if (key == null) {
  42.             throw new IllegalArgumentException("键不能为null");
  43.         }
  44.         
  45.         // 检查是否需要扩容
  46.         if (size >= keys.length * loadFactor) {
  47.             resize();
  48.         }
  49.         
  50.         int index = hash(key);
  51.         int i = 0;
  52.         
  53.         // 线性探测查找空闲位置或已存在的键
  54.         while (i < keys.length) {
  55.             int currentIndex = probe(index, i);
  56.             
  57.             // 如果找到空闲位置或已删除的位置
  58.             if (keys[currentIndex] == null || keys[currentIndex] == DELETED) {
  59.                 keys[currentIndex] = key;
  60.                 values[currentIndex] = value;
  61.                 size++;
  62.                 return;
  63.             }
  64.             
  65.             // 如果找到已存在的键,更新值
  66.             if (keys[currentIndex].equals(key)) {
  67.                 values[currentIndex] = value;
  68.                 return;
  69.             }
  70.             
  71.             i++;
  72.         }
  73.         
  74.         // 如果没有找到空闲位置,扩容
  75.         resize();
  76.         put(key, value);
  77.     }
  78.    
  79.     // 获取键对应的值
  80.     public V get(K key) {
  81.         if (key == null) {
  82.             throw new IllegalArgumentException("键不能为null");
  83.         }
  84.         
  85.         int index = hash(key);
  86.         int i = 0;
  87.         
  88.         // 线性探测查找键
  89.         while (i < keys.length) {
  90.             int currentIndex = probe(index, i);
  91.             
  92.             // 如果找到空位置,说明键不存在
  93.             if (keys[currentIndex] == null) {
  94.                 return null;
  95.             }
  96.             
  97.             // 如果找到键,返回对应的值
  98.             if (keys[currentIndex] != DELETED && keys[currentIndex].equals(key)) {
  99.                 return values[currentIndex];
  100.             }
  101.             
  102.             i++;
  103.         }
  104.         
  105.         return null;
  106.     }
  107.    
  108.     // 删除键值对
  109.     public V remove(K key) {
  110.         if (key == null) {
  111.             throw new IllegalArgumentException("键不能为null");
  112.         }
  113.         
  114.         int index = hash(key);
  115.         int i = 0;
  116.         
  117.         // 线性探测查找键
  118.         while (i < keys.length) {
  119.             int currentIndex = probe(index, i);
  120.             
  121.             // 如果找到空位置,说明键不存在
  122.             if (keys[currentIndex] == null) {
  123.                 return null;
  124.             }
  125.             
  126.             // 如果找到键,标记为已删除
  127.             if (keys[currentIndex] != DELETED && keys[currentIndex].equals(key)) {
  128.                 V oldValue = values[currentIndex];
  129.                 keys[currentIndex] = (K) DELETED;
  130.                 values[currentIndex] = null;
  131.                 size--;
  132.                 return oldValue;
  133.             }
  134.             
  135.             i++;
  136.         }
  137.         
  138.         return null;
  139.     }
  140.    
  141.     // 检查键是否存在
  142.     public boolean containsKey(K key) {
  143.         return get(key) != null;
  144.     }
  145.    
  146.     // 获取散列表的大小
  147.     public int size() {
  148.         return size;
  149.     }
  150.    
  151.     // 检查散列表是否为空
  152.     public boolean isEmpty() {
  153.         return size == 0;
  154.     }
  155.    
  156.     // 清空散列表
  157.     @SuppressWarnings("unchecked")
  158.     public void clear() {
  159.         keys = (K[]) new Object[keys.length];
  160.         values = (V[]) new Object[values.length];
  161.         size = 0;
  162.     }
  163.    
  164.     // 扩容
  165.     @SuppressWarnings("unchecked")
  166.     private void resize() {
  167.         K[] oldKeys = keys;
  168.         V[] oldValues = values;
  169.         keys = (K[]) new Object[oldKeys.length * 2];
  170.         values = (V[]) new Object[oldValues.length * 2];
  171.         size = 0;
  172.         
  173.         // 重新插入所有元素
  174.         for (int i = 0; i < oldKeys.length; i++) {
  175.             if (oldKeys[i] != null && oldKeys[i] != DELETED) {
  176.                 put(oldKeys[i], oldValues[i]);
  177.             }
  178.         }
  179.     }
  180. }
复制代码
3.4.5 散列表的应用场景

3.4.6 散列表的优缺点

3.4.7 散列表与其他数据结构的比较

3.4.8 散列表的变种

4. 算法复杂度分析

4.1 时间复杂度

4.1.1 通俗明确

4.1.2 常见复杂度

4.1.3 分析方法

4.1.4 常见算法的时间复杂度

4.2 空间复杂度

4.2.1 通俗明确

4.2.2 影响因素

4.2.3 常见空间复杂度

4.2.4 常见算法的空间复杂度

4.3 实际应用中的思量因素

4.3.1 时间与空间的权衡

4.3.2 实际性能与理论复杂度

4.3.3 优化策略

4.3.4 实际案例分析

4.4 复杂度分析的进阶主题

4.4.1 平摊分析

4.4.2 随机化算法分析

4.4.3 在线算法分析

4.4.4 参数化复杂度分析

4.4.5 量子算法复杂度

5. 数据结构应用

5.1 数据库体系

5.1.1 索引结构

5.1.2 查询优化

5.1.3 事务处理

5.2 操作体系

5.2.1 内存管理

5.2.2 进程管理

5.2.3 文件体系

5.3 网络体系

5.3.1 路由算法

5.3.2 拥塞控制

5.3.3 负载平衡

5.4 编译体系

5.4.1 符号表

5.4.2 语法分析

5.4.3 代码优化

5.5 人工智能和机器学习

5.5.1 特征工程

5.5.2 模型存储

5.5.3 推理优化

5.6 游戏开发

5.6.1 游戏状态管理

5.6.2 物理模仿

5.6.3 寻路算法

5.7 安全体系

5.7.1 加密算法

5.7.2 访问控制

5.7.3 安全存储

6. 数据结构与算法计划

6.1 计划原则

6.2 计划模式

6.3 优化本领

6.4 算法策略

6.5 代码实现

6.6 测试与验证

6.7 实际应用案例

7. 数据结构实战案例

7.1 电商体系

7.1.1 商品管理


7.1.2 库存管理


7.1.3 付出体系


7.2 交际网络

7.2.1 关系管理


7.2.2 内容管理


7.2.3 及时通信


7.3 搜索引擎

7.3.1 索引构建


7.3.2 查询处理


7.3.3 爬虫体系


7.4 数据库体系

7.4.1 索引结构


7.4.2 查询优化


7.4.3 事务处理


7.5 操作体系

7.5.1 内存管理


7.5.2 进程管理


7.5.3 文件体系


7.6 网络体系

7.6.1 路由算法


7.6.2 拥塞控制


7.6.3 负载平衡


7.7 编译器体系

7.7.1 符号表


7.7.2 语法分析


7.7.3 代码优化


7.8 人工智能与机器学习

7.8.1 特征工程


7.8.2 模型存储


7.8.3 推理优化


7.9 游戏开发

7.9.1 游戏状态管理


7.9.2 物理模仿


7.9.3 寻路算法


7.10 安全体系

7.10.1 加密算法


7.10.2 访问控制


7.10.3 安全存储


7.11 金融体系

7.11.1 交易处理


7.11.2 市场数据


7.11.3 投资组合


7.12 物联网体系

7.12.1 传感器数据


7.12.2 设备管理


7.12.3 边缘计算


7.13 区块链体系

7.13.1 数据结构


7.13.2 共识算法


7.13.3 智能合约


7.14 大数据处理

7.14.1 数据存储


7.14.2 数据处理


7.14.3 数据分析


7.15 云计算体系

7.15.1 资源管理


7.15.2 服务编排


7.15.3 云原生应用


7.16 移动应用开发

7.16.1 UI组件


7.16.2 数据存储


7.16.3 网络通信


7.17 嵌入式体系

7.17.1 及时体系


7.17.2 内存管理


7.17.3 外设控制


8. 数据结构与性能优化

8.1 内存优化

8.1.1 内存布局


8.1.2 缓存优化


8.1.3 垃圾接纳优化


8.2 算法优化

8.2.1 时间复杂度优化


8.2.2 空间复杂度优化


8.2.3 算法实现优化


8.3 数据结构选择

8.3.1 基本操作分析


8.3.2 场景特定选择


8.3.3 复合数据结构


8.4 并发优化

8.4.1 线程安全


8.4.2 并发数据结构


8.4.3 并行计算


8.5 I/O优化

8.5.1 文件I/O优化


8.5.2 网络I/O优化


8.5.3 数据库I/O优化


8.6 体系级优化

8.6.1 操作体系优化


8.6.2 假造机优化


8.6.3 分布式体系优化


8.7 性能测量与分析

8.7.1 性能指标


8.7.2 性能分析工具


8.7.3 性能测试方法


8.8 实际案例分析

8.8.1 数据库查询优化


8.8.2 Web应用优化


8.8.3 大数据处理优化


9. 数据结构与并发编程

9.1 并发数据结构

9.1.1 线程安全集合


9.1.2 无锁数据结构


9.2 并发控制

9.2.1 同步机制


9.2.2 并发模式


9.3 线程安全计划

9.3.1 不可变对象


9.3.2 线程当地存储


9.3.3 线程封闭


9.4 并发编程最佳实践

9.4.1 计划原则


9.4.2 性能优化


9.4.3 调试与测试


10. 数据结构与内存管理

10.1 内存分配

10.1.1 静态分配


10.1.2 动态分配


10.2 内存接纳

10.2.1 手动接纳


10.2.2 自动接纳


10.3 内存优化

10.3.1 内存布局


10.3.2 缓存优化


10.3.3 内存池优化


10.4 内存管理策略

10.4.1 内存分配策略


10.4.2 内存接纳策略


10.4.3 内存管理最佳实践


10.5 高级内存管理技能

10.5.1 假造内存


10.5.2 内存映射文件


10.5.3 共享内存


10.5.4 非统一内存访问(NUMA)


11. 数据结构与数据库

11.1 索引结构

11.1.1 B+树索引


11.1.2 哈希索引


11.1.3 位图索引


11.1.4 全文索引


11.1.5 LSM树


11.1.6 R树


11.2 查询优化

11.2.1 实验筹划


11.2.2 性能调优


11.2.3 并行查询


11.2.4 查询优化器


11.3 事务处理

11.3.1 ACID特性


11.3.2 并发控制


11.3.3 规复机制


11.3.4 分布式事务


11.4 数据库计划

11.4.1 数据模型


11.4.2 数据库范式


11.4.3 反范式化


11.4.4 分区策略


12. 数据结构与网络编程

12.1 网络协议

12.1.1 协议实现


12.1.2 性能优化


12.2 网络应用

12.2.1 服务器实现


12.2.2 客户端实现


12.3 网络数据结构

12.3.1 协议数据结构


12.3.2 网络缓冲区


12.4 网络算法

12.4.1 路由算法


12.4.2 拥塞控制


12.4.3 负载平衡算法


12.5 网络安全

12.5.1 加密算法


12.5.2 安全协议


12.5.3 安全数据结构


13. 数据结构与分布式体系

13.1 分布式存储

13.1.1 数据分片


13.1.2 数据同步


13.2 分布式计算

13.2.1 任务调度


13.2.2 数据流处理


13.3 分布式和谐

13.3.1 一致性算法


13.3.2 分布式锁


13.4 分布式数据结构

13.4.1 分布式哈希表


13.4.2 分布式计数器


13.4.3 分布式集合


13.5 分布式算法

13.5.1 共识算法


13.5.2 分布式排序


13.5.3 分布式图算法


14. 数据结构与大数据处理

14.1 数据存储

14.1.1 列式存储


14.1.2 分布式存储


14.2 数据处理

14.2.1 批处理


14.2.2 流处理


14.3 数据索引与查询

14.3.1 索引结构


14.3.2 查询优化


14.4 数据挖掘与机器学习

14.4.1 特征工程


14.4.2 模型存储


14.5 数据可视化

14.5.1 可视化数据结构


14.5.2 交互式可视化


15. 数据结构与人工智能

15.1 机器学习

15.1.1 特征工程


15.1.2 模型训练


15.2 深度学习

15.2.1 神经网络


15.2.2 优化算法


15.3 强化学习

15.3.1 状态表示


15.3.2 动作选择


15.4 自然语言处理

15.4.1 文本表示


15.4.2 语言模型


15.5 计算机视觉

15.5.1 图像表示


15.5.2 卷积神经网络



免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。




欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4