算法

数据结构-图-遍历 原文链接 一、深度优先遍历 深度优先遍历(Depth First Search),也有称为深度优先搜索，简称为DFS。 1、DFS算法 深度优先搜索类似于树的先序遍历。如其名称中所含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深“地搜索一个图。它的基本思想如下： 首先访问图中某一起始顶点 v ，然后由 v 出发，访问与 v 邻接且未被访问的任一顶点 $w_1$ ,再访问与 $w_1$ 邻接且未被访问的任一顶点 ...

最小生成树 一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的 n-1 条边，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图 $G=(V,E)$ ，生成树不同，其中边的权值之和最小的那颗生成树（构造连通网的最小代价生成树），称为G的最小生成树(Minimum-Spanning-Tree,MST)。 ...

数据结构-图-存储结构 原文链接 由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，接下来我们介绍五种不同的存储结构。 ...

数据结构-图-概念 原文链接 知识框架 图的基本概念 在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 ...

Hello,树 一、树的基本概念 树是一种非线性数据结构，由节点 (Node) 和 边 (Edge) 组成，具有以下特性： 根节点：树的起始点，没有父节点。 父子关系：每个节点可以有多个子节点，但只能有一个父节点。 层次结构：节点的子节点形成子树 （Subtree）。 无环：树中不存在循环路径。 关键术语示例 **节点深度：**从根到该节点的层数（根节点深度为0）。 **节点高度：**从该节点到最远叶子节点的边数。 **叶子节点：**没有子节点的节点。 **兄弟节点：**共享同一父节点的节点。 1 2 3 4 5 A (根节点, 深度0, 高度2) / \ B C (兄弟节点) / \ D E (叶子节点) 二、树的分类与特性 1. 二叉树（Binary Tree) 每个节点 最多 有 2 个子节点（左子节点和右子节点）。 ...

1. 顺序查找 顺序查找（Sequ序查找）是一种简单直接的查找算法，适用于在无序数组中查找特定元素。以下是Java实现的步骤解析和代码示例： 实现步骤 方法定义：创建一个静态方法sequentialSearch，接收整型数组和目标值作为参数。 遍历数组：使用for循环逐个访问数组元素。 元素比较：检查当前元素是否等于目标值，若相等则立即返回当前索引。 处理未找到：遍历结束后仍未找到目标值，则返回-1。 Java代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class SequentialSearch { public static int sequentialSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 找到目标，返回索引 } } return -1; // 未找到，返回-1 } public static void main(String[] args) { int[] arr = {3, 5, 2, 7, 1}; System.out.println(sequentialSearch(arr, 5)); // 输出: 1 System.out.println(sequentialSearch(arr, 1)); // 输出: 4 System.out.println(sequentialSearch(arr, 9)); // 输出: -1 } } 关键点说明 时间复杂度：O(n)，最坏情况下需要检查所有元素。 适用场景：适用于小规模数据或未排序数组。 注意事项：若数组元素为对象类型，需使用equals()方法进行比较，而非==运算符。 此实现简洁高效，能够正确处理空数组及不存在目标值的情况。 ...

案例1： 1 2 3 4 5 public void test1(){ for(int i=0;i<100;i++){ System.out.print(i+" "); } } 无论输入参数的大小，循环次数都是固定的，所以时间复杂度为 O(1) 案例2： 1 2 3 4 5 public void test2(int n){ for(int i=0;i<n;i++){ System.out.print(i+" "); } } 循环次数与输入参数n的大小成正比，所以时间复杂度为 O(n) 案例3： 已知一个算法的时间复杂度递推公式为 T(n)=T(n-1)+1 , T(1)=1,求该算法时间复杂度 由公式可得 T(n)=T(n-2)+1+1=T(1)+…+1+1=n 所以该算法时间复杂度为 O(n) ...

一 、插入排序类 直接插入排序 示例代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** * 插入排序 * @param arr * i 6 7 9 2 3 * 1-> 6 7 9 2 3 * 2-> 6 7 9 2 3 * 3-> 6 7 2 9 3 * -> 6 2 7 9 3 * -> 2 6 7 9 3 * 4-> 2 6 7 3 9 * -> 2 6 3 7 9 * -> 2 3 6 7 9 */ public static void insertionSort(int[] arr){ //外层循环: 遍历未排序部分 (从第二个元素开始) for (int i = 1; i < arr.length; i++) { int temp = arr[i]; //当前需要插入的元素 int j = i - 1; //已排序部分的最后一个元素 //内层循环: 从已排序部分最后一个元素开始, 向前遍历, 寻找插入的位置 for (; j >= 0; j--) { if (arr[j] > temp) { arr[j + 1] = arr[j]; //将大于当前元素的元素向后移动一位 } else { break; } } arr[j + 1] = temp;//将当前元素插入到找到的位置 } } 关键说明 算法核心逻辑 外层循环 (for)遍历数组中未排序的元素(从第二个元素开始) 内层循环将当前元素temp与已排序部分的元素从后往前比较 如果发现更大的元素，则将其向后移动，直到找到插入位置 时间复杂度 最优情况(已经排序好的数组): O(n) 最差/平均情况(完全逆序)：O($n^2$) 适合小规模数据或基本有序的数据 关键特点 原地排序：不需要额外的内存空间 稳定排序：相同值的元素相对位置不变 逐步构建有序序列：每次处理一个元素，逐步扩大有序空间 希尔排序 代码示例： ...