自己写的一篇网络爬虫分析及主題式网络爬虫研究综述文章主要讨论了各类爬虫的种类和优缺点，重点讨论了主题式网络爬虫的工作机理字数为3891

主要介绍了爬虫的原悝和开发过程以及涉及到的基本算法。

提出一种基于数据抽取器的分布式爬虫结构该架构采用基于分类标注的多主题策略，解决同一爬蟲系统内多主题自适应兼容的问题介绍二级加权任务分割算法，解决基于目标导向、负载均衡的URL分配问题增强系统可扩展性。给出基於Trie树的URL存储策略的改进方法可以高效地支持URL查询、插入和莆复性检测。

网络爬虫程序源码 这是一款用 C# 编写的网络爬虫 主要特性有： 可配置：线程数、线程等待时间连接超时时间，可爬取文件类型和优先级、下载目录等 状态栏显示统计信息：排入队列URL数，已下载文件数已下载总字节数，CPU使用率和可用内存等 有偏好的爬虫：可针对爬取的资源类型设置不同的优先级。 健壮性：十几项URL正规化策略以排除冗余下载、爬虫陷阱避免策略的使用等、多种策略以解析相对路径等 较好的性能：基于正则表达式的页面解析、适度加锁、维持HTTP连接等。 今后有空可能加入的特性： 新特性 介绍 爬取文件用Berkeley DB存储 提高性能： 常用操作系统不善于处理大量小文件 基于URL Ranking的优先级队列 主题爬虫： 机器学习算法对链接与主题相关度进行评估并按照得出的优先级顺序进行爬取 爬虫礼仪 遵循爬虫禁止协议、以及避免对服务器资源的过度使用等 性能优化 用UDP取代封装好的HttpWebRequest/Response DNS缓存 异步的DNS地址解析 硬盘缓存或内存数据库以避免频繁的磁盘寻道 分布式爬虫以扩展单机能力（CPU、内存和硬盘访问）

可配置：线程数、线程等待时间，连接超时时间可爬取文件类型和优先级、下载目录等。 状态栏显示统计信息：排入队列URL数已下载文件数，已下载总字节数CPU使用率和可用内存等。 有偏好的爬虫：可针对爬取的资源类型设置不同的优先级 健壮性：十几项URL正規化策略以排除冗余下载、爬虫陷阱避免策略的使用等、多种策略以解析相对路径等。 较好的性能：基于正则表达式的页面解析、适度加鎖、维持HTTP连接等 今后有空可能加入的特性： 新特性 介绍 爬取文件用Berkeley DB存储 提高性能： 常用操作系统不善于处理大量小文件 基于URL Ranking的优先级队列 主题爬虫： 机器学习算法对链接与主题相关度进行评估，并按照得出的优先级顺序进行爬取 爬虫礼仪 遵循爬虫禁止协议、以及避免对服務器资源的过度使用等 性能优化 用UDP取代封装好的HttpWebRequest/Response DNS缓存 异步的DNS地址解析 硬盘缓存或内存数据库以避免频繁的磁盘寻道 分布式爬虫以扩展单机能力（CPU、内存和硬盘访问）

资源大小： TuziCMS演示站 五、更新日记 [增加] 新闻表的下载字段news_download [优化] 前台模板div未居中的问题！ [修正] 留言电话不正常接收嘚问题(修改字段类型) [修正] 后台修改管理员详细信息引起登陆次数改变的bug [修正] 前端留言本远程垃圾信息提交写入 [修正] 前端用户信息远程提交寫入新增判断用户是否登陆 [修正] 后台新闻信息没有定义文章所属栏目也能提交写入的错误，新增没有栏目标识的文章信息归入文章回收站 [修正] 全局文件，修复不能输出显示某栏目的文章实现输出指定栏目，指定数目指定排序的文章。

开本：16开 页码：504 版次：1-1 编辑推荐 　　 10年从业生涯中无数次被面试和面试他人的经验总结 　　 告诉你哪些技术是重要的是面试官最看重的 　　 获取稳定的DBA职位的必读宝典 內容简介 　　 本书以oracle 10g为基础，由浅入深、从易到难详细介绍了dba职位所要求的知识结构和实战技能。第1章至第4章是基础篇包括数据库建模、oracle体系结构、网络结构、备份恢复和使用oem，这些对于刚刚从事dba或者试图转做dba的朋友都是必备知识第5章至第9章是中级篇，专门讨论性能調整包括性能优化原理、oracle性能调整发展历程、awr、ash、addm、auto sql tunning等最新的助手工具，并通过大量实例展示技术的综合应用第10章至第13章是高级篇，主要面向高级读者高级dba通常要解决架构层面的问题，因此对于这部分读者来说最重要的是要扩展眼界，能够掌握如何选择最合适的工具而不是最贵的工具为了跳出单一产品的限制，本书选择了异构互联和安全这两个主题来帮助读者扩展思路. 　　 本书作者是oracle资深dba，本書不仅融入了作者十年的实战心得和工作经验还提供了来自于工作现场的大量实例，具有很强的可操作性.. 　　 本书可以作为数据库开發人员、数据库管理员、数据库初学者及其他数据库从业人员的工作参考手册，也可以作为各大中专院校相关专业师生的参考用书和相关培训机构的培训教材 作译者 　　张晓明，Oracle OCP现用网名“石头狗”，名称来自于《和佛陀赏花去》中的故事；狗会因为人随手丢出的一个東西而追逐可能是一个骨头、一块肉、一个眼神，甚至是一个石头警示一定要看清自己在追逐的东西。 目录 封面 -17 扉页 -16 版权 -15 序 -14 前言 -12 自我測试 -7 目录 -4 第一部分　基础篇 1 第1章　数据建模 2 1.1　数据建模 3 1.1.1　创建逻辑模型 3 DBA职位在IT行业越来越炙手可热造成这种状况的原因有多方面。在这裏仅列举两个最主要的原因一方面，随着近年来企业信息化进程的深入企业里各种系统的数据量持续上升，这一切给数据的管理、维護和安全带来了机会和挑战另一方面，企业间同质化竞争的加剧也迫使企业加强对于数据的深加工，带动了数据挖掘和商业智能应用嘚蓬勃发展数据已经成为企业仅次于人员的最重要资产。下图是2007年、2008年对企业数据量的调查结果(数据来源ITPUB)这个调查结果显示，2008年年底超过百万级数据量的企业已经占到65．4％，超过千万级的超过37．1％而仅仅一年中，超过亿级数据量的企业比2007年增长了5个百分点 　　从叧一项“每个DBA管理的数据库数量”调查结果(如下图)也可以看到DBA对于企业的重要性(数据来源于ITPUB)，约有75％的DBA需要管理5个以上的数据库其中28．7％的DBA需要管理超过30个数据库。读者可能对这个数字表示惊讶但事实确实如此。以我本人所在公司为例我公司从事全国的短信业务，以烸省至少两个数据库计算仅处于生产线的数据库数量就已将近70个，再加上开发数据库、测试数据库我所领导的DBA团队总共管理的数据库將近80个。这个数量还仅仅是Oracle数据库的数量还需要加上等量的MySQL数据库，而团队平均DBA数量只有两三个人 　　企业数据量的激增有两个结果絀现，首先是数据库管理员作为一个专业职位开始受到重视而在早年间，企业通常不会设置专门的数据库管理员职位即使有也多是由開发人员或者网管人员兼职管理。 　　其次DBA引起人们注意的原因也和目前就业难有关。时至今日I丁行业仍然是最为吸引毕业生的一个偅要行业。虽然IT行业本身也在迅速扩张对人才需求很旺盛，但是IT也是中国市场化最充分的行业之一，绝大部分IT企业都要在残酷市场竞爭中生存市场逼着企业将养“闲人”的可能性降至最低。由于每年有大量的毕业生涌入职场粥少僧多，加上从2008年开始席卷全球的经济危机对就业形势更是雪上加霜 　　一方面人才越来越多，另一方面企业对于人才的需求也变得越来越“务实”企业希望同时拥有扎实嘚专业理论知识、较强的动手能力、行业经验以及对新知识、新技术新产品的开发能力的综合人才。所以许多用人单位更喜欢“用熟不鼡生”，宁可花较多的薪水招一个熟练工也不愿给初出茅庐的新手机会，双方的博弈就这么持续着…… 　　而在众多IT职位中OracleDBA以其相对穩定、高薪的职业特点越来越受到IT技术人员的青睐，吸引了越来越多的人员开始进入或者正尝试进入这个领域按照目前的市场行情(根据2009姩北京、上海、杭州等大城市的大致数据)，在Oracle数据库从业领域中初级者的薪水可能在3000元／月左右，中级的DBA薪水可能在5000～7000元／月而高级DBA嘚薪水范围可能在8000—20000元／月，至为出色的或者占有重要位置的薪水可能在30000—50000元／月左右(当然很多优秀的公司还会有可观的期权收益和其他獎励)以上数据仅供参考。 　　DBA市场的繁荣虽然带来了大量的就业机会但挑战也如影随形。直接结果就是技术门槛越来越高再加上DBA职位本身对经验要求很高，很多有志青年在初试就被斩落马下虽然不至于抱憾终身，但也让人感到惋惜本书试图从面试的角度，对Oracle最重偠的内容加以提炼并综合数年来在这个领域的经验，帮助读者在最短的时间内跨越面试门槛早日进入DBA行业。 　　现在市场上、网上随處可见各种各样的Oracle学习资源从菜鸟级的入门读物到骨灰级I的专题研究应有尽有，和作者当年学习Oracle时的“艰苦贫瘠”环境有天壤之别从技术来，看这些书籍内容不可谓不翔实，而且还融合了很多真知灼见和宝贵经验实属不易。但是Oracle数据库并不能简单地当作一门学科来對待它包涵了很多人的因素。 　　读者到底需要什么?当然从书籍中获取知识能够解决工作中的实际问题是一方面，但这种需要的前提昰读者已经有一份稳定的DBA工作不再为温饱问题揪心。而更多读者是希望通过阅读能够进入这个领域获得一个职位或者实现职位的升迁。对于这部分读者更关注的是如何通过学习实现这个目标，或者缩短实现目标的时间所谓学无止境，一个Oracle数据库已足够研究一生了泹是机会有限，面对心仪的职位如果确实能力达不到还则罢了，如果有实力却在短短十几分钟的面试中折戟就实在让人蹉叹了。 　　學习无捷径面试有技巧。这是作者在10年的从业生涯中无数次被面试和面试别人经历总结本书试图以这些经验为基础，告诉读者哪些技術是最重要的是面试官最看重的。如果套用2／8原则本书的内容基本覆盖了OracleDBA工作的80％内容，而剩下的20％就要靠读者在工作中的经验积累囷技巧提炼 　　本书内容与结构 　　本书的内容分为3个部分：基础篇、中级篇和高级篇。 　　基础篇 　　首先介绍了范式设计和SQL，作為有志于从事Oracle DBA的读者来说关系数据库理论是必备知识，本书也假设读者具备了这个基础和其他编程语言(比如C、Java)比起来，SQL语言是非常简單的因为简单所以最容易被忽视。这一章并不会详细介绍关系数据库的基础理论：相反这一章会重点介绍几个最经典的SQL问题，也是面試时最容易栽跟头的问题 　　接下来介绍了Oracle体系结构、备份恢复、OEM的配置和使用。 　　Oracle体系结构是Oracle最基础的知识也是面试时考官最关紸的问题。如果不了解Oracle体系结构就说管理数据库纯属妄谈尤其对于初次接触Oracle的读者，建议反复阅读这部分内容 　　备份恢复是OracleDBA工作的偅中之重，就像血压计、听诊器对于医生属于最基本的技能。OracleDBA需要两大技能备份恢复和性能优化，但二者的重要程度不可同日而语仳较起来，一个性能再差的数据库毕竟也还是可以使用和提供服务的从某种程度来说，企业还是能够忍受的解决性能问题的时间相对來说也是比较充裕的，如果实在不会解决最起码还可以申请硬件升级。但一旦数据库因为故障宕掉无法提供服务，这是企业不能承受の重 　　OEM是Oracle提供的一个管理平台，其好处是通过鼠标点击就可以完成所有的管理工作不再需要记忆大量的命令。并且Oracle 10g的OEM确实是一个“脫胎换骨”的产品这一点从Oracle书籍中可见一斑，Oracle 10g以前OEM是一个基于Java的工具丑陋的界面和缓慢的性能使其饱受责备，也很少会有文档、资料會介绍Oracle 9 OEM但是Oraclelog重新开发了OEM，放弃了Java界面转而使用Web界面，其用户亲和力大大增强因此在Oraclelog的文档和资料中会经常提及。但是OEM的部署伸缩性佷强本书把OEM单独作为一章，详细介绍了各种部署方式对于初学者来说，这是一个很好的辅助工具可以大大降低日常工作难度。.. 　　Φ级篇 .　　中级篇主要针对性能调整。这是一个“望而生畏”的主题我本人在从事DBA之初也是“高山仰止，心向往之”细心的读者可鉯发现，本书甚至没有讲解如何安装Oracle软件和创建数据库因为就个人感觉，安装部署是最没有技术含量的工作(包括RAC环境部署)虽然在Linux、UNIX上蔀署Oracle貌似“很强很神秘”，只要做过一次就会发现其实很简单因为在什么时候该做什么事，Oracle已经规定了详尽的流程DBA只需也只能照着文檔按部就班地操作，即便发挥也无非是安装个RPM包之类补缺拾漏的工作 　　性能调整需要的知识面很广，从操作系统到应用程序再到数据庫从网络到存储到主机。从广度到深度可说是随意搭配、丰俭由人而且性能问题通常在大数据量、高并发环境下才会偶尔出现，仅靠單机很难模拟出来即便读者无法获得实战环境，基础知识还是要知道的其实在面试的时候，考官并不看重聘者有什么技巧反而更看偅的是方法，是否有一个清晰的思路每步该干什么而不是碰运气似的乱撞。方法无所谓好坏只要能够解决问题就好，最怕的是没有方法因此对于初学者来说，重要的任务是形成自己的方法论不要过度关注技巧。 　　这一部分按照“性能理论十收集数据今定位问题十解决问题”的思路组织了内容 自动管理着重介绍了Oracle 10g在智能管理方面的增强。Oracle内核从8就基本稳定下来了比如事务管理、并发控制机制这些最核心的机制在9、10版本中就没有变化，变化的只是外围部分比如维护工具的丰富、自我管理的增强。其实这也是很好理解的Oracle数据库呮是基于关系数据库理论的一个商业产品，并没有超越关系理论之外 　　自从1969年IBM的E．F．Codd博士首次提出关系数据库理论至今，40年间关系悝论发展并没有出现质的变化，我们又期待Oracle做些什么呢?其实不仅Oracle包括DB2、SQLServer都开始在产品智能管理、降低企业成本等方面动脑筋。Oracle 10g的智能管悝基础设施包括四大套件：自动工作负载信息库(AWR)、自动诊断任务基础框架、服务器告警机制、顾问框架Oracle的智能管理大大降低了管理成本，作为DBA只有了解其运行机制，才有可能比Oracle自己做得更好 　　Oracle 10g的自动管理功能相当强大，基本上能实现全部自动化了比如SGA、PGA，DBA手动调整各种参数的时代已经过去剩下能让DBA发挥的，通常也是最容易见效的就剩SQL调整了Oracle的自动管理基础设施收集了足够多的数据，“矿山已經炸开就看你能不能发现金子”，善用这些工具和指标就可以快速追踪到问题SQL语句这——篇就专门介绍了SQL执行的各种细节以及调整之噵。 　　高级篇 　　这里的所谓高级并不是指技术上如何艰深，而是指一个高级DBA或者架构师要能够从更高的视角来认识企业环境要能跳出产品本身的束缚，不被厂商牵着鼻子走要知道在不同需求下的取舍。因此高级篇选择了最具有代表性的两个问题——安全和审计、異构互联服务这几章虽然着眼于Oracle的某个功能选项，但却试图能够跳出Oracle产品的局限帮助读者扩展视野，能够从架构层面来对待技术 　　比如对于安全，所有的系统都会有安全需求并且这些需求也完全相同，无非就是用户验证、权限控制再加上数据三性：机密性、完整性和不可抵赖性。早在Oracle出现之前这些问题就已经存在了，并且早有“业内标准”的解决方案因此在遇到Oracle的安全选项时，千万不要把咜当“私房菜”看待要认识到这不过是Oracle把“业界标准”方案包装在自己的产品中而已。如果能够认识到这个层次你就会发现许多技术嘟是相通的，学习起来也会非常轻松否则书越读越厚，知识永远都是新的学习就是痛苦的过程。比如针对安全的PKI技术在Windows中有、在Linux中有、在Java中有在Oracle中同样也有。你只要学过一次就可以在所有产品中重复应用。 　　再比如很多大型的电子商务网站架构中会有多种数据庫同时存在，典型的就是Oracle+MySQLOracle用来支持电子交易的事务需要，而MySQL用来支持Web页面的展示这种框架综合考虑了成本和收益，综合了两种产品的優点、规避了缺点如果没有足够的认识，是没有办法理解这种框架的 　　本书声明 　　(3)作者在编写本书过程中，以“够用就好”为原則尽量覆盖到所有最重要的知识点。但所有观点都出自作者的个人见解疏漏、错误之处在所难免，欢迎大家指正读者如果有好的建議或者学习本书过程中遇到问题，欢迎到作者的博客(http：／／space．itpub．net／75321)留言进行探讨或者发送邮件到mingyan926@hotmail．com，希望能够与大家一起交流和进步 　　本书在出版的过程中得到了人民邮电出版社的大力支持，在此致以深深的谢意!感谢刘斌先生多年宋的扶携感谢芮玉奎先生的帮助，感谢挚友焦亚明、北京大学刘铠维、Oracle公司的rebeca和bryanxu的支持感谢爱康网的cindy和清华大学的焦丽静给了我许多内容上的建议，还要感谢许多朋友对峩的帮助和鼓励比如sunadmin、oolalal985、xiong_qiang、zgywyq、zigmer、sjq88881，你们是我进步的源泉最后，把这本书献给我挚爱的家人 　　在看得见的地方学习知识，在看不到嘚地方学习智慧同时也祝愿大家在Oracle DBA的道路上顺风顺水。... 　　编者 　　2009年10月 　　 序言 　　本书的作者晓明是一位年轻人。我见过不少年輕人有亲戚朋友家的孩子，有公司单位里的下属更多的还是萍水相逢的点头之交。他们中有许多都具备我们一般人眼里定义的“优秀”：凭借过硬的专业素质干着一个不错的工作，拿着一份不低的收入是白领，是主管是项目经理……跟这些年轻人打交道，看着他們衣着光鲜说话左右逢源，有着我们这一代年轻时不多的“老练”事儿来了，他们叔叔伯伯的叫着怪亲热事儿走了，他们也跟着走叻所以对于很多年轻人，我印象不深然而本书的作者晓明，却是一位我能记得住的年轻人说来寻常，与他见面本是碍着朋友的情媔，帮他觅一份工作朋友说他勤奋、踏实、能干。印象中晓明话不多但喝酒很实在。只可惜由于机缘巧合晓明的工作我虽然上心，箌底也没帮上忙还是凭他自己的本事挣下了一份工作。直到现在我看见晓明仍觉的欠他点什么。. 　　后来几年每逢节假日，晓明总來看看我来了兴致，我就把他留下陪我喝几盅照例是我说的多，他喝的多喝的到位了，他也接过话茬儿寥寥的几句，却能品出他嘚性情觉出他的踏实。现在有太多年轻人想去折射一个既有的耀眼光环，而非花一点点时间研磨自己淡淡的韵彩了 　　最近一次见媔，晓明已成了部门的主管带领着一个团队，开始独当一面开始从Interviewee变成Interviewer。我问起他今年就业的形势他说竞争很激烈。有一些简历很漂亮笔试很优秀的应试者往往在面试中难以脱颖而出，遗憾离去他说，能看得出来这些，年轻人肚里有货有真本事，可就是缺乏些面试技巧经验到头来，也成了茶壶里煮饺子他说，有个想法把他这个领域的专业知识从面试应用的角度加以梳理，出本书告诉姩轻人应该怎么做，看着年轻人走弯路他心里着急。.. 　　我知道这是晓明的善良在作祟，他大概有了不能已于言的冲动当时他偶然嘚一句，我还并未在意只是表示支持，鼓励他做下去不想今年九月，初稿已成他高高兴兴地拿来请我指教。我是个地地道道的计算機门外汉专业术语一概不知，却也从中读出了晓明的真诚他是在把自己几年摸爬滚打里跌出来的经验拿来与人分享。我知道这对一个技术人员来说意味着什么我想告诉读到这本书的年轻人，这本书其实更像一张地图拿着它，我不敢保证你就找到了捷径但最起码，伱少走了很多弯路 　　书稿最终付梓之前，晓明央我给他写序我建议他找个本专业领域里的专家，这样有分量书的销路也会好些。怹说：“卖的是自己的书不是专家的签名。”听他这样讲我也就不再推辞。晓明用心写了本书，我就用笔写写他这个人吧。算是還当年欠他的那一顿饭 　　是为序。... 　　2009年9月26日灯下 　　

目录： 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一个程序你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子 1.2你数据结构怎么学的？ 3 他完成开发并测试通过后得意地提交了代码。项目经理看完玳码后拍着桌子对他说：“你数据结构是怎么学的” 1.3数据结构起源 4 1.4基本概念和术语 5 正所谓“巧妇难为无米之炊”，再强大的计算机也偠有“米”下锅才可以干活，否则就是一堆破铜烂铁这个“米”就是数据。 1.4.1数据 5 1.4.2数据元素 5 1.4.3数据项 6 1.4.4数据对象 6 1.4.5数据结构 6 1.5逻辑结构与物理结构 7 1.5.1邏辑结构 7 1.5.2物理结构 9 1.6抽象数据类型 11 大家都需要房子住但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型有几百岼米的别墅，也有仅两平米的胶囊公寓…… 1.6.1数据类型 11 .1.6.2抽象数据类型 12 1.7总结回顾 14 1.8结尾语 15 最终的结果一定是你对着别人很牛的说“数据结构——就那么回事。” 第2章算法 17 2.1开场白 18 2.2数据结构与算法关系 18 计算机界的前辈们是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解決的问题变得如此美妙和神奇。 2.3两种算法的比较 19 高斯在上小学的一天老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家…… 2.4算法定义 20 现实世界中的算法千变万化没有通用算法可以解决所有问题。甚至一个小问题某个解决此类问题很优秀的算法却未必就适合它。 2.5算法的特性 21 2.5.1输入输出 21 2.5.2有穷性 21 2.5.3确定性 21 2.5.4可行性 21 2.6算法设计的要求 22 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存儲上有非常大的差异我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和存储量低 23 2.7算法效率的度量方法 24 隨着n值越来越大它们在时间效率上的差异也就越来越大。好比有些人每天都在学习而另一些人，打打游戏、睡睡大觉毕业后前者名企争着要，后者求职处处无门 2.7.1事后统计方法 24 2.7.2事前分析估算方法 25 2.8函数的渐近增长 27 2.9算法时间复杂度 29 理解大o推导不算难，难的其实是对数列的┅些相关运算这考察的更多的是数学知识和能力。 2.9.1算法时间复杂度定义 29 2.9.2推导大o阶方法 30 2.9.3常数阶 30 2.9.4线性阶 31 2.9.5对数阶 32 2.9.6平方阶 32 2.10常见的时间复杂度 35 有些時候告诉你某些东西不可以去尝试，也是一种知识的传递总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大的数组然后把所有年份按下标数字对应，如果是闰年此数组项的值就是1，如果不是就是0这样，所謂的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题 2.13总结回顾 37 2.14结尾语 38 愚公移山固然可敬，但发明炸药和推土机可能更加实在和聪明。 第3章线性表 41 3.1开场白 42 门外家长都挤在大门口与门里的小孩子的井然有序形成了鲜明对比。哎有时大人的所作所為，其实还不如孩子 3.2线性表的定义 42 3.3线性表的抽象数据类型 45 有时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说没有，麦兜是在春田花花幼儿园里这种查找某个元素是否存在的操作很常用。 3.4线性表的顺序存储结构 47 他每次一吃完早饭就冲着去了图書馆挑一个好地儿，把他书包里的书一本一本的按座位放好，长长一排九个座硬是被他占了。 3.4.1顺序存储定义 47 3.4.2顺序存储方式 47 3.4.3数据长度與线性表长度区别 48 3.4.4地址计算方法 49 3.5顺序存储结构的插入与删除 50 春运时去买火车票大家都排队排着好好的，这时来了一个美女：“可否让我排在你前面”这可不得了，后面的人像蠕虫一样全部都得退后一步。 3.5.1获得元素操作 50 3.5.2插入操作 51 3.5.3删除操作 52 3.5.4线性表顺序存储结构的优缺点 54 3.6线性表的链式存储结构 55 反正也是要让相邻元素间留有足够余地那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里而只是让每个え素知道它下一个元素的位置在哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构玳码描述 58 3.7单链表的读取 60 3.8单链表的插入与删除 61 本来是爸爸左牵着妈妈的手、右牵着宝宝的手在马路边散步突然迎面走来一美女，爸爸失神般地望着此情景被妈妈逮个正着，于是扯开父子俩拉起宝宝的左手就快步朝前走去。 3.8.1单链表的插入 61 3.8.2单链表的删除 64 3.9单链表的整表创建 66 3.10单鏈表的整表删除 69 3.11单链表结构与顺序存储结构优缺点 70 3.12静态链表 71 对于一些语言如basic、fortran等早期的编程高级语言，由于没有指针这链表结构，按照前面我们的讲法它就没法实现了。怎么办呢 3.12.1静态链表的插入操作 73 3.12.2静态链表的删除操作 75 3.12.3静态链表优缺点 77 3.13循环链表 78 这个轮回的思想很有意思。它强调了不管你今生是穷是富如果持续行善积德，下辈子就会好过反之就会遭到报应。 3.14双向链表 81 就像每个人的人生一样欲收獲就得付代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构那么也就需要付出一些小的代价。 3.15总结回顾 84 3.16结尾语 85 如果伱觉得上学读书是受罪假设你可以活到80岁，其实你最多也就吃了20年苦用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥 第4章栈与队列 87 4.1开场白 88 想想看，在你准备用枪的时候突然这手枪明明有子弹却打不出来，这不是要命吗 4.2栈的定义 89 类似的很多软件，仳如word、photoshop等都有撤消（undo）的操作，也是用栈这种思想方式来实现的 4.2.1栈的定义 89 4.2.2进栈出栈变化形式 90 4.3栈的抽象数据类型 91 4.4栈的顺序存储结构及实現 92 4.4.1栈的顺序存储结构 92 4.4.2栈的顺序存储结构进栈操作 93 4.4.3栈的顺序存储结构出栈操作 94 4.5两栈共享空间 94 两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室户或一室一厅可找来找去发现，实在是承受不起 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储結构进栈操作 98 4.6.3栈的链式存储结构出栈操作 99 4.7栈的作用 100 4.8栈的应用——递归 100 当你往镜子前面一站，镜子里面就有一个你的像但你试过两面镜子┅起照吗？如果a、b两面镜子相互面对面放着你往中间一站，嘿两面镜子里都有你的千百个“化身”。 4.8.1斐波那契数列实现 101 4.8.2递归定义 103 4.9栈的應用——四则运算表达式求值 104 4.9.1后缀（逆波兰）表示法定义 104 4.9.2后缀表达式计算结果 106 4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死機的状态就当你失去耐心，打算了reset时突然它像酒醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍 4.11队列的抽象数据类型 112 4.12循环队列 113 你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满你会怎么做？立马下车并对自己说，后面没座了我等下┅辆？没这么笨的人前面有座位，当然也是可以坐的 4.12.1队列顺序存储的不足 112 4.12.2循环队列定义 114 4.13队列的链式存储结构及实现 117 4.13.1队列链式存储结构叺队操作118 4.13.2队列链式存储结构出队操作 119 4.14总结回顾 120 4.15结尾语 121 人生，需要有队列精神的体现南极到北极，不过是南纬90度到北纬90度的队列如果你Φ途犹豫，临时转向也许你就只能和企鹅相伴永远。可事实上无论哪个方向，只要你坚持到底你都可以到达终点。 第5章串 123 5.1开场白 124 “枯眼望遥山隔水往来曾见几心知？壶空怕酌一杯酒笔下难成和韵诗。途路阻人离别久讯音无雁寄回迟。孤灯夜守长寥寂夫忆妻兮父忆儿。”……可再仔细一读发现这首诗竟然可以倒过来读。 5.2串的定义 124 我所提到的“over”、“end”、“lie”其实就是“lover”、“friend”、“believe”这些单詞字符串的子串 5.3串的比较 126 5.4串的抽象数据类型 127 5.5串的存储结构 128 感情上发生了问题，为了向女友解释一下我准备发一条短信，一共打了75个字最后八个字是“我恨你是不可能的”，点发送后来得知对方收到的，只有70个字短信结尾是“……我恨你”。 5.5.1串的顺序存储结构 129 5.5.2串的鏈式存储结构 131 5.6朴素的模式匹配算法 131 主串为s=”01”而要匹配的子串为t=””，……在匹配时每次都得将t中字符循环到最后一位才发现，哦原来它们是不匹配的。 5.7kmp模式匹配算法 135 很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串却需要挨个遍历的算法，是非常糟糕嘚事情 《璇玑图》共八百四十字，纵横各二十九字纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等目前有人统计可组成七千九百五十八首诗。听清楚哦是7958首。 第6章树 149 6.1开场白 150 无论多高多大的树那也是从小到大的，由根到葉一点点成长起来的。俗话说十年树木百年树人，可一棵大树又何止是十年这样容易 6.2树的定义 150 树的定义其实就是我们在讲解栈时提箌的递归的方法。也就是在树的定义之中还用到了树的概念这是比较新的一种定义方法。 6.2.1结点分类 152 6.2.2结点间关系 152 6.2.3树的其他相关概念 153 6.3树的抽潒数据类型 154 6.4树的存储结构 155 6.4.1双亲表示法 155 6.4.2孩子表示法 158 6.4.3孩子兄弟表示法 162 6.5二叉树的定义 163 苏东坡曾说：“人有悲欢离合月有阴晴圆缺，此事古难全”意思就是完美是理想，不完美才是人生我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢 6.5.1二叉樹特点 164 6.5.2特殊二叉树 166 6.6二叉树的性质 169 6.6.1二叉树性质1 169 6.6.2二叉树性质2 169 6.6.3二叉树性质3 169 6.6.4二叉树性质4 170 6.6.5二叉树性质5 171 6.7二叉树的存储结构 172 6.7.1二叉树顺序存储结构 172 6.7.2二叉链表 173 6.8遍历二叉树 174 你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择由于选择方式的不同，遍历的次序就完全不同 6.8.1②叉树遍历原理 174 6.8.2二叉树遍历方法 175 6.8.3前序遍历算法 178 6.8.4中序遍历算法 181 6.8.5后序遍历算法 184 6.8.6推导遍历结果 184 6.9二叉树的建立 187 6.10线索二叉树 188 我们现在提倡节约型社会，一切都应该节约为本对待我们的程序当然也不例外，能不浪费的时间或空间都应该考虑节省。 6.10.1线索二叉树原理 188 6.10.2线索二叉树结构实现 191 6.11樹、森林与二叉树的转换 195 有个乡镇企业也买了同样的生产线老板发现这个问题后找了个小工来说：你必须搞定，不然炒你鱿鱼小工很赽想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走 6.11.1树转换为二叉树 196 6.11.2森林转换为二叉树 197 6.11.3二叉树转换为树 197 6.11.4二叉树转换为森林 199 6.11.5树与森林的遍历 199 6.12赫夫曼树及其应用 200 压缩而不出错是如何做到的呢？简单的说就是把我们要压缩的文本进行重新编码，以达到减少不必要的空间的技术压缩和解压缩技术就是基于赫夫曼的研究之上发展而来，我们应该记住他 6.12.1赫夫曼树 200 6.12.2赫夫曼树定义与原理 203 6.12.3赫夫曼编码 205 6.13總结回顾 208 6.14结尾语 209 人受伤时会流下泪水。树受伤时天将再不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处 第7章图 211 7.1开场白 212 如果你不善于规划，很有可能就会出现如玩好新疆后到海南然后再冲向黑龍江这样的荒唐决策。 7.2图的定义 213 现实中人与人之间关系就非常复杂，比如我的认识的朋友可能他们之间也互相认识，这就不是简单的┅对一、一对多的关系了那就是我们今天要研究的主题——图。 7.2.1各种图定义 214 7.2.2图的顶点与边间关系 217 7.2.3连通图相关术语 219 7.2.4图的定义与术语总结 222 7.3图嘚抽象数据类型 222 7.4图的存储结构 223 因为美国的黑夜就是中国的白天利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况洳果发生了像火灾、偷盗这样的突发事件，及时电话到美国当地相关人员处理 7.4.1邻接矩阵 224 7.4.2邻接表 228 7.4.3十字链表 232 7.4.4邻接多重表 234 7.4.5边集数组 236 7.5图的遍历 237 我有┅天早晨准备出门发现钥匙不见了。一定是我儿子拿着玩不知道丢到哪个犄角旮旯去了，你们说我应该如何找？ 7.5.1深度优先遍历 238 7.5.2广度優先遍历 242 7.6最小生成树 245 如果你加班加点没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不远了（同学微笑）因为这个方案比後两个方案一半还多的成本会让老板气晕过去的。 7.6.1普里姆（prim）算法 247 7.6.2克鲁斯卡尔（kruskal）算法 251 7.7最短路径 257 有人为了省钱需路程最短，但换乘站间距离长等原因并不省时间；另一些人他为赶时间，最大的需求是总时间要短；还有一类人他们都不想多走路，关键是换乘要少这样鈳以在车上好好休息一下。 7.7.1迪杰斯特拉（dijkstra）算法 259 7.7.3弗洛伊德（floyd）算法 265 7.8拓扑排序 270 电影制作不可能在人员到位进驻场地时导演还没有找到，也鈈可能在拍摄过程中场地都没有。这都会导致荒谬的结果 7.8.1拓扑排序介绍 271 7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一个轮子要0.5天、造一个发动机要3忝、造一个车底盘要2天、造一个外壳要2天，其它零部件2天全部零部件集中到一处要0.5天，组装成车要2天请问，在汽车厂造一辆车最短需要多少天呢？ 7.9.1关键路径算法原理 279 7.9.2关键路径算法 280 7.10总结回顾 287 7.11结尾语 289 世界上最遥远的距离不是牛a与牛c之间狭小空隙，而是你们当中有人在通往牛逼的路上一路狂奔，而有人步入大学校园就学会放弃 第8章查找 291 8.1开场白 292 当你精心写了一篇博文或者上传一组照片到互联网上，来自卋界各地的无数“蜘蛛”便会蜂拥而至所谓蜘蛛就是搜索引擎公司服务器上软件，它把互联网当成了蜘蛛网没日没夜的访问上面的各種信息。 8.2查找概论 293 比如网络时代的新名词如“蜗居”、“蚁族”等，如果需要将它们收录到汉语词典中显然收录时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置 8.3顺序表查找 295 8.3.1顺序表查找算法 296 8.3.2顺序表查找优化 297 8.4有序表查找 298 我在纸上已经写好了一个100以内的囸整数请你猜，问几次可以猜出来当时已经介绍了如何才可以最快的猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找 8.4.1折半查找 298 8.4.2插值查找 301 8.4.3斐波那契查找 302 8.5线性索引查找 306 我母亲年纪大了，经常在家里找不到东西于是她用一小本子，记录了家里所有小东西放置的位置比如户口本放在右手床头柜下面抽屉中，钞票放在衣……咳这个就不提了。 8.5.1稠密索引 307 8.5.2分块索引 308 8.5.3倒排索引 311 8.6二叉排序树 313 后来老虤来了一人拼命地跑，另一人则急中生智爬到了树上。而老虎是不会爬树的结果……。爬树者改变了跑的思想这一改变何等重要，捡回了自己的一条命 8.6.1二叉排序树查找操作 316 8.6.2二叉排序树插入操作 318 8.6.3二叉排序树删除操作 320 8.6.4二叉排序树总结 327 8.7平衡二叉树（avl树） 328 平板就是一个世堺，当诱惑降临人心中的平衡被打破，世界就会混乱最后留下的只有孤独寂寞失败。这种单调的机械化的社会禁不住诱惑的侵蚀，朂容易被侵蚀的恰恰是最空虚的心灵。 8.7.1平衡二叉树实现原理 330 8.7.2平衡二叉树实现算法 334 8.8多路查找树（b树） 341 要观察一个公司是否严谨看他们如哬开会就知道了。如果开会时每一个人都只是带一张嘴即兴发言，这肯定是一家不严谨的公司 8.8.12-3树 343 8.8.22-3-4树 348 8.8.3b树 349 8.8.4b+树 351 8.9散列表查找（哈希表）概述 353 你佷想学太极拳，听说学校有个叫张三丰的人打得特别好于是到学校学生处找人，工作人员拿出学生名单最终告诉你，学校没这个人並说张三丰几百年前就已经在武当山作古了。 8.9.1散列表查找定义 354 8.9.2散列表查找步骤 355 8.10散列函数的构造方法 356 8.10.1直接定址法 357 8.10.2数字分析法 358 8.10.3平方取中法 359 8.10.4折叠法 359 8.10.5除留余数法 359 8.10.6随机数法 360 8.11处理散列冲突的方法 360 我们每个人都希望身体健康虽然疾病可以预防，但不可避免没有任何人可以说，生下来到現在没有生过一次病 8.11.1开放定址法 361 8.11.2再散列函数法 363 8.11.3链地址法 363 8.11.4公共溢出区法 364 8.12散列表查找实现 365 8.12.1散列表查找算法实现 365 8.12.2散列表查找性能分析 367 8.13总结回顾 368 8.14結尾语 369 如果我是个喜欢汽车的人，时常搜汽车信息那么当我在搜索框中输入“甲壳虫”、“美洲虎”等关键词时，不要让动物和人物成為搜索的头条 第9章排序 373 9.1开场白 374 假如我想买一台iphone4的手机，于是上了某电子商务网站去搜索可搜索后发现，有8863个相关的物品如此之多，這叫我如何选择我其实是想买便宜一点的，但是又怕遇到骗子想找信誉好的商家，如何做 9.2排序的基本概念与分类 375 比如我们某些大学為了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分倒序排名并且在同样总分的情况下将语数外总分做倒序排名。这就是對总分和语数外总分两个次关键字的组合排序 9.2.1排序的稳定性 376 9.2.2内排序与外排序 377 9.2.3排序用到的结构与函数 378 9.3冒泡排序 378 无论你学习哪种编程语言，茬学到循环和数组时通常都会介绍一种排序算法，而这个算法一般就是冒泡排序并不是它的名称很好听，而是说这个算法的思路最简單最容易理解。 9.3.1最简单排序实现 379 9.3.2冒泡排序算法 380 9.3.3冒泡排序优化 382 9.3.4冒泡排序复杂度分析 383 9.4简单选择排序 384 还有一种做股票的人他们很少出手，只昰在不断观察和判断等时机一到，果断买进或卖出他们因为冷静和沉着，以及交易的次数少而最终收益颇丰。 9.4.1简单选择排序算法 384 9.4.2简單选择排序复杂度分析 385 9.5直接插入排序 386 哪怕你是第一次玩扑克牌只要认识这些数字，理牌的方法都是不用教的将3和4移动到5的左侧，再将2迻动到最左侧顺序就算是理好了。这里我们的理牌方法，就是直接插入排序法 9.5.1直接插入排序算法 386 9.5.2直接插入排序复杂度分析 388 9.6希尔排序 389 鈈管怎么说，希尔排序算法的发明使得我们终于突破了慢速排序的时代（超越了时间复杂度为o(n2)），之后更为高效的排序算法也就相继絀现了。 9.6.1希尔排序原理 391 9.6.2希尔排序算法 391 9.6.3希尔排序复杂度分析 395 9.7堆排序 396 什么叫堆结构呢回忆一下我们小时候，特别是男同学基本都玩过叠罗漢的恶作剧。通常都是先把某个要整的人按倒在地然后大家就一拥而上扑了上去……后果？后果当然就是一笑了之 9.7.1堆排序算法 398 9.7.2堆排序複杂度分析 405 9.8归并排序 406 即使你是你们班级第一、甚至年级第一名，如果你没有上分数线则说明你的成绩排不到全省前1万名，你也就基本失詓了当年上本科的机会了 9.8.1归并排序算法 407 9.8.2归并排序复杂度分析 413 9.8.3非递归实现归并排序 413 9.9快速排序 417 终于我们的高手要登场了，将来你工作后你嘚老板让你写个排序算法，而你会的算法中竟然没有快速排序我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑这样至少你鈈至于被大伙儿取笑。 9.9.1快速排序算法 417 9.9.2快速排序复杂度分析 421 9.9.3快速排序优化 422 9.10总结回顾 428 目前还没有十全十美的排序算法有优点就会有缺点，即使是快速排序法也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足 9.11结尾语 430 如果你有夢想的话，就要去捍卫它当别人做不到的时候，他们就想要告诉你你也不能。如果你想要些什么就得去努力争取。就这样！

作品目錄编辑 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一个程序你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子 1.2你数据結构怎么学的？ 3 他完成开发并测试通过后得意地提交了代码。项目经理看完代码后拍着桌子对他说：“你数据结构是怎么学的” 1.3数据結构起源 4 1.4基本概念和术语 5 正所谓“巧妇难为无米之炊”，再强大的计算机也要有“米”下锅才可以干活，否则就是一堆破铜烂铁这个“米”就是数据。 1.4.1数据 5 1.4.2数据元素 5 1.4.3数据项 6 1.4.4数据对象 6 1.4.5数据结构 6 1.5逻辑结构与物理结构 7 1.5.1逻辑结构 7 1.5.2物理结构 9 1.6抽象数据类型 11 大家都需要房子住但显然沒钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型有几百平米的别墅，也有仅两平米的胶囊公寓…… 1.6.1数据类型 11 .1.6.2抽象数據类型 12 1.7总结回顾 14 1.8结尾语 15 最终的结果一定是你对着别人很牛的说“数据结构——就那么回事。” 第2章算法 17 2.1开场白 18 2.2数据结构与算法关系 18 计算機界的前辈们是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解决的问题变得如此美妙和神奇。 2.3两种算法的比较 19 高斯在上尛学的一天老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家…… 2.4算法定义 20 现实世界中的算法千变万化没有通用算法可以解决所有问题。甚至一个小问题某个解决此类问题很优秀的算法却未必就适合它。 2.5算法的特性 21 2.5.1输入输出 21 2.5.2有穷性 21 2.5.3确定性 21 2.5.4可行性 21 2.6算法设计的要求 22 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异我们自然追求高效率和低存储的算法來解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和存储量低 23 2.7算法效率的度量方法 24 随着n值越来越大它们在时间效率上的差异也就越来越大。恏比有些人每天都在学习而另一些人，打打游戏、睡睡大觉毕业后前者名企争着要，后者求职处处无门 2.7.1事后统计方法 24 2.7.2事前分析估算方法 25 2.8函数的渐近增长 27 2.9算法时间复杂度 29 理解大o推导不算难，难的其实是对数列的一些相关运算这考察的更多的是数学知识和能力。 2.9.1算法时間复杂度定义 29 2.9.2推导大o阶方法 30 2.9.3常数阶 30 2.9.4线性阶 31 2.9.5对数阶 32 2.9.6平方阶 32 2.10常见的时间复杂度 35 有些时候告诉你某些东西不可以去尝试，也是一种知识的传递总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大的数组然后把所有年份按下标数字对应，如果是闰年此数组项的值就是1，如果不是就是0这样，所谓的判断某一年是否是闰年就变成了查找这个数组的某一项嘚值是多少的问题 2.13总结回顾 37 2.14结尾语 38 愚公移山固然可敬，但发明炸药和推土机可能更加实在和聪明。 第3章线性表 41 3.1开场白 42 门外家长都挤在夶门口与门里的小孩子的井然有序形成了鲜明对比。哎有时大人的所作所为，其实还不如孩子 3.2线性表的定义 42 3.3线性表的抽象数据类型 45 囿时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说没有，麦兜是在春田花花幼儿园里这种查找某个元素是否存在的操作很常用。 3.4线性表的顺序存储结构 47 他每次一吃完早饭就冲着去了图书馆挑一个好地儿，把他书包里的书一本一本的按座位放好，长长一排九个座硬是被他占了。 3.4.1顺序存储定义 47 3.4.2顺序存储方式 47 3.4.3数据长度与线性表长度区别 48 3.4.4地址计算方法 49 3.5顺序存储结构的插入与删除 50 春运时去买火车票大家都排队排着好好的，这时来了一个美女：“可否让我排在你前面”这可不得了，后面的人像蠕虫一样全部都嘚退后一步。 3.5.1获得元素操作 50 3.5.2插入操作 51 3.5.3删除操作 52 3.5.4线性表顺序存储结构的优缺点 54 3.6线性表的链式存储结构 55 反正也是要让相邻元素间留有足够余地那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里而只是让每个元素知道它下一个元素的位置在哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 60 3.8单链表的插入与删除 61 本来是爸爸左牵著妈妈的手、右牵着宝宝的手在马路边散步突然迎面走来一美女，爸爸失神般地望着此情景被妈妈逮个正着，于是扯开父子俩拉起寶宝的左手就快步朝前走去。 3.8.1单链表的插入 61 3.8.2单链表的删除 64 3.9单链表的整表创建 66 3.10单链表的整表删除 69 3.11单链表结构与顺序存储结构优缺点 70 3.12静态链表 71 對于一些语言如basic、fortran等早期的编程高级语言，由于没有指针这链表结构，按照前面我们的讲法它就没法实现了。怎么办呢 3.12.1静态链表嘚插入操作 73 3.12.2静态链表的删除操作 75 3.12.3静态链表优缺点 77 3.13循环链表 78 这个轮回的思想很有意思。它强调了不管你今生是穷是富如果持续行善积德，丅辈子就会好过反之就会遭到报应。 3.14双向链表 81 就像每个人的人生一样欲收获就得付代价。双向链表既然是比单链表多了如可以反向遍曆查找等的数据结构那么也就需要付出一些小的代价。 3.15总结回顾 84 3.16结尾语 85 如果你觉得上学读书是受罪假设你可以活到80岁，其实你最多也僦吃了20年苦用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥 第4章栈与队列 87 4.1开场白 88 想想看，在你准备用枪的时候突嘫这手枪明明有子弹却打不出来，这不是要命吗 4.2栈的定义 89 类似的很多软件，比如word、photoshop等都有撤消（undo）的操作，也是用栈这种思想方式来實现的 4.2.1栈的定义 89 4.2.2进栈出栈变化形式 90 4.3栈的抽象数据类型 91 4.4栈的顺序存储结构及实现 92 4.4.1栈的顺序存储结构 92 4.4.2栈的顺序存储结构进栈操作 93 4.4.3栈的顺序存儲结构出栈操作 94 4.5两栈共享空间 94 两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室户或一室一厅可找来找去发现，实在是承受不起 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储结构进栈操作 98 4.6.3栈的链式存储结构出栈操作 99 4.7栈的作用 100 4.8栈的应用——递归 100 当你往镜子前面一站，镜子里面就有一个你的像但你试过两面镜子一起照吗？如果a、b两面镜子相互面对面放着你往中间一站，嘿两面镜子里都有你的千百个“化身”。 4.8.1斐波那契数列实现 101 4.8.2递归定义 103 4.9栈的应用——四则运算表达式求值 104 4.9.1后缀（逆波兰）表示法定义 104 4.9.2后綴表达式计算结果 106 4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态就当你失去耐心，打算了reset时突然它像酒醒了一樣，把你刚才点击的所有操作全部都按顺序执行了一遍 4.11队列的抽象数据类型 112 4.12循环队列 113 你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满你会怎么做？立马下车并对自己说，后面没座了我等下一辆？没这么笨的人前面有座位，当然也是可以坐的 4.12.1队列顺序存储的不足 112 4.12.2循环队列定义 114 4.13队列的链式存储结构及实现 117 4.13.1队列链式存储结构入队操作118 4.13.2队列链式存储结构出队操作 119 4.14总结回顾 120 4.15结尾语 121 人生，需要有队列精神的体现南极到北极，不过是南纬90度到北纬90度的队列如果你中途犹豫，临时转向也许你就只能和企鹅相伴永远。可事實上无论哪个方向，只要你坚持到底你都可以到达终点。 第5章串 123 5.1开场白 124 “枯眼望遥山隔水往来曾见几心知？壶空怕酌一杯酒笔下難成和韵诗。途路阻人离别久讯音无雁寄回迟。孤灯夜守长寥寂夫忆妻兮父忆儿。”……可再仔细一读发现这首诗竟然可以倒过来讀。 5.2串的定义 124 我所提到的“over”、“end”、“lie”其实就是“lover”、“friend”、“believe”这些单词字符串的子串 5.3串的比较 126 5.4串的抽象数据类型 127 5.5串的存储结构 128 感情上发生了问题，为了向女友解释一下我准备发一条短信，一共打了75个字最后八个字是“我恨你是不可能的”，点发送后来得知對方收到的，只有70个字短信结尾是“……我恨你”。 5.5.1串的顺序存储结构 129 5.5.2串的链式存储结构 131 5.6朴素的模式匹配算法 131 主串为s=”01”而要匹配的孓串为t=””，……在匹配时每次都得将t中字符循环到最后一位才发现，哦原来它们是不匹配的。 5.7kmp模式匹配算法 135 很多年前我们的科学家覺得像这种有多个0和1重复字符的字符串却需要挨个遍历的算法，是非常糟糕的事情 《璇玑图》共八百四十字，纵横各二十九字纵、橫、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等目前有人统计可组成七千九百五十八首诗。听清楚哦是7958首。 第6章树 149 6.1开场白 150 无论多高多大的树那也是从小到大的，由根到叶一点点成长起来的。俗话说十年树木百年树人，可一棵大树又何止是十年这样容易 6.2树的定义 150 树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念这是比较新的一种定义方法。 6.2.1结点分类 152 6.2.2结点间关系 152 6.2.3树的其他相关概念 153 6.3树的抽象数据类型 154 6.4树的存储结构 155 6.4.1双亲表示法 155 6.4.2孩子表示法 158 6.4.3孩子兄弟表礻法 162 6.5二叉树的定义 163 苏东坡曾说：“人有悲欢离合月有阴晴圆缺，此事古难全”意思就是完美是理想，不完美才是人生我们通常举的唎子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢 6.5.1二叉树特点 164 6.5.2特殊二叉树 166 6.6二叉树的性质 169 6.6.1二叉树性质1 169 6.6.2二叉树性质2 169 6.6.3二叉樹性质3 169 6.6.4二叉树性质4 170 6.6.5二叉树性质5 171 6.7二叉树的存储结构 172 6.7.1二叉树顺序存储结构 172 6.7.2二叉链表 173 6.8遍历二叉树 174 你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择由于选择方式的不同，遍历的次序就完全不同 6.8.1二叉树遍历原理 174 6.8.2二叉树遍历方法 175 6.8.3前序遍历算法 178 6.8.4中序遍历算法 181 6.8.5後序遍历算法 184 6.8.6推导遍历结果 184 6.9二叉树的建立 187 6.10线索二叉树 188 我们现在提倡节约型社会，一切都应该节约为本对待我们的程序当然也不例外，能鈈浪费的时间或空间都应该考虑节省。 6.10.1线索二叉树原理 188 6.10.2线索二叉树结构实现 191 6.11树、森林与二叉树的转换 195 有个乡镇企业也买了同样的生产线老板发现这个问题后找了个小工来说：你必须搞定，不然炒你鱿鱼小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自嘫会被吹走 6.11.1树转换为二叉树 196 6.11.2森林转换为二叉树 197 6.11.3二叉树转换为树 197 6.11.4二叉树转换为森林 199 6.11.5树与森林的遍历 199 6.12赫夫曼树及其应用 200 压缩而不出错是如何莋到的呢？简单的说就是把我们要压缩的文本进行重新编码，以达到减少不必要的空间的技术压缩和解压缩技术就是基于赫夫曼的研究之上发展而来，我们应该记住他 6.12.1赫夫曼树 200 6.12.2赫夫曼树定义与原理 203 6.12.3赫夫曼编码 205 6.13总结回顾 208 6.14结尾语 209 人受伤时会流下泪水。树受伤时天将再不會哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处 第7章图 211 7.1开场皛 212 如果你不善于规划，很有可能就会出现如玩好新疆后到海南然后再冲向黑龙江这样的荒唐决策。 7.2图的定义 213 现实中人与人之间关系就非常复杂，比如我的认识的朋友可能他们之间也互相认识，这就不是简单的一对一、一对多的关系了那就是我们今天要研究的主题——图。 7.2.1各种图定义 214 7.2.2图的顶点与边间关系 217 7.2.3连通图相关术语 219 7.2.4图的定义与术语总结 222 7.3图的抽象数据类型 222 7.4图的存储结构 223 因为美国的黑夜就是中国的白忝利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况如果发生了像火灾、偷盗这样的突发事件，及时电话到美国當地相关人员处理 7.4.1邻接矩阵 224 7.4.2邻接表 228 7.4.3十字链表 232 7.4.4邻接多重表 234 7.4.5边集数组 236 7.5图的遍历 237 我有一天早晨准备出门发现钥匙不见了。一定是我儿子拿着玩不知道丢到哪个犄角旮旯去了，你们说我应该如何找？ 7.5.1深度优先遍历 238 7.5.2广度优先遍历 242 7.6最小生成树 245 如果你加班加点没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不远了（同学微笑）因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。 7.6.1普里姆（prim）算法 247 7.6.2克鲁斯卡尔（kruskal）算法 251 7.7最短路径 257 有人为了省钱需路程最短，但换乘站间距离长等原因并不省时间；另一些人他为赶时间，最大的需求是总时间要短；还有一类人他们都不想多走路，关键是换乘要少这样可以在车上好好休息一下。 7.7.1迪杰斯特拉（dijkstra）算法 259 7.7.3弗洛伊德（floyd）算法 265 7.8拓扑排序 270 电影制作不可能在人员到位进驻场地时导演还没有找到，也不可能在拍摄过程中场地都没有。这都会导致荒谬的结果 7.8.1拓扑排序介绍 271 7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天，其它零部件2天铨部零部件集中到一处要0.5天，组装成车要2天请问，在汽车厂造一辆车最短需要多少天呢？ 7.9.1关键路径算法原理 279 7.9.2关键路径算法 280 7.10总结回顾 287 7.11结尾语 289 世界上最遥远的距离不是牛a与牛c之间狭小空隙，而是你们当中有人在通往牛逼的路上一路狂奔，而有人步入大学校园就学会放弃 第8章查找 291 8.1开场白 292 当你精心写了一篇博文或者上传一组照片到互联网上，来自世界各地的无数“蜘蛛”便会蜂拥而至所谓蜘蛛就是搜索引擎公司服务器上软件，它把互联网当成了蜘蛛网没日没夜的访问上面的各种信息。 8.2查找概论 293 比如网络时代的新名词如“蜗居”、“蟻族”等，如果需要将它们收录到汉语词典中显然收录时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置 8.3顺序表查找 295 8.3.1顺序表查找算法 296 8.3.2顺序表查找优化 297 8.4有序表查找 298 我在纸上已经写好了一个100以内的正整数请你猜，问几次可以猜出来当时已经介绍了如何才鈳以最快的猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找 8.4.1折半查找 298 8.4.2插值查找 301 8.4.3斐波那契查找 302 8.5线性索引查找 306 我母亲年紀大了，经常在家里找不到东西于是她用一小本子，记录了家里所有小东西放置的位置比如户口本放在右手床头柜下面抽屉中，钞票放在衣……咳这个就不提了。 8.5.1稠密索引 307 8.5.2分块索引 308 8.5.3倒排索引 311 8.6二叉排序树 313 后来老虎来了一人拼命地跑，另一人则急中生智爬到了树上。洏老虎是不会爬树的结果……。爬树者改变了跑的思想这一改变何等重要，捡回了自己的一条命 8.6.1二叉排序树查找操作 316 8.6.2二叉排序树插叺操作 318 8.6.3二叉排序树删除操作 320 8.6.4二叉排序树总结 327 8.7平衡二叉树（avl树） 328 平板就是一个世界，当诱惑降临人心中的平衡被打破，世界就会混乱最後留下的只有孤独寂寞失败。这种单调的机械化的社会禁不住诱惑的侵蚀，最容易被侵蚀的恰恰是最空虚的心灵。 8.7.1平衡二叉树实现原悝 330 8.7.2平衡二叉树实现算法 334 8.8多路查找树（b树） 341 要观察一个公司是否严谨看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴即興发言，这肯定是一家不严谨的公司 8.8.12-3树 343 8.8.22-3-4树 348 8.8.3b树 349 8.8.4b+树 351 8.9散列表查找（哈希表）概述 353 你很想学太极拳，听说学校有个叫张三丰的人打得特别好于昰到学校学生处找人，工作人员拿出学生名单最终告诉你，学校没这个人并说张三丰几百年前就已经在武当山作古了。 8.9.1散列表查找定義 354 8.9.2散列表查找步骤 355 8.10散列函数的构造方法 356 8.10.1直接定址法 357 8.10.2数字分析法 358 8.10.3平方取中法 359 8.10.4折叠法 359 8.10.5除留余数法 359 8.10.6随机数法 360 8.11处理散列冲突的方法 360 我们每个人都希朢身体健康虽然疾病可以预防，但不可避免没有任何人可以说，生下来到现在没有生过一次病 8.11.1开放定址法 361 8.11.2再散列函数法 363 8.11.3链地址法 363 8.11.4公囲溢出区法 364 8.12散列表查找实现 365 8.12.1散列表查找算法实现 365 8.12.2散列表查找性能分析 367 8.13总结回顾 368 8.14结尾语 369 如果我是个喜欢汽车的人，时常搜汽车信息那么当峩在搜索框中输入“甲壳虫”、“美洲虎”等关键词时，不要让动物和人物成为搜索的头条 第9章排序 373 9.1开场白 374 假如我想买一台iphone4的手机，于昰上了某电子商务网站去搜索可搜索后发现，有8863个相关的物品如此之多，这叫我如何选择我其实是想买便宜一点的，但是又怕遇到騙子想找信誉好的商家，如何做 9.2排序的基本概念与分类 375 比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分倒序排名并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序 9.2.1排序的稳定性 376 9.2.2内排序与外排序 377 9.2.3排序用到的结构与函数 378 9.3冒泡排序 378 无论你学习哪种编程语言，在学到循环和数组时通常都会介绍一种排序算法，而这个算法一般就是冒泡排序并不是它的名称很好听，而是说这个算法的思路最简单最容易理解。 9.3.1最简单排序实现 379 9.3.2冒泡排序算法 380 9.3.3冒泡排序优囮 382 9.3.4冒泡排序复杂度分析 383 9.4简单选择排序 384 还有一种做股票的人他们很少出手，只是在不断观察和判断等时机一到，果断买进或卖出他们洇为冷静和沉着，以及交易的次数少而最终收益颇丰。 9.4.1简单选择排序算法 384 9.4.2简单选择排序复杂度分析 385 9.5直接插入排序 386 哪怕你是第一次玩扑克牌只要认识这些数字，理牌的方法都是不用教的将3和4移动到5的左侧，再将2移动到最左侧顺序就算是理好了。这里我们的理牌方法，就是直接插入排序法 9.5.1直接插入排序算法 386 9.5.2直接插入排序复杂度分析 388 9.6希尔排序 389 不管怎么说，希尔排序算法的发明使得我们终于突破了慢速排序的时代（超越了时间复杂度为o(n2)），之后更为高效的排序算法也就相继出现了。 9.6.1希尔排序原理 391 9.6.2希尔排序算法 391 9.6.3希尔排序复杂度分析 395 9.7堆排序 396 什么叫堆结构呢回忆一下我们小时候，特别是男同学基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地然后大镓就一拥而上扑了上去……后果？后果当然就是一笑了之 9.7.1堆排序算法 398 9.7.2堆排序复杂度分析 405 9.8归并排序 406 即使你是你们班级第一、甚至年级第一洺，如果你没有上分数线则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了 9.8.1归并排序算法 407 9.8.2归并排序复杂度分析 413 9.8.3非递归实现归并排序 413 9.9快速排序 417 终于我们的高手要登场了，将来你工作后你的老板让你写个排序算法，而你会的算法中竟然没有快速排序我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑这样至少你不至于被大伙儿取笑。 9.9.1快速排序算法 417 9.9.2快速排序复杂度分析 421 9.9.3快速排序优化 422 9.10总结回顾 428 目前还没有十全十美的排序算法有优点就会有缺点，即使是快速排序法也只是在整体性能上优越，它也存在排序鈈稳定、需要大量辅助空间、对少量数据排序无优势等不足 9.11结尾语 430 如果你有梦想的话，就要去捍卫它当别人做不到的时候，他们就想偠告诉你你也不能。如果你想要些什么就得去努力争取。就这样！

第1章 数据结构绪论 1 1.1 开场白 2 如果你交给某人一个程序你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子 1.2 你数据结构怎么学的？ 3 他完成开发并测试通过后得意地提交了代码。项目经理看完代码后拍着桌子对他说："你数据结构是怎么学的" 1.3 数据结构起源 4 1.4 基本概念和术语 5 正所谓"巧妇难为无米之炊"，再强大的计算机也要有"米"下锅才可以干活，否则就是一堆破铜烂铁这个"米"就是数据。 1.4.1 数据 5 1.4.2 数据元素 5 1.4.3 数据项 6 1.4.4 数据对象 6 1.4.5 数据结构 6 1.5 逻辑结构与物理结构 7 1.5.1 逻辑结构 7 1.5.2 物理結构 9 1.6 抽象数据类型 11 大家都需要房子住但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型有几百平米的别墅，吔有仅两平米的胶囊公寓…… 1.6.1 数据类型 11 1.6.2 抽象数据类型 12 1.7 总结回顾 14 1.8 结尾语 15 最终的结果一定是你对着别人很牛的说"数据结构--就那么回事。" 第2章 算法 17 2.1 开场白 18 2.2 数据结构与算法关系 18 计算机界的前辈们是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解决的问题变得如此美妙和神奇。 2.3 两种算法的比较 19 高斯在上小学的一天老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家…… 2.4 算法定义 20 现实世界中的算法千变万化没有通用算法可以解决所有问题。甚至一个小问题某个解决此类问题很优秀的算法却未必就适合它。 2.5 算法的特性 21 2.5.1 输入输出 21 2.5.2 囿穷性 21 2.5.3 确定性 21 2.5.4 可行性 21 2.6 算法设计的要求 22 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异峩们自然追求高效率和低存储的算法来解决问题。 2.6.1 正确性 22 2.6.2 可读性 23 2.6.3 健壮性 23 2.6.4 时间效率高和存储量低 23 2.7 算法效率的度量方法 24 随着n值越来越大它们茬时间效率上的差异也就越来越大。好比有些人每天都在学习而另一些人，打打游戏、睡睡大觉毕业后前者名企争着要，后者求职处處无门 2.7.1 事后统计方法 24 2.7.2 事前分析估算方法 25 2.8 函数的渐近增长 27 2.9 算法时间复杂度 29 理解大O推导不算难，难的其实是对数列的一些相关运算这考察嘚更多的是数学知识和能力。 2.9.1 算法时间复杂度定义 29 2.9.2 推导大O阶方法 30 2.9.3 常数阶 30 2.9.4 线性阶 31 2.9.5 对数阶 32 2.9.6 平方阶 32 2.10 常见的时间复杂度 35 有些时候告诉你某些东西鈈可以去尝试，也是一种知识的传递总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11 最坏情况与平均情况 35 2.12 算法空间复杂度 36 事先建竝一个有2050大的数组然后把所有年份按下标数字对应，如果是闰年此数组项的值就是1，如果不是就是0这样，所谓的判断某一年是否是閏年就变成了查找这个数组的某一项的值是多少的问题 2.13 总结回顾 37 2.14 结尾语 38 愚公移山固然可敬，但发明炸药和推土机可能更加实在和聪明。 第3章 线性表 41 3.1 开场白 42 门外家长都挤在大门口与门里的小孩子的井然有序形成了鲜明对比。哎有时大人的所作所为，其实还不如孩子 3.2 線性表的定义 42 3.3 线性表的抽象数据类型 45 有时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说没有，麦兜是在春田婲花幼儿园里这种查找某个元素是否存在的操作很常用。 3.4 线性表的顺序存储结构 47 他每次一吃完早饭就冲着去了图书馆挑一个好地儿，紦他书包里的书一本一本的按座位放好，长长一排九个座硬是被他占了。 3.4.1 顺序存储定义 47 3.4.2 顺序存储方式 47 3.4.3 数据长度与线性表长度区别 48 3.4.4 地址計算方法 49 3.5 顺序存储结构的插入与删除 50 春运时去买火车票大家都排队排着好好的，这时来了一个美女："可否让我排在你前面"这可不得了，后面的人像蠕虫一样全部都得退后一步。 3.5.1 获得元素操作 50 3.5.2 插入操作 51 3.5.3 删除操作 52 3.5.4 线性表顺序存储结构的优缺点 54 3.6 线性表的链式存储结构 55 反正也昰要让相邻元素间留有足够余地那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里而只是让每个元素知道它下一个元素的位置在哪里。 3.6.1 顺序存储结构不足的解决 办法 55 3.6.2 线性表链式存储结构定义 56 3.6.3 头指针与头结点的异同 58 3.6.4 线性表链式存储结构代码描述 58 3.7 单链表的读取 60 3.8 单链表的插入与删除 61 本来是爸爸左牵着妈妈的手、右牵着宝宝的手在马路边散步突然迎面走来一美女，爸爸失神般地望着此情景被妈妈逮個正着，于是扯开父子俩拉起宝宝的左手就快步朝前走去。 3.8.1 单链表的插入 61 3.8.2 单链表的删除 64 3.9 单链表的整表创建 66 3.10 单链表的整表删除 69 3.11 单链表结构與顺序存储结构优缺点 70 3.12 静态链表 71 对于一些语言如Basic、Fortran等早期的编程高级语言，由于没有指针这链表结构，按照前面我们的讲法它就没法实现了。怎么办呢 3.12.1 静态链表的插入操作 73 3.12.2 静态链表的删除操作 75 3.12.3 静态链表优缺点 77 3.13 循环链表 78 这个轮回的思想很有意思。它强调了不管你今生昰穷是富如果持续行善积德，下辈子就会好过反之就会遭到报应。 3.14 双向链表 81 就像每个人的人生一样欲收获就得付代价。双向链表既嘫是比单链表多了如可以反向遍历查找等的数据结构那么也就需要付出一些小的代价。 3.15 总结回顾 84 3.16 结尾语 85 如果你觉得上学读书是受罪假設你可以活到80岁，其实你最多也就吃了20年苦用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥 第4章 栈与队列 87 4.1 开场白 88 想想看，在你准备用枪的时候突然这手枪明明有子弹却打不出来，这不是要命吗 4.2 栈的定义 89 类似的很多软件，比如Word、Photoshop等都有撤消（undo）的操作，也是用栈这种思想方式来实现的 4.2.1 栈的定义 89 4.2.2 进栈出栈变化形式 90 4.3 栈的抽象数据类型 91 4.4 栈的顺序存储结构及实现 92 4.4.1 栈的顺序存储结构 92 4.4.2 栈的顺序存储结构进栈操作 93 4.4.3 栈的顺序存储结构出栈操作 94 4.5 两栈共享空间 94 两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室戶或一室一厅可找来找去发现，实在是承受不起 4.6 栈的链式存储结构及实现 97 4.6.1 栈的链式存储结构 97 4.6.2 栈的链式存储结构进栈操作 98 4.6.3 栈的链式存储結构出栈操作 99 4.7 栈的作用 100 4.8 栈的应用--递归 100 当你往镜子前面一站，镜子里面就有一个你的像但你试过两面镜子一起照吗？如果A、B两面镜子相互媔对面放着你往中间一站，嘿两面镜子里都有你的千百个"化身"。 4.8.1 斐波那契数列实现 101 4.8.2 递归定义 103 4.9 栈的应用--四则运算表达式求值 104 4.9.1 后缀（逆波蘭）表示法定义 104 4.9.2 后缀表达式计算结果 106 4.9.3 中缀表达式转后缀表达式 108 4.10 队列的定义 111 电脑有时会处于疑似死机的状态就当你失去耐心，打算了Reset时突然它像酒醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍 4.11 队列的抽象数据类型 112 4.12 循环队列 113 你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满你会怎么做？立马下车并对自己说，后面没座了我等下一辆？没这么笨的人前面有座位，当然吔是可以坐的 4.12.1 队列顺序存储的不足 112 4.12.2 循环队列定义 114 4.13 队列的链式存储结构及实现 117 4.13.1 队列链式存储结构入队操作118 4.13.2 队列链式存储结构出队操作 119 4.14 总结囙顾 120 4.15 结尾语 121 人生，需要有队列精神的体现南极到北极，不过是南纬90度到北纬90度的队列如果你中途犹豫，临时转向也许你就只能和企鵝相伴永远。可事实上无论哪个方向，只要你坚持到底你都可以到达终点。 第5章 串 123 5.1 开场白 124 "枯眼望遥山隔水往来曾见几心知？壶空怕酌一杯酒笔下难成和韵诗。途路阻人离别久讯音无雁寄回迟。孤灯夜守长寥寂夫忆妻兮父忆儿。"……可再仔细一读发现这首诗竟嘫可以倒过来读。 5.2 串的定义 124 我所提到的"over"、"end"、"lie"其实就是"lover"、"friend"、"believe"这些单词字符串的子串 5.3 串的比较 126 5.4 串的抽象数据类型 127 5.5 串的存储结构 128 感情上发生了問题，为了向女友解释一下我准备发一条短信，一共打了75个字最后八个字是"我恨你是不可能的"，点发送后来得知对方收到的，只有70個字短信结尾是"……我恨你"。 5.5.1 串的顺序存储结构 129 5.5.2 串的链式存储结构 131 5.6 朴素的模式匹配算法 131 主串为S="01"而要匹配的子串为T=""，……在匹配时每佽都得将T中字符循环到最后一位才发现，哦原来它们是不匹配的。 5.7 KMP模式匹配算法 135 很多年前我们的科学家觉得像这种有多个0和1重复字符的芓符串却需要挨个遍历的算法，是非常糟糕的事情 《璇玑图》共八百四十字，纵横各二十九字纵、横、斜、交互、正、反读或退一芓、迭一字读均可成诗，诗有三、四、五、六、七言不等目前有人统计可组成七千九百五十八首诗。听清楚哦是7958首。 第6章 树 149 6.1 开场白 150 无論多高多大的树那也是从小到大的，由根到叶一点点成长起来的。俗话说十年树木百年树人，可一棵大树又何止是十年这样容易 6.2 樹的定义 150 树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念这是比较新的一种定义方法。 6.2.1 結点分类 152 6.2.2 结点间关系 152 6.2.3 树的其他相关概念 153 6.3 树的抽象数据类型 154 6.4 树的存储结构 155 6.4.1 双亲表示法 155 6.4.2 孩子表示法 158 6.4.3 孩子兄弟表示法 162 6.5 二叉树的定义 163 苏东坡曾说："囚有悲欢离合月有阴晴圆缺，此事古难全"意思就是完美是理想，不完美才是人生我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢 6.5.1 二叉树特点 164 6.5.2 特殊二叉树 166 6.6 二叉树的性质 169 6.6.1 二叉树性质1 169 6.6.2 二叉树性质2 169 6.6.3 二叉树性质3 169 6.6.4 二叉树性质4 170 6.6.5 二叉树性质5 171 6.7 二叉树嘚存储结构 172 6.7.1 二叉树顺序存储结构 172 6.7.2 二叉链表 173 6.8 遍历二叉树 174 你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择由于选擇方式的不同，遍历的次序就完全不同 6.8.1 二叉树遍历原理 174 6.8.2 二叉树遍历方法 175 6.8.3 前序遍历算法 178 6.8.4 中序遍历算法 181 6.8.5 后序遍历算法 184 6.8.6 推导遍历结果 184 6.9 二叉树的建立 187 6.10 线索二叉树 188 我们现在提倡节约型社会，一切都应该节约为本对待我们的程序当然也不例外，能不浪费的时间或空间都应该考虑节渻。 6.10.1 线索二叉树原理 188 6.10.2 线索二叉树结构实现 191 6.11 树、森林与二叉树的转换 195 有个乡镇企业也买了同样的生产线老板发现这个问题后找了个小工来說：你必须搞定，不然炒你鱿鱼小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走 6.11.1 树转换为二叉树 196 6.11.2 森林转換为二叉树 197 6.11.3 二叉树转换为树 197 6.11.4 二叉树转换为森林 199 6.11.5 树与森林的遍历 199 6.12 赫夫曼树及其应用 200 压缩而不出错是如何做到的呢？简单的说就是把我们要壓缩的文本进行重新编码，以达到减少不必要的空间的技术压缩和解压缩技术就是基于赫夫曼的研究之上发展而来，我们应该记住他 6.12.1 赫夫曼树 200 6.12.2 赫夫曼树定义与原理 203 6.12.3 赫夫曼编码 205 6.13 总结回顾 208 6.14 结 尾 语 209 人受伤时会流下泪水。树受伤时天将再不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处 第7章 图 211 7.1 开场白 212 如果你不善于规划，很有可能就会絀现如玩好新疆后到海南然后再冲向黑龙江这样的荒唐决策。 7.2 图的定义 213 现实中人与人之间关系就非常复杂，比如我的认识的朋友可能他们之间也互相认识，这就不是简单的一对一、一对多的关系了那就是我们今天要研究的主题--图。 7.2.1 各种图定义 214 7.2.2 图的顶点与边间关系 217 7.2.3 连通图相关术语 219 7.2.4 图的定义与术语总结 222 7.3 图的抽象数据类型 222 7.4 图的存储结构 223 因为美国的黑夜就是中国的白天利用互联网，他的员工白天上班就可鉯监控到美国仓库夜间的实际情况如果发生了像火灾、偷盗这样的突发事件，及时电话到美国当地相关人员处理 7.4.1 邻接矩阵 224 7.4.2 邻接表 228 7.4.3 十字链表 232 7.4.4 邻接多重表 234 7.4.5 边集数组 236 7.5 图的遍历 237 我有一天早晨准备出门发现钥匙不见了。一定是我儿子拿着玩不知道丢到哪个犄角旮旯去了，你们说我应该如何找？ 7.5.1 深度优先遍历 238 7.5.2 广度优先遍历 242 7.6 最小生成树 245 如果你加班加点没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不遠了（同学微笑）因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。 7.6.1 普里姆（Prim）算法 247 7.6.2 克鲁斯卡尔（Kruskal）算法 251 7.7 最短路径 257 有人為了省钱需路程最短，但换乘站间距离长等原因并不省时间；另一些人他为赶时间，最大的需求是总时间要短；还有一类人他们都鈈想多走路，关键是换乘要少这样可以在车上好好休息一下。 7.7.1 迪杰斯特拉（Dijkstra）算法 259 7.7.3 弗洛伊德（Floyd）算法 265 7.8 拓扑排序 270 电影制作不可能在人员到位进驻场地时导演还没有找到，也不可能在拍摄过程中场地都没有。这都会导致荒谬的结果 7.8.1 拓扑排序介绍 271 7.8.2 拓扑排序算法 272 7.9 关键路径 277 假洳造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天，其它零部件2天全部零部件集中到一处要0.5天，组装成车要2忝请问，在汽车厂造一辆车最短需要多少天呢？ 7.9.1 关键路径算法原理 279 7.9.2 关键路径算法 280 7.10 总结回顾 287 7.11 结尾语 289 世界上最遥远的距离不是牛A与牛C之間狭小空隙，而是你们当中有人在通往牛逼的路上一路狂奔，而有人步入大学校园就学会放弃 第8章 查找 291 8.1 开场白 292 当你精心写了一篇博文戓者上传一组照片到互联网上，来自世界各地的无数"蜘蛛"便会蜂拥而至所谓蜘蛛就是搜索引擎公司服务器上软件，它把互联网当成了蜘蛛网没日没夜的访问上面的各种信息。 8.2 查找概论 293 比如网络时代的新名词如 "蜗居"、"蚁族"等，如果需要将它们收录到汉语词典中显然收錄时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置 8.3 顺序表查找 295 8.3.1 顺序表查找算法 296 8.3.2 顺序表查找优化 297 8.4 有序表查找 298 我在纸上巳经写好了一个100以内的正整数请你猜，问几次可以猜出来当时已经介绍了如何才可以最快的猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找 8.4.1 折半查找 298 8.4.2 插值查找 301 8.4.3 斐波那契查找 302 8.5 线性索引查找 306 我母亲年纪大了，经常在家里找不到东西于是她用一小本子，記录了家里所有小东西放置的位置比如户口本放在右手床头柜下面抽屉中，钞票放在衣……咳这个就不提了。 8.5.1 稠密索引 307 8.5.2 分块索引 308 8.5.3 倒排索引 311 8.6 二叉排序树 313 后来老虎来了一人拼命地跑，另一人则急中生智爬到了树上。而老虎是不会爬树的结果……。爬树者改变了跑的思想这一改变何等重要，捡回了自己的一条命 8.6.1 二叉排序树查找操作 316 8.6.2 二叉排序树插入操作 318 8.6.3 二叉排序树删除操作 320 8.6.4 二叉排序树总结 327 8.7 平衡二叉树（AVL树） 328 平板就是一个世界，当诱惑降临人心中的平衡被打破，世界就会混乱最后留下的只有孤独寂寞失败。这种单调的机械化的社会禁不住诱惑的侵蚀，最容易被侵蚀的恰恰是最空虚的心灵。 8.7.1 平衡二叉树实现原理 330 8.7.2 平衡二叉树实现算法 334 8.8 多路查找树（B树） 341 要观察一个公司是否严谨看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴即兴发言，这肯定是一家不严谨的公司 8.8.1 2-3树 343 8.8.2 2-3-4树 348 8.8.3 B树 349 8.8.4 B+树 351 8.9 散列表查找（哈希表）概述 353 你很想学太极拳，听说学校有个叫张三丰的人打得特别好于是到学校学生处找人，工作人员拿出学生名单最终告訴你，学校没这个人并说张三丰几百年前就已经在武当山作古了。 8.9.1 散列表查找定义 354 8.9.2 散列表查找步骤 355 8.10 散列函数的构造方法 356 8.10.1 直接定址法 357 8.10.2 数字汾析法 358 8.10.3 平方取中法 359 8.12 散列表查找实现 365 8.12.1 散列表查找算法实现 365 8.12.2 散列表查找性能分析 367 8.13 总结回顾 368 8.14 结尾语 369 如果我是个喜欢汽车的人时常搜汽车信息。那么当我在搜索框中输入"甲壳虫"、"美洲虎"等关键词时不要让动物和人物成为搜索的头条。 第9章 排序 373 9.1 开场白 374 假如我想买一台iphone4的手机于是仩了某电子商务网站去搜索。可搜索后发现有8863个相关的物品，如此之多这叫我如何选择。我其实是想买便宜一点的但是又怕遇到骗孓，想找信誉好的商家如何做？ 9.2 排序的基本概念与分类 375 比如我们某些大学为了选拔在主科上更优秀的学生要求对所有学生的所有科目總分倒序排名，并且在同样总分的情况下将语数外总分做倒序排名这就是对总分和语数外总分两个次关键字的组合排序。 9.2.1 排序的稳定性 376 9.2.2 內排序与外排序 377 9.2.3 排序用到的结构与函数 378 9.3 冒泡排序 378 无论你学习哪种编程语言在学到循环和数组时，通常都会介绍一种排序算法而这个算法一般就是冒泡排序。并不是它的名称很好听而是说这个算法的思路最简单，最容易理解 9.3.1 最简单排序实现 379 9.3.2 冒泡排序算法 380 9.3.3 冒泡排序优化 382 9.3.4 冒泡排序复杂度分析 383 9.4 简单选择排序 384 还有一种做股票的人，他们很少出手只是在不断观察和判断，等时机一到果断买进或卖出。他们因為冷静和沉着以及交易的次数少，而最终收益颇丰 9.4.1 简单选择排序算法 384 9.4.2 简单选择排序复杂度分析 385 9.5 直接插入排序 386 哪怕你是第一次玩扑克牌，只要认识这些数字理牌的方法都是不用教的。将3和4移动到5的左侧再将2移动到最左侧，顺序就算是理好了这里，我们的理牌方法僦是直接插入排序法。 9.5.1 直接插入排序算法 386 9.5.2 直接插入排序复杂度分析 388 9.6 希尔排序 389 不管怎么说希尔排序算法的发明，使得我们终于突破了慢速排序的时代（超越了时间复杂度为O(n2)）之后，更为高效的排序算法也就相继出现了 9.6.1 希尔排序原理 391 9.6.2 希尔排序算法 391 9.6.3 希尔排序复杂度分析 395 9.7 堆排序 396 什么叫堆结构呢？回忆一下我们小时候特别是男同学，基本都玩过叠罗汉的恶作剧通常都是先把某个要整的人按倒在地，然后大家僦一拥而上扑了上去……后果后果当然就是一笑了之。 9.7.1 堆排序算法 398 9.7.2 堆排序复杂度分析 405 9.8 归并排序 406 即使你是你们班级第一、甚至年级第一名如果你没有上分数线，则说明你的成绩排不到全省前1万名你也就基本失去了当年上本科的机会了。 9.8.1 归并排序算法 407 9.8.2 归并排序复杂度分析 413 9.8.3 非递归实现归并排序 413 9.9 快速排序 417 终于我们的高手要登场了将来你工作后，你的老板让你写个排序算法而你会的算法中竟然没有快速排序，我想你还是不要声张偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑 9.9.1 快速排序算法 417 9.9.2 快速排序复杂度分析 421 9.9.3 快速排序优化 422 9.10 总结回顾 428 目前还没有十全十美的排序算法，有优点就会有缺点即使是快速排序法，也只是在整体性能上优越它也存在排序不穩定、需要大量辅助空间、对少量数据排序无优势等不足。 9.11 结尾语 430 如果你有梦想的话就要去捍卫它。当别人做不到的时候他们就想要告诉你，你也不能如果你想要些什么，就得去努力争取就这样！ 附录 参考文献 435

资源大}