大话数据结构 (程杰) (Z-Library)

大话数据结构 作者：程杰 字数：29.1万字 大小：49.00MB 书号：978-7-3022-5565-9 出版：2011-06-01 更新：2015-02-16 超级畅销书《大话设计模式》作者程杰三年磨一剑推出大话第二季， 以一个计算机教师教学为场景，讲解数据结构和相关算法的知识。 《大话数据结构》是一本关于数据结构和算法的自学读物，全书模拟 上课场景，让一个说话有趣的老师来和同学们交流数据结构知识。它 不板着脸灌输，它期望和读者做朋友，在每每的会心一笑中，只是融 入了读者脑海，化为读者自己的本领。它是这么做的—— 1、一图值千言。作者精心设计了多幅结构独特的图片，充分运用图形 语言来体现抽象内容，力求让读者通过图形的直观表达，更高效地换 取数据结构的知识。 2、善于打比方。世界上很多道理都是相通的。精心构思的类比能让人 发出“原来如此”的感叹。读者会发现：枯燥的数据结构知识背后， 也隐藏着一个个生活中的小故事。 3、细致深入，适合自学。作者对数据结构涉及到的一些经典算法进行 了逐行分析，并进行了多算法比较。 本书适合学过一门编程语言的如下读者： • 在读的大中专计算机专业学生； • 想转行做开发的非专业人员；

• 欲考计算机研究生的应届或在职人员； • 工作后需要补学或温习数据结构和算法的程序员。 前言 本书起因 大家好！我是《大话设计模式》（2008年初出版）的作者，三年来， 承蒙广大读者的厚爱，《大话设计模式》取得了较大的成功。仅在当 当网，截止本文写作时，就已经有1073次评论，705次5星评价，位居 五星图书榜计算机/网络类的累计总榜第二名。此书已经成为国内原创 计算机类图书最畅销的书籍之一。 对于这样一个自己喜欢做、可以做得好，而且已经得到了市场广泛认 可，为很多朋友提供帮助的事情，我没有理由不去继续做下去。这就 是我准备再写书的原因。 我曾做过调查，数据结构的学习者大多都有这样的感慨：数据结构很 重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困 难，学得很累。可我更希望传达这样的信息：数据结构非常有趣，很 多算法是智慧的结晶，学习它是去感受计算机编程技术的魅力，在理 解掌握它的同时，整个过程都是一种愉悦的精神感受，而非枯燥乏味 的一门课程。因此我决定写作一本关于数据结构有趣的书。 不过现实总比理想来得更“现实”。要想把书写好，谈何容易，我需 要突破很多困难……嗐！不管如何，现在您看到了本书，那就说明我 已经克服了困难战胜了自己。希望您可以喜欢上这本书。 本书定位 本书的定位就是一本适合读者自学数据结构的书籍，它有区别于教 材，希望给大家另一种阅读体验。 通常讲解数据结构的图书都是以教材的方式呈现。在写作前，我购买 或在图书馆借阅了十几本非常好的数据结构相关教材用来为写作本书

做准备。但经过认真阅读后，我发现，它们大多不是一本好的“自 学”读物。 我没有轻视这些好书的意思，不过教材和自学读物，所面向的读者是 完全不同的。 好的教材应该是提纲挈领、重点突出，一定要留出思考的空间，否则 就没必要再听老师上课了。很多内容的讲解是由老师在课堂完成，教 材中有练习、课后习题、思考题等，这些大多可以通过老师来解答。 比如我们中学时的语文、数学课本，很薄的一本书通常要用一学期、 甚至一年的时间来学习，这就是因为它们是教材而不是自学读物。如 果是小说，可能一两天就读完了。 好的自学读物的目标是让初学者“独自”全盘掌握知识，需要强调 “独自”一词，这就说明读者在阅读时，是完全依靠自己的力量来向 未知发出挑战。因此书中内容，要么不写，写了就应该写透。如果读 者在阅读时总是疑惑重重，那么这本书就有很大的问题了。 我也就是在基于这样的认识，决心将《大话数据结构》真正写成一本 关于数据结构和算法的自学读物来展开写作的。 本书特色 1．趣味引导 大部分的编程类图书，在内容上基本都是直奔主题。但是尼采曾说 过：“人们无法理解他没有经历过的事情。”换句话说，我们只接受 过去早已理解的事物相关的信息。这是一种比较学习过程，在这个过 程中，大脑寻找每条信息之间的联系。所以教育专家普遍认为，吸引 学生的注意力，比较好的办法是用他们比较熟知的知识开始。 因此在本书中，我会用一个故事、一个趣味题目、一部电影的介绍等 形式来作为每一章甚至很多小节的开头，选择的内容也多多少少与要 讲的主题内容相关。这并不是多余，而是有意为之。事实上，这样的 形式在我的前一本书中已经得到了普遍认可。 2．图文并茂

西方有句谚语，“A picture is worth a thou-sand words.（一图值 千言）”。用上千个字描述不明白的东西，很可能一张图就能解释清 楚。 我非常认可这个观点，所以本书虽没有达到每一页都有图，但基本做 到了绝大部分讲解都有相关图示，关键算法更是通过多图逐步分解剖 析。尽管这带来了写作上的难度，但却可以达到较好的效果。毕竟， 读者通过本书开始学习数据结构时，要从一无所知或略知一二到完全 理解，甚至掌握应用，是需要一个比较艰苦的过程，用大量的图示可 以减少这个过程的长度。 3．代码详解 我在写作中尽量摒弃了传统数据结构教材的“重理论思想而轻代码讲 解”的作法。在准备数据结构写作时我发现，很多教材对数据结构理 论和算法设计思想讲得比较好，可一到实际代码时，有的把代码贴出 来加少量注释，有的直接用伪代码形式。这对于上课的学生还好，毕 竟有老师在课堂中去详解代码编写原理，可是对于初学数据结构和算 法的自学者而言，如果书中不去解释代码某些细节为什么那样编写的 原因，甚至代码根本不可能在某个编译器中运行通过，其挫折感是很 强烈的。比如即使理解了图结构中的最短路径求解原理，也可能无法 写出最短路径的算法。 我把代码在运行过程中变量的变化融入到整个算法设计思想的讲解 中，配合相应的示意图，会帮助大家更加容易理解算法的实质。这种 讲解模式在本书的第6、7、8、9章的很多复杂算法中有具体体现，越 是复杂的代码越是讲解细致。这算是本书的一个特色，希望对读者有 帮助。 4．形式新颖 我把本书的内容虚构成了一个老师上课的场景，所有内容都通过这位 老师表达出来，书中的文字非常口语化，这样做的目的是为了更加直 观地让读者感觉，自己是在学习，是在上课。有人可能会说，现在的 课堂大都是让人昏昏欲睡，把读者带入上课场景，不是更加让读者犯 困吗？我觉得如果你的学习经历中听过一些优秀老师的课，你就不会 下这样的结论。好的老师讲课，是可以做到引人入胜的。

有人可能会问，我为什么不用《大话设计模式》中的对话形式，而采 用讲课形式呢？这是对数据结构这门学问的特点考虑的。设计模式主 要都是思想体现，通常会仁者见仁、智者见智，用对话展开比较容 易；而数据结构中更多的是定义、术语、经典算法等，这些公认的知 识，可讨论的地方并不多，更多的是需要把它讲清楚。让两个人在一 起讨论某个设计模式的优缺点，会非常合适，而讨论数据结构定义的 好坏，就没有太大意义了，不如让一个老师告诉学生数据结构的定义 好在哪里更符合实际。因此用传统的讲课形式会好一些。 另外，本书没有习题，有思考的题目也一定会给出某种答案。但本书 每个复杂知识点的末尾，都会提供另一本书的进一步阅读建议。这也 是基于它是一本自学读物的原则。读者阅读本书可能是任何时间任何 地方，如果书中存在没有解答的习题，碰到了困难是没法及时找到老 师来帮助的，因此本书尽量避免让读者有这样的困惑存在。如果需要 练习的同学，我觉得还是应该考虑再去买本习题集来学习。学习数据 结构和算法，做题和上机写代码非常有必要，从这个角度也说明，阅 读完本书其实也只是完成入门而已。 本书既然是以老师上课的形式来进行，那就免不了要融入一名教师除 了授业解惑以外，还要传达一些个人价值观的体现。书中很多细微 处，如对某位科学家的尊敬、对某个算法的推崇、对勤奋励志故事的 讲述等都在表达着一个老师向学生传递真、善、美的意愿。我始终认 为，读者拿到的虽然只是一本没有表情、不会说话的书，但其实也是 在隔空与另一个朋友交流。人与人的交流不可能只是就事论事，一定 会有情感的沟通，这种情感如果能产生共鸣、达成互信，就会让事情 （比如学习数据结构与算法这件事）本身更容易理解和接受。 本书内容 本书主要是按照教育部关于计算机专业数据结构课程大纲的要求略微 增减来组织内容的。 主要包括：数据结构介绍，算法推导大O阶的方法，线性表结构的介 绍，顺序结构与链式结构差异，栈与队列的应用，串的朴素模式匹 配、KMP模式匹配算法，树结构的介绍，二叉树前中后序遍历，线索二 叉树，赫夫曼树及应用，图结构的介绍，图的深度、广度遍历，最小 生成树两种算法，最短路径两种算法，拓扑排序与关键路径算法，查

找应用的相关介绍，折半查找、插值查找、斐波那契查找等静态查 找，稠密索引、分块索引、倒排索引等索引技术，二叉排序树、平衡 二叉树等动态查找，B树、B+树技术，散列表技术，排序应用的相关介 绍，冒泡、选择、插入等简单排序，希尔、堆、归并、快速等改进排 序，各位排序算法的对比等。 本书读者 数据结构是计算机软件相关专业的基础课程，几乎可以说，要想从事 编程工作，无论你是否是科班出身，都不可以绕过这部分知识。因 此，适合阅读本书的读者非常广泛，包括在读的本专科、中专职高技 校等计算机专业学生、想转行做开发的非专业人员、欲考计算机研究 生的应届或在职人员，以及工作后需要补学或温习数据结构和算法的 程序员等各类读者。 本书对读者的技术背景要求比较低，只要是学过一门高级编程语言， 例如C、C++、Java、C#、VB等就可以开始阅读本书。不过由于当中涉 及到比较复杂的算法知识，需要读者有一定的数学修养和逻辑思维能 力，否则可能书籍的后半部分阅读起来会比较吃力。 本书研读方法 事实上，任何有难度的知识和技巧，都不是那么容易被掌握的。我尽 管已经朝着通俗易懂的方向努力，可有些数据结构，特别是经典算 法，是几代科学家的智慧结晶，因此要掌握它们还是需要读者的全力 投入。 美国畅销书《如何阅读一本书》中提到“阅读可以是一件主动的事， 阅读越主动，效果越好。拿同样的书给背景相近的两个人阅读，一个 人却比另一个人从书中得到了更多，这是因为，首先在于这人的主 动，其次，在于他在阅读中的每一种活动都参与了更多的技巧。这两 件事是息息相关的。阅读是一个复杂的活动，就跟写作一样，包含了 大量不同的活动。要达成良好的阅读，这些活动都是不可或缺的。一 个人越能良好运作这些活动，阅读的效果也就越好。” 我当然希望读者在阅读本书后收获巨大，但这显然是一厢情愿。要想 获得更多，您可能也需要付出类似我写作一样的力气来阅读，例如摘

抄文字、眉批心得、稿纸演算、代码输入电脑，以及您自己在编程工 作中的运用等。这些相应活动的执行，将会使您得到巨大的收获。 作为作者，建议本书的研读方法为： 复习C语言的基础知识。如果你掌握的是别的语言也不要紧，适当 了解一些C语言和你掌握的编程语言的语法差异还是有必要的。甚 至将本书代码改造成另一种语言本身就是一种非常好的学习方 法。 阅读第一遍时，建议从头至尾进行。如果你对前面的知识有足够 了解，当然可以跳过直接阅读后面的章节。不过若要学习一门完 整的知识并形成体系。通读本书，还是最好的学习方法。 阅读时，摘抄是非常好的习惯。“最淡的墨水也胜于最强的记 忆！”有不少读者会认为摘抄了将来也不会再去看，有什么必 要，但其实在写字的过程就是大脑学习的过程，写字在减缓你阅 读的速度，从而让你更好地消化阅读的内容。相信大家都能理 解，“囫囵吞枣”和“慢慢品味”的差异，学习同样如此。 阅读每一章时，特别是在阅读算法的推导过程时，一定要在电脑 中运行代码（本书源码的下载地址可以到 http://cj723.cnblogs.com中的 《大话数据结构相关主题》中找到），了解代码的运行过程。本书的 很多算法都做到了逐行讲解，但单纯阅读可能真的很难达到理解的程 度（这是纸质书无法克服的缺陷），需要你通过开发工具调试，并设 置断点和逐行执行，并参照书中的讲解，观察变量的变化情况来理解 算法的编写原理。 阅读完每一章时，一定要在理解基础上记忆一些关键东西。最佳 的效果就是你可以不看书也做到一点不错地默写出相关算法。 阅读完每一章时，一定要适当练习。本书没有提供练习题，但市 场上相关的数据结构习题集比比皆是，可以选择尝试。另外互联 网上也可以获得足够的习题来给你练习。练习的目的是为了检测 自己是否真的完全理解了书中的内容。事实上很多时候，阅读中 的人们只是自我感觉理解，而并非真正的明白。 学习不可能一蹴而就，数据结构和算法如果通过一本书就可以掌 握，那本身就是笑话。本书附录提供了本书写作时的参考书目，

基本都是最优秀的数据结构或相关的中文书籍各有侧重，建议大 家可以适当地阅读。 例如C90标准的注释要求是“/ 注释文字 /”而不允许是“//注释文 字”：要求变量声明必须要在函数的最前面，只能是“int i;for(i=0;i<n;i++)……”，而不允许如“for(int i=0;i<n;i++)” 这样的方式：再比如C++中函数的参数可以传递如“void CreateBiTree(BiTree &T)”的地址变量，但在C语言中，只能传递如 “void CreateBi-Tree(BiTree T)”的指针变量。因此当你看到书中 的有些代码到处都是“ ”时，就用不着奇怪了。 出于为了让代码可以在低端编译环境通过的考虑，牺牲一些代码的简 捷性和优雅性也是无可奈何和必要的。最终我将书中全部代码都改成 C90标准的代码。 C语言初学者可能会因为刚接触编程语言，特别是对指针的理解不深， 而担心阅读困难。我个人感觉，单纯学习指针是很难理解它的真正用 途和好处，而通过学习数据结构，特别是像链式存储结构在各种结构 算法中的运用，反而可以让读者进一步的理解指针的优越之处。从这 个角度说，数据结构的学习可以反过来加强读者对C语言，特别是指针 概念的理解。 编程语言差异 C语言是一门古老的高级语言，它的应用范围非常广泛，因此我选择它 作为本书的算法展示语言。如果读者之前学过它，那么阅读本书就不 存在语言障碍。懂得C++语言的读者，同样也不会有任何语言上的问 题。 掌握Java、C#、VB等面向对象语言的读者，当面对书中大量的C语言式 的结构（struct）声明和针对结构的参数传递的代码时，可以理解为 是类的定义和由类生成对象的传递。尽管的确存在差异，但并不影响 整体对数据结构知识和算法原理的理解。 我个人感觉，哪怕是对C语言不熟悉，也不妨利用学习数据结构的机 会，学习一下C语言的编程方法，这对于将来应用其他高级语言也是有 很大帮助的。

不是一个人在战斗 首先要感谢我的妻子李秀芳对我写作本书期间的全力支持，我辞职写 作，没有她精神上的理解鼓励和生活上的悉心照顾，是不可能走出这 一步并顺利完成书稿的。我们的儿子程晟涵如今已经三周岁，我是在 他每日的欢声笑语和哭哭啼啼中进行每一章节的构思和写作，希望他 可以茁壮成长。我的父母已经年迈，他们为我的全职创作也甚为担心 和忧虑，这里也要说一声抱歉。 写作过程中，本人购买和借阅了与数据结构相关的大量书籍，详细书 目见附录。没有前辈的贡献，就没有本书的出版，也希望本书能成为 这些书籍的前期读物。在此向这些图书作者表示衷心的感谢。 仅有作者是不可能完成图书的出版的，本人要非常感谢清华大学出版 社的朋友们，他们是本书的最初读者，也是协助本人将此书由毛糙变 精良的最有力帮手。本书的封面设计程瑜、插图设计周翔，都是在反 反复复的修改中完成创作的。写作中还得到了周筠、卢鸫翔、张伸、 胡文佳、Milo、陈钢、刘超、刘唯一、杨绣国、戚妩婷、雷顺、杨诗 盈、高宇翔、林健的友情帮助，他们都在本人的创作中提出了宝贵建 议。 在此向所有帮助与支持我的朋友道一声：谢谢！ 程杰 编者的话 2007年，一本特立独行的IT技术图书《大话设计模式》横空出世，开 创了一种新派技术图书风格。当年以及后来的数年间，横扫各大排 行，目前销售已经超过5万册，几乎是纯粹的店销销量，在最近10年的 IT图书市场中，这是个了不起的数据。 作者程杰并没有满足这个成绩，耗时3年潜心创作了另外一本同样是程 序员基础的著作——《大话数据结构》。 说实话，作为策划，我并没有过多干预作者的创作过程，仅仅是在细 节上提出我的一些看法。我的工作更多的是与作者来回推敲成稿后的

一些说法或者技术点上的问题，另外还反复探讨了书中的类比案例的 可理解性。最终细节敲定还是在上海一家咖啡馆里完成的，我和作者 在那里折腾了一下午，终于达成共识。 数据结构在某种程度上和设计模式类似，都是前辈的武功套路。不同 的是，设计模式是近几十年的卓越程序员的智慧结晶，而数据结构是 几百上千年的无数科学家、数学家的智慧沉淀，更加具有深厚的背 景。 大家知道，程序是利用计算机高速运算能力来协助我们处理一些需要 海量运算得出结果的问题，应用程序花哨的界面和有效的用户体验， 归根到底都需要在后台看不见的地方进行运算，得出我们需要的结果 ——无论是在气象预报还是“极品飞车”。 一台计算机的CPU运算能力是固定的，只会机械地接受程序的指令，所 以，算法的优劣就决定了程序设计水平的高低。举个简单的例子，数 据库性能优化这个工作，收费是按照小时来计算的，水平高的每小时 可以达到30万美金，为什么会值这么多钱？有价值吗？这其实就是算 法的力量，使用优秀的算法可以为大型企业节省海量的硬件投入同时 带来巨大的效率提升——比如之前需要100台小型机，优化之后只需要 10台就够了；之前查询一个数据需要一分钟出来结果，优化之后1秒钟 就够了……这些对于企业来说，节省的成本可就远远不止投入的几十 上百万的优化费用了。 国内外优秀的程序员很多毕业于数学专业，也在一定程度上说明了这 个问题。国内的程序开发现状跟国外略有不同，大家都在关注界面和 用户体验，在算法上往往要求不高。这其实是国内软件行业与国外软 件行业的最大差距所在。 我们的程序员因为在受教育的过程中（大都是在大学），由于种种原 因，数据结构和算法的基本功通常要差一些，等从业以后想再补课又 缺乏好的 教材，或者说适合自学的教材。数据结构不是说没有优秀教 材，比如《数据结构》《算法导论》这样的经典著作我们绝对不能说 不好，但是作为自学，实在是有点难啃。《大话数据结构》延续了作 者一贯的轻松调侃的风格，采用了师生对话的方式，展开讨论，其中 穿插了大量“庸俗”的类比案例，帮助大家迅速“开窍”。

在我的一篇博文（kobeluan.blog.51cto.com/237742/212175）中谈到 国内原创技术书整体层次偏低，不是因为国内没有高手，最关键的原 因有两条：第一，国内版税太低，与高手作者的收入差别太大，导致 很多人没有时间和心气来写书；第二，国内知识产权保护不力，出版 社无法用提高定价的方式来为读者和作者提供更好的服务。 类似程杰这样的作者，真诚地将自己的感悟奉献出来，与作者的用心 相比，作为策划编辑付出的劳动就不值得一提了。这里真心希望读者 可以从书中找到需要的东西，也希望国内更多高人涌现出来，为大家 创作更适合中国人阅读的优秀技术图书。清华大学出版社　栾大成启 示数据结构：是相互之间存在一种或多种特定关系的数据元素的集 合。 第1章 数据结构绪论 启示 数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。 1.1　开场白 If you give someone a program, you willfrustrate them for a day; if you teach themhow to program, you will frustrate them fora lifetime.（如果你交给某人一个程序，你将折磨他一整天；如 果你教某人如何编写程序，你将折磨他一辈子。） 而我可能就是要折磨你们一辈子的那个人。大家好！我是《数据结 构》这门课的老师，我叫封清扬。同学私下里都叫我“疯子”，嘿 嘿，疯子可是有思想的标志哦。 在座的大家给我面子，都来选修我的课，这点我很高兴。不过在上课 前，有些话还是要先说一下。 数据结构是计算机专业的基础课程，但也是一门不太容易学好的课， 它当中有很多费脑子的东西，之后在上课时，你若碰到了困惑或不解

的地方，都是很正常的反应，就像你想乘飞机去旅行，在飞机场晚点 几个钟头，上了飞机后又颠簸恐慌了一把一样，别大惊小怪，都很平 常，只要能安全到达就是成功。 如果你的学习目的是为了将来要做一个优秀的程序员，向微软、 Google的工程师们看齐，那么你应该要努力学好它，不单是来听课、 看看教科书，还需要课后做题和上机练习。不过话说回来，如果你真 有这样的志向，课前就该开始研究了，这样来听我的课，就更加有主 动性，收获也会更大。 如果你的目的是为了考计算机、软件方面的研究生，那么这门必考 课，你现在就可以准备起来——很多时候，考研玩的不是智商，其实 就是一个人投入的时间而已。 如果你只是为了混个学分，那么你至少应该要坚持来上课，在我的课 堂上听懂了，学明白了，考前适当地复习，拿下这几个学分应该不在 话下。 如果你只是来打酱油的，当然也可以，我的课不妨碍你打酱油，但你 也不要妨碍其他同学坐到好位子，所以请靠后坐，并且保持安静，静 心打酱油就好。 如果，我是说真的如果，你是一个对编程无比爱好的人，你学数据结 构的目的，既不是为了工作为了钱，也不是为了学位和考试，而只是 为了更好地去感受编程之美。啊，你应该得到我的欣赏，我想我非常 愿意与你成为朋友——因为我自己也没有做到如此纯粹地去学习和应 用它。 1.2　你数据结构怎么学的？ 早先我有一个学生叫蔡遥，绰号“小菜”。他前段时间一直通过E- mail与我交流，其中说起了他工作的一些经历，感慨万千。我在这里 就讲讲小菜的故事。 他告诉我，在做我学生时，其实根本就没好好学数据结构，时常逃 课，考试也是临时突击后勉强及格。毕业后，他几经求职，算是找到 了一份程序员的工作。

工作中，有一次他们需要开发一个客服电话系统，他们项目经理安排 小菜完成客户排队模块的代码工作。 小菜觉得这个很容易，用数据库设计了一张客户排队表，并且用一个 自动递增的整型数字作为客户的编号。只要来一个客户，就给这张表 的末尾插入一条数据。等客服系统一有空闲，就从这张表中取出最小 编号的客户提交，并且删除这条记录。花了两天时间，他完成开发并 测试通过后，得意地提交了代码。谁知他们的项目经理，看完代码 后，跑到他的桌前，拍着桌子对他说：“你数据结构怎么学的？这种 实时的排队模块，用什么数据库呀，在内存中完成不就行了吗。赶快 改，今天一定要完成，明天一早交给我。” 小菜吓得一身冷汗，这脸丢得有些大了，自己试用期都没结束，别因 此失去工作。于是他当天加班加点，忙到晚上十一点，用数组变量重 新实现了这个功能，因为考虑到怕数组不够大而溢出，于是他设计100 作为数组的长度。 回到家中，他害怕这个代码有问题，于是就和他的表哥大鸟说起了这 个事。他表哥笑嘻嘻地对他说：“你数据结构怎么学的？”小菜惊讶 地张着大口，一句话也说不出来。然后他表哥告诉他，这种实时的排 队系统，通常用数据结构中的“队列结构”是比较好的，用数组虽然 也可以，但是又要考虑溢出，又要考虑新增和删除后的数据移动，总 的说来很不方便。你只要这样……这样……就可以了。 小菜在大鸟的帮助下，忙到凌晨3点，重新用队列结构又写了一遍代 码，上班时用U盘拷回公司，终于算是过了项目经理这一关。 之后，小菜开始重视数据结构，找回大学的课本重新学习。他还给我 发了好些邮件，问了我不少他困惑的数据结构和算法的问题，我也一 一给了他解答。终于有一天，他学完了整个课程的内容，并给我写了 一封感谢信，信中是这么说的：“封老师：您好！感谢您这段时间的 帮助，在大学时没有好好上您的课真是我最大的遗憾。我现在已经学 完了《数据结构》整本书的内容，收获还是很大的。可是我一直有这 样的困惑想请教您，那就是我在工作中发现，我所需要的如栈、队 列、链表、散列表等结构，以及查找、排序等算法，在编程语言的开 发工具包中都有完美的实现，我只需要掌握如何使用它们就可以了， 为什么还要去弄懂这里面的算法原理呢？”

我收到这封信时，立马跳了起来，马上拨通了他的手机，第一句话就 是……你们猜猜看，我说了啥？“你数据结构怎么学的？”（全场同 学齐声大喊，大笑） 好了，我为什么这么讲，等你们学完我的课程就自然会明白。我只希 望在将来，不要有某个人也对你们说出这句话，如果当真听到了这句 话，就拜托你不要说你的数据结构老师是我封清扬，嘿嘿。 现在我们正式开始上课。 1.3　数据结构起源 早期人们都把计算机理解为数值计算工具，就是感觉计算机当然是用 来计算的，所以计算机解决问题，应该是先从具体问题中抽象出一个 适当的数据模型，设计出一个解此数据模型的算法，然后再编写程 序，得到一个实际的软件。 可现实中，我们更多的不是解决数值计算的问题，而是需要一些更科 学有效的手段（比如表、树和图等数据结构）的帮助，才能更好地处 理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操 作对象，以及它们之间的关系和操作等相关问题的学科。 1968年，美国的高德纳（Donald E. Knuth）教授在其所写的《计算机 程序设计艺术》第一卷《基本算法》中，较系统地阐述了数据的逻辑 结构和存储结构及其操作，开创了数据结构的课程体系。同年，数据 结构作为一门独立的课程，在计算机科学的学位课程中开始出现。也 就是说，那之后计算机相关专业的学生开始接受《数据结构》的“折 磨”——其实应该是享受才对。 之后，70年代初，出现了大型程序，软件也开始相对独立，结构程序 设计成为程序设计方法学的主要内容，人们越来越重视“数据结 构”，认为程序设计的实质是对确定的问题选择一种好的结构，加上 设计一种好的算法。可见，数据结构在程序设计当中占据了重要的地 位。程序设计=数据结构+算法 1.4　基本概念和术语

说到数据结构是什么，我们得先来谈谈什么叫数据。 正所谓“巧妇难为无米之炊”，再强大的计算机，也是要有“米”下 锅才可以干活的，否则就是一堆破铜烂铁。这个“米”就是数据。 1.4.1　数据 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被 计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整 型、实型等数值类型，还包括字符及声音、图像、视频等非数值类 型。 比如我们现在常用的搜索引擎，一般会有网页、MP3、图片、视频等分 类。MP3就是声音数据，图片当然是图像数据，视频就不用说了，而网 页其实指的就是全部数据的集合，包括最重要的数字和字符等文字数 据。 也就是说，我们这里说的数据，其实就是符号，而且这些符号必须具 备两个前提： 可以输入到计算机中。 能被计算机程序处理。 对于整型、实型等数值类型，可以进行数值计算。 对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频 等其实是可以通过编码的手段变成字符数据来处理的。 1.4.2　数据元素 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常 作为整体处理。也被称为记录。 比如，在人类中，什么是数据元素呀？当然是人了。 畜类呢？哈，牛、马、羊、鸡、猪、狗等动物当然就是禽类的数据元 素。

1.4.3　数据项 数据项：一个数据元素可以由若干个数据项组成。 比如人这样的数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据 项，也可以有姓名、年龄、性别、出生地址、联系电话等数据项，具 体有哪些数据项，要视你做的系统来决定。 数据项是数据不可分割的最小单位。在数据结构这门课程中，我们把 数据项定义为最小单位，是有助于我们更好地解决问题。所以，记住 了，数据项是数据的最小单位。但真正讨论问题时，数据元素才是数 据结构中建立数据模型的着眼点。就像我们讨论一部电影时，是讨论 这部电影角色这样的“数据元素”，而不是针对这个角色的姓名或者 年龄这样的“数据项”去研究分析。 1.4.4　数据对象 数据对象：是性质相同的数据元素的集合，是数据的子集。 什么叫性质相同呢，是指数据元素具有相同数量和类型的数据项，比 如，还是刚才的例子，人都有姓名、生日、性别等相同的数据项。 既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具 有相同性质，在不产生混淆的情况下，我们都将数据对象简称为数 据。 好了，有了这些概念的铺垫，我们的主角登场了。 说了数据的定义，那么数据结构中的结构又是什么呢？ 1.4.5　数据结构 结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子 之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列 的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特 定的关系，我们将这些关系称为结构。那数据结构是什么？数据结 构：是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系 的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据 的组织形式。 为编写出一个“好”的程序，必须分析待处理对象的特性及各处理对 象之间存在的关系。这也就是研究数据结构的意义所在。 定义中提到了一种或多种特定关系，具体是什么样的关系，这正是我 们下面要讨论的问题。 1.5　逻辑结构与物理结构 按照视点的不同，我们把数据结构分为逻辑结构和物理结构。 1.5.1　逻辑结构 逻辑结构：是指数据对象中数据元素之间的相互关系。其实这也是我 们今后最需要关注的问题。逻辑结构分为以下四种： 1．集合结构 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间 没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同 属于一个集合”。数据结构中的集合关系就类似于数学中的集合（如 图1-5-1所示）。

图1-5-1 2．线性结构

线性结构：线性结构中的数据元素之间是一对一的关系（如图1-5-2所 示）。 图1-5-2 3．树形结构 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系 （如图1-5-3所示）。