本章主要介绍以下内容.doc

第1 章 绪 论 本章主要介绍以下内容 1、数据结构中涉及的基本概念、术语及所研究的主要内容 2、本教材使用的描述工具 本章重点和难点： 1、数据结构、数据类型、ADT、算法等重要概念。 用计算机求解任何问题都离不开程序设计，而程序设计的实质是数据表示和数据处理。数据要能被计算机处理，首先必须能够存储在计算机的内存中，这项任务称为 数据表示 ，数据表示的核心任务是数据结构的设计；一个实际问题的求解必须满足各项处理要求，这项任务称为 数据处理 ，数据处理的核心任务是算法设计。数据结构课程主要讨论数据表示和数据处理的基本问题。本章将概括地介绍数据结构的基本概念、基本思想和基本方法。 1.1 数据结构的兴起和发展 数据结构起源于程序设计 。随着计算机科学与技术的不断发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此相应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就给程序设计带来一个问题：应如何组织待处理的数据以及数据之间的关系（结构）。 1968 年克努思教授 1开创了数据结构的最初体系，他所著的计算机程序设计艺术第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 70 年代初，数据结构作为一门独立的课程开始进入大学课堂。 数据结构随着程序设计的发展而发展 。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段： 无结构阶段。 4060 年代，计算机的应用主要针对科学计算，程序设计技术以机器语言 / 汇编语言为主，程序处理的数据是纯粹的数值，数据之间的关系主要是数学公式或数学模型。这一阶段，在人类的自然语言与计算机编程语言之间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计人员关注的重心是使程序尽可能地被计算机接受并按指令正确执行，至于程序能否让人理解并不重要。 结构化阶段。 6080 年代，计算机开始广泛应用于非数值处理领域，数据表示成为程序设计的重要问题，人们认识到程序设计规范化的重要性，提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的。数据结构概念的引入，对程序设计的规范化起到了重大作用。图灵 2奖获得者沃思3给出了一个著名的公式：数据结构 + 算法 = 程序。从这个公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件系统通常是以一个或几个关键数据结构为核心而组织的。 随着软件系统的规模越来越大、复杂性不断增加，人们不得不对结构化技术重新评价。由于软件系统的实现依赖于关键数据结构，如果这些关键数据结构的一个或几个有所改变，则涉及到整个系统，甚至导致整个系统彻底崩溃。 面向对象阶段。 面向对象技术（首先是面向对象程序设计）始于 80 年代初，是目前最流行的程序设计技术。 在面向对象技术中，问题世界的相关实体被视为一个对象，对象由属性和方法构成，属性用以描述实体的状态或特征，方法用以改变实体的状态或描述实体的行为。一组具有相同属性和方法的对象的集合抽象为类，每个具体的对象都是类的一个实例。例如，“教师”是一个类，“ 王老师”、“ 李老师”等对象都是“教师”类的实例。 由于对象（类）将 密切相关的属性（数据）和方法（操作）定义为一个整体，从而实现了封装和信息隐藏。使用类时，无需了解其内部的实现细节，一旦数据（结构）修改了，只需修改类内部的局部代码，软件系统的其余部分无需修改。 数据结构主要强调两个方面的内容： 数据之间的关系； 针对这些关系的基本操作。这两个方面实际上蕴涵着面向对象的思想：类重点描述实体的状态与行为，而数据结构重点描述数据之间的关系及其基本操作，数据及其相互关系构成了对实体状态的描述，针对数据元素之间关系的操作构成了对实体行为的描述。由此可见，类 与数据结构之间具有对应关系，如图 1 - 1 所示。 “数据结构 + 算法 = 程序”这个公式在软件开发的进程中曾产生了深远的影响，但是，它并没有强调数据结构与解决问题的算法是一个整体，因此有人主张将它修改为“（数据结构 + 算法） = 程序”，以体现面向对象的思想。 值得注意的是，数据结构的发展并未终结。一方面，数据结构将继续随着程序设计的发展而发展；另一方面，面向各专门领域的数据结构得到研究和发展，各种实用的高级数据结构被研究出来，各种空间数据结构也在探索中。 1 克努思 （ Donald.E.Knuth ， 1938 年生）从小就是个优秀的学生，多次获得学业成就奖。 1963 年担任加利福尼亚理工学院的教师， 1968 年担任斯坦福大学教授。 1992 年为集中精力写作而荣誉退休，保留教授头衔。他特别感兴趣的是为计算机程序设计艺术丛书完成新卷并更新旧卷。这套丛书是 1962 年他还是研究生时以编译程序为中心开始写作的，对计算机科学的发展产生了深远的影响。从某种意义上说，克努思就意味着计算机程序设计艺术，也就意味着数据结构和算法这一类问题的答案。 2 图灵（ Alan.Mathison.Turing 1912 - 1954 ）出生于伦敦， 24 岁提出图灵机理论（这一理论奠定了整个现代计算机的理论基础）， 31 岁参与 COLOSSUS 的研制， 33 岁设想仿真系统， 35 岁提出自动程序设计概念， 38 岁发表论文计算机能思考吗？，论证了人工智能的可能性，被人们推崇为人工智能之父。美国计算机协会（ ACM ）为了纪念图灵对计算机科学的贡献，从 1966 年起设立图灵奖。 3 沃思（ Niklaus.Wirth ） 1934 年生于瑞士。 1968 年设计并实现了 PASCAL 语言 （被誉为 PASCAL 之父） ， 1971 年提出了结构化程序设计， 1976 年设计并实现了 Modula 2 语言。除了程序设计语言之外，沃思在其他方面也有许多创造，如扩充了著名的巴科斯范式，发明了语法图等。 1984 年获图灵奖。 1.2 数据结构的研究对象 用计算机求解问题一般包含两个步骤： 抽象出问题的模型； 求该模型的解。对于数值问题抽象出的模型通常是数学方程，例如求解梁架结构中应力的模型是线性方程组；预报人口增长情况的模型为微分方程。但更多的非数值问题是难以用数学方程来描述的。下面请看三个例子。 例 1-1 学籍管理问题 用计算机来完成学籍管理，就是由计算机程序处理学生学籍登记表，实现增、删、改、查等功能。表 1 - 1 所示就是一张简单的学生学籍登记表。在学籍管理问题中，计算机的操作对象是每个学生的学籍信息-称为档案表项，各档案表项之间的关系可以用称为线性表的数据结构来描述。 表 1-1 学生学籍登记表 例 1-2 人-机对弈问题 计算机之所以能和人对弈，是因为对弈的策略实现已存入计算机。在对弈问题中，计算机的操作对象是对弈过程中可能出现的棋盘状态-称为格局，而格局之间的关系是由对弈规则决定的。因为从一个格局可以派生出多个格局，所以，这种关系通常不是线性的。如图 1 - 2 ( a ) 所示为井字棋 1 的一个格局，从该格局出发可以派生出五个新的格局，从新的格局出发，还可以再派生出新的格局，如图 1 - 2 ( b ) 所示。格局之间的关系可以用称为树的数据结构来描述。 例 1-3 教学计划编排问题 一个教学计划包含许多课程，有些课程之间必须按规定的先后次序进行，图 1 - 3 ( a ) 列出了计算机软件方向的一些课程以及课程之间的次序关系。教学计划编排问题中，计算机的操作对象是课程， 课程之间的次序关系可以用称为图的数据结构来描述。如图 1 - 3 ( b ) 所示，其中 每个顶点表示一门课程，如果从顶点 c i 到 c j 之间存在边 ，则表示课程 c i 是课程 c j 的先修课。 由以上三个例子可见，描述这些非数值问题的模型不再是数学方程，而是线性表、树、图等数据结构。在抽象出问题的模型后，数据结构的任务还包括对这个模型进行求解。因此，数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。1 井字棋又称三子连珠，由两个人对弈，棋盘为 3 3 的方格，当一方的三个棋子占同一行、或同一列、或同一对角线时便为胜方。 1.3 数据结构的基本概念 1.3.1 数据结构 数据 （ Data ）是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数据可以分为两大类：一类是整数、实数等数值数据；另一类是图形、图象、声音、文字等非数值数据。 数据是计算机程序加工的“原料”，例如，编译程序加工的数据是源程序；学籍管理程序加工的数据是学籍登记表。 数据元素 （ Data Element ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。构成数据元素的不可分割的最小单位称为数据项。例如，对于学生学籍登记表，每个学生的档案就是一个数据元素，而档案中的学号、姓名、出生日期等是数据项。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。 数据元素具有广泛的含义，一般来说，能独立、完整地描述问题世界的一切实体都是数据元素。例如，对弈中的棋盘格局、教学计划中的某个课程、一年中的四个季节，甚至一次学术报告、一场足球比赛都是数据元素。数据元素又称为元素、结点、顶点或记录。 数据对象 （ Data Object ）是具有相同性质的数据元素的集合，是数据的子集。在实际应用中处理的数据元素通常具有相同性质，例如，学籍登记表中每个数据元素具有相同数目和类型的数据项，所有数据元素（学生的档案）的集合就构成了一个数据对象。在不产生混淆的情况下，我们将数据对象简称为数据。 数据结构 1（ Data Structure ）是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的 逻辑结构 （ Logical Structure ）是指数据元素之间逻辑关系的整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关系的不同，数据结构分为四类： 集合 数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； 线性结构 数据元素之间存在着一对一的线性关系； 树结构 数据元素之间存在着一对多的层次关系； 图结构 数据元素之间存在着多对多的任意关系。 树结构和图结构也称为非线性结构。 数据的逻辑结构常用逻辑结构图来描述，其描述方法是：将每一个数据元素看做一个结点，用圆圈表示，元素之间的逻辑关系用结点之间的连线表示，如果强调关系的方向性，则用带箭头的连线表示关系。图 1 - 4 描述了四种基本数据结构的逻辑结构图。 数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。 数据的 存储结构 2（ Storage Structure ）又称为 物理结构 ，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了存储数据元素之外，必须隐式或显式地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组 连续 的存储单元 依次 存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。例如，线性表 ( bat ， cat ， eat ) 的顺序存储示意图如图 1 - 5 所示。 链接存储结构的基本思想是：用一组 任意 的存储单元存储数据元素， 数据元素之间的逻辑关系是用指针来表示的。例如，线性表 ( bat ， cat ， eat ) 的链接存储示意图如图 1 - 6 所示。 数据的存储结构属于具体实现的视图，是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。 数据的逻辑结构和存储结构是密切相关的两个方面。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。1.3.2 数据结构的访问接口 数据的访问（也称操作）是指对数据的读取、修改、加工、处理等操作。操作的种类很多，一般随应用的不同而不同。数据结构的一个重要的问题是：对每种数据结构，如何设置一些操作，使得各种应用都能通过这些操作实现对数据的各种访问，这类操作称为数据结构的 基本操作 或 基本运算 。操作的调用形式与规范（例如形参表、返回类型等）称为操作的接口，数据结构的基本操作的接口的全体称为 数据结构的访问接口 。 什么操作才能作为数据结构的基本操作呢？一般来说，基本操作具有如下特性： 抽象性：不涉及具体应用，是关于数据结构的操作； 基本性：可以作为构造更复杂操作的基础； 完备性：只通过基本操作就能进一步实现对数据结构的各种访问； 一般性： 操作所接受输入的一般性，可供其他应用调用以构造高级操作。 一般来说，数据结构的基本操作是定义在逻辑结构之上，而实现于存储结构的。数据结构的访问接口体现了数据结构对外呈现的性质和功能，使得应用程序只需要了解访问接口就能使用数据结构，屏蔽了存储结构的细节，体现了数据的封装和信息隐藏。 1.3.3 抽象数据类型 1 数据类型 数据类型 （ Data Type ）是一组值的集合以及定义于这个值集上的一组操作的总称。数据类型规定了该类型数据的取值范围和对这些数据所能采取的操作。例如， C+ 中的整型变量可以取的值是机器所能表示的最小负整数和最大正整数之间的任何一个整数，允许的操作有 + 、 - 、 * 、 / 、 % 、 、 、 = 、 = 、 != 等。 2 抽象 所谓 抽象 （ Abstract ），就是抽出问题本质的特征而忽略非本质的细节，是对具体事物的一个概括。比如，地图是对它所描述地域的一种抽象，中国人是对所有具有中国国籍的中国公民的一种抽象。 3 抽象数据类型 抽象数据类型 （ A bstract D ata T ype ，以下简称 ADT ）是一个数据结构以及定义在该结构上的一组操作的总称。 ADT 可理解为对数据类型的进一步抽象，数据类型和 ADT 的区别仅在于：数据类型指的是高级程序设计语言支持的基本数据类型，而 ADT 指的是自定义的数据类型。 ADT 提供了使用和实现两个不同的视图，实现了封装和信息隐藏。例如，整数的数学概念和施加到整数的运算构成一个 ADT ， C+ 的变量类型 int 是对这个 ADT 的物理实现。各种程序设计语言都拥有整数类型，尽管他们在不同处理器上实现的方法不同，但由于其 ADT 相同，在用户看来都是相同的。 在设计 ADT 时，把 ADT 的定义和实现分开来。定义部分只包含数据的逻辑结构的定义和所允许的操作集合，一方面，使用者依据这些定义来使用 ADT ，即通过操作集合对该 ADT 进行操作；另一方