Java数据结构和算法

### Java数据结构和算法知识点详解 #### 一、数组与简单排序 ##### 数组 **概念**: 数组是一种基本的数据结构，用于存储一系列相同类型的元素。数组中的元素可以通过索引进行访问。 **特点**: - **类型一致**: 数组中的所有元素必须具有相同的类型。 - **索引访问**: 元素可以通过索引进行访问，索引是从0开始的整数。 - **固定大小**: 数组的大小在创建时确定，不能更改。 **一维数组**: - **声明**: `type arrayName[];` - **创建**: 使用`new`关键字分配内存。例如: `int[] myArray = new int[10];` - **初始化**: 可以在声明时初始化数组，如: `int[] arr = {1, 2, 3};` **多维数组**: - 多维数组实际上是数组的数组。例如，二维数组可以表示为矩阵。 - **声明与创建**: 如 `int[][] matrix = new int[5][10];` - **初始化**: 可以逐行初始化，例如: `int[][] matrix = {{1, 2}, {3, 4}};` **数组边界检查**: - Java提供了自动的数组边界检查功能，防止访问不存在的数组元素。 - 如果尝试访问超出范围的元素，Java会抛出`ArrayIndexOutOfBoundsException`异常。 ##### 简单排序算法 **冒泡排序**: - **思想**: 通过不断比较相邻两个元素并交换位置，将最大(或最小)的元素“冒泡”到数组的末尾(或开头)。 - **实现**: ```java public void bubbleSort() { for (int out = nums.length - 1; out > 0; out--) { for (int in = 0; in < out; in++) { if (nums[in] > nums[in + 1]) { swap(in, in + 1); } } } } ``` - **时间复杂度**: O(n^2)，其中n是数组长度。 **选择排序**: - **思想**: 每次从未排序的部分找到最小(或最大)的元素放到已排序序列的末尾。 - **实现**: ```java public void selectSort() { for (int out = 0; out < nums.length - 1; out++) { int min = out; for (int in = out + 1; in < nums.length; in++) { if (nums[in] < nums[min]) { min = in; } } swap(out, min); } } ``` - **时间复杂度**: O(n^2)，其中n是数组长度。 **插入排序**: - **思想**: 假设数组的一部分已经排序，每次将一个未排序的元素插入到已排序部分的正确位置。 - **实现**: ```java public void insertionSort() { for (int out = 1; out < nums.length; out++) { int temp = nums[out]; int in = out; while (in > 0 && nums[in - 1] > temp) { nums[in] = nums[in - 1]; in--; } nums[in] = temp; } } ``` - **时间复杂度**: 最好情况下的时间复杂度为O(n)，平均和最坏情况为O(n^2)。 #### 二、栈与队列 **栈(Stack)**: - **概念**: 栈是一种只能在一端进行插入或删除操作的线性表。 - **操作**: push(入栈), pop(出栈) - **应用场景**: 表达式求值、函数调用等。 **队列(Queue)**: - **概念**: 队列是一种允许在一端进行插入操作而在另一端进行删除操作的线性表。 - **操作**: enqueue(入队), dequeue(出队) - **应用场景**: 消息传递、任务调度等。 #### 三、链表 **概念**: 链表是一种由节点组成的线性集合，每个节点包含数据和指向下一个节点的指针。 - **单链表**: 节点只有一个指向下一个节点的指针。 - **双链表**: 节点有两个指针，一个指向前一个节点，另一个指向后一个节点。 - **循环链表**: 尾节点指向头节点，形成一个闭环。 **操作**: - 插入 - 删除 - 查找 #### 四、递归 **概念**: 递归是一种算法或函数调用自身的编程技术。 - **递归的构成**: - **基本情况**(base case): 递归终止条件。 - **递归步骤**: 递归函数如何调用自身。 - **应用场景**: 文件系统遍历、树结构处理等。 #### 五、哈希表 **概念**: 哈希表是一种数据结构，通过哈希函数将键映射到特定位置来存储和检索数据。 - **特点**: - 快速查找 - 平均时间复杂度为O(1) **冲突解决**: - **开放寻址法**: 如线性探测再散列、二次探测再散列等。 - **链地址法**: 在每个哈希位置使用链表来存储多个元素。 #### 六、高级排序 - **快速排序** - **归并排序** - **堆排序** #### 七、二叉树 **概念**: 二叉树是一种树形数据结构，其中每个节点最多有两个子节点。 - **类型**: - 完全二叉树 - 满二叉树 - 二叉搜索树(BST) **操作**: - 插入 - 删除 - 查找 - 遍历(前序、中序、后序) #### 八、红黑树 **概念**: 红黑树是一种自平衡的二叉搜索树。 - **性质**: - 每个节点要么是红色，要么是黑色。 - 根节点是黑色。 - 所有叶子节点都是黑色(空节点)。 - 每个红色节点的两个子节点都是黑色。 - 任意节点到其每个叶子节点的所有路径上包含相同数量的黑色节点。 **应用场景**: 许多数据结构库使用红黑树作为基础实现。 #### 九、堆 **概念**: 堆是一种特殊的完全二叉树结构，可以实现优先队列。 - **类型**: - 最大堆: 每个父节点的值大于等于其子节点的值。 - 最小堆: 每个父节点的值小于等于其子节点的值。 **操作**: - 插入 - 删除最大/最小元素 - 堆调整 #### 十、带权图 **概念**: 图是由节点(顶点)和边组成的数据结构，其中边可以带有权重。 - **类型**: - 无向图 - 有向图 **应用算法**: - 最短路径算法(Dijkstra算法、Floyd算法) - 最小生成树(Kruskal算法、Prim算法) 以上介绍了Java中常见的数据结构和算法的基础知识，每种数据结构和算法都有其独特的应用场景和优势。掌握这些内容对于理解和设计高效的程序至关重要。