和E为单行道。在路口有13条可行的通路,其中有的可以同时通行,如A→B和E→C, 而有的不能同时通行如E→B和A→D。那末,在路口应如何设置交通灯进行车辆的管 理呢? AB D BA DA EBJEC ED a (b) 图1.3五叉路口交通管理示意图 (a)五叉路;(b)表示通路的图。 通常,这类交通道路问题的数学模型是一种称谓“图”的数据结构。例如在此例的问 题中可以图中一个顶点表示一条通路,而通路之间互相矛盾的关系以两个顶点之间的连 线表示。如在图1.3(b)中,每个圆圈表示图1.3(a)所示五叉路口上的一条通路,两个圆 圈之间的连线表示这两个圆圈表示的两条通路不能同时通行。设置交通灯的问题等价为 对图的顶点的染色问题,要求对图上的每个顶点染一种颜色,并且要求有线相连的两个顶 点不能具有相同颜色而总的颜色种类应尽可能地少。图1.3(b)所示为一种染色结果 圆圈中的数字表示交通灯的不同颜色,例如3号色灯亮时只有D→A和D→B两条路可通 综上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程而是诸如 表树和图之类的数据结构。因此简单说来数据结构是一门研究非数值计算的程序设 计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构》作为一门独立的课程在国外是从1968年才开始设立的。在这之前它的 某些内容曾在其它课程如表处理语言中有所阐述。1968年在美国一些大学的计算机系 的教学计划中虽然把(《数据结构》规定为一门课程但对课程的范围仍没有作明确规定。 当时数据结构几乎和图论特别是和表树的理论为同义语。随后数据结构这个概念被 扩充到包括网络、集合代数论、格、关系等方面,从而变成了现在称之为《离散结构》的内 容。然丽,由于数据必须在计算机中进行处理,因此,不仅考虑数据本身的数学性质而且 还必须考虑数据的存储结构这就进一步扩大了数据结构的内容。近年来,随着数据库系 统的不断发展,在数据结构课程中又增加了文件管理(特别是大型文件的组织等)的内容。 1968年美国唐欧克努特教授开创了数据结构的最初体系,他所著的《计算机程序 设计技巧》第一卷(基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操
作的著作。从60年代末到70年代初出现了大型程序,敕件也相对独立结构程序设计 成为程序设计方法学的主要内容,人们就越来越重视数据结构,认为程序设计的实质是对 确定的问题选择一种好的结构加上设计一种好的算法。从70年代中期到80年代初各 种版本的数据结构著作就相继出现。 目前在我国,《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之 而且是其它非计算机专业的主要选修课程之一。 数据结构)在计算机科学中是一门综合 性的专业基础课。数据结构的研究不仅涉及 数学 到计算机硬件(特别是编码理论、存储装置和 存取方法等)的研究范围,而且和计算机软件 代数系统 的研究有着更密切的关系,无论是编译程序 编码理论 算子关系 还是操作系统,都涉及到数据元素在存储器 数据类型 中的分配问题。在研究信息检索时也必须考 数据表示法数据的运算 文件系统 虑如何组织数据,以便查找和存取数据元素(存碳装量数据构了敬据组织 更为方便。因此,可以认为数据结构是介于 数据存取 信息检索 数学计算机硬件和计算机软件三者之间的 硬件机器组织/软件 计算机系统 〔计算机程序 门核心课程(如图1.4所示)。在计算机科 设计) 设计) 学中数据结构不仅是一般程序设计(特别是 非数值计算的程序设计)的基础而且是设计 图14(数据结构》所处的地位 和实现编译程序操作系统、数据库系统及其 它系统程序和大型应用程序的重要基础。 值得注意的是数据结构的发展并未终结,一方面,面向各专门领域中特殊问题的数 据结构得到研究和发展如多维图形数据结构等;另一方面从抽象数据类型的观点来讨 论数据结构已成为一种新的趋势,越来越被人们所重视。 12基本概念和术语 在本节中我们将对一些概念和术语赋以确定的含义以便与读者取得“共同的语 言”。这些概念和术语将在以后的章节中多次出现。 数据(Dat)是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机 中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。例如,一个利用 数值分析方法解代数方程的程序其处理对象是整数和实数;一个编译程序或文字处理程 序的处理对象是字符串。因此对计算机科学而言数据的含义极为广泛如图象声音等 都可以通过编码而归之于数据的范畴。 数据元素( Data element)是数据的基本单位在计算机程序中通常作为一个整体 进行考虑和处理。例如例12中的“树中的一个棋盘格局例13中的“图”中的一个圆 圈都被称为一个数据元素。有时,一个数据元素可由若干个数据项( Data item)组成,例 如例11中一本书的书目信息为一个数据元素而书目信息中的每一项(如书名、作者名
等)为一个数据项。数据项是数据的不可分割的最小单位。 数据难象( Data object)是性质相同的数据元素的集合,是数据的一个子集。例如 整数数据对象是集合N=10,±1,±2,…,字母字符数据对象是集合C={A’,"B', z'}。 数据结构( Data structure)是相互之间存在一种或多种特定关系的数据元素的集 合。这是本书对数据结构的一种简单解释①从11节中 在的,而是在它们之间存在着某种关系这种数据元素相互粲名000 三个例子可以看到,在任何问题中数据元素都不是孤立存 之间的关系称为结构( Structure)根据数据元素之间关系 的不同特性通常有下列四类基本结构:1)集合结构中线性0000° 的数据元素之间除了“同属于一个集合”的关系外,别无其 它关系②;(2)线性结构结构中的数据元素之间存在一个树 对一个的关系;(3)树形结构结构中的数据元素之间存在 个对多个的关系;(4)图状结构或网状结构结构中的数 据元素之间存在多个对多个的关系。图15为上述四类基 图 本结构的关系图。由于“集合”是数据元素之间关系极为松 散的一种结构,因此也可用其它结构来表示它。 数据结构的形式定义为:数据结构是一个二元组 图1.5四类基本结构关系图 Data_ Structure =(D, S) (1-1) 其中:D是数据元素的有限集,S是D上关系的有限集。下面举两个简单例子说明之。 例14在计算机科学中复数可取如下定义:复数是一种数据结构 mplex=(C, R) 其中:C是含两个实数的集合{c1,c2};R=|P},而P是定义在集合C上的一种关系 (c1,c2)},其中有序偶(1,c2)表示c1是复数的实部,c2是复数的虚部。 例15假设我们需要编制一个事务管理的程序,管理学校科学研究课题小组的各 项事务,则首先要为程序的操作对象一一课题小组设计一个数据结构。假设每个小组由 一位教师、一至三名研究生及一至六名本科生组成,小组成员之间的关系是:教师指导研 究生,而由每位研究生指导一至两名本科生。则可以如下定义数据结构 Group=(P, R) 其中:P={T,G1,…,Gn,S1!Sm≤n≤15m2 R={R1,R2 R1=1(7,G1)l1s;<nns R2=1(G,S) ①对于数据结构这个概念,至今尚未有一个被一致公认的定义不同的人在使用这个词时所表达的意思有所不 同 ②这和数学中的集合概念是一致的。 ③T表示导师G表示研究生,S表示大学生
上述数据结构的定义仅是对操作对象的一种数学描述,换句话说,是从操作对象抽象 出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系因此又称为 数据的逻辑结构。然而讨论数据结构的目的是为了在计算机中实现对它的操作因此还 需研究如何在计算机中表示它。 数据结构在计算机中的表示(又称映象)称为数据的物理结构,又称存储结构。它包 括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位 叫做位bt)。在计算机中我们可以用一个由若干位组合起来形成的一个位串表示一个 数据元素(如用一个字长的位串表示一个整数用八位二进制数表示一个字符等),通常称 这个位串为元素(Emen)或结点(Node)。当数据元素由若干数据项组成时,位串中 对应于各个数据项的子位串称为数据城( Data field)。因此,元素或结点可看成是数据元 素在计算机中的映象。 数据元素之间的关系在计算机中有两种不同的表示方法顺序映康和非顺序映象,并 由此得到两种不同的存储结构顺序存储结构和链式存储结构。顺序映象的特点是借助 元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如,假设用两个字长的 位串表示一个实数,则可以用地址相邻的四个字长的位串表示一个复数,如图16(a)为 表示复数x1l=30-23和x2=-07+48的顺序存储结构;非顺序映象的特点是借 助指示元素存储地址的指针( Pointer)表示数据元素之间的逻辑关系,如图16(b)为表示 复数x1的链式存储结构其中实部和虚部之间的关系用值为“0415”6指针来表示(0415 是虚部的存储地址)②。数据的逻拇结构和物理结构是密切相关的两个方面,以后读者会 看到,任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的存 储结构。 0300 3,0 0302 2.3 0415 -2.3 0632 07 0611 06344.8 0613|0415 图1.6复数存储结构示意图 (a)顺序存储结构;(b)链式存储结构 ①本书中有时也把数据元素简称为元素读者应从上下文去理解分辨之。 ②在实际应用中像复数这类极简单的结构不需要采用链式存储结构在此仅为了简化讨论而作为假例引用
如何描述存储结构呢。虽则存储结构涉及数据元素及其关系在存储器中的物理位 置,但由于本书是在高级程序语言的层次上讨论数据结构的操作,因此不能如上那样直接 以内存地址来描述存储结构但我们可以借用高级程序语言中提供的“数据类型"来描述 它,例如可以用所有高级程序语言中都有的“一维数组”类型来描述顺序存储结构,以C 语言提供的“指针”来描述链式存情结构。假如我们把C语言看成是一个执行C指令和C 数据类型的虚拟处理器,那末本书中讨论的存储结构是数据结构在C虚拟处理器中的表 示,不妨称它为虚拟存储结构。 数据类型 Data Type)是和数据结构密切相关的一个概念,它最早出现在高级程序 语言中用以刻画(程序)操作对象的特性。在用高级程序语言编写的程序中,每个变量、 常量或表达式都有一个它所属的确定的数据类型。类型明显或隐含地规定了在程序执行 期间变量或表达式所有可能取值的范围,以及在这些值上允许进行的操作。因此数据类 型是一个值的集合和定义在这个值集上的一组操作的总称。例如C语言中的整型变量, 其值集为某个区闻上的整数(区间大小依赖于不同的机器),定义在其上的操作为:加、 减、乘、除和取模等算术运算。 按“值”的不同特性,高级程序语言中的数据类型可分为两类:一类是非结构的原子类 型。原子类型的值是不可分解的。如:C语言中的基本类型(整型实型字符型和枚举 类型)指针类型和空类型。另一类是结构类型。结构类型的值是由若干成分按某种结构 组成的因此是可以分解的,并且它的成分可以是非结构的也可以是结构的。例如数组 的值由若于分量组成,每个分量可以是整数也可以是数组等。在某种意义上,数据结构 可以看成是“一组具有相同结构的值”则结构类型可以看成由一种数据结构和定义在其 上的一组操作组成。 实际上,在计算机中数据类型的概念并非局限于高级语言中每个处理器(包括 计算机硬件系统、操作系统高级语言、数据库等)都提供了一组原子类型或结构类型。例 如,一个计算机硬件系统通常含有“位”、“字节”、“字”等原子类型,它们的操作通过计算机 设计的一套指令系统直接由电路系统完成而高级程序语言提供的数据类型其操作需通 过编译器或解释器转化成低层即汇编语言或机器语言的数据类型来实现。引人“数据类 型”的目的,从硬件的角度看,是作为解释计算机内內存中信息含义的一种手段,而对使用数 据类型的用户来说,实现了信息的隐蔽,即将一切用户不必了解的细节都封装在类型中。 例如,用户在使用“整数”类型时,既不需要了解“整数”在计算机内部是如何表示的也不 需要知道其操作是如何实现的。如“两整数求和”,程序设计者注重的仅仅是其“数学上求 和”的抽象特性,而不是其硬件的“位"操作如何进行。 抽象数据类型( Abstract Data Type i简称ADT)是指一个数学模型以及定义在该模 型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性而与其在计算机内 部如何表示和实现无关即不论其内部结构如何变化,只要它的数学特性不变都不影响 其外部的使用。 抽象数据类型和数据类型实质上是一个概念。例如,各个计算机都拥有的“整数”类 ①在此指广义的处理器包括计算机的硬件泵统和软件系统