第1章 绪论

1.1 什么是数据结构

计算机的迅猛发展早已使其摆脱了单纯的科学计算。而今各部门各个行业都有大量的计算机在从事着行政事务管理、生产作业调度和实时控制以及通信、教育等方面工作。近年来人工智能领域的研究成果更加提高了计算机的“智力”，使其在很多方面已能辅助人们或代替人们做出决策、诊断等具有专家性质的工作。

计算机的普及和发展，使人们要求计算机能处理的问题愈来愈多，愈来愈复杂，问题的规模愈来愈大。要使计算机发挥更大的作用，人们就必须设计出更好的程序来。要做到这一点，就应该掌握一系列程序设计知识，其中数据结构的知识是不可少的。因为人们着手处理问题时，必须分析该问题涉及到哪些数据，这些数据具有什么性质，数据之间有什么关系，采用什么方式存储数据并体现出它们之间的关系，所涉及的问题又包含有哪些运算，可采用什么算法。这些正是数据结构这门学科所研究的内容。

一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是对问题的分析，即从问题中提取出操作对象并找出这些操作对象之间含有的关系，加以简化、抽象后，用数学语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述，下面是三个例子。

例1.1 表1.1中列出的是某班级学生的基本情况表，表中每一行包含的信息有：学号、姓名、性别、出生日期、所在院系、政治面貌。对于这类文档管理的数学模型，在计算机处理的对象之间通常存在一种最简单的线性关系，这类数学模型可称为线性模型。

表1.1 某班级学生基本情况表

例1.2 在迷宫问题中，计算机之所以能找到迷宫的出口，是因为人们已将搜索出口的策略事先存入计算机中。在迷宫中，每走到一处，接下来可走的通路有三条，如图1.1所示。计算机处理的这类对象之间通常存在的关系不是线性关系。例如，若将从迷宫入口处到出口的过程中所有可能的通路都画出，则可得到一棵倒长的“树”。“树根”是迷宫入口，“树叶”是出口或死路。所以，“树”可以是某些非数值计算问题的数学模型。

图1.1 迷宫下一步的通路

例1.3 在一个由若干个城市组成的交通网中，现要将一些原有的公路修建成高速公路，使所有城市之间都有高速通道存在。这时，有多种方案可选择，但若要考虑投入和效益，最佳的方案是在交通网中构造最小生成树，即确定n-1条线路连通这n个城市，并且代价最小。这类交通、道路问题的数学模型是一种被称为“图”的数据结构。

综上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此，数据结构是一门研究非数值计算程序中数据对象及其关系和操作的学科。