-
6.3 树的抽象数据类型
6.3 树的抽象数据类型 6.3 树的抽象数据类型 相对于线性结构，树的操作就完全不同了，这里我们给出一些基本和常用操作。 ADT 树( tree ) Data 树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。 Operation InitTree (* T ): 构... -
6.6 二叉树的性质
6.6 二叉树的性质 6.6.1 二叉树性质1 6.6.2 二叉树性质2 6.6.3 二叉树性质3 6.6.4 二叉树性质4 6.6.5 二叉树性质5 6.6 二叉树的性质 二叉树有一些需要理解并记住的特性，以便于我们更好地使用它。 6.6.1 二叉树性质1 性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。 这个性质很好记忆，... -
7.3 图的抽象数据类型
7.3 图的抽象数据类型 7.3 图的抽象数据类型 图作为一种数据结构，它的抽象数据类型带有自己特点，正因为它的复杂，运用广泛，使得不同的应用需要不同的运算集合，构成不同的抽象数据操作。我们这里就来看看图的基本操作。 ADT 图( Graph ) Data 顶点的有穷非空集合和边的集合。 Operation Create... -
8.4.1 折半查找
8.4.1 折半查找 8.4.1 折半查找 我们在讲树结构的二叉树定义（本书第6.5节）时，曾经提到过一个小游戏，我在纸上已经写好了一个100以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如图8-4-1所示。 图8-4-1 折半查找（Binary Search）技术... -
8.6.4 二叉排序树总结
8.6.4 二叉排序树总结 8.6.4 二叉排序树总结 总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少... -
8.8 多路查找树（B树）
8.8 多路查找树（B树） 8.8 多路查找树（B树） 台湾出版人何飞鹏在《自慢》书中曾经有这样的文字：“要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司，因为肯定每一个人都只是用直觉与反射神经在互相应对，不可能有深度的思考与规划……，语言是沟通的工具，文字是记录存证的工具，而文字化的... -
9.8.2 归并排序复杂度分析
9.8.2 归并排序复杂度分析 9.8.2 归并排序复杂度分析 我们来分析一下归并排序的时间复杂度，一趟归并需要将SR[1]～SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]～TR1[n]中，这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行次，因此，总的时间复杂度为O...