文章 44
浏览 11238
Linux 简单文件系统实现

Linux 简单文件系统实现

Linux 简单文件系统实现 前言 借鉴于Linux文件系统的实现 存储设备分区 文件系统的最终目的是把大量数据有组织的放入持久性的存储设备中,比如硬盘和磁盘。这些存储设备与内存不同。它们的存储能力具有持久性,不会因为断电而消失;存储量大,但读取速度慢。 观察常见存储设备。最开始的区域是MBR,用于Linux开机启动(参考Linux开机启动)。剩余的空间可能分成数个分区(partition)。每个分区有一个相关的分区表(Partition table),记录分区的相关信息。这个分区表是储存在分区之外的。分区表说明了对应分区的起始位置和分区的大小。 我们在Windows系统常常看到C分区、D分区等。Linux系统下也可以有多个分区,但都被挂载在同一个文件系统树上。 数据被存入到某个分区中。一个典型的Linux分区包含有下面各个部分: 分区的第一个部分是启动区(Boot block),它主要是为计算机开机服务的。Linux开机启动后,会首先载入MBR,随后MBR从某个硬盘的启动区加载程序。该程序负责进一步的操作系统的加载和启动。为了方便管理,即使某个分区中没有安装操作系统,Linux....

最短路径

最短路径

计算图的最短路径有几种经典的算法: 弗洛伊德(Floyd)算法 迪杰斯特拉(Dijkstra)算法 贝尔曼福德(Bellman-Ford)算法 SPFA 算法 弗洛伊德算法 弗罗伊德算法的思想来自于动态规划。 基本思路为: 我们知道若给定任意结点 A、B,若想使两点之间的距离减小只有引入第三个点。 首先引入 结点 1 ,是否能使任意两个结点之间距离缩短呢?若能则更新距离。接着引入 结点 2 ,是否能在结点 1 的基础上继续缩短距离呢?这样一直到 结点 N。 因为每次引入 结点 i+1 都是在 结点 i 的基础上,所以最终的结果就是任意两点间的最短距离。 算法模板: cin>>n>>m; //n为节点数,m为路径数 for(i=0;i<m;i++){ cin>>begin>>end>>len; route[begin][end]=len; //读入路径 } for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if....