数据结构与算法“文件与外排序”教学设计 北京大学信息科学技术学院宋国杰 1在课程中的定位和前测知识点 作为对内排序的延伸,外排序指将排序的对象从内存空间转移到外存空间, 通过内存与外存之间的数据交换以及文件块的内排序,完成文件的排序。外排序 是实际系统中频繁采用的运算,具有重要地位。 外排序学习的重点是让学生掌握尽可能少IO操作完成文件排序过程的技 能。介绍了外存中文件的组织方式和对大量记录进行排序的基本算法。具体包括 置换选择排序和二路外排序。 前测知识点要求如下,可以根据需要给学生补充 1)内排序; 2)排序树的概念; 3)堆的概念; ) Huffman树的概念。 2学习目标 1)了解文件结构及其组织管理的基本知识 2)理解外排序的特点,熟练掌握置换排序、二路外排序的过程 3知识点和学时分配 理论授课2学时,实验课1学时。 主要知识点包括: 1)主存储器和外存储器的特点 2)文件的组织形式 3)外排序思想 4)置换选择排序
数据结构与算法“文件与外排序”教学设计 北京大学信息科学技术学院 宋国杰 1 在课程中的定位和前测知识点 作为对内排序的延伸，外排序指将排序的对象从内存空间转移到外存空间， 通过内存与外存之间的数据交换以及文件块的内排序，完成文件的排序。外排序 是实际系统中频繁采用的运算，具有重要地位。 外排序学习的重点是让学生掌握尽可能少 I/O 操作完成文件排序过程的技 能。介绍了外存中文件的组织方式和对大量记录进行排序的基本算法。具体包括 置换选择排序和二路外排序。 前测知识点要求如下，可以根据需要给学生补充 1) 内排序； 2) 排序树的概念； 3) 堆的概念； 4) Huffman 树的概念。 2 学习目标 1) 了解文件结构及其组织管理的基本知识； 2) 理解外排序的特点，熟练掌握置换排序、二路外排序的过程。 3 知识点和学时分配 理论授课 2 学时，实验课 1 学时。 主要知识点包括： 1) 主存储器和外存储器的特点 2) 文件的组织形式 3) 外排序思想 4) 置换选择排序
5)二路外排序 6)选择树(贏者树和败者树 4重点和难点 重点和难点主要包括: 1)置换排序和多路归并排序的特点; 2)多路平衡归并等外排序方法及败者树构造方法; 3)最佳归并树的建立方法。 5授课提示 理解文件结构及其管理方法,把握外排序的基本过程及优化技巧,在实践中 进行应用。 在讲授重点和难点内容的过程中,需要重点关注的有 1)置换排序 置换选择排序的核心思想是利用最小值堆(或最大值堆)对数据进行处理。 每输出一个最小值(或最大值),就从缓冲区中读入下一个数。 置换选择算法的效果:如果堆的大小是M,一个顺串的最小长度就是M个 记录,至少原来在堆中的那些记录将成为顺串的一部分。最好的情况下,例如输 入已经被排序,有可能一次就把整个文件生成为一个顺串 讲解过程除了讲解清楚基本排序过程外,还要帮助分析置换排序的性能。 2)多路归并排序 基本原理:把多个顺串加以合并成为一个顺串,即形成一个已排序的文件。 在K路归并中,最直接的方法就是作K-1次比较来找出所要的记录,但这样 做花的代价较大,采用选择树的方法来实现K路归并。选择树是完全二叉树, 有两种类型:贏者树和败者树 (1)赢者树 在利用选择树进行归并时,将两个子女结点中的赢者(关键码值较小者)上 升到父结点,称这种选择树为赢者树。因此,根结点是树中的最终赢者的索引, 即为下一个要输出的记录结点
5) 二路外排序 6) 选择树（赢者树和败者树） 4 重点和难点 重点和难点主要包括： 1) 置换排序和多路归并排序的特点； 2) 多路平衡归并等外排序方法及败者树构造方法； 3) 最佳归并树的建立方法。 5 授课提示 理解文件结构及其管理方法，把握外排序的基本过程及优化技巧，在实践中 进行应用。 在讲授重点和难点内容的过程中，需要重点关注的有： 1) 置换排序 置换选择排序的核心思想是利用最小值堆（或最大值堆）对数据进行处理。 每输出一个最小值（或最大值），就从缓冲区中读入下一个数。 置换选择算法的效果：如果堆的大小是 M，一个顺串的最小长度就是 M 个 记录，至少原来在堆中的那些记录将成为顺串的一部分。最好的情况下，例如输 入已经被排序，有可能一次就把整个文件生成为一个顺串。 讲解过程除了讲解清楚基本排序过程外，还要帮助分析置换排序的性能。 2) 多路归并排序 基本原理：把多个顺串加以合并成为一个顺串，即形成一个已排序的文件。 在 K 路归并中，最直接的方法就是作 K-1 次比较来找出所要的记录，但这样 做花的代价较大，采用选择树的方法来实现 K 路归并。选择树是完全二叉树， 有两种类型：赢者树和败者树。 （1）赢者树 在利用选择树进行归并时，将两个子女结点中的赢者（关键码值较小者）上 升到父结点，称这种选择树为赢者树。因此，根结点是树中的最终赢者的索引， 即为下一个要输出的记录结点
(2)败者树 在利用选择树进行归并时,将两个子女结点中的败者(关键码值较大者)上 升到父结点,同时另加进一个结点以代表比赛的全局获胜者的索引值,称这种选 择树为败者树。 败者树比赛过程:将新进入树的结点与其父结点进行比赛把败者存放在父结 点中而把胜者再与上一级的父结点进行比赛这样的比赛不断进行,直到根结点 处。并将全局获胜者的索引值存放在添加结点中。 在授课过程中的难点是,如何借助完全二叉树完成赢者树和败者树的构造。 3)最佳归并 最佳归并树:如果在进行多路归并的时候,各初始顺串的长度不同,对外存 扫描的次数,即执行时间会产生影响。把所有初始顺串的块数作为树的叶结点的 权值,如果是K路归并则建立起一棵K-叉 Huffman树。这样的一棵 Huffman树 就是最佳归并树。通过最佳归并树进行多路归并可以使对外存的ⅣO降到最少 提高归并执行效率。 授课过程中,举例讲解最佳归并树的构造方法和构造过程。 6课后练习和实习 课后练习重点是置换排序、二路归并排序以及最佳归并树的构造。 可以安排2道综合上机实习题。安排1次习题讲评 7总结 外部排序是内部排序的延伸和扩展,是实际数据管理系统中广泛应用的基本 操作。学完本章后,关键是要能够在实践中理解课程核心内容和技术难点。 参考文献: []张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材。 [2]张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3]北京大学《数据结枃与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 Ee"),http://www.jpk.pkueducn/pkujpk/course/sjjg/
（2）败者树 在利用选择树进行归并时，将两个子女结点中的败者（关键码值较大者）上 升到父结点，同时另加进一个结点以代表比赛的全局获胜者的索引值，称这种选 择树为败者树。 败者树比赛过程：将新进入树的结点与其父结点进行比赛把败者存放在父结 点中而把胜者再与上一级的父结点进行比赛这样的比赛不断进行，直到根结点 处。并将全局获胜者的索引值存放在添加结点中。 在授课过程中的难点是，如何借助完全二叉树完成赢者树和败者树的构造。 3) 最佳归并 最佳归并树：如果在进行多路归并的时候，各初始顺串的长度不同，对外存 扫描的次数，即执行时间会产生影响。把所有初始顺串的块数作为树的叶结点的 权值，如果是 K 路归并则建立起一棵 K-叉 Huffman 树。这样的一棵 Huffman 树 就是最佳归并树。通过最佳归并树进行多路归并可以使对外存的 I/O 降到最少， 提高归并执行效率。 授课过程中，举例讲解最佳归并树的构造方法和构造过程。 6 课后练习和实习 课后练习重点是置换排序、二路归并排序以及最佳归并树的构造。 可以安排 2 道综合上机实习题。安排 1 次习题讲评。 7 总结 外部排序是内部排序的延伸和扩展，是实际数据管理系统中广泛应用的基本 操作。学完本章后，关键是要能够在实践中理解课程核心内容和技术难点。 参考文献： [1] 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 [2] 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 [3] 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/
[4]蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3← [S]张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
[4] 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 [5] 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91