1.1 数据结构的研究内容
计算机主要用于数值计算时，一般要经过如下几个步骤：首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。在此过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。例如，用计算机进行全球天气预报时，就需要求解一组球面坐标系下的二阶椭圆偏微分方程；预测人口增长情况的数学模型为常微分方程。求解这些数学方程的算法是计算数学研究的范畴，如高斯消元法、差分法、有限元法等算法。数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型，下面通过三个实例加以说明。
【例1.1】 学生学籍管理系统。
高等院校教务处使用计算机对全校的学生情况作统一管理。学生的基本信息，包括学生的学号、姓名、性别、籍贯、专业等，如表1.1所示。每个学生的基本情况按照不同的顺序号，依次存放在“学生基本信息表”中，根据需要对这张表进行查找。每个学生的基本信息记录按顺序号排列，形成了学生基本信息记录的线性序列，呈一种线性关系。
表1.1 学生基本信息表
诸如此类的线性表结构还有图书馆的书目管理系统、库存管理系统等。在这类问题中，计算机处理的对象是各种表，元素之间存在简单一对一的线性关系，因此这类问题的数学模型就是各种线性表，施加于对象上的操作有查找、插入和删除等。这类数学模型称为“线性”的数据结构。
【例1.2】 人机对弈问题。
计算机之所以能和人对弈是因为已经将对弈的策略在计算机中存储好。由于对弈的过程是在一定规则下随机进行的，所以，为使计算机能灵活对弈，就必须把对弈过程中所有可能发生的情况及相应的对策都加以考虑。以最简单的井字棋为例，初始状态是一个空的棋盘格局。对弈开始后，每下一步棋，则构成一个新的棋盘格局，且相对于上一个棋盘格局的可能选择可以有多种形式，因而整个对弈过程就如同图1.1所示的“一棵倒长的树”。在这棵“树”中，从初始状态（根）到某一最终格局（叶子）的一条路径，就是一次具体的对弈过程。
图1.1 井字棋的对弈树
人机对弈问题的数学模型就是如何用树结构表示棋盘和棋子等，算法是博弈的规则和策略。诸如此类的树结构还有计算机的文件系统、一个单位的组织机构等。在这类问题中，计算机处理的对象是树结构，元素之间是一对多的层次关系，施加于对象上的操作有查找、插入和删除等。这类数学模型称为“树”的数据结构。
【例1.3】 最短路径问题。
从城市A到城市B有多条线路，但每条线路的交通费不同，那么，如何选择一条线路，使得从城市A到城市B的交通费用最少呢？解决的方法是，可以把这类问题抽象为图的最短路径问题。如图1.2所示，图中的顶点代表城市，有向边代表两个城市之间的通路，边上的权值代表两个城市之间的交通费。求解A到B的最少交通费用，就是要在有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
图1.2 最短路径问题
最短路径问题的数学模型就是图结构，算法是求解两点之间的最短路径。诸如此类的图结构还有网络工程图和网络通信图等，在这类问题中，元素之间是多对多的网状关系，施加于对象上的操作依然有查找、插入和删除等。这类数学模型称为“图”的数据结构。
从上面三个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
20世纪60年代初期，“数据结构”有关的内容散见于操作系统、编译原理等课程中。1968年，“数据结构”作为一门独立的课程被列入美国一些大学计算机科学系的教学计划，同年，著名计算机科学家D.E.Knuth教授发表了《计算机程序设计艺术》第一卷《基本算法》。这是第一本较系统地阐述“数据结构”基本内容的著作。之后，随着大型程序和大规模文件系统的出现，结构化程序设计成为程序设计方法学的主要研究方向，人们普遍认为程序设计的实质就是对所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好的算法，著名科学家Wirth教授的《算法+数据结构=程序》正是这种观点的集中体现。
目前，数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统都涉及数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以使查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。
有关“数据结构”的研究仍不断发展，一方面，面向各专门领域中特殊问题的数据结构正在研究和发展；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。