Introduction to Data Structures

欢迎你学习《数据结构基础》！相信大家听说过一个著名的公式"程序 = 数据结构 + 算法"，掌握数据结构和相关算法是设计程序来解决实际问题的基础能力。如何在解决一个问题的过程中把信息抽象出来？数据管理应当以什么样的方法存储？应当使用什么算法去求解问题？所选择的算法是否高效？学习了概论内容之后，你将对数据结构和相关算法有基本的了解，掌握一些算法效率分析的基本方法。另外，本模块还补充了编程作业指南和C++面向对象知识。重点：问题求解、数据结构的基本概念（逻辑、存储、运算），抽象数据类型，算法和算法的复杂度分析。难点：问题建模，抽象数据类型的理解，算法复杂度渐进分析。

线性结构是最简单而应用最广泛的一种数据结构，在不同的场合会采取不同的存储结构和实现方法。本模块将介绍一种简单的线性结构——线性表，就是同类型的元素排成的一个线性序列，并且介绍了线性表的两种实现方法，即顺序表和链表。如何来实现顺序表和链表？什么时候应该用顺序表，什么时候链表更好？这一模块可以让你学会使用线性表及其相关的一些操作，解决一些简单问题，并考察分析时间空间上的效率，例如约瑟夫问题。

日常生活中，你会发现如果桌上有一叠盘子，大家都只会拿最上面的那一个，食堂排队的时候，你总是先找到队尾加入，而排在队首的同学打完饭之后就会离开。也就是说，有的时候你也许只需要在线性序列的一端或两端进行操作，对应的就是栈和队列这两种受限的线性表，他们是最简单的基础数据结构，应用也最广泛。栈和队列有哪些特殊的操作？栈和队列能解决什么样的问题？学习完本章之后，你就可以用栈和队列这种数据结构，来解决与"先进先出"、"先进后出"有关的实际问题了，如宽度优先搜索、表达式求值等。

生活中不仅仅只有数值或单个字符，很多情况下，由若干个字符构成的字符串能表达更明确的信息。在计算机中，字符串是如何存储的？有哪些相关操作？字符串常用的运算——模式匹配有哪些相关算法？你将会了解到字符串在计算机中的存储形式，常用的字符串操函数，以及模式匹配的一些高效的算法，并在实际问题中运用字符串处理技术。

你是不是发现，在线性表中查找一个元素每次都要遍历整个表？效率如此低下，怎么改进呢？解决方案是使用非线性的数据结构——树型结构，这一章主要介绍一种最基础而最重要的非线性结构——二叉树。二叉树有哪些性质？如何在一棵二叉树中寻找一个特定的元素？如何来实现一棵二叉树？学习完这一模块，你会对二叉树的概念，以及一些简单的相关操作有基本的了解。

你需要在一堆数据中快速查找某一个元素？你需要经常删除数据中的最大值？你需要对一些信息进行最优编码？在学习了二叉树这种数据结构之后，我们可以对二叉树附加一些限制条件，使得二叉树满足一些特殊的性质，并方便我们进行插入、删除、修改的操作，从而可以用来解决相关的实际问题。在这一模块中，你将学到二叉搜索树、堆与优先队列、Huffman树这三种最常用的特殊二叉树，了解他们的性质和实现方法。

生活中，树形结构是很多客观事物与关系的抽象模型，例如亲属关系可以形成一个族谱，公司的上下级关系可以形成一个人事表。不过这些树形结构中，父结点往往都不止一个子结点，说明二叉树的表达能力不足以表示这些常见的客观问题。本章将引入树和森林的概念，介绍树的存储结构和多种表示方法。在实际应用中，你可以根据不同的情境，使用不同存储方式的树，从而解决相关的问题。

实际生活中可以用图的形式描述的问题随处可见，例如通信网络、社交网络等。图通常用来描述一个网状关系，图的结点描述了个体的信息，结点与结点之间的边描述了个体之间的关系，边还可以有权重，描述了这种关系的强弱程度。在这一章中，除了图的存储结构、遍历方法，你还会学到图结构的实际应用，如最短路径和最小生成树这两类最常见、最经典问题的解决方法。

恭喜大家完成了《数据结构基础》这门课的所有教学模块，现在就让我们一鼓作气完成期末考试，给这段难忘的学习里程画上一个圆满的句号吧！期末考试的题目将帮助你全方位地回顾课程中的重难点，让你体会到我们一路学习过后的成长与进步。如果测试没有一次通过也不要紧，只要认真复习相应的教学视频，一定能找到答案，我们的自助平台课程鼓励你反复尝试直到取得满意的成绩，加油！如果你成功地通过了测试，那我们就相约在专项课程的下一门《高级数据结构与算法》中见咯！