第二话:数据结构的历史与来由

正视数据结构的历史
服务器君一共花费了356.712 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

一些数据结构的历史

  • 有句话是这么说的,程序 = 数据 + 算法。这里的数据,是数据结构吗?
  • 不完全对噢。记得Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书,书名叫作《算法+数据结构=程序》,所以我觉得这里的数据应该是数据结构才对。

算法与数据结构之于程序设计的重要性不言自明。那么,什么是算法?什么是数据结构?什么又是程序呢?

  • 我们先从阐明大家最为熟悉的“程序”的概念入手。程序是计算机指令的某种组合,控制计算机的工作流程,完成一定的逻辑功能,以实现某种任务;
  • 再来看什么是算法,算法是程序的逻辑抽象,是解决某类客观问题的数学过程;
  • 最后我们来看一看数据结构又是什么呢?在这里,数据结构具有两个层面上的涵义--逻辑结构和物理结构:客观事物自身所具有的结构特点,我们将其称之为逻辑结构。如家族谱系是一个天然的树型逻辑结构。而逻辑结构在计算机中的具体实现则称之为物理结构。如树型逻辑结构是用指针表示还是使用数组实现。 

仔细体会一下,就会发现算法与数据结构间的紧密性。用一个较为贴切的例子来形容,若把数据结构喻为建筑工程中的建筑设计图,那么算法就是工程中的施工流程图。数据结构与算法呈相互依托的关系,恰当的确立了问题的结构,问题的解决才能根据确立的层次结构选择合适的解决方法。因此任何讲解数据结构的书都不可能撇开算法,单单介绍数据结构,反之亦然。

  • 那就是说,程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。
  • 是的。早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。
  • 可现实中,我们更多的不是解决数值计算的问题,而是需要一些更科学有效的手段(比如表、树和图等数据结构)的帮助,才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

1968年,美国的高德纳(DonaU E. Knuth)教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统地阐述了数据的逻辑结构和存储结构及其操作, 开创了数据结构的课程体系。同年,数据结构作为一门独立的课程,在计算机科学的学位课程中开始出现。也就是说,那之后计算机相关专业的学生开始接受《数据结构》的“折磨”其实应该是享受才对。

之后,70年代初,出现了大型程序,软件也开始相对独立,结构程序设计成为程序设计方法学的主要内容,人们越来越重视“数据结构”。

延伸阅读

此文章所在专题列表如下:

  1. 第一话:你的数据结构怎么学的?
  2. 第二话:数据结构的历史与来由
  3. 第三话:关于数据结构的一些概念
  4. 第四话:数据的逻辑结构
  5. 第五话:数据的物理结构
  6. 第六话:关于数据类型
  7. 第七话:抽象数据类型ADT
  8. 第八话:补充数据结构基本概念的关系
  9. 第九话:数据结构与算法的关系
  10. 第10话:什么是算法?
  11. 第11话:算法的五个基本特征
  12. 第12话:什么样的算法才是好算法
  13. 第13话:算法的性能分析
  14. 第14话:如何计算算法的时间复杂度
  15. 第15话:算法的最坏情况与平均情况
  16. 第16话:算法的空间复杂度

本文地址:http://www.nowamagic.net/librarys/veda/detail/2175,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2175

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《致加西亚的信》 阿尔伯特·哈伯德(Hubbard.E.) (作者), 赵立光 (译者), 艾柯 (译者)

《致加西亚的信(经典盒装版)》内容简介:美西战争爆发以后,美国必须立即与古巴起义军首领加西亚取得联系,并获得他的合作。但当时,加西亚身在古巴的深山里——没有人知道他的确切地点,所以没法与他取得联系。这时,有人向总统推荐一个名叫罗文的人,说他有办法找到加西亚,而且也只有他才能找得到。他们找来罗文,交给他一封写给加西亚的信。三周后,罗文徒步走过一个危机四伏的国家,最终把那封信交给了加西亚。 此后,罗文的事迹被传为佳话,“送信”成为了敬业、忠诚、勤奋的象征,罗文便成了每个领导都想找到的人和每个员工都应该学习和效仿的榜样。

更多计算机宝库...