资源描述：
《算法的本质new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Articlesof兮软算法+数据结构的本质2011-09-2016:09:44minlearnTOC1何谓数据结构1.1数据结构的产生1.2作为实现模式1.3数据结构与算法的关系2数据结构用于编程2.1数据结构与数据抽象2.2数据与数据属性2.3用ADT来表达数据结构何谓数据结构数据结构是什么?它是组织内存中对象或基本类型数值(primtivetypes)的形式,为了更好地组织和使用这些对象而慢慢发展起来的固有形式,惯用法(idioms),是计算机开发领域用处理数据的方法来解决问题的一套科学.对数据结
2、构知识的系统整理最初源于一个科学者的一本书1.以上是常见于一些教科书上对数据结构与算法的定义。所有这些，是针对数据结构已经被具化了，跟语言结合之后的概念，它其实首先是作为解决平台，问题，语言问题的工程模式中的一种模式而存在。所以，这些概念并没有从它的本质上去说明未必太流于浅层，。比如，它使初学者不能把握一些明显的东西。比如，为什么要提出数据结构与算法？可以不提出这样一个东西吗？它处于开发的什么层次？数据结构的产生它其实是用数学的眼光来解决问题的一种模式，这才是谈到数据结构时首先要谈到的话题。这其实涉及到
3、计算机的产生和计算机软件的产生这个话题。数学与计算机科学的关系可以比喻为母子关系,计算机的产生源于19世纪时的一次数学危机,当时,人们发现数学不能完全表达为一些”形式”,换言之,数学是不能被形式化的,它还具有某些感性的部分,这个历史是这样的:希尔伯特为了发展欧式几何公理体系的严密性(大约从中学开始,我们就已经见识到了欧式几何的全部,值得注意的是,欧几里德在公元前300年前,就整个地完成了这里面全部的成果),而定义了一套新的”公理体系.这个公理体系就被叫做希尔伯特公理体”.它企图用一套纯粹形式化,不具有逻
4、辑关系的推理体系来表达整个数学.它假设,任何数学课题,都可以用某一套形式化的东西给推导出来.这些推导过程只需要是根据已有的公理,进行纯形式上的复合(而不需要联系关乎它们的相关数学逻辑)得出的新的公理.无疑,这样的计划是具有非凡的意义的.这个体系对后来数学的展开的确起了很大的作用,产生了一些好的成果,只是,人们也无法确定这个工作本身是不是足够严密的.后来出现了一个叫康托尔的人,它运用泛集合论的方法,”造性地将一一对应和对角线方法运用到无穷集合理论的建立当中”,康托尔的工作,对后来者的工作起了一个承上启下的
5、作用.源于康氏的工作,哥德尔后来提出了”不完备性理论”,这个理论结果直接推翻了希尔伯特的体系,只是希尔伯特公理体系已经产生了非常好的数学成果,人们一时陷于恐慌,这就给整个数学造成了一次”危机”,这就是被称为第三次数学危机的事情.但是危机归危机,形式化数学的工作还是在继续,为了不走进哥德尔的陷阱,只需使”算法”(形式化了的数学步骤)努力避开哥德尔专门设置的陷阱和假设就可以了,身为数学家和破码专家的图灵,后来就从数学上”建立了计算机最初的工作原理”的成果(值得注意的是,它是数学意义上的,所以是”计算机科学”
6、),冯诺伊曼完善了它,最终从物理上造出了这样一台机器.图灵就是计算机数学之父(计算机科学之父),而冯氏,是计算机器之父.其实在那个时候,与图灵一道,另一个叫丘奇的人,也提出一套lisp数学体系(它也可以被用来制造计算机,后来的确也产生了lisp机),这二大体系,它们的区别应该首先是体现在数学上,然后才体系在其各自对计算机的意义上(图灵的抽象机更易产生出物理的机器,而丘奇的太过于注重数学上的美感.)那么计算机能执行的算法会是什么样的呢?首先,它必须不能是哥德尔式的.不能有缪论的发生,对于这种算法要被形式化
7、的要求,它一定能具有有限的步骤,即复杂性理论要保证在多项式内完成,对于某个输入,一定要产生某个结果,一定要使计算机在有限步之后停机.所有这些,都是科学上的事情了..这篇文章,只是让你能对当时的历史有所理解,并体会到,在纯科学上,计算机这个东西,是吸着数学的乳汁长大的.所以，代表计算机科学的,不是计算机编程科学,,而是与数学密切联系处的算法科学,即实现计算机的科学，宏大的《theartofcomputerprogramming》讲述的全是算法和数学相关的理论.编程部分比例几乎没有.于是，当用数学，和机器的
8、眼光直面解决问题的时候（而不是语言映射手段，那处在开发层次，而不是实现层次，只是语言映射也可以被用来实现而已，即系统编程语言和系统编程）,很自然地就产生了一门学科,即数据结构和算法。作为实现模式数据结构属于解决平台，问题，语言三种模式中的一种，即实现模式。我们在前言中说到，数据结构与语言映射虽然都可以被于编程的形式体现，然而，数据结构是解决问题的问题，而语言映射是解决映射问题的问题。算法提供了一种用语言来进行设计的手段,是实现抽象,当你不知
