算法c语言实现

【实例简介】
算法c语言实现算法
该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^∧ 鳶言 本书旨在综述当令程序员使用的最重要的计算机算法,间时为越来越多需要学习这些 算法的人讲解基本技术。本书可以用作学剑计算机科学的第二、第三或弟四门课程的教科 书,供那些掌握了基本编程技能并熟悉了计算机系统,但还未学习计算机科学或着计算机 应用的高阶领城专业课程的学生来选修。本书也可以作为从事计算机系统或应用程序开发 的自学教材或参考书,因为它包含有用算法的实现以及这些算法性能特征的详细信息。木 书讲解全面,也是一本合适的算法导论书 我全部重写了新版内容,添加了1000多个新练习、100多幅新图以及许多新程序。我还 为所有插图和程序添加了详细的注释。这坐新材料既包含了些新主题,还对许多经典算法 提供了更全的解释。整本书还添加了一个重点内容,即抽象数据类型,使得这些程序更加 通用、更适应于现代面向对象编程环境。铡读过本书版的读者在新版中可以学到大量新知 识:所有读者都可以阅读到丰宮的教学材料,通过它们可以快速掌握一些重要概念 由于添加了大量新材料,所以将新版分为二卷,每一卷都与旧版篇幅相当,本书为第-卷。 这-畚包括基本概念、数据结构、排序算法以及搜索算法:第二卷在本书基本抽象和方法基 础上讲解高级算法和应用。在新版本中,儿乎所有基础知识和数据结构的材料都是新的。 本书所面向的对象并不仪仪是程序员利计算机专业的学生。几乎每个计算机的使用者 都希望计算极能够进行得更快或者能够解决更大的问题。本书中的算法代表过去50年的知 识发展水平,针对各种不同的应用。在高效使用计算机中不可或缺。从物理学上的N-体模 拟(A- body simulation)问题到分子生物学中的基因序列问题,这里描述的基本方法已成为 科学研究中的核心要素:而且从数据库系统到因特网搜索引擎,它们已成为现代软件系统 的核心部分。随着计算机的应用范围越来越广泛,本书介纲的一些基本方法的影响也随之 增大。对」邢些有志于掌握这些其本算法,并且灵巧地利用它们作为将来所从事的计算机 应用的基本工具的学生和专业人员,本书的目标就是作为他们实现理想的宝贵资源。 讨论范围 本书分16章,共4部分:基础知识、数据结构、排序和搜索。这里的描述是为了让读 者对尽可能广泛的基本算法的基本性质有一个大概的了解。这里描述了从二项式队列到 patricia tme等特巧方法,它们都与计算机科学核心中的基本范例相关。第二卷包括另外4 部分,涉及串、儿何体、图以及髙级丰趣。我编撰这两本书的目的是,从不同的领域将这 些基本方法汇集起来,为读者提供已知的通过计算机解决问题的域佳方法 如果你选修过计算机学科中的一到两汀预备课程,或者有过与之当的编程经验,则 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^ C算法(第一卷基础、敷据结构、排序和搜京)〔第三版〕 会从本书受益最大s这些选修课程可以是一门高级编程语吉,如C、JVa或C++,也可以 是讲述编程系统基本概念的课程。因而,本书面向那些熟悉现代编程话言以及现代计算机 系统基本特征的读者。对正文中讲解的知识,读者通过参考文献可以进一步详细了解 大部分支撑本书分析结果的数学内容都是独立的(或者作为超出了本书的讨论范围而 标记出来),因此,学习本书需要很少的数学预备知识,当然,深厚的数学造诣对学习过程 无疑是有益的 如何在课程中使用 根据老师的教学方法上差异以及学生的预备知识的多寡,讲授本书的方式可以灵活 多变这里描述的算法多年来得到了广泛的应用,丽且代表着熟练程序员以及计算机科学 学生的核心知识面。本书包含了很多的数据结构方面的基本内容,因此,可以用于数据结 构课程的教学。本书也对算法进行∫相当详细的讨论,并提供了足够的高级内容,因此, 也可以用于算法课程的教学。一些老师可能希望重点讲解实现以及实际应用上的问题,另 外些老师可能希望重点讨论分析和理论概念 在本书的主页上,可以找到用于授课的整套幻灯片、小例编程作业布置、学生使用的 交互练习以及其他些材料。 数据结构和算法的基本课程可以重点讲解第二部分屮的基本数据结树以及第三、四部 分中在实现里的运用。算法设计和分析课程可以重点讲解第一部分和第5章中的基本内容, 然后学习第三部分和第四部分中的算法,学习这些算法是如何达到好的渐近性能的。软件 工程裸程可以忽略数学和高级算法内容,重点讲解如何在大型程序或系统中集成书中提供 的实现算法课程对于所有这些内容,可以采取综述、简介的方式来讲授。 近几年,全球很多院校使用本书的旧版本作为计算机科学的第二或第三门课程教材, 同时也作为其他课程的辅助阅读内容。在普林斯顿大学,我们的教学经验是,本书所囊括 的内容可以作为主修评的计算机科学导论,在算法分析、系统编程以及理论计算机科学等 后续课程上可以进步潦入,同时,还为其他学科中不断增长的学生群体提供丰富的技能, 他们可以将这些技术立即完美地付之于实峨 书中的练习分为几类〔在新版本中,大部分练习为新添加的)有些练习是为了测试读 者对课文内容的理解,只是要求读者完成一个例子,或者应用正文中描述的概念、有些练 习包括实现代码和算法的综合,或者通过试验研究比较算法的变种,并学习其性质。还有 些练习提供了许多重要雨详细的信息,这些信息不适合于在正文中讲解。每位读者阅读 和思考这些练习都会有收获。 算法的实用 任何希望更高效使用计算机的人都可将本书作为参考书,或者用于自学。具有编程 经验的人在全书各章节都可以找到特定主题的有用信息。虽然在某些情况下,某一章中的 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看 前言 算法可能借用前面章节的方法,但在很大程度上,读者可以独立阅读各章节 本书的目标就是学习那些可能运用于实践的算法。它提供了足够的信息,读者可以胸 有成竹地运行、调试程序,并且获得有效算法来解决实际问题,或者为应用程序提供功能。 书中提供了所讨论方法的亢整实现代码,描述了一系列相关联的例程中的运算。因为我们 提供的是实际代码,而不是伪码,所以这些程序可以直接运用于实践。在本书的主页可以 下载所有程序源代码。 实际上,在整本书中,为每个算法都展示了实际应用,并H配制了相关的数百幅说明 图示。通过这种直观的演示说明,许多算法变得浅显易懂 书中详细讨论了这些算法的特征和它们可以发挥作用的场合。算法分析和理论计算机 科学的联系垃然不是重点内容,但也在本书中安排了适当的篇幅进行讲解。适当的时候会 引用试验和分析结论,米说明优先选择某些算法的原因。必要的时候,书中还会描述所讨 论的实际算法与纯理论结论之间的关系。本书自始至终地综合、归纳和探讨了算法及其实 现的性能特征的专门信息 编程语 所有实现都使用C语音写成。任何语言都有优缺点,我们选开C语音,是因为它得到 了广泛应用,而且提供了实现所需要的功能。这些程序很容易被转换成其他现代编程语言, 因为其中使月的c独特结构很少。我们尽可能使用标准C约定,但这本书不是本学习C 语言编程的参考书 新版本添加了许多新程序,同时重写了许多旧程序,王要是为了让它们更容易用作 抽象嫩据类型实现。针对这些程序,程序的人量的比较测试讨论贯穿于全书中 本书的旧版本提供了用 Pascal、C++和 Modula-3写成的些基本程序。这些程序在网 站上可以下载使用:新程序的代码以及用新语言(如Java)编写的代码也作了适当的增补 本书的日的是以尽可能简单、直接的形式讲解算法。尽可能保持-致的风格,让相似 的程序看起来比较统一。对于本书中的许多算法,不管用何种语言写成,它们均保持相似 性。举个突出的例了,快速排序( quicksort)能进行快速排序,不管是用 Algul-60、 Busic Fortran、 Smalltalk、Ada、 Pascal、C、 PostScript、Java,还是用其他编程语言和环境来实 现,亡仍被认为是一种高效的排序方法 我们尽量提供雅致、紧凑、可移植的实现,但要考虑到它们的效率问题,因此我们 尽量在编制实现的各个阶段留意代码的性能特征第1章按这种方式为算法开发了高效的C 实现,列举了一个详细的示例,并且为余下各章节的学习打好基础。 致谢 很多旧版读者为我提供了有用的反馈。特别是,普林斯顿大学和布朗大学的数百名学 生多年使用本书的初稿,并提出了宝贵意见特别感谢Tina和 Tom freeman对初版的付梓 3 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^∧ C算法〔第一卷巷础、数据鲒构、排序和披索)(笫三版 给了的帮助:感谢 Janet Incerpi在利用早剪原始数字化训算机排版硬件和软件生成初版样稿 时付出的创造性芳动和智慧:谢 Marc brown参与算法可视化表小的研究互作,使得本书 能配备如此多的精美插图:感谢 Dave hanson尽心解答所有与C语亩有关的问题。还妥感 谢为本书的不同版本提供详细评论的诸多读者,他们有: Guy Alnes, Jon Bentley, Marc brown, Jay Gischer, Allan Heydon, Kennedy Lemke, Udi Manber, Dana Richards, John Reif, M Rosenfeld, Ste phen Seidman, Michael Quinn #4 Willian Ward 为了新版本的问世,我有幸与 Addison- Wesley出版社的 Peter gordon和 Debbie lafferty 合作,从本书的一般更新到大量重写,他们始终予以耐心的指导。岜很荣幸能与 Addison-Wey出版社的其他压位专业人士合作,根据这一项目的髙定位,对于他们来讲 这本书的编辑T作意味着不同寻常的挑战,我由衷敬佩他们坚韧不拔的精神。 编与吡书时,我喜获两位新导帅,我尤其要表达对他们的感激之情。第一位是Seve summit,他从技术上仔细审查了手稿的早期版木,并提语了数千条详细意见,尤其是对程 序提出的宝贵意见。 Steve准确理解了我为读者提供雅致、有效以及高效实现的意图,他的 意见不仅帮助我在实现代码间保持致性,而且帮助我切实改进了许多程序。第二位是In Dupre,他也对原稿提出了数千条详细意见,它们的宝贵价值不仗在于帮功我更正和避免语 法上的错误,而且吏重要的是,帮動我找到一种致、连贯的编写风格,这有助于组织书 中的大量技术材料。能有幸聆听Sve和Iyn的教诲,实在是荣幸之至,他们的付出对本书 的顺利编撰至关重要。 我在这則所写的很多内容来自于我在斯坦福大学的导师 Don Knuth的讲授和著作。量 然D对这书没有直接影响,但在本书可以处处感觉到他的影响,囚为正是他将算法的 研究置于科学的殿堂之中,从而使得编写这样的书成为可能。我的朋友和同事Phip Flajole在算法分析发展成一门成熟研究科学的过程中是主力,他对木书也相似的影响 深深感谢普林斯顿大学、布朗大学以及法国国家信息与动化研究院〔 INRIA)的支 持,我在这地方完成了本书的大部分工作。也感谢美国国防部防御分析研究所〔The institute for Defense Analyses)和 Xerox palo alto研究中心的支持,我在访问这些单位期 间完成了本书的部分工作。本书的许多部分与美国国家科学基金会和海军妍究外公室的大 方支持的研有关。最后,我要感谢 Bill Bowen、 Aaron lemonick和 Neil Rudenstine在普 林斯顿大学建立相关学术环境中给予的支持,使我在完成其他丁作职责之然,仍然能够在 这样的学术环境中准备本书的撰写。 Robert sedgewick 法图 Marly-le-Roi市,1983年2月 美国新泽西州普林斯顿,199年1月 美国罗得鸟州詹姆新敦,997年8月 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^ 关于书中练习 对书中练习进行分类充满了不确定因素,因为读者的知识水平和经验参差不齐。尽管如此, 提侠一定的指导是适的,所以许多练习带有4种符号中的种,帮助误孝决定如何使月这些 练习。 测试对知识理解程度的练习标有…个空心角形,如下所示: t>57.把 EASY QUESTION键入个初始为空的二项式队列,写出得到的项式队列 最通常的情况是,这些练习与正文中的示例直接相关。它们没有特殊的难度,但完成这些 练习后,可以帮助你进步掌握文中没能理解的结论或概念, 为正文中的知识点添加了新的、值得进-步思考的信息时,这样的练丬标有个空心圆, 如所示 O20.编’一个程序,使用分离链在大小为M100的表中插入N个随机整数,然后求最短表 与最长表的长度,分别取N=10,104,103和0°n 水种练鼓励你思考一些与正文中的材料有关的重要概念,或者答阅读让文时可能碰到 的问题。即使你没有时间来完成这些冻习,这些练习可熊也植得闯读。 对读者来说具有挑战性的练习标有一个黑圆点,如下所小 ●46.设实现归并排序时在随机位置分解文件,而不是在准确的中间位置分解。通过这种丿 法来排序N个元素,平均需要多少次比较? 这类练习可能需要相当多的时间来完成,根据读者的经验多少底有所不同。一般而言,最 仨途径是分戈儿个不同的阶段来完成。 还有少数相当难的练习〔与其他大部分练习相比而言〕,它们标有两个黑色圆点,如卜 所示: ●●29证!由N个随机位串生成的re高度约为2N 这梐冻习与研究文献中解决的问趣相似,但根据本书提供的材料,可以从尝试解决文献 中的那些司题得到乐趣(也许能完美解决)。 根据读者的编程能力和数学背景,这些注释定位道中。那些需要专业编程知识和数学分析 的练习是不证自明的。鼓励所有读者逦过实现算法来測试对它们的理解。还有种类似丁沘的 练习对于熟练程序员或学过编程课程的学生来说简单易懂,但对于未曾从事过编程的人来说, 可能工作量相当大 23.修攻程序1斗,生成介于到N-]之间的随机数对,而不是从标准输入读取,同时 一直循环到N1次集合并运算执行完成。分别在N10,10,10以及10的情况下运行此程序 而且打印出对应每个N值生成的边总数 同理,我也建议所有读者认真解答证明箅法性质的分析基础知识的练习。对于那些离散数 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^∧ C算法(笫一卷基础、数据结构、排序和拽烹)〔第三版) 学专业的科学家或学生来说,这些练习并不难,但对于不精通数学分析的人来悦,这些练习可 能需要较大的三作量: 13.由加权快速集合并算法生成的具有2个节点的最坏情况树中,计算从某节点到根的平 均距离。 读者需要消化吸收的练习太多,我希望在这本书中提供足够的练习,激励读者对感兴趣的 知识有更宽广的理解,而不只是对正文内容走马观花、 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^∧ 目录 第部分基础知识 第1章导论… 鲁中智自自中曾!P會早P 11算法……… ■■■省口■山·↓·自■↓·db看●■dψ看■讠■■晕■昏■■■■■■昏晷■■曾■昏『TP■■冒号『甲T曾罾「日口■日■ 12问题示例:连通性( connectivity) 4 练习 13并集一查找算法 练习 凸■■凵■■■■『■【■t音自自鲁d【自4 14展望 會■鲁■鲁P曾曾◆曾驴曾早P早!旱 18 练习 ………………19 15小结 19 第2章算法分析原理… 冒■冒4旱!■ 22 21实现与试验分析 ■■■■■昏■■■■■■■■冒■■冒冒■■■冒冒P■曾P 啬d 练习……………·……25 22算法分析 會會會自鲁■■■會曾■■鲁■·會會日會曾 425 练习 ……27 23函数增长 27 练习 32 24O记号 32 练习 t…35 2基本递推式 會■■ P早q日P■口自■自省自命命·血自备自●自日·●●司■■●看·■●食 练习……………………………………………………………,灬……·38 26算法分析示例 甲,中中一平↓中·血“通晶↓“音hd■·■4讠【日吾骂日■↓ 39 练习 v号甲平曾甲甲画d山白b山d函晶山b晶日b吾山日b晶■日晶晶西■日面■ 27保证、预测与限制… ■■φ西ψ血L』血西■晶·↓酯昌·晶b晶h郾暴晶●ψψ■■西■h晶司■顰司命罪讠罩罪哥聊卜自身■鲁自者自 44 练习 ■■■冒■■■冒看■·ψ■··音自自自皛自自4b◆者鲁唱自自备會■鲁4■昏自曾鲁噜■■昏■自日曾冒号卩即噜!P冒會号即早争 第一部分参考文献 會■■口會個 會P會P曾!會 47 该书下载自-书部落分享计算机经典巨著!-www.shubulo.com!仅供试看^∧ C算法(笄一卷础、数据结构、排序和搜索}(第三版) 第二部分数据结构 第3章基本数据结构 ▲■日卩聊『■■■■自专詈自l自』自自會◆鲁自■●啁◆自即◆φ■自P早唱早命『◆ ■■幽■■個■■■個■一 49 3基石…50 练习 b山↓↓■■_■·d↓↓■毛d國b↓甲罪■罪罩罩甲■ ■■■■ 自幽幽■會曾■幽曾■■P曾4P◆■■■ 57 32数组… 4!甲…·57 练习……… 口鱼■■個■■■血 63 33链表………………………………………4 练习……………………………………………… 34基本表处理 :…………70 练习 ■會■■昏音血··斷自白會自會■血自鲁會曾■會?·督甲■P鲁甲·甲平日■1 35表的内存分配 矫习 36 串 练习……………………984 37复合数据结构…r ■■■■■■鲁一■■ ▲φd國山■b郾h』J■db■■■●旮■●■■h■■■■■■晋昏■留■■昏■■鲁申自自自血自自鲁鲁會目血噜自曾自中即目!?冒旱曾 92 第4章抽象数据类型 ……………93 41抽象对象与对象集合……………………“……………………"95 练习 P中·早早◆中P■血■ 聯■■■■幽◆自■自跏山自。●咱自自●■咖ψdpp●●卩珈■罪即·即血■■■會■罪■“■■■■■音目■『■自自音音自自山b幽 42下推栈ADT ……:97 练习 43栈ADT客户程序示例 练习 山鹵▲晶矗■▲d■山▲■■■凸■d■▲■b▲画■d画▲西■凸晶■■■晶▲■■■■■■画晶■诅■■■■■昏昏■■日■■■■昏昏■1■■■■■啬【自詈會音b幽引·自自鲁◆鲁自1■■鲁鲁自自鲁 44栈ADT实现 ……105 练习…………………………………108 4.5创建新ADT 即P中!旱"會◆甲平鲁早早P鲁早■■■日■■日■咱日■b■ 练习 46FIPO队列及广义队列∵ 练习… 晶b晶↓↓凸_↓d郾晶↓■■晶 11T 47重复项和索引项…4118 练 自■自口■幽啁■■■啁■幽■■自··咱自■自;血唱咖自幽自·■。看鲁自咖■咖血↓··幽自咖●血■◆跏白d■●■嵋p跏··p●■■●日·咖■■看园●日甲●暗1●聊罪罩司 121 48一级ADTI 122 练习………………………………………………………… d·●命p●咖甲唱 真3Q 49ADT应用水例 會自自鲁鲁自◆血命■自會自■◆鲁中鲁血自鲁即■嚯鲁鲁口■鲁曾■曾鲁唱■『!曾↓早冒中P早早甲早甲早會■■ 争号P■■■■■■■ 131 【实例截图】
【核心代码】