1.1 引言

1.1.1 什么是数据结构

“数据结构”作为计算机科学技术专业的专业基础课，是十分重要的核心课程，其主要的研究内容就是数据之间的逻辑关系和物理实现，探索有利的数据组织形式及存取方式。所有计算机系统软件和应用软件的设计、开发都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂项目的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握数据结构的有关知识。

数据结构包含两方面的内容，其一是构成集合的数据元素，其二是数据元素之间存在的关系。数据结构也就是带有结构的数据元素的集合，结构指的是数据元素之间的相互关系，即数据的组织形式。由此可见，计算机所处理的数据是具有内在联系的集合。著名的计算机科学家N. Writh提出“算法+数据结构程序”的思想，明确地指出了数据结构实际上是程序的主要部分。

数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般非数值计算机程序设计的基础，还是设计和实现汇编语言、编译程序、操作系统、数据库系统，以及其他系统程序和大型应用程序的重要基础。

从我国的计算机教学现状来看，数据结构不仅是计算机专业教学计算机中的核心课程之一，而且已经逐步成为非计算机专业学生的重要选修课程。

1.1.2 数据结构研究内容

用计算机解决一个实际问题时，大致需要以下几个步骤：

（1）从具体问题抽象出一个适当的数学模型；

（2）设计求解数学模型的算法；

（3）编制、运行并调试程序，直到解决实际问题。

所以，建立数学模型的过程就是分析问题，并找出这些对象的关系，用数学语言来描述。下面通过几个实例来了解一下如何构造数据结构。

【例1-1】 学生的学籍档案管理表。

假设一个学籍档案管理系统应包含如表1-1所示的学生信息。

表1-1 学生信息登记表

将表1-1称为一个数据结构，表中的每一行是一个结点，或称为记录（Record），它由学号、姓名、性别、出生年月日、入学总分等数据项（Item）组成。在这个表中，第一条记录没有直接前驱，称为开始结点；最后一条记录没有直接后继，称为终端结点。除了第一条记录以外，其余的记录都有且只有一条直接前驱记录和一条直接后继记录。这些结点之间的关系是“一对一”的关系，这就是该表的逻辑结构。

此外，该表在计算机的外存中是如何存储的？表中各元素是存储在连续的单元中（顺序结构），还是用指针链接存储在不连续的存储单元（链式存储）？这就构成了该表的存储结构。

对该表进行的查找记录、插入记录、删除记录、对记录进行排序、统计等，就构成了数据的运算。

数据结构就是研究数据的逻辑、存储结构和运算方法（即算法）的学科。

【例1-2】 井字棋人机对弈问题。

井字棋对弈过程中，任何一方只要使相同的三个棋子连成一条直线即为胜方（可以是一行、一列或一条对角线）。如果下一棋子由“×”方下，可以派生出五个子格局，如图1-1所示。

若将从对弈开始到结束的过程中所有的可能的格局画在一张图上，即形成了一棵倒挂的对弈“树”。“树根”是对弈开始时的第一步棋，而所有的“叶子”便是可能出现的结局。在本例中，对弈开始之前的棋盘格局没有直接前驱，称为开始结点（即根），以后每走一步棋，都有多种对应的策略，结点之间存在着“一对多”的关系，它构成了井字棋对弈的逻辑结构。

【例1-3】 制订教学计划。

在制订教学计划时，需要考虑各门课程的开设顺序。有些课程需要先修课程，有些课程则不需要，而有些课程又是其他课程的先修课程。比如，计算机专业课程的开设情况如表1-2所示。

表1-2 计算机专业学生的必修课程

教学计划的关系图如图1-2所示。

在图1-2中，各结点都有多个直接前驱和多个直接后继，结构之间存在着“多对多”的关系，称为图。

综上实例可知，非数值计算问题的数学模型不再是数学方程的问题，而是诸如上述的表、树、图之类的数据结构。因此，数据结构是一门研究非数值计算的程序设计问题的学科，主要研究数据的逻辑结构、存储结构和算法。

下面介绍一下这三方面的知识。