出 版 说 明 信息时代早已显现其诱人魅力,当前几乎每个人随身都携有多个媒体、信息和通信设备,享受其带来的快乐和便宜。 我国高等教育早已进入大众化教育时代。而且计算机技术发展很快,知识更新速度也在快速增长,社会对计算机专业学生的专业能力要求也在不断翻新。这就使得我国目前的计算机教育面临严峻挑战。我们必须更新教育观念——弱化知识培养目的,强化对学生兴趣的培养,加强培养学生理论学习、快速学习的能力,强调培养学生的实践能力、动手能力、研究能力和创新能力。 教育观念的更新,必然伴随教材的更新。一流的计算机人才需要一流的名师指导,而一流的名师需要精品教材的辅助,而精品教材也将有助于催生更多一流名师。名师们在长期的一线教学改革实践中,总结出了一整套面向学生的独特的教法、经验、教学内容等。本套丛书的目的就是推广他们的经验,并促使广大教育工作者更新教育观念。 在教育部相关教学指导委员会专家的帮助和指导下,在各大学计算机院系领导的协助下,清华大学出版社规划并出版了本系列教材,以满足计算机课程群建设和课程教学的需要,并将各重点大学的优势专业学科的教育优势充分发挥出来。 本系列教材行文注重趣味性,立足课程改革和教材创新,广纳全国高校计算机优秀一线专业名师参与,从中精选出佳作予以出版。 本系列教材具有以下特点。 1. 有的放矢 针对计算机专业学生并站在计算机课程群建设、技术市场需求、创新人才培养的高度,规划相关课程群内各门课程的教学关系,以达到教学内容互相衔接、补充、相互贯穿和相互促进的目的。各门课程功能定位明确,并去掉课程中相互重复的部分,使学生既能够掌握这些课程的实质部分,又能节约一些课时,为开设社会需求的新技术课程准备条件。 2. 内容趣味性强 按照教学需求组织教学材料,注重教学内容的趣味性,在培养学习观念、学习兴趣的同时,注重创新教育,加强“创新思维”,“创新能力”的培养、训练;强调实践,案例选题注重实际和兴趣度,大部分课程各模块的内容分为基本、加深和拓宽内容3个层次。 3. 名师精品多 广罗名师参与,对于名师精品,予以重点扶持,教辅、教参、教案、PPT、实验大纲和实验指导等配套齐全,资源丰富。同一门课程,不同名师分出多个版本,方便选用。 4. 一线教师亲力 专家咨询指导,一线教师亲力;内容组织以教学需求为线索;注重理论知识学习,注重学习能力培养,强调案例分析,注重工程技术能力锻炼。 经济要发展,国力要增强,教育必须先行。教育要靠教师和教材,因此建立一支高水平的教材编写队伍是社会发展的关键,特希望有志于教材建设的教师能够加入到本团队。通过本系列教材的辐射,培养一批热心为读者奉献的编写教师团队。 清华大学出版社前言 “数据结构与算法”课程涉及的内容十分丰富,包含了计算机科学与技术专业的许多重要知识,许多分析、解决问题的方法新颖,技巧性强,对学生计算机软件素质的培养作用明显。为培养、训练学生选用合适的数据结构与算法设计方法编写质量高、风格好的应用程序,学生需要不断地进行编程实践,将实验与课程设计实践环节与理论教学相融合,通过实践教学促进数据结构与算法理论知识的学习,有效提高教学效果和教学水平。 本书是游洪跃、唐宁九主编,清华大学出版社出版的《数据结构与算法(C++版)(第2版)》(ISBN 9787302557746,后面简称为主教材)的配套教材。全书分为3部分,具体如下。 第1部分总结了主教材所述的数据结构与算法基础知识。主要目的是帮助读者回顾所学知识,顺利完成后续的实验与课程设计。 第2部分包含了22个实验。这些实验题目包括了主教材正文内容的不同实现方式(例如实现不带头节点形式的单链表),包括了对主教材内容的改进(例如对主教材的哈夫曼树类模板的方法EnCode加以改进,将查找字符位置通过指向函数的指针来实现),包括了对主教材算法的优化(例如用赋值语句代替交换两个数据元素的方法,来优化快速排序算法与堆排序),包括了对主教材算法的改造与提高(例如改进最小生成树的Kruskal算法),还包括了数据结构与算法的有趣应用(例如要求在一个n×n的棋盘上放置n个皇后并且放置的n个皇后不会互相吃掉),通过实验极大提高读者数据结构与算法的应用能力。每个实验都包括目的与要求、工具及准备工作、实验分析、实验步骤、测试与结论以及思考与感悟几部分。实验给出了具体操作步骤以及具体、实用的指导,让初学者面对实验题目不会束手无策。希望读者通过实验能够学有所思,得到启迪与感悟。 第3部分包含了11个课程设计项目。简单的项目可以一个人单独完成,复杂的项目可由几个人共同完成。这些项目包括对主教材中实例研究的改进(例如从键盘上输入中缀算术表达式,包括括号,计算出表达式的值),包括接近实际课题的项目(例如采用哈夫曼算法开发一个压缩软件,以及采用图的知识开发公园导游系统),包括容易引起读者兴趣的项目(例如词典变位词检索系统),还包括开拓学生视野的项目(例如用具有自学习功能的专家系统思想实现《动物游戏》的开发)。课程设计项目一般都提供功能的扩展方法,基础较差的读者可只实现基础功能,对数据结构与算法有兴趣的读者可实现更强的功能,这样使不同层次的读者都会有所收获。读者通过做这些项目能快速提高解决实际问题的能力。每个项目都给出了分析与实现方法,还给出了一些改进建议,读者可以在完成基本任务的前提下,对程序加以改进和提高。 本书所有实验与课程设计都在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01中通过测试。 为满足不同层次的教学需求,本教材使用了分层的思想,分层方法如下: 没加星号“”及“”的部分是基本内容,适合所有读者学习;加有星号“”的部分是适合计算机专业的读者深入学习的选学部分;加有两个星号“”的部分适合感兴趣的同学研究,尤其适合那些准备参加ACM竞赛的读者加以深入研究。作者为本书提供了全面的教学支持,读者可在清华大学出版社官网的本书页面下载如下教学资源。 (1) 本书作者开发软件包(包含所有本书所讲的数据结构与算法的类模板与函数模板)。 (2) 全书所有实验与课程设计的在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境中的测试程序。 (3) 数据结构与算法相关的其他资料(例如DevC++v5.11与CodeBlocks v16.01软件等开源C++编译器)。 通过扫描二维码可观看全书所有实验与课程设计的测试程序演示视频,其中第1个二维码对应Visual C++ 6.0开发环境的测试程序演示视频,第2个二维码对应VisualC++ 2017开发环境的测试程序演示视频,第3个二维码对应DevC++ v5.11开发环境的测试程序演示视频,第4个二维码对应CodeBlocks v16.01开发环境的测试程序演示视频。 在附录D中介绍Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境建立工程的步骤,可通过扫描二维码观看具体操作视频。 程艳红、袁平、陈良银、游倩、张银、文芝明等人对本书做了大量的工作,包括提供资料,调试算法,参与了部分内容的编写,在此特向他们表示感谢;作者还要感谢为本书提供直接或间接帮助的每一个朋友,由于你们的热情帮助和鼓励,才激发了作者写好本书的信心和写作热情。 本书的出版要感谢清华大学出版社的相关编校人员大力支持,由于他们为本书的出版倾注了大量热情,也由于他们的前瞻性眼光,才让读者有机会看到本书。 尽管作者有认真负责的态度,并做了最大努力,但由于作者水平有限,书中难免出现不妥之处,敬请各位读者不吝赐教,以便及时修正,提高本书的水准。 作者2020年9月