数据结构发展史

1、题目：数据结构发展史综述院:电子信息通信工程班 级：122学号： 31吴敏学生姓名:2014年3月15日-JUL.刖s目录错误！未定义书签。第一章 什么是数据结构 错误！未定义书签。第二章数据结构主要研究什么错误！未定义书签。第三章 数据结构的史源 错误!未定义书签。第四章数据结构的飞速发展 错误！未定义书签。第五章 数据结构发展的三阶段 错误!未定义书签。数据结构随着程序设计的发展而发展。错误！未定义书签。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结 构的发错误！未定义书签。错误！未定义书签。错误!未定义书签。展也经历了三个阶段：无结构阶段。第六章数据结构的前

2、景.第二章数据结构主要研究什么错误！未定义书签。第五章 数据结构发展的三阶段 错误!未定义书签。随着计算机科学与技术的不断发展,计算机的应用领域己不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此相应，计算机 处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具 有一 定结构的数据，处理的数据量也越来越大，这就给程序设计带来一个问题： 应如何组织待处理的数据以及数据之间的关系（结构）。数据结构技术从诞生到现在，在不到半个世纪的时间里，形成了坚实的理 论基础、成熟的商业产品和广泛的应用领域，吸引越来越多的研究者加 入。 数据结构的诞生和发展给计算机信息管理带来了一场巨大

3、的革命。三十多年 来，它已成为企业、部门乃至个人日常工作、生产和生活的基础设施。同 时，随着应用的扩展与深入，数据结构的数量和规模越来越大，数据结构的 研究领域也已经大大地拓广和深化了。30年间数据结构领域获得了三次 计算机图灵奖（ Bachman,）,更加充分地说明了数据结构是一个充满活 力和创新精神的领域。就让我们沿着历史的轨迹，追溯一下数据结构的发展 历程。第一章什么是数据结构数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构 分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是 对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式 地定义为（K,

4、 R）（或（D, S）,其中，K是数据元素的有限集，R 是K上的关系的有限集。数据结构是在整个计算机科学与技术领域上广泛被 使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分 数据 构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构 和物理 上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物 理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存 在的形式。数据结构信息的一种组织方式，其目的是为了提高 算法的效率， 它通常与一组算法的集合相对应，通过这组算法集合可以对 数据结构中的数 据进行某种操作。数据结构在计算机中的表示（映像）称 为数据的

5、物理（存 储）结构。它包括数据元素的表示和关系的表示。数据 元素之间的关系有两 种不同的表示方法：顺序映象和非顺序映象，并由此 得到两种不同的存储结 构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结 点存储在物理位銘相邻的存储单元里，结点间的逻 辑关系由存储单元的邻接 关系来体现，由此得到的存储表示称为顺序存储 结构。顺序存储结构是一种 最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存 储方法：它不要求逻辑上相邻的结点在物理 位路上亦相邻，结点间的逻辑关 系是由附加的指针字段表示的。由此得到 的存储表示称为链式存储结构，链 式存储结构通常借助于程序设计语言中

6、的指针类型来实现。索引存储方法： 除建立存储结点信息外，还建立附加 的索引表来标识结点的地址。散列存储 方法：就是根据结点的关键字直接计算出该结点的存储地址。第二章数据结构主要研究什么数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及 对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数 据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于 数据的逻辑结构，算法的实现取决于数据的物理存储结构。其具体的最 主要内容有以下几点：1. 数据的各种逻辑结构和物理结构，以及他们之间的相应关系2. 并对每种结构定义相适应的各种运算3. 设计出相应的算法4. 分析算法的效

7、率第三章数据结构的史源1968年在美国开设。它随着大型程序的出现而出现。“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年美国唐？欧？克努特教授开创了数据结构的最初体系，他所著的计 算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑 结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综 合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之 间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是 非数值性程序设。1968年克努思教授开创了数据结构的最初体系，他所著 的计算机程序设计艺术第一卷基本算法是第一本较系统地阐述数据

8、的逻辑结构和存储结构及其操作的著作。70年代初，数据结构作为一门独 立的课程开始进入大学课堂。数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的 不同而有不同的表述方法。例的数据元素之间的各种联系。这些联系可以通 过定义相关的函数来给出。”他将数据对象（data object ）定义为“一 个数据对象是实例或值的集合”。数据结构在计算机科学界至今没有标准 的定义。个人根据各自的理解的不同而有不同的表述方法。Sartaj Sahni在他的数据结构、算法与应用一书中称：“数据结 构是数据对象，以及存在于该对象的实例和组成实Clifford在数据结构与算法分析一书中的定义是：“数据结构是

9、ADT （抽象数据类型Abstract Data Type）的物理实现。”第四章数据结构的飞速发展自从美国唐欧克努特教授用汇编语言编写的计算机程序设计技巧第一卷基本算法问世以来，己经出现了用Pascal、Java C、C+、C#等语言编写的数据结构方面的书。总体说来，这些语言基本上分为面向过程的语言和面向对象的语言两大类,也出现过采用两种语言描述数据结构的书籍，如C和C+语言描述，但作者实际上是按照C+语言描述。 同时 采用面向过程和面向对象语言描述数据结构，目前国内基本上是空白。 对 于同一种数据结构与算法，同时采用面向过程和面向对象语言进行描述, 可以从中更深刻理解这两种思想的不同，这对于

10、深刻理解计算机语言和思 想 有着重要的作用。c语言是现在最流行的面向过程的语言，在业界使用非 常广泛。而C#语言作为微软在新一代开发平台（.NET）上推岀的、完全面 向对象的语言，凭着其简洁、高效、模板、标准化的特性，使得C#语言像程 序设计语言中的一件艺术品，也吸引着越来越多的开发人员。当然，C#与C是相似的。第五章数据结构发展的三阶段数据结构随着程序设计的发展而发展。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段， 相应地，数据结构的发展也经历了三个阶段：(1)无结构阶段。4060年代，计算机的应用主要针对科学计算，程序设计技术以机 器语言/汇编语言为主，程序处理的数据是纯粹

11、的数值，数据之间的关系 主要是数学公式或数学模型。这一阶段，在人类的自然语言与计算机编程 语言之间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计 人员关注的重心是使程序尽可能地被计算机接受并按指令正确执行，至于 程序能否让人理解并不重要。结构化阶段。6080年代，计算机开始广泛应用于非数值处理领域，数据表示成 为程序设计的重要问题，人们认识到程序设计规范化的重要性，提出了程 序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数 据类型就是在这种情况下形成的。数据结构概念的引入，对程序设计的规 范化起到了重大作用。图灵2奖获得者沃思3给出了一个著名的公 式：数据结构+算法=

12、程序。从这个公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件系统通常是以一个或几个关键 数据结构为核心而组织的。随着软件系统的规模越来越大、复杂性不断增 加，人们不得不对结构化技术重新评价。由于软件系统的实现依赖于关键 数据结构，如果这些关键数据结构的一个或几个有所改变，则涉及到整个 系统，甚至导致整个系统彻底崩溃。面向对象阶段面向对象技术（首先是面向对象程序设计）始于80年代初，是目前 最流行的程序设计技术。在面向对象技术中，问题世界的相关实体被视为 一个对象，对象由属性和方法构成，属性用以描述实体的状态或特征，方 法用以改变实体的状态或描述实体的行为。一组具有相同属性和

13、方法的对 象的集合抽象为类，每个具体的对象都是类的一个实例。例如，教师” 是一个类，“王老师”、“李老师”等对象都是“教师”类的实例。由于对象（类）将密切相关的属性（数据）和方法（操作）定义为 一个整体，从而实现了封装和信息隐藏。使用类时，无需了解其内部的实 现细节，一旦数据（结构）修改了，只需修改类内部的局部代码，软件系 统的其余部分无需修改。第六章数据结构的前景1. 数据结构将继续随着程序设计的发展而发展；2. 面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在 探索中。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。 对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内 存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示； 此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的 效率。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考 虑因素。许多大型系统的构造经验表明，系统实现的困