和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年美国唐欧克努特教授开创了数据结构的最初体系,他所著的《计算机程序 设计技巧》第一卷(基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操