1.1 引言

在计算机科学中，数据结构与算法是计算机科学与工程的基础性学科，是开发高效计算机程序以解决各领域应用问题的核心。数据结构与算法是计算机学科中最基础的课程，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。这门课程的内容不仅是一般程序设计（特别是非数值程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。

由于早期所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算显得越来越重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。

【例1.1】学生信息检索系统。

当我们需要查询某个学生的有关情况时；或者想查询某个专业或年级的学生的有关情况时，只要建立了相关的数据结构，按照某种算法编写相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表（见图1.1（a））以及分别按姓名（见图1.1（b）），专业（见图1.1（c）），年级（见图1.1（d））顺序排列的索引表。由这4 张表构成的文件便是学生信息检索的数学模型，计算机的主要操作就是按照某个特定要求（如给定姓名）对学生信息文件进行查询。

诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在一种简单的线性关系，这类数学模型可称为线性的数据结构。

【例1.2】人机对弈问题。

人机对弈是一个古老的人工智能问题，其解题思路是将对弈的策略事先存入计算机，包括对弈过程中所有可能出现的情况和响应的对策。在决定对策时，根据当前局势发展的趋势作出最有利的选择。因此计算机操作的对象（数据元素）是对弈过程中的每一步棋盘状态（格局），元素之间的关系由比赛规则决定。通常这个关系不是线性的，从一个格局可能派生出多个格局，因此常用树形结构来表示，如图1.2所示。

【例1.3】教学计划编排问题。

一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称为图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。

由以上3 个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作。

学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来，并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。 3keLXYmg9/2y7J28wrqDhg6QNoV0WDxrdWk/3iisOIK87f4Q9U9zuF+ckrX3xXLO