数据结构与算法“高级数据结构”教学设计 北京大学信息科学技术学院张铭 1.高级数据结构在课程中的定位和前测知识点 为满足一些特定需要,人们可以对简单数据结构进行扩展,实现一些功能更为强大、具有 更多操作的高级数据结构。本章可以作为《数据结构与算法》课程的提高内容,根据学生的 接受程度选择讲授的深浅。 高级数据结构一章主要介绍了几种常用的高级线性结构和高级树结构。多维数组是向量 的扩充。广义表在文本处理、人工智能和计算机图形学等领域都得到了广泛的应用。Trie和 Patricia树结构被广泛地运用于字符串存储,存储和检索字符串都有很高的效率。改进二叉 搜索树与普通二叉树相比能够提高检索效率,在现实中有广泛的应用。 希望学生能够掌握多维数组和广义表的使用,了解常用存储管理技术,理解Trie结构 和 Patricia树结构、掌握改进的二叉搜索树的原理和使用 前测知识点要求如下,可以根据需要给学生补充 (1)广义表的操作 (2)伙伴系统地址的计算: (3)动态规划算法; (4) Huffman树的原理 2.学习目标 (1)掌握高级线性结构的概念 (2)掌握多维数组的概念、存储表示、基本运算 (3)掌握广义表的概念、存储表示、基本运算; (4)掌握存储管理技术; (5)理解Trie树结构和 Patricia树结构原理及其应用; (6)理解二叉搜索树的几个变体,掌握平衡的二叉搜索树的几种变换; 3.知识点和学时分配 理论授课4学时。 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面。对于非计算机类的学生,可以不讲高级树结构 各知识点建议授课时间如下 多维数组 0.5小时 广义表 1小时 存储管理技术 0.5小时 Trie结构和 Patricia树1小时 改进的二叉搜索树 4.重点和难点
数据结构与算法“高级数据结构”教学设计 北京大学信息科学技术学院 张铭 1. 高级数据结构在课程中的定位和前测知识点 为满足一些特定需要,人们可以对简单数据结构进行扩展,实现一些功能更为强大、具有 更多操作的高级数据结构。本章可以作为《数据结构与算法》课程的提高内容，根据学生的 接受程度选择讲授的深浅。 高级数据结构一章主要介绍了几种常用的高级线性结构和高级树结构。多维数组是向量 的扩充。广义表在文本处理、人工智能和计算机图形学等领域都得到了广泛的应用。Trie 和 Patricia 树结构被广泛地运用于字符串存储，存储和检索字符串都有很高的效率。改进二叉 搜索树与普通二叉树相比能够提高检索效率，在现实中有广泛的应用。 希望学生能够掌握多维数组和广义表的使用，了解常用存储管理技术，理解 Trie 结构 和 Patricia 树结构、掌握改进的二叉搜索树的原理和使用。 前测知识点要求如下，可以根据需要给学生补充 （1）广义表的操作； （2）伙伴系统地址的计算； （3）动态规划算法； （4）Huffman 树的原理； 2．学习目标 （1）掌握高级线性结构的概念； （2）掌握多维数组的概念、存储表示、基本运算； （3）掌握广义表的概念、存储表示、基本运算； （4）掌握存储管理技术； （5）理解 Trie 树结构和 Patricia 树结构原理及其应用； （6）理解二叉搜索树的几个变体，掌握平衡的二叉搜索树的几种变换； 3. 知识点和学时分配 理论授课４学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。对于非计算机类的学生，可以不讲高级树结构。 各知识点建议授课时间如下： 多维数组 0.5 小时 广义表 1 小时 存储管理技术 0.5 小时 Trie 结构和 Patricia 树 1 小时 改进的二叉搜索树 1 小时 4．重点和难点
高级数据结构重点如下 (1)特殊矩阵和稀疏矩阵的计算 (2)广义表的存储结构和周游算法 (3)Tre树和 Patricia树的原理及应用 (4)平衡的二叉搜索树及其各种变换 高级数据结构难点如下 (1)Tie树和 Patricia树的应用 (2)最佳二叉搜索树的动态规划算法 (3)平衡的二叉搜索树的各种变换 5.授课提示 开展研究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 能,培养学生的创新意识、创新能力 下面是索引部分的重点和难点内容的讲授注意事项。 (1)特殊矩阵和稀疏矩阵的计算 维数组可以被看作是矩阵,所以它也经常被用来表示矩阵。几种比较特殊的矩阵 包括:三角矩阵、对称矩阵、对角矩阵。根据各自的矩阵结构其索引值存在一定规律。 稀疏矩阵是指矩阵中元素非零元素非常少,而且分布不规律的一种矩阵。常用十字 链表来存储稀疏矩阵。十字链表用两组链表组成。两组链表分别是行和列的指针序列。 每个结点包含它自己的行列值和指向同行下一个元素、同列下一个元素的两个指针。稀 疏矩阵的运算包括经典的矩阵乘法 稀疏矩阵可以结合矩阵图像向学生讲述,使学生更容易理解。十字链表的建立、添 加、删除可以配合代码解释。稀疏矩阵乘法的实现和复杂度计算也需要向学生介绍 (2)广义表的存储结构和周游算法 广义表是线性表的一种推广,可以采用数组存储或者链表存储。分别介绍没有头结 点和带头结点的广义表的插入、删除、搜索算法。不带头结点的广义表在删除结点时会 出现问题。添加头结点后可以简化插入、删除算法。 广义表周游相当于深度优先周游。对表头结点设置mak标记来防止进入循环链中 无法跳出。周游结束后要将mark设置为未访问。 (3)Trie树和 Patricia树的原理及应用 Trie树和 Patricia树用于存储字符串,使得检索效率大大提高。Trie结构广泛应用 于信息检索、大规模英文词典中。 Patricia是Trie结构的变体。 Patricia不是对关键码大 小范围的划分,而是根据关键码每一个二进制位的编码来划分。 Patricia结构是一颗满 二叉树,一次检索不会用超过关键码位数的比较。 PatriciaTrie是一种比较好的中文字典 组织方式。 这两种结构或者其变体在现实中都有广泛应用。可以介绍很多实际的例子。激发学 生的兴趣,让学生理解更深刻 (4)最佳二叉搜索树的动态规划算法 最佳二叉搜索树是平均检索长度最短的二叉树。介绍最佳二叉搜索树的构造可以深
高级数据结构重点如下： （1）特殊矩阵和稀疏矩阵的计算 （2）广义表的存储结构和周游算法 （3）Trie 树和 Patricia 树的原理及应用 （4）平衡的二叉搜索树及其各种变换 高级数据结构难点如下： （1） Trie 树和 Patricia 树的应用 （2） 最佳二叉搜索树的动态规划算法 （3） 平衡的二叉搜索树的各种变换 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是索引部分的重点和难点内容的讲授注意事项。 （1） 特殊矩阵和稀疏矩阵的计算 二维数组可以被看作是矩阵，所以它也经常被用来表示矩阵。几种比较特殊的矩阵 包括：三角矩阵、对称矩阵、对角矩阵。根据各自的矩阵结构其索引值存在一定规律。 稀疏矩阵是指矩阵中元素非零元素非常少，而且分布不规律的一种矩阵。常用十字 链表来存储稀疏矩阵。十字链表用两组链表组成。两组链表分别是行和列的指针序列。 每个结点包含它自己的行列值和指向同行下一个元素、同列下一个元素的两个指针。稀 疏矩阵的运算包括经典的矩阵乘法。 稀疏矩阵可以结合矩阵图像向学生讲述，使学生更容易理解。十字链表的建立、添 加、删除可以配合代码解释。稀疏矩阵乘法的实现和复杂度计算也需要向学生介绍。 （2） 广义表的存储结构和周游算法 广义表是线性表的一种推广，可以采用数组存储或者链表存储。分别介绍没有头结 点和带头结点的广义表的插入、删除、搜索算法。不带头结点的广义表在删除结点时会 出现问题。添加头结点后可以简化插入、删除算法。 广义表周游相当于深度优先周游。对表头结点设置 mark 标记来防止进入循环链中 无法跳出。周游结束后要将 mark 设置为未访问。 （3） Trie 树和 Patricia 树的原理及应用 Trie 树和 Patricia 树用于存储字符串，使得检索效率大大提高。Trie 结构广泛应用 于信息检索、大规模英文词典中。Patricia 是 Trie 结构的变体。Patricia 不是对关键码大 小范围的划分，而是根据关键码每一个二进制位的编码来划分。Patricia 结构是一颗满 二叉树，一次检索不会用超过关键码位数的比较。PatriciaTrie 是一种比较好的中文字典 组织方式。 这两种结构或者其变体在现实中都有广泛应用。可以介绍很多实际的例子。激发学 生的兴趣，让学生理解更深刻。 (4) 最佳二叉搜索树的动态规划算法 最佳二叉搜索树是平均检索长度最短的二叉树。介绍最佳二叉搜索树的构造可以深
化对动归算法的理解。同时可以介绍动态规划的算法复杂度分析。 (4)平衡二叉树及其各种变换 AVL树是一种平衡的二叉搜索树,适用于组织较小的、内存中的目录。为了维护 AVL树的平衡,在插入和删除结点时要进行旋转。旋转的方法比较复杂,很多细节容 易被忽略,应该结合动画进行讲解。对AVL树的效率和高度进行计算。 伸展树在搜索过程中自动调整结构,但是不能保证树的高度。伸展树的旋转分为: 单旋转、一字形旋转和之字形旋转。旋转的目的是使访问最频繁的结点靠近树结构的根, 从而减少访问代价。同样需要结合动画进行讲解。 可以介绍一些实际的例子来体现AVL树和伸展树各自的特点和用途 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上级题,帮助学生更好地掌握排序算法的基本原理,训练学生的创新思维能 力训练、工程实践能力 高级数据结构可以安排46道书面作业。安排一次习题讲评。 本章内容适合布置小型综合设计型实习题,例如利用广义表、稀疏矩阵等技术,结合字 符串出来技术,判断两个源程序的相似度。 7.教学案例 半伸展(semi- splaying)树是伸展树的变体,它对于同构的“一字型'(zig-zig型)的情况, 类似于AVL树的LL、RR型那样处理。下图比较了半伸展和全伸展的在同构的“一字 型(zg-zg型)情况处理的区别。下一轮的伸展,当前结点上移到父结点,父结点位置开始 旋转。也就是说半伸展不需要把检索结点移到根 普通 字旋转△ △ 半伸展 一字旋转 △AA△ A 下一次旋转从y开始,而不从x开始 8.总结 高级数据结构是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践 能力的重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用。可以组织学生搜集高级数 据结构在实际中的应用实例,进行讨论。比如广义表在LSP语言中的运用等
化对动归算法的理解。同时可以介绍动态规划的算法复杂度分析。 (4)平衡二叉树及其各种变换 AVL 树是一种平衡的二叉搜索树，适用于组织较小的、内存中的目录。为了维护 AVL 树的平衡，在插入和删除结点时要进行旋转。旋转的方法比较复杂，很多细节容 易被忽略，应该结合动画进行讲解。对 AVL 树的效率和高度进行计算。 伸展树在搜索过程中自动调整结构，但是不能保证树的高度。伸展树的旋转分为： 单旋转、一字形旋转和之字形旋转。旋转的目的是使访问最频繁的结点靠近树结构的根， 从而减少访问代价。同样需要结合动画进行讲解。 可以介绍一些实际的例子来体现 AVL 树和伸展树各自的特点和用途。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上级题，帮助学生更好地掌握排序算法的基本原理，训练学生的创新思维能 力训练、工程实践能力。 高级数据结构可以安排 4~6 道书面作业。安排一次习题讲评。 本章内容适合布置小型综合设计型实习题，例如利用广义表、稀疏矩阵等技术，结合字 符串出来技术，判断两个源程序的相似度。 7. 教学案例 半伸展（semi-splaying）树是伸展树的变体，它对于同构的“一字型”(zig-zig 型)的情况， 类似于 AVL 树的 LL、RR 型那样处理。下图比较了半伸展和全伸展的在同构的“一字 型”(zig-zig 型)情况处理的区别。下一轮的伸展，当前结点上移到父结点，父结点位置开始 旋转。也就是说半伸展不需要把检索结点移到根。 z y x A B C D y z C D 半伸展 ==> 一字旋转 x A B z y x A B C D y z C D B A == > 普通 一字旋转 * * * * 下一次旋转从y开始，而不从x开始 x ８．总结 高级数据结构是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践 能力的重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用。可以组织学生搜集高级数 据结构在实际中的应用实例，进行讨论。比如广义表在 LISP 语言中的运用等
参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材。 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkuedu.cn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91