6第六章树和二叉树..ppt

Zhejiang University of Technology * 练习1 有一份电文中共使用5个字符：a、b、c、d、e，它们出现的频率依次为4、7、5、2、9，试画出对应的Huffman树（按左子树根结点的权小于等于右子树根节点的权的次序构造），并求出每个字符的Huffman编码。 Zhejiang University of Technology * 练习2 设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵Huffman树，并求其加权路径长度WPL。 Zhejiang University of Technology * 　程序设计=数据结构+算法 程序设计就像盖房子，数据结构就像砖、瓦，而算法就是设计图纸。若想盖房子首先必须有原料（数据结构），但是这些原料不能自动地盖起想要的房子；必须按照设计图纸（算法）上的说明一砖一瓦地去砌，才能拥有你想要的房子。 Zhejiang University of Technology * 程序设计也一样，编译工具（如Java /C/Basic/Pascal等）中有各种功能语句或基本结构（如Read/Write/Real/Boolean等），它们不会自动排列成你要的程序代码。 你得按照程序规定的功能去编写，而程序的功能实现就是算法的具体体现。 所以通俗地说：你必须按照特定的规则，把特定的功能语句和基本结构按照特定的顺序排列起来，形成一个有特定功能的程序，这就是：程序设计＝数据结构＋算法。　 Zhejiang University of Technology * 数据结构是程序设计这座大厦的基础，没有基础，无论设计有多么高明，这座大厦不可能建造起来的。算法则是程序设计的思想，它的灵魂！ 没有灵魂的程序不能叫程序，只是一堆杂乱无章的符号而已。在程序设计中，数据结构就像物质，算法就是意识。 这就像哲学上说的：意识是依赖于物质而存在的，物质是由于意识而发展。双方是相互依存、缺一不可的！ 　 Zhejiang University of Technology * 数据结构内容不多仅仅有几个系统自带的基本结构（像顺序结构、分支结构、循环结构、函数过程）、数据类型（整型、实型、布尔、字符等）和用户定义的高级点的数据结构（数组、集合、文件、指针（队列、栈、树、图等）······）就这么多。 算法则多种多样！可以让你的数据以你想要的方式排列（当然要符合语法和功能要求）。 Zhejiang University of Technology * 再打个比方，数据结构是人体的各种组织、器官，算法则是人的思想。 你可以用你的思想去支配你身体的各个可以运动的器官随意运动。如果，你想去取一个苹果，你可以走过去，也可以跑过去，只要你想，你甚至可以爬过去。 但是无论如何，你的器官还是你的器官（没有变），目的还是同一个目的（取苹果），而方式却是随心所欲！这就是算法的灵活性，不固定性。因此可以这样说：数据结构是死的，而算法是活的！ Zhejiang University of Technology * 有学生问：“我数据结构上面的都学了，也知道该怎么样用，可是我为什么还是在编程时，不知道该怎样用呢？“ 其实，这就是缺少算法思想的一个具体表现。并不是学好了数据结构就会编程了。算法是灵活多变的，它不像数据结构那样有固定的形式。算法的不固定性就决定了它的特点，你不可能把所有的算法都学会，因为它是无穷尽的。但是如果能把自己学的有限的算法融会贯通了，那就了不起了。 Zhejiang University of Technology * 首先，你要养成一个良好的程序设计风格和习惯。其中最重要的是养成自上向下逐步求精的程序设计思想和方法。 怎样才是自上向下逐步求精的程序设计呢，举个例子。有这样一个问题：已知三角形的两边及夹角，求第三边及面积。 Zhejiang University of Technology * 现在，当你看到这个问题时，你不要立即下手去编写，而是要思考一下怎样才能求解（算法），然后写下来以免忘记。于是就写了： 一级算法： １　输入两边的长度ａ、ｂ以及夹角Ａ　　　　　　　　　　　　　　　　　　　　　　　　 ２　计算第三边ｃ和面积ｓ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ３　输出c以及s　 Zhejiang University of Technology * 当你写完之后，你若觉得第２步不太清晰，还不能写出代码，那就继续求精。 二级求精： 2-1、将α的角度转换为弧度； 2-2、c=sqrt(a*a+b*b-2*a*b*cos(α)); 2-3、s=1/2*(a*b*sin(α)) 求精可以因人而异，像上面的题目，若是一个编过很多程序的程序员来说，可能不用什么