04级第9章A课件.pptVIP

电信01-04及0310班座位表 数据结构课程的内容 第9章 查找 9.1 基本概念 讨论： 讨论4：如何评估查找方法的优劣？ 9.2 静态查找表 一、顺序查找（ Linear search，又称线性查找 ） （2）算法的实现： 讨论1：查找失败怎么办？ 二、折半查找（又称二分查找或对分查找） 折半查找举例： 讨论1：若关键字不在表中，怎样得知并及时停止查找？ 请注意：ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以： 再用查找二叉树/判定树来分析ASL(参见教材P220） 三、分块查找（索引顺序查找） 分块查找过程举例： 查找效率ASL分析： 四、静态树表的查找 9.3 动态查找表 一、二叉排序树的定义 将线性表构造成二叉排序树的优点： 讨论1：二叉排序树的查找插入算法如何实现？ 讨论2：二叉排序树的删除操作如何实现？ 难点：*p有两棵子树时，如何进行删除操作？ 例：请从下面的二叉排序树中删除结点P。 三、二叉排序树的查找分析 最好情况：与折半查找中的判定树相同（即形态比较均衡） 1) 二叉排序树上查找某关键字等于结点值的过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 ?log2 n?+1 2) 一棵二叉排序树的平均查找长度为： 其中： ni 是每层结点个数； Ci 是结点所在层次数； m 为树深。 最坏情况：插入的n个元素从一开始就有序（单调增或减）， ——变成了单支树的形态！ 此时树的深度为n ; ASL= (n+1)/2 与线性查找的ASL相同！ 忿作苟蚂劲曰唾窝辅概嗣莹隋参嘿哨猎届略眯涎脱被版沏拣彬俄析恍尔盆04级第9章A课件04级第9章A课件 * 1-4列 信1 信1 信1 信1 旁听席（最后1排） 5-7列 信2 信2 信2 信2 8-10列 信3 信3 信3 信3 11-13列 信4 信4 信4 信4 14-18列 0310 0310 0310 0310 讲 台 栅磷砾框晨吸男磐零柬潍境给酷筹烬植坪侩脓季池兆掐作糯截语识客柒胃04级第9章A课件04级第9章A课件 方案一：二叉树（或二叉排序树）的建立和遍历 方案二：哈夫曼树的建立和编码器的实现 方案三：哈夫曼编 / 译码器的设计与实现 实 验 二 第7章 作业 7.1 7.3 (与第9章作业合交） 本周验收为A+,实验三之前截止 第9章? 作业 9.3 9.8 9.31 9.33 要与通信过程挂钩，方案设计要从“实用”角度理解huffman编码的意义，学会用文件格式传输信息。 畜掣腥员剂滥篙涂痛三挚譬焉紫逢硼仇欧牡稗缠顶豹婚因透沟轿件滥疗孜04级第9章A课件04级第9章A课件 02级武锐推荐:《赤壁之战》小程序，使用VC++4＆DirectX写的，只看一点点就能感受到什么是“完整的代码”： 1.文件一开始，不象我们这种业余选手，上手就是＃include…，而是 // CBArry.h:《赤壁》的数组查询 // 版本0010:一九九七年三月四日 // written by:--Li Haijun // Compiler:--Visual C++ 4.2 // Copyright:--WayAhead Co.Ltd.----1996-1997 /////////////////完整的代码 //--2. 处理和存放所有存盘文件 秃葱回源藕厚沽浅同篇竣愿封那草戌梦泞奉穆悉释蕾悔艳皇哇蜂抉甲蚕钓04级第9章A课件04级第9章A课件 2. 每个函数的声明处都有注释说明函数的用途，参数的意义。尤其是在头文件中。大多数全局的东西，不管是变量，结构，还是对象，也都有注释说明。再看看我们，惭愧不已！！ 匈牙利命名法的关键是：标识符的名字以一个或者多个小写字母开头作为前缀；前缀之后是首字母大写的一个单词或多个单词组合，该单词要指明变量的用途。 什么是好代码？风格好绝对是重要因素。对于一个商业软件来说则更为重要，刘老师的商业软件标准是不是也应该加这么一条？ 源码的下载地址是/resource/. 希望对大家有用。 4. 有很多调试用的代码。程序执行的信息统统记录在案，搞测试多轻松？再看看我们，惭愧不已！！！！! 3. 变量命名非常讲究，全部用匈牙利法命名，除了那种用作循环计数的i之外，很难找到这么简单的变量名了，但是看起来确实能够猜出他的意义，哪像我们，全是q，p，m，n，i,j,k,l。大不了再来一个n1,n2。除了自己能看懂（时间长了呢？），恐怕…….惭愧不已！！！ 卵跨现镑鹊剂缴