高级数据结构与算法

检索是一种常见的、也是必不可少的运算。在数据量很小的时候，顺序检索就可以快速找到目标，但当数据量很大的时候，顺序检索的效率就很差了。那如何在这种情况下进行检索呢？生活中，比如我们要查一个英文单词在字典的哪一页，我们可以根据拼写，判断这个单词是在当前页之前还是之后；又比如我们也可以问一个“天才”，他能直接告诉我们那个词在第几页。那如何找到、创造这样的“天才”呢？通过本模块的学习，除了检索的基本知识、基于线性表的检索方法、对集合的检索外，你还会学习到一种可以根据关键码值直接找到记录存储地址的方法——基于散列表的检索。

重点：检索最重要的度量是平均检索长度ASL。检索效率的分析需要注意成功检索和失败检索两种情况。散列函数的选择、冲突和聚集的解决方案（开散列、闭散列），散列方法的实现及其效率分析。 难点：负载因子、散列函数的选择、闭散列方法中的双散列。

索引相当于图书馆的卡片目录，有了卡片目录之后，就不需要在整个书库中搜索某一本书，而可以在卡片目录中检索到该书的位置。有了索引技术之后，我们可以高效地进行检索、插入、删除等操作。如何来实现索引？如何动态地调整索引？如何提高在索引中的检索效率？通过这一模块的学习，你会了解静态索引、倒排索引的相关知识，B树B+树是如何维护的，红黑树又是通过怎样的调整，提高增删和检索效率的。

重点：要充分理解索引的意义。也就是（key, pointer）。基于属性的倒排、对正文文件的倒排、B/B+树的概念及相关操作、红黑树的定义和数学性质、红黑树的插入/删除操作。 难点：注意多级索引的建立是动态的，在整个建索引的过程中都要保持结构，并且保持性能。B/B+树要注意阶（子结点数）和关键码数目的限制，另外要注意插入时候的分离，删除时候的借关键码、合并结点。B树的隐含指针（指向key本身在外部主文件中的地址）。红黑树插入算法首先是采用BST的方法把结点插入到位，然后注意调整，尤其是“红红”冲突的解决。

生活中，很多事物是有层次结构关系的，如果只是用线性表之类的简单数据结构来描述，就会丢失一些重要的信息。另一方面，为了支持动态数据结构，操作系统需要对内存进行动态地分配和回收，但也因此会产生如“碎片问题”、“内存泄露”等问题。如何利用高级数据结构来描述实际问题？如何实现相应的高级数据结构？如何管理内存分配，使内存利用率更高？通过本模块的学习，你将会了解多维数组、广义表这两个高级数据结构的实现，以及多种内存动态分配和回收的技术。

重点：特殊矩阵和稀疏矩阵的计算，了解索引下标的规律（例如，特殊矩阵多维到一维下标的相互映射）。广义表的存储结构可以看成是树和图结构的综合，理解和运用广义表的 head(), tail()两个函数。内存管理系统可以看成线性结构的应用。 难点：稀疏矩阵的十字链表存储有很多应用。广义表的结构和遍历，注意广义表的线性表顺序结构、树层次结构、图mark标记的结合

你是不是发现，二叉搜索树的运行效率并没有想象中那么好？这是因为二叉搜索树是一种基于对象空间分解的数据结构，即关键码范围的分解是由树中的对象决定的，并受到关键码输入的影响，因此就有可能变得非常不平衡，例如退化为线性结构。那如何来改进二叉搜索树呢？在这一模块中，你将学到Trie树、AVL树、伸展树的基本思想以及他们在具体进行插入删除操作时，是如何调整树的结构以保持平衡的。重点：Trie树的概念及其改进、AVL树的概念及插入删除操作、伸展树的概念及其旋转操作。

祝贺大家完成了《高级数据结构与算法》这门课的所有教学模块，只要顺利通过期末考试，你就向成为优秀的程序设计人员的梦想又迈进了一步哦！如果你同时也完成了《程序设计与算法》专项课程的其他部分，那么恭喜你，你已经由轻叩计算机世界大门的初学者，成长到了一名优秀的准程序员啦！快来通过期末考试，向我们的毕业项目出发，用实际的企业开发案例证明你的实力吧！