数据结构发展史.doc

数据结构发展史 张抒菲 120081001104一、数据结构起源于程序设计随着计算机科学与技术的不断发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此相应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就给程序设计带来一个问题：应如何组织待处理的数据以及数据之间的关系（结构）。 1968 年克努思教授 1开创了数据结构的最初体系，他所著的计算机程序设计艺术第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 70 年代初，数据结构作为一门独立的课程开始进入大学课堂。 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法。例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法： Sartaj Sahni在他的数据结构、算法与应用一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 Clifford A.Shaffer在数据结构与算法分析一书中的定义是：“数据结构是 ADT（抽象数据类型Abstract Data Type） 的物理实现。” Lobert L.Kruse在数据结构与程序设计一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S），其中，K是数据元素的有限集，R是K上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。 数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。自从美国唐欧克努特教授用汇编语言编写的计算机程序设计技巧第一卷基本算法问世以来，已经出现了用Pascal、Java、C、C+、C#等语言编写的数据结构方面的书。总体说来，这些语言基本上分为面向过程的语言和面向对象的语言两大类，也出现过采用两种语言描述数据结构的书籍，如C和C+语言描述，但作者实际上是按照C+语言描述。同时采用面向过程和面向对象语言描述数据结构，目前国内基本上是空白。对于同一种数据结构与算法，同时采用面向过程和面向对象语言进行描述，可以从中更深刻理解这两种思想的不同，这对于深刻理解计算机语言和思想有着重要的作用。C语言是现在最流行的面向过程的语言，在业界使用非常广泛。而C#语言作为微软在新一代开发平台(.NET)上推出的、完全面向对象的语言，凭着其简洁、高效、模板、标准化的特性，使得C#语言像程序设计语言中的一件艺术品，也吸引着越来越多的开发人员。当然，C#语言也吸收了C语言的一些东西，如语法等，所以，在有些方面，C#与C是相似的。二、数据结构随着程序设计的发展而发展。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：数据结构随着程序设计的发展而发展 。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段： 无结构阶段。 4060 年代，计算机的应用主要针对科学计算，程序设计技术以机器语言 / 汇编语言为主，程序处理的数据是纯粹的数值，数据之间的关系主要是数学公式或数学模型。这一阶段，在人类的自然语言与计算机编程语言之间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计人员关注的重心是使程序尽可能地被计算机接受并按指令正确执行，至于程序能否让人理解并不重要。 结构化阶段。 6080 年代，计算机开始广泛应用于非数值处理领域，数据表示成为程序设计的重要问题，人们认识到程序设计规范化的重要性，提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的。数据结构概念的引入，对程序设计的规范化起到了重大作用。图灵 2奖获得者沃思3给出了一个著名的公式：数据结构 + 算法 = 程序。从这个公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件系统通常是以一个或几个关键数据结构为核心而组织的。 随着软件系统的规模越来越大、复杂性不断增加，人们不得不对结构化技术重新评价。由于软件系统的实现依赖于关键数据结构，如果这些关键数据结构的一个或几个有所改变，则涉及到整个系统，甚至导致整个系统彻底崩溃。 面向对象阶段。 面向对象技术（首先是面向对象程序设计）始于 80 年代初，是目前最流行的程序设计技术。 在面向对象技术中，问题世界的相关实体被视为一个对象，对象由属性和方法构成，属性用以描述实体的状态或特征，方法用以改变实体的状态或描述实体的行为。一组具有相同属性和方法的对象的集合抽象为类，每个具体的对象都是类的一个实例。例如，“教师”是一个类，“ 王老师”、“ 李老师”等对象都是“教师”类的实例。 由于对象（类）将 密切相关的属性（数据）和方法（操作）定义为一个整体，从而实现了封装和信息隐藏。使用类时，无需了解其内部的实现细节，一旦数据（结构）修改了，只需修改类内部的局部代码，软件系统的其余部分无需修改。 数据结构主要强调两个方面的内容： 数据之间的关系； 针对这些关系的基本操作。这两个方面实际上蕴涵着面向对象的思想：类重点描述实体的状态与行为，而数据结构重点描述数据之间的关系及其基本操作，数据及其相互关系构成了对实体状态的描述，针对数据元素之间关系的操作构成了对实体行为的描述。由此可见，类 与数据结构之间具有对应关系，如图 1 - 1 所示。“数据结构 + 算法 = 程序”这个公式在软件开发的进程中曾产生了深远的影响，但是，它并没有强调数据结构与解决问题的算法是一个整体，因此有人主张将它修改为“（数据结构 + 算法） = 程序”，以体现面向对象的思想。 值得注意的是，数据结构的发展并未终结。一方面，数据结构将继续随着程序设计的发展而发展；另一方面，面向各专门领域的数据结构得到研究和发展，各种实用的高级数据结构被研究出来，各种空间数据结构也在探索中。三、数据结构的发展并未终结。1.数据结构将继续随着程序设计的发展而发展；2.面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中1 克努思 （ Donald.E.Knuth ， 1938 年生）从小就是个优秀的学生，多次获得学业成就奖。 1963 年担任加利福尼亚理工学院的教师， 1968 年担任斯坦福大学教授。 1992 年为集中精力写作而荣誉退休，保留教授头衔。他特别感兴趣的是为计算机程序设计艺术丛书完成新卷并更新旧卷。这套丛书是 1962 年他还是研究生时以编译程序为中心开始写作的，对计算机科学的发展产生了深远的影响。从某种意义上说，克努思就意味着计算机程序设计艺术，也就意味着数据结构和算法这一类问题的答案。 2 图灵（ Alan.Mathison.Turing 1912 - 1954 ）出生于伦敦， 24 岁提出图灵机理论（这一理论奠定了整个现代计算机的理论基础）， 31 岁参与 COLOSSUS 的研制， 33 岁设想仿真系统， 35 岁提出自动程序设计概念， 38 岁发表论文计算机能思考吗？，论证了人工智能的可能性，被人们推崇为人工智能之父。美国计算机协会（ ACM ）为了纪