c++中的I/O流
在 C++ 中，输入输出（I/O）库提供了流（stream）的状态管理功能。每个流对象（如 cin, cout, ifstream, ofstream 等）都有一个与之相关的状态，标志着当前流的操作是否成功。流的状态主要通过流的条件标志（flags）来表示。这些标志通常用于检查流是否处于有效的状态，以便在进行输入输出操作时处理异常或错误。 流的条件状态（Flags）流的条件状态通过 ios 类中的几个成员标志进行管理，这些标志包括： **good()**：流是否处于正常状态，即没有发生任何错误。 **eof()**：流是否已经到达文件末尾。 **fail()**：流是否遇到输入/输出错误。 **bad()**：流是否发生严重错误，导致无法继续读取或写入。 这些状态标志可以通过流对象的方法访问，通常用于判断流的状态。 流的状态检查1. good() good() 返回 true 如果流没有遇到任何错误，输入输出操作可以继续进行。它相当于检查流的状态是否为 ios::goodbit。 123if (cin.good()) { cout...
c++中的四种命名的强制类型转换
在 C++ 中，有四种强制类型转换操作符，分别是： static_cast dynamic_cast const_cast reinterpret_cast 这四种类型转换都属于强制类型转换,值得一提的是其实这四种强制转换都是较为危险的，很容易出现错误，尽量少用 1. static_caststatic_cast 用于在类型之间进行转换时，进行编译时类型检查。 它适用于转换那些在语义上兼容的类型，例如基本数据类型、类之间的转换等。 任何具有明确定义的类型转换，只要不包含底层const，都可以使用static_cast 用法： 类之间的转换（如父类和子类的转换）。 基本数据类型之间的转换。 指针类型之间的转换，当有继承关系时，可以转换指向基类的指针和指向派生类的指针。 示例：12345678910111213141516171819202122232425#include <iostream>//类之间的转换class Base {public: virtual void show() { std::cout <<...
指向常量的指针与指针常量
好久没有更新博客了，与最近考试多有关，也与个人怠惰有关 今天的内容是指向常量的指针（pointer to const）（也就是常量指针）与指针常量（const pointer），这是昨天在阅读《c++ primer》中重新理解的内容，有了些许新的感悟，趁热打铁，发在博客上 在讲那两个之前，先说一下const与对常量的引用（reference to const）const修饰词使用const修饰词修饰的变量，即常量，是必须初始化的，且初始化后不能修改其值 初始化时除了用如下方法 1const int a=1; 同样可以用非常量但同类型的值进行赋值（拷贝） 123int a=1;const int b=a;a=b; const修饰的对象在编译时直接替换，类似define，即提前将所有出现其的位置替换成对应的数值，不申请额外空间 以下场景除外(都要等具体的值才能初始化) 12const int a =fun();const int &b=c; 同时const对象仅在文件内部有效，要实现在一个文件中定义，在多个文件中声明并使用，要用extern...
前缀表与KMP算法
KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的高效算法，它能够在文本串中查找模式串出现的位置。KMP算法的核心在于避免重复比较字符，从而提高匹配效率。 KMP算法的基本思路 预处理模式串：通过构建一个“部分匹配表”（或称为“失配表”），在模式串中记录每个位置的最长可匹配前缀长度。 匹配过程：利用部分匹配表，在匹配失败时，根据前缀信息跳过不必要的比较，从而加速匹配过程。 部分匹配表（LPS数组）LPS（Longest Prefix Suffix）数组用于存储模式串的每个前缀的最长相等前后缀的长度。具体构建方式如下： **LPS[i]**：表示模式串的前缀（pattern[0] 到...
leetcode心得
1.对于复杂条件的题，看能不能将条件简化，比如通过排序让题目简单，比如去掉多余空格，让后序算法简化操作 2.双指针对于局部的变化有奇效
平衡二叉树的调整(左旋与右旋)
平衡二叉树平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它在结构上保持一定的平衡，以确保在最坏情况下依然具有较好的查找、插入和删除性能。 平衡二叉树的定义平衡的具体定义可以根据不同类型的平衡树略有不同。一般来说，一个二叉树是平衡的，当其任意节点的左右子树高度差的绝对值不超过某个特定值（通常是1）时。 常见类型的平衡二叉树 AVL树： 每个节点的左右子树高度差（平衡因子）只允许为 -1、0 或...
单源最短路径问题与Dijkstra算法
单源最短路径问题（Single Source Shortest Path, SSSP）是图论中的一个经典问题。它的目标是在一个加权图中，找到给定的起点（源点）到图中所有其他节点的最短路径。问题定义： 图：图可以是有向图或无向图，通常包含若干个节点和边，每条边都有一个非负权重（即从一个节点到另一个节点的代价或距离）。 起点（源点）：单源最短路径问题会指定一个起始节点，称为源节点，问题要求从这个源节点出发，计算它到图中其他所有节点的最短路径。 最短路径：最短路径是指从源节点到目标节点经过的路径中，总边权重之和最小的路径。 具体目标：对于给定的源节点s，你需要找到从s到每个其他节点v的最短路径长度，并且路径上的权重和最小。 常见的算法： Dijkstra算法： 解决边权非负的单源最短路径问题，时间复杂度为$O((V + E) \log V)$，适合稀疏图。 Bellman-Ford算法： 可以处理负权边的情况，且能够检测负权环，时间复杂度为$O(V \times...
kahn算法实现拓扑排序
1. 拓扑排序（Topological Sorting）是什么？拓扑排序是一种用于 有向无环图（DAG, Directed Acyclic Graph） 的节点排序算法。它的目标是将图中的所有节点排成一个 线性序列，使得对于图中每一条从节点 u 到节点 v 的有向边 u -> v，在排序中节点 u 都排在节点 v 的前面。 简单来说，如果图中有一条边 u -> v，那么在拓扑排序中，节点 u 必须排在节点 v 的前面。这个排序是图中所有节点的线性排列，并且保证了这种有向依赖关系。 2. 拓扑序列是什么？拓扑序列是拓扑排序的结果，即节点的一个线性排列，满足上述的依赖关系。对于给定的有向无环图，可能存在多个不同的拓扑序列，只要它们满足图中所有边的依赖关系。 3....
最小生成树:Prim 算法和Kruskal 算法
在 C++ 中，实现最小生成树（MST）的常用算法有两种：Prim 算法和Kruskal 算法。这两种算法适用于加权无向图，用于寻找包含所有顶点的边的集合，使得边的总权重最小，且没有环路。 1. Prim 算法Prim 算法通过贪心策略来构建 MST，从任意起始顶点开始，每次选择权重最小的边扩展 MST。 实现步骤 初始化一个集合 MST，包含图中的任意一个顶点。 找到从集合 MST 到剩余顶点中权重最小的边，并将该边加入 MST。 重复步骤 2，直到所有顶点都包含在 MST 中。 C++ 实现示例（使用优先队列）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <iostream>#include <vector>#include <queue>#include...
邻接表，邻接矩阵和十字链表
1. 邻接表的实现邻接表使用一个数组或 vector 来存储每个顶点的边列表。每个顶点的边列表存储在一个链表或 vector 中。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <vector>using namespace std;class Graph { int V; // 顶点数量 vector<vector<int>> adj; // 邻接表public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); } void printGraph() { for...
