青春不谢-CSDN博客

转载源码分析redis的有序集合，学习skiplist跳跃表数据结构

最近在看redis源码，看到跳跃表的插入操作时感觉很头大，网上各种文章都只是在进行一个原理性的分析，唯独这篇文章一行一行代码地讲解，非常仔细和透彻。希望能帮助正在阅读redis源码的你！文章地址源码分析redis的有序集合，学习skiplist跳跃表数据结构

2016-05-03 16:51:33 731

原创第7章图

leetcode刷了一大半，数组，链表，树，队列和栈的题目已经做了好多，感觉比较扎实了。突然发现后面好多关于图算法的问题，没办法，又继续开始学习“图”这种数据结构。折腾了一天，把图的创建，深度优先级遍历（DFS）和广度优先级遍历（BFS）都用c++写出来了，算法参照了《算法导论》和《数据结构和算法》。遍历是各种图操作的基本思路，所以一定要熟练掌握。注：1. 图的表示采用了邻接链表，因为这种结构在

2016-03-28 22:32:00 588

原创用C++的string::size()和string::length()返回值做比较

楼主今天在自己实现kmp算法的c++代码时，发现了一个问题。我先把代码贴上来。//kmp search#include <iostream>#include <vector>using namespace std;vector<int> GetNext(string pattern){ vector<int> next(pattern.size(), -1); int i =

2016-03-16 14:17:59 3420 7

原创 LeetCode: 9. Palindrome Number

求一个整数是否是回文数。形如121, 73637等等之类的数都是回文数。要求空间复杂度为O(1)，这就让很多想转换为字符串再去判断的同学止步了；有的同学可能想把该整数倒转之后再去和原数比较是否相等，但是倒转后的数可能超过有符号整数范围，比如2147483647，倒转之后是7463847412，显然不合法。我的思路是这样的：逐个去掉该整数的最后一位，将去掉的一位作为新整数的最高位；一边“砍掉”

2016-02-24 15:04:21 659

32位机器上的最大有符号数为2147483647，最大无符号数是4294967295。这对于实际的计算显然是不够的，于是就产生了大数乘法的需求。其思路不算难，按照我们平时计算两个数的乘积的流程就行了。如果你使用的是c语言等不能动态扩展数组的语言，有一个需要考虑的问题是：两数相乘后的位数为多少？这需要一点点的数学知识，两数乘积的位数不大于两数的位数之和。所以需要提前分配好足够的空间。我这里使用c++来

2016-02-24 10:44:52 3939

原创 Trie树的c++实现

关于Trie树的理论的东西，各位大神都已经说得很多了。参见这里是Trie树的简单介绍或者这里是它和其他一些树结构的使用场景。 Trie树又称“字典树”或“前缀树”，常见于小规模地统计词频，典型的用空间换时间。下面是我的一种c++实现，记录一下。 trie.h头文件#ifndef _TRIE_STRUCTURE_H#define _TRIE_STRUCTURE_H#include <string

2016-02-18 19:56:09 963

原创 LeetCode: 113. Path Sum II

这道题折磨了我好长时间，终于通过了所有test。语言c++，时间16ms。成就感能让我继续努力，所以记录一下。题目在这里Path Sum II，题目的意思是定义从二叉树的根结点到叶子结点为一条路径，将路径上所有结点的值加起来是该路径的和（path sum），现在给定一个整数，求出所有路径和等于该数的路径，结果保存在二维数组中。思路一：递归。与二叉树有关的大部分问题都可以用递归来处理，当问题规模不大时

2016-02-17 21:44:35 851

原创次优二叉树 --- 折半查找在元素不等概情况下的改进

1、次优查找树是折半查找的一种一般形式，其理论基础是“被查找的各元素是不等概的”，而折半查找就是等概的，我们在使用中默认了这一性质。比如，对于有序数组 int a = {1,2,3,4,5}; 用折半查找时，应该现比较最中间的3，如果如果待查整数等于3，查找结束。如果小于3，就继续在左边的部分数组里查找；反之，在右边的数组里查找。问题在于，我们为什么不从4开始找呢？为什么不从1开始呢？

2016-02-05 13:55:37 3226

原创求二叉树的每个结点的子孙数量

《数据结构》严蔚敏版习题6.55 为二叉链表的结点增加DescNum域，表示该结点的子孙数量。编写一个算法，求二叉树的每个结点的子孙数目并存入其DescNum域。思路：方案1，利用递归，从根节点开始对每个结点都调用一次函数来求每个节点的子孙数量很明显递归调用肯定很慢，因为要不断地压栈弹栈。方案2，与方案1的遍历方向相反，从最下面的叶子结点开始计算每个结点的子孙数量，然后对于其双亲节点，

2016-01-26 17:42:35 6337 1

原创求任意一颗二叉树的繁茂度

在《数据结构》严蔚敏版上的习题看到这个问题。繁茂度的定义：各层节点数的最大值与树的高度的乘积树的深度好求，递归调用就行了。关键在于如何求出各层的最大节点树？下面是我的一种实现方法： bitree.h#include <iostream>#include <cstdlib>#include <cstdio>#include <stack>using namespace std;typ

2016-01-23 18:42:37 4557 1

原创赫夫曼树的创建

今天在看《数据结构》（严蔚敏版），第6章第6节，讲到创建赫夫曼树的时候，给出的算法没有实现Select()函数，即选出数组中最小的两个权值的节点。于是我自己用c++实现了一个版本，考虑到算法的效率问题，我选择了创建一个小顶堆，每次从堆顶提取出最小的权值节点，这样比暴力for循环求最小权值节点的效率要高，特别是在树的节点很多时。而建堆的操作也使得节点会被调整顺序，这也使得我定义的描述的节点的结构体跟书

2016-01-13 21:53:41 1339

原创基于python的密码管理工具

如何记住各种各样的账户名和密码？这是一个头疼的问题。现在各种社区，商业网站，客户端app，全都使用用户名+密码或邮箱+密码的登陆方式。当你使用了越来越多的服务，就意味着你要管理越来越多的账户和密码，怎么能把他们都记住呢？因为你也并不是每个网站都经常上，有时候需要了才发现用户名什么的根本就忘记了，这个时候难道还要再重新注册一个账户吗？把用户名和密码全部记下来？万一被别人看到了怎么办？放到手机

2016-01-05 22:56:51 2827

原创 C++编程思想学习笔记---第15章多态性和虚函数

多态性（polymorphis）提供了接口与具体实现之间的另一层隔离，从而将”what”与”how”分离开来。多态性改善了代码的组织性和可读性，同时也使创建的程序具有可扩展性。15.1 C++程序员的演变c程序员可以用三步演变为C++程序员简单地把C++作为一个更好的C：更强的类型检查等进入基于对象的C++：将数据结构和操作绑定，更清晰地组织代码使用虚函数：这是面向对象设计的精髓15.2

2015-12-30 18:23:35 794

原创 C++编程思想学习笔记---第14章继承和组合

继承是面向对象程序设计的基石14.1 组合语法下面一段代码把类型X的一个对象作为公共对象嵌入到一个新类内部，实现了组合的语法。//: C14: useful.h//A class to reuse#ifndef USEFUL_H#define USEFUL_Hclass X{ int i;public: X() { i = 0; } void set(int ii

2015-12-29 22:55:48 758

原创第6章树和二叉树要点提炼

6.2 二叉树6.2.1 二叉树的定义二叉树是一种特殊的树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒6.2.2 二叉树的性质性质1——在二叉树的第i层上至多有2i−12^{i-1}个结点性质2——深度为k的二叉树至多有2k−12^{k}-1个结点，（k ≥\geq 1）性质3——对任何一棵二叉树T，如果其终端结点数为n0n_{0}，度为2的结

2015-12-24 15:00:40 637

原创 C++编程思想学习笔记---第13章　动态创建对象

一个空中交通指挥系统需要处理多少架飞机？一个网络中将会有多少个节点？为了解决这个普通的问题，我们需要在运行时可以创建和销毁对象是最基本的要求。当然Ｃ早就提供了动态内存分配函数malloc()和free()，它们可以从堆中分配存储单元。然而这些函数将不能很好地运行，因为构造函数不允许我们向他传递内存地址来进行初始化。如果这么做了，我们可能： 1. 忘记了。则在c++中的对象初始化将会难以保证

2015-11-08 17:57:00 821

原创 C++编程思想学习笔记---第12章　运算符重载

C++编程思想学习笔记—第12章　运算符重载运算符重载只是一种语法上的方便，只是另一种形式的函数调用。应当说明，运算符重载不应该被滥用，只有在能使涉及类的代码更易写，特别是更易读时，才有理由重载运算符12.1　运算符重载的语法：#include <iostream>using namespace std;class Integer{ int i;public: I

2015-09-24 22:41:03 625

原创 C++编程思想学习笔记----第11章　引用和拷贝构造函数

11.1 C++中的指针c和c++指针的最重要区别在于c++是一种类型要求更强的语言。在c中，void* 类型的指针可以随意地指向其他类型的指针，而c++中必须显示地使用类型转换通知编译器和读者，这算是它比较严谨的地方。11.2 C++中的引用#include using namespace std;int y;int& r = y;//r is a reference

2015-09-22 22:51:22 612

原创循环缓冲区C++的一种实现

之前去腾讯面试的时候被问到的一道题目：实现一个循环缓冲区（不带互斥锁）。仔细一想，其实和循环队列的思想一模一样，还是怪自己数据结构没学好阿（其实我是学通信的，所以最近在恶补）。还是先上代码头文件如下，CircleBuffer.h#ifndef _CIRCLE_BUFFER_H_#define _CIRCLE_BUFFER_H_//basic data type renamety

2015-09-09 23:17:03 3188 1

原创 N皇后问题的一般解法--回溯法

先上代码#include #include #include #include using namespace std;vector board;void ShowQueen(void){ for(unsigned int i = 0; i < board.size(); i++) { cout << "(" << i << "," << board[i] << ")

2015-09-07 19:31:10 1882

原创打印一个集合的幂集C++实现

问题：打印一个集合的幂集？分析：可自行百度幂集的定义，简单点说就是打印一个集合（此处用英文字母代替）的所有子集（包括空集）。例如：集合 {A，B，C}的幂集为ABC, AB#, A#C, A##, #BC, #B#, ##C, ###, 其中#表示空之前去一家公司面试的时候碰到的一道题，当时也想到了应该用递归，不过细节没考虑好，导致当时很囧地做不出来。回来之后花了10分钟写一个，不

2015-09-01 18:02:53 2815

原创 C++编程思想学习笔记---第十章名字控制

第十章名字控制10.1 来自C语言中的静态元素在C和C++的定义中，static都有两种基本含义：1) 在固定的地址上进行存储分配，对象在静态区创建，而不是每次调用函数时在堆栈上产生。 ===> 生存期：在每次进入定义该变量的函数时2) 如果static变量是定义在某个文件中，不在任何函数内，则它在该文件中是全局的。 ===>作用域：仅在该文件中可用（除非用extern在别的文

2015-06-25 21:49:38 658

原创 C++编程思想学习笔记---第九章内联函数

第九章内联函数为了解决C中不太方便，且容易出错的宏定义的问题，C++中使用内联函数来代替。内联函数的两大有点：1) 增加了参数检查，保证了代码的正确性 2) 仍然像C中一样，内联函数在调用处展开，而不是像普通函数一样需要压栈，RETURN等返回，减少了函数调用的开销

2015-05-17 13:40:33 727

原创 C++编程思想学习笔记---第八章常量

第八章常量概念（由关键字const表示）是为了使程序员能够在变和不变之间画一条界限。这在C++程序设计项目中提供了安全性和可控性1、值代替C语言用#define BUFSIZE 100的宏定义方式来做值替换。好处是100的意义清楚，并且修改方便。有经验的程序员会把100加上括号，以防止某些因为逻辑不严谨造成的错误。但是因为预处理器只做些文本替代，它既没有类型检查概念，也没有该

2015-04-26 19:51:58 670

原创 C++编程思想学习笔记---第七章函数重载与默认参数

第七章函数重载与默认参数一、为什么要重载函数1.我们想用同一个函数的调用对不同类型的数据参数进行处理，编译器知道在声明函数的时候它的参数是什么类型。比如我想比较两个（同类型）数的大小，事先并不知道会是什么类型的数。我只需要一个函数名compare(); 对于不同的数据类型，我只需要修改参数即可。如compare(int a, int b)是比较两个整型数的大小，compare(doubl

2015-04-18 11:48:39 715

转载大小端模式详解

大小端模式详解端模式（Endian）的这个词出自Jonathan Swift书写的《格列佛游记》。这本书根据将鸡蛋敲开的方法不同将所有的人分为两类，从圆头开始将鸡蛋敲开的人被归为Big Endian，从尖头开始将鸡蛋敲开的人被归为Littile Endian（这句话最为形象）。小人国的内战就源于吃鸡蛋时是究竟从大头（Big-Endian）敲开还是从小头（Little-Endian）敲开。在

2015-04-08 15:54:32 858

原创 C++编程思想学习笔记---第五章隐藏实现

C++编程思想的学习笔记

2015-04-06 17:03:53 805

原创 2G模块如何实现内置协议栈上网

前一阵之做了一个2G模块作客户端通过内置协议栈上网的项目，我只负责库文件，业务层的实现是由别人完成的。这里想就过程中遇到的问题做个总结，算是学习笔记。注：以下内容都是本人在工作过程中的自己思考和向前辈工程师们讨教的结果，若有侵权，请与我联系。首先想说一下什么是内置协议栈。说白了就是模块内部已经集成了TCP/IP协议栈，开发者只需要调用模块供应商提供的AT指令接口就可以实现数据的收发

2015-03-21 17:05:57 8003

原创内置协议栈的GPRS模块SIM800，只用AT指令控制就可以拨号上网了吗？

最近在做一个无线模块SIM800，手册上是说内置TCP/IP协议

2014-11-18 11:12:13 8054 3

青春不谢的专栏