算法数据结构程序

《算法数据结构程序》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法+数据结构=程序--评《数据结构、算法与应用--C++语言描述》　　记得Pascal之父、结构化程序设计的先驱NiklausWirth最著名的一本书，书名叫作《算法+数据结构=程序》，算法与数据结构之于程序设计的重要性不言自明。那么，什么是算法？什么是数据结构？什么又是程序呢？　　我们先从阐明大家最为熟悉的"程序"的概念入手。程序是计算机指令的某种组合，控制计算机的工作流程，完成一定的逻辑功能，以实现某种任务；再来看什么是算法，算法是程序的逻辑抽象，是解决某类客观问题的数学过程；最后我们来看一看数据结构又是什么呢？在这

2、里，数据结构具有两个层面上的涵义--逻辑结构和物理结构：客观事物自身所具有的结构特点，我们将其称之为逻辑结构。如家族谱系是一个天然的树型逻辑结构。而逻辑结构在计算机中的具体实现则称之为物理结构。如树型逻辑结构是用指针表示还是使用数组实现。　　仔细体会一下，就会发现算法与数据结构间的紧密性。用一个较为贴切的例子来形容，若把数据结构喻为建筑工程中的建筑设计图，那么算法就是工程中的施工流程图。数据结构与算法呈相互依托的关系，恰当的确立了问题的结构，问题的解决才能根据确立的层次结构选择合适的解决方法。因此任何讲解数据结构的书都不可

3、能撇开算法，单单介绍数据结构，反之亦然。下面，我们就来看看IEEE'97Booth教育奖获得者SartajSahni是如何处理数据结构、算法和程序他们三者之间的关系的吧！　　一般来说，计算机专业著作有两种基本写作方式：一种是教材，一种是百科全书。本书是按照大学教材的结构来写的，然而令人惊讶的是本书的内容是如此的丰富，以至于同样可以将它看作是一本关于数据结构与算法的大全。显然，这本书并不适合初学，将它作为数据结构进阶学习的第二本书是恰当的。这本书最为显著的特点是特别注重应用，我们很快就会看到这一点。　　首先，我们来看一看《数

4、据结构、算法与应用--C++语言描述》这本书的组织结构。书由三个部分组成：预备知识、数据结构和算法设计。　　第一部分预备知识回顾了具备面向对象特性的C++语言的重要特征。因为不是在介绍C++语言，这里的回顾和前提引入直接切入到了C++中许多重要而又易被忽略以至于显得较为模糊的概念。参数传递、函数返回、模板、递归还有操作符重载等等，如若在以前学习C++时，对其理解不是十分深入的话，你是否清楚在什么样的情形下函数返回引用更为合适呢？随后探讨程序时空复杂性的分析、测量与渐进符号（Ο、Ω、Θ、ο），为后面的算法分析内容建立基础。较

5、为特别的是，作者提早在第一部分就讲述了程序设计中的一些基本设计方法：简单的排序与搜索算法、多项式求值和矩阵运算。这样做是要冒风险的（对基础差一些的读者来说就会觉得难度较大），不过作者深厚的写作功力使其显得自然而又恰如其分。　　第二部分数据结构是本书的主体，阐述线性表、数组、矩阵、堆栈、队列、跳跃表、散列、二叉树、优先队列、竞赛树、搜索树还有图。与一般的数据结构书不同，这里采用了四种不同的数据描述方法：公式化描述、链接描述、间接寻址和模拟指针。随着学习的深入，你很快就可以发现相同的逻辑结构，其物理结构的实现竟是如此的不同。而

6、不同的物理结构又各自存在着自己的优缺点，这是由不同的物理结构的自身特点所决定的。例如：使用数组实现的线性表可直接存取元素，然而元素插入与删除的效率却特别低；而若线性表采用链表描述，则正好与顺序表的优缺点相反。若欲博采众长，就必须设计或是选择更为复杂的数据结构，这又为算法设计带来了更多的麻烦。而且，整体结构和具体实现会显得不是那么清晰与自然，甚至会变得非常的难于理解。　　学习数据结构的诀要就在于掌握基本的数据结构，在解决现实问题时选择合适的结构或设计更为恰当的模型，然后根据确立的结构特性编写出算法。　　我们前面提到的关于本书

7、最为独特的地方就在于它特别强调应用。这一特色，就表现在这第二部分中。书中给出了大量来自不同领域的应用：布线路由、元件折叠、电路板排列、LZW压缩编码、迷宫问题、工厂仿真、货箱装船、LPT调度、货郎担问题…这些具体问题的实现不仅使学习充满了乐趣，而且所选择出来的典型实例对于我们解决现实问题具有很强的指导作用。同时，这些经典实例的实现能够大幅度提高我们阅读和编写复杂的大型程序的能力。我们的程序设计能力和算法思维能力的提高，正是建立在对基本数据结构和算法原理的理解以及阅读中、大型程序源代码的基础上的。　　本书的第三部分侧重于计算

8、机算法的分析与实现。书中提供了五种基本的算法设计方法：贪婪算法、分而治之算法、动态规划、回溯和分支定界。由于这里已经是书末，读者的基础知识已经相当的充实，故而本部分也是本书最难的地方。算法的定义采用了正式的数学定义，有算法引论或组合数学基础的读者会更容易理解一些。　　正如文前所述，这里更强调的是问题的解