1. 最短路 1.1 单源最短路Dijkstra算法 求某个点到所有其他点的最短路程 类似prim算法 从源点出发 每次贪心地扩大一个节点 维护一个表即可 第一列列为除了选中点的其余目标点, 第一行表轮次 如 第一次 第二次 第一次初始化 一行一行看,每次仅允许从已有 点团/集 到其余所有点走一步的距离 1->2 1->3 1->4 将1到其余点路程中最短的那个保留下来,例如 1到2比1到3 1到4更近,那么把2纳入点团/集 得到{1,2},然后再贪心地找1, 2 这个集使得1到其他点更短的路径 .保留最短的那条路对应的点,纳入点集 ,继续 1.2 多源最短路Floyd算法 求任意两点最短路程…
数据结构复习框架（重要考点章节）
数据结构与算法QA
算法笔记 学习
0. 基础与复杂度（✅ 必考） 数据结构三要素：逻辑结构 / 存储结构 / 操作（算法） 时间复杂度： 符号：O（上界）、Ω（下界）、Θ（紧确界） 场景：最好/最坏/平均（如快排、查找） 计算方法：求和法、递推法（展开/代入）、主定理（分治类） 空间复杂度： 关注辅助空间（不包括输入） 递归算法：栈空间 = 递归深度 算法特性：正确性、可读性、健壮性、效率（时间+空间） ⚠️ 常考题型：三重循环复杂度（如 for i=1..n; for j=1..i; for k=1..j）、递归式求解（如 T(n)=2T(n/2)+n） 1. 线性表 1.1 顺序表 地址计算：Loc(a[i]) = Loc…
Q：串和线性表有何区别？ 串（String）和线性表（Linear List）都是数据结构中的基本概念，它们之间既有紧密联系，又有显著区别。核心区别在于：串是线性表的一个特例，但其元素类型和操作具有特殊性。 以下是详细对比： 特征串 (String)线性表 (Linear List)本质线性表的特例更广泛、更基础的概念元素类型严格受限：必须是字符 (char)任意类型：整数、浮点数、结构体、对象、甚至另一个线性表等数据含义元素具有整体语义 (如单词、句子、代码)元素通常是独立的个体，彼此间语义关联不强制核心操作文本处理操作：连接、子串查找/提取、模式匹配、替换、比较通用数据管理操作：插入、删除…
1 如何使用本书? x 我的笔记本 getline 末尾(string)无'/0' 所以printf会报错 puts会自动换行 cin.getline(char,num)会补添'/0' 与gets -s 效果一样 puts 无结束符会报错 printf也会 cin.getline好,别用puts 别用! memcpy(backup,str,sizeof str)
算法设计与分析笔记
1、概述 2、递归 3、分治法-基于递归思想 二路归并 T(n)=O(nlogn) 自底向上 自顶向下 描述一个算法 解决问题的步骤 例： 3.3.1查找最大和次大元素T=O(n) 分治法求最大和次大元素的思路可以简要概括为以下几个步骤： 分解：将当前问题的数据集分成两个大小大致相等的子集. 解决：递归地在两个子集中分别找到最大和次大元素. 合并：比较两个子集各自的最大元素,确定整个数据集的最大元素.次大元素可能是以下几种情况之一：两个子集中较小的最大元素.两个子集中的次大元素(如果最大元素来自同一个子集).对这些候选元素进行比较,确定整个数据集的次大元素.4、直接解决：如果数据集足够小,直接…