《数据结构与算法分析》的原文摘录
-
数据抽象类型（ADT）是一些操作的集合。抽象数据类型是数学的抽象；在ADT的定义中根本没有涉及如何实现操作的集合。这可以看成模块化设计的扩充。 (查看原文) —— 引自第64页 -
对表的操作可以用数组来实现。但是需要对表的大小的最大值进行估计，通常需要估计得大一些，会浪费大量的空间。这是严重的局限，特别是存在许多未知大小的表的情况下。所以简单数组一般不用来实现表这种结构。 (查看原文) —— 引自第64页 -
任何表的形式都能实现栈。 (查看原文) —— 引自第64页 -
队列的基本操作时入队，它是在表的末端插入一个元素，还有出队，它是删除在表开头的元素。 队列一般被用于处理用概率方法计算用户排队预计等待时间，等待服务的队列。诸如此类的问题被称为排队论。 (查看原文) —— 引自第64页 -
算法分析评估里面的N是代表输入数据的规模 对于大量数据的输入，链表的线性访问时间太慢，不宜使用。树这种数据结构的运行时间平均为O(log N)。树的一种自然的定义方式是递归方法。 (查看原文) —— 引自第100页 -
具有相同父亲的节点为兄弟（sibling）.一个树的深度等于它的最深树叶的深度，该深度总是等于这棵树的高度。 树节点的定义：将灭个节点的所有儿子都放在树节点的链表中。 (查看原文) —— 引自第100页 -
树有很多应用。最流行的用法之一就是UNIX,VAX/VMS和DOS在内常用操作系统的目录结构。严格来说UNIX文件系统不是树，是类树（treelike）。 (查看原文) —— 引自第100页 -
二叉树有许多与搜索无关的重要应用。主要用途之一就是在编译器设计领域。 (查看原文) —— 引自第100页 -
使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它在左子树中所有关键字值小于X的关键字值，而它右子树中所有关键字值大于X的关键字值。 (查看原文) —— 引自第100页 -
正如许多数据结构那样，最困难得是删除。如果删除次数不多，则通常使用的策略是懒惰删除（lazy Deletion）。当一个元素要被删除时，它仍然留在树中，而是只是做了个被删除的记号。 (查看原文) —— 引自第100页 -
一棵树的所有节点的深度的和称为内部路径长。 (查看原文) —— 引自第100页 -
阶为M的B树是一棵具有下列结构特性的树： a.树的根或者是一片树叶，或者其儿子数在2和M之间。 b.根除外，所有非树叶节点的儿子树在[M/2]（向上取整）和M之间。 c.所有的树叶都在相同的深度上。 所有的数据都在树叶上。 B树实际用于数据库系统中，在那里的树被存储在物理磁盘上，而不是内存中 (查看原文) —— 引自第100页 -
散列表的实现常常叫做散列(hashing)。散列是一种用于以常数平均时间执行插入，删除和查找的技术。但是，需要元素间任何排序信息的操作将不会得到有效支持。 (查看原文) —— 引自第131页 -
分离链表法的缺点是需要指针，由于给新单元分配地址需要时间，因此就导致算法的速度多少减慢。在开放定址法中，如果有冲突发生，就尝试选择另外的单元，知道找到空的单元为止。 (查看原文) —— 引自第131页 -
优先队列至少允许两种操作的数据结构：Insert（插入），它的工作是显而易见的，以及DeleteMin（删除最小者），它的工作是找出，返回和删除优先队列中最小的元素。 (查看原文) —— 引自第164页 -
用链表，以O(1)在表头执行插入，再以O(N)遍历找出最小元。用二叉查找树，如果用二叉查找树，DeleteMin会反复删除最小元，右子树加重，损害树的平衡 (查看原文) —— 引自第164页 -
堆有两个性质：结构性和堆序性。对堆的一次操作可能破坏两个性质中的一个，因此，堆操作必须要到堆的所有性质都被满足时才能终止。 (查看原文) —— 引自第164页 -
堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。容易证明，一棵高为h的完全二叉树，节点有2^h到2^(h+1) - 1个节点。所以完全二叉树的高是floor(log N)，显然它是O(log N)。 完全二叉树很有规律，它可以用一个数组来表示，不需要指针。 对于数组中任意一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的（2i + 1）中，它父亲则在位置floor(i / 2)上。一个堆结构将由一个数组，一个代表最大值的整数以及当前的堆大小组成。 (查看原文) —— 引自第164页 -
使操作被快速执行的性质被称为堆序性。在一个堆中，对于每个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。根据堆序性，最小元总可以在根处找到。 (查看原文) —— 引自第164页 -
Insert的一般策略是上滤（percolate up）.新元素在堆中上滤直到找出正确的位置。 把一个小于或等于堆中任何元素的值放到位置0，使得循环得以终止。我们称为标记。 (查看原文) —— 引自第164页
作者: 韦斯 (Mark Allen Weiss)
副标题: Java语言描述（英文版·第3版）
isbn: 7111412362
书名: 数据结构与算法分析
页数: 614
定价: 79.00元
出版社: 机械工业出版社
出版年: 2013-2-1
装帧: 平装