发表于 | 分类于
字数统计: 3,686 | 阅读时长 ≈ 15
引论哈希（Hashing）是以一种能以常数平均时间进行插入，查找，删除的技术。常数时间一般意义上是指O(1)。 是的，Hashing是一种技术，从英文名也可以看出，这是动名词，一般动名词大多表示的不是一个静态的东西。就像抽象数据结构（ADT），ADT是一系列的操作的集合。而不应该是一般以为的抽象的一 ...
阅读全文 »

发表于 | 分类于
字数统计: 611 | 阅读时长 ≈ 3
引论为什么要提出左堆这么一个概念呢？有了二插堆还不够么。这是因为前面提到的数据结构在支持合并（merge）操作的时候是比较差的。比如对于一个二叉查找树来说，要把两个二叉查找树合并，那么可能需要把一个二叉树的结点一个一个的插入到另一个二叉树中，这个的时间消耗是一个很恐怖的事情。因此我们引入左堆。 左堆 ...
阅读全文 »

发表于 | 分类于
字数统计: 1,626 | 阅读时长 ≈ 7
引论优先队列英文名为Priority Queue，也常被称为Heaps，也就是堆。 前面已经有了链表，堆栈，队列，树等数据结构，尤其是树，是一个很强大的数据结构，能做很多事情，那么为什么还要引进一个优先队列的东东呢？它和队列有什么本质的不同呢？看一个例子，有一个打印机，但是有很多的文件需要打印，那么 ...
阅读全文 »

发表于 | 分类于
字数统计: 675 | 阅读时长 ≈ 2
伸展树是一种相对简单的树结构，它保证从空树开始任意M次对树的操作最多花费O(MlogN)的时间。 这种保证并不能排除某次操作的时间为O(N)的可能，但是能保证每次操作平均的时间为O（logN）。对于一系列的操作，有的可能花费时间多些，有的少些。 伸展树基于这样的一个事实： 对于时间花费为O(N}的二 ...
阅读全文 »

发表于 | 分类于
字数统计: 1,320 | 阅读时长 ≈ 6
前面介绍了二叉查找树，二叉查找树的平均时间复杂度为O(logN),是相当低的，因此是一种非常优异的模型。但是这只是对一个随机输入的二叉查找树有效（平衡的二叉树）。当我们进行一定次数的插入（或删除）后，可能会导致二叉树不平衡，甚至退化成链表，这样会重新使时间复杂度变为O(logN).因此，引入AVL树 ...
阅读全文 »

发表于 | 分类于
字数统计: 471 | 阅读时长 ≈ 2
定义大多数的查找树都是二叉树，这个可以理解，因为二叉树相对来说比较简单，易行，用递归方式编程也较易实现。这里介绍一种非二叉的树，即B树。 B数的性质一个M阶的B树，应该具有以下的性质： 根节点要么是叶子，要么具有2-M个子节点 非叶节点（根节点除外）具有[M/2]-M个子节点 所有的叶节点具有 ...
阅读全文 »

发表于 | 分类于
字数统计: 1,127 | 阅读时长 ≈ 5
首先回顾一些树的基本概念：根节点（root）：没有父亲的结点。 树叶（leaf）：没有儿子的结点。 路径（path）：是一个结点到另一个结点的序列表示，这些结点都应该是父子关系。 路径的长（length）: 路径上边的条数。为序列个数减一。 深度（depth）：根结点到某一结点的唯一路径的长。 高（ ...
阅读全文 »

发表于 | 分类于
字数统计: 573 | 阅读时长 ≈ 2
引论递归的定义是：A function defined in terms of itself is called recursive. 也就是说一个函数的定义需要用到这个函数的本身。递归是一个很奇妙的思想，从上面的定义看去，递归貌似一个死循环，这个当然是不对的，递归总会有一个结束的条件，也就是基准情 ...
阅读全文 »

发表于 | 分类于
字数统计: 375 | 阅读时长 ≈ 2
队列与堆栈不同，队列是一边进，另一边出的表，如下图所示： 队列的主要操作也比较少，主要的有入队，出队，检查队列是否为空， 队列一般会有两个标志位，即Front和Rear，表示对头和队尾，通过对这两个标志位进行操作，可以对队列进行适当的操作。 数组形式声明与实现1234567891011struct ...
阅读全文 »

发表于 | 分类于
字数统计: 532 | 阅读时长 ≈ 2
栈就是插入和删除都在一个方向的一种表的数据结构，也就是所谓的“先进后出”，其实就像一个瓶子，只有一面是能够打开的，要想拿出最里面的东西，就要先吧上面的东西移开。下图形象的显示了什么是栈。其实这个图说明了一切 <注意图中的SP与下面程序中的S不是一个东西，SP是栈指针，它指向栈顶元素，而S是为 ...
阅读全文 »