数据结构发展史

《数据结构发展史》由会员分享，可在线阅读，更多相关《数据结构发展史（8页珍藏版）》请在装配图网上搜索。

1、数据结构发展史张抒菲 120081001104一、数据结构起源于程序设计随着计算机科学与技术的不断发展，计算机的应用领域已不再局 限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此 相应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、 图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就 给程序设计带来一个问题：应如何组织待处理的数据以及数据之间的 关系(结构)。1968年克努思教授1开创了数据结构的最初体系，他所著的 计算机程序设计艺术第一卷基本算法是第一本较系统地阐述 数据的逻辑结构和存储结构及其操作的著作。70年代初，数据结构 作为一门独立的课程开始进入大学课堂

2、。数据结构在计算机科学界至今没有标准的定义。个人根据各自的 理解的不同而有不同的表述方法。例的数据元素之间的各种联系。这 些联系可以通过定义相关的函数来给出。”他将数据对象(data object) 定义为“一个数据对象是实例或值的集合”。数据结构在计算机科 学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表 述方法：Sartaj Sahni在他的数据结构、算法与应用一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实Clifford A.Shaffer在数据结构与算法分析一书中的定义是： “数据结构是ADT （抽象数据类型Abstract Data Type）的物理实 现

3、。”Lobert L.Kruse在数据结构与程序设计一书中，将一个数据结 构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指 抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实 现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的 实现。数据结构是指同一数据元素类中各数据元素之间存在的关系。 数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数 据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数 据结构。逻辑结构形式地定义为（K，R）（或（D，S），其中， K是数据元素的有限集，R是K上的关系的有限集。数据元素相互之间的关系称为结构。有四类基本结构：

4、集合、 线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构 全称为非线性结构。集合结构中的数据元素除了同属于一种类型外， 别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图 形结构中每个结点的前驱结点数和后续结点数可以任意多个。数据结构在计算机中的表示（映像）称为数据的物理（存储） 结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有 两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同 的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把 逻辑上相邻的结点存储在物理位置相邻的存储单元里，结

5、点间的逻辑 关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存 储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程 序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的 结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表 示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借 助于程序设计语言中的指针类型来实现。索引存储方法:除建立存储 结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法 就是根据结点的关键字直接计算出该结点的存储地址。数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系） 可以把数据结构分成线性结构和非线性结构。线性结构的

6、顺序存储结 构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存 取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单 元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相 对位置、所含结点个数都无关。自从美国唐欧克努特教授用汇编语言编写的计算机程序设 计技巧第一卷基本算法问世以来，已经出现了用Pascal、Java、 C、C+ +、C#等语言编写的数据结构方面的书。总体说来，这些语言 基本上分为面向过程的语言和面向对象的语言两大类，也出现过采用 两种语言描述数据结构的书籍，如C和C+语言描述，但作者实际 上是按照C+语言描述。同时采用面向过程和面向对象语言描述数 据结

7、构，目前国内基本上是空白。对于同一种数据结构与算法，同时 采用面向过程和面向对象语言进行描述，可以从中更深刻理解这两种 思想的不同，这对于深刻理解计算机语言和思想有着重要的作用。C 语言是现在最流行的面向过程的语言，在业界使用非常广泛。而C# 语言作为微软在新一代开发平台(.NET)上推出的、完全面向对象的语 言，凭着其简洁、高效、模板、标准化的特性，使得C#语言像程序 设计语言中的一件艺术品，也吸引着越来越多的开发人员。当然，C# 语言也吸收了C语言的一些东西，如语法等，所以，在有些方面， C#与C是相似的。二、数据结构随着程序设计的发展而发展。程序设计经历了三个阶段:无结构阶段、结构化阶段

8、和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：应用领域：科学计瞥；程序设计面向计算机应用领域：科学计算与非数值处理：算法+数据结构殖序应用殖域：更多地应用于拄数值处理：（算法+数据结构：唯序数据结构随着程序设计的发展而发展。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展 也经历了三个阶段： 无结构阶段。4060年代，计算机的应用主要针对科学计算，程序设计技术 以机器语言/汇编语言为主，程序处理的数据是纯粹的数值，数据 之间的关系主要是数学公式或数学模型。这一阶段，在人类的自然语 言与计算机编程语言之间存在着巨大的鸿沟，程序设计属于面向计算 机的程

9、序设计，设计人员关注的重心是使程序尽可能地被计算机接受 并按指令正确执行，至于程序能否让人理解并不重要。结构化阶段。6080年代，计算机开始广泛应用于非数值处理领域，数据表 示成为程序设计的重要问题，人们认识到程序设计规范化的重要性， 提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据 结构及抽象数据类型就是在这种情况下形成的。数据结构概念的引 入，对程序设计的规范化起到了重大作用。图灵2奖获得者沃思3给 出了一个著名的公式：数据结构+算法二程序。从这个公式可以 看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件 系统通常是以一个或几个关键数据结构为核心而组织的。随着软件系

10、统的规模越来越大、复杂性不断增加，人们不得不 对结构化技术重新评价。由于软件系统的实现依赖于关键数据结构， 如果这些关键数据结构的一个或几个有所改变，则涉及到整个系统， 甚至导致整个系统彻底崩溃。面向对象阶段。面向对象技术（首先是面向对象程序设计）始于80年代初， 是目前最流行的程序设计技术。在面向对象技术中，问题世界的相 关实体被视为一个对象，对象由属性和方法构成，属性用以描述实体 的状态或特征，方法用以改变实体的状态或描述实体的行为。一组具 有相同属性和方法的对象的集合抽象为类，每个具体的对象都是类的 一个实例。例如，“教师”是一个类，“王老师”、“李老师”等 对象都是“教师”类的实例。由

11、于对象（类）将密切相关的属性（数据）和方法（操作） 定义为一个整体，从而实现了封装和信息隐藏。使用类时，无需了解 其内部的实现细节，一旦数据（结构）修改了，只需修改类内部的局 部代码，软件系统的其余部分无需修改。数据结构主要强调两个方面的内容： 数据之间的关系； 针对这些关系的基本操作。这两个方面实际上蕴涵着面向对象的思 想：类重点描述实体的状态与行为，而数据结构重点描述数据之间的 关系及其基本操作，数据及其相互关系构成了对实体状态的描述，针 对数据元素之间关系的操作构成了对实体行为的描述。由此可见，类与数据结构之间具有对应关系，如图1 - 1所示。图1-1类和数据结构之间的对应关系“数据结构

12、+算法二程序”这个公式在软件开发的进程中 曾产生了深远的影响，但是，它并没有强调数据结构与解决问题的算 法是一个整体，因此有人主张将它修改为“（数据结构+算法）二 程序”，以体现面向对象的思想。值得注意的是，数据结构的发展并未终结。一方面，数据结构 将继续随着程序设计的发展而发展；另一方面，面向各专门领域的数 据结构得到研究和发展，各种实用的高级数据结构被研究出来，各种 空间数据结构也在探索中。三、数据结构的发展并未终结1.数据结构将继续随着程序设计的发展而发展;2.面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中1 克努思（Donald.E.Knuth , 1938年生）从

13、小就是个优秀的学 生，多次获得学业成就奖。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年获图灵奖