跳表的c++实现

从很早之前就从微信的技术文章中学到了跳表的知识,也大概了解了跳表是个什么结构。其实跳表就是有序链表的升级版,在第一层的有序链表之上,构建N层节点数更小的链表。但是一直没有静下心来自己写一下跳表的实现。     跳表的实现,有使用数组的,也有使用单链表的。其中使用单链表的或许更容易理解一点。先放上跳表的示例图。 ...

libevent中的数据结构之尾队列

尾队列,在libevent中也是个应用很高的数据结构。在核心结构event中就有使用到。现在我们来学习下这个数据结构。     首先,我们来看下尾队列有哪些结构体。 结构体定义 尾队列头 ...

libevent中的数据结构之简单队列

这节我们学习libevent提供的五类数据结构中的简单队列。说到队列,我们的映像就是队头出元素,队尾入元素的那种。那么,简单队列,是什么样子的呢??我们先来看下它的结构体定义有哪些,它们又分别是什么样子的。 结构体定义 队列头部结构体 ...

libevent中的数据结构之链表

上一节,我们学习了libevent中的单链表,现在我们再来看看链表的实现。这里我们要重点关注指针的指针的用法。 结构体定义 链表头结构体 ...

libevent中的数据结构之单链表

libevent是使用C语言实现的一套事件驱动的网络库,内部定义了五种常用的数据结构,分别是单向链表、链表,简单队列,尾队列,循环队列、实现在 compat/sys/queue.h中。其中对指针的指针的运用非常值得好好学习    C语言中通过宏定义的,可以实现类似实现C++的模板类。 单...

STL中vector迭代器老调重弹的失效问题

    我们都很了解,STL中迭代器遍历的时候,有个很严峻的问题,失效。但是,我们一直没有对失效下过严格的定义。最早,接触迭代器失效时,是从别人的博客上了解的。当时对整体也没一个明确的概念,只是看博客上写了插入的时候可能会失效,就这么记下了。到现在,自己看了STL中插入的源码,才开始了解,插入的时候,迭代器失效是个什么原因。 插入时迭代器...

通过源码分析STL中set和map对底层红黑树的使用

STL中,set、map、multiset、multimap的底层数据结构,都是红黑树。所以,在查看源码的时候,会发现,对set或者map的插入、删除等操作,其实底层都是对红黑树的插入和删除。所以,我们先来看下STL中的红黑树类的定义。 stl_tree.h     ...

红黑树删除的详细实例

阅读算法导论中关于红黑树删除的部分,关于节点的删除的几种情况,有一些不是很明了,现在画图说明。     情况1:x的兄弟是红色。 此时,红黑树如图1。其中Z表示待删除节点。          &n...

数据结构堆的代码实现

堆的数据结构,是什么呢?其实是一组完全二叉树。堆满足如下几个性质: 假如一个节点的索引是i(这里的索引从1开始),那么它的父节点的索引是⌊i/2⌋,左子节点的索引是 2i,右子节点的索引是 2i+1 父节点的值要么大于儿子节点,要么小于儿子节点。 当父节点大于儿子...

图在实际场景中的应用之wordladder-0.2

继续上次0.1的讨论。 在上个博客中,我提到,这个代码是错误的,原因就在于逆向探测部分存在的问题,那么,是什么问题呢??我们来分析下 首先,新的图: ...