【二手】大话数据结构 --大话设计模式程杰清华大学出版社97873022556592011-06-01
批量上传，套装书可能不全，下单前咨询在线客服！ 正版书 ！！！
￥ 16.64 2.8折 ￥ 59 九品
仅1件
四川成都
认证卖家担保交易快速发货售后保障
作者程杰
出版社清华大学出版社
ISBN9787302255659
出版时间2011-06
装帧平装
开本16开
定价59元
货号140050
上书时间2024-10-01
- 最新上架
商品详情
- 品相描述：九品
- 商品描述
-
导语摘要
数据结构好枯燥，算法很复杂，这是真的吗？程杰编写的这本《大话数据结构》尝试用轻松的文字和形象的图示重新组织这部分知识的讲解过程，大话让数据结构和算法的学习变得有趣了。不信？翻开读读就知道真假了。
商品简介
《大话数据结构》主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、赫夫曼树及应用；图的深度、广度遍历；很小生成树两种算法、很短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B+树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。
作者肖像展示图：
作者简介
程杰，一个被读者誉为很适合写IT技术书的家伙。《大话设计模式》作者。此书07年末出版至今已经简体版印刷9次、繁体版印刷6次，取得了较好的成绩，开创了一种适合国人阅读的趣味讲解IT知识的风格模式。其本人参与过政府、证券、游戏、交通等多种行业的软件开发及项目管理工作，也曾做过软件培训的教师。因曾有过两年半高中数学教学的独特经历，使得其书作当中处处以初学者视角考虑和分析问题，他成为了当前很受欢迎的IT技术图书作者之一。
目录
第1章数据结构绪论第2章算法第3章线性表第4章栈与队列第5章串第6章树第7章图第8章查找第9章排序关键词索引参考文献
内容摘要
程杰编写的《大话数据结构》以一个计算机教师教学为场景，讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述，大量引用了各种各样的生活知识来类比，并充分运用图形语言来体现抽象内容，对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比，本书内容趣味易读，算法讲解细致深刻，是一本非常适合自学的读物。《大话数据结构》主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、赫夫曼树及应用；图的深度、广度遍历；最小生成树两种算法、最短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B+树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。《大话数据结构》适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学生、想转行做开发的非专业人员、欲考计算机研究生的应届或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等。
主编推荐
超级畅销书《大话设计模式》作者的新作！用户群更为广泛，写作风格一如既往，技术沉淀更加深厚，势必掀起全民数据结构的热潮！大话设计模式谈笑间，读懂IT世界大话存储谈笑间，读懂IT世界大话处理器谈笑间，读懂IT世界
精彩内容
第2章算法 启 示算法： 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 2.1开场白 各位同学大家好。 上次上完课后，有同学对我说，老师，我听了你的课，感觉数据结构没什么的，你也太夸大它的难度了。 是呀，我好像是强调了数据结构比较搞脑子，而上次课，其实还没拿出复杂的东西来说道。不是不想，是没必要，次课就把你们糊弄晕，那以后还玩什么，逃课的不就更多了吗？你们看，今天来的人数和次差不多，而且暂时还没有睡觉的。 今天我们介绍的内容在难度上就有所增加了，做好准备了吗？ 2.2数据结构与算法关系 我们这门课程叫数据结构，但很多时候我们会讲到算法，以及它们之间的关系。市场上也有不少书叫数据结构与算法分析这样的名字。 有人可能就要问了，那你到底是只讲数据结构呢，还是和算法一起讲？它们之间是什么关系呢？干吗要放在一起？ 这问题怎么回答。打个比方吧，今天是你女友生日，你打算请女友去看爱情音乐剧，到了戏院，抬头一看《梁山伯》18：00开演。嗯，怎么会是这样？一问才知，今天饰演祝英台的演员生病，所以梁山伯唱独角戏。真是搞笑了，这还有什么看头。于是你们打算去看爱情电影。到了电影院，一看海报《罗密欧》，是不是名字写错了，问了才知，原来饰演朱丽叶的演员因为嫌弃演出费用太低，中途退演了。制片方考虑到已经开拍，于是就把电影名字定为《罗密欧》，主要讲男主角的心路旅程。哎，这电影还怎么看啊？ 事实上，数据结构和算法也是类似的关系。只谈数据结构，当然是可以，我们可以在很短的时间就把几种重要的数据结构介绍完。听完后，很可能你没什么感觉，不知道这些数据结构有何用处。但如果我们再把相应的算法也拿来讲一讲，你就会发现，甚至开始感慨：哦，计算机界的前辈们，的确是一些很牛很牛的人，他们使得很多看似很难解决或者没法解决的问题，变得如此美妙和神奇。 也许从这以后，慢慢地你们中的一部分会开始把你们的崇拜对象，从帅哥美女、什么哥什么姐们，转移到这些大胡子或者秃顶的老头身上，那我就非常欣慰了。而且，这显然是一种成熟的表现，我期待你们中多一点这样的人，这样我们国家的软件行业，也许就有得救了。 不过话说回来，现在好多大学里，通常都是把算法分出一门课单独讲的，也就是说，在《数据结构》课程中，就算谈到算法，也是为了帮助理解好数据结构，并不会详细谈及算法的方方面面。我们的课程也是按这样的原则来展开的。 2.3两种算法的比较 大家都已经学过一门计算机语言，不管学的是哪一种，学得好不好，好歹是可以写点小程序了。现在我要求你写一个求123100结果的程序，你应该怎么写呢？ 大多数人会马上写出下面的C语言代码（或者其他语言的代码）： inti,sum=0,n=100; for（i=1;i=n;i） { sum=sumi; } printf（"%d",sum）; 这是简单的计算机程序之一，它就是一种算法，我不去解释这代码的含义了。问题在于，你的直觉是这样写的，但这样是不是真的很好？是不是效？ 此时，我不得不把伟大数学家高斯的童年故事拿来说一遍，也许你们都早已经听过，但不妨再感受一下，天才当年是如何展现天分和才华的。 据说18世纪生于德国小村庄的高斯，上小学的一天，课堂很乱，就像我们现在下面那些窃窃私语或者拿着手机不停摆弄的同学一样，老师非常生气，后果自然也很严重。于是老师在放学时，就要求每个学生都计算12100的结果，谁先算出来谁先回家。 天才当然不会被这样的问题难倒，高斯很快就得出了答案，是5050。老师非常惊讶，因为他自己想必也是通过12=3，33=6，64=10，，4950100=5050这样算出来的，也算了很久很久。说不定为了怕错，还算了两三遍。可眼前这个少年，为何可以这么快地得出结果？ 高斯解释道： 用程序来实现如下： inti,sum=0,n=100; sum=（1n）*n/2; printf（"%d",sum）; 神童就是神童，他用的方法相当于另一种求等差数列的算法，不仅仅可以用于1加到100，就是加到一千、一万、一亿（需要更改整型变量类型为长整型，否则会溢出），也就是瞬间之事。但如果用刚才的程序，显然计算机要循环一千、一万、一亿次的加法运算。人脑比电脑算得快，似乎成为了现实。 2.4算法定义 什么是算法呢？算法是描述解决问题的方法。算法（Algorithm）这个单词早出现在波斯数学家阿勒?花刺子密在公元825年（相当于我们中国的唐朝时期）所写的《印度数字算术》中。如今普遍认可的对算法的定义是： 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 刚才的例子我们也看到，对于给定的问题，是可以有多种算法来解决的。 那我就要问问你们，有没有通用的算法呀？这个问题其实很弱智，就像问有没有可以包治百病的药呀！ 现实世界中的问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决所有的问题。甚至解决一个小问题，很优秀的算法却不一定适合它。 算法定义中，提到了指令，指令能被人或机器等计算装置执行。它可以是计算机指令，也可以是我们平时的语言文字。 为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能，这就是算法了。 2.5算法的特性 算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。 2.5.1输入输出 输入和输出特性比较容易理解，算法具有零个或多个输入。尽管对于绝大多数算法来说，输入参数都是必要的，但对于个别情况，如打印helloworld！这样的代码，不需要任何输入参数，因此算法的输入可以是零个。算法至少有一个或多个输出，算法是一定需要输出的，不需要输出，你用这个算法干吗？输出的形式可以是打印输出，也可以是返回一个或多个值等。 2.5.2有穷性 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以接受的有边界。你说你写一个算法，计算机需要算上个二十年，一定会结束，它在数学意义上是有穷了，可是媳妇都熬成婆了，算法的意义也不就大了。 2.5.3确定性 确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有的输出结果。算法的每个步骤被精确定义而无歧义。 2.5.4可行性 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法，不是说理论上不能实现，而是因为过于复杂，我们当前的编程方法、工具和大脑限制了这个工作，不过这都是理论研究领域的问题，不属于我们现在要考虑的范围。 2.6算法设计的要求 刚才我们谈到了，算法不是的。也就是说，同一个问题，可以有多种解决问题的算法。这可能让那些常年只做有标准答案题目的同学失望了，他们多么希望存在标准答案，只有一个是正确的，把它背下来，需要的时候套用就可以了。不过话说回来，尽管算法不，相对好的算法还是存在的。掌握好的算法，对我们解决问题很有帮助，否则前人的智慧我们不能利用，就都得自己从头研究了。那么什么才叫好的算法呢？ 嗯，没错，有同学说，好的算法，起码要是正确的，连正确都谈不上，还谈什么别的要求？ 2.6.1正确性 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 但是算法的正确通常在用法上有很大的差别，大体分为以下四个层次。 1．算法程序没有语法错误。 2．算法程序对于合法的输入数据能够产生满足要求的输出结果。 3．算法程序对于非法的输入数据能够得出满足规格说明的结果。 4．算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。 对于这四层含义，层次1要求，但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱，不能算是生活幸福一样。而层次4是困难的，我们几乎不可能逐一验证所有的输入都得到正确的结果。 因此算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次3作为一个算法是否正确的标准。 好算法还有什么特征呢？ 很好，我听到了说算法容易理解。没错，就是它。 2.6.2可读性 可读性：算法设计的另一目的是为了便于阅读、理解和交流。 可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难于调试和修改。 我在很久以前曾经看到过一个网友写的代码，他号称这程序是用少代码实现俄罗斯方块。因为我自己也写过类似的小游戏程序，所以想研究一下他是如何写的。由于他追求的是少代码这样的极致，使得他的代码真的不好理解。也许除了计算机和他自己，绝大多数人是看不懂他的代码的。 我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了些什么。可读性是算法（也包括实现它的代码）好坏很重要的标志。 2.6.3健壮性 一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。 2.6.4时间效率高和存储量低 后，好的算法还应该具备时间效率高和存储量低的特点。 时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。在生活中，人们都希望花少的钱，用短的时间，办的事，算法也是一样的思想，好用少的存储空间，花少的时间，办成同样的事就是好的算法。求100个人的高考成绩平均分，与求全省的所有考生的成绩平均分在占用时间和内存存储上是有非常大的差异的，我们自然是追求可以高效率和低存储量的算法来解决问题。 综上，好的算法，应该具有正确性、可读性、健壮性、高效率和低存储量的特征。 2.7算法效率的度量方法 刚才我们提到设计算法要提高效率。这里效率大都指算法的执行时间。那么我们如何度量一个算法的执行时间呢？ 正所谓是骡子是马，拉出来遛遛。比较容易想到的方法就是，我们通过对算法的数据测试，利用计算机的计时功能，来计算不同算法的效率是高还是低。 2.7.1事后统计方法 事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。 但这种方法显然是有很大缺陷的： ?必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法，不是竹篮打水一场空吗？ ?时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。要知道，现在的一台四核处理器的计算机，跟当年286、386、486等老爷爷辈的机器相比，在处理算法的运算速度上，是不能相提并论的；而所用的操作系统、编译器、运行框架等软件的不同，也可以影响它们的结果；就算是同一台机器，CPU使用率和内存占用情况不一样，也会造成细微的差异。 ?算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序，不管用什么算法，差异几乎是零。而如果有一百万个随机数字排序，那不同算法的差异就非常大了。那么我们为了比较算法，到底用多少数据来测试，这是很难判断的问题。 基于事后统计方法有这样那样的缺陷，我们考虑不予采纳。 2.7.2事前分析估算方法 我们的计算机前辈们，为了对算法的评判更科学，研究出了一种叫做事前分析估算的方法。 事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。 经过分析，我们发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： 1．算法采用的策略、方法。 2．编译产生的代码质量。 3．问题的输入规模。 4．机器执行指令的速度。 第1条当然是算法好坏的根本，第2条要由软件来支持，第4条要看硬件性能。也就是说，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。 我们来看看今天刚上课时举的例子，两种求和的算法： 种算法： inti,sum=0,n=100;/*执行1次*/ for（i=1;i=n;i）/*执行了n1次*/ { sum=sumi;/*执行n次*/ } printf（"%d",sum）;/*执行1次*/ 第二种算法： intsum=0,n=100;/*执行一次*/ sum=（1n）*n/2;/*执行一次*/ printf（"%d",sum）;/*执行一次*/ 显然，种算法，执行了1（n1）n1次=2n3次；而第二种算法，是111=3次。事实上两个算法的条和后一条语句是一样的，所以我们关注的代码其实是中间的那部分，我们把循环看作一个整体，忽略头尾循环判断的开销，那么这两个算法其实就是n次与1次的差距。算法好坏显而易见。 我们再来延伸一下上面这个例子： inti,j,x=0,sum=0,n=100;/*执行一次*/ for（i=1;i=n;i） { for（j=1;j=n;j） { x;/*执行nn次*/ sum=sumx; } } printf（"%d",sum）;/*执行一次*/ 这个例子中，i从1到100，每次都要让j循环100次，而当中的x和sum=sumx；其实就是12310000，也就是1002次，所以这个算法当中，循环部分的代码整体需要执行n2（忽略循环体头尾的开销）次。显然这个算法的执行次数对于同样的输入规模n=100，要多于前面两种算法，这个算法的执行时间随着n的增加也将远远多于前面两个。 此时你会看到，测定运行时间可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。 我们不关心编写程序所用的程序设计语言是什么，也不关心这些程序将跑在什么样的计算机中，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作，终，在分析程序的运行时间时，重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。 可以从问题描述中得到启示，同样问题的输入规模是n，求和算法的种，求12n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是f（n）=n，显然运行100次的同一段代码规模是运算10次的10倍。而第二种，无论n为多少，运行次数都为1，即f（n）=1；第三种，运算100次是运算10次的100倍。因为它是f（n）=n2。 我们在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数（如图2-7-1所示）。 图2-7-1 我们可以这样认为，随着n值的越来越大，它们在时间效率上的差异也就越来越大。好比你们当中有些人每天都在学习，我指有用的学习，而不是只为考试的死读书，每天都在进步，而另一些人，打打游戏，睡睡大觉。入校时大家都一样，但毕业时结果可能就大不一样，前者名企争抢着要，后者求职无门。 2.8函数的渐近增长 我们现在来判断一下，两个算法A和B哪个更好。假设两个算法的输入规模都是n，算法A要做2n3次操作，你可以理解为先有一个n次的循环，执行完成后，再有一个n次循环，后有三次赋值或运算，共2n3次操作。算法B要做3n1次操作。你觉得它们谁更快呢？ 准确说来，答案是不一定的（如表2-8-1所示）。 表2-8-1 次数 算法A（2n3）算法A（2n）算法B（3n1）算法B（3n） n=15243 n=27476 n=396109 n=1023203130 n=100203200301300 当n=1时，算法A效率不如算法B（次数比算法B要多一次）。而当n=2时，两者效率相同；当n2时，算法A就开始优于算法B了，随着n的增加，算法A要越来越好过算法B了（执行的次数比Ｂ要少）。于是我们可以得出结论，算法A总体上要好过算法B。 此时我们给出这样的定义，输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐近增长的。 函数的渐近增长：给定两个函数f（n）和g（n），如果存在一个整数N，使得对于所有的nN，f（n）总是比g（n）大，那么，我们说f（n）的增长渐近快于g（n）。 从中我们发现，随着n的增大，后面的3还是1其实是不影响终的算法变化的，例如算法A与算法B，所以，我们可以忽略这些加法常数。后面的例子，这样的常数被忽略的意义可能会更加明显。 我们来看第二个例子，算法C是4n8，算法D是2n21（如表2-8-2所示）。 表2-8-2 次数算法C（4n8）算法C（n）算法D（2n21）算法D（n2） n=112131 n=216294 n=3203199 n=104810201100 n=1004081002000110000 n=10004008100020000011000000 当n3的时候，算法C要差于算法D（因为算法C次数比较多），但当n3后，算法C的优势就越来越优于算法D了，到后来更是远远胜过。而当后面的常数去掉后，我们发现其实结果没有发生改变。甚至我们再观察发现，哪怕去掉与n相乘的常数，这样的结果也没发生改变，算法C的次数随着n的增长，还是远小于算法D。也就是说，与次项相乘的常数并不重要。 我们再来看第三个例子。算法E是2n23n1，算法F是2n33n1（如表2-8-3所示）。 表2-8-3 次数算法E（2n23n1）算法E（n2）算法F（2n33n1）算法F（n3） n=16161 n=2154238 n=32896427 n=1023110020311000 n=100203011000020003011000000 当n=1的时候，算法E与算法F结果相同，但当n1后，算法E的优势就要开始优于算法F，随着n的增大，差异非常明显。通过观察发现，次项的指数大的，函数随着n的增长，结果也会变得增长特别快。 我们来看后一个例子。算法G是2n2，算法H是3n1，算法I是2n23n1（如表2-8-4所示）。 表2-8-4 次数算法G（2n2）算法H（3n1）算法I（2n23n1） n=1246 n=28715 n=5501666 n=1020031231 n=1002000030120301 n=1,000200000030012003001 n=10,00020000000030001200030001 n=100,0002000000000030000120000300001 n=1,000,000200000000000030000012000003000001 这组数据应该就看得很清楚。当n的值越来越大时，你会发现，3n1已经没法和2n2的结果相比较，终几乎可以忽略不计。也就是说，随着n值变得非常大以后，算法G其实已经很趋近于算法I。于是我们可以得到这样一个结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（阶项）的阶数。 判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的。根据刚才的几个样例，我们发现，如果我们可以对比这几个算法的关键执行次数函数的渐近增长性，基本就可以分析出：某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法。这其实就是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。 2.9算法时间复杂度 2.9.1算法时间复杂度定义 在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。 这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。 一般情况下，随着n的增大，T(n)增长
— 没有更多了 —
以下为对购买帮助不大的评价