- 博客(17)
- 收藏
- 关注
RSS订阅原创 无向图的广/深度优先搜索
无向图的BFS和DFS无向图的遍历存在广度优先搜索(BFS)和深度优先搜索(DFS)两种方法；深度优先搜索概念：沿着深度遍历树的节点，尽可能深的搜索分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。算法...
2020-03-29 20:14:11
2154
原创 堆排序C++实现
堆排序C++实现堆的数据结构实际就是完全二叉树，即叶子节点只可能出现在最下面两层，且最后一层的叶子节点，从左往右进行排列；堆的简单性质由上面所说的堆的结构，可以推出一些简单的堆的性质，这些性质在实现的时候，会用到(将堆存放在数组中)：父节点的下标为i，左子节点的下标为2*i;父节点的下标为i，右子节点的下标为2*i+1;一个下标为i的节点，其父节点为[i/2];堆排序的实现步骤...
2020-03-14 16:59:52
472
原创 Redis跳跃表的实现
Redis跳跃表的实现在看redis代码的时候，看到了redis实现了一个跳跃表，看了一下结构，写了一个小demo，记录一下，代码链接；跳跃表结构跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。从图中可以看到， 跳跃表主要由以下部分构成：表头：负责维护跳跃表的节...
2020-03-08 21:38:29
337
原创 内核Generic Netlink通信
内核netlink通信select函数Netlink 是一种在内核与用户应用间进行双向数据传输的非常好的方式，用户态应用使用标准的 socket API 就可以使用 netlink 提供的强大功能，内核态需要使用专门的内核 API 来使用 netlink。Netlink 相对于系统调用，ioctl 以及 /proc文件系统而言具有以下优点：1，netlink使用简单，只需要在includ...
2019-11-12 00:20:39
1346
原创 网络限流令牌桶算法原理及实现
令牌桶算法原理及实现令牌桶算法的原理令牌桶算法的简单实现令牌桶算法的原理令牌桶算法听起来蛮牛逼，但是原理非常简单，简单说就是在一个桶中匀速放入令牌，如果桶中有令牌，就取走一个令牌，进行服务，若没有则拒绝服务。简单示意图如下所示：实际的令牌桶算法具体实现流程图如图所示：流程key是否存在。因为流程图是基于分布式缓存做的集群限流，需要根据不同key做统计，第一次访问初始化key。...
2019-10-27 15:38:26
1565
原创 boost::noncopyable的实现
boost::noncopyable最近在看muduo网络库，muduo是基于boost库做开发的。里面很多类是继承自noncopyable，顺手查看了noncopyable类的实现。noncopyable类的作用默认情况下，如果类没有声明拷贝构造函数和复制构造函数，编译器会自动的为类创建隐含的public拷贝构造机复制构造函数。但是noncopyable类的实现是将构造函数与析构函数声明...
2019-09-15 19:36:01
713
原创 Linux定时任务crontab详解
Linux定时任务crontab详解crontab的作用crontab的设置crontab的用法crontab的编辑列表crontab的配置crond进程crontab命令后的> /dev/null 2 > &1的含义crontab遇过的坑crontab的作用定时循环任务是由linux上的crond系统服务来控制的，这个系统服务实现是以守护进程的方式实现，守护进程的详解戳文...
2019-09-01 21:56:40
388
原创 C++基于对象编程与function,bind用法
C++基于对象编程与function,bind用法博主今天在看muduo多线程库开源代码的时候，看到了在muduo库中使用的基于对象编程，何为基于对象编程与面向对象编程有什么不同，看了下面例子，基本就可以了解。在基于对象编程方法实现中，主要用到的是C++中的function和bind，也同时总结下function和bind的用法。参考:C++ primer，https://www.bilib...
2019-07-28 20:35:03
516
原创 I/O多路复用(select,poll)函数及示例程序
I/O多路复用在网络编程中，不得不提的一个概念就是I/O多路复用机制，采用I/O多路复用机制，使得内核一旦发现进程指定的一个或多个I/O条件就绪，就通知进程进行处理，能够同时处理多个描述符。目前Linux上的I/O多路复用机制主要有三种select，poll，epoll，因为select与poll比较相似，因此这篇文章先讲select和poll函数。接下来分别从函数、结构、注意点分别进行说明...
2019-07-21 18:53:10
1032
原创 守护进程构造原理及实现
守护进程详解守护进程的作用守护进程实例守护进程特性及构造原理守护进程特性进程、进程组、控制终端登陆会话之间的关系守护进程的构造原理(APUE中的创建步骤，实际操作中有些不同)调用umask将文件模式创建屏蔽字设置为一个已知值(通常为0)：调用fork，然后是父进程exit：调用setsid创建一个新会话：改变当前工作目录：关闭不再需要的文件描述符：某些守护继承打开/dev/null使其具有文件描述...
2019-07-13 17:15:43
1709
原创 [基础算法]--分治法
「基础算法」分治法分治法基本概念分治法解题的基本步骤分治法例题归并排序leetcode23. 合并K个排序链表(困难)题目描述：示例：题解：备注分治法基本概念分治法是一种比较常见的算法，也是我们在平常做题或者分析复杂问题的一种思路。分治法简而言之就是分而治之，将大的问题分解成小的问题，再将小问题继续划分，变成足够简单可以直接求解的子问题进行解析，最后再将子问题合并。在我们见过的算法中，归并排序...
2019-07-07 21:51:29
319
原创 Leetcode 75.颜色分类 Sort Colors
Leetcode 75.颜色分类 Sort Colors题目描述（中等）示例题解解题思路：备注题目描述（中等）给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。进阶：一个直观的解决方案是使用计数...
2019-06-30 17:20:46
284
原创 Leetcode 51.N皇后N-Queens
Leetcode 51.N皇后N-Queens题目描述（困难）示例题解题意理解：解题思路：备注题目描述（困难）n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表...
2019-06-30 12:57:14
305
原创 Leetcode 11.盛最多水的容器
Leetcode 11.盛最多水的容器题目描述示例题解备注题目描述给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。图中垂直线代表输入数组 [1,8...
2019-06-30 10:39:29
403
原创 ARP协议
ARP协议ARP协议的作用ARP协议的请求和应答ARP缓存表ARP缓存表自动学习ARP协议的作用当一台主机要将一个帧发送到另一台主机上时，仅知道IP地址是不够的，还需要知道主机在网络中的有效硬件地址。操作系统软件必须知道目的主机的硬件地址，以便向其发送数据。对于TCP/IP网络，ARP(地址解析协议)提供了一种IPV4地址和硬件地址(MAC地址)映射，简而言之就是询问目标IP的MAC地址。A...
2019-06-29 17:18:53
441
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人