1.1 从问题到程序

“数据结构”是计算机科学与技术专业的专业基础课，也是十分重要的核心课程，其主要研究内容是数据之间的逻辑关系和物理实现，即探索有利的数据组织形式及存取方式。计算机系统软件和应用软件的设计、开发要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅仅依赖几种计算机程序设计语言是不够的，还必须学习和掌握数据结构的有关知识。

在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题中抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，再编写程序并进行调试、测试，最后运行程序并得到答案（如图1.1所示）。例如，求解梁架结构中应力数学模型的线性方程组，该方程组可以使用迭代算法来求解。

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

【例1.1】 图书信息检索系统。在现代图书馆中，人们往往借助计算机图书检索系统来查找需要的图书信息；或者直接通过图书馆信息系统进行图书借阅。为此，需要将图书信息分类编排，建立合适的数据结构进行存储和管理，按照某种算法编写相关程序，实现计算机自动检索。由此，一个简单的图书信息检索系统包括一张按图书分类号和登录号顺序排列的图书信息表，以及分别按作者、出版社等顺序排列的各类索引表，如图1.2所示。由这三张表构成的文件便是图书信息检索的数学模型，计算机的主要操作便是按照用户的要求（如给定作者）通过不同的索引表对图书信息进行检索、查询。

诸如此类的还有电话自动查号系统、学生信息查询系统、仓库库存管理系统等。在这类数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系，这类数学模型是线性数据结构的。

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

【例1.3】 教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些课程必须按规定的先后次序进行学习，有些则没有次序要求。课程之间先修和后修的次序关系可用一个称做图的数据结构来表示，如图1.4所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi,vj>，则表示课程i必须先于课程j进行学习。

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

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