数据结构&数据库

大话数据结构 考题等,这些大多可以通过老师来解答。比如我们中学时的语文、数学课本,很薄的 一本书通常要用一学期、甚至一年的时间来学习,这就是因为它们是教材而不是自学 读物。如果是小说,可能一两天就读完了。 好的自学读物的目标是让初学者“独自”全盘掌握知识,需要强调“独自” 词,这就说明读者在阅读时,是完全依靠自己的力量来向未知发出挑战。因此书中内 容,要么不写,写了就应该写透。如果读者在阅读时总是疑惑重重,那么这本书就有 很大的问题了 我也就是在基于这样的认识,决心将《大话数据结构》真正写成一本关于数据结 构和算法的自学读物来展开写作的。 本书特色 1.趣味引导 大部分的编程类图书,在内容上基本都是直奔主题。但是尼采曾说过:“人们无法 理解他没有经历过的事情。”换句话说,我们只接受过去早已理解的事物相关的信息 这是一种比较学习过程,在这个过程中,大脑寻找每条信息之间的联系。所以教育专 家普遍认为,吸引学生的注意力,比较好的办法是用他们比较熟知的知识开始。 因此在本书中,我会用一个故事、一个趣味题目、一部电影的介绍等形式来作为 每一章甚至很多小节的开头,选择的内容也多多少少与要讲的主题内容相关。这并不 是多余,而是有意为之。事实上,这样的形式在我的前一本书中已经得到了普遍认 2.图文并茂 西方有句谚语,“ A picture is worth a thousand words.(一图值千言)”。用上千个 字描述不明白的东西,很可能一张图就能解释清楚。 我非常认可这个观点,所以本书虽没有达到每一页都有图,但基本做到了绝大部 分讲解都有相关图示,关键算法更是通过多图逐步分解剖析。尽管这带来了写作上的 难度,但却可以达到较好的效果。毕竟,读者通过本书开始学习数据结构时,要从一 无所知或略知一二到完全理解,甚至掌握应用,是需要一个比较艰苦的过程,用大量 的图示可以减少这个过程的长度。 3.代码详解 我在写作中尽量摒弃了传统数据结构教材的“重理论思想而轻代码讲解的作 前言 法。在准备数据结构写作时我发现,很多教材对数据结构理论和算法设计思想讲得比 较好,可一到实际代码时,有的把代码贴出来加少量注释,有的直接用伪代码形式。 这对于上课的学生还好,毕竟有老师在课堂中去详解代码编写原理,可是对于初学数 据结构和算法的自学者而言,如果书中不去解释代码某些细节为什么那样编写的原 因,甚至代码根本不可能在某个编译器中运行通过,其挫折感是很强烈的。比如即使 理解了图结构中的最短路径求解原理,也可能无法写出最短路径的算法。 我把代码在运行过程中变量的变化融人到整个算法设计思想的讲解中,配合相应 的示意图,会帮助大家更加容易理解算法的实质。这种讲解模式在本书的第6、7、 8、9章的很多复杂算法中有具体体现,越是复杂的代码越是讲解细致。这算是本书的 一个特色,希望对读者有帮助 4.形式新颖 我把本书的内容虚构成了一个老师上课的场景,所有内容都通过这位老师表达出 来,书中的文字非常口语化,这样做的目的是为了更加直观地让读者感觉,自己是在 学习,是在上课。有人可能会说,现在的课堂大都是让人昏昏欲睡,把读者带入上课 场景,不是更加让读者犯困吗?我觉得如果你的学习经历中听过一些优秀老师的课, 你就不会下这样的结论。好的老师讲课,是可以做到引人入胜的。 有人可能会间,我为什么不用《大话设计模式》中的对话形式,而采用讲课形式 呢?这是对数据结构这门学问的特点考虑的。设计模式主要都是思想体现,通常会仁 者见仁、智者见智,用对话展开比较容易;而数据结构中更多的是定义、术语、经典 算法等,这些公认的知识,可讨论的地方并不多,更多的是需要把它讲清楚。让两个 人在一起讨论某个设计模式的优缺点,会非常合适,而讨论数据结构定义的好坏,就 没有太大意义了,不如让一个老师告诉学生数据结构的定义好在哪里更符合实际。因 此用传统的讲课形式会好一些。 另外,本书没有习题,有思考的题目也一定会给出某种答案。但本书每个复杂知 识点的末尾,都会提供另一本书的进一步阅读建议。这也是基于它是一本自学读物的 原则。读者阅读本书可能是任何时间任何地方,如果书中存在没有解答的习题,碰到 了困难是没法及时找到老师来帮助的,因此本书尽量避免让读者有这样的困惑存在。 如果需要练习的同学,我觉得还是应该考虑再去买本习题集来学习。学习数据结构和 算法,做题和上机写代码非常有必要,从这个角度也说明,阅读完本书其实也只是完 成入门而已。 本书既然是以老师上课的形式来进行,那就免不了要融入一名教师除了授业解惑 数据结构 以外,还要传达一些个人价值观的体现。书中很多细微处,如对某位科学家的尊敬、 对某个算法的推崇、对勤奋励志故事的讲述等都在表达着一个老师向学生传递真 善、美的意愿。我始终认为,读者拿到的虽然只是一本没有表情、不会说话的书,但 其实也是在隔空与另一个朋友交流。人与人的交流不可能只是就事论事,一定会有情 感的沟通,这种情感如果能产生共鸣、达成互信,就会让事情(比如学习数据结构与 算法这件事)本身更容易理解和接受。 本书内容 本书主要是按照教育部关于计算机专业数据结构课程大纲的要求略微增减来组织 内容的。 主要包括:数据结构介绍,算法推导大O阶的方法,线性表结构的介绍,顺序结 构与链式结构差异,栈与队列的应用,串的朴素模式匹配、KMP模式匹配算法,树结 构的介绍,二叉树前中后序遍历,线索二叉树,赫夫曼树及应用,图结构的介绍,图 的深度、广度遍历,最小生成树两种算法,最短路径两种算法,拓扑排序与关键路径 算法,査找应用的相关介绍,折半查找、插值查找、斐波那契查找等静态查找,稠密 索引、分块索引、倒排索引等索引技术,二叉排序树、平衡二又树等动态查找,B 树、B+树技术,散列表技术,排序应用的相关介绍,冒泡、选择、插入等简单排序, 希尔、堆、归并、快速等改进排序,各位排序算法的对比等。 本书读者 数据结构是计算机软件相关专业的基础课程,几乎可以说,要想从事编程工作, 无论你是否是科班出身,都不可以绕过这部分知识。因此,适合阅读本书的读者非常 广泛,包括在读的本专科、中专职高技校等计算机专业学生、想转行做开发的非专业 人员、欲考计算机研究生的应届或在职人员,以及工作后需要补学或温习数据结构和 算法的程序员等各类读者。 本书对读者的技术背景要求比较低,只要是学过一门高级编程语言,例如C C+、Java、C#、VB等就可以开始阅读本书。不过由于当中涉及到比较复杂的算法知 识,需要读者有一定的数学修养和逻辑思维能力,否则可能书籍的后半部分阅读起来 会比较吃力。 前言 本书研读方法 事实上,任何有难度的知识和技巧,都不是那么容易被掌握的。我尽管已经朝着 通俗易懂的方向努力,可有些数据结构,特别是经典算法,是几代科学家的智慧结 晶,因此要掌握它们还是需要读者的全力投入。 美国畅销书《如何阅读一本书》中提到“阅读可以是一件主动的事,阅读越主 动,效果越好。拿同样的书给背景相近的两个人阅读,一个人却比另一个人从书中得 到了更多,这是因为,首先在于这人的主动,其次,在于他在阅读中的每一种活动都 参与了更多的技巧。这两件事是息息相关的。阅读是一个复杂的活动,就跟写作 样,包含了大量不同的活动。要达成良好的阅读,这些活动都是不可或缺的。一个人 越能良好运作这些活动,阅读的效果也就越好。 我当然希望读者在阅读本书后收获巨大,但这显然是一厢情愿。要想获得更多, 您可能也需要付出类似我写作一样的力气来阋读,例如摘抄文字、眉批心得、稿纸演 算、代码输入电脑,以及您自己在编程工作中的运用等。这些相应活动的执行,将会 使您得到巨大的收获。 作为作者,建议本书的研读方法为: 复习C语言的基础知识。如果你掌握的是别的语言也不要紧,适当了解一些 C语言和你掌握的编程语言的语法差异还是有必要的。甚至将本书代码改造 成另一种语言本身就是一种非常好的学习方法 阅读第一遍时,建议从头至尾进行。如果你对前面的知识有足够了解,当然 可以跳过直接阅读后面的章节。不过若要学习一门完整的知识并形成体系。 通读本书,还是最好的学习方法。 ■阅读时,摘抄是非常好的习惯。“最淡的墨水也胜于最强的记忆!”有不少读 者会认为摘抄了将来也不会再去看,有什么必要,但其实在写字的过程就是 大脑学习的过程,写字在减缓你阅读的速度,从而让你更好地消化阅读的内 容。相信大家都能理解,“囫囵吞枣”和“慢慢品味”的差异,学习同样如 此 m阅读每一章时,特别是在阅读算法的推导过程时,一定要在电脑中运行代码 (本书源码的下载地址可以到htp://cj723cnblogs.com中的《大话数据结构相 关主题》中找到),了解代码的运行过程。本书的很多算法都做到了逐行讲 解,但单纯阅读可能真的很难达到理解的程度(这是纸质书无法克服的缺 陷),需要你通过开发工具调试,并设置断点和逐行执行,并参照书中的讲 解,观察变量的变化情况来理解算法的编写原理。 庆话数据结构 ■阅读完每一章时,一定要在理解基础上记忆一些关键东西。最佳的效果就是 你可以不看书也做到一点不错地默写出相关算法 阅读完每一章时,一定要适当练习。本书没有提供练习题,但市场上相关的 数据结构习题集比比皆是,可以选择尝试。另外互联网上也可以获得足够的 习题来给你练习。练习的目的是为了检测自己是否真的完全理解了书中的内 容。事实上很多时候,阅读中的人们只是自我感觉理解,而并非真正的明 学习不可能—蹴而就,数据结构和算法如果通过一本书就可以掌握,那本身 就是笑话。本书附录提供了本书写作时的参考书目,基本都是最优秀的数据 结构或相关的中文书籍各有侧重,建议大家可以适当地阅读。 ■在之后的编程学习和工作中,尽量把已经学到的数据结构和算法知识运用到 现实开发中。遗忘时翻阅本书回顾相关内容,最终达到精通数据结构和相关 算法的境界。 编程语言说明 本书是用C语言编写,基于C90(lsOC)的标准。读者可以选择任何一款基于 C90标准的C语言开发工具或更高版本的开发工具来学习本书中的代码。 本人一直习惯于用 Visual Studio2008作为开发工具,因此在写作此书时,也是用 此工具的 Visual C+来编译调试代码,一切都相安无事,但写作完成后,考虑到不同 读者应用开发工具的习惯不同,最终在编辑的建议下,决定提供一份可在C90标准的 C语言开发环境中编译通过的代码,结果发现错误百出。 例如C90标准的注释要求是“/*注释文字*/”而不允许是“/注释文字”:要求 变量声明必须要在函数的最前面,只能是“inti;for(i=0;i