写的很好的数据结构的书，浅显易懂
前言 本书起因 大家好!我是《大话设计模式》(2008年初出版)的作者,三年来,承蒙广大读 者的厚爱,《大话设计模式》取得了较大的成功。仅在当当网,截止本文写作时,就已 经有1073次评论,05次5星评价,位居五星图书榜计算机/网络类的累计总榜第二 名。此书已经成为国内原创计算机类图书最畅销的书籍之一。 对于这样一个自己喜欢做、可以做得好,而且已经得到了市场广泛认可,为很多 朋友提供帮助的事情,我没有理由不去继续做下去。这就是我准备再写书的原因。 我曾做过调查,数据结构的学习者大多都有这样的感慨:数据结构很重要,一定 要学好,但数据结构比较抽象,有些算法理解起来很困难,学得很累。可我更希望传 达这样的信息:数据结构非常有趣,很多算法是智慧的结晶,学习它是去感受计算机 编程技术的魅力,在理解掌握它的同时,整个过程都是一种愉悦的精神感受,而非枯 燥乏味的一门课程。因此我决定写作一本关于数据结构有趣的书。 不过现实总比理想来得更“现实”。要想把书写好,谈何容易,我需要突破很多困 难……瞎!不管如何,现在您看到了本书,那就说明我已经克服了困难战胜了自己 希望您可以喜欢上这本书。 本书定位 本书的定位就是一本适合读者自学数据结构的书籍,它有区别于教材,希望给大 家另一种阅读体验。 通常讲解数据结构的图书都是以教材的方式呈现。在写作前,我购买或在图书馆 借阅了十几本非常好的数据结构相关教材用来为写作本书做准备。但经过认真阅读 后,我发现,它们大多不是一本好的“自学”读物。 我没有轻视这些好书的意思,不过教材和自学读物,所面向的读者是完全不同 的 好的教材应该是提纲挈领、重点突出,一定要留出思考的空间,否则就没必要再 听老师上课了。很多内容的讲解是由老师在课堂完成,教材中有练习、课后习题、思 大话数据结构 考题等,这些大多可以通过老师来解答。比如我们中学时的语文、数学课本,很薄的 本书通常要用一学期、甚至一年的时间来学习,这就是因为它们是教材而不是自学 读物。如果是小说,可能一两天就读完了。 好的自学读物的目标是让初学者“独自”全盘掌握知识,需要强调“独自 词,这就说明读者在阅读时,是完全依靠自己的力量来向未知发出挑战。因此书中内 容,要么不写,写了就应该写透。如果读者在阅读时总是疑惑重重,那么这本书就有 很大的问题了。 我也就是在基于这样的认识,决心将《大话数据结构》真正写成一本关于数据结 构和算法的自学读物来展开写作的。 本书特色 1.趣味引导 大部分的编程类图书,在内容上基本都是直奔主题。但是尼采曾说过:“人们无法 理解他没有经历过的事情。”换句话说,我们只接受过去早已理解的事物相关的信息。 这是一种比较学习过程,在这个过程中,大脑寻找每条信息之间的联系。所以教育专 家普遍认为,吸引学生的注意力,比较好的办法是用他们比较熟知的知识开始。 因此在本书中,我会用一个故事、一个趣味题目、一部电影的介绍等形式来作为 每一章甚至很多小节的开头,选择的内容也多多少少与要讲的主题内容相关。这并不 是多余,而是有意为之。事实上,这样的形式在我的前一本书中已经得到了普遍认 可 2.图文并茂 西方有句谚语,“ A picture is worth a thousand words.(一图值千言)"。用上千个 字描述不明白的东西,很可能一张图就能解释清楚 我非常认可这个观点,所以本书虽没有达到每一页都有图,但基本做到了绝大部 分讲解都有相关图示,关键算法更是通过多图逐步分解剖析。尽管这带来了写作上的 难度,但却可以达到较好的效果。毕竟,读者通过本书开始学习数据结构时,要从一 无所知或略知一二到完全理解,甚至掌握应用,是需要一个比较艰苦的过程,用大量 的图示可以减少这个过程的长度。 3.代码详解 我在写作中尽量摒弃了传统数据结构教材的“重理论思想而轻代码讲解”的作 前言 法。在准备数据结构写作时我发现,很多教材对数据结构理论和算法设计思想讲得比 较好,可一到实际代码时,有的把代码贴出来加少量注释,有的直接用伪代码形式。 这对于上课的学生还好,毕竟有老师在课堂中去详解代码编写原理,可是对于初学数 据结构和算法的自学者而言,如果书中不去解释代码某些细节为什么那样编写的原 因,甚至代码根本不可能在某个编译器中运行通过,其挫折感是很强烈的。比如即使 理解了图结构中的最短路径求解原理,也可能无法写出最短路径的算法。 我把代码在运行过程中变量的变化融入到整个算法设计思想的讲解中,配合相应 的示意图,会帮助大家更加容易理解算法的实质。这种讲解模式在本书的第6、7、 8、9章的很多复杂算法中有具体体现,越是复杂的代码越是讲解细致。这算是本书的 一个特色,希望对读者有帮助。 4.形式新颖 我把本书的内容虚构成了一个老师上课的场景,所有内容都通过这位老师表达出 来,书中的文字非常口语化,这样做的目的是为了更加直观地让读者感觉,自己是在 学习,是在上课。有人可能会说,现在的课堂大都是让人昏昏欲睡,把读者带入上课 场景,不是更加让读者犯困吗?我觉得如果你的学习经历中听过一些优秀老师的课, 你就不会下这样的结论。好的老师讲课,是可以做到引人入胜的。 有人可能会问,我为什么不用《大话设计模式》中的对话形式,而采用讲课形式 呢?这是对数据结构这门学问的特点考虑的。设计模式主要都是思想体现,通常会仁 者见仁、智者见智,用对话展开比较容易;而数据结构中更多的是定义、术语、经典 算法等,这些公认的知识,可讨论的地方并不多,更多的是需要把它讲清楚。让两个 人在一起讨论某个设计模式的优缺点,会非常合适,而讨论数据结构定义的好坏,就 没有太大意义了,不如让一个老师告诉学生数据结构的定义好在哪里更符合实际。因 此用传统的讲课形式会好一些。 另外,本书没有习题,有思考的题目也一定会给出某种答案。但本书每个复杂知 识点的末尾,都会提供另一本书的进一步阅读建议。这也是基于它是一本自学读物的 原则。读者阅读本书可能是任何时间任何地方,如果书中存在没有解答的习题,碰到 了困难是没法及时找到老师来帮助的,因此本书尽量避免让读者有这样的困惑存在。 如果需要练习的同学,我觉得还是应该考虑再去买本习题集来学习。学习数据结构和 算法,做题和上机写代码非常有必要,从这个角度也说明,阅读完本书其实也只是完 成入门而已。 本书既然是以老师上课的形式来进行,那就免不了要融入一名教师除了授业解惑 大话]数据结构 以外,还要传达一些个人价值观的体现。书中很多细微处,如对某位科学家的尊敬、 对某个算法的推崇、对勤奋励志故事的讲述等都在表达着一个老师向学生传递真、 善、美的意愿。我始终认为,读者拿到的虽然只是一本没有表情、不会说话的书,但 其实也是在隔空与另一个朋友交流。人与人的交流不可能只是就事论事,一定会有情 感的沟通,这种情感如果能产生共鸣、达成互信,就会让事情(比如学习数据结构与 算法这件事)本身更容易理解和接受。 本书内容 本书主要是按照教育部关于计算机专业数据结构课程大纲的要求略微增减来组织 内容的。 主要包括:数据结构介绍,算法推导大0阶的方法,线性表结构的介绍,顺序结 构与链式结构差异,栈与队列的应用,串的朴素模式匹配、KMP模式匹配算法,树结 构的介绍,二又树前中后序遍历,线索二叉树,赫夫曼树及应用,图结构的介绍,图 的深度、广度遍历,最小生成树两种算法,最短路径两种算法,拓扑排序与关键路径 算法,查找应用的相关介绍,折半查找、插值查找、斐波那契查找等静态查找,稠密 索引、分块索引、倒排索引等索引技术,二又排序树、平衡二又树等动态查找,B 树、B+树技术,散列表技术,排序应用的相关介绍,冒泡、选择、插入等简单排序, 希尔、堆、归并、快速等改进排序,各位排序算法的对比等。 本书读者 数据结构是计算机软件相关专业的基础课程,几乎可以说,要想从事编程工作 无论你是否是科班出身,都不可以绕过这部分知识。因此,适合阅读本书的读者非常 广泛,包括在读的本专科、中专职高技校等计算机专业学生、想转行做开发的非专业 人员、欲考计算机研究生的应届或在职人员,以及工作后需要补学或温习数据结构和 算法的程序员等各类读者。 本书对读者的技术背景要求比较低,只要是学过一门高级编程语言,例如C、 C++、Java、C#、VB等就可以开始阅读本书。不过由于当中涉及到比较复杂的算法知 识,需要读者有一定的数学修养和逻辑思维能力,否则可能书籍的后半部分阅读起来 会比较吃力。 前言 本书研读方法 事实上,任何有难度的知识和技巧,都不是那么容易被掌握的。我尽管已经朝着 通俗易懂的方向努力,可有些数据结构,特别是经典算法,是几代科学家的智慧结 晶,因此要掌握它们还是需要读者的全力投入。 美国畅销书《如何阅读一本书》中提到“阅读可以是一件主动的事,阅读越主 动,效果越好。拿同样的书给背景相近的两个人阅读,一个人却比另一个人从书中得 到了更多,这是因为,首先在于这人的主动,其次,在于他在阅读中的每一种活动都 参与了更多的技巧。这两件事是息息相关的。阅读是一个复杂的活动,就跟写作 样,包含了大量不同的活动。要达成良好的阅读,这些活动都是不可或缺的。一个人 越能良好运作这些活动,阅读的效果也就越好。” 我当然希望读者在阅读本书后收获巨大,但这显然是一厢情愿。要想获得更多 您可能也需要付出类似我写作一样的力气来阅读,例如摘抄文字、眉批心得、稿纸演 算、代码输入电脑,以及您自己在编程工作中的运用等。这些相应活动的执行,将会 使您得到巨大的收获。 作为作者,建议本书的研读方法为: 复习C语言的基础知识。如果你掌握的是别的语言也不要紧,适当了解一些 C语言和你掌握的编程语言的语法差异还是有必要的。甚至将本书代码改造 成另一种语言本身就是一种非常好的学习方法。 ■阅读第一遍时,建议从头至尾进行。如果你对前面的知识有足够了解,当然 可以跳过直接阅读后面的章节。不过若要学习一门完整的知识并形成体系。 通读本书,还是最好的学习方法。 ■阅读时,摘抄是非常好的习惯。“最淡的墨水也胜于最强的记忆!"有不少读 者会认为摘抄了将来也不会再去看,有什么必要,但其实在写字的过程就是 大脑学习的过程,写字在减缓你阅读的速度,从而让你更好地消化阅读的内 容。相信大家都能理解,“囫囵吞枣”和“慢慢品味”的差异,学习同样如 此 ■阅读每一章时,特别是在阅读算法的推导过程时,一定要在电脑中运行代码 (本书源码的下载地址可以到hp/r723cnbbogs.com中的《大话数据结构相 关主题》中找到),了解代码的运行过程。本书的很多算法都做到了逐行讲 解,但单纯阅读可能真的很难达到理解的程度(这是纸质书无法克服的缺 陷),需要你通过开发工具调试,并设置断点和逐行执行,并参照书中的讲 解,观察变量的变化情况来理解算法的编写原理。 大话数据结构 ■阅读完每一章时,一定要在理解基础上记忆一些关键东西。最佳的效果就是 你可以不看书也做到一点不错地默写出相关算法。 ■阅读完每一章时,一定要适当练习。本书没有提供练习题,但市场上相关的 数据结构习题集比比皆是,可以选择尝试。另外互联网上也可以获得足够的 习题来给你练习。练习的目的是为了检测自己是否真的完全理解了书中的内 容。事实上很多时候,阅读中的人们只是自我感觉理解,而并非真正的明 ■学习不可能一蹴而就,数据结构和算法如果通过一本书就可以掌握,那本身 就是笑话。本书附录提供了本书写作时的参考书目,基本都是最优秀的数据 结构或相关的中文书籍各有側重,建议大家可以适当地阅读。 ■在之后的编程学习和工作中,尽量把已经学到的数据结构和算法知识运用到 现实开发中。遗忘时翻阅本书回顾相关内容,最终达到精通数据结构和相关 算法的境界。 编程语言说明 本书是用C语言编写,基于C90(soC)的标准。读者可以选择任何一款基于 C90标准的C语言开发工具或更高版本的开发工具来学习本书中的代码。 本人一直习惯于用 Visual studio2008作为开发工具,因此在写作此书时,也是用 此工具的 Visual C++来编译调试代码,一切都相安无事,但写作完成后,考虑到不同 读者应用开发工具的习惯不同,最终在编辑的建议下,决定提供一份可在C90标准的 C语言开发环境中编译通过的代码,结果发现错误百出。 例如C90标准的注释要求是“/*注释文字*/”而不允许是“//注释文字”:要求 变量声明必须要在函数的最前面,只能是“inti;fror[i=0;i<n;i++)…",而不允许如 for[inti=0i<n;i+)”这样的方式:再比如C++中函数的参数可以传递如“void Create bitree( BiTree&T”的地址变量,但在C语言中,只能传递如“woid CreateBiTree BiTree*T)”的指针变量。因此当你看到书中的有些代码到处都是“* 时,就用不着奇怪了 出于为了让代码可以在低端编译环境通过的考虑,牺牲一些代码的简捷性和优雅 性也是无可奈何和必要的。最终我将书中全部代码都改成C90标准的代码。 C语言初学者可能会因为刚接触编程语言,特别是对指针的理解不深,而担心阅 读困难。我个人感觉,单纯学习指针是很难理解它的真正用途和好处,而通过学习数 前言 据结构,特别是像链式存储结构在各种结构算法中的运用,反而可以让读者进一步的 理解指针的优越之处。从这个角度说,数据结构的学习可以反过来加强读者对C语 言,特别是指针概念的理解。 编程语言差异 C语言是一门古老的高级语言,它的应用范围非常广泛,因此我选择它作为本书 的算法展示语言。如果读者之前学过它,那么阅读本书就不存在语言障碍。懂得C+ 语言的读者,同样也不会有任何语言上的问题。 掌握Java、C#、VB等面向对象语言的读者,当面对书中大量的C语言式的结构 ( struct)声明和针对结构的参数传递的代码时,可以理解为是美的定义和由类生成对 象的传递。尽管的确存在差异,但并不影响整体对数据结构知识和算法原理的理解。 我个人感觉,哪怕是对C语言不熟悉,也不妨利用学习数据结构的机会,学习一 下C语言的编程方法,这对于将来应用其他高级语言也是有很大帮助的。 不是一个人在战斗 首先要感谢我的妻子李秀芳对我写作本书期间的全力支持,我辞职写作,没有她 精神上的理解鼓励和生活上的悉心照顾,是不可能走出这一步并顺利完成书稿的。我 们的儿子程晟涵如今已经三周岁,我是在他每日的欢声笑语和哭哭啼啼中进行每一章 节的构思和写作,希望他可以茁壮成长。我的父母已经年迈,他们为我的全职创作也 甚为担心和忧虑,这里也要说一声抱歉。 写作过程中,本人购买和借阅了与数据结构相关的大量书籍,详细书目见附录 没有前辈的贡献,就没有本书的出版,也希望本书能成为这些书籍的前期读物。在此 向这些图书作者表示衷心的感谢。 仅有作者是不可能完成图书的出版的,本人要非常感谢清华大学出版社的朋友 们,他们是本书的最初读者,也是协助本人将此书由毛糙变精良的最有力帮手。本书 的封面设计程瑜、插图设计周翔,都是在反反复复的修改中完成创作的。写作中还得 到了周筠、卢鸫翔、张伸、胡文佳、Mi、陈钢、刘超、刘唯一、杨绣国、戚妩婷、 雷顺、杨诗盈、高宇翔、林健的友情帮助,他们都在本人的创作中提出了宝贵建议。 在此向所有帮助与支持我的朋友道一声:谢谢! 程杰 目录 第1章数据结构绪论 ………丰丰……………… ① 2)34(s 1.1开场白……… 如果你交給某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折 磨他一辈子 12你数据结构怎么学的?…… 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说: “你数据结构是怎么学的?” 1.3数据结构起源……… 1.4基本概念和术语……………………………5 正所谓“巧妇难为无米之炊”,再强大的计算机,也要有“米”下锅才可以干活,否则 就是一堆破铜烂铁。这个“米”就是数据。 14.1数据…5144数据对象 6 14.2数据元素. 145数据结构.…6 14.3数据项 于世干干平斗是上号+: 6 1.5逻辑结构与物理结构…… …197 1.5.1逻辑结构… .71.52物理结构.……9 1.6抽象数据类型…………………………………………1 大家都需要房子住,但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种 各样的户型,有几百平米的别墅,也有仅两平米的胶震公寓…… 16.1数据类型 ……“ 1.62抽象数据类型 12 17总结回顾…… ………………………14