In-Depth Study of Data Structures and Algorithms

学习了基本的数据结构后，我们已经可以用程序来解决现实中的一些问题了。但是，怎样提升程序在运行效率呢？如何快速地把图书按序号从小到大整理好？如何通过一个ID编号在数据库中高效地查找相对应的信息？如何迅速找到所有内容中含有"数据结构"的文档？《高级数据结构与算法》将通过使用高级的数据结构和高效的算法，让你学会如何解决这些对运行时间要求比较严格的问题。高级数据结构和算法能够根据实际情况，满足一些复杂问题对数据规模、运行时间的要求，帮助我们更有效地解决问题。当我们面对实际问题的时候，高级数据结构和算法让我们有更广泛的空间，选择出与问题本身最为契合的数据结构，并利用相关算法来提升运行效率。完成这门课之时，你将掌握多维数组、广义表、Trie树、AVL树、伸展树等高级数据结构，并结合内排序、外排序、检索、索引有关的算法，高效地解决现实生活中一些比较复杂的应用问题。合理使用这些高级数据结构和相关算法是程序运行效率的关键因素，学好这门课会让你在之后的计算机专业课程以及项目设计中更得心应手，同时也将让你站在更高的角度去理解问题、设计程序。

生活中，排序操作无处不在，列队出操的时候，需要让同学们从矮到高依次站好，举行运动会的时候，会把每位运动员的成绩从高到低排序。在计算机的存储结构中，分为内存和外存，前者相对后者来说速度快、容量小，因此，当整个排序过程中所有的记录都可以直接放入内存中时，我们称之为内排序。可以按照什么策略来进行排序？每种排序算法的时间代价是多少？这一模块中，你将会学到三种类型的排序算法：插入排序、选择排序和交换排序，并了解到各个算法的稳定性和时间代价。重点：排序问题的基本概念，时间和空间复杂度分析（比较次数和移动次数，一个swap操作是3次移动）；直接插入排序、Shell排序、直接选择排序、堆排序、冒泡排序、快速排序的实现。难点：快速排序的实现及其优化、时间复杂度分析。

有些算法时间代价太大？有的时候可以根据数据本身的特性，或是排序的特殊要求，调整排序的策略。例如，现在要将一叠试卷按得分从高到低排序，假设老师只给了"合格"、"不合格"两种分数，相信你立马就能整理好。原因就在于你并不需要再去整理所有"合格"试卷的相对次序了。本模块中，你将会学习到归并排序、分配排序和索引排序，并了解它们各自的基本思想、适用范围和时间代价。重点：归并排序及其优化、桶式排序、静态/链式基数排序的实现、地址索引排序的结果整理。难点：归并排序的实现、排序问题的下限的决策树分析方法（了解即可）。

当待处理的数据对象非常多，以至于内存容纳不下所有数据时，如果我们仍旧按照内排序的算法进行排序，大量的I/O会使得时间代价非常大，那应该怎么办呢？一般我们需要将数据文件分成若干段，每次将一段放入内存中进行排序，得到一系列的顺串，最后通过逐趟归并顺串，形成对整个数据文件的排序文件。在这一模块中，你将学到如何让初始文件形成尽可能长的初始顺串、如何通过增加每次参与归并的顺串个数，来减少对数据扫描的趟数，从而减少访问外存次数提高排序效率。重点：置换选择算法、二路归并算法、赢者树算法的基本思想和实现。难点：败者树的类定义及其成员函数的实现。

检索是一种常见的、也是必不可少的运算。在数据量很小的时候，顺序检索就可以快速找到目标，但当数据量很大的时候，顺序检索的效率就很差了。那如何在这种情况下进行检索呢？生活中，比如我们要查一个英文单词在字典的哪一页，我们可以根据拼写，判断这个单词是在当前页之前还是之后；又比如我们也可以问一个"天才"，他能直接告诉我们那个词在第几页。那如何找到、创造这样的"天才"呢？通过本模块的学习，除了检索的基本知识、基于线性表的检索方法、对集合的检索外，你还会学习到一种可以根据关键码值直接找到记录存储地址的方法——基于散列表的检索。重点：检索最重要的度量是平均检索长度ASL。检索效率的分析需要注意成功检索和失败检索两种情况。散列函数的选择、冲突和聚集的解决方案（开散列、闭散列），散列方法的实现及其效率分析。难点：负载因子、散列函数的选择、闭散列方法中的双散列。

索引相当于图书馆的卡片目录，有了卡片目录之后，就不需要在整个书库中搜索某一本书，而可以在卡片目录中检索到该书的位置。有了索引技术之后，我们可以高效地进行检索、插入、删除等操作。如何来实现索引？如何动态地调整索引？如何提高在索引中的检索效率？通过这一模块的学习，你会了解静态索引、倒排索引的相关知识，B树B+树是如何维护的，红黑树又是通过怎样的调整，提高增删和检索效率的。重点：要充分理解索引的意义。也就是（key, pointer）。基于属性的倒排、对正文文件的倒排、B/B+树的概念及相关操作、红黑树的定义和数学性质、红黑树的插入/删除操作。难点：注意多级索引的建立是动态的，在整个建索引的过程中都要保持结构，并且保持性能。B/B+树要注意阶（子结点数）和关键码数目的限制，另外要注意插入时候的分离，删除时候的借关键码、合并结点。B树的隐含指针（指向key本身在外部主文件中的地址）。红黑树插入算法首先是采用BST的方法把结点插入到位，然后注意调整，尤其是"红红"冲突的解决。

生活中，很多事物是有层次结构关系的，如果只是用线性表之类的简单数据结构来描述，就会丢失一些重要的信息。另一方面，为了支持动态数据结构，操作系统需要对内存进行动态地分配和回收，但也因此会产生如"碎片问题"、"内存泄露"等问题。如何利用高级数据结构来描述实际问题？如何实现相应的高级数据结构？如何管理内存分配，使内存利用率更高？通过本模块的学习，你将会了解多维数组、广义表这两个高级数据结构的实现，以及多种内存动态分配和回收的技术。重点：特殊矩阵和稀疏矩阵的计算，了解索引下标的规律（例如，特殊矩阵多维到一维下标的相互映射）。广义表的存储结构可以看成是树和图结构的综合，理解和运用广义表的 head(), tail()两个函数。内存管理系统可以看成线性结构的应用。难点：稀疏矩阵的十字链表存储有很多应用。广义表的结构和遍历，注意广义表的线性表顺序结构、树层次结构、图mark标记的结合

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

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