关闭

关闭

封号提示

内容

首页 算法(第四版).pdf

算法(第四版).pdf

算法(第四版).pdf

上传者: 哈哈混蛋杰西 2014-02-21 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《算法(第四版)pdf》,可适用于高等教育领域,主题内容包含RobertSedgewickKevinWayne美著计算机计算机科学分类建议人民邮电出版社网址:wwwptpresscomcnISBN定价:元Al符等。

RobertSedgewickKevinWayne美著计算机计算机科学分类建议人民邮电出版社网址:wwwptpresscomcnISBN定价:元AlgorithmsFourthEdition算法(第版)AlgorithmsFourthEdition算法(第版)著美RobertSedgewickKevinWayne译谢路云Sedgewick之巨著与高德纳TAOCP一脉相承几十年多次修订经久不衰的畅销书涵盖所有程序员必须掌握的种算法RobertSedgewick 斯坦福大学博士导师为DonaldEKnuth从年开始一直担任普林斯顿大学计算机科学系教授曾任该系主任也是AdobeSystems公司董事会成员曾在XeroxPARC、国防分析研究所(lnstituteforDefenseAnalyses)和法国国家信息与自动化研究所(INRIA)从事研究工作。他的研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。KevinWayne 康奈尔大学博士普林斯顿大学计算机科学系高级讲师研究方向包括算法的设计、分析和实现特别是图和离散优化。本书全面讲述算法和数据结构的必备知识具有以下几大特色。算法领域的经典参考书Sedgewick畅销著作的最新版反映了经过几十年演化而成的算法核心知识体系内容全面全面论述排序、搜索、图处理和字符串处理的算法和数据结构涵盖每位程序员应知应会的种算法全新修订的代码全新的Java实现代码采用模块化的编程风格所有代码均可供读者使用与实际应用相结合在重要的科学、工程和商业应用环境下探讨算法给出了算法的实际代码而非同类著作常用的伪代码富于智力趣味性简明扼要的内容用丰富的视觉元素展示的示例精心设计的代码详尽的历史和科学背景知识各种难度的练习这一切都将使读者手不释卷科学的方法用合适的数学模型精确地讨论算法性能这些模型是在真实环境中得到验证的与网络相结合配套网站algscsprincetonedu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源算法︵第版︶wwwpearsoncom图灵社区:wwwituringcomcn新浪微博:图灵教育图灵社区反馈投稿推荐信箱:contactturingbookcom热线:()转延伸阅读计算机程序设计艺术卷:基本算法(英文版第版)计算机程序设计艺术卷:半数值算法(英文版第版)计算机程序设计艺术卷:排序与查找(英文版第版)计算机程序设计艺术卷A:组合算法(一)(英文版)计算机体系结构:量化研究方法(第版)具体数学:计算机科学基础(第版)编译器设计(第版)图灵程序设计丛书算法(第版)人民邮电出版社北  京谢路云 译美 RobertSedgewick KevinWayne 著Algorithms,FourthEdition内容提要本书作为算法领域经典的参考书全面介绍了关于算法和数据结构的必备知识并特别针对排序、搜索、图处理和字符串处理进行了论述。第版具体给出了每位程序员应知应会的个算法提供了实际代码而且这些Java代码实现采用了模块化的编程风格读者可以方便地加以改造。配套网站提供了本书内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。本书适合用做大学教材或从业者的参考书。图灵程序设计丛书算法(第版)定价:元读者服务热线:()转 印装质量热线:()反盗版热线:()著    美RobertSedgewick KevinWayne译    谢路云责任编辑 朱 巍执行编辑 丁晓昀 刘美英人民邮电出版社出版发行  北京市崇文区夕照寺街号邮编   电子邮件 ptpresscomcn网址 http:wwwptpresscomcn北京      印刷开本: 印张:字数:千字年月第版印数:册年月北京第次印刷著作权合同登记号图字:号ISBN版权声明AuthorizedtranslationfromtheEnglishlanguageedition,entitledAlgorithms,FourthEdition,byRobertSedgewick,KevinWayne,publishedbyPearsonEducation,Inc,publishingasAddisonWesley,CopyrightbyPearsonEducation,IncAllrightsreservedNopartofthisbookmaybereproducedortransmittedinanyformorbyanymeans,electronicormechanical,includingphotocopying,recordingorbyanyinformationstorageretrievalsystem,withoutpermissionfromPearsonEducation,IncCHINESESIMPLIFIEDlanguageeditionpublishedbyPEARSONEDUCATIONASIALTDandPOSTSTELECOMPRESSCopyright本书中文简体字版由PearsonEducationAsiaLtd授权人民邮电出版社独家出版。未经出版者书面许可不得以任何方式复制或抄袭本书内容。本书封面贴有PearsonEducation(培生教育出版集团)激光防伪标签无标签者不得销售。版权所有侵权必究。谨以此书献给Adam、Andrew、Brett、Robbie并特别感谢Linda。RobertSedgewick献给Jackie和Alex。KevinWayne译 者 序在计算机领域算法是一个永恒的主题。即使仅把算法入门方面的书都摆出来国内外的加起来怕是能铺满整个天安门广场。在这些书中有几本尤其与众不同本书就是其中之一。本书是学生的良师。在翻译的过程中我曾无数次感叹:“要是当年我能拥有这本书那该多好!”应该说本书是为在校学生量身打造的。没有数学基础?没关系只要你在高中学过了数学归纳法那么书中以上的数学内容你都可以看得懂更何况书中还辅以大量图例。没学过编程?没关系第章会给大家介绍足够多的Java知识即使你不是计算机专业的学生也不会遇到困难。整本书的内容编排循序渐进由易到难前后呼应足见作者的良苦用心。没有比本书更专业的算法教科书了。本书是老师的好帮手。如果老师们还只能照本宣科只能停留在算法本身一二三四的阶段那就已经大大落后于这个时代了。算法并不仅仅是计算的方法探究算法的过程反映出的是我们对这个世界的认知方法:是唯唯诺诺地将课本当做圣经还是通过“实验失败再实验”循环的锤炼?数学是保证数据是验证。本书通过各种算法从各个角度多次说明了这个道理这也正是第章是全书内容最多的一章的原因。希望每一位读者都不要错过第章。无论你有没有编程基础都会从中得到有益的启示。本书是程序员的益友。在工作了多年之后快速排序、霍夫曼编码、KMP等曾经熟悉的概念在你脑中是不是已经凋零成了一个个没有内涵的名词?是时候重新拾起它们了。无论是为手头的工作寻找线索还是为下一份工作努力准备这些算法基础知识都是你不能跳过的。本书强调软件工程中的最佳实践特别适合已有工作经验的程序员朋友。所有的算法都是先有API再有实现之后是证明最后是数据。这种先接口后实现、强调测试的做法无疑是在工作中摸爬滚打多年的程序员最熟悉的。本书也有一些遗憾比如没有介绍动态规划这样重要的思想。但是瑕不掩玉它仍然是最好的入门级算法书。我强烈地希望能够把本书翻译成中文但同时也诚惶诚恐如履薄冰担心自己的水平不足以准确传达原文的意思。翻译的过程虽然辛苦但我觉得非常值得。感谢人民邮电出版社图灵公司给了我这个机会感谢编辑和审稿专家的细心检查。同时感谢我的妻子朱天的全力支持。译者水平有限bug在所难免还请读者批评指正。谢路云前  言本书力图研究当今最重要的计算机算法并将一些最基础的技能传授给广大求知者。它适合用做计算机科学进阶教材面向已经熟悉了计算机系统并掌握了基本编程技能的学生。本书也可用于自学或是作为开发人员的参考手册因为书中实现了许多实用算法并详尽分析了它们的性能特点和用途。这本书取材广泛很适合作为该领域的入门教材。算法和数据结构的学习是所有计算机科学教学计划的基础但它并不只是对程序员和计算机系的学生有用。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。本书中的算法代表了近年来的大量优秀研究成果是人们工作中必备的知识。从物理中的N体模拟问题到分子生物学中的基因序列问题我们描述的基本方法对科学研究而言已经必不可少从建筑建模系统到模拟飞行器这些算法已经成为工程领域极其重要的工具从数据库系统到互联网搜索引擎算法已成为现代软件系统中不可或缺的一部分。这仅是几个例子而已随着计算机应用领域的不断扩张这些基础方法的影响也会不断扩大。在开始学习这些基础算法之前我们先要熟悉全书中都将会用到的栈、队列等低级抽象的数据类型。然后依次研究排序、搜索、图和字符串方面的基础算法。最后一章将会从宏观角度总结全书的内容。独特之处本书致力于研究有实用价值的算法。书中讲解了多种算法和数据结构并提供了大量相关的信息读者应该能有信心在各种计算环境下实现、调试并应用它们。本书的特点涉及以下几个方面。算法 书中均有算法的完整实现并讨论了程序在多个样例上的运行状况。书中的代码都是可以运行的程序而非伪代码因此非常便于投入使用。书中程序是用Java语言编写的但其编程风格方便读者使用其他现代编程语言重用其中的大部分代码来实现相同算法。数据类型 我们在数据抽象上采用了现代编程风格将数据结构和算法封装在了一起。应用 每一章都会给出所述算法起到关键作用的应用场景。这些场景多种多样包括物理模拟与分子生物学、计算机与系统工程学以及我们熟悉的数据压缩和网络搜索等。学术性 我们非常重视使用数学模型来描述算法的性能。我们用模型预测算法的性能然后在真实的环境中运行程序来验证预测。广度 本书讨论了基本的抽象数据类型、排序算法、搜索算法、图及字符串处理。我们在算法的讨论中研究数据结构、算法设计范式、归纳法和解题模型。这将涵盖世纪年代以来的经典方法以及近年来产生的新方法。我们的主要目标是将今天最重要的实用算法介绍给尽可能广泛的群体。这些算法一般都十分巧妙奇特行左右的代码就足以表达。它们展现出的问题解决能力令人叹为观止。没有它们创造计算智能、解决科学问题、开发商业软件都是不可能的。本书网站本书的一个亮点是它的配套网站algscsprincetonedu。这一网站面向教师、学生和专业人士免费提供关于算法和数据结构的丰富资料。一份在线大纲 包含了本书内容的结构并提供了链接浏览起来十分方便。全部实现代码 书中所有的代码均可以在这里找到且其形式适合用于程序开发。此外还包括算法的其他实现例如高级的实现、书中提及的改进的实现、部分习题的答案以及多个应用场景的客户端代码。我们的重点是用真实的应用环境来测试算法。习题与答案 网站还提供了一些附加的选择题(只需要一次单击便可获取答案)、很多算法应用的例子、编程练习和答案以及一些有挑战性的难题。动态可视化 书是死的但网站是活的在这里我们充分利用图形类演示了算法的应用效果。课程资料 网站包含和本书及网上内容对应的一整套幻灯片以及一系列编程作业、核对表、测试数据和备课手册。相关资料链接 网站包含大量的链接提供算法应用的更多背景知识以及学习算法的其他资源。我们希望这个站点和本书互为补充。一般来说建议读者在第一次学习某种算法或是希望获得整体概念时看书并把网站作为编程时的参考或是在线查找更多信息的起点。作为教材本书为计算机科学专业进阶的教材涵盖了这门学科的核心内容并能让学生充分锻炼编程、定量推理和解决问题等方面的能力。一般来说此前学过一门计算机方面的先导课程就足矣只要熟悉一门现代编程语言并熟知现代计算机系统就都能够阅读本书。虽然本书使用Java实现算法和数据结构但其代码风格使得熟悉其他现代编程语言的人也能看懂。我们充分利用了Java的抽象性(包括泛型)但不会依赖这门语言的独门特性。书中涉及的多数数学知识都有完整的讲解(少数会有延伸阅读)因此阅读本书并不需要准备太多数学知识不过有一定的数学基础当然更好。应用场景都来自其他学科的基础内容同样也在书中有完整介绍。本书涉及的内容是任何准备主修计算机科学、电气工程、运筹学等专业的学生应了解的基础知识并且对所有对科学、数学或工程学感兴趣的学生也十分有价值。前  言VII背景介绍这本书意在接续我们的一本基础教材《Java程序设计:一种跨学科的方法》那本书对计算机领域做了概括性介绍。这两本书合起来可用做两到三个学期的计算机科学入门课程教材为所有学生在自然科学、工程学和社会科学中解决计算问题提供必备的基础知识。本书大部分内容来自Sedgewick的算法系列图书。本质上本书和该系列的第版和第版最接近但还包含了作者多年教学和学习的经验。Sedgewick的《C算法(第版)》、《C算法(第版)》、《Java算法(第版)》更适合用做参考书或是高级课程的教材而本书则是专门为大学一、二年级学生设计的一学期教材也是最新的基础入门书或从业者的参考书。致谢本书的编写花了近年时间因此想要一一列出所有参与人是不可能的。本书的前几版一共列出了好几十人其中包括(按字母顺序)AndrewAppel、TrinaAvery、MarcBrown、LynDupré、PhilippeFlajolet、TomFreeman、DaveHanson、JanetIncerpi、MikeSchidlowsky、SteveSummit和ChrisVanWyk。我要感谢他们所有人尽管其中有些人的贡献要追溯到几十年前。至于第版我们要感谢试用了本书样稿的普林斯顿及其他院校的数百名学生以及通过本书网站发表意见和指出错误的世界各地的读者。我们还要感谢普林斯顿大学对于高质量教学的坚定支持这是本书得以面世的基础。PeterGordon几乎从本书写作之初就提出了很多有用的建议这一版奉行的“归本溯源”的指导思想也是他最早提出的。关于第版我们要感谢BarbaraWood认真又专业的编辑工作JulieNahil对生产过程的管理以及Pearson出版公司中为本书的付梓和营销辛勤工作的朋友。所有人都在积极地追赶进度而本书的质量并没有受到丝毫影响。VIII前  言目  录第章基础 基础编程模型 Java程序的基本结构 原始数据类型与表达式语句简便记法数组静态方法API字符串输入输出二分查找展望数据抽象使用抽象数据类型抽象数据类型举例抽象数据类型的实现更多抽象数据类型的实现数据类型的设计背包、队列和栈API集合类数据类型的实现链表综述算法分析科学方法观察数学模型增长数量级的分类设计更快的算法倍率实验注意事项处理对于输入的依赖内存展望案例研究:unionfind算法动态连通性实现展望第章排序初级排序算法游戏规则选择排序插入排序排序算法的可视化比较两种排序算法希尔排序归并排序原地归并的抽象方法自顶向下的归并排序自底向上的归并排序排序算法的复杂度快速排序基本算法性能特点算法改进优先队列API初级实现堆的定义堆的算法堆排序应用将各种数据排序我应该使用哪种排序算法问题的归约排序应用一览第章 查找 符号表 API 有序符号表 用例举例 无序链表中的顺序查找 有序数组中的二分查找 对二分查找的分析 预览 二叉查找树 基本实现 分析 有序性相关的方法与删除操作 平衡查找树 查找树 红黑二叉查找树 实现 删除操作 红黑树的性质 散列表 散列函数 基于拉链法的散列表 基于线性探测法的散列表 调整数组大小 内存使用 应用 我应该使用符号表的哪种实现 集合的API 字典类用例 索引类用例 稀疏向量第章图无向图术语表表示无向图的数据类型深度优先搜索寻找路径广度优先搜索连通分量符号图总结有向图术语有向图的数据类型有向图中的可达性环和有向无环图有向图中的强连通性总结最小生成树原理加权无向图的数据类型最小生成树的API和测试用例Prim算法Prim算法的即时实现Kruskal算法展望最短路径最短路径的性质加权有向图的数据结构最短路径算法的理论基础Dijkstra算法无环加权有向图中的最短路径算法一般加权有向图中的最短路径问题展望第章字符串字符串排序键索引计数法低位优先的字符串排序高位优先的字符串排序三向字符串快速排序字符串排序算法的选择单词查找树单词查找树单词查找树的性质三向单词查找树三向单词查找树的性质应该使用字符串符号表的哪种实现子字符串查找历史简介暴力子字符串查找算法X目  录X目  录KnuthMorrisPratt子字符串查找算法BoyerMoore字符串查找算法RabinKarp指纹字符串查找算法总结正则表达式使用正则表达式描述模式缩略写法正则表达式的实际应用非确定有限状态自动机模拟NFA的运行构造与正则表达式对应的NFA数据压缩游戏规则读写二进制数据局限热身运动:基因组游程编码霍夫曼压缩第章背景索引目  录XI目  录XI本书的目的是研究多种重要而实用的算法即适合用计算机实现的解决问题的方法。和算法关系最紧密的是数据结构即便于算法操作的组织数据的方法。本章介绍的就是学习算法和数据结构所需要的基本工具。首先要介绍的是我们的基础编程模型。本书中的程序只用到了Java语言的一小部分以及我们自己编写的用于封装输入输出以及统计的一些库。节总结了相关的语法、语言特性和书中将会用到的库。接下来我们的重点是数据抽象并定义抽象数据类型(ADT)以进行模块化编程。在节中我们介绍了用Java实现抽象数据类型的过程包括定义它的应用程序编程接口(API)然后通过Java的类机制来实现它以供各种用例使用。之后作为重要而实用的例子我们将学习三种基础的抽象数据类型:背包、队列和栈。节用数组、变长数组和链表实现了背包、队列和栈的API它们是全书算法实现的起点和样板。性能是算法研究的一个核心问题。节描述了分析算法性能的方法。我们的基本做法是科学式的即先对性能提出假设建立数学模型然后用多种实验验证它们必要时重复这个过程。我们用一个连通性问题作为例子结束本章它的解法所用到的算法和数据结构可以实现经典的unionfind抽象数据结构。算法编写一段计算机程序一般都是实现一种已有的方法来解决某个问题。这种方法大多和使用的编程语言无关它适用于各种计算机以及编程语言。是这种方法而非计算机程序本身描述了解决问题的步骤。在计算机科学领域我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。算法是计算机科学的基础是这个领域研究的核心。要定义一个算法我们可以用自然语言描述解决某个问题的过程或是编写一段程序来实现这个过程。如发明于多年前的欧几里德算法所示其目的是找到两个数的最大公约数:自然语言描述计算两个非负整数p和q的最大公约数:若q是则最大公约数为p。否则将p除以q得到余数rp和q的最大公约数即为q和r的最大公约数。Java语言描述Publicstaticintgcd(intp,intq){if(q==)returnpintr=pqreturngcd(q,r)}欧几里德算法第章基础~第章 基  础如果你不熟悉欧几里德算法那么你应该在学习了节之后完成练习和练习。在本书中我们将用计算机程序来描述算法。这样做的重要原因之一是可以更容易地验证它们是否如所要求的那样有限、确定和有效。但你还应该意识到用某种特定语言写出一段程序只是表达一个算法的一种方法。数十年来本书中许多算法都曾被表达为多种编程语言的程序这正说明每种算法都是适合于在任何计算机上用任何编程语言实现的方法。我们关注的大多数算法都需要适当地组织数据而为了组织数据就产生了数据结构数据结构也是计算机科学研究的核心对象它和算法的关系非常密切。在本书中我们的观点是数据结构是算法的副产品或是结果因此要理解算法必须学习数据结构。简单的算法也会产生复杂的数据结构相应地复杂的算法也许只需要简单的数据结构。本书中我们将会研讨许多数据结构的性质也许本书就应该叫《算法与数据结构》。当用计算机解决一个问题时一般都存在多种不同的方法。对于小型问题只要管用方法的不同并没有什么关系。但是对于大型问题(或者是需要解决大量小型问题的应用)我们就需要设计能够有效利用时间和空间的方法了。学习算法的主要原因是它们能节约非常多的资源甚至能够让我们完成一些本不可能完成的任务。在某些需要处理上百万个对象的应用程序中设计优良的算法甚至可以将程序运行的速度提高数百万倍。在本书中我们将在多个场景中看到这样的例子。与此相反花费金钱和时间去购置新的硬件可能只能将速度提高十倍或是百倍。无论在任何应用领域精心设计的算法都是解决大型问题最有效的方法。在编写庞大或者复杂的程序时理解和定义问题、控制问题的复杂度和将其分解为更容易解决的子问题需要大量的工作。很多时候分解后的子问题所需的算法实现起来都比较简单。但是在大多数情况下某些算法的选择是非常关键的因为大多数系统资源都会消耗在它们身上。本书的焦点就是这类算法。我们所研究的基础算法在许多应用领域都是解决困难问题的有效方法。计算机程序的共享已经变得越来越广泛尽管书中涉及了许多算法我们也只实现了其中的一小部分。例如Java库包含了许多重要算法的实现。但是实现这些基础算法的简化版本有助于我们更好地理解、使用和优化它们在库中的高级版本。更重要的是我们经常需要重新实现这些基础算法因为在全新的环境中(无论是硬件的还是软件的)原有的实现无法将新环境的优势完全发挥出来。在本书中我们的重点是用最简洁的方式实现优秀的算法。我们会仔细地实现算法的关键部分并尽最大努力揭示如何进行有效的底层优化工作。为一项任务选择最合适的算法是困难的这可能会需要复杂的数学分析。计算机科学中研究这种问题的分支叫做算法分析。通过分析我们将要学习的许多算法都有着优秀的理论性能而另一些我们则只是根据经验知道它们是可用的。我们的主要目标是学习典型问题的各种有效算法但也会注意比较不同算法之间的性能差异。不应该使用资源消耗情况未知的算法因此我们会时刻关注算法的期望性能。本书框架接下来概述一下全书的主要内容给出涉及的主题以及本书大致的组织结构。这组主题触及了尽可能多的基础算法其中的某些领域是计算机科学的核心内容通过对这些领域的深入研究我们找出了应用广泛的基本算法而另一些算法则来自计算机科学和相关领域比较前沿的研究成果。总之本书讨论的算法都是数十年来研发的重要成果它们将继续在快速发展的计算机应用中扮演重要角色。第章 基  础第章 基础它讲解了在随后的章节中用来实现、分析和比较算法的基本原则和方法包括Java编程模型、数据抽象、基本数据结构、集合类的抽象数据类型、算法性能分析的方法和一个案例分析。第章 排序有序地重新排列数组中的元素是非常重要的基础算法。我们会深入研究各种排序算法包括插入排序、选择排序、希尔排序、快速排序、归并排序和堆排序。同时我们还会讨论另外一些算法它们用于解决几个与排序相关的问题例如优先队列、选举以及归并。其中许多算法会成为后续章节中其他算法的基础。第章 查找从庞大的数据集中找到指定的条目也是非常重要的。我们将会讨论基本的和高级的查找算法包括二叉查找树、平衡查找树和散列表。我们会梳理这些方法之间的关系并比较它们的性能。第章 图图的主要内容是对象和它们的连接连接可能有权重和方向。利用图可以为大量重要而困难的问题建模因此图算法的设计也是本书的一个主要研究领域。我们会研究深度优先搜索、广度优先搜索、连通性问题以及若干其他算法和应用包括Kruskal和Prim的最小生成树算法、Dijkstra和BellmanFord的最短路径算法。第章 字符串字符串是现代应用程序中的重要数据类型。我们将会研究一系列处理字符串的算法首先是对字符串键的排序和查找的快速算法然后是子字符串查找、正则表达式模式匹配和数据压缩算法。此外在分析一些本身就十分重要的基础问题之后这一章对相关领域的前沿话题也作了介绍。第章 背景这一章将讨论与本书内容有关的若干其他前沿研究领域包括科学计算、运筹学和计算理论。我们会介绍性地讲一下基于事件的模拟、B树、后缀数组、最大流量问题以及其他高级主题以帮助读者理解算法在许多有趣的前沿研究领域中所起到的巨大作用。最后我们会讲一讲搜索问题、问题转化和NP完全性等算法研究的支柱理论以及它们和本书内容的联系。学习算法是非常有趣和令人激动的因为这是一个历久弥新的领域(我们学习的绝大多数算法都还不到“五十岁”有些还是最近才发明的但也有一些算法已经有数百年的历史)。这个领域不断有新的发现但研究透彻的算法仍然是少数。本书中既有精巧、复杂和高难度的算法也有优雅、朴素和简单的算法。在科学和商业应用中我们的目标是理解前者并熟悉后者这样才能掌握这些有用的工具并学会算法式思考以迎接未来计算任务的挑战。第章 基  础 基础编程模型我们学习算法的方法是用Java编程语言编写的程序来实现算法。这样做是出于以下原因:‰程序是对算法精确、优雅和完全的描述‰可以通过运行程序来学习算法的各种性质‰可以在应用程序中直接使用这些算法。相比用自然语言描述算法这些是重要而巨大的优势。这样做的一个缺点是我们要使用特定的编程语言这会使分离算法的思想和实现细节变得困难。我们在实现算法时考虑到了这一点只使用了大多数现代编程语言都具有且能够充分描述算法所必需的语法。我们仅使用了Java的一个子集。尽管我们没有明确地说明这个子集的范围但你也会看到我们只使用了很少的Java特性而且会优先使用大多数现代编程语言所共有的语法。我们的代码是完整的因此希望你能下载这些代码并用我们的测试数据或是你自己的来运行它们。我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。本节以及节会详细说明这个模型相关内容自成一体主要是作为文档供读者查阅以便理解本书的代码。我们的另一本入门级的书籍AnIntroductiontoProgramminginJava:AnInterdisciplinaryApproach也使用了这个模型。作为参考图所示的是一个完整的Java程序。它说明了我们的基础编程模型的许多基本特点。在讨论语言特性时我们会用这段代码作为例子但可以先不用考虑代码的实际意义(它实现了经典的二分查找算法并在白名单过滤应用中对算法进行了检验请见

职业精品

精彩专题

上传我的资料

热门资料

资料评价:

/ 129
所需积分:0 立即下载

意见
反馈

返回
顶部

Q