1.2.2 什么是数据结构

一般而言，利用计算机解决一个具体问题时，大致需要经过如下3个步骤：

①从具体问题抽象出一个合适的数学模型。

②设计一个可解此数学模型的算法。

③编写程序，进行测试、调整，直到问题得以解决。

寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。为了说明这个问题，此处首先举一个例子，然后给出明确的含义。

例1-1　对于八皇后问题，不是根据某种确定的计算法则进行处理，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步产生一个新的状态，整个试探过程形成一棵隐含的状态树，如图1-1所示（此处为了描述方便，将八皇后问题简化为四皇后问题）。用回溯法求解的过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。

图1-1　四皇后问题隐含状态树

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