数据结构发展史.doc

题目:数据结构发展史综述学院:___电子信息_____专业:___通信工程_____班级:___122_____学号:___1208060531____学生姓名:___吴敏_____3月15日目录前言 3第二章数据结构主要研究什么? 6第三章数据结构的史源....... 7第四章数据结构的飞速发展 8第五章数据结构发展的三阶段 9第六章数据结构的前景 11前言随着计算机科学与技术的不断发展,计算机的应用领域已不再局限于科学计算,而更多地应用于控制、管理等非数值处理领域。与此相应,计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据,处理的数据量也越来越大,这就给程序设计带来一个问题:应如何组织待处理的数据以及数据之间的关系(结构)。数据结构技术从诞生到现在,在不到半个世纪的时间里,形成了坚实的理论基础、成熟的商业产品和广泛的应用领域,吸引越来越多的研究者加入。数据结构的诞生和发展给计算机信息管理带来了一场巨大的革命。三十多年来,它已成为企业、部门乃至个人日常工作、生产和生活的基础设施。同时,随着应用的扩展与深入,数据结构的数量和规模越来越大,数据结构的研究领域也已经大大地拓广和深化了。30年间数据结构领域获得了三次计算机图灵奖(,,),更加充分地说明了数据结构是一个充满活力和创新精神的领域。就让我们沿着历史的轨迹,追溯一下数据结构的发展历程。第一章什么是数据结构数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构(物理结构)和数据的运算。数据的逻辑结构是对数据之间关系的描述,有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为(K,R)(或(D,S)),其中,K是数据元素的有限集,R是K上的关系的有限集。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构信息的一种组织方式,其目的是为了提高算法的效率,它一般与一组算法的集合相对应,经过这组算法集合能够对数据结构中的数据进行某种操作。数据结构在计算机中的表示(映像)称为数据的物理(存储)结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。顺序存储方法:它是把逻辑上相邻的结点存储在物理位臵相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,一般借助于程序设计语言中的数组来实现。链接存储方法:它不要求逻辑上相邻的结点在物理位臵上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构一般借助于程序设计语言中的指针类型来实现。索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。第二章数据结构主要研究什么?数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构,以及对数据的各种操作。因此,主要有三个方面的内容:数据的逻辑结构;数据的物理存储结构;对数据的操作(或算法)。一般,算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构。 其具体的最主要内容有以下几点:数据的各种逻辑结构和物理结构,以及她们之间的相应关系 并对每种结构定义相适应的各种运算 设计出相应的算法 。它随着大型程序的出现而出现。  “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年美国唐•欧•克努特教授开创了数据结构的最初体系,她所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不但是一般程序设计(特别是非数值性程序设。1968年克努思教授开创了数据结构的最初体系,她所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。70年代初,数据结构作为一门独立的课程开始进入大学课堂。  数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法。例的数据元素之间的各种联