Qωω，程杰著

    唱画F一-四

    清华大学出版社内容简介

    本书以一个计算机教师教学为场景，讲解放据结构和相关算法的知识.iEf富以一种趣l 床方式来叙述，大量引用了各种各样的佳话知识来类比， 并充分运用图形语言宋体现抽象内容，对敛据结构所涉及到的一

    些经典算法做到逐行分析、多算法比较。与市场上的同炎数据结构图书相比，本书内容趣味易读，算法讲

    解细致深圳，是一本非常适合自学的读物.

    本书主妥内容包含: 数据结构介绍、算法推导大 0 阶的方法:顺序结构与链式结构差异、校与 队列

    的应用:串的朴素模式匹配、陆1P 模式匹配算法; 二叉树前中后序遍历、赫夭曼树及应用:阁的深度、广度池历:最小生成树两种算法、短路径两种算法: f 石扑排序与关键路径算法:折半查找、插值查找、斐放那~资找等静态奈找: 稠密索引、分快索引、倒排索引4事索引技术: 二叉排序树、平衡二义树等动态

    查找， B 树、 B+树技术， 1 技列表技术:冒炮、 ij?择、报i入等简单排序: 希尔、雄、归在1: 、快地等改进排序…

    本书适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学生、想转行做开发的非专业

    人员、欲考计挥机研究生的应届或在职人员，以及工作后需妥补学或温习数据缔构和算法的程序员等。

    本书封面贿有清华大学出版社防伪标签， 无标签者不得销售。

    版权所有 .侵权必究. 侵权举报电话: 010-62782989 13701121933

    图书在版编自 (CIP)数据

    大iìi数据结构稳杰~:. 一北京: 消华大学出版社， 20 川 .6

    ISBN 978-7-302-25565-9

    1 .①大… n. ①程… 阻，①数据结构 N ①TP3 1 J.l 2

    中国版本阁书馆 crp 数据核字 ( 201 1 ) 第084835 号

    责任编辘z 奕大成

    责任校对z 徐俊伟

    责任印制 :杨拖

    出版发行· 清华大学出版社

    http : www.wp. com. cn

    丰土 总 机: 010-62770175

    地 址 : 北京清华大学学研大fJl.. A 座

    邮编: 100084

    由自 购 : 010-62786544

    投稿与读者服务， 010-62795951 . jsjjc@lUp. ts inghua. edll. cn

    质量反馈: 010-62772015 ,zhiliang@tup. tsinghua. edu. cn

    印 刷者z 北京愈丰华彩印有限公司

    装订者:北京国马印刷厂

    经 销: 全国新华书店

    开 本: 188 X 260 印张， 29 播页: 1 字擞: 555 千字

    版次: 2011 年 6 月第 1 版 印 次 : 2011 年 8 月 2在2 次印刷

    印徽: 5001~10000

    定价 59.00 元

    产品编号: 042342-02 目。吕

    本书起因

    大家好!我是 《大话设计模式>> ( 2008 年初出版)的作者，三年来，承蒙广大读

    者的厚爱， <<大话设计模式》 取得了较大的成功。 仅在当当网，截止本文写作时，就已

    经有 1073 次评论， 705 次 5 星评价，位居五星图书榜计算机网络类的累计总榜第二

    名。 此书已经成为国内原创计算机关图书最畅销的书籍之一。

    对于这样一个自己喜欢做、可以做得好，而且已经得到了市场广泛认可，为很多

    朋友提供帮助的事情，我没有理由不去继续做下去。 这就是我准备再写书的原因。

    我曾做过调查，数据结掏的学习者大多都有这样的感慨:数据结构很重要， 一定

    要学好，但数据结构比较抽象， 有些算法理解起来很困难，学得很累。可我更希望传

    达这样的信息:数据结构非常有趣，很多算法是智慧的结晶，学习它是去感受计算机

    编程技术的魅力，在理解掌握宫的同时，整个过程都是一种愉悦的精神感受，而非枯

    蝶乏味的一门课程。 因此我决定写作一本关于数据结构有趣的书。

    东过现实总比理想来得更现实气要想把书写好，谈何容易，我需要突破很多困

    难……嘻! . 不管如何，现在您看到了本书，那就说明我已经克服了困难战胜了自己。

    希望您可以喜欢上这本书。

    本书定位

    本书的定位就是一本适合读者自学数据结构的书籍，它有区别于教材，希望给大

    家另一种阅读体验。

    通常讲解数据结构的图书都是以教材的方式呈现。在写作前，我购买或在图书馆

    借阅了十几本非常好的数据结构相关教材用来为写作本书做准备。但经过认真阅读

    后， 我发现，它们大多不是一本好的自学n 读物。

    我没有轻视这些好书的意思， 不过教材和自 学读物，所面向的读者是完全不同

    的。

    好的教材应该是提纲擎领、重点突出， 一定要留出思考的空间，否则就没必要再

    听老师上课了。很多内容的讲解是由老师在课堂完成，教材中有练习、课后习题、思、l宋懂噩噩噩噩E

    考题等p 这些大多可以通过老师来解答。比如我们中学时的语文、数学课本，很畴的

    一本书通常要用一学期、 甚至一年的时间来学习，这就是因为色们是教材而不是自学

    读物。如果是小说，可能一两天就读完了。

    好的自学读物的目标是让初学者独自全盘掌握知识，需要强调独自一

    词，这就说明读者在阅读时， 是完全依靠自己的力量来向未知发出挑战。因此书中内

    容，要么不写，写了就应该写透。如果读者在阅读时总是疑惑重茧，那么这本书就有

    很大的问题了。

    我也就是在基于这样的认识， 决心将 《大话数据结构》 真正写成一本关于数据结

    掏和算法的自学读物来展开写作的。

    本书特色

    1. 趣味引导

    大部分的编程类图书，在内容上基本都是直奔主题。但是尼采曾说过人们无法

    理f 阳也没有经历过的事情。'换句话说，我们只接受过去早已理解的事物相关的信息。

    这是一种比较学习过程，在这个过程中，大脑寻找每条信息之间的联系。所以教育专

    家普遍认为，吸引学生的注意力，比较好的办法是用他们比较熟知的知识开始。

    因此在本书中，我会用一个故事、一个趣味题目 、 一部电影的介绍等形式来作为

    每一章甚至很多小节的开头，选择的内 容也多多少少与要讲的主题内容相关。这并不

    是多余，而是有意为之。事实上，这样的形式在我的前一本书中已经得到了普遍认

    可。

    2 . 图文并茂

    西方有句谚语， A picture is worth a thousand wor?. (一图值千言) 。 用上千个

    字描述不明白的东西，很可能一张图就能解释清楚。

    我非常认可这个观点，所以本书虽没有达到每一页都有圈，但基本做到了绝大部

    分讲解都有相关图示，关键算法更是通过多图逐步分解剖析。尽管这带来了写作土的

    难度，但却可以达到较好的效果。 毕竟，读者通过本书开始学习数据结构时，要从一

    无所知或略知一二到完全理解，甚至掌握应用，是需要一个比较艰苦的过程，用大量

    的图示可以减少这个过程的长度。

    3 . 代码详解

    我在写作中尽量摒弃了传统数据结构教材的重理论思想而轻代码讲解n 的作

    2 前言

    法。在准备数据结构写作时我发现，很多教材对数据结构理论和算法设计思想讲得比

    较好，可一到实际代码时，有的把代码贴出来加少量注释，有的直接用伪代码形式。

    这对于上课的学生还好，毕竟有老师在课堂中去详解代码编写原理，可是对于初学数

    据结构和~法的自学者而言，如果书中不去解释代码某些细节为什么那样编写的原

    因，甚至代码棍本不可能在某个编译器中运行通过，其挫折感是很强烈的。比如即使

    理解了图结构中的最短路径求解脱础，也可能无法写出最短路径的算法。

    我把代码在运行过程中变量的变化融入到整个算法设计思想的讲解中，配合相应

    的示意图，会帮助大家更加容易理解算法的实质.这种讲解模式在本书的第 6、 1

    8 、 9 章的很多复杂算法中有具体体现，越是复杂的代码越是讲解细致。这算是本书的

    一个特色，希望对读者有帮助。

    4. 形式靳颖

    我把本书的内容虚构成了一个老师上课的场景，所有内容都通过这位老师表达出

    来，书中的文字非常口语化，这样做的目的是为了更加直观地让读者感觉，自己是在

    学习，是在上课。有人可能会说，现在的课堂大都是让人昏昏欲睡，把读者带入上课

    场最，不是更加让读者犯困吗?我觉得如果你的学习经历中听过一些优秀老师的课，你就不会下这样的结论。好的老师讲课，是可以做到引人入胜的。

    有人可能会问，我为什么东用 《大话设计棋式》中的对话形式，而采用讲课形式

    呢?这是对敏据结构这门学问的特点考虑的. 设计模式主要都是思想体现，通常会仁

    者见仁、智者见智，用对话展开比较容易i 而数据结构中更多的是定义、术语、经典

    算法等，这些公认的知识，可讨论的地方并不多，更多的是需要把官讲清楚。让两个

    人在一起讨论某个设计模式的优缺点，会非常合适，而讨论数据结构定义的好坏，就

    没有太大意义了，不如让一个老师告诉学生数据结掏的定义好在哪里更符合实际. 因

    此用传统的讲课形式会好一些。

    另外，本书没有习题，有思考的题目也一定会给出某种答案。但本书每个复杂知

    识点的末尾，部会提供另一本书的进一步阅读建议。这也是基于宫是一本自学读铀的

    原则。读者阅读本书可能是任何时间任何地方，如果书中存在没有解答的习题，碰到

    了困难是设法及时找到老师来帮助的，因此本书尽量避免让读者有这样的困惑存在。

    如果需要练习的同学，我觉得还是应该考虑再去实本习题集来学习。学习数据结构和

    n沽，做姐和上机写代码非常有必要，从这个角度也说明，阅读完本书其实也民是完

    成人门而已。

    本书既然是以老师上课的形式来进行，那就免不了要融入一名教师除了授业解惑

    3 l束画E噩噩噩

    以外，还要传达一些个人价值观的体现。书中很多细微处，如对某位科学家的尊敬、对某个算法的推崇、对勤奋励志故事的讲述等都在表达着一个老师向学生传递真、善、美的意愿。我始终认为，读者拿到的虽然只是一本没有表情、不会说话的书，但

    其实也是在隔空与另一个朋友交流。人与人的交流不可能只是就事论事，一定会有情

    感的沟通，这种情感如果能产生共鸣、 达成互信，就会让事情(比如学习数据结构与

    算法这件事)本身更睿易理解和接受。

    本书内容

    本书主要是按照教育部关于计算机专业数据结构课程大纲的要求略微增减来组织

    内容的。

    主要包括:数据结胸介绍，算法推导大 0 阶的方?去，线性表结构的介绍，顺序结

    构与链式结构差异，饿与队列的应用，串的朴素模式匹配、 KMP 模式匹配算法，树结

    构的介绍， 二叉树前中后序遍历，线索二叉树，赫夫曼树及应用，图结掏的介绍，图

    的深度、广度遍历，最小生成树两种算法，最短路径两种算法，拓扑排序与关键路径

    算法，查找应用的相关介绍，折半查找、插值查找、斐被那契查找等静态查拢，稠密

    索引、分块索引、倒排索引等索引技术， 二叉排序树、平衡二叉树等动态查找， 8

    树、 B+树技术、 散列表技术，排序应用的相关介绍，冒泡、选择、插入等简单排序，希尔、堆、归井、快速等改进排序，各位排序算法的对比等。

    本书读者

    数据结构是计算机软件相关专业的基础课程，几乎可以说，要想从事编程工作，无论你是否是科班出身，者阳之可以绕过这部分知识。因此，适合阅读本书的读者非常

    广泛 ，包括在读的本专科、中专职高技校等计算机专业学生、想转行做开发的非专业

    人员、欲考计算机研究生的应届或在职人员，以及工作后需要补学或温习数据结构和

    算法的程序员等各类读者。

    本书对读者的技术背景要求比较低，只要是学过一门高级编程语言，例如 C 、C++ 、 J ava 、 C、 vs. 等就可以开始阅读本书。 不过由于当中涉及到比较复杂的算法知

    识，需要读者有一定的数学修养和逻辑思维能力，否则可能书籍的后半部分阅读起来

    会比较吃力.

    4 前言

    本书研读方法

    事实上， 任何有难度的知识和技巧， 都不是那么容劫被掌握的。我尽管已经朝打

    通俗易懂的方向努力 ， 时有些数据结构， 特别是经典拌法，是几代科学家的辑'也结

    晶 ，因此要掌握它们还是仰要读者的全力投入。

    美国畅销书《如何阅读一本书》 中提到阅读可以是一件主动的事，阅读越主

    动，效果越好。拿同样的书给背景相近的两个人阅读，一个人却比另一个人从书中得

    到了更多， 这是因为，首先在于这人的主动，其次，在于他在阅读中的每一种活动都

    参与了更多的技巧。这两件事是息息相关的。阅读是一个复杂的活动，就跟写作一

    样， 包含了大最不同的活动.耍达成良好的阅读，这些活动都是不可或缺的。 一个人

    越能良好运作这些话动， 阅读的效果也就越好。

    我当然希望读者在阅读本书后收获巨大，但这显然是一厢情愿。要想在走得更多，您可能也需要付出类似我写作一样的力气来阅读，例如摘抄文字、眉批心得、稿纸演

    算、 代码输入电脑，以及您自己在编程工作中的运用等。这些相应活动的执行，将会

    使您得到巨大的收获。

    作为作者，建议本书的研读方法为:

    复习 C 语言的基础知识。如果价:掌握的是别的语言也不要紧，造当了解一些

    C 语言和你华握的编程语言的语法差异还是有必要的。甚至将本书代码改造

    成另一种语言本身就是一种非常好的学习方法。

    阅读第一遍时 ， 建议从头至尾进行。如果你对前面的知识有足够了解，当然

    可以跳过直接阅读后丽的章节。不过若耍学习一门完整的知识并形成体系。

    通读本书，还是最好的学习方法。

    阅读时，摘抄是非常好的习惯。 a 最淡的墨水也胜于最强的记忆! 有不少读

    者会认为摘抄了将来也不会再去看，有什么必要，但其实在写字的过程就是

    大脑学习的过程，写字在减缓你阅读的速度，从而让你更好地消化阅读的内

    容。 相信大家都能理解， 66 圆圆吞枣和 眼慢品睐'1 的差异， 学习同样如

    此。

    阅读每一章时，特别是在阅读算法的推导过程时，一定要在电脑中运行代码

    (本书源码的下载地址可以到 h即:cl 723.cnblogs.com 中的 《大话数据结构相

    关主题》 中找到) ， 了解代码的运行过程。 本书的很多算法都做到了逐行讲

    解，但单纯阅读可能真的很难达到理解的程度(这是纸质书无法克服的峡

    陷) ，需要你通过开发工具调试， 并设置断点和逐行执行，并参照书中的讲

    解，观察变量的变化情况来理解算法的编写原理。

    5 Ii 谊E噩噩噩

    阅读完每一章时，一定要在理解基础上记忆一些关键东西。最佳的效果就是

    你可以不看书也做到一点不错地默写出相关算法。

    阅读完每一章时，一定要适当练习。本书没有提供练习题，但市场上相关的

    数据结构习题集比比皆是，可以选择尝试。另外互联网上也可以获得足够的

    习题来给你练习。练习的目的是为了检测自己是否真的完全理解了书中的内

    容。事实上很多时候，阅读中的人们只是自我感觉理解，而并非真正的明

    白。

    学习不可能一蹦而'就，数据结构和算法如果通过一本书就可以掌握，那本身

    就是笑话。本书附录提供了本书写作时的参考书目，基本都是最优秀的数据'

    结构或相关的中文书籍各有侧重，建议大家可以适当地阅读。

    在之后的编程学习和工作中，尽量把已经学到的数据结构和;算法知识运用到

    现实开发中。遗忘时翻阅本书回顾相关内容， 最终达到精通数据结构和相关

    算法的境界。

    编程语言说明

    本书是用 C 语言编写，基于 C90 ( ISO C) 的标准。读者可以选择任何一款基于

    C90 标准的 C 语言开发工具或更高版本的开发工具来学习本书中的代码。

    本人一直习惯于用 Visua) Studio 2008 作为开发工具，因此在写作此书时，也是用

    此工具的 Visual C++采编译调试代码， 一切都相安无事，但写作完成后，考虑到不同

    读者应用开发工具的习惯不同，最终在编辑的建议下，决定提供一份可在 C90 标准的

    C 语言开发环境中编译通过的代码，结果发现错误百出。

    例如 C90 标准的注释要求是 注释文字 j 而不允许是 jj注释文字 要求

    变监声明必须要在函数的最前面，只能是 int i; for(i=O;i
    U for (int i=O;i
    CreateBiTree(BiTree T) 的 地址变量，但在 C 语言中，只能传递如void

    CreateBiTree(8iTree η 的指针变盘。因此当你看到书中的有些代码到处都是

    时，就用不着奇怪了。

    出于为了让代码可以在低端编译环境通过的考虑，牺牲一些代码的简捷性和优雅

    性也是无可奈何和必要的。最终我将书中全部代码都改成 C90 标准的代码。

    C 语言初学者可能会因为刚接触编程语言， 特别是对指针的理解不深， 而担心阅

    读困难。我个人感觉，单纯学习指针是很难理解它的真正用途和好处，而通过学习数

    6 前言

    据结构，特别是你链式存俯结构在各种结构算法中的运用，反而可以让读者进一步的

    理解捐针的优越之处。 从这个角度说，数据结构的学习可以反过来加强读者对 C 语

    言，特别是指针概念的理解。

    编程语言差异

    c m盲是一门古老的高级语言，它的应用范围非常广泛，因此我选择芭作为本 I S

    的算法展示情言。如果读者之前学过它，那么阅读本书就不存在语言附碍。恤得 C++

    语育的读者，同样也不会有任何语言上的问题。

    掌握 J ava、 C、 VB 等面向对象语言的读者，当面对书中大量的 C 语言式的结构

    ( struct) 声明和针对结构的参数传递的代码时，可以理解为是类的定义和由类生成对

    象的传递。尽管的确存在差异，但并不影响整体对数据结构知识和t?:法原理的理解。

    我个人感觉，哪怕是对 C 语言不熟悉，也不妨利用学习数据'结构的机会，学习一

    下 C 语言的编程方法，这对于将来应用其他高级语言也是有很大帮助的。

    不是一个人在战斗

    首先要感谢我的妻子李秀好对我写作本书期阔的全力支持，我辞职写作，没有她

    精神上的理解鼓励和生活上的恶心照顾，是不可能走出这一步并顺利完成书稿的。我

    们的儿子程展涵如今已经三周岁，我是在他每日的欢声笑语和哭哭啼啼中进行每一章

    节的构思相写作，希望他可以tiS 壮成长。我的父母已经年迈，他们为我的全职创作也

    甚为担心和忧虑，这里也要说一声抱歉。

    写作过徨中，本人购买租借阅了与数据结构相关的大量书籍，详细书目见附录。

    没有前萃的贡献，就投有本书的出版，也希望本拮能成为这些书籍的lj1y期读物。在此

    向这些图书作者表示衷心的感谢.

    仅有作者是不可能完成困阳的出版的，本人要非常感谢清华大学出版社的朋友

    们，他们是本书的最初读者，也是协助本人将此书由毛糙变精良的品有力帮手。本书

    的封面设计程瑜、插图设计用翔，都是在反反复泣的修改中完成创作的。写作中还得

    到了周捕、卢鸦翔、张伸、胡文佳、 Milo 、陈钢、刘超、刘唯一、杨绣国、戚兢婷、富版、杨诗盈、高宇翔、林健的友情帮助，他们都在本人的创作中提出了宝贵建议。

    在此向所有帮助与支持我的朋友道一声:谢谢!

    程杰

    7 目录

    第 1 章 数据结构绪论... .... ...... .. ......

    1.1 开场白....... ....

    如果你交给某人一个程序，你将折磨他，一签天;如果你教采人如何编写程序，你将折

    磨他-~子.

    1.2 你数据结构怎么学的? ...

    他完成开发并测试通过后，得意地提交11、码.项目经理看完伏，码后拍着采子对他说:

    你数据结构是怎么擎的?

    1.3 数据结构起摞…

    1.4 基本概念和术语……… …

    正所谓巧妇难为元米之炊，再强大的计算机，也妥有米下销才可以千活，否则

    就是一堆破铜应钦.这个米就是数据.

    1.4.1 数据…………….......…..…….....5

    1.4.2 数据元素.......………….......…5

    1.4.3 数据项……..........……... .....… ..6

    1 .4.4数据对象....-.....……...... ...1.. …....….... .. ..... ... . ....6

    1.4.5 数据结构…………·…………·…........….... .... .. .6

    1.5 逻辑结构与物理结构.........……………·……......….......................…

    1.5J 逻辑结构………·……. ..........… 7 1.5.2 物理结构………......………..….，…… J…·…....9

    1.6 抽象数据类型…..…… ·

    大家都需要房子位，但显然l没钱考虑大房子是没有意义的. 于是商品房就出现了各种

    各样的户型，ι 有儿百平米的别蟹，也有仅两平米的胶拿公寓…

    1.6.1 数据类型.......…………………….11 1.6.2 抽象数据类型............ ...... ........…..…..…..12

    1.7 总结回顾…….......

    9 l去画圄回国

    1.8 结尾语.......………....... …... . ......... ........ ..叫川 .... . …………………………....叫叫...... .....………........ . .... ......… '15

    最终的结呆一定是，你对着别人很牛的说 数据结构一一就那么回事

    第 2 章算法…… .. ... ..

    10

    不同算法的操作数量对比

    制 1 50; 1 1 J 二: 辰 I 2 3 4 5 6 7 8 9 10 甲-1

    问题输入规模n

    2. 1 开场臼.-.. .. ..... …...... . .……... .... ....… … ……- . .... . …... .... . ... .. . .……..小 ……...... . ……... . ....... . ...... .……..... . 1 8

    2.2 数据结构与算法关系……... ….........….. ... . ..…... . ....……..………........…·……... ... ....……………·比

    计算机界的前笨们，是一帮很牛很牛的人，他们使得很多看似没法解决或者4如住解决

    的问题， 交待如此美妙和神奇.

    2.3 两种算法的比较…. ........... . ... .. ....……. . .. . …................……..…..…... . .. …..…..... ， ....… . ....... . ........ … 19

    高斯在上小学的一天，老师妥求每个学生都计算 1+2+ …+100 的结果，谁先算1:来谁;先

    回家...

    2.4 算法定义川，.......….. .. ...……·

    现实世界中的算法千交万化，没有通用算法可以解决所有问题.甚至一个小问题， 某

    个解决此类问题很优秀的算法却未必就适合它.

    2.5 算法的特性…...... ...………·

    2.5.1 输入输出 ................................2 1

    2.5.2 有穷性 . ............... . ....... . .… .. ...2 1

    2.5.3 确定性....…………..……........…....................2 1

    2.5 .4 可行性………..……...... . .…..... .. ..…..…..… ..... . .2. 1

    2.6 算法设计的要求.......……............. . .. .. .... …..…………........………..…..…..………·…... . ........ .…·……22

    求 100 个人的高考成绩平均分与求全省所有考生的成绩平均分在占用 时间和内存在储

    丰有非常大的差异， 我们自然追求高效牟和低存储的算法来解决问是.

    2.6.1 正确性…………….... . 叶 .... .....22

    2.6.2 可读性.......….... ...……..…...... ..23

    2.6.3 健壮性……......…..……......……………...............23

    2.6.4 时间效率高利存储盘低....…...'....... .-.旷....... .. ..23自豪

    2.7 算法效率的度量方法…….........…................-................ ...........…..….... ...............….......…..............24

    随着 n 值越来越大，它们在时间效牟上的差异也就越来越大.好比有些人每天都在学

    习，而另一些人，打打游戏.瞻睡大觉，毕3k.后前者名企争着袅，后者求职处处元n .

    2.7.1 事后统计方法.......……..........24 2.7.2 事前分析估算方法.......………....... ……........25

    2.8 函数的渐近增长.......….，....….............................叫......……山…………………H刊....川川............川...川………..……..….川 .27

    2.9 ，草法时间复杂度……........…....……................…·…..……..……..…...............…..…..…..………..…......29

    理解大 o ~在导不算'鼻，难的其实是对数列的一些相关运算，这考察的关多的是数学知

    识和能力.

    2.9.1 算法时间复杂皮定义.....……29

    2.9.2 推导大0 阶方法....................3 0

    2.9.3 常数阶...........…….......….........30

    2.9.4 线性阶......………·….... .....………..…..…......31

    2.9.5 对数阶..............…....……... .……....……............32

    2.9.6 平方阶.................... ........…. .... ..……... ............32

    2.10 常见的时间复杂度.......………·…………….......................... ….........…....… . .............…........… 35

    有些时候，告诉你采些东西不可以去尝试，也是一种知识的传递.总不能非委会被毒

    纶咬一口才知道Jrè不可以去招惹吧.

    2.11 最坏情况与平均情况………·…

    2.12 算法空间复杂度…..…………………........... .._..………….......…...... . …....….......…..............…..…........36

    事先建立一个有 2050 大的欲组，然后把所有年份按τ标数字对应，如果是闷年，比.ft

    纽项的4直就是1，如果不是就是 O. 这样，所谓的判断采一年是否是问年就变成了查找

    这个数纽约采一项的位是多少的闷地

    2.13 总结回顾…..……....................们们......................... .......………… …….………..………..…..…..………..………..………..…..….川……….，…..…..………..…..…..………..….叫………..…..…..………..…..……….川…..…..………..…..… ..3 引 刀 7

    2.14 结尾语叫………..…..…..….......….........……………….......…........…................…..........……..……… '38

    愚公移山固然可敬，但发明炸药和粮土机，可能更加实在和u明.

    第 3 章线性表……….......…

    . ‘

    结点q-)next或

    p-)next - )neXl

    f一λ---

    儿

    …一二一一二J……_... _...一一一一…--【'【…【'

    11 3.1 开场白….............. ...…..…..…........…·…........………... . ... .. . ....... . …….........….... . ... .….. .... . ..………….42

    门外家长都挤在大门口与门里的小孩子的井然有序.形成了鲜明对比. 咬，有时大人

    的所作所为. 其实还不知孩子.

    3.2 线性表的定义- …..……H.. . ... …..….......….... . ..……· ……..…. . .. ……..…..…..…. .…….............. ...... ...….42

    3.3 线性袤的抽象数据类型………....... …..……. ........…............. …·…….......…. . ...... . ... . …..…. .. ..... 45

    有时我们想知道某个小朋友{比如麦克)是否是统级的问学，老师会告诉我说，没有，麦先是在春回花花幼儿园里.这种查找某个元，愈是否h存在的操作很常用，3 .4 线性袤的顺序存储结构….. …..…….. ..……….........………..…....………........…. . .. . ....... ........ . ....… . 47

    他每次一吃完早饭就冲着去了图书馆，挑一个好地儿，把他书包里的书，一本一本的

    接应位放好， 长长一排，九个座硬是被他占了 .

    3.4.1 顺序存储定义………·…..….......47

    3.4.2 顺序存储方式….... ……............ 47

    3.4.3 数据长度与线性表长度区别 . . .. ... ……......… 48

    3.4.4 地址计算方法....... . .…..…..…..…..…..…..... ....49

    3.5 顺序存储结构的插入与删除…….... . ............ .. ..…..…..... . .. . ..-... . .. ... . ... ...... . ….. .. ........... .. .. .. . …….50

    春运时会买火车票， 大京都排队排着好好的，这时来T 一个美女. ..可否让我排在你前

    面? 这可不得了， 后面的人像虫在虫一样，全部都得退后一步.

    3.5.1 获得元素操作…... ............. . ..... 50

    3.5.2 插入操作......………........ .... ...51

    3.6 线性表的链式存储结构…

    3.5.3 删除操作......... .…….... . .... .....…........…..... . .…..52

    3.5.4 线性表l顺序，存储结构的优缺点………… 54

    反正也是要让相邻元余间留有足够余地那干脆所有元，素都不要考虑相邻位置了 ，哪

    有空位就到哪里.而只是让每个元，余知道它下一个元素的位亘在哪里.

    12

    3.6.1 顺序存储结构不足的解决

    办法 ……...... . .... . ......… .......... . 55

    3.6.2 线性表链式存储结构定义…..56

    3.6.3 头指针与头绪点的异同………· …………........58

    3.6.4 线性表链式存储结构代码描述................... 58

    3.7 单链衰的读取…........…………........…..…. ......……….-. ......………..…………γ……………… '60

    3.8 单链表的插入与删除…....…….......…..….... .............………. .... .. .. …....-. .....….........…..…..….. .....6 1

    本来是爸爸左牵着妈妈的手、右牵着宝宝的手在马路边散步.突然迎面走来一美女，爸爸失神般地，望着，此情景被妈妈i定个正着，于是拉开父子俑，拉起宝宝的左手就快

    步4月前走去.

    3.8.1 单链袤的插入………………..61 3.8.2 单链袤的删除........ ......... .... ..…..............… ....64

    3.9 单链衰的整表创建…..….......… . ....………... ......………·…..………·……................…......... . .... ， ..... . ...….66自豪

    3.10 单链袤的整表删除-…..………·…..…..…... ... .. .……..…............... . ... ..... .. .. .. ........ ... . ... . ......…...… ..69

    3.11 单链表结构与顺序存储结构优缺点….. . ..... . .......…..…..… . . ….......….. .....……..... ... .… ……….70

    3.12 静态链表...... ....…... ......……....... . ... . .........- . ..... . ….. .. .....……….......... ... .. .…·………............ . .. .………71

    对于一些错言，如 Basic、 Fo.r tran 等平糊的编程高级语言， 由于没有指针，这链求结

    构，按照前面我们的讲法，它就没法实现了.怎么办呢?

    3.12.1 静态链袤的插入操作.... . ......73

    3.12.2 静态链袤的删除操作.... . …. . .75

    3.12.3 静态链表优缺点…........……………. .... . .…… 77

    3.13 循环链表. ... .. .......... . ... . ...…… ..............….... ..... .. ... . ......... . ..-.…...... . ..………... ……·…………………78

    这个轮回的思想很有意思.它强调了不管你今生是穷是富，如果持续行善和、穗，下辈

    子就会好过， 反之就知t到报应.

    3.14 双向链表…..…... .. . .. .. ..... . .. ...…. . ..... ..... ... . .…… …..……….. . ... …….......……… …. ......…… . . ...... .81

    就像每个人的人生一样，欲收获就得付代价.双向链'-既然是比单链求多了如可以反

    向选历查找等的数据结构， 那么也就需要付出一些小的代价.

    3.1 5 总结回顾 . .............….. .. .. .. ……..... ... . ….. . .....….. . .…….. .. ， ....... . ...……............. .......... . ... .… …..…… 84

    3.16 结尾语…..…………........... .. ...……..…...... .. .. ... .. ...... . .. ..... . …........ . .......………..… ..……...............85

    如果你觉得丰学读书是受.w..假设你可以活到 80 岁，其实你最多也就吃了 20 年苦.

    用人生四分之一的时间来换取其余时间的幸福生活.这点苦不算哈.

    第 4 章 钱与队到…-

    3 1 月…一一…·一- . ~-7............-……一一一一一一…·……·…一…一一一一一一…......

    ~l!. 2 月

    -一一一一一一……-… H 坛 马

    一一-…… ιH 汇一… H 兴、辽亏《 ω …_..........-…一-一- 让乞 Trr 士一 7

    一一……..… J乙一、一一…..一一γ了一一一一….... . .;;....- I---- ~~-_......._- …

    24 8ι 怒， 丑 2 . 5月

    一 γ书 一石γ- 3-JYJ 马户与一 百 - I JL J:- AE- jy?

    13 l束画圈圈圈圈

    4.1 开场臼........ . ….. . ............... ……..... ... . .... .. .…………·…. .…. . ............ . ...….......….. .............. . ..............88

    想想看.在你准备用枪的时候，突然这手枪明明有子弹却打不出来，这不是安命吗.

    4 .2 校的定义…..…..…..…....... …. ......……. .. .... .…..……..... .. . .. . .....……....... .. ..... . .... .. .....…..…. ... . ...….......89

    类似的很多软件，比如 Word、 Pllotoshop 等，都有撤消 (uneo) 的操作，也是用是这

    种思也方式来实现的.

    4.2.1 梢的定义…..…………….. .. 89 4.2.2 进校出钱变化形式……......…... ......…..…….....90

    4.3 拢的抽象数据类型…......….......………….......…·…..…….........……........….......…..............91

    4.4 枝的!顿序存储结构及实现…·…….. . ~.. .……·…………..............…………..……·…....... ... ...... 。但

    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 两面镜子相互面对面放着， 1，中4主中间一站，吃黑，两面镜子里都有你的千百个化身.

    4.8.1 斐波那契数列实现…………. . 101 4.8.2 递归定义…..………·………· …...... …...... . ..… ..103

    4.9 战的应用一一四则运算表达式求值...………… .. ………… .. …… .. …….川…...………….川………… .. ……….川…….川川.川……… .μ ………… .. ………… .. ……….川…… .. ….川………… .. ………….………….川…….川……… .. ………… .. ……… .. …… .. …... 川.................. . ...…. . .. .............…104

    4.9.1 后缀 〈逆波兰〉表示法定义104 4.9.3 中缀表达式转后缀表达式……......…..…… 108

    4.9.2 后缀表达式计算结果........... 106

    4.1 0 队列的定义…..…..….. .

    14 也脑有时会处于疑似死机的状态.就当你久去耐心，打算 ROot 时.突然宫像滔画11

    一样，把你刚才点击的所有操作全部都接顺序执行了一边.

    自豪

    4 .l ) 队列的抽象数据类型……..….........…·………·….......….........…................…............................. 1 12

    4.12 循环队列…………..............………....... .…. . .. . ..…..……….. . ....................….................... . ... . …·……川

    你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做?立

    马下车，并对自己说.后面没应了.我等下一辆?没这么笨的人，前面有座位.当然

    也是可以坐的.

    4.12.1 队列顺序存储的不足……112 4.12.2 循环队列定义........…·……………...…·….....1 1 4

    4. 13 队列的链式存储结构及实现-….-.... . …. . .... .…..…..…..….......….......................................…….. 117

    4.13.1 队列的链式存储结构-一 4.13.2 队列的链式存储结构一一出队操作............ 1 19

    入队操作 ..... . ....，......…… .... .118

    4. 14 总结回顾…….........…............…..…..………·….......................................…..................................… '120

    4. 15 结尾语…….....................…..........…....................................................................………...............… 121

    人生，需要有队列精神的体现.南极到北极，不过是''纬 90~到北纬 90 度的队列.

    如果你中途犹豫.临时转向.也许你就只能和企鹅相伴永远.可事实上， 无论哪个方

    向，只晏你坚持到底，你都可以到这伶点.

    第 5 章串…

    s I a I b I …I 5 I a I b I …|

    I ~ ~ _v'! ~

    Tla l b _l…I T I a I b I …|

    良、唾p

    T[ I]=e, T[2)吨.5[2] 吨

    显然T[IJT【刻. T[2J 喝[2J I?I此T(1 】S(2J 副此当T位于第二位蠢的判

    断.根本不布要是行了

    5.1 J干杨白……...... ...... ... .......……............ . ........… .... .. .. ........ ......................… . . .................……….... . ...… .. 1 24

    枪自民莹透山隔水，往来曾几儿心知?金空怕的一杯酒，笔下难成和韵诗. 途4fll人

    l\ Jl']九讯者元~寄回i.. 孤灯夜守长寥寂，久.t. 乙要兮父忆)1...……可耻于细一该发

    现，这首诗竟然可以倒过来读.

    5.2 净的定义…..…..…..…....……..............….....-0..…................…..…..….......…..…..................…..……......124

    我所提到的 over 、 end飞 1 ie 其实就是 lover 、 friond飞 betieve 这些

    单词字符亭的子事.

    5.3 净的比较…......…..…………….................…叫…..….........…………·…………..................…................… 1 26

    15 5.4 串的抽象数据类型……….......…………………..............……·…........... . .. ......……........ .. .....….......... 127

    5.5 串的存储结构….... .. .. .. ...... ..……....... ..…….......... ..........… ... ..... _. . ..... .. ........….........…... ... ….......... 129

    感情上发生了问趟， 为了向女友'事择一下， 我准备发一条短信，一头打了 7S 个字.最

    后八个字是我J恨你是不可能的气 点发送.后来得知对方收到的， 只有 70 个字短

    信结尾式 .. 我恨你气

    5.5.1 的顺序存储结构...............]29 5.5.2 净的链式存储结构... ......……·……..…… .......131

    5.6 朴素的模式匹配算法……..... ………..…….......... . .. . ......... . ..……..….. .. ........ ..... . .......…..…..…… 1 3 1

    主亭为 S-00000000000000000000000000000000000000000000000001， 而要匹配的子

    事为严0000000001 ， ......在匹配时， 每次都将将 Tt字符循环到最后一位才发现，哦，原来它们是不匹配的.

    5.7 K阳模式匹配算法\ ……·……....... ...... .... . .................... ... .... ..... ..... . .....…. 川 …… ………………… .. …………….川………… .. …………….川…………… .. …………… .. …………… .. …………… .. ………… .. ……… .. …….川………… .. ……… .. …… .. ….. 135

    很多年前我们的科学家觉得像这种有多个 0 和 1 重复字符的字符事.却需要挨个选厉

    的算法，是非常糟糕的事情.

    5.7.1 KMP 模式匹配算法原理.... . 135

    5.7.2 next 数组值推导…..……........139

    5.7.3 KMP 模式匹配算法实现.....141

    5川 KMP 模式匹配算法改进........ ….............. . 142

    5.7.5 nextval 数组值推导 ....... . ... ..… ..... . …..…....1. 44

    5.8 总结回顾…….... . ...……….......…..….......……......… . .. ...... . .....…… . ... . .……….. . …...............................146

    5.9 结尾语…............. .... ...... ...... .... .. .. .. .. . ... . .. .... ..... .. .... ... ， .…....... . ……. .. ... .......... ..... ..... . ….... ...……….. 146

    《就是.tJL图)) 4斗八百四十字. 纵横各二十九字，纵、横、 斜、 交豆、豆、á.' 谈或i是一字、这一字读均可成诗. 诗有三、四、豆、六、七言不等， 目前有人统计可组成七千九百

    五十八首诗.听清楚哦， 是 7958 首.

    第 6 章树. . ........….......... .... . …·………………·……·……… …………·… …... .… … …'149。 O

    J阳

    -

    4

    、为 度 点 结 此

    A U

    为 度 市中 绩 比

    J

    此血可点J?: J.J 3-

    G J

    16 目景

    6.1 开场白 ……………·……· ………· 叫 ........... . .…........ . ………·…. .....…………..…·….... .. .….......….. .. ..... . t 50

    元，伦多高 多大的树， 那也是从小到大的， 由根到叶， 一点点成长起来的. 俗话说十年

    树木， 百年树人、可一棵大树又何止是十年这样容易.

    6.2 树的定义……·… ...... 叶 川 叶川叫..... ...........…………………………………·…….......… . ......…… .... .. ................ 1 50

    树的定义其实就是我们在讲解税时捉到的逆归的方法.也就是在树的定义之中还用到

    了树的概念，这是比较新的一种定义方法.

    6.2.1 结点分类....…………………. 1 52

    6.2.2 结点问关系........……........ .... 152

    6.3 树的抽象数据类型……·

    6.4 树的存储结构…

    6.4. 1 双亲表示法…. .………… …… 155

    6.4.2 孩子表示法…..…. .………. . .158

    6.2.3 树的其他相关概念….. …..…..…..…..…. . ……153

    6.4.3 孩子凡弟表示法.......………………………. . .. 162

    6.5 二叉树的定义-……….. ......... . .... . ........……..…... .. ..…. .......... …….... ...........…. ..............……. .....…… 163

    苏东被曾说. ..人有悲欢离合，月有阴晴圆缺，此事古'在会飞意思就是完美乏理想，不完美才是人生旷我们通常举的例子也都是:左祸右低、 参差不齐的二叉树.那是否存

    在完美的二叉树呢?

    6.5.1 二叉树特点.......……..……... 165 6.5.2 特殊二叉树.…._…......…...….... .......... . …..… 166

    6.6 二叉树的性质…·……..........…...... . ....... . .…………... ........…....... . ……..….. . .-..……·………·….. ..... . ..169

    6.6.1 二叉树性质 1. ....... . .… . ... . .... .. 1 69

    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

    你人生的道路上， 高考填志愿要面'恪哪个浅帘、哪所大学、具体专业等选择. 由于选

    择方式的不同 ， 边厉的次J乎就完全不同 .

    6.8.1 二叉树遍历原理……·……... 1 74

    6.8.2 二叉树遍历方法.... ..…·…. . .. 175

    6.8.3 前序jlfi历算法. . …….. .. . ..... .. .178

    6.8.4 中序遍历算法... . ........………………….. …….. 181

    6.8.5 后序泌历算法.…………. ... ..... . ………·…， . ...184

    6.8.6 推导l!1i历结果………..... .. .. .………....... ….... 1 84

    17 l束蕾噩噩噩圃

    6.9 二叉树的建立..…..…............. ... . .... .........… ..…... . ..….. . ............... . ..…......... . ..... ...... ..... .. . ... .. ...… .. 1 87

    6.10 线索二叉树…………E …………………………………..………………………………………………………………….188

    我们现在提倚节约型社会， 一切都应该节约为本.对待我们的程序当然也不例外，能

    不浪费的时间或空间， 丁 都应该考虑节省.

    6.10. 1 线索二叉树原理. ...........…. . 188 6.10.2 线索二叉树结构实现………............…….191

    6.1 I 树、 森林与二叉树的转换..........……·

    有个乡镇企业也买了同样的生产线，老板发现这个问是后找了个小工来说:你必须搞

    定，不然炒你就鱼. 小工很快想出了办法:他在生产线旁边放了台风扇猛吹，空皂金

    自然会被吹丈.

    6. L 1.1 树转换为二叉树.....…..... .. .. t96

    6.1 1.2 森林转换为二叉树..........… 1 97

    6.11.3 二叉树转换为树.......…….. . 197

    6.11.4 二叉树转换为森林…....…………·…..……. 198

    6.11 .5 树与森林的遍历H…….. ......…....… .. . .. ... . .. .. 199

    6.12 赫夫曼树及其应用…..， ....……... ...…... ......... …..…..………... .... . ...…. .. ...........……..... ..………......… .200

    压缩而不出错是如何做到的呢?简单的说，就是把我们要压缩的文本进行重新编码，以达到减少‘不必袅的空间的技术. 压缩和解压缩技术就是基于赫久曼的研究之上发展

    而来，我们应该记住他.

    6.12. 1 赫夫受树….. …… ...... .... . .....200

    6.1 2.2 赫失受树定义与原理.....…203

    6.12.3 赫失曼编码……..…..……... ...……………..， .205

    6.1 3 总结回顾………... ...... .. . ......... ................. . ...………...……….川…….川 …...…… …..……..….川..叫…… ..川…….. … ……. 川 叮 . 什山...….叶山… .μ 川.川..………..……..…. ...………..……..…. .………....………. .….川. ……… .. .………..………..………. .… … .川 …...………..…. 川….川.. ……….叫…..…. . .………..…..…..斗o 佣 8

    6.14 结尾语…… …... . ... ……· ……........ . ……. .... . ..........…...... . ….......……………...............…........… 209

    人受伤时会流下泪水，树受伤时， 夭将再不会灾. 希望我们的未来不要仅仅是钢篇水

    泥建造的高楼， 也妥有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处.

    第 7 章 图…........………·…….......…·…...…………...... ....川.............山......….........…… . .. ι 川 ιμ . . .. …………..……. .…….川…..…………..…………. .……… … ..………. .……..…. . …..寸.

    18 目录

    7.1 开场白….......…………………….. ......._..... . .............. .. ............... . ... .. ...… ...................................212

    如果你不善于规划，很有可能就会出现如玩a好新疆后到海南，然后再冲向黑龙江这样

    的荒J量决策.

    7.2 图的定义…... ... ………·…………·……………........…·……........………………............ ........... .…… 2 1 3

    现实中，人与人之间关系就非常复杂，比如我的认识的朋友，可能他们之间也互相认

    识，这就不是简单的一对一、一对多的关系丁，那就是我们今久要研究的主是一一图.

    7.2. 1 各种固定义………….... .. ........2 14

    7.2.2 图的顶点与;也闯关系..………217

    72.3 连通图相关术语.... …. . …........……… ............219

    7.2.4 图的定义与术语总结………....... ....... . ........222

    7.3 图的抽象数据类型…......................…..………….........…..... . ~ . ... ... . ……….... ... . ... 1 . . .. ………·………222

    7.4 图的存储结构…..….......…..….. ................ .. ........ . .............…. ........….......……...... . …... ....……….123

    因为美爵的黑夜就是中国的白天.利用互联网，他的员工白天上班就可以监控到美国

    仓碎夜间的实际情况，如采发生了像火灾、偷盗这样的， 突发事件，及时电话到美因当

    地拥关人员处理

    7.4.1 邻按矩阵 ..... . ................... .. .. . 224

    7.4.2 邻接表……………….. . ..........228

    7.4.3 十字链褒......…·…..…..……...232

    7.4.4 邻接多重表......_.. .........…....…… ...................234

    7.4.5 边集数组…..….............……….........…..………· 刷 236

    7.5 图的遍历…..…. . .... . …………….........……........… · ……………….............. .. ...... ... . .......…..…….... .... . 237

    我有一采.f-晨准备出门，发现，钥也不见了 . 一定是我儿子拿着玩，不知道丢到哪个特

    角夺元去了 ， 你们说， 我应该如何找?

    7.5.1 深度优先遍历.…..….......…...23 8 7.5.2 广度优先遍历....………·…………………242

    7.6 最小生成树…...... .. ....…..…..… H…......... ……........ . .，. . ... . ....山…..…...... . .................. -..…..............245

    如果你加班加点，没日没夜设计出的结果是方案一，我想你离被地!ì税1且应该是不远了

    (同学微笑).因为这个方案比后两个方案一半还多的成本会让老板气晕过去的.

    7.6.1 笛'望姊 (PTim) 算法….. ......247 7.6.2 克鲁斯卡尔〈后uskal)￥法….................251

    7 7.7 最短路径....... .. . ........................…………….........……………… …………… ……. 25 盯

    有人为了省钱， 需路程最短，但换来站间距离长等原因并不有时间i 另 一些人，他为

    赶时间，最大的需求是总时间委组;还有一类;人，他们都不想多文惑，关键是换来妥

    少，这样可以在车上好好休息一下.

    7.7.1 池~斯特拉〈叫kstra) 算法 .259 7工2 弗洛伊德 (Floyd) 算法 ……......... .…….. 265

    7.8 拓扑排ff. ........……..……......... ….........…………..…........……..........…………….......………..….......270

    19 怵锚-噩噩

    电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中.

    场地都没有. 这都会导款荒谬的结果.

    7.8.1 拓扑排序介绍…….... . ............271 7.8.2 拓扑排序算法........……..……….......…… 272

    7.9 关键路径………·…..................…..….. .....……... . ....………..... ......... . ， ....…................. . .…...… ...... .......277

    假如这一个轮子委 0.5 天、造一个发动机要 3 天、造一个车底金委 2 夭、造一个外先

    妥3 天，其它零部件 2 天，全部零部件集中到一处要 0. 5 天，组:表咸丰要 2 夭，请问，在汽车厂造一辆车，最短需要多少天呢.?

    7织l 关键路径3丰 .法原理，…..…..…279 7.9.2 关键路径算法.........……….......... .. . .…........280

    7.1 0 总结回顾..........… ………..…………..........………….......叫…. ... . .....……...…..................…..... . .…..... .. 287

    7. 11 结尾语.......... ........ . .....…·……..………..... ......，. . ..…......... . ...….....….................… . ......…................. 289

    世界上最遥远的3é禽，不是牛 A 与牛 C 之间狭小空隙，而是你们当中， 有人在通往牛

    边的且在上-4狂奔，而有人步入大学校园就学会放弃.

    第 8 章查找………...……·…………...……·……….....…………...... .………...…....291

    20

    s

    ( I 2 7 )

    d;( ( 12 5è6 ~ c6尘 自由 1 刚2 E自1 阳4

    在是妇任主忌也) 阳S 倒币 l目7

    8.1 开场自…...... .…..…………………………. . ....…... . ...... . .…........… . . ............……….............. ..... .. ......... .. 292

    当你精心写守一篇博文或者主传一组照片到互联网上， 来自世界各地的元数 蜘蛛'

    便会缘拥而至.所谓蜘炼就是搜索引擎公司服务葛上软件，它才~互联网当成了蜘蛛网，没日没夜的访问上面的各种信息.

    8.2 查找概论............... .. . ...... .….....-.…. . .... .… 叶 …………..…… .. . ……..…..……..... .........-…..……….293

    比如网络时代的新名词.如蜗居、蚁族等，如来常委将它们收录到汉语词典中，显然收录时就需要查找它们是、 否存在，以及找到如果不存在时应该收录的位豆.

    8.3 顺序表查找…..…….... ............ . ... ， .......…叫.... ...…川…........… - ……..................…… .............. 295自豪

    8.3.1 顺序表查找算法...................296 8.3.2 顺序褒查找优化…............................……..… 297

    8.4 有序表查找·…..……………………......….... .. .…....……..….........……..…..…………. . .. .....…..….......… 298

    成在纸上已经写好了一个 100 以内的」正整数请你猎，闷儿次可以输出来.当时已经介

    绍了如何才可以最快的输出这个数字. 4民们把这种每次取中间记录查找的方法叫做折

    半查找.

    8.4.1 折半查找.....……………….......298

    8.4.2 擂值查找....-.....……..............30 1

    8.4.3 斐汲那爽资找.u.... . .....…..……….......…..… ....302

    8.5 线性索引查找…..................... ..............................................……………………·…………..……….306

    4民母亲年纪火丁 ，经常在东里找不到东西.于是她用一小本子，记录了家里所有小东

    西放置的位置，比如户口本放在右手床头柜7画抽A是中 ，钞票放在农……咳，这个就

    不提了.

    8.5.1 稠密索弓|…..….......…....… ..... 307

    8.5.2 分块索引....................….......308

    8.5.3 fjlJ 排索引……......…..山………..…. .... . ...… .......311

    8.6 二叉排序树….................…. . ............……..…...........…..…..…..….......…..…….......……......…….......… .313

    后来老虎来了， 一人拚命地跑，另一人..1 急中生智， 爬到了树上.而老成是不会爬树

    的，结果…….爬树者改变了'色的思想.这一改变何等重要， 捻回了自己的一条命.

    8.6.1 二叉排序树查找操作...........316

    8.6.2 二叉排序树插入操作........... 318

    8.6.3 二叉排序树删除操作.....……… …..…-…..320

    8.6.4 二叉排序树总结.... ………... ....... .….........…·…327

    8.7 平衡二叉树 ( AVL 树) .

    乎板就是一个世界，当诱惑降恼，人心中的平衡被打破，世界就会混乱，录后窗下的

    只有孤独寂寞失欺.这种单调的积揣化的社会， 禁不住诱.t的侵蚀， 最容易被侵蚀的.

    恰恰是最空虚的心灵.

    8.7.1 平衡二叉树实现原理...........330 8.7.2 平衡二叉树实现算法…..……....................334

    8.8 多路查找树 ( B 树〉…..…..….......…..…..… …………......................…....………..……...........……. 341

    要观察一个公司是否严谨， 着他们如何开会就知道1 . 如果开会时每F小人都只是带

    一张嘴. IIp兴发宫，这肯定是一家不严谨的公司.

    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

    4 位4哀怨学太极系，听说学校有个叫张三半的人打得特别好.于是到学校学生处找人，.I..作人员拿出学生名单..佟告诉你，学校没这个人， 并说张三丰儿百年前就已经在

    武当山作古了.

    21 目录

    8.9.1 散列表查找定义…….. ， . ... .. . ..354 8.9.2 散列表查找步骤......….-.......... …. . …........ .. . .. 355

    8.10 散列函数的构造方法…..………………….................……·……......~.…·…….........…·……………..356

    8.1 0.1 室接定址法..........…..……357

    8.1 0.2 数字分析法... ....…·…..…....358

    8.10.3 平方取中法…..…. .………..358

    8.]0.4 折叠法........…….... ...………....... . ......... .. ... ... . .359

    8.1 0.5 除留余数法……..…............……….... ....… 359

    8.10.9 随机数法....，.. ......………·….......……...... . ..360

    8.11 处理散列冲突的方法….......….. .......……. . ……........ . ………………………·…..... ... .. . ..…. . …..…. ......360

    我们每个人都希望身体健康，虽然疾病可以预防，但不可避允.欢有任何人可以说，生下来到现在没有生过一次病.

    8.11.1 开放定址法……..…..…..…361

    8.1 1.2 再做到函数法....……………..363

    8.1 1.3 链地址法……..... .……·………..………... .. . 363

    8.1 1.4 公共溢出区法..........….. ……...... . .............…364

    8.12 散列表查找实现…...

    8.12.1 散列表查找算法实现…..…365 8.12.2 散列表查找性能分析...……·…..….. …........367

    8.13 总结回顾.. .. .. ........... . .......…………........………...............….........…................…….......… 368

    8.14 结尾语….....~..…..….......………·…..…..…….. .......…..……...................……..….......……... ........... ........369

    如果我是个喜欢汽车的人，时常J 枝汽车信息.那么当我在校余柜中输入甲壳虫、美

    洲虎等关键饲时，不要让动物和人物成为投余的头条.

    第 9 章排序…...山……·…......... 山 ………………………. .………………… . ..373

    9. J 开场白……………·…....... …叶…………....... .......…........…..............…...........….......…...…..…….........… 374

    假如我想买一台 iphone4 .的手机，于是，仨了某电子商务网站去放索.可搜索后发现，有 8863 个相关的物惕，如此之多.这叫我知，何选择. 我其实是想买俊宜一点的，但是

    又怕遇到骗子，想找信誉好的商家，如何做?

    2. 2 9 织归 .2 排序的基本概念与分类.………..………..……. .… E ….……….…… … . …-

    比如幸我址们某些大学为了选拔4 在且主科d 丰 ι桑仪优，秀的学生，要求对所有学生的所有科目总分

    倒序排名，并且在同样总分的情况下将语数外总分1 做伽l序排名.这就是对总分和语数

    外总分两个次关键字的组合排序.

    目录

    9.2.1 排序的稳定性. .........……… 376

    9.2.2 内排序与外排序.....……........377

    9.2.3 排序用到的结构与函数………………......378

    9.3 冒泡排序…..…………...... ..…………..………………… .H..... . ........ …… . . .......…. ......... . ..…… 378

    无论你学习哪种编程语言，在学到循环和数组时.通常都会介绍一种排序算法，而这

    个算法一般就是冒泡排序. 并不是它的名称很好听，而是说这个算法的思路最简单，最容易理解.

    9.3.1 -1羡简单排序实现……......……379

    9.3.2 冒泡排序算法…..…..…..........380

    9.3.3 冒泡排序优化..'. ....... . .... . ...…·山…..………382

    9.3.4 冒泡排序复杂度分析.. .... .. . .…..………….......383

    9.4 简单选择排序…..…..………........………. ........…... . ...…….......…..…...............… . ...….......…·….....384

    还有一种做股票的人，他1((1~在沪、出手，只走在不断观察和判断，等时机一到， 果断买

    进或卖出. 他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰.

    9.4.1 简单选择排序算法............…..384 9.4.2 简单选择排序复杂度分析……... . .… ............385

    9.5 直接插入排序…..........，....................

    哪怕你是第一次玩，扑克牌，只安认识这些数字.J1!.牌的方法都是不用教的. 将 3 和 4

    移动到 5 的左侧?再将 2 移动到最左侧，顺J乎就算是理好了 . 这里，我们的理牌方法.

    就是直接插入排序法.

    9.5. 1 直接插入排序算法...............386 9.5.2 直接插入排序复杂度分析 . ....………..….388

    9.6 希尔排序. ...... . ......... . .................….. . ....…..-...... . ... . ............... ..…....... ....... .. ..… .......…… …... ......…..… 3 89

    不管怎么说，希尔排序算法的发明， 使得我们终于突破了慢速排序的时代(超越了对

    闯复杂度为 o (nl) ).之后，灵，为高效的排序算法也就相绽出现了.

    9.6.1 希尔排序原理........ . ..............391

    9.6.2 希尔排序算法.....…......…… 391

    9.6.3 希尔排ff 复杂分析... .....………. ......…… ....395

    9.7 雄排序…..叫…... ................ . ... .. .... .. .. ........ ..-... . …..……….........………… . . ... . ..........… ..................396

    什么叫难结构呢?回忆一下我们小时候， 特别走男同学，基本都玩过叠罗汉的悉作剧.

    通常都是先把某个要整的人按倒在地，然后大家就一拥而.J:Ar 了.J:去……后来?后来

    当然就是一笑了之.

    9.7.1 堆排序算法…....…................398 9.7.2 雄排序复杂度分析.. .. ......... . ....…..… ....... ....405

    23 9.8 归并排序…..…........…·……......…........……..........................................…....……..…..…..…............... 406

    即使你是你们班级第一、 甚至年级第一名， 如果你没有本分数线. JlJ 说明你的成绩排

    不到全省前 1 万名，你也就基本失会了当年J:.本科的机会1 .

    9.8.1 归并排序算法…..... .. . ....…… 407

    9.8.2 归并排序复杂度分析.....…...4 1 3

    9.8.3 非i撞归实现归并排序... . ………....……….... .4 1 3

    9.9 快速排序..........….......………..…..….........……… … ……………………川. 4 创1 7

    终于我们的高手要登场7 . 将来你工作后， 你的老板让你写个神序算法，ifQ你会的算

    法中竟然没有快速排序. f;..想你还是不要声张， 偷偷去祀快速排~~法找来.tt进龟脯，这样至少你不至于被大伙儿'民笑.

    9.9.1 快速排序算法.... ...… ...... . .. . 41 7

    9.9.2 快边排序复杂度分析…..…...421

    9.9.3 快速排序优化......… . .. . ...…..…..……………....422

    9. 10 总结回顾....川....川...... .. ... .... ...... . u ....... . ......... . ....... .... . ..........叫.......... .. ..... ............. ....... . ._，............… 428

    目前还没有十全十关的排序算法， 有优点就会有缺点， 即使是快速梯A-法，也只是在

    整体性能上优越. 它也存在排序不稳定、需委大量辅.空间 . 对少量..据梯序元优势

    等不;c

    9. 门 结尾语…..….......…..…….......… 巾 ……..………….........…………..…….........H............…….......... 430

    24

    如果你有梦想的话， 就妥会捍卫它.当别人做不到的时候， 他们就想要4告诉你， 你也

    不能. 如果你~''1是什么 ， 就待会努力争取.就这样!

    关键词索引........... . .....…. .. .. ......... . ..........….... . ... …….. . ...........…….. . ...... . .. . ...…...... . .………. 435

    参考文献……...... . .. ............…...... . …· …... . ......... . .... .. .. .. . ................... ... . …….... ... .. .. ... . .….... 439 第 1 章数据结构绪论

    数据结构;

    是相互之间存在一种或多种特定关系的数据元素的集合。1.1 开场自

    lf you give someone a program, you will frus旬在te them for a 也y; if you teach them

    how to program, you will frustrate them for a lifetime. (如果你交给某人一个程序，你

    将折磨他一整天i 如果你教某人如何编写程序，你将折磨他一辈子。)

    而我可能就是要折磨你们一辈子的那个人。大家好!我是 《数据结构》这门课的

    老师，我叫封清扬。同学私下里都叫我 疯子n ，嘿嘿，疯子可是有思想的标志哦。

    在座的大家给我面子，都来选修我的课，这点我很高兴@不过在上课前，有些话

    还是要先说一下。

    数据结构是计算机专业的基础课程，但也是一门不太容易学好的课，它当中有很

    多费脑子的东西，之后在上课时，你若碰到了困惑或不解的地方， 都是很正常的反

    应，就像你想乘飞机去旅行，在飞机场晚点几个钟头，上了飞机后又颠簸恐慌了一把

    一样，别大惊小怪，都很平常，只要能安全到这就是成功。

    如果你的学习目的是为了将来要做一个优秀的程序员，向微软、 Google 的工程师

    们看齐，那么你应该要努力学好笆，不单是来听课、 看看教科书，还需要课后做题和

    上机练习。不过话说回来a 如果你真有这样的志向，谋前就该开始研究了，这样来听

    我的课，就更加有主动性，收获也会更大。

    如果你的目的是为了考计算机、软件方面的研究生，那么这门必考课，你现在就

    可以准备起来一一习良多时候，考研玩的不是智商，其实就是一个人投入的时间而已。

    如果你只是为了混个学分，那么你至少应该要坚持来上课，在我的课堂上听懂

    了，学明白了 ，考前适当地复习，拿下这几个学分应该不在话下。

    如果你只是来打酱油的，当然也可以，我的课不妨碍你打酱油，但你也不要妨碍

    其他同学坐到好位子，所以请靠后坐，并且保持安静，静心打酱油就好。

    如果，我是说真的如果，你是一个对编程无比爱好的人，你学数据结构的目的，既不是为了工作为了钱，也不是为了学位和考试，而只是为了更好地去感受编程之

    美。啊，你应该得到我的欣赏，我想我非常愿意与你成为朋友一一因为我自己也没有

    做到如此纯粹地去学习和应用宫。

    2 第1'1挺戴德结构绪论

    1.2 你数据结构怎么学的?

    孚先我有一个学生叫蔡遥，绰号小菜。他前段时间一直通过 E-maiJ 与我交

    流，其中说起了他工作的一些经历，感慨万千。我在这里就讲讲小菜的故事。

    他告诉我，在做我学生时，其实根本就没好好学数据结构，时常逃课，考试也是

    临时突击后勉强及格。 毕业后，他几经求职，算是找到了一份程序员的工作。

    工作中，有一次他们需要开发一个客服电话系统，他们项目经理安排小菜完成客

    户排队模块的代码工作。

    小菜觉得这个很容易，用数据库设计了一张客户排队衰，并且用一个自动递增的

    整型数字作为客户的编号。只要来一个客户，就给这张表的末尾插入一条数据。等客

    服系统一有空闲，就从这张表中取出最小编号的客户提交，并且删除这条记录。花了

    两天时间，他完成开发井测试通过后，得意地提交了代码。谁知他们的项目经理，看

    完代码后，跑到他的桌前，拍着桌子对他说..你数据结构怎么学的?这种实时的排队

    模块，用什么数据库呀，在内存中完成不就行了吗。赶快改，今天一定要完成，明天

    一早交给我。

    小菜吓得一身冷汗，这脸丢得有些大了，自己试用期都投结束，别因此失去工

    作。于是他当天加班加点，忙到晚上十一点，用数组变量重新实现了这个功能，因为

    考虑到怕敬组不够大而溢出，于是他设计 100 作为数组的长度。

    回到家中，他害怕这个代码有问题，于是就和他的表哥大鸟说起了这个事。他表

    哥笑嘻嘻地对他说你数据结构怎么学的? '刀、菜惊讶地张着大口， 一句话也说不出

    来。然后他表哥告诉他，这种实时的排队系统，通常用数据结构中的队列结构n 是

    比较好的，用数组虽然也可以，但是又要考虑溢出，又要考虑新增和删除后的数据移

    动，总的说来很不方便。你只要这样.......这样…·就可以了。

    小菜在大鸟的帮助下，忙到凌晨 3 点，重新用队列结构又写了一遍代码，上班时

    用 U 盘拷回公司，终于算是过了项目经理这一关。

    之后，小菜开始重视数据结构，找回大学的课本重新学习。他还给我发了好些邮

    件，问了我不少他困惑的数据结构和算法的问题，我也一一给了他解答。终于有一

    天，他学完了整个课程的内容，并给我写了一封感谢倍，信中是这么说的:

    封老师:您好!感谢您这段时间的帮助，在大学时没有好好土您的课真是我最大

    的遗憾。 我现在巳经学完了 〈 数据结构》整本书的内容，收获还是很大的。 可是我一

    3 直有这样的困惑想请教您，那就是我在工作中发现，我所需要的如辑、队列、链表、散列表等结构，以及查找、 排序等算法，在编程语言的开发工具缸中都有完美的 实

    现，我只需要掌握如何使用它们就可以了，为什么还要去弄懂这里面的算法房、理

    呢?

    我收到这封信时，立马跳了起来，马上拨通了他的孚机，第一句话就是……你们

    猜猜看，我说了啥?

    你数据结构怎么学的? .. ( 全场同学齐声大喊，大笑)

    好了，我为什么这么讲，等你们学完我的课程就自然会明白。我只希望在将来，不要有某个人也对你们说出这句话，如果当真听到了这句话，就拜托你不要说你的数

    据结构老师是我封清扬，嘿嘿。

    现在我们正式开始上课。

    1.3 数据结构起源

    早期人们都把计算机理解为数值计算工具，就是感觉计算机当然是用来计算的，所以计算机解决问题，应该是先从具体间题中抽象出一个适当的数据模型，设计出一

    个解此数据模型的算法，然后再编写程序，得到一个实际的软件。

    可现实中， 我们更多的不是解决数值计算的问题，而是需要一些更科学有效的手

    段(比如表、树和图等数据结构)的帮助，才能更好地处理问题。 所以数据结构是一

    门研究非数值计算的程序设计问题中的操作对象，以及官们之间的关系和操作等相关

    问题的学科。

    1968 年，美国的高德纳 ( Donakl E. Knuth) 教授在其所写的 《计算机程序的f艺

    术》 第一卷 《基本算法》 中，较系统地阐述了数据的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。 同年，数据结构作为一门独立的课程，在计算机科学的

    学位课程中开始出现。 也就是说，那之后计算机相关专业的学生开始接受 《数据结

    构》 的 u折磨n 一一其实应该是享受才对。

    之后， 70 竿代初，出现了大型程序，软件也开始相对独立，结构程序设计成为程

    序设计方法学的主要内容，人们越来越重视数据结构气认为程序设计的实质是对确

    定的问题选择一种好的结构，加上设计一种好的算法。可见，数据结构在程序设计当

    中占据了重要的地位。

    4 第 11脏 敛据统构绪论

    程序设计 = 鼓据结构+算法

    1.4 基本概念和术语

    说到数据结构是什么，我们得先来谈谈什么叫数据。

    正所谓巧妇难为无米之炊'\再强大的计算机，也是要有米'下锅才可以干活

    的，否则就是一堆破铜烂铁。 这个米就是数据。

    1 .4. 丁数据

    数据:是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识

    别，并输入给计算机处理的符号集合。 数据不仅仅包括整型、实型等数值类型，还包

    括字符及声音、图像、视频等非数值类型。

    比如我们现在常用的搜索引擎，一般会有网页、 M陀、图片、视频等分类。 MP3

    就是声音数据，图片当然是图像数据，视频就不用说了，而网页其实指的就是全部数

    据的搜索，包括最重要的数字和字符等文字数据。

    也就是说，我们这里说的数据，其实就是符号，而且这些符号必须具备两个前

    提:

    可以输入到计算机中。

    能被计算机程序处理。

    对于整型、实型等数值类型，可以进行数值计算。

    对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频等其实i 是可

    以通过编码的手段变成字符数据来处理的。

    1 .4.2 数据元素

    数据元素:是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处

    理。 也被称为记录。

    比如，在人类中，什么是数据元素呀? 当然是人了。

    富类呢?哈， 牛、马、羊、鸡、猪、 狗等动物当然就是禽类的数据元素。

    5 l束雷

    1.4.3 数据项

    数据项:一个数据元素可以自若干个数据项组成。

    比如人这样的数据元素，可以有眼、耳、鼻、嘴、 手、脚这些数据项，也可以有

    姓名、年龄、性别、出生地址、联系电话等数据项，具体有哪些数据项，要视你做的

    系统来决定。

    数据项是数据不可分割的最小单位。在数据结构这门课程中，我们把数据项定义

    为最小单位，是有助于我们更好地解决问题。所以，记住了，数据项是数据的最小单

    位。但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。就像我们

    讨论一部电影时，是讨论这部电影角色这样的数据元素，而不是针对这个角色的姓

    名或者年龄这样的数据项去研究分析。

    1 . 4. 4 数据对象

    数据对象:是性质相同的数据元素的集合，是数据的子集。

    什么叫性质相同呢，是指数据元素具有相同数量和类型的数据项，比如，还是刚

    才的例子，人都有姓名、生日、性别等相同的数据项。

    既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性

    质， 在不产生混淆的情况下，我们都将数据对象简称为数据e

    好了，有了这些慨念的铺垫，我们的主角登场了。

    说了数据的定义，那么数据结构中的结构又是什么呢?

    1 .4 . 5 数据结构

    结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列

    方式。严格点说， 结构是指各个组成部分相互搭配和排列的方式，在现实世界中，不

    同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。 那数

    据结构是什么?

    数据结梅:是相互之间存在-种或多种特定关系的数据元蠢的集舍。

    在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集

    合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

    为编写出一个 α好的程序，必须分析待处理对象的特性及各处理对象之间存在

    6 第 1 章戴掘结构编论

    的关系。这也就是研究数据结构的意义所在。

    定义中提到了一种或多种特定关系，具体是什么样的关系，这正是我们下面要讨

    论的问题。

    1.5 逻辑结构与物理结构

    按照视点的不同， 我们把数据结构分为逻辑结构和物理结构。

    1.5. 1 逻辑结构

    逻辑结构:是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需

    要关注的问题。 逻辑结构分为以下四种:

    1. 集合结构

    集合结构:集合结构中的数据元素除了同属于一个集合外，宫们之间没有其他关

    系。 各个数据元素是平等'的，官们的共同属性是同属于一个集合。数据结构中

    的集合关系就类似于数学中的集合(如图 1-5-1 所示)。

    2. 线性结构

    ①①

    ①①①

    ①2 ①

    因 1-5- [

    线性结构:统性结构中的数据元素之间是一对一的关系 (如图 1-5- 2 所示)。

    7 囱 1 -5-2

    3. 树形结构

    树形结构:树形结构中的数据元素之间存在一种一对多的层次关系 (如图 1-5-3

    所示)。

    8

    J

    图 1--3

    4. 图形结构

    图形结构:图形结构的数据元素是多对多的关系 ( 如图 1-5-4 所示)。

    图 1--4

    我们在用示意图表示数据的逻辑结构时，要注意两点:

    将每一个数据元素看做一个结点，用圈圈表示。

    元素之闯的逻辑关系用结点之间的连线表示.如果这个关系是有方向的，那么用

    带箭头的连续表示。第 1 章戴据结构编论

    从之前的例子也可以看出，逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

    1 . 5. 2 物理结构

    说完了逻辑结构，我们再来说说数据的物理结构 (很多书中也叫做存储结构，你

    只要在理解上把官们当一回事就可以了)。

    物理结构:是指数据的逻辑结构在计算机中的存储形式。

    数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素

    存储到计算机的存储器中。存储器主要是针对内存而言的，像硬盘、软盘、光盘等外

    部存俯器的数据组织通常用文件结构来描述。

    数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的，如何

    存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

    数据元素的存储结构形式有两种:顺序存储和链式存储。

    1 . 顺序存储结构

    顺序存储结构:是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关

    系和物理关系是一致的 (如图 1-5-5 所示)。

    阳双双双双双吹训 翻 1-5-5

    这种存储结构其实很简单，说白了， 就是排队占位。大家都按顺序排好，每个人

    占一小段空间，大家谁也别插谁的队。 我们之前学计算机语言时，数组就是这样的顺

    序存储结构。当你告诉计算机，你要建立一个有 9 个整型数据的数组时，计算机就在

    内存中找了片空地， 按照一个整型所占位置的大小乘以 9 ，开辟一段连续的空间，于

    是第一个数组数据就放在第-个位置，第二个数据放在第二个，这样依次摆放。

    2. 链式存储结构

    如果就是这么简单和有规律，一切就好办了。可实际上 ，总会有人插队，也会有

    人要上厕所、有人会放弃排队。所以这个队伍当中会添加新成员，也有可能会去掉老

    元素，整个结构时刻都处于变化中。显然，面对这样时常要变化的结构，顺序存储是

    不科学的。 那怎么办呢?

    9 l束髓噩噩噩噩圃

    现在如银行、医院等地方，设置了排队系统，也就是每个人丢了，先领一个号，等着叫号，叫到时去办理业务或者病。在等待的时候，你爱在哪在哪，可以坐着、站

    着或者走动，甚至出去逛一圈，只要及时回来就行。 你关注的是前一个号有没有被叫

    到，叫到了，下一个就轮到了。

    链式存储结构:是把数据元素存放在任意的存储单元里，这组存储单元可以是连

    续的，也可以是不连续的。 数据元素的存储关系并不能反映其逻辑关系，因此需要用

    一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置(如

    图 1-5-6 所示) 。

    因 1-5-6

    显然，链式存储就灵活多了，数据存在哪里不重要，只要有一个指针存放了相应

    的地址就能找到白了。

    前几年香港有部电影叫 《无间道)> ，大陆还有部电视剧叫 《潜伏>> ，都很火，不知

    道大家有没有看过。 大致说的是，某一方潜伏在敌人的内部，进行一些情报收集工

    作。为了不暴露每个潜伏人员的真实身份，往往都是单线联系，只有上线知道下线是

    谁，并且是通过暗号来联络。正常情况下，情报是可以顺利地上传下达的，但是如果

    某个链条中结点的同志牺牲了，那就麻烦了，因为其他人不知道上钱或者下钱是谁，后果就很严重. 比如在 《无间道》 中，梁朝伟是警方在黑社会中的卧底，一直是与黄

    秋生扮演的警官联络，可当黄遇害后，梁就无法证明自己是一个警察。所以影片的结

    尾， 当梁朝伟用枪指着刘德华的头说，对不起，我是警察。 刘德华马上反问道 tt 谁

    知道呢? 是呀，当没有人可以证明你身份的时候， 谁知道你是谁呢?影片看到这

    里，多少让人有些唏嘘感慨。 这其实就是链式关系的一个现实样例。

    逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数

    据及其逻辑关系存储到计算机的内存中。

    10 第1i院费量据结构绪论

    1.6 抽象数据类型

    1 .6 .1 数据类型

    数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

    数据类型是按照值的不同进行划分的。在高级语言中，每个变盘、常量和表达式

    都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

    当年那些设计计算机语言的人，为什么会考虑到数据类型呢?

    比如，大家都需要住房子，也都希望房子越大越好。但显然，没有钱，考虑房子

    是没啥意义的。于是商品房就出现了各种各样的房型，有别墅的，有错层的，有单阔

    的;有一百多平米的，也有几十平米的，甚至在北京还出现了胶囊公寓一一只有两平

    米的房间·…..这样就满足了不同人的需要。

    同样，在计算机中，内存也不是无限大的，你要计算一个如 1+1=2 、 3+5=8 这样

    的整型数字的加减乘除运算，显然不需要开辟很大的适合小数甚至字符运算的内存空

    间。于是计算机的研究者们就考虑，要对数据进行分类，分出来多种数据类型。

    在 C 语言中，按照取值的不同，数据类型可以分为两类;

    原子类型:是不可以再分解的基本类型，包括整型、实型、字符型等。

    结构类型:自若干个类型组合而戚，是可以再分解的。例如，整型数组是由若干整

    型数据组成的。

    比如，在 C 语言中变量声明 i nt a , b ，这就意味着，在给变量 a 和 b 赋值时不能

    超出 int 的取值范围，变量 a 和 b 之间的运算只能是 int 类型所允许的运算。

    因为不同的计算机有不同的硬件系统，这就要求程序语言最终通过编译器或解释

    器转换成底层语言，如汇编语言甚至是通过机器语言的数据类型来实现的。可事实

    上，高级语言的编程者不管最终程序运行在什么计算机上，他的目的就是为了实现两

    个整型数字的运算，如 a+b、 a-b、 axb 和 ab 等，他才不关心整数在计算机内部是如

    何表示的 ， 也不想知道 CPU 为了实现 1+2 进行几次开关操作，这些操作是如何实现

    的，对高级语言开发者来讲根本不重要。于是我们就会考虑，无论什么计算机、什么

    计算机语言，大都会面临着如整数运算、实数运算、字符运算等操作，我们可以考虑

    把它们都抽象出来。

    11 抽象是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的

    细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细

    节，只保留实现目标所必需的信息。

    1 . 6 . 2 抽象数据类型

    我们对已有的数据类型进行抽象，就有了抽象数据类型。

    抽象数据类型 (Abstract Dataη肘， ADT) : 是指一个数学模型及定义在该模型

    上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内

    部如何表示和实现无关。

    比如刚才的例子， 各个计算机，不管是大型机、小型机、 町、平板电脑、 PDA .

    甚至智能手机都拥有 整数类型，也需要整数阔的运算，那么整型其实就是一个抽

    象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由

    于其定义的数学特性相向，在计算机掬程者看来，它们都是捆同的。因此， 抽象'的

    意义在于数据类型的数学抽象特性。

    而且，抽象数据类型不仅仅指那些已经定义并实现的数据类型，还可以是计算机

    编程者在设计软件程序时自己定义的数据类型，比如我们编写关于计算机绘图或者地

    图类的软件系统，经常都会用到坐标。也就是说，总是有成对出现的 x 和 Y . 在 31D

    系统中还有 z 出现，既然这三个整型数字是始终在一起出现，我们就定义一个叫 point

    的抽象数据类型，包有 x、 y、 z 三个整型变量，这样我们很方便地操作一个 point 数

    据变量就能知道这一点的坐标了。

    根据抽象数据类型的定义，它还包括定义在该模型上的一组操作。就像超级玛

    丽这个经典的任天堂游戏，里面的游戏主角是马里奥 ( Marì的。我们给他定义了几

    种基本操作，走(前进、后退、 上、 下)、跳、打子弹等。 一个抽象数据类型定义了 :

    一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于，一个

    抽象数据类型到底需要哪些操作，这就只能由设计者根据实际需要来定。像马里奥，可能开始只有两种操作， 走和跳，后来发现应该要增加一种打子弹的操作， 再后来发

    现有些玩家希望宫可以走得快一点，就有了按住打子弹键后前进就会 u跑的操作。

    这都是根据实际情况来设计的。

    12 第 11能做据结构编论。 ?

    画

    画 在盲运回

    t ~'' ~ ~. __ C:J I

    ~户:世 I~ ，飞 íI

    融销制ig!即持剧组事盼斟组; m 1-6-1

    事实上， 抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽

    象数据类型把实际生活中的问题分解为多个规模小且窑易处理的问题， 然后建立一个

    计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而

    使具体实现过程隐藏起来。

    为了便于在之后的讲解中对抽象数据类型进行规范的描述，我仍给出了描述抽象

    数据类型的标准格式:

    hDT 抽象数据类型名

    Data

    数据元素之间逗得关系的定义。Feration

    操作 1

    初始条件

    操作结来描述

    操作 2

    操作 n

    endADT

    13 l束菌噩噩噩圄

    1.7 总结回顾

    今天首先用我一个不争气的学生为例子，说明数据结构很重要。接着讲了数据结

    构的起源，说白了，就是一老外，觉得编程这玩意儿不弄得复杂点，不能证明他厉

    害，所以推出数据结构'这一课程，让所有学编程的入享受它带来的乐趣或者

    体验被折磨后无尽的烦恼.

    接着，正式介绍了数据结构的一些相关概念，如图 1平1 所示。

    数据元素 数据元素

    数据

    数据对象

    数据元素 数据元素

    数据项1 数据项2 数据项1 数据项2 数据项l 数据项2 数据项1 数据项2

    1!l 1-7-1

    由这些概念，给出了数据结构的定义: 数据结构是相互之间存在一种或多种特定

    关系的数据元素的集合。 同样是结构，从不同的角度来讨论，会有不同的分类，如图

    1-7-2 所示。

    14

    逻辑结构 I

    · 集合结构

    · 线性结构

    . 树形结构

    · 图形结构

    00 1-7-2

    理结构 1

    . J 购芋存储吉构

    · 链接存储吉构

    之后，我们还介绍了抽象数据类型及它的描述方法，为今后的课程打下基础。第 1 到E 鼓据结构绪论

    1.8 结尾语

    最后，我想对那些已经开始自学数据结构的同学说，可能你们会困惑、不懂、习之

    理解、不会应用，甚至不知所云。可实际上，无论学什么，都是要努力才可以学到真

    东西。只有真正掌握技术的人，才有可能去享用它。 如果你中途放弃了，之前所有的

    努力和付出都会变得没有价值。学会游泳难吗?掌握英语口语难吗?可能是难，但在

    掌握了的人眼里，这根本不算什么，就那么回事呀。只要你相信自己一定可以学得

    会、学得好，既然无数人已经掌握了，你凭什么不行。

    最终的结果一定是，你对着别人很牛地说数据结构一一就那么回事。

    哎，我如此口干舌燥地投众位所好，怎么还有人打瞌睡呢?罢了罢了，下课。

    15 16 第 2 章算法

    算 法:

    算法是解决特定问题求解步骤的描述， 在计算机中表现为指令的有限序列， 并且

    每条指令表示一个或多个操作。2.1 开场白

    各位同学大家好。

    上次上完课后，有同学对我说，老师，我听了你的课，感觉数据结构没什么的，你也太夸大宫的难度了。

    是呀，我好像是强调了数据结构比较搞脑子，而上次课，其实还没拿出复杂的东

    西来说道。不是不想，是没必要，第一次课就把你们糊弄晕，那以后还玩什么，逃课

    的不就更多了吗?你们看，今天来的人数和第一次差不多，而且暂时还没有睡觉的。

    今天我们介绍的内容在难度上就有所增加了，做好准备了吗?

    2.2 数据结构与算法关系

    我们这门课程叫数据'结构，但很多时候我们会讲到算沽，以及它们之间的关系。

    市场上也有不少书叫数据结构与算法分析'这样的名字。

    有人可能就要问了，那你到底是只讲数据结构呢，还是和算法一起讲?它们之间

    是什么关系呢? 干吗要放在一起?

    这问题怎么回答。打个比方吧，今天是你女友生日，你打算请女友去看爱情音乐

    剧，到了戏院，抬头一看一一 《梁山伯>> 18 : 00 开演。 嗯，怎么会是这样? 一间才

    知，今天饰演祝英台的演员生病，所以梁山伯唱独角戏。 真是搞笑了，这还有什么看

    头。于是你们打算去看爱情电影。到了电影院， 一看海报一一- <<罗密欧>> ，是不是名字

    写错了，问了才知，原来饰潢朱丽叶的演员因为嫌弃演出费用大低，中途退摸了。制

    片方考虑到已经开拍，于是就把电影名字定为 《罗密欧>> ，主要讲男主角的心路旅程a

    歧，这电影还怎么看啊?

    事实上，数据结构和算法也是类似的关系。只谈数据结构 ， 当然是可以，我们可

    以在很短的时间就把几种重要的数据结构介绍完。听完后，很可能你没什么感觉，不

    知道这些数据结构有何用处。 但如果我们再把相应的算法也拿来讲一讲，你就会发

    现，甚至开始感慨:哦，计算机界的前辈们，的确是一些很牛很牛的人，他们使得很

    多看似很难解决或者设法解决的问题，变得如此美妙和神奇。

    也许从这以后，慢慢地你们中的一些人会开始把你们的崇拜对象， 从帅哥美女、18 第 2 :1撞算法

    什么 u哥n 什么姐们，转移到这些大胡子或者秃顶的老头身上，那我就非常欣慰

    了。而且，这显然是一种成熟的表现，我期待你们中多一点这样的人，这样我们国家

    的软件行业，也许就有得救了。

    不过话说回来，现在好多大学里，通常都是把 u算法n 分出一门课单独讲的，也

    就是说，在《数据结构》课程中，就算谈到算法，也是为了帮助理解好数据结构，并

    不会详细谈及算法的方方面面。 我们的课程也是按这样的原则来展开的。

    2.3 两种算法的比较

    大家都已经学过一门计算机语言，不管学的是哪一种，学得好不好，好歹是可以

    写点小程序了。现在我要求你写一个求 1+2+3+……+ 100 结果的程序，你应该怎么写

    呢?

    大多数人会马上写出下面的 C 语言代码(或者其他语言的代码) :

    int i , sum = 0 , n ; 100;

    for (i = 1; i < = n; i++)

    sum = sum + í ;

    printf ( n 皆.d n, sum) ;

    这是最简单的计算机程序之一，官就是一种算法，我不去解释这代码的含义了。

    问题在于，你的第一直觉是这样写的，但这样是不是真的很好?是不是最高放?

    此时，我不得不把伟大数学家高斯的童年故事拿来说一遍，也许你们都早已经听

    过，但不妨再感受一下，天才当年是如何展现天分和才华的。

    据说 18 世纪生于德国小村庄的高斯， 上小学的一矢，课堂很乱，就像我们现在下

    面那些费窃私语或者'拿着手机不停摆弄的同学一样， 老师非常生气， 后果自然也很严

    重。于是老师在放学时，就要求每个学生都计算 1+2+ …+100 的结果，谁先算出来谁

    先回家。

    天才当然不会被这样的问题难倒，高斯很快就得出了答案，是 5050。老师非常惊

    讶，因为他自己想必也是通过 1+2=3 ， 3+3=6 , 6+4=10,……, 4950+ 100=505。 这样

    算出来的，也算了很久很久。说不定为了怕错，还算了两三遍。可眼前这个少年， 为

    何可以这么快地得出结果?

    19 怵雷噩噩噩圄

    高斯解释道:

    用程序来实现如下:

    sum = 1 + 2 + 3 + ... + 99 + 100

    sum = 100+ 99+ 98+... + 2+ 1

    2xsum= 101 + 101 + 101+ ... + 101+ 101

    、、 J

    、俨

    共 100 个

    所以 sum=50S0

    int 1, sum = 0, n = 10.0:

    sum = (1 + n) n I 2;

    printf ( 剧， sum);

    神童就是神童，他用的方法相当于另一种求等差数列的算法，不仅仅可以用于 1

    加到 100 ，就是加到一千、一万、一亿(需要更改整型变量类型为长整型，否则会溢

    出) ，也就是瞬间之事。但如果用刚才的程序，显然计算机要循环一千、 一万、一亿次

    的加法运算。人脑比电脑算得快，似乎成为了现实。

    2.4 算法定义

    什么是算法呢?算法是描述解决问题的方法。算法 ( Algo付出m) 这个单词最早出

    现在被斯数学家阿勒·花刺子密在公元 825 年(相当于我们中国的唐朝时期)所写的

    《印度数字算术》中。 如今普遍认可的对算洁的定义是:

    算法是解决特定问噩求解步'的描述，在计算机中表现为指令的

    有限序列，并且4事务指令亵示一个或多个操作。

    刚才的例子我们也看到，对于给廷的问题，是可以有多种算法来解决的。

    那我就要问问你们，有没有通用的算法呀?这个问题其实很弱智，就像间有没有

    可以包治百病的药呀!

    现实世界中的问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决

    所有的问题。甚至解决一个小问题，很优秀的算法去阿三一定适合宫。

    算法定义中，提到了指令，指令能被人或机器等计算装置执行。它可以是计算机

    指令，也可以是我们平时的语言文字。

    20 第 2. 算法

    为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一

    组操作，每一个操作都完成特定的功能，这就是算法了。

    2.5 算法的特性

    算法具有五个基本特性: 输入、输出、 有穷性、确定性和可行性。

    2.5.1 输入输出

    输入和输出特性比较容易理解， 算法具有零个或多个输入。尽管对于绝大多数算

    法来说，输入参数都是必要的，但对于个别情况，如打印 hello world ! 这样的代

    码，不需要任何输入参数3 因此算法的输入可以是零个。 算法至少有一个或多个输

    出， 算法是一定需要输出的，不需要输出，你用这个算法干吗?输出的形式可以是打

    印输出，也可以是返回一个或多个值等.

    2. 5.2 有穷性

    有穷性:指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每

    一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有

    穷性。当然这里有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以

    接受的有边界飞你说你写一个算法，计算机需要算上个二十年，一定会结束，它在

    数学意义上是有穷了，可是媳妇都熬成婆了，算法的意义也不就大了。

    2. 5. 3 确定性

    确定性:算法的每一步骤都具有确定的含义， 不会出现二义性。 算法在一定条件

    下，只有一条执行路径，相同的输入只能有唯一的输出结果@算法的每个步骤被精确

    定义而无歧义。

    2. 5. 4 可行性

    可行性:算法的每一步都必须是可行的， 也就是说，每一步都能够通过执行有限

    次数完成。 可行性意味着算法可以转换为程序上机运行，并得到正确的结果。尽管在

    目前计算机界也存在那种没有实现的极为复杂的算沽， 不是说理论上不能实现， 而是

    21 l束画噩噩噩回

    因为过于复杂，我们当前的编程方法、 工具和大脑限制7这个工作，不过这都是理论

    研究领域的问题，不属于我们现在要考虑的范围。

    2.6 算法设计的要求

    刚才我们谈到了，算法不是唯一的。也就是说，同一个问题，可以有多种解决问

    题的算法。 这可能让那些常年只做有标准答案题目的同学失望了， 他们多么希望存在

    标准答案， 只有一个是正确的，把它背下来，需要的时候套用就可以了。不过话说回

    来， 尽管算法不唯一， 相对好的算法还是存在的。掌握好的算法，对我们解决问题很

    有帮助， 否则前人的智慧我们不能利用，就都得自己从头研究了。 那么什么才叫好的

    算法呢?

    嗯，没错， 有同学说，好的算法，起码要是正确的，连正确都谈不上，还谈什么

    别的要求?

    2. 6. 1 正确性

    正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。

    但是算陆的正确通常在用法上有很大的差别，大体分为以下四个层次。

    1. 算法程序没有语法错误。

    2. 算法程序对于合法的输入数据能够产生满足要求的输出结果。

    3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。

    4 . 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

    对于这四层含义，层次 1 要求最低，但是仅仅没有语法错误实在谈环上是好算

    法。 这就如同仅仅解决温饱， 不能算是生活幸福一样。 而层次 4 是最困难的，我们几

    乎不可能逐一验证所有的输入都得到正确的结果。

    因此算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明

    的。证明一个复杂算法在所4寄层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次 3 作为一个算法是否正确的标准。

    好算法还有什么特征呢?

    22 .2 章 .法

    很好，我听到了说算法容易理解。 没错， 就是它。

    2 . 6.2 可读性

    w读性: 算法设计的另一目的是为了便于阅读、 理解和交流。

    可读性高有助于人们理解算法，晦涩难愤的算法往往醋、合错误，不易被发现， 并

    且难于调试和修改。

    我在很久以前曾经看到过一个网友写的代码，他号称这程序是用史上最少代码

    实现俄罗斯方块'。 因为我自己也写过类似的小游戏程序，所以想研究一下他是如何写

    的。 由于他追求的是最少代码 这样的极致，使得他的代码真的不好理解。 也许除

    了计算机和他自己，绝大多数人是看不懂他的代码的。

    我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了

    便于他人阅读， 让人理解和交流， 自 己将来也可能阅读，如果可读性不好，时间长了

    自己都不知道写了些什么。 可读性是算法(也包括实现宫的代码)好坏很重要的标

    志

    2. 6.3 健壮性

    一个好的算法还应该能对输入数据不合法的情况做合适的处理。 比如输入的时间

    或者距离不应该是负数等。

    健壮性:当输入数据不合法时，算法也能做出相关处理， 而不是产生异常或莫名

    其妙的结果。

    2 .6.4时间效率高和存储量低

    最后，好的算法还应该具备时间效率高和存储虽低的特点。

    时间效率指的是算法的执行时间， 对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。 存储量需求指的是算法在执行过程

    中需要的最大存储空间， 主要指算法程序运行时所占用的内存或外部硬盘存储空间。

    设计算法应该尽量满足时间效率高和存储量低的需求. 在生活中，人们都希望花最少

    的钱，用最短的时间， 办最大的事，算法也是一样的思想，最好用最少的存储空间，花最少的时间，办成同样的事就是好的算法。求 100 个人的高考成绩平均分， 与求全

    省的所有考生的成绩平均分在占用时间和内存存储上是有非常大的差异的 ，我们 自然

    23 l束画噩噩噩噩噩

    是追求可以高效率和低存储量的算法来解决问题。

    综上，好的算法，应该具有正确性、 可读性、健壮性、 高效率和低存储量的特

    征。

    2.7 算法效率的度量方法

    刚才我们提到设计算法要提高敢率。 这里效率大都指算浊的执行时间。 那么我们

    如何度量一个算法的执行时间呢?

    正所谓是骤子是马，拉出来遛遛气比较容易想到的方法就是，我们通过对算法

    的数据测试，利用计算机的计时功能，来计算不同算法的效率是高还是低。

    2. 7. 1 事后统计方法

    事后统计方法:这种方法主要是通过设计好的测试程序和数据，利用计算机计时

    器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

    24

    但这种方法显然是有很大缺陆的:

    必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。 如果

    编制出来发现宫根本是很糟糕的算法，不是竹篮打水一场空吗?

    时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优

    劣。 要知道，现在的一台四核处理器的计算机， N~ 当年 286、 386、 486 等

    老爷爷辈的机器相比，在处理算法的运算速度上，是不能相提并论的 i 而

    所用的操作系统、编译器、 运行框架等软件的不同，也可以影响官们的结

    果;就算是同一台机器， CPU 使用率和内存占用情况不一样，也会造成细

    微的差异。

    算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模

    有很大关系，效率高的算法在才、的测试数据面前往往得不到体现。 比如 10

    个数字的排序，不管用什么算沽， 差异几乎是零。 而如果有一百万个随机

    数字排序，那不同算法的差异就非常大了。那么我们为了比较算沽，到底

    用多少数据来测试，这是很难判断的问题。

    基于事后统计方法有这样那样的缺陷，我们考虑不予采纳。第 2 章篝法

    2.7.2 事前分析估算方法

    我们的计算机前辈们，为了对算法的评判更科学，研究出了一种叫做事前分析估

    算的方法。

    事前分析估算方法:在计算机程序编制前，依据统计方法对算法进行估算。

    经过分析， 我们发现， 一个用高级程序语言编写的程序在计算机上运行时所消耗

    的时间取决于下列因素:

    1. 算法采用的策略、 方法。

    2 . 编译产生的代码质量。

    3 . 问题的输入规模。

    4. 机器执行指令的速度。

    第 1 条当然是算法好坏的根本，第 2 条要由软件来支持， 第 4 条要看硬件性能。

    也就是说， 抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于

    算法的好坏和问题的输入规模。 所谓问题输入规模是指输入量的多少。

    我们来看看今天刚上课时举的例子， 两种求和的算法:

    第一种算法:

    int i , su1íl ~白， n ~ 100;

    for (1, ~ _ 1 ; i < ~ n; i++)

    s um = s um + i ;

    p rin tf ( .. 曹d ， sum') ;

    第二种算法:

    int sum 声 。， n = 1 00 ;

    sum = (1 -+ h) - n2 ;

    printf C 制内， -s um) i

    1 执行 1 次 1< 1

    1 执行了 n+1 次 叫

    邮 执行 。 次~

    1 执行 1 次 货

    1 执A于一次 1

    户 执行一次 耐

    食执行一次 1

    显然，第一种算法，执行了 1+ ( n+1 ) +0+1 次=2肘3 次i 而第二种算法，是

    1+1+1=3 次。事实上两个算法的第一条和最后一条语句是一样的，所以我们关注的代

    码其实是中间的那部分，我们把循环看作一个整体， 忽略头尾循环判断的开销， 那么

    这两个算法其实就是 n 次与 1 次的差距。算法好坏显而易见。

    25 l画-四

    我们再来延伸一下上面这个例子:

    i nt 1. , j , x ~ O, sum - 0 , 0 a 100; 川执行一次 1

    ~or (i - 1; i < = n; i扑)

    for (j ~ 1 ; j < = n; jH)

    X++i 1 执行 rtXn 次警

    sum ; sum + x;

    printf ( %d飞 sum) ; ..执行一次 叮

    这个例子中， i 从 1 到 100 ，每次都要让 j 循环 100 次，而当中的 x++和 sum =

    sum + x ; 其实就是 1+2+3+…+10000 ，也就是 1002 次，所以这个算法当中，循环部

    分的代码整体需要执行 n2 (忽略循环体头尾的开销)次。显然这个算法的执行次数对

    于同样的输入规模 n = 100 ， 要多于前面两种算法，这个算法的执行时间随着 n 的增

    加也将远远多于前面两个。

    此时你会看到，测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操

    作的执行次数， 运行时间与这个计数成正比。

    我们不关心编写程序所用的程序设计语言是什么，也不关心这些程序将跑在什么

    样的计算机中，我们只关心官所实现的算法。这样，不计那些循环索引的递增和循环

    终止条件、 变童声明、打印结果等操作， 最终，在分析程序的运行时间时，最重要的

    是把程序看成是强立于程序设计语言的算法或一系列步骤。

    可以从问题描述中得到启示，同样问题的输入规模是 n ，求和算法的第一种，求

    1+2+…+n 需要一段代码运行 n 次。那么这个问题的输入规模使得操作数量是 f (n)

    = n ，显然运行 100 次的同一段代码规模是运算 10 忱的 10 倍。而第二种，无论 n 为

    多少，运行次数都为 1 ，即 f (n) ;; 1 ; 第三种，运算 100 次是运算 10 次的 100

    倍。因为它是 f (n) =耐。

    我们在分析一个算法的运行时间时，重要的是把基本操作的敬量与输入规模关联

    起来， f!P基本操作的数量必须表示成输入规模的函数(如图 2-7-1 所示) 。

    26 第 2 章'尊法

    n.n

    一-n

    不同算法的操作数量对比

    -一

    白 20

    100

    80

    60

    40

    20

    0

    算法实

    际 操作数量--1

    10 9 8 7 6 5 4 3 2

    问题输入规模n

    我仍可以这样认为，随着 n 值的越来越大，它们在时间效率上的差异也就越来越

    大。好比你们当中有些人每天都在学习，我指有用的学习，而不是只为考试的死读

    书， 每天都在进步，而另一些人，打打游戏，睡睡大觉。 人校时大家都一样， 但毕业

    时结果可能就大不一样，前者名企争抢着耍，后者求llP..7?门。

    图 2-7- 1

    函数的渐近增长 2.8

    我们现在来判断一下，两个算法 A 和 B 哪个更好。 假设两个算法的输入规模都是

    n ，算法 A 要做 2n + 3 次操作，你可以理解为先有一个 n 次的循环，执行完成后，再

    有一于n 次循环，最后有三次赋值或运算，共 2n + 3 次操作。 算法 B 要做 3n + 1 次

    操作。 你觉得它们谁更快呢?

    准确说来，答案是不一定的(如表 2-8-1 所示)。

    次搬 篝法 A (2n + 3 ) 篝法 A' (2n) 算法 B {3n +，忖 算法官( 3n)

    n = l 5 2 4 3

    n = 1 7 4 7 6

    n= 3 9 6 10 9

    n 10 23 20 31 30

    n = 100 203 200 301 300

    表 2-8-1

    当 n = 1 时，算法A 效率不如算法 B (次数比算法 B 要多一次)。 而当 n = 2 时，两者效率相同 i 当 n>2 时，算法 A 就开始优于算法 B 了，随着 n 的增加，算法 A 比

    27 l束画画画画画

    算法 B 越来越好了: (执行的次数比B 要少)。于是我们可以得出结论，算法 A 总体上

    要好过算法 B o

    此时我们给出这样的定义，输入规模 n 在没有限制的情况下，只要超过一个数值

    N ，这个函数就总是大于另一个函数，我的称函数是渐近增长的。

    画颤的渐近增长:给定两个画鼓 f (川和 9 ( n )， 如果存在-个整鼓 N ，使得对于所有的 n > N, f ( n )总是比 9 ( n )大，那么， 我们说 f ( n ,)

    的增长渐近快子 9 ( n )。

    从中我们发现，随着 n 的增大，后面的 +3 还是 +1 其实是不影响最终的算法变化

    的，例如算法 A' 与算法 B' ，所以， 我们可以忽略这些加法常数。 后面的例子，这

    样的常数被忽略的意义可能会更加明显。

    我们来看第二个例子，算法 C 是 4n+8 ，算法 D 是 2n2 + 1 (如表 2-8-2 所示) 。

    表2-8-2

    次做 篝法 C ( 4n+8) 篝法 C' (0) 法 0(202叫} 法 0' ( n2)

    n=l 12 l 3 1

    n=2 16 2 9 4

    n = 3 20 3 19 9

    n = 10 48 10 201 100

    n = 100 408 100 20001 10000

    n = 1000 4008 1000 2000001 1000000

    当 n ζ3 的时候，算法 C 要羞于算法 o (因为算法 C 次数比较多) ，但当 n > 3

    后，算法 C 的优势就越来越优于算法 。 了，到后来更是远远胜过。而当后面的常数去

    掉后，我们发现其实结果没有发生改变。 甚至我们再观察发现， 哪怕去掉与 n 相乘的

    常数，这样的结果也没发生改变，算法 c' 的次数随着 n 的增长，还是远小于算法

    0' 。 也就是说， 与最高次项相乘的常数并不重要。

    我们再来看第三个例子。算法 E 是 2n2 + 3n + 1 ，算法 F 是 2n3 + 3n + 1 (如表

    2-8-3 所示)。

    表 2-8-3

    次戴 算法 E ( 20与30+1 ) ，事法 E' ( 02) '事法 F (2n3

    +3n叫} 篝法 F' (,n3)

    n=l 6 6 1

    n=2 15 4 23 8

    n= 3 28 9 64 27

    n = 10 231 100 2031 1000

    n : lOO 20301 10 000 2000301 1000 000

    28 第 H候，摩法

    当 n=l 的时候， 算法 E 与算法 F 结果相同，但当 n>l 后， 算法 E 的优势就要开

    始优于算法 F ，随着 n 的增大，差异非常明显。通过观察发现， 最高次项的指数大

    的，函数随着 n 的增长，结果也会变得增长特别快。

    我们来看最后一个例子。算法 G 是 2肘，算法 H 是 3n + 1 ， 算法 1 是 2n2 + 3n + 1

    (如表 2-8-4 所示)。

    表 2-8-4

    次戴 篝法 G( 却2 ) .法 H (3n刊} 法川 2n2+3n叫 }

    0=1 2 4 6

    n = 2 8 7 15

    n = 5 50 16 66

    n = 10 200 31 231

    n = 100 20 000 301 20301

    D = 1,00'0 2 000000 3001 200'3001

    n = 10,000 200000000 30001 200030001

    n = 100,000 20 000 000 000 300001 20000300001

    D = 1,000,000 2 000 000 000 000 3000' 00'] 200 000 3000 001

    这组数据应该就看得很清楚。 当 n 的值越来越大时，你会发现， 3n+l 已经没法和

    2旧 的结果相比较， 最终几乎可以忽略不计。也就是说， 随着 n 值变得非常大以后，算法 G 其实已经很趋近于算法 l 。于是我们可以得到这样一个结论， 判断…个算法的

    效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)

    的阶数。

    判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的。根据刚才

    的几个样例， 我们发现，如果我们可以对比这几个算法的关键执行次数函数的渐近增

    长性，基本就可以分析出:某个算法，随着 n 的增大，宫会越来越优于另一算法，或

    者越来越羞于另一算法。这其实就是事前估算方法的理论依据， 通过算法时间复杂度

    来估算算法时间效率。

    2.9 算法时间复杂度

    2. 9. 1 算法时间复杂度定义

    在进行算法分析时， 语旬总的执行次撞 T ( n )是关子问题规模 n

    的每鼓，进而分析 T ( n )随 n 的变化情况并确定丁{川的数量

    29 l画-圈圈

    缉。 算洼的时闽复豪度.也就是算法的时闽量度，记f 乍: T ( n )

    = O(f(n))。 它褒示随间匾规模 n 的增大，算法执行时间的增长率和

    f (川的增长率相同，都伟算法的渐近时间复杂度，简称为时间复

    杂度。 其申 f ( n) 是问题规模 n 的某个函敬。

    这样用大写 O来体现算法时间复杂度的记法，我们称之为大 0 记法。

    一般情况下，随着 n 的增大， T(n)增长最慢的算法为最优算法。

    显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别

    为 O(叶 ， O(刀， O(nη。我们分别给官们取了非官方的名称， 0(1) 叫常数阶、 O(n) 叫线

    性阶、 O(n2) 叫平方阶，当然，还有其他的一些阶，我们之后会介绍。

    2.9. 2 推导大 O 阶方法

    那么如何分析一个算法的时间复杂度呢?即如何推导大 0 阶呢?我们给出了下面

    的推导方法，基本上，这也就是总结前面我们举的例子。

    推导大 O 阶:

    1. 用常鼓 1 取代运行时闺中的所有加法常颤。

    2. 在修改后的运行次搬画锺中，只保留最高阶项。

    3. 如果最高阶项存在且不是 1 ，则去除与这个项相乘的常敢。

    得到的结果就是大 O 阶。

    哈，仿佛是得到了游戏攻略一样，我们好像已经得到了一个推导算法时间复杂度

    的万能公式。可事实上，分析一个算法的时间复杂度，没有这么简单，我们还需要多

    看几个例子。

    2. 9. 3 常数阶

    首先顺序结构的时间复杂度。下面这个算法，也就是刚才的第二种算法(高斯算

    法) .为什么时间复杂度不是 0(3) .而是 O(巧。

    ìnt s um = O, n ' 100;

    5um ' '( l +n ) 惜 nZ;

    prìntf ( %d , sum) ;

    1< 执行一次1<

    执行一次

    川执行一次叮

    这个算法的运行次数函数是 f (n) =3 0 根据我们推导大 0 阶的方法，第一步就是

    把常数项 3 改为 1 。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的

    30 第 2)院算法

    时间复杂度为 0(1) 。

    另外，我们试想一下，如果这个算法当中的语句 sum= ( 1+0 ) 句12 有 10 旬，即:

    inc sum = 0 , 0 = 100 ; 执行 1 次

    sum = ( l+n) 02; 执行第 1 次

    sum = (1+n), 02; 执行第 2 次 1

    sum = (1+n) 02, ; 执行第 3 次

    sum 呈( 1+0) n 2; 执行第 4 次叮

    sum = (1+n) 禽 n2 ; 执行第 5 次

    sum = (1+n) 句2; 执J于第 6 次

    SUm = (1+0) . 咱2; 1 执待解 7 次

    sum = (1+n) 吨2; 执行第 8 次

    sum = (l+n) n2; J ' 执行第 9 : 次 V

    sum = (1+n) 句2 ; l 执行第 10 次讲

    pdotf (吨d.' ， sum) ; 执行 1 次

    事实上无论 n 为多少，上面的两段代码就是 3 次和 12 次执行的差异。这种与问

    题的大小无关 ( n 的多少) ，执行时间恒定的算法，我们称之为具有 0(1)的时间复杂

    度，又叫常数阶。

    注意: 不管这个常数是多少，我们都记作 O(町，而不能是 0(3) 、 0(12)等其他任

    何数字，这是初学者常常犯的错误。

    对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着 n 的

    变大而发生变化，所以单纯的分支结构(不包含在循环结构中) ，其时间复杂度也是

    0(1) 。

    2. 9.4 线性阶

    线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个

    特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分

    析循环结构的运行情况。

    下面这段代码，它的循环的时间复杂度为 O(n) ， 因为循环体中的代码须要执行 n

    次。

    int i;

    for (i = 0; i < n; i村)

    31 时间复杂皮为。(川的程序步骤序，向'l

    2.9 . 5 对数阶

    下面的这段代码，时间复杂度又是多少呢?

    int count = 1;

    while (count < n)

    count = count 2;

    时间复杂皮为 O( 口 的秘序步'霞序11J

    由于每次 count 乘以 2 之后，就距离 n 更近了一分。 也就是说，有多少个 2 相乘

    后大于 n ，则会退出循环。 由 2X=n 得到 x=bg2n 。 所以这个循环的时间复杂度为

    o (k>gn) 。

    2.9. 6 平方阶

    下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为

    O(n) 。

    i nt i , j ;

    for (i - 0; i < n; i++)

    for ( j - 0 ; j < n ; j++ )

    舍时间..成为。t 川的程序步穰序列

    而对于外层的循环，不过是内部这个时间复杂度为 O(n)的语旬，再循环 n 次。 所

    以这段代码的时间复杂度为 O(n2) .

    如果外循环的循环次数改为了 矶 时间复杂度就变为 O(m Xn) 。

    int i , j;

    for(i = 0 ; í < m; i++)

    32 第 2 章算法

    for (j = 0; j < n; j++)

    1 时阅复杂成为 O(川的程序步骤序列 1

    所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行

    的次数。

    那么下面这个循环嵌套，它的时间复杂度是多少呢?

    int i , j:

    fór (i 冒 0; i < n; i++)

    for (j = i; j < n ; j++) 1 注意 j = i 而不是 o 1

    时间复杂度为 O(川的程序步骤序列

    由于当 i= 0 时，内循环执行了 n 次，当 i = 1 时，执行了 n-1 次，……当 i=n一1

    时，执行了 1 次。所以总的执行次数为:

    n(n+1) n2

    n + (n - 1) + (n - 2) +…+ 1 = ~J=τ+E

    用我们推导大 0 阶的方法，第一条，没有加法常数不予考虑j 第二条，只保留最

    高阶项，因此保留时2; 第三条，去除这个项相乘的常数，也就是去除 12 ，最终这

    段代码的时间复杂度为 O(n2) 。

    从这个例子，我们也可以得到一个经验，其实理解大 0 推导不算难，难的是对数

    列的一些相关运算，这更多的是考察你的数学知识和能力，所以想考研的朋友，要想

    在求算法时间复杂度这里不失分，可能需要强化你的数学，特别是数列方面的知识和

    解题能力。

    我们继续看例子，对于方法调用的时间复杂度又如何分析。

    int i , j;

    for (i = 0 ; 丰< n; i++)

    function (i) ;

    33 上面这段代码调用一个函数 function。

    void fun_ ction (int count)

    print (count) ;

    函数体是打印这个参数。 其实这很好理解， func?on 函数的时间复杂度是 0(1) 。

    所以整体的时间复杂度为 O(n) .

    假如 func?on 是下面这样的:

    void function (int count)

    int j;

    for (j = count; j < n; j++)

    时间复杂度为 。(川 的程序步骤序列 1

    事实上，这和刚才举的例子是一样的，只不过把嵌在内循环放到了函数中，所以

    最终的时间复杂度为 0(n2) 。

    34

    下面这段相对复杂的语句:

    n++;

    function (n) ;

    int i , j;

    for (i = 0; i < n; i++)

    function (i);

    for(i = 0; i < n; i t+)

    for (j = i;j < n; j++)

    执行次欲为 1

    户执行次.为 n

    执行次数为 n' .

    执行次数为 n(n+1)2;

    时间复杂皮为 。{川 的程序步骤序1') 第 2 章算法

    它的执行次数J(n}=1+n+n2+主但土旦=Zd+Zn +1 ， 根据推导大 0 阶的方法， 2 2 2

    最终这段代码的时间复杂度也是 0(n2) 。

    2.10 常见的时间复杂度

    常见的时问复杂度如表 2-10-1 所示。

    褒 2-才 0-1

    执行次搬函撇 阶 非正式术语

    12 。(1) 常费生阶

    2n+3 。(n) 线性阶

    3n2 +2n+1 。(n1) 千方阶

    5Io~n+20 。(Iogn) 对数阶

    2.n+3nlog2n+19 。(nlogn) nlogn 阶

    6n3

    +202+3n+4 。(11) 立方阶

    2n

    0(2) 指疆生阶

    常用的时间复杂度所耗费的时间从小到大依次是:

    0(1) < O(logn) < O(n) < O(nlogn) < 0(n2) < 0(n3) < 0(2 ) < O(n!) < O(n)

    我们前面已经谈到了 。(1)常数阶、 。(bgn)对数阶、 O(n)线'性阶、 0(n2)平方阶等，至于 O(nlogn)我们将会在今后的课程中介绍，而像 O(明，过大的 n 都会使得结果变

    得不现实。同样指数阶 0(2n)和阶乘阶 O(n!)等除非是很小的 n 值，否则哪怕 n 只是

    100 ，都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度，一般我们都不

    去讨论宫。

    2.11 最坏情况与平均情况

    你早晨上班出门后突然想起来，孚机忘记带了，这年头，钥匙、钱包、 孚机三大

    件，出门哪样也不能少呀。于是回家找。打开门一看，孚机就在门口玄关的台子上，原来是出门穿鞋时忘记拿了。这当然是比较好，基本没花什么时间寻找。可如果不是

    放在那里，你就得进去到处找，找完客厅找卧室、 找完卧室找厨房、 找完厨房找卫生

    间，就是找不到，时间一分一秒的过去，你突然想起来，可以用家里座机打一下手

    35 阳回国

    机，听着手机铃声来找呀，真是笨。终于找到了，在床上枕头下面。你再去上班，迟

    到 ......