（第二版).张乃孝，包含了大量的经典算法，而且简单易懂，很容易上手，值得一读。第8章排序。介绍了10种排序方法,讨论了这些算法的复杂性及稳定性第9章图。介绍了图的基本概念和抽象数据类型,讨论了图的周游方法和图的相邻矩阵及邻接表的表示方法,重点讲解求图的最小生威树(林〕和求图中结点间最燈路径等算法,最后介绍了两个典型的应用第10章算法分析与设计。主要给读者概括地介绍算法的分析和设计的主要技术,以便于将本书所学到的算法归类整理,达到开阔思路、提高观点、增强兴趣的目的读者对象与使用方法本书可以作为各种类型大学的本科和专科的“数据结构”、“数据结构与算法”或者“算法与数据结构”等课程的教材。本书在編写中注意到知识模块的独立性和相关性,不同专业的学生可以根据不同的需要进行组合使用。基础部分1第1章绪论(除去1.34、I.4.2和1.4.3)2第2章线性表(除去2.4、2.5和2.6)。3第4章栈与队列(除去4.3和4.6)。4第5章二叉树与树(除去545.5、5.6和57)。5第6章集合与字典(除去62.1和6.5.4)。6第8章排序(除去8.2.3、8.24、8,3.2、8.5和8.6.2)7第9章图(除去9.5.2、9.6,和97)提高部分8应用实例:分散在24、43、4.65.4、9.6和97等节中。9增强基础:学习在基础部分各章中被除去的那些(有关文件的内容除外)肉容0第3章字符串。11第7章高级字典结构。任选部分12文件内容:分散在1.3.4(外存数据的组织)654(散列文件)76(素引义件)和862(外排序)。13第10章算法分析与设计。除去基础部分中的内容应该顺序学习以外,其他部分均时以灵活安排。著者建议:◆对于生物、化学和医农等专业的本科学生的相关课,可以主要学习1~5的内容,和68中部分内容◆对于一般理工科的本科学生,可以主要学习1~9的内容,和10-11中部分内容。◆对于信息或计算机(或者与它们要求相似的〉专业的本科学生,可以主要学丬1~11的内容,和12~13中部分内谷此外,在使用本书时,请读者注意以下几点语言考虑到目前囡内“计算概论”(或“基本程序设计”)课程的教学情况,同时也因为用C语描述算法十分有效,分析使用C语言描述的算法又比较直观,因此本书釆用C语言伫为描述语言,并且假设读者都具备了这方面的基础知识索引为了便于使用,对于比较重要的概念都鋰立了对应的索引,读者可以利用本书最后的索引杏阅。习题学习算法与数据结构必须理论与实践相结合,所以在理解书本知识的同时,应该尽可能做更多的习题。在本书的每章最后,都配备了比较丰富的习题,根据不同的目的,分成复习题、算法题和应用(上机)题三种。这些题目的参考答案可以在本书参考文献[3]中找到。对于初学者而言,最难完成的是算法题。设计算法的关键在于设计的思路,不同的思路产生出不同的算法。读者通过自己的学习、思考和实践,就能从中体会到算法与数据结构的真谛,提高自记分析问题和解决问题的能力学时根据著者的经验,对于比较熟悉C语言的对象,讲授全部内谷需要6070学时感谢此书能够顺利与读者见闻,首先应该感谢的是长期支持和鼓励著者从事教学和研究的北京大学(特别是北大的数学学院和计算机系)。能够在北大这片沃土上,实践著者“追求真理、探索人生”的理想是著者今生的最大满足。为此,著者数小年来孜孜以求,从来不敢懈怠;平平淡淡,确也无怨无悔。借此机会略表感谢与怀念之情。感谢在近二十多年中,与著者合作编写教材的许多老师(按照时间顺序):唐世渭、杨冬清、刘主明、许卓群、邵维忠、孙玉方、裘宗燕、韩玉真、陈光和刘筠等。在与他们的合作过程中,著者不仅仅学到许多的知识,同时也学到了许多为人的道埋。其屮裘宗燕教授还阅读了本书的大部分修改稿,提出许多中肯的意见。衷心感谢曾经和将要使用本教材的老师同学和所有读者,你们的每条宝贵意见都是对著者最大的支持与鼓励。上分感谢高等教育出版社计算机分社的刘建元社长和刘茜、康兆华、耿芳以及所有相关的工作人员,著者的几本主要教材,都是在他们的攴持下得以顺利出版。非常感谢著者所有的亲人,没有他们的理解、支持和关爱,著者很难能够平安度过这坎坷的前半生。特别要感谢的是赵素兰女土,在近四十年的共同生活中,是她的无私奉献构筑了如今幸福美满的家庭。最后,真诚地期望这个世界变得更加美好;衷心地祝愿我们的子孙后代生活得更加快乐。张乃孝znx@pku.edu.cn005年6月11日目录2.3链接表p司申日●自■p甲幽·■(391绪论2.3.1单链表表示(39)l从问题到程序……(1232单链表上运算的实现……(411.1.1问题分析与抽象……(2)2.3.3分析与比较■d4b●(441.1.2程序的设计与实现(3)2.3.4单链表的改进和扩充(45)1.2抽象数据类型…(62.4应用举例(48)2.1什么是抽象数据类型24.1 Josephus问题(48)1.2.2意义与作用……………(7)2.4.2采用顺序表模拟(49)1.2.3举例………(7)2.4.3采用循环链表模拟(50)3数据结构…(8)2.5矩阵53)1.3.1什么是数据结构……(9)2.5.1矩阵的顺序表示…………(53)1.3.2数据结构的分类…2.5.2稀疏矩阵的表示方法………(54)1.3.3结点与结构(12)2.6广义表与动态存储管理……57.3.4外存数据的组织(132.6.1广义表……………………………(58)1.4算法(16)2.6.2结点的动态分配与回收…60.4.1升么是算法…………(162.6.3废料收集与存储压缩…(64)1,4.2算法的设计(17)小结(65)1.4.3算法的精化……………(18)习题1.4.4算法的分析……(21)小结●●■●罪看■●………(25)3字符串……………………………………(69)习题(27)3.1字符串及其抽象数据类型……(69)31.1基本概念(69)2线性表bb■●咖d自■自我個◆………………(29)3.1.2抽象数据类型………………(70)2.1基本概念与抽象数据类型(29)3.2字符串的实现(71)2.1.1基本概念……(29)2.1顺序表示………………………(71)2.1.2抽象数据类型……………(30)3.2.2链接表示…………(72)2.2顺序表示(31)3.3模式匹配………(75)2.2.1存储结构(31)3.3.1朴素的模式匹配…………(75)2.2.2运算的实现(33)33.2无回溯的模式匹配(77)2.2.3分析与评价……………………(36)小绪即4■中d●●甲2.24顺序表空间的扩展……………(38)习题(83)目录5.4.2哈夫曼树及其应用(1444栈与队列(85)5.5树及其抽象数据类型…………(1514.1栈及其抽象数据类型(85)5.5.1基本概念………………………(151)4.1.1基本概念(85)2抽象数据类型152)4.1.2抽象数据类型………………(86)5.5.3树的周游备■●◆…·(153)4.2栈的实现(86)6树的实现(156)4.2.1顺序表示……………(86)5.6.1父指针表示法……………(156)4.2.2链接表示………(89)5.6.2子表表示法甲旷中由血。斷■申甲I(158)4.3栈的应用………(9156.3长子一兄弟表示法(1604.3.1栈与递归(92)5.6.4树的其他表示法(161)4.3.2迷宫问题………………(96)57树林◆■●p●带由口4■口山■bp■mmd●………(162)表达式计算(100)5.7.1树林的周游……(162)队列及其抽象数据类型102)5.7.2树林的存储表示………………(162)4.4.]基本概念(102)57.3树林与二叉树的转换……(1634.4.2抽象数据类型……(102)小结……………………(165)4.5队列的实现(103)习题甲早◆日看p·甲◆自命■●日■◆p4·■p电血(166)4.5.]顺序表示……(1034.5.2链接表示…(106)6集合与字典…(169)6队列的应用(109)6.]集合及其抽象数据类型……………(169)小结………………(113)6.1.1基本概念…(169)习题………………………………(114)6.1.2主要运算…………………………(170)6.1.3抽象数据类型……………(171)5二叉树与树(117)6.2集合的实现……………………(172)5叉树及其抽象数据类型…………(117)6.2.1集合的位向量表示…………(172)基本概念●鲁p即■曾■D■■■……(117)62.2集合的单链表表示(1775.1.2主要性质……………………(120)6.3字典及其抽象数据类型…(180)51.3抽象数据类型(122)6.3.1基本概念……(180)2二:叉树的周游……………………(123)6.3.2抽象效据类型………(181)5.2.1什么是周游………(123)64字典的顺序表示…………(181)52.2周游的分类……(124)64.存储结构……………………(181)52.3一个例子………………………(125)6.4.2算法的实现……………………(182)52.4周游的抽象算法…(126)64.3有序顺序表与二分法检索……(183)5.3-义树的实现…………………(131)6.5字典的散列表示……………………(186)5.3.1顺序表示………(131)6.5.1基本概念……………………(186)5.3.2链接表示(1336.5.2散列函数………(187)线索二叉树…………………(135)6.5.3碰撞的处理………………(189)54二叉树的应用(139)6.5.4散列文件………………(195)54.1堆与优先队列(139)小结……………(197)目录习题……(198)8.3.2堆排序(255)84交换排序(259)7高级字典结构(200)84.1起泡排序1卓看(259)7.1字典与索引……………………(200)8.4.2快速排序…(261)7.1.1字典的索引200)8.5分配排序………………………(263)7.1.2索引的抽象…(201)8.5.1概述(264)7.2字符树…………(202)8.5.2基数排序…(264)7.2.1双链树表示…(203)86归并排序(267)7.2.2多链表示……203)86.1内排序………………………(267)7.3二义排序树…(205)8.6.2外排序…(270)7.3.1二叉排序树……………(205)小结冒督●■看号甲口甲看(276)7.3.2二叉排序树的检索(206)习题278)叉排序树的插人和构造(206)7.3.4二义排序树的删除209)9图………………………………………(280)7.4最佳二叉排序树……………(211)9.1基本概念及其抽象数据类型…(280)7.4.1基本概念……(211)91.1基本概念(280)7.4.2等概率的检索(213)9.1.2抽象数据类型(283)7.4.3不等概的情况………(214)9.2图的周游…(285)7.5平衡二叉排序树(220)9.2.1深度优先周游285)7.5.1基本概念…………………(220)9.2.2广度优先周游………………(287)7.5.2调整平衡的模式…(221)9.3存储表示…(288)7.5.3实现………………………(226)9.3.1邻接矩阵表示法……………(289)7.6索引文件(23293.2邻接表表示法……(2917.6.1多分树(232)9.3.3两种表示的比较(292)7.6.2B树(234)94最小生成树(2937.6.3B‘树(239)94.1最小生成树及其性质…………(294小结(242)9.4.2最小牛成树的构造……(295)习题…………………(243)9.5最短路径………………………(300)9.5.1 Dijkstra算法…(301)8排序…………………………………………(245)9.5.2 Floyd算法(34)8.1基本概念(245)96拓扑排序(307)8.2插人排序…………………………………(246)9.6.1AOV网…(3078.21直接插入排序……………(246)9.6.2拓扑排序……(308)8.22分法插人排序……(249)9.7关键路径……(311)8.2.3表插人排序(251)9.7.1AOE网…(31)8.24ShCl排序……………(252)9.7.2关键路径……(312)8.3选择排序…(254)小结(3168.31直接选择排序(254习题(3]7)4目录2.5分枝界限法与0/1背包10箅法分析与设计………(320)问题(338)10.1算法分析技术320)小结(342)10.1.1空间代价分析(320)习题(343)10.1.2时间代价分析(322)10.2算法设计技术326)参考文献(345)l0.2、1分治法…326)索引346)10.2.2贪心法………(327)算法清单(355)10.2.3动态规划法……(30)后记………………(358)10.24回溯法(335)1绪论“算法与数据结构”是学习计算机科学的基础课程。其主要目的是使读者较全面地理解算法和数据结构的概念、掌握应用数据结构与算法的主要原理和方法、比较不同数据结构和算法的特点。通过学习和实践,使学生能够提高使用计算机解决实际问题的能力。学好这门课对于所有研究或使用计算机的读者都是很有裨益的。本章首先通过一个实例讲解使用计算机处理实际问题的过程,然后对一些最基本、最重要的概念分别展开讨论。本章重点是:理解从问题到程序的主要过程;体会数据结构、算法和抽象数据类型在问题求解过程中的作用;了解数据结构的主要概念和分类方法;了解算法的概念和主要设计、分析方法。通过本章学习,使读者对全书有个整体的鸟瞰,以使读者在后继各章学习时,能更好理解它们的地位和相互关系1.1从问题到程序用计算机实现问题求解,实质上就是在计算机中建立一个解决问题的模型。用来表示间题或处理问题的模型可以有不同的抽象形式:容易被人理解但不太严格的需求模型;比较抽象但很精确的数学模型;容易被计算机理解或执行的实现模型程序是使用程序设计语言精确描述的实现模型,它是问题求解的一个可以在计算机上运行的模型。程序中描述的数据用来表示问题中涉及的对象,程序中描述的过程表示了对于数据的处理算法;通过接受实际问题的输人,经过程序的运行,便可以得到实际问题的一个解。为一个实际问题建立一个正确的求解程序,通常可以分成以下几个阶段分析阶段。这阶段的任务,首先是弄清用户的需求是什么,设计者根据它进行深入分析,使用规范说明语言(或数学语言等工县)给出系统的需求模型(或数学卩绪模型)。设计阶段。这阶段的饪务是建立求解系统的实现模型,重点是算法的设计和数据结构的设计。对于大型的复杂的系统,这一阶段往往还包括抽象数据类型或者模块的设计。一般而言,设计过程需要从粗到细,经过多次精化才能完成编码阶段。它的主要任务是采用适当的程序设计语言(C语言、C++语言或是Jaa语言等)把设计阶段的成果,编写成可执行的程序。调试和维护。其仼务包括使用足够的例子调试编写的程序,发现和排除程序代码中的错误;在计算机上执行程序,获得问题的解;也包括在系统投入运行后,解决在使用过程中发现的隐含错误和根据使用中提出的要求进行必要的维护和完显然,与本课程关系最为密切的是设计阶段,但由于设计阶段介于分析和编码这两个阶段之间,因此讨论中也需要牵涉到它们。下而通过一个实例,具体展开问题求解的主要过程,重点讨论问题的分析和算法与数据结构的设计等11.1问题分析与抽象为了能正确地解决问题,必须首先深刻地理解需要解决的问题。只有在深刻地认以了这个问题以后,才能着手确定这个问题的解决方法。信号灯问题考虑一个多叉路口(见图1.1),在这个路中,共有五条道路相交,其中C和E是单行线,其他为双行线。提出的任务是:为这个路口设计一个安仝有效的交通信号灯的管理系统分析为了完成上述任务,首先需要研究一下这个路口所有车辆的行驶路线,找出你在的冲突。这可以归结为对车辆的可能行驶方向作某种分组,分组的结果满足:任图1.1·个交义路口的模型个组中各个方向行驶的车辆可以同时安全行驶(不发生碰撞)。显然,对这个问题存在许多不同分组方案,其中最简单的方案就是把每个可能的行驶路线分为一组。例如:根据这个路冂的实际清况,可以确定13个可能通行方向:A→B,A→+C,A→D,B→+A,B→C,B→D,D→A,)→B,D→C,E→→A,E→→B,E→C,E→D。如果把它们分在13个组中,每组只包含种通行方向,当然非常安全。但是,这种方案是不会在实际中采用的。因为如果分绀越少,可以同时行驶的车辆也就越多,路口的运行效率就越高。我们需要的就是如何能够找到个比较高效的方案。