/android-chrome-192x192.png

Bing's Blog

自由 分享 合作

  

数据结构与算法之图

什么是图

在前面的文章中, 我们了解了树的概念, 重点是二叉树, 图在拓扑结构上和树有点类似, 但是图不是树.

直观地, 先来看一个图的拓扑结构:


Union可以怎么用

union 改名操作

比如以下这个类,我期望外部不仅能通过P1这个名字访问P1这个成员变量,也能通过Y/R等名字访问他的P1。


数据结构与算法之跳表

一维链表

链表不需要一块很大的连续的存储空间是其优点, 但是对一串有序序列, 使用一维链表查询的时间复杂度是$O(n)$, 能否如查找二叉树之类, 将其查找时间复杂度降为$O(logn)$呢?


数据结构与算法之二叉查找树

什么是二叉查找树

对一般容器的查找, 我们可以按顺序遍历, 找到符合要求的元素就返回; 对于元素是有序的容器, 可以使用二分查找等方法查找, 减少操作的时间复杂度.

容易知道, 一般查找的平均时间复杂度是O(n), 二分查找的平均时间复杂度是O(logn).