分类 : 70个相关结果 959次浏览

数据结构与算法二十三:字符串匹配基础(上)

从今天开始,我们来学习字符串匹配算法。字符串匹配这样一个功能,我想对于任何一个开发工程师来说,应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数,比如 Java 中的 indexOf(),Python 中的 find() 函数等 …

数据结构与算法二十二:深度和广度优先搜索

上一节我们讲了图的表示方法,讲到如何用有向图、无向图来表示一个社交网络。在社交网络中,有一个六度分割理论,具体是说,你与世界上的另一个人间隔的关系不会超过六度,也就是说平均只需要六步就可以联系到任何两个互不相识的人。 一个用户的一度连接用户 …

数据结构与算法二十一:图的表示

微博、微信、LinkedIn 这些社交软件我想你肯定都玩过吧。在微博中,两个人可以互相关注;在微信中,两个人可以互加好友。==那你知道,如何存储微博、微信等这些社交网络的好友关系吗?== 这就要用到我们今天要讲的这种数据结构:图。实际上,涉 …

数据结构与算法十九:堆得应用

搜索引擎的热门搜索排行榜功能你用过吗?你知道这个功能是如何实现的吗?实际上,它的实现并不复杂。搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的 Top 10 搜索关键词。 那请 …

数据结构与算法十八:堆和堆排序

我们今天讲另外一种特殊的树,“堆”(Heap)。堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。 前面我们学过快速排序,平均情况下,它的时间复杂度为 O(nlogn)。 …

数据结构与算法十七:递归树!

今天,我们来讲树这种数据结构的一种特殊应用,递归树。 我们都知道,递归代码的时间复杂度分析起来很麻烦。《排序(下)》里讲过,如何利用递推公式,求解归并排序、快速排序的时间复杂度,但是,有些情况,比如快排的平均时间复杂度的分析,用递推公式的话 …

数据结构与算法十六:红黑树(下)!

红黑树是一个让我又爱又恨的数据结构,“爱”是因为它稳定、高效的性能,“恨”是因为实现起来实在太难了。我今天讲的红黑树的实现,对于基础不太好的同学,理解起来可能会有些困难。但是,我觉得没必要去死磕它。 我为什么这么说呢?因为,即便你将左右旋背 …

数据结构与算法十六:红黑树(上)

上两节,我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时间复杂度跟树的高度成正比,理想情况下,时间复杂度是 O(logn)。 不过,二叉查找树在频繁的动态更新过程中,可能会出现 …

数据结构与算法十五:二叉树基础(下)

上一节我们学习了树、二叉树以及二叉树的遍历,今天我们再来学习一种特殊的的二叉树,二叉查找树。二叉查找树最大的特点就是,支持动态数据集合的快速插入、删除、查找操作。 我们之前说过,散列表也是支持这些操作的,并且散列表的这些操作比二叉查找树更高 …

数据结构与算法十五:二叉树基础(上)

前面我们讲的都是线性表结构,栈、队列等等。今天我们讲一种非线性表结构,树。树这种数据结构比线性表的数据结构要复杂得多,内容也比较多,所以我会分四节来讲解。 我反复强调过,带着问题学习,是最有效的学习方式之一,所以在正式的内容开始之前,我还是 …