Linux文件系统在使用计算机的过程中，文件是经常被提到的概念，例如可执行文件、文本文件等,这里说的文件是一个抽象的概念,它是存放一切数据化信息的仓库。用户为了保存数据或信息，首先要创建-一个文件，然后把数据或信息写人该文件。最终这些数据被保存到文件的载体上，通常情况下是磁盘上，只要给出存放文件的路径和文件名，文件系统就可以在磁盘上找到该文件的物理位置，并把它调人内存供用户使用。在这个过程...

前言在上篇博客中我们主要讲了AVL树的四种旋转方法以及如何构建AVL树,这篇博客我们主要来看一下AVL树的删除与销毁操作.正文构建AVL树的过程是一个边插入边调整的过程,而删除某个节点的操作那么也是这样的(完成节点的删除后我们需要对AVL树进行判断,如果不再平衡我们需要进行调整).这里将其分为三种情况:删除叶子节点,删除有一颗子树的节点,删除左右子树都有的节点.一个思路:左子树上节点的删...

二叉查找树在正式介绍AVL树之前,我们先来了解一下二叉查找树.二叉查找树（Binary Search Tree）（又称二叉搜索树，二叉排序树）,它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。那么二叉查找树的引入有什么用呢...

最短路径最短路径是一种思想不同于最小生成树的另一种图的应用，对网图来说，最短路径就是指两个顶点之间经过的边上权值和最小的路径，我们称第一个顶点为源点，最后一个顶点为终点（非网图边上没有权值，所说的最短路径就是两个顶点之间经过的边数最少的路径）。此篇博客围绕Dijkstra算法展开，也就是从某个源点到图中其余各顶点的最短路径问题。Dijkstra算法Dijkstra算法通常被用来解决单源最短...

最小生成树一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有n - 1条边，我们把构造连通图的最小代价生成树称为最小生成树。如上左图所示，这是一个无向带权图，而右图是它的生成树之一。显然，生成树不唯一，可能有多颗。此图才是上左图的最小生成树。构造最小生成树有多种算法，经典的有两种，Prim算法和Kruskal算法，此篇博客将围绕Kruskal算法展开。Kruskal算...

此篇博客主要就图的储存结构——邻接表展开。邻接表图的一种最便于理解的储存结构就是邻接矩阵了（可以简单的把它视为一个二维数组），但是邻接矩阵在处理边数较少，但顶点较多的情况时会浪费不少的储存空间。因此便有了邻接表这种储存结构。图中顶点用一个一维数组存储， 当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的...

三次握手在握手正式开始之前，服务器必须准备好接收外来的连接。这通常通过调用socket, bind, listen这3个函数来完成，称之为被动打开。第一次握手：客户通过调用connect发起主动打开。这导致客户TCP发送一个 SYN（同步）分节，它告诉服务器客户将在（待建立的）连接中发送的数据的初始序列号（ISN）。此时客户处于SYN_SENT状态。第二次握手：服务器必须确认（ACK）客户...

关联容器关联容器支持高效的关键字查找和访问，两个主要的关联容器类型就是map和set，此篇博客主要围绕map展开。标准库提供8个关联容器，这些容器间的不同体现在三个维度中：（1）或者是一个map，或者是一个set（2）或者要求不重复的关键字，或者允许重复关键字（3）按顺序保存元素，或无序保存允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以unor...

系统调用与内核函数内核函数与普通函数形式上没有什么区别，只不过前者在内核实现，因此要满足一些内核编程的要求。系统调用是用户进程进入内核的接口层，它本身并非内核函数，但它是由内核函数实现的，进入内核后，不同的系统调用会找到相应的内核函数，这些内核函数被称为系统调用的“服务例程”。比如系统调用getpid()实际调用的是服务例程sys_getpid()，也可以说，系统调用getpid()是服务例...

引言在计算机中不管是CPU，内存，或者是一些外围设备，它们之所以能有条不紊的协同工作，是因为有一层软件不遗余力的管理着它们。这层软件就是操作系统。操作系统在整个计算机系统中的位置从这张图中可以看出用户界面是操作系统的外在表象，内核才是操作系统的内在核心，它真正完成用户程序所要求的操作。那么就可以说一方面操作系统是上层软件与硬件打交道的窗口和桥梁，另一方面操作系统是其他所有用户程序运行的基础...