c算法 第1卷:基础、数据结构、排序和搜索

所需积分/C币:10 2016-05-12 17:12:16 51.7MB PDF
8
收藏 收藏
举报

经典算法基础书籍,罗伯特两卷本第一卷 涉及算法基础、数据结构、排序和搜索
前 本书旨在综述当今程序员使用的最重要的计算机算法,同时为越来越多需要学习这些 算法的人讲解基本技术。本书可以用作学习计算机科学的第二、第三或第四门课程的教科 书,供那些掌握了基本编程技能并熟悉了计算机系统,但还未学习计算机科学或着计算机 应用的高阶领域专业课程的学生来选修。本书也可以作为从事计算机系统或应用程序开发 的自学教材或参考书,因为它包含有用算法的实现以及这些算法性能特征的详细信息。本 书讲解全面,也是一本合适的算法导论书。 我全部重写了新版内容,添加了1000多个新练习、100多幅新图以及许多新程序。我还 为所有插图和程序添加了详细的注释。这些新材料既包含了一些新主题,还对许多经典算法 提供了更全面的解释。整本书还添加了一个重点内容,即抽象数据类型,使得这些程序更加 通用、更适应于现代面向对象编程环境。阅读过本书旧版的读者在新版中可以学到大量新知 识:所有读者都可以阅读到丰富的教学材料,通过它们可以快速掌握一些重要概念。 由于添加了大量新材料,所以将新版分为二卷,每一卷都与旧版篇幅相当,本书为第一卷 这-卷包括基本概念、数据结构、排序算法以及搜索算法;第二卷在本书基本抽象和方法的基 础上讲解高级算法和应用。在新版本中,几乎所有基础知识和数据结构的材料都是新的。 本书所面向的对象并不仅仅是程序员和计算机专业的学生。几乎每个计算机的使用者 都希望计算机能够进行得更快或者能够解决更大的问题。本书中的算法代表过去50年的知 识发展水平,针对各种不同的应用,在高效使用计算机中不可或缺。从物理学上的N体模 拟(N- body simulation)问题到分子生物学中的基因序列问题,这里描述的基本方法已成为 科学研究中的核心要素:而且从数据库系统到因特网搜索引擎,它们已成为现代软件系统 的核心部分。随着计算机的应用范围越来越广泛,本书介绍的一些基本方法的影响也随之 增大。对于那些有志于掌握这些基本算法,并且灵巧地利用它们作为将来所从事的计算机 应用的基本工具的学生和专业人员,本书的目标就是作为他们实现理想的宝贵资源。 讨论范围 本书分16章,共4部分:基础知识、数据结构、排序和搜索。这里的描述是为了让读 者对尽可能广泛的基本算法的基本性质有一个大概的了解。这里描述了从二项式队列到 patricia tre等精巧方法,它们都与计算机科学核心中的基本范例相关。第二卷包括另外4 部分,涉及串、几何体、图以及高级主题。我编撰这两本书的日的是,从不同的领域将这 些基本方法汇集起来,为读者提供已知的通过计算机解决问题的最佳方法。 如果你选修过计算机学科中的一到两门预备课程,或者有过与之相当的编程经验,则 C算法(第一卷基础、数据结构、排序和搜索)(第三版) 会从本书受益最大。这些选修课程可以是一门高级编程语言,如C、Java或C++,也可以 是讲述编程系统基本概念的课程。因而,本书面向那些熟悉现代编程语言以及现代计算机 系统基本特征的读者。对正文中讲解的知识,读者通过参考文献可以进一步详细了解 大部分支撑本书分析结果的数学内容都是独立的(或者作为超出了本书的讨论范围而 标记出来),因此,学习本书需要很少的数学预备知识,当然,深厚的数学造诣对学习过程 无疑是有益的 如何在课程中使用 根据老师的教学方法上的差异以及学生的预备知识的多寡,讲授本书的方式可以灵活 多变。这里描述的算法多年来得到了广泛的应用,而且代表着熟练程序员以及计算机科学 学生的核心知识面。本书包含了很多的数据结构方面的基本内容,因此,可以用于数据结 构课程的教学。本书也对算法进行了相当详细的讨论,并提供了足够的高级内容,因此, 也可以用于算法课程的教学。一些老师可能希望重点讲解实现以及实际应用上的间题,另 外一些老师可能希望重点讨论分析和理论概念。 在本书的主页上,可以找到用于授课的整套幻灯片、示例编程作业布置、学生使用的 交互练习以及其他一些材料 数据结构和算法的基本课程可以重点讲解第二部分中的基本数据结构以及第三、四部 分中在实现里的运用。算法设计和分析课程可以重点讲解第一部分和第5章中的基本内容, 然后学习第三部分和第四部分中的算法,学习这些算法是如何达到好的渐近性能的。软件 工程课程可以忽略数学和高级算法内容,重点讲解如何在大型程序或系统中集成书中提供 的实现。算法课程对于所有这些内容,可以采取综述、简介的方式来讲授。 近几年,全球很多院校使用本书的旧版本作为计算机科学的第二或第三门课程教材, 同时也作为其他课程的辅助阅读内容。在普林斯顿大学,我们的教学经验是,本书所囊括 的内容可以作为主修课的计算机科学导论,在算法分析、系统编程以及理论计算机科学等 后续课程上可以进一步深入,同时,还为其他学科中不断增长的学生群体提供丰富的技能, 他们可以将这些技术立即完美地付之于实践。 书中的练习分为几类(在新版本中,大部分练习为新添加的)。有些练习是为了测试读 者对课文内容的理解,只是要求读者完成一个例子,或者应用正文中描述的概念。有些练 习包括实现代码和算法的综合,或者通过试验研究比较算法的变种,并学习其性质。还有 些练习提供了许多重要而详细的信息,这些信息不适合于在正文中讲解。每位读者阅读 和思考这些练习都会有收获。 算法的实用 任何希望更高效使用计算机的人都可以将本书作为参考书,或者用于自学。具有编程 经验的人在全书各章节都可以找到特定主题的有用信息。虽然在某些情况下,某一章中的 前言 算法可能借用前面章节的方法,但在很大程度上,读者可以独立阅读各章节 本书的目标就是学习那些可能运用于实践的算法。它提供了足够的信息,读者可以胸 有成竹地运行、调试程序,并且获得有效算法来解决实际问题,或者为应用程序提供功能。 书中提供了所讨论方法的完整实现代码,描述了一系列相关联的例程中的运算。因为我们 提供的是实际代码,而不是伪码,所以这些程序可以直接运用于实践。在本书的主页可以 下载所有程序源代码。 实际上,在整本书中,为每个算法都展示了实际应用,并且配制了相关的数百幅说明 图示。通过这种直观的演示说明,许多算法变得浅显易懂 书中详细讨论了这些算法的特征和它们可以发挥作用的场合。算法分析和理论计算机 科学的联系虽然不是重点内容,但也在本书中安排了适当的篇幅进行讲解。适当的时候会 引用试验和分析结论,来说明优先选择某些算法的原因。必要的时候,书中还会描述所讨 论的实际算法与纯理论结论之间的关系。本书自始至终地综合、归纳和探讨了算法及其实 现的性能特征的专门信息 编程语言 所有实现都使用C话言写成。任何语言都有优缺点,我们选用C语言,是因为它得到 了广泛应用,而且提供了实现所需要的功能。这些程序很容易被转换成其他现代编程语言, 因为其中使用的C独特结构很少。我们尽可能使用标准C约定,但这本书不是一本学习C 语青编程的参考书 新版本中添加了许多新程序,同时重写了许多旧程序,主要是为了让它们更容易用作 抽象数据类型实现。针对这些程序,程序的大量的比较测试讨论贯穿于全书中。 本书的旧版本提供了用 Pascal、C++和 Modula-3写成的一些基本程序。这些程序在网 站上可以下载使用;新程序的代码以及用新语言(如Java)编写的代码也作了适当的增补。 本书的目的是以尽可能简单、直接的形式讲解算法。尽可能保持一致的风格,让相似 的程序看起来比较统一。对于本书中的许多算法,不管用何种语言写成,它们均保持相似 性。举一个突出的例子,快速排序( quicksort)能进行快速排序,不管是用 algol-60、 Basic、 Fortran、 Smalltalk Ada、 Pascal、C、 PostScript、Java,还是用其他编程语言和环境来实 现,它仍被认为是一种高效的排序方法。 我们尽量提供雅致、紧凑、可移植的实现,但要考虑到它们的效率问题,因此,我们 尽量在编制实现的各个阶段留意代码的性能特征。第1章按这种方式为算法开发了高效的C 实现,列举了一个详细的示例,并且为余下各章节的学习打好基础。 致谢 很多旧版读者为我提供了有用的反馈。特别是,普林斯顿大学和布朗大学的数百名学 生多年使用本书的初稿,并提出了宝贵意见。特别感谢Trna和 Tom freeman对初版的付梓 C算法(第一卷基础、数据结构、排序和搜索)(第三版) 给予的帮助;感谢 Janet Incerpi在利用早期原始数字化计算机排版硬件和软件生成初版样稿 时付出的创造性劳动和智慧;感谢 Marc brown参与算法可视化表示的研究工作,使得本书 能配备如此多的精美插图;感谢 Dave hanson尽心解答所有与C语言有关的问题。还要感 谢为本书的不同版本提供详细评论的诸多读者,他们有: Guy alms, Jon Bentley, Marc Brown, Jay Gischer, Allan Heydon, Kennedy Lemke, Udi Manber, Dana Richards, John Reif, M Rosenfeld, Ste phen Seidman, Michael Quinn #l Willian Wardo 为了新版本的问世,我有幸与 Addison- Wesley出版社的 Peter gordon和 Debbie lafferty 合作,从本书的·般更新到大量重写,他们始终予以耐心的指导。也很荣幸能与 Addison- Wesley出版社的其他几位专业人土合作。根据这一项目的高定位,对于他们来讲, 这本书的编辑工作意味着不同寻常的挑战,我由衷敬佩他们坚韧不拔的精神。 编写此书时,我喜获两位新导师,我尤其要表达对他们的感激之情。第一位是Stev Summit,他从技术上仔细审查了手稿的早期版本,并提出了数千条详细意见,尤其是对程 序提出的宝贵意见。 Steve准确理解了我为读者提供雅致、有效以及高效实现的意图,他的 意见不仅帮助我在实现代码间保持一致性,而且帮助我切实改进了许多程序。第二位是Lyn Dupre,他也对原稿提出了数千条详细意见,它们的宝贵价值不仅在于帮助我更正和避免语 法上的错误,而且更重要的是,帮助我找到一种致、连贯的编写风格,这有助于组织书 中的大量技术材料。能有幸聆听 Steve和Lyn的教诲,实在是荣幸之至,他们的付出对本书 的顺利编撰至关重要。 我在这里所写的很多内容来自于我在斯坦福大学的导师 Don Knuth的讲授和著作。虽 然Don对这本书没有直接影响,但在本书可以处处感觉到他的影响,凼为正是他将算法的 研究置于科学的殿堂之中,从而使得编写这样的书成为可能。我的朋友和同事 Philippe Flajolet在算法分析发展成一门成熟研究科学的过程中是主力,他对本书也有相似的影响 深深感谢普林斯顿大学、布朗大学以及法国国家信息与自动化研究院( INRIA)的支 持,我在这些地方完成了本书的大部分工作。也感谢美国国防部防御分析研究所(The nstitute for Defense Analyses)和 Xerox Palo alto研究中心的支持,我在访问这些单位期 间完成了本1的部分工作。本书的许多部分与美国国家科学基金会和海军研究办公室的大 力支持的研究有关。最后,我要感谢 Bil Bowen、 Aaron lemonick和 Neil rudenstine在普 林斯顿大学建立相关学术环境中给予的支持,使我在完成其他工作职责之外,仍然能够在 这样的学术环境屮准备本书的撰写。 Robert sedgewick 法国 Marly-le-Roi市,1983年2月 美国新泽西州普林斯顿,1990年1月 美国罗得岛州詹姆斯敦,1997年8月 关于书中练习 对书中练习进行分类充满了不确定因素,因为读者的知识水平和经验参差不齐。尽管如此, 提供一定的指导是适宜的,所以许多练习带有4种符号中的种,帮助读者决定如何使用这些 练习 测试对知识理解程度的练习标有个空心三角形,如下所示 D57.把 EASY QUESTION键入个初始为空的“项式队列,写出得到的二项式队列 最通常的情况是,这些练习与正文中的示例直接相关。它们没有特殊的难度,但完成这些 练习后,可以帮助你进一步掌握正文中没能理解的结论或概念。 为正文中的知识点添加了新的、值得进一步思考的信息时,这样的练刈标有一个空心圆, 如下所示: ○20.编一个程序,使用分离链在大小为M100的表中插入N个随机整数,然后求最短表 与最长表的长度,分别取N=103,10,10和10 这种练小鼓励你思考一些与正文中的材料有关的重要概念,或者回答阅读正文时可能碰到 的问题。即使你没有时间来完成这些练习,这些练习可能也值得阅读。 对读者来说具有挑战性的练习标有个黑圆点,如下所示 ●46.设实现归并排序时在随机位置分解文件,而不是在准确的中间位置分解。通过这种方 法来排序N个元素,平均需要多少次比较? 这类练习叮能需要相当多的时间来完成,根据读者的经验多少而有所不同。一般而言,最 佳途径是分成儿个不同的阶段来完成。 还有少数相当难的练习(与其他大部分练习相比而言),它们标有两个黑色圆点,如下 ●●29.证明由N个随机位串牛成的te高度约为2lgN 这些练习与研究文献中解决的问题相似,但根据本书提供的材料,可以从尝试解决文献 屮的那些问题得到乐趣(也许能完美解决) 根据读者的编程能力和数学背景,这些注释定位适中。那些需要专业编程知识和数学分析 的练习是不证自明的。鼓励所有读者通过实现算法来测试对它们的理解。还有一种类似于此的 练习对于熟练程序员或学过编程课程的学生来说简单易懂,但对于未曾从事过编程的人来说, 叮能工作量相当大 23.修玫程序14,生成介于0到N-1之间的随机整数对,而不是从标准输入读取,同时 直循环到N1次集合并运算执行完成。分别在N=103,10,103以及10的情况下运行此程序, 而且打印出对应每个N值生成的边总数。 同理,我也建议所有读者认真解答证明算法性质的分析基础知识的练习。对于那些离散数 C算法(第一卷基础、数据结构、排序和搜索)(第三版) 学专业的科学家或学生来说,这些练习并不难,但对于不精通数学分析的人来说,这些练习可 能需要较大的工作量: 13.由加权快速集合并算法生成的具有2个节点的最坏情况树中,计算从某节点到根的平 均距离。 读者需要消化吸收的练习太多,我希望在这本书中提供足够的练习,激励读者对感兴趣的 知识有更宽广的理解,而不只是对正文内容走马观花 H录 第部分基础知识 第1章导论… 如s自◆中◆··●·◆·“·自◆··号·4qp日甲p日日■··自········吾号●◆·命晋;音日◆·4◆;··最 1.1算法 电◆◆·命●·合●■吾自●●D鲁即号●甲卓日日日p·自自咖白b白·自目·D●●◆◆●●自●··●.·身● 12问题示例:连通性( connectivity) 练习 4—命命◆s自口昏■■阝罪即『罪●银ψ中ψ申事◆自●····●自t·命··;4自自自日音自日·自日●4日··日··●■··◆ 3并集一查找算法 练习…………………………………17 14展望 ……………………………18 练习 19 15小结……… 19 第2章算法分析原理 21实现与试验分析 练习 ◆●●■曾●罪●●即号罪甲甲●即甲即q日·争·咖ψ咖自电中白中咖咖q··昏辛号单语自白日自自·备幽自命 22算法分析…… ●即◆曾·◆●· ……a…“a■…···25 练习 单●■命鼻·■ 23函数增长… 练习 ● 240记号………32 练习 ψ。■●自ψ●ψpD●●嵋●●ψ◆·咖命◆噜●b·命ψ·◆自命ψ●鲁昌●自凸▲自备山昌■b■鲁晶■自自■备鲁语鲁p鲁音■·●音D口■■。晕■●即导■冒■罪冒即· 2基本递推式 …36 练习 4●D■日■省■即昏昏昏曾咖咖·咖■e◆■自ψψ自自咖◆◆自自·咖自自中即●·章·●●●φψ告卓●p咖申命如●自命卓自即自身4晶■昌■暑音音 26算法分析示例 9 练习……………………………………43 27保证、预测与限制…………………44 练习 46 第一部分参考文献 ↓甲即◆◆q◆咖◆咖ψ哈·自●ψψψpψ咖·咱●◆中b●●自自命·●唱·●●●命 ●自啬b自b過曹昏婚·鲁晷鲁■自b■鲁■●鲁自● C算法(第一卷基础、数据结构、排序和搜索)(第三版 第二部分数据结构 第3章基本数据结构 …49 3.1基石……………50 练习……57 32数组…………………………………………57 练习 毒ψ·■■●●幽↓·如▲血··鲁■血·血■··命命鲁自省·自◆晷鲁鲁晋看D·◆·鲁鲁马号罩旱罩■ 33链表 ·。自···b·●·●◆·■·ψ·昏◆命◆·鲁●罪●·◆·●自■●D●φ哥喜ψ罪●·●命音卓自血自自幽备鲁 练习 34基本表处理 ●●ψ◆帚命命◆·●●D·●●◆●b●音命备◆自命卓良卓血自b自■自语晋备·自命备■●普p●鲁吾會■D罪看看甲导v甲·罪ψ·● s70 练习 ■ψ聊最自p■·■■■■备自看■晋D■■鲁●日會。·目聊曾晋曾·◆即申申自申ψψ·ψ聊即φ音●●唱中咖聊●自命罪命咖自西白命自自 35表的内存分配 丶●即罪罪聊善鲁即■↓■着■p即·D即即■命自咖↓● ●自·●●●●pD·●单。自命自凸·■命备自 练 习…·" 36串……80 练习 ·p··●●睿鲁即。p曾●●命鲁食·章昏◆ 37复合数据结构………… 练习 ●·■鲁●p會●●p看鲁●■鲁●■·◆會睿◆◆●命自●●看●自··●●昏·『●司目罩旱罪司录罩 92 第4章抽象数据类型 ●自·■看●●●即ψ◆D命ψ命◆··鲁自自看省自自血 93 41抽象对象与对象集合…… 练习 ●备自●■■■●。會●口↓口●會國■q昏口 97 42下推栈AT 97 练习 甲●●“·●聊卓●·■■■画■命■ 43栈ADT客户程序示例 咖冒■◆咖··曹自鲁 99 练习…… ■d●鲁 44栈ADT实现 105 练习…… 108 45创建新ADT 109 练习 46FFO队列及广义队列 aaan 111 练习… 117 4.7重复项和索引项 118 练习 48级ADT……… ●d看鲁國■●魯b●b咖鲁鲁『●●●冒·●@●·动录·命昏号龟●·司最驴龟量昂b■■罩■■■■鲁身■ ? 练习 ■p●■■·●■■啁■D■■口■■·■bD即·啁■p啁■■pp啁■口■■■音■咖自咖咖血會咖口音■ψψ看自ψ合自會自鲁·晋·自·鲁●會會唱●p◆●命 啁·罪◆● 49ADT应用示例…………………………………………………131

...展开详情
试读 127P c算法 第1卷:基础、数据结构、排序和搜索
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
c算法 第1卷:基础、数据结构、排序和搜索 10积分/C币 立即下载
1/127
c算法 第1卷:基础、数据结构、排序和搜索第1页
c算法 第1卷:基础、数据结构、排序和搜索第2页
c算法 第1卷:基础、数据结构、排序和搜索第3页
c算法 第1卷:基础、数据结构、排序和搜索第4页
c算法 第1卷:基础、数据结构、排序和搜索第5页
c算法 第1卷:基础、数据结构、排序和搜索第6页
c算法 第1卷:基础、数据结构、排序和搜索第7页
c算法 第1卷:基础、数据结构、排序和搜索第8页
c算法 第1卷:基础、数据结构、排序和搜索第9页
c算法 第1卷:基础、数据结构、排序和搜索第10页
c算法 第1卷:基础、数据结构、排序和搜索第11页
c算法 第1卷:基础、数据结构、排序和搜索第12页
c算法 第1卷:基础、数据结构、排序和搜索第13页
c算法 第1卷:基础、数据结构、排序和搜索第14页
c算法 第1卷:基础、数据结构、排序和搜索第15页
c算法 第1卷:基础、数据结构、排序和搜索第16页
c算法 第1卷:基础、数据结构、排序和搜索第17页
c算法 第1卷:基础、数据结构、排序和搜索第18页
c算法 第1卷:基础、数据结构、排序和搜索第19页
c算法 第1卷:基础、数据结构、排序和搜索第20页

试读结束, 可继续阅读

10积分/C币 立即下载 >