数据结构发展史
数据结构是计算机科学中的一门重要领域,它的发展史与计算机科学的发展紧密相连。早期的计算机科学主要应用于科学计算领域,随着计算机科学与技术的不断发展,计算机的应用领域扩展到控制、管理等非数值处理领域。与此相应,计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据。
1968年,克努思教授开创了数据结构的最初体系,他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。70年代初,数据结构作为一门独立的课程开始进入大学课堂。
数据结构的定义不存在标准的定义,每个人根据各自的理解都有不同的表述方法。例如,Sartaj Sahni在他的《数据结构、算法与应用》一书中称:“数据结构是数据对象,及存在于该对象的实例和组成实例。”Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是:“数据结构是ADT(抽象数据类型)的物理实现。”
数据结构可以分为逻辑结构、存储结构(物理结构)和数据的运算。逻辑结构是对数据之间关系的描述,有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为(K,R)(或(D,S)),其中,K是数据元素的有限集,R是K上的关系的有限集。数据元素相互之间的关系称为结构。
数据结构中有四类基本结构:集合、线性结构、树形结构、图形结构(网状结构)。树形结构和图形结构全称为非线性结构。在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个。
数据结构在计算机中的表示(映像)称为数据的物理(存储)结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。
顺序存储方法是把逻辑上相邻的结点存储在物理位臵相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。链式存储方法是把逻辑上相邻的结点存储在物理位臵不相邻的存储单元里,结点间的逻辑关系是由附加的指针字段表示的,由此得到的存储表示称为链式存储结构。
索引存储方法是建立存储结点信息外,还建立附加的索引表来标识结点的地址。散列存储方法是根据结点的关键字直接计算出该结点的存储地址。
数据结构中,逻辑上可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构,线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
逻辑结构与数据元素本身的形式、内容、相对位臵、所含结点个数都无关。自从美国唐〃欧〃克努特教授用汇编语言编写的《计算机程序设计技巧》第一卷《基本算法》问世以来,已经出现了用Pascal、Java、C、C++、C#等语言编写的数据结构方面的书。总体说来,这些语言基本上分为面向过程的语言和面向对象的语言两大类,也出现过采用两种语言描述数据结构的书籍。