第 章 绪 论
计算机是对各种各样数据进行处理的机器 。在计算机 中如何组织数据 ，如何处理数据 ，从
而如何更好地利用数据是计算机科学的基本研究 内容 。掌握数据在计算机 中的各种组织和处
理方法是继续深入学习的基础 。
数据结构 的基本概念
数据 结构( )研究的是计算机所处理的数据元素间的结构关系及其操作实
现 的算法 。
早期的计算机都用于进行数值计算 ，数值计算 的特 点是数据元素间的关系简单 ，但计算复
杂。随着计算机应用范围的扩展， 目前计算机更多地被用于非数值处理，如管理、控制等领域，
非数值处理 问题 的特 点是数据元素间的关系复杂 ，而计算较简单 。
数据元素间的结构关系 (或称逻辑结构 )有几种基本形式 。最简单 的是线性结构，这时其
有关结构 的性质可 以归纳为下述一些 问题 ：哪一个数据元素是线性表 中的第一个数据元素 ？
哪一个数据元素是线性表 中的最后一个数据元素 ？某一个数据元素 的前驱和后继各是哪一个
数据元素等等 。更为复杂 的结构关系有树形结构 表示着等级和分枝 的关系 ，还有 图形结
构 表示着更复杂 的客观事物之间的关系 。
为 了有效地在计算机上解决具有各种 结构关系 的实 际问题 ，我们还必须研 究这种具有结
构关系的数据在计算机 内部的存储方法 (或称存储结构 )以及在计算机 中处理这样 的具有结构
关系数据所需进行的操作和操作 的实现方法 。
我们先来看一个最简单 的线性表关系的例子 。
例 建立一个住院病人押金情况表 。住院病人押金情况表包括：姓名、性别、年龄 、住
院押金。要求：每当病人住院时，插入一条记录；每当病人出院时，删去该病人的记录。
分析每个病人 的数据为一条记录 ，每个记录包括姓名、性别、年龄 、住院押金 四个数据
项 。所有病人 的记录构成一个线性表 。这构成 了该 问题 的逻辑数据结构 。
线性表上要求有插入 、删 除一条记录 的操作 。插入操作和删 除操作构成 了该线性表 的操
作集 合 。
线性表可 以选用不 同的存储结构 。具体到这个线性表可 以有两种存储结构 ：
)顺序存储结构 ：即把所有记录依次存储在一个数组 中。如
数组下标姓名性别年龄住院押金
张 三
李 四
)单链存储结构 ：即把每个记录看作一个结点，让所有结点依次链接 。如
显然 ，存储结构不同则实现操作的算法就不同。
由此可见，一个具体 问题的软件设计通常包括三个步骤： 分析和确定该 问题 的逻辑数
据 结 构 ； 设计该问题的具体存储结构； 设计该 问题在具体存储结构下的操作实现算法 。
下边我们较为准确地定义我们所 引进 的几个基本术语 ：
数据在计算机 中这个术语含义非常广泛 ，可 以认为它是描述客观事物的数字、字符 以及
所有能输入到计算机 中并能为计算机所接受的符号集 。
数据元素数据的基本单位 ，是计算机进行输入输出操作的最小单位 。大多数情况下，一
个数据元素 由若干个数据项组成 。数据项是数据不可分割的最小单位 。
数据结构是指计算机处理 的数据元素 的组织形式和相互间关系 。从数据元素之 间的不
同特性分 ，数据结构有三种基本类型：线性结构、树形结构和图形结构 。从不同的抽象层次看，
数据结构可分为逻辑数据结构和物理数据结构 (或称存储结构 )。存储结构主要有两种基本类
型：顺序存储结构和链式存储结构。
操作是指数据结构上需要或能够进行的处理 。对一个具体 问题来说 ，存储结构不 同则
操作的具体实现算法就不同；相 同的存储下也可有许多种不同的操作实现算法 。
我们研究数据结构 ，需要研究如下问题 ：一个具体 问题的逻辑数据结构是什么 ？适宜选用
什么样 的存储结构 ？采用什么样 的操作实现算法效率更高 ？由此我们可 以说 ，数据结构是一
研究非数值处理 问题 的软件设计 中计算机 的操作对象 以及它们之 间的关系和操作实现等 的
学科 。换句
