Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  数据结构分类

STL中链表的排序

STL中的链表使用起来非常方便,但其不能使用标准的排序函数sort,那么怎么对其进行排序呢?其实list自带有sort成员函数,使用的是非递归的归并排序,本文将讲解其排序的基本思想及具体代码实现。

继续阅读»

二叉树遍历(递归、非递归、Morris遍历)

二叉树遍历是二叉树中最基本的问题,其实现的方法非常多,有简单粗暴但容易爆栈的递归算法,还有稍微高级的使用栈模拟递归的非递归算法,另外还有不用栈而且只需要常数空间和线性时间的神奇Morris遍历算法,本文将对这些算法进行讲解和实现。

继续阅读»

AVL树

AVL树是一种自平衡的二叉查找树(Balanced Binary Tree),由于其任意节点的左右子树的高度差至多为一,查找、插入、删除等操作的复杂度在平均和最坏情况下都是O(log n)。AVL树和红黑树都是平衡的二叉查找树,但二者有一些细微的区别,本文将详细讲解AVL树的原理与实现,并且部分实现过程参照了红黑树,具体可以参考 红黑树

继续阅读»

Linux内核中的链表

链表是最基本的数据结构之一,Linux的内核中也广泛使用了链表,特别是双向链表,比如进程的描述符、设备列表以及各种功能模块中的数据组织。
但是Linux内核中链表的实现方式比较特殊,本文将介绍其实现细节及如何在自己的程序中使用这个链表。

继续阅读»

Linux内核红黑树原理与使用

红黑树(Red-Black Tree,RBT)是一种平衡的二叉查找树,前面的红黑树原理与实现这篇文章中详细介绍了红黑树的细节。在Linux的内核源代码中已经给我们实现了一棵红黑树,我们可以方便地拿过来进行使用。
本文将参考Linux内核的源码和文档资料,介绍Linux内核中红黑树的实现细节及使用方法。

继续阅读»

红黑树

二叉查找树可以方便地维护一个动态集合,实现快速的添加、删除以及查询操作。但仅仅当树的高度较低时执行速度较快,当树的高度增加甚至变得极度不平衡时,各种操作的性能急剧下降。红黑树(Red-Black Tree,RBT)是一种平衡的二叉查找树,能在最坏情况下仍然获得较好的时间复杂度。目前C++ STL中包括set、multiset、map、multimap等多种数据结构内部都使用了红黑树或者其变体进行实现。
本文参考算法导论中红黑树章节,将详细介绍红黑树的原理及其在C/C++中的具体实现代码。注意,红黑树的思想及实现跟普通的二叉查找树关系非常大,如果你对二叉查找树还不是非常熟悉,建议先阅读此文:二叉查找树 http://noalgo.info/603.html

继续阅读»

二叉查找树

二叉查找树(binary search tree,又叫二叉搜索树或者二叉排序树)是一种非常重要的数据结构,许多高级树结构都是二叉查找树的变种,例如AVL树、红黑树等,理解二叉查找树对于后续树结构的学习有很好的作用。同时利用二叉查找树可以进行排序,称为二叉排序,也是很重要的一种思想。
本文主要参考算法导论,详细介绍二叉查找树的原理及具体的C++代码实现。

继续阅读»

并查集及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。
本文首先介绍并查集的定义、原理及具体实现,然后以其在最小生成树算法中的一个经典应用为例讲解其具体使用方法。

继续阅读»

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论