概述: 1.动态规划是通过组合子问题的解而解决原问题的。 2.动态规划适用于子问题不是独立的情况,也就是各子问题的包含公共的子子问题。 3.动态规划对每个子问题只求解一次,将其结果保存在一张表中。 4.动态规划的设计步骤:a.描述最优解的结构b.递归定义最优解的值c.按自底向上的方式计算最优觖的值d.由计算出的结构构造一个最优解 15.1钢条切割 钢条切割问题:给定定长的钢条和价格表,求切割方案,使得收益最大。如果n英寸的钢条的价格足够大,则不需要切割。 代码如下: //朴素递归求解钢条切割收益,由于递归过程中反复…

2014年8月18日 0条评论 3点热度 阅读全文

12.1 二叉查找树 定义:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。如果y是x的右子树中的一个结点,则key[x]≤key[y]. 前序遍历:先遍历根再遍历左右子树,简称根-左-右。 中序遍历:先遍历左子树再遍历根再遍历右子树,简称左-根-右。 后序遍历:先遍历左右子树再遍历根,简称左-右-根。 书中中序遍历代码: //中序遍历 void INORDER-TREE-WALK(struct Tree *p) { if (p->key) { INORDER-TR…

2014年6月6日 0条评论 17点热度 阅读全文

12.1 二叉查找树 定义:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。如果y是x的右子树中的一个结点,则key[x]≤key[y]. 前序遍历:先遍历根再遍历左右子树,简称根-左-右。 中序遍历:先遍历左子树再遍历根再遍历右子树,简称左-根-右。 后序遍历:先遍历左右子树再遍历根,简称左-右-根。 书中中序遍历代码: //中序遍历 void INORDER-TREE-WALK(struct Tree *p) { if (p->key) { INORDER-TR…

2014年6月6日 0条评论 4点热度 阅读全文

二叉查找树是一种应用十分广泛的数据结构,它在算法中应用十分广泛,二叉查找树支持多种动态集合的操作,这些操作主要包括: 1、查找某个特定值: 2、二叉查找树中最小值: 3、二叉查找树中最大值: 4、某个节点的前驱: 5、某个节点的后继: 6、插入特定值: 7、删除特定值: 一般情况下,我们为了保持查找和删除情况的唯一性,假设二叉查找树中各个元素的key值不想等。 下面一一剖析二叉查找树的结构与方法: 1、二叉查找树的数据结构: // 构造二叉查找数的内部类,这就相当于C语言中的结构体 private class Tr…

2014年4月2日 0条评论 11点热度 阅读全文

查找树是一种数据结构,它支持多种动态集合操作,包括search, minimum, maximum, predecessor, successor, insert以及delete。他既可以用作字典,也可以用作优先队列。 二叉查找树上基本操作的执行时间和树的高度成正比。对一棵n个结点的完全二叉树来说,这些操作的最坏情况运行时间为Θ(lgn)。但是如果树是含有那个结点的线性链,则这些操作的最坏运行时间是Θ(n)。本章可以看到一棵随机构造的二叉查找树的期望高度为O(lgn)。 实际中,并不能总是保证二叉查找树是随机构造的…

2011年2月26日 0条评论 8点热度 阅读全文