探秘算法世界、求索数据结构之道
汇集经典问题、畅享编程技法之趣
点拨求职热点、敲开业界名企之门
探秘算法世界、求索数据结构之道
汇集经典问题、畅享编程技法之趣
点拨求职热点、敲开业界名企之门
本书以现代计算机常用的十八种数据结构为线索,结合C++中的STL编程实践,详细介绍了四大算法设计思想(贪心法、动态规划、分治法、回溯法)、二十大经典问题和四十二个重要算法。具体涉及的数本书围绕算法与数据结构这个话题,循序渐进、深入浅出地介绍了现代计算机技术中常用的40余个经典算法,以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中,本书也系统地讲解了链表(包括单向链表、单向循环链表和双向循环链表)、栈、队列(包括普通队列和优先级队列)、树
(包括二叉树、哈夫曼树、堆、红黑树、AVL树和字典树)、图、集合(包括不相交集)与字典等常用数据结构。同时,通过对22个经典问题(包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等)的讲解,逐步揭开隐匿在数据结构背后的算法原理,力图帮助读者夯实知识储备,激活思维技巧,并最终冲破阻碍编程能力提升的重重藩篱。
左飞,服务于中国规模较大的移动通信运营商,业余时间他撰写了多部计算机方面的著作,并译有《编码》、《提高C++性能的编程技术》等经典名著。
第1 章 从数据到算法 .................................................................. 1
本章参考文献 ................................................................................................ 23
第2 章 指针与数组——也谈中国古代兵制 ................................ 24
本章参考文献 ................................................................................................ 61
第3 章 字符串与模式匹配——梦里寻她千百度 ......................... 62
本章参考文献 ................................................................................................ 89
第4 章 链表——老鹰捉小鸡 ..................................................... 91
本章参考文献 .............................................................................................. 126
第5 章 先进先出与后进先出——简单而深刻 .......................... 127
本章参考文献 .............................................................................................. 158
第6 章 递归——老和尚讲故事 ................................................ 159
本章参考文献 .............................................................................................. 183
第7 章 树——从红楼梦说起 ................................................... 184
本章参考文献 .............................................................................................. 230
第8 章 图——始于哥尼斯堡的七桥问题 .................................. 231
本章参考文献 .............................................................................................. 283
第9 章 树形搜索结构——做一名出色的园艺师 ....................... 284
本章参考文献 .............................................................................................. 320
第10 章 集合与字典——再言搜索之话题 ............................... 321
本章参考文献 .............................................................................................. 374
第11 章 排序——有序让世界更美好 ....................................... 375
本章参考文献 .............................................................................................. 407
附录 经典求职面试题目 .......................................................... 408
2014 年的冬天,一部讲述计算机科学之父艾伦?图灵传奇人生的传记电影在美国上映,这部影片就是《模仿游戏》。次年,该片荣获第87 届奥斯卡金像奖最佳改编剧本奖,以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的7 项提名,一时风光无限。尽管现代计算机已经无处不在,但因图灵的时代离我们过于久远,现今人们对他的研究工作已经知之甚少。
要说起图灵的贡献,我们还得把时间再往前推。1900 年,德国数学家大卫?希尔伯特在巴黎举行的国际数学家大会上做了题为《数学问题》的演讲,在这篇重要的演讲中,他提出了著名的希尔伯特之23 个问题。尽管此后的数学发展远远超过了希尔伯特的预料,但他所提出的23 个问题仍然对20 世纪的数学发展起到了非常积极的推动作用。
希尔伯特的第10 个问题是要设计一个算法来测试多项式是否有整数根。他没有使用算法这个术语,而是采用了下面这种表述:“通过有限多次运算就可以决定的过程”。有意思的是,从希尔伯特对这个问题的陈述可以看出,他明确地要求设计一个算法。因此,他显然是假设这样的算法是存在的,人们所要做的只是找到它。现在我们知道,这个任务是无法完成的,即它是算法上不可解的。但对那个时期的数学家来说,以他们对算法的直观认识,得出这样的结论是不可能的。
非形式地说,算法是为实现某个任务而构造的简单指令集。以日常用语来说,算法又称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学文献中就包含有执行各种各样计算任务的算法描述。例如,我国古代数学经典《九章算术》中就记述了包括求最大公约数、最小公倍数、开平方根、开立方根等在内的诸多算法。现代计算机科学中更是充满了各种各样的算法。例如,求解最短路径的狄克斯特拉算法,进行字符串匹配的KMP 算法等。
虽然算法在数学中已有很长的历史,但在20 世纪之前,算法概念本身一直没有精确的定义。数学家们面对希尔伯特的第10 个问题,显得束手无策。由于缺乏对于算法本身的精确定义,所以要证明某个特定任务不存在算法则完全不可能。要想破解希尔伯特的第10 个问题,人们不得不等待算法之精确定义的出现。
直到1936 年,曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中之应用》的论文。该文最终于1937 年正式发表,并立即引起了广泛的注意。在论文中,图灵描述了一种可以辅助数学研究的机器,也就是后来被称为“图灵机”的抽象系统。与此同时,另外一位数学家阿隆佐?丘奇也独立地提出了另外一套系统,即所谓的λ演算。图灵采用他的图灵机来定义算法,而丘奇则采用λ演算来定义算法,后来图灵证明这两个定义是等价的。由此,人们在算法的非形式概念和精确定义之间建立了联系,即算法的直觉概念等价于图灵机算法,这就是所谓的丘奇-图灵论题。
丘奇-图灵论题提出的算法定义是解决希尔伯特第10 个问题所必需的。而第10 个问题的真正解决则要等到1970 年,借助于丘奇与图灵的杰出贡献,马提亚塞维齐在戴维斯、普特纳姆和罗宾逊等人工作的基础上,最终证明检查多项式是否有整数根的算法是不存在的。
从图灵开始,算法已然同计算机科学之间产生了密不可分的联系。当然,本书的内容并不打算从图灵机开始讲起。回顾建立算法形式化定义和破解希尔伯特第10 个问题的那段风起云涌的历史,更多地是想说明算法之于我们的世界是多么重要。
无论你是信息技术的从业人员,还是计算机专业的在校学生,再或者是从事相关专业的研究人员,熟练掌握一门计算机语言的重要性都不言而喻。但是不是掌握了这其中的语法规则就能写出漂亮的程序了呢?答案当然是否定的。因为你还需要另外一样至少同等重要的工具——算法。算法和语言的关系,其实很像是“道”和“术”的关系。掌握一门语言,就如同习得一门技艺,可以成为一名工匠。但要想从工匠一跃成为大师,单单停留在“术”的层面显然不够,更重要的是悟“道”。而算法无疑就是计算机程序设计中的“道”。
谈到算法的重要性就不得不提及计算机科学家安德鲁?艾派尔在1985 年所开展的一项研究工作,这也是程序性能优化领域的经典案例。彼时,艾派尔编写了一个用于计算重力场中天体间相互作用之问题的程序。给定场中物体质量、初始位置和速度等条件,该程序即可对10000 个天体相互作用时其中两个天体的运行状态进行模拟和仿真。由于计算量太大,最初的程序要完成该项计算大约需要耗时一年。在一系列的改进之后,艾派尔最终将程序耗时有效地缩短到了一天!而在这个改进过程中,算法和数据结构的调优占了主要比重。
再说一个发生在笔者身上的例子。曾经在上学的时候,老师布置了一道编程作业,用于模拟一个猜三和弦的游戏。一个三和弦是指从A、B、C、D、E、F、G 这7 个音中任选3 个组成的一个旋律,而每个音又有高音、中音、低音3 种情况(分别用1、2、3 来表示)。现在假设一名作曲家心中有了一个心仪的旋律,然后一个钢琴演奏者试图猜测这个答案。每当演奏者给出一个猜测,例如“A1、B2、C3”。那么作曲家将只能答复这其中完全猜中的音调(即音符和音高都猜对)有几个,除了完全猜中的音调以外,音符猜中了几个,音高猜中了几个。然后演奏者继续猜测,直到完全猜中为止。要知道,全部的组合可能有1330 种之多!而我们希望用越少的次数猜中越好。不知道本书的各位读者心中是否已想到什么方法来解决这个问题。不过笔者最终实现的程序可以做到平均4.2 次便猜中答案。而在这个过程中,设计一个绝佳的算法无疑是不二之选。
说起算法又不得不提及数据结构,二者是相辅相成、密不可分的。一方面,算法一定要借助相应的数据结构才能得以实现,另一方面我们在定义一个数据结构的同时其实也已经定义了与之相关的操作。这些操作本身执行的步骤就是算法。
总的来说,本书围绕算法与数据结构这个话题,循序渐进、深入浅出地介绍了现代计算机技术中常用的40 余个经典算法(包括模式匹配算法、排序算法、散列算法、最短路径算法等),以及回溯法、分治法、贪婪法和动态规划等算法设计思想。本书也系统地讲解了链表(包括单向链表、单向循环链表和双向循环链表)、栈、队列(包括普通队列和优先级队列)、树(包括二叉树、哈夫曼树、堆、红黑树、AVL 树和字典树)、图、集合(包括不相交集等)与字典等常用数据结构。同时,通过对22 个经典问题(包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等)的讲解,逐步揭开隐匿在数据结构背后的算法原理,力图帮助读者夯实知识储备,激活思维技巧,并最终冲破阻碍编程能力提升的重重藩篱。
更值得一提的是,算法与数据结构知识是技术类求职过程中的必考内容。希望广大读者,尤其是处于求职应聘阶段的毕业生,在夯实基础、培养能力的同时,亦能设法将知识转化为生产力,求得一份称心如意的职位。若能事半功倍、一石二鸟,何乐而不为?为此,笔者特别在附录中整理出了一些求职面试中的经典题目,供有相关需求的读者参考学习。该套题目主要以算法与数据结构问题为主线,并穿插以C/C++相关的编程问题,具有较高的实用性,对提高应聘竞争力很有帮助。特别地,在正文中涉及相关考点之处,笔者均采用旁注的形式点明了可以参考的题目编号,便于读者在阅读过程中,边学边练,知行合一。
纸上得来终觉浅,绝知此事要躬行。锤炼数据结构的运用能力和深化算法思想的理解程度都有赖于编程实践活动。本书采用C++作为描述语言,并提供有涉及的全部数据结构和算法之实现代码,供读者参考学习。这些代码均在基于TDM-GCC 4.9.2 的DEV-C++ 5.11 和Visual Studio 2013 环境下编译通过。本书特别提供了一个在线支持资源,地址http://blog.csdn.net/baimafujinji,从中读者可以下载得到全书的配套代码和附录题库的参考答案,本书的勘误也将实时发布在此博客上。同时欢迎读者就本书中的问题和不足与笔者展开讨论,有关问题请在上述博客中留言。
最后,刘航、吴凯、姜萌、何鹏、胡俊、李召恒、初甲林等人也参与了本书编写工作,笔者在此表示由衷的感谢。
自知论道须思量,几度无眠一文章。由于时间和能力有限,书中纰漏在所难免,真诚地希望各位读者和专家不吝批评斧正。
我一直在寻找一本能够真正解答我心中疑惑的书,关于那些数据结构和算法的底层逻辑。市面上充斥着大量的“速成”教程,它们教你如何去“用”,却鲜少告诉你“为什么”。我曾尝试过一些同类书籍,但往往在学习了几个算法的实现后,就陷入了机械的记忆,无法融会贯通。我渴望的是一种更深层次的理解,一种能够让我举一反三、触类旁通的能力。这本书的书名《算法之美》以及副标题“隐匿在数据结构背后的原理(C++版)”恰好戳中了我的痛点。它似乎在告诉我,算法并非孤立存在,它们与数据结构的巧妙结合,才能发挥出惊人的力量。而C++作为一门强大的语言,想必能为我们揭示这些原理提供绝佳的视角。我期待这本书能够带领我拨开迷雾,看见那些隐藏在代码之下的智慧之光。
评分作为一名在编程领域摸爬滚打多年的老兵,我对算法的理解一直停留在“能用就行”的层面。虽然我能够熟练地运用各种数据结构和算法来解决实际问题,但每当深入思考其背后的原理时,总会感到一丝力不从心。那种感觉就像是拥有了一把万能钥匙,却不知道锁的构造。这本书的出现,仿佛是为我打开了一扇新的大门。它不仅仅是关于算法的知识点罗列,更强调“原理”,这正是我想深入了解的部分。C++版的定位也让我觉得非常贴切,因为它是一门对底层有更直接控制的语言,能够帮助我们更清晰地理解算法的运行机制。我希望通过这本书,能够构建起一个更加扎实的算法理论体系,不再仅仅是“知其然”,而是真正“知其所以然”。
评分这本书的封面设计着实吸引眼球,深邃的蓝色背景搭配若隐若现的算法图谱,瞬间就勾起了我对计算机科学核心的好奇心。我一直觉得,那些看似复杂的算法,背后一定蕴藏着某种优雅的逻辑,正如书名所暗示的“美”。只是,很多时候,我们接触到的只是冰冷的公式和生硬的代码,却很少有机会去探究它们是如何被构建起来的,更遑论其中的巧妙之处。这本《算法之美》听起来就像是为我这样的读者量身定做的,它承诺的不仅仅是技术的传授,更是对原理的深入剖析。C++版更是让我眼前一亮,因为C++这门语言本身就充满了强大的表现力和精巧的设计,用它来阐述算法原理,想必会带来更直观、更深刻的理解。我非常期待能通过这本书,不仅掌握算法的实现,更能体会到那种“美”的所在,真正理解“隐匿在数据结构背后的原理”。
评分近年来,我愈发觉得,想要在计算机科学领域走得更远,对基础知识的理解就越发重要。尤其是在算法和数据结构方面,很多人都陷入了对框架和库的过度依赖,而忽略了最根本的原理。每次遇到性能瓶颈或者需要优化代码时,我都会感到力不从心,因为我对底层的理解不够深入。这本《算法之美 隐匿在数据结构背后的原理(C++版)》的书名,正是我一直在寻找的。它承诺的不仅仅是算法的实现,更是对其背后原理的挖掘。C++作为一门对性能和底层有极高要求的语言,用它来阐述算法,想必能让我们更清晰地看到各种算法的设计思想和优化技巧。我期待这本书能让我真正理解“为什么”要这样设计,而不是仅仅停留在“怎么用”。
评分我对那些能够将抽象概念具象化的书籍总是情有独钟。算法和数据结构,在我看来,就是计算机科学中最抽象也最核心的组成部分。很多时候,我们在学习它们的时候,就像是在和一堆符号打交道,很难将其与实际的、有逻辑的“原理”联系起来。这本书的名字——《算法之美》,以及“隐匿在数据结构背后的原理”这个副标题,立刻引起了我的兴趣。它似乎在暗示,算法并非冷冰冰的指令,而是有着内在的逻辑美感和巧妙的设计。C++版的选择,也让我对这本书的深度和实用性充满了期待,毕竟,C++能够让我们更好地窥探到底层运行的细节。我希望这本书能够帮助我摆脱对算法的“死记硬背”,真正理解它们是如何运作的,以及为何能发挥出如此强大的作用。
评分很不错 优惠买的划算 放心买吧正版
评分好书,买后还没看,相信不会让我失望
评分ok,ok.ok,ok.ok,ok.ok,ok.
评分东西不错,挺好的。一次不错的购物旅程!
评分给力!!!!!!!!!!!!!!!!
评分京东购买图书送货快,非常方便
评分asdfsadfsadgdsfgdfgsdgdsgsdfgsdfgsd
评分书写的可以,难度适中,通俗易懂
评分帮朋友买的,可以可以
本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度,google,bing,sogou 等
© 2025 book.cndgn.com All Rights Reserved. 新城书站 版权所有