查找

数据结构 Time Date (4)找到,则输出其值,找不到则输出0; (5)重复上述过程,查找下一个数组元素。

源程序清单(略)

9.6 小 结

本章主要介绍了查找的基本概念以及常用的查找方法：顺序查找、折半查找、分块查找、二叉排序树以及散列表。顺序查找算法简单适用面广,对表的结构没有要求,但其平均查找长度较大,当数据很多时,查找效率很低;折半查找算法查找效率较高,但要求表结构为有序顺序表;分块查找要求索引表有序,块内无序。二叉排序树和散列表主要用于动态查找表。通过本章的学习,掌握各种查找算法,并能应用于实践中。

9.7 思 考 题

1. 对含有n个互不相同元素的集合,同时找最大元素和最小元素至少需进行多少次比较？ 2. 对给定的关键字集合,以不同的次序插入初始为空的树中,是否有可能得到同一棵二叉排序树？ 3. 为什么对有序的单链表不能进行折半查找？

9.8 习 题

1. 比较各种查找算法的特点、性能及适用情况。

2. 试分别画出在线性表 (a,b,c,d,e,f) 中查找e、f和g的折半查找过程。 3. 构造散列表的设计思想是怎样的？两个关键问题是什么？ 4. 画出以序列 {3,2,5,8,7,9,1,4,6}建立的一棵二叉排序树。

5. 设散列表的长度为11,散列函数为H(k)=k,给定的关键码序列为56,74,23,11,69,22,59,29。试画出用

线性探测法解决冲突时所构成的散列表。

9.9 实 验

1．题目

试根据全班学生的姓名,构造一个散列表,选择适当的散列函数和解决碰撞方法,设计并实现插入、删除和查找算法,统计碰撞发生的次数。(用拉链法解决碰撞时装填因子α=2,用开放定址法时α=1/2)

25

数据结构 Time Date 2．实验目的

学会构造散列表,并能解决散列表冲突问题。

3．实验要求

选择使用链表或顺序表求解问题。

Grace Murray Hopper 从1943年到1992年元旦去世，美国海军少将Grace Murray Hopper的生活与计算密不可分。1991年，由于“她在计算机程序设计语言开发方面的杰出贡献，简化了计算机技术，为广大用户打开了一扇大门”，她被授予美国国家科技奖章。 海军少将Hoppper于1906年12月9日出生在纽约市的Grace Brewster Murray家。她曾就读于Vassar大学，并从Yale大学获得了数学博士学位。之后的10年中，她在Vassar大学教授数学。 1943年，Hopper加入了美国海军，被分配到哈佛大学的军械计算项目处，担任Mark I的程序员。战争过后，她仍留在哈佛大学，担任教员，继续从事有关海军的Mark II和Mark III计算机的工作。1949年，她加入了Eckert-Mauchly Computer公司，从事有关UNIVAC I的工作。就是在这里，她对计算做出了富有传奇性的贡献，发现了第一个计算机bug，即计算机硬件的一个问题。 1952年，Hopper得到了一台能够运行的编译器，当时普遍认为计算机只能进行算术运算。虽然Hopper并不属于设计计算机语言COBOL的委员会，但她也积极参与了这种语言的设计、实现和使用。COBOL(面向商业的通用语言，Common Business-Oriented Language)是在20世纪60年代早期开发的，目前仍广泛应用于商业数据处理中。 1966年，Hopper从海军退休了，但同年即被招回，负责指导海军维护程序设计语言的一致性。就像海军将领Hyman Rickover被称为美国有核海军之父一样，海军少将Hopper是美国海军计算机化的数据自动化之母。直到1986年再次退休，她一直服务于海军数据自动化司令部，军街为海军少将。在去世时，她是Digital Equipment公司的高级顾问。 在Hopper的一生中，曾收到过来自40多所学院和大学的荣誉学位。此外，她还得到过多种荣誉，包括Data Processing Managment Association授予的第一个计算机科学年度人物奖，和Spcial Interest Group for Computer Science Education(隶属于ACM)授予的计算机科学教育贡献奖。 Hopper热爱年轻人，喜欢在学院和大学校园中进行讲座。她常常分发彩色的电线，她称之为“一毫微秒”，因为这些电线的长度是一英尺，即光速运行一毫微秒(十亿分之一秒)的距离。她对年轻人的教诲是“你掌管着一切，领导着人们。我们要极度热衷于管理，而忘记自己的领导身份。” 当被问道在她的诸多成就中，她最为自豪的是什么时，她答道“我多年来培养出的所有年轻人。” 26

数据结构 Time 教学教具 教学日期/课时 习题课 Date 课程 学时 2 班级 数据结构 06网络 多媒体课件 /2课时 教学单元 教学方法 教学目标 讲授（PPT） 对作业中常见的问题进行讲解、探讨 教学重点 教学难点 组 织 教 学 作 业 在分析问题和解决问题时易出现的错误 如何高效地学习数据结构课程 常见问题的分析与解决 进行期末复习阶段 课堂情况及 课后分析

27