第 1 章 数据结构基础结构之美无处不在：说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子， 还有看不见却也存在的化学中的分子、原子。可见，一件事物只要存在，就一定会有自己 的结构。一幅画的生成，作家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规 划、谋篇布局。一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各 个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服。还有教育管理系 统的结构、通用技术的学科结构和课堂教学结构等。试想一下，管理大量数据是否也需要 用到数据结构呢？本章知识要点：ffl 数据结构的基本概念ffl数据类型和抽象数据类型ffl算法和算法分析1.1 数据结构的基本概念计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计 算机可以直接处理的最基本和最重要的对象。无论是进行科学计算，还是数据处理、过程 控制、对文件的存储和检索以及数据库技术等计算机应用，都是对数据进行加工处理的过 程。因此，要设计出一个结构良好而且效率较高的程序，必须研究数据的特性、数据间的 相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。计算机在发展的初期，其应用范围是数值计算，所处理的数据都是整型、实型和布尔 型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。随着计算技术的 发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中 与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音 和视频等复杂的数据。这些复杂的数据不仅量大，而且具有一定的结构。例如，一幅图像 是一个由简单数值组成的矩阵，一个图形中的几何坐标可以组成表。此外，语言编译过程 中所使用的栈、符号表和语法树，操作系统中用到的队列、磁盘目录树等，都是有结构的 数据。数据结构所研究的就是这些有结构的数据，因此，数据结构知识无论是对研制系统 软件还是对开发应用软件来说，都非常重要，是学习软件知识和提高软件设计水平的重要基础。1.1.1 数据结构的研究内容在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当使用计算 机来解决一个具体问题时，一般需要经过如下几个步骤：首先要从该具体问题中抽象出一 个适当的数学模型，然后设计或选择一个求解此数学模型的算法，最后编出程序进行调试、 测试，得到最终的解答。例如，用计算机进行全球天气预报时，可以通过求解一组球面坐 标系下的二阶椭圆偏微分方程来实现。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题变得越来越重要。据 统计，目前非数值计算问题的处理占用了 90%以上的机器时间。这类问题涉及的数据结构 更为复杂，数据元素之间的相互关系一般无法用数学方程式来描述。因此，解决这类问题 的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。数据结构主要研究非 数值计算问题，下面通过具体实例加以说明。例 1-1 学生信息检索系统。当系统需要查找某个学生的有关情况，或需要查询某个专业 或年级的学生的有关情况时，只要建立了相关的数据结构，按照某种算法编写了相关程序， 就可以实现计算机自动检索。为此，可以在学生信息检索系统中建立一张按学号顺序排列 的学生信息表和若干张分别按姓名、专业和年级顺序排列的索引表，如表1-1表1-4所示。 由这4张表构成的文件便是学生信息检索系统的数学模型。表 1-1 学生基本信息表学号姓名性别专业年级2011010001崔志永男计算机科学与技术2011 级2011030005李淑芳女软件工稈2011 级2012040010陆丽女数学与应用数学2012 级2012030012张志强男软件工稈2012 级2012010012李淑芳女计算机科学与技术2012 级2013040001王宝国男数学与应用数学2013 级2013010001石国利男计算机科学与技术2013 级2013030001刘文茜女软件工稈2013 级表 1-2 姓名索引表姓名索引号姓名索引号姓名索引号崔志永1张志强4石国利7李淑芳2, 5王宝国6刘文茜8陆丽3表 1-3 专业索引表专业索引号计算机科学与技术1, 5, 7软件工稈2, 4, 8数学与应用数学3, 6表 1-4 年级检索表年 级2011 级2012 级索引号!，23, 4 5年 级2013 级索引号6, 7 8诸如此类的还有电话号码查询问题、考试成绩查询问题和企业进销存管理系统等。在 这类文档管理系统的数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系 因此，这类数学模型可称为线性的数据结构。例 1-2 计算机系统组成结构,如图1-1 所示。图 1-1 计算机系统组成结构图计算机系统由硬件系统和软件系统组成，硬件系统由CPU、存储器、输入/输出设备和 外设组成，软件系统由系统软件和应用软件组成。如果把它们视为数据元素，则这些元素 之间呈现的是一种层次关系，从上到下按层进行展开，可形成一棵倒立的“树”，最上层 是“树根”，依层向下射出“结点”和“树叶”。同样是树结构的还有某个单位的组织机构、国家行政区域规划、书籍目录等。在这类 问题中，计算机处理的对象是树结构，元素之间是一对多的层次关系，这类数学模型被称 为树的数据结构。例 1-3 最短路径问题。从城市 A 到城市 B 有多条线路可达,但每条线路的交通成本不同, 那么，应怎样选择一条线路，使得从城市A出发到达城市B所花费的费用最低呢？可以将 这类问题抽象为图的最短路径问题。如图1-2 所示,图中的顶点代表城市,有向边代表两 个城市之间的通路，边上的权值代表两个城市之间的交通费。求解A到B的最低费用，就 是要在有向图从A点到B点的多条路径中，寻找到一条各边权值之和最小的路径，即求该 图的最短路径。同样是图结构的还有网络工程图、教学计划编排问题和比赛编排问题等。在这类问题 中，元素之间是多对多的网状关系，这类数学模型被称为图的数据结构。由以上 3 个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸 如表、树、图之类的数据结构。因此，可以说“数据结构”课程主要是在研究非数值计算 的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。1968 年，“数据结构”第一次在美国被确定为一门独立的课程。同年，著名的美国计 算机科学家 D.E.Knuth 教授编著了计算机程序设计技巧的第一卷基本算法，这是 第一本系统地阐述数据的逻辑结构以及运算的著作。20 世纪 60 年代末到 70 年代初，出现 了大型程序，程序与数据相对独立，结构化程序设计成为程序设计方法学的主要内容，人 们越来越感到数据结构的重要，认为程序设计的实质就是为所处理的问题选择一种好的数 据结构，并加之一种好的算法。数据结构在计算机科学中是一门综合性较强的专业基础课，是操作系统、数据库、人 工智能等课程的基础。同时，数据结构技术也广泛地应用于信息科学、系统工程、应用数 学以及各种工程技术领域。数据结构涉及的知识面十分广，可以认为它是介于数学、计算图 1-2 最短路径问题图 1-3 数据结构与其他课程的关系学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理 对象在计算机中表示出来，并对它们进行处理。对于计算机专业的学生，不学习数据结构， 几乎无法继续前行，因为几乎所有的程序和软件都要用到某种或某些数据结构。例如，在 面向对象程序设计中，一个对象在严格意义上来说就是一个数据结构，而哪个程序不使用 对象呢？可以这样说，不懂数据结构，就编不出什么像样的程序和软件。此外，数据结构在软件工程和计算机学科的其他领域也发挥着非常重要甚至是极为关 键的作用。例如，对大型数据库的管理、为互联网提供索引服务、云计算和云存储等都需 要广泛使用数据结构。在软件工程领域，数据结构被单独提取出来，作为软件设计与实现 过程的一个阶段。1.1.2 基本概念和术语在系统地学习数据结构知识之前，先来学习一下数据、数据元素、数据项等基本概念 和术语的确切含义。数据（Data）是信息的载体，能够被计算机识别、存储和加工处理。它是计算机程序 加工的原料，应用程序处理各种各样的数据。计算机科学中，数据就是计算机加工处理的 对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主 要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像和语数据元素(Data Element)是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点和记录等。例如，学生信息检索系统里学生信息表中的一个记录、计算机 系统组成结构中状态树的一个状态以及最短路径问题中的一个顶点等，都被称为一个数据有时，一个数据元素可由若干个数据项组成。例如，学生信息检索系统中学生信息表 的每一个数据元素都是一个学生记录，它包括学生的学号、姓名、性别、专业和年级数据 项。这些数据项可以分为两种：一种叫做初等数据项，如学生的性别、年级等，这些数据 项是数据处理时不能再分割的最小单位；另一种叫做组合数据项，如学生的成绩，它可以 再划分为由多门不同课程成绩组成的更小项。数据项(Data Item)是组成数据元素的有独立含义且不可分割的最小单位，如表1-1 中的学号、姓名和年级等都是数据项。数据项有名和值之分，数据项名是一个数据项的标 识，用变量定义，而数据项值是它的一个可能取值。例如，表1-1 中的 2011010001 是数据 项“学号”的一个取值。数据项具有一定的类型，依数据项的取值类型而定。数据对象(Data Object )是相同性质的数据元素的集合，是数据集合的一个子集。在 某个具体问题中，数据元素具有相同的性质(但元素值不一定相等)，属于同一个数据对 象，数据元素是数据元素类的一个实例。例如，在最短路径问题中，所有的顶点都是一个 数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据 元素的值分别为A和B。数据结构(Data Structure )是指互相之间存在着一种或多种特定关系的数据元素的集 合。在计算机中，数据元素不是孤立的，它们之间存在着这样或那样的关系，这种数据元 素之间的关系称为结构。一个数据结构包含两个要素：一个是数据元素的集合；另一个是 关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。数据结构的形式定义为一个二元组：Data_Structure =(D,R)其中，D是数据元素的有限集，R是D上关系的有限集。数据结构包括数据的逻辑结构和数据的存储结构。1逻辑结构数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，与数据的存储形式无关。根据数据元素间关系的不同特性，通常有下列4 类基本的逻辑结构，如图1-4所示。(a)集合结构(b)线性结构图 1-4 4 类基本逻辑结构示意图（1）集合结构。结构中数据元素间的关系是“属于同一个集合”。集合是元素关系极 为松散的一种结构