文档介绍：数据结构与算法“高级数据结构”教学设计

北京大学信息科学技术学院张铭

1. 高级数据结构在课程中的定位和前测知识点
为满足一些特定需要,人们可以对简单数据结构进行扩展,实现一些功能更为强大、具有
更多操作的高级数据结构。本章可以作为《数据结构与算法》课程的提高内容,根据学生的
接受程度选择讲授的深浅。
高级数据结构一章主要介绍了几种常用的高级线性结构和高级树结构。多维数组是向量
的扩充。广义表在文本处理、人工智能和计算机图形学等领域都得到了广泛的应用。Trie 和
Patricia 树结构被广泛地运用于字符串存储,存储和检索字符串都有很高的效率。改进二叉
搜索树与普通二叉树相比能够提高检索效率,在现实中有广泛的应用。
希望学生能够掌握多维数组和广义表的使用,了解常用存储管理技术,理解 Trie 结构
和 Patricia 树结构、掌握改进的二叉搜索树的原理和使用。
前测知识点要求如下,可以根据需要给学生补充
(1)广义表的操作;
(2)伙伴系统地址的计算;
(3)动态规划算法;
(4)Huffman 树的原理;

(1)掌握高级线性结构的概念;
(2)掌握多维数组的概念、存储表示、基本运算;
(3)掌握广义表的概念、存储表示、基本运算;
(4)掌握存储管理技术;
(5)理解 Trie 树结构和 Patricia 树结构原理及其应用;
(6)理解二叉搜索树的几个变体,掌握平衡的二叉搜索树的几种变换;

3. 知识点和学时分配
理论授课4学时。
以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学
生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉
猎面。对于非计算机类的学生,可以不讲高级树结构。
各知识点建议授课时间如下:
多维数组小时
广义表 1 小时
存储管理技术小时
Trie 结构和 Patricia 树 1 小时
改进的二叉搜索树 1 小时

高级数据结构重点如下:
(1)特殊矩阵和稀疏矩阵的计算
(2)广义表的存储结构和周游算法
(3)Trie 树和 Patricia 树的原理及应用
(4)平衡的二叉搜索树及其各种变换

高级数据结构难点如下:
(1) Trie 树和 Patricia 树的应用
(2) 最佳二叉搜索树的动态规划算法
(3) 平衡的二叉搜索树的各种变换

开展研究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性
能,培养学生的创新意识、创新能力。
下面是索引部分的重点和难点内容的讲授注意事项。
(1) 特殊矩阵和稀疏矩阵的计算
二维数组可以被看作是矩阵,所以它也经常被用来表示矩阵。几种比较特殊的矩阵
包括:三角矩阵、对称矩阵、对角矩阵。根据各自的矩阵结构其索引值存在一定规律。
稀疏矩阵是指矩阵中元素非零元素非常少,而且分布不规律的一种矩阵。常用十字
链表来存储稀疏矩阵。十字链表用两组链表组成。两组链表分别是行和列的指针序列。
每个结点包含它自己的行列值