高级数据结构重点如下 (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) 最佳二叉搜索树的动态规划算法 最佳二叉搜索树是平均检索长度最短的二叉树。介绍最佳二叉搜索树的构造可以深