数据结构与算法“检索”教学设计 北京大学信息科学技术学院张铭 1.检索在课程中的定位和前测知识点 检索是各种数据结构中必不可少的运算,也是许多计算机应用程序的核心功能。在数据 处理中,经常涉及到信息存储和信息检索,即对所存储的数据进行快速有效的检索操作 检索一章主要介绍了一些检索的基本知识,侧重于基于线性表的检索和基于散列表的 检索。基于线性表的检索介绍了顺序检索和二分检索,并简单讨论了算法中的分支策略。基 于散列表的检索是本章的重点,也是难点。散列函数和冲突解决技术是散列算法的核心 前测知识点要求如下,可以根据需要给学生补充: (1)基于数组和链表的线性表相关算法、排序算法 (2)掌握概率的基本概念,理解等概率假设; (3)集合的基本概念和相关性质。 2.学习目标 (1)理解检索的基本概念,熟练掌握各种主要检索算法; (2)能根据概率知识衡量检索算法的效率,理解各种算法的优缺点 (3)理解分治算法的思想,会设计一般的分治算法 4)重点掌握基于散列的检索算法,掌握各种散列函数、散列探查方法 (5)了解集合检索相关知识。 3.知识点和学时分配 理论授课4学时,建议安排实验10学时 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面 各知识点建议授课时间如下: 检索的基本概念0.5小时 基于线性表的检索1小时 基于集合的检索 0.5小时 散列方法 2小时 4.重点和难点 检索重点如下: (1)衡量检索算法的效率,评价各种算法的优缺点 (2)基于线性表的检索算法,即顺序检索、二分检索、分块检索: (3)二分检索与分治算法的思想 (4)基于散列的检索算法,各种散列函数、散列探查方法。 检索难点如下: (1)散列方法,包括各种散列函数以及碰撞的处理方法;
数据结构与算法“检索”教学设计 北京大学信息科学技术学院 张铭 1. 检索在课程中的定位和前测知识点 检索是各种数据结构中必不可少的运算，也是许多计算机应用程序的核心功能。在数据 处理中，经常涉及到信息存储和信息检索，即对所存储的数据进行快速有效的检索操作。 检索一章主要介绍了一些检索的基本知识，侧重于基于线性表的检索和基于散列表的 检索。基于线性表的检索介绍了顺序检索和二分检索，并简单讨论了算法中的分支策略。基 于散列表的检索是本章的重点，也是难点。散列函数和冲突解决技术是散列算法的核心。 前测知识点要求如下，可以根据需要给学生补充： （1）基于数组和链表的线性表相关算法、排序算法； （2）掌握概率的基本概念，理解等概率假设； （3）集合的基本概念和相关性质。 2．学习目标 （1）理解检索的基本概念，熟练掌握各种主要检索算法； （2）能根据概率知识衡量检索算法的效率，理解各种算法的优缺点； （3）理解分治算法的思想，会设计一般的分治算法； （4）重点掌握基于散列的检索算法，掌握各种散列函数、散列探查方法； （5）了解集合检索相关知识。 3. 知识点和学时分配 理论授课 4 学时，建议安排实验 10 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。 各知识点建议授课时间如下： 检索的基本概念 0.5 小时 基于线性表的检索 1 小时 基于集合的检索 0.5 小时 散列方法 2 小时 4．重点和难点 检索重点如下： （1）衡量检索算法的效率，评价各种算法的优缺点； （2）基于线性表的检索算法，即顺序检索、二分检索、分块检索； （3）二分检索与分治算法的思想； （4）基于散列的检索算法，各种散列函数、散列探查方法。 检索难点如下： （1）散列方法，包括各种散列函数以及碰撞的处理方法；
(2)散列在实际应用中的性能分析。 5.授课提示 开展硏究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 能,培养学生的创新意识、创新能力。 下面是检索的重点和难点内容的讲授注意事项 (1)基于线性表的检索算法 基于线性表的顺序检索、二分检索和分块检索这三种不同实现方法各有优缺点。其中, 顺序检索效率最低但限制最少,二分检索效率最高但限制多,而分块检索则介于上述二者之 间。应注意对三种检索算法的效率进行分析 在实际应用中,可根据表的具体情况进行选择,需要综合考虑检索效率、插入删除频率 (2)散列函数的设计 采用散列技术需要考虑的两个首要问题是,如何构造使结点“分布均匀”的散列函数, 以及一旦发生冲突用什么方法解决。此外,还需考虑散列表本身的组织方法。 常用的散列函数,包括除余法、乘余取整法、平方取中法、数字分析法、基数转换法 折叠法、 ELFhash字符串散列函数。讲授中着重介绍这些散列函数的基本思想以及各自的特 点,使同学们在实际使用中能够根据应用条件选取合适的散列函数。 3)散列表冲突解决策略 冲突解决技术可分为两大类,即开散列方法和闭散列方法。两者的不同之处在于:开散 列法把发生冲突的关键码存储在散列表主表之外,而闭散列把发生冲突的关键码存储在表中 另一个槽内。闭散列方法中有以下几种常见的形成探査的方法,即线性探查法、二次探查法。 讲授中应使学生理解冲突解决方法的基本原理,引导其思考其各自的效率、特点和适用 的条件。注意分析开散列方法(包括拉链法和桶式散列)和闭散列方法的空间需求和平均检 索长度,注意分析负载因子对检索效率的影响。开散列方法非常简单、易于实现,删除也极 为方便;经过精心设计的闭散列效率比开散列稳定。开散列方法的效率最好,实际系统中大 多使用开散列方法 (4)闭散列方法、散列探查方法 闭散列方法中,一旦发生冲突,发生冲突的关键码存储在散列表中的另一个槽内。根据 发生冲突时形成探查的方法不同,所得到的解决冲突的方法也不同。 本章介绍了几种常见的闭散列方法,包括线性探査、二次探査、伪随机数序列探査、爽 散列探査法。讲授中介绍各种散列方法的基本思想,注重分析各种方法的优缺点 本章还介绍了闭散列方法的不同实现方式,还介绍了闭散列的插入、检索和删除算法的 实现,分析了使用“墓碑”带给闭散列插入和删除算法性能上的改进。 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上级题,帮助学生更好地掌握检索算法的基本原理,训练学生的创新思维能 力训练、工程实践能力。 检索可以安排46道书面作业,1道综合上机实习题 通过书面练习检査学生对各种散列方法、散列函数和散列探査方法的理解。设计与学科
（2）散列在实际应用中的性能分析。 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是检索的重点和难点内容的讲授注意事项。 （1）基于线性表的检索算法 基于线性表的顺序检索、二分检索和分块检索这三种不同实现方法各有优缺点。其中， 顺序检索效率最低但限制最少，二分检索效率最高但限制多，而分块检索则介于上述二者之 间。应注意对三种检索算法的效率进行分析。 在实际应用中，可根据表的具体情况进行选择，需要综合考虑检索效率、插入删除频率 等。 （2）散列函数的设计 采用散列技术需要考虑的两个首要问题是，如何构造使结点“分布均匀”的散列函数， 以及一旦发生冲突用什么方法解决。此外，还需考虑散列表本身的组织方法。 常用的散列函数，包括除余法、乘余取整法、平方取中法、数字分析法、基数转换法、 折叠法、ELFhash 字符串散列函数。讲授中着重介绍这些散列函数的基本思想以及各自的特 点，使同学们在实际使用中能够根据应用条件选取合适的散列函数。 （3）散列表冲突解决策略 冲突解决技术可分为两大类，即开散列方法和闭散列方法。两者的不同之处在于：开散 列法把发生冲突的关键码存储在散列表主表之外，而闭散列把发生冲突的关键码存储在表中 另一个槽内。闭散列方法中有以下几种常见的形成探查的方法，即线性探查法、二次探查法。 讲授中应使学生理解冲突解决方法的基本原理，引导其思考其各自的效率、特点和适用 的条件。注意分析开散列方法（包括拉链法和桶式散列）和闭散列方法的空间需求和平均检 索长度，注意分析负载因子对检索效率的影响。开散列方法非常简单、易于实现，删除也极 为方便；经过精心设计的闭散列效率比开散列稳定。开散列方法的效率最好，实际系统中大 多使用开散列方法。 （4）闭散列方法、散列探查方法 闭散列方法中，一旦发生冲突，发生冲突的关键码存储在散列表中的另一个槽内。根据 发生冲突时形成探查的方法不同，所得到的解决冲突的方法也不同。 本章介绍了几种常见的闭散列方法，包括线性探查、二次探查、伪随机数序列探查、爽 散列探查法。讲授中介绍各种散列方法的基本思想，注重分析各种方法的优缺点。 本章还介绍了闭散列方法的不同实现方式，还介绍了闭散列的插入、检索和删除算法的 实现，分析了使用“墓碑”带给闭散列插入和删除算法性能上的改进。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上级题，帮助学生更好地掌握检索算法的基本原理，训练学生的创新思维能 力训练、工程实践能力。 检索可以安排 4-6 道书面作业，1 道综合上机实习题。 通过书面练习检查学生对各种散列方法、散列函数和散列探查方法的理解。设计与学科
前沿研究相结合的综合实习大项目进行设计型和综合型实践训练,例如使用散列方法实现对 文档(html或者tt文件)中词语的倒排索引,为课程综合实习之搜索引擎做准备 7.教学案例 基于线性表的二分检索法 算法思想如下: 将任意元素 dataList[]key与给定值K比较 有三种情况 (1)Key=K,检索成功,返回 datalist[l (2)Key>K,若有则一定排在 dataList订前 (3)Key int BinSearch(vector*>& dataList, int length, Type k) int low=l, high=length, mid while(lowgetKeyo) ∥右缩检索区间 else if(>dataList mid]->getKeyO) ∥左缩检索区间 else returm mid 成功返回位置 return0,∥检索失败,返回0 讲解算法时,注意结合动画进行讲解。例如,图1所示,以有序表(15,17,18,22, 35,51,60,88,93)为例说明用二分检索算法查找K=18的过程(这里假定表中各元素 只含关键码)。首先,取整个有序表为检索区间,这通过分别置low、high为1、9来完成。 关键码18low=1high=9 123456789 1517182235516088|93 mid 第一次:l=1,h=9,mid=s,aray5}=35>18 第二次:l=1,h=4,mid=2,aray[2]17<18 第三次:l=3,h=4,mid=3;aray[3=18=18 图1.二分检索过程分解 因区间长度大于0,取区间中间位置mid=(1+9)2=5,将mid位置上元素的关键码值 35与K=18比较。因18<35,将区间缩小为[1,4。注意此新区间与原区间[1,9的差别 仅在于上界不同,通过修改上界high=md1=5-l=4完成缩小区间的工作 由于循环终止条件未满足,重复上述过程。这时区间中点为mid=(1+4)2=2,比较结
前沿研究相结合的综合实习大项目进行设计型和综合型实践训练，例如使用散列方法实现对 文档（html 或者 txt 文件）中词语的倒排索引，为课程综合实习之搜索引擎做准备。 7．教学案例 基于线性表的二分检索法。 算法思想如下： 将任意元素 dataList[i].key 与给定值 K 比较。 有三种情况： （1）Key = K，检索成功，返回 dataList[i] （2）Key > K，若有则一定排在 dataList[i]]前 （3）Key int BinSearch (vector*>& dataList, int length, Type k){ int low=1, high=length, mid; while (lowgetKey()) high = mid-1; //右缩检索区间 else if (k>dataList[mid]->getKey()) low = mid+1; //左缩检索区间 else return mid; //成功返回位置 } return 0; //检索失败，返回 0 } 讲解算法时，注意结合动画进行讲解。例如，图 1 所示，以有序表（15，17，18，22， 35，51，60，88，93）为例说明用二分检索算法查找 K = 18 的过程（这里假定表中各元素 只含关键码）。首先，取整个有序表为检索区间，这通过分别置 low、high 为 1、9 来完成。 关键码18 low=1 high=9 35 1 2 3 4 5 6 7 8 9 15 22 51 60 88 93 low mid high 17 18 第一次：l=1, h=9, mid=5; array[5]=35>18 第二次：l=1, h=4, mid=2; array[2]=17<18 第三次：l=3, h=4, mid=3; array[3]=18＝18 图 1. 二分检索过程分解 因区间长度大于 0，取区间中间位置 mid = (1+9)/2 = 5，将 mid 位置上元素的关键码值 35 与 K = 18 比较。因 18<35，将区间缩小为[1，4]。注意此新区间与原区间[1，9]的差别 仅在于上界不同，通过修改上界 high = mid-1 = 5-1 = 4 完成缩小区间的工作。 由于循环终止条件未满足，重复上述过程。这时区间中点为 mid = (1+4)/2 = 2，比较结
果18>17表明区间应改为[3,4,这一修改由下界的修改low=mid+1=2+1=3完成。 再次进行比较时,区间中点为mid=(3+4)2=3,比较结果表明 dataList(mid]是待查 元素,检索成功,返回结果为mid=3 可以画一棵二分检索的决策树来描述检索过程,该决策树还可以用于分析检索性能,如 图2所示(注意:圆圈外标注的是元素下标),可以看出这是一棵BST(二叉搜索树)。在搜 索18时,正好走了一条从根结点到与该给定值对应结点的路径,所以BST中关键码与给定 值的比较次数正好等于该值对应结点所在的层数加1,因此,二分检索到要求元素所需的比 较次数最多不超过这棵树的层数加1(即BST的高度)。请注意,由对同一长度的有序数组 采用相同的二分检索算法,所对应的决策树的形状是固定的。也就是说,不管数组中元素的 数值是什么,数组下标位置的BST保持不变。 介绍了二分检索的基本原理,需要二分检索进行性能分析。 最大检索长度og2(n+1)1 失败的检索长度是 或og2(n+D7 Llog2(n+1)」 成功的平均检索长度为 ASL=1(;21-1) 图2二分检索的决策树 log?(n+D) g,(n+1) (n>50) 8.总结 检索是各种数据结构中必不可少的运算,也是许多计算机应用程序的核心功能。在数据 处理中,经常涉及到信息存储和信息检索,即对存储的数据进行快速有效的检索操作 除了要求学生对基于线性表和集合的检索方法,散列表和散列方法、各种散列函数和散 列探査方法的基本思想的理解之外,还需提醒学生注意实际应用,在实际应用中分析检索效 率。例如,可以根据应用规模的大小、应用的特点(如是否是范围检索)、应用的时间和空 间限制等,权衡检索的算法复杂度与效率,选择最合适的数据结构和检索算法。 参考文献: 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkuedu.cn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3
果 18>17 表明区间应改为[3，4]，这一修改由下界的修改 low = mid+1 = 2+1 = 3 完成。 再次进行比较时，区间中点为 mid = (3+4)/2 = 3，比较结果表明 dataList[mid]正是待查 元素，检索成功，返回结果为 mid = 3。 可以画一棵二分检索的决策树来描述检索过程，该决策树还可以用于分析检索性能，如 图 2 所示(注意：圆圈外标注的是元素下标) ，可以看出这是一棵 BST（二叉搜索树）。在搜 索 18 时，正好走了一条从根结点到与该给定值对应结点的路径，所以 BST 中关键码与给定 值的比较次数正好等于该值对应结点所在的层数加 1，因此，二分检索到要求元素所需的比 较次数最多不超过这棵树的层数加 1（即 BST 的高度）。请注意，由对同一长度的有序数组， 采用相同的二分检索算法，所对应的决策树的形状是固定的。也就是说，不管数组中元素的 数值是什么，数组下标位置的 BST 保持不变。 介绍了二分检索的基本原理，需要二分检索进行性能分析。 最大检索长度 失败的检索长度是 或 log（2 n 1） log（2 n 1） log（2 n 1） 成功的平均检索长度为： (n > 50) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n 8．总结 检索是各种数据结构中必不可少的运算，也是许多计算机应用程序的核心功能。在数据 处理中，经常涉及到信息存储和信息检索，即对存储的数据进行快速有效的检索操作。 除了要求学生对基于线性表和集合的检索方法，散列表和散列方法、各种散列函数和散 列探查方法的基本思想的理解之外，还需提醒学生注意实际应用，在实际应用中分析检索效 率。例如，可以根据应用规模的大小、应用的特点（如是否是范围检索）、应用的时间和空 间限制等，权衡检索的算法复杂度与效率，选择最合适的数据结构和检索算法。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 15 18 22 51 7 8 9 2 1 3 4 88 60 93 35 17 5 6 图2 二分检索的决策树
5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91
