本书结合C++面向对象程序设计的特点，讨论了数据结构与算法基础知识，并构建了实验与课程设计，对所有算法都在Visual C++ 6.0、Visual C++ 2017、Dev-C++ v5.11和CodeBlocks v16.01开发环境中进行了严格的测试，同时还提供了大量的教学支持内容。

出 版 说 明

信息时代早已显现其诱人魅力，当前几乎每个人随身都携有多个媒体、信息和通信设备，享受其带来的快乐和便宜。

我国高等教育早已进入大众化教育时代。而且计算机技术发展很快，知识更新速度也在快速增长，社会对计算机专业学生的专业能力要求也在不断翻新。这就使得我国目前的计算机教育面临严峻挑战。我们必须更新教育观念——弱化知识培养目的，强化对学生兴趣的培养，加强培养学生理论学习、快速学习的能力，强调培养学生的实践能力、动手能力、研究能力和创新能力。

教育观念的更新，必然伴随教材的更新。一流的计算机人才需要一流的名师指导，而一流的名师需要精品教材的辅助，而精品教材也将有助于催生更多一流名师。名师们在长期的一线教学改革实践中，总结出了一整套面向学生的独特的教法、经验、教学内容等。本套丛书的目的就是推广他们的经验，并促使广大教育工作者更新教育观念。

在教育部相关教学指导委员会专家的帮助和指导下，在各大学计算机院系领导的协助下，清华大学出版社规划并出版了本系列教材，以满足计算机课程群建设和课程教学的需要，并将各重点大学的优势专业学科的教育优势充分发挥出来。

本系列教材行文注重趣味性，立足课程改革和教材创新，广纳全国高校计算机优秀一线专业名师参与，从中精选出佳作予以出版。

本系列教材具有以下特点。

1. 有的放矢

针对计算机专业学生并站在计算机课程群建设、技术市场需求、创新人才培养的高度，规划相关课程群内各门课程的教学关系，以达到教学内容互相衔接、补充、相互贯穿和相互促进的目的。各门课程功能定位明确，并去掉课程中相互重复的部分，使学生既能够掌握这些课程的实质部分，又能节约一些课时，为开设社会需求的新技术课程准备条件。

2. 内容趣味性强

按照教学需求组织教学材料，注重教学内容的趣味性，在培养学习观念、学习兴趣的同时，注重创新教育，加强“创新思维”，“创新能力”的培养、训练；强调实践，案例选题注重实际和兴趣度，大部分课程各模块的内容分为基本、加深和拓宽内容3个层次。

3. 名师精品多

广罗名师参与，对于名师精品，予以重点扶持，教辅、教参、教案、PPT、实验大纲和实验指导等配套齐全，资源丰富。同一门课程，不同名师分出多个版本，方便选用。

4. 一线教师亲力

专家咨询指导，一线教师亲力；内容组织以教学需求为线索；注重理论知识学习，注重学习能力培养，强调案例分析，注重工程技术能力锻炼。

经济要发展，国力要增强，教育必须先行。教育要靠教师和教材，因此建立一支高水平的教材编写队伍是社会发展的关键，特希望有志于教材建设的教师能够加入到本团队。通过本系列教材的辐射，培养一批热心为读者奉献的编写教师团队。

清华大学出版社

“数据结构与算法”课程涉及的内容十分丰富，包含了计算机科学与技术专业的许多重要知识，许多分析、解决问题的方法新颖，技巧性强，对学生计算机软件素质的培养作用明显。为培养、训练学生选用合适的数据结构与算法设计方法编写质量高、风格好的应用程序，学生需要不断地进行编程实践，将实验与课程设计实践环节与理论教学相融合，通过实践教学促进数据结构与算法理论知识的学习，有效提高教学效果和教学水平。 

本书是游洪跃、唐宁九主编，清华大学出版社出版的《数据结构与算法(C++版)(第2版)》(ISBN 9787302557746，后面简称为主教材)的配套教材。全书分为3部分，具体如下。

第1部分总结了主教材所述的数据结构与算法基础知识。主要目的是帮助读者回顾所学知识，顺利完成后续的实验与课程设计。

第2部分包含了22个实验。这些实验题目包括了主教材正文内容的不同实现方式(例如实现不带头节点形式的单链表)，包括了对主教材内容的改进(例如对主教材的哈夫曼树类模板的方法EnCode加以改进，将查找字符位置通过指向函数的指针来实现)，包括了对主教材算法的优化(例如用赋值语句代替交换两个数据元素的方法，来优化快速排序算法与堆排序)，包括了对主教材算法的改造与提高(例如改进最小生成树的Kruskal算法)，还包括了数据结构与算法的有趣应用(例如要求在一个n×n的棋盘上放置n个皇后并且放置的n个皇后不会互相吃掉)，通过实验极大提高读者数据结构与算法的应用能力。每个实验都包括目的与要求、工具及准备工作、实验分析、实验步骤、测试与结论以及思考与感悟几部分。实验给出了具体操作步骤以及具体、实用的指导，让初学者面对实验题目不会束手无策。希望读者通过实验能够学有所思，得到启迪与感悟。

第3部分包含了11个课程设计项目。简单的项目可以一个人单独完成，复杂的项目可由几个人共同完成。这些项目包括对主教材中实例研究的改进(例如从键盘上输入中缀算术表达式，包括括号，计算出表达式的值)，包括接近实际课题的项目(例如采用哈夫曼算法开发一个压缩软件，以及采用图的知识开发公园导游系统)，包括容易引起读者兴趣的项目(例如词典变位词检索系统)，还包括开拓学生视野的项目(例如用具有自学习功能的专家系统思想实现《动物游戏》的开发)。课程设计项目一般都提供功能的扩展方法，基础较差的读者可只实现基础功能，对数据结构与算法有兴趣的读者可实现更强的功能，这样使不同层次的读者都会有所收获。读者通过做这些项目能快速提高解决实际问题的能力。每个项目都给出了分析与实现方法，还给出了一些改进建议，读者可以在完成基本任务的前提下，对程序加以改进和提高。

本书所有实验与课程设计都在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01中通过测试。

为满足不同层次的教学需求，本教材使用了分层的思想，分层方法如下: 没加星号“”及“”的部分是基本内容，适合所有读者学习；加有星号“”的部分是适合计算机专业的读者深入学习的选学部分；加有两个星号“”的部分适合感兴趣的同学研究，尤其适合那些准备参加ACM竞赛的读者加以深入研究。作者为本书提供了全面的教学支持，读者可在清华大学出版社官网的本书页面下载如下教学资源。

(1) 本书作者开发软件包(包含所有本书所讲的数据结构与算法的类模板与函数模板)。

(2) 全书所有实验与课程设计的在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境中的测试程序。

(3) 数据结构与算法相关的其他资料(例如DevC++v5.11与CodeBlocks v16.01软件等开源C++编译器)。

通过扫描二维码可观看全书所有实验与课程设计的测试程序演示视频，其中第1个二维码对应Visual C++ 6.0开发环境的测试程序演示视频，第2个二维码对应VisualC++ 2017开发环境的测试程序演示视频，第3个二维码对应DevC++ v5.11开发环境的测试程序演示视频，第4个二维码对应CodeBlocks v16.01开发环境的测试程序演示视频。

在附录D中介绍Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境建立工程的步骤，可通过扫描二维码观看具体操作视频。

程艳红、袁平、陈良银、游倩、张银、文芝明等人对本书做了大量的工作，包括提供资料，调试算法，参与了部分内容的编写，在此特向他们表示感谢；作者还要感谢为本书提供直接或间接帮助的每一个朋友，由于你们的热情帮助和鼓励，才激发了作者写好本书的信心和写作热情。

本书的出版要感谢清华大学出版社的相关编校人员大力支持，由于他们为本书的出版倾注了大量热情，也由于他们的前瞻性眼光，才让读者有机会看到本书。

尽管作者有认真负责的态度，并做了最大努力，但由于作者水平有限，书中难免出现不妥之处，敬请各位读者不吝赐教，以便及时修正，提高本书的水准。

作者2020年9月

第1部分基 础 知 识

第1章绪论3

1.1数据结构的基本概念3

1.2算法和算法分析4第2章线性表6

2.1线性表的逻辑结构6

2.2线性表的顺序存储结构7

2.3线性表的链式存储结构7第3章栈和队列9

3.1栈9

3.2队列10

3.3优先队列12第4章串13

4.1串类型的定义13

4.2字符串模式匹配算法13第5章数组和广义表16

5.1数组16

5.2矩阵17

5.3广义表19第6章树和二叉树22

6.1树的基本概念22

6.2二叉树23

6.3二叉树遍历25

6.4线索二叉树26

6.5树和森林的实现27

6.6哈夫曼树与哈夫曼编码32

6.7树的计数33第7章图35

7.1图的定义和术语35

7.2图的存储表示38

7.3图的遍历40

7.4连通无向网的最小代价生成树40

7.5有向无环图及应用41

7.6最短路径41第8章查找43

8.1查找的基本概念43

8.2静态查找表43

8.3动态查找表43

8.4哈希表47第9章排序50

9.1概述50

9.2插入排序51

9.3交换排序51

9.4选择排序51

9.5归并排序52

9.6基数排序52

9.7外部排序53

第10章文件55

10.1主存储器和辅助存储器55

10.2各种常用文件结构55

第11章算法设计与分析56

11.1算法设计56

11.2算法分析58

第2部分实验

实验1石头、剪刀、布61

实验221点70

实验3不带头节点形式的单链表80

实验4任意大非负整数的任意大非负整数次方93

实验5病人就医管理102

实验6利用后缀表达式计算中缀表达式的值107

实验7文本串的加密115

实验8改造串类120

实验9螺旋方阵130

实验10引用数使用空间表法广义表存储结构134

实验11用二叉树表示表达式147

实验12改进哈夫曼树类153

实验13求最小生成树的Kruskal的算法改进161

实验14图的根顶点166

实验15链地址法处理冲突的哈希表170

实验16字符统计177

实验17改造快速排序算法181实验18改造基数排序算法186

实验19学生基本信息管理193

实验20电话号码的查找205

实验21农夫过河问题216

实验22n皇后问题225

第3部分课 程 设 计

项目1算术表达式求值233

项目2停车场管理系统237

项目3电话客户服务模拟器244

项目4简单文本编辑器250项目5压缩软件260

项目6排课软件271

项目7公园导游系统282

项目8理论计算机科学家族谱的文档／视图模式288

项目9动物游戏296

项目10简单个人图书管理系统302

项目11词典变位词检索系统311

参考文献316

附录A本书配套软件包318

附录B实验报告格式324

附录C课程设计报告格式325

附录D流行C++开发环境的使用方法326

（1）提供本书作者开发的软件包（包含所有本书所讲的数据结构与算法的类模板与函数模板）。

（2）介绍Visual C++ 6.0、Visual C++ 2017、Dev-C++ v5.11和CodeBlocks v16.01开发环境建立工程的步骤，在工程建立新文件与向工程添加已有文件的方法的文档，以及打开一个工程的视频。

（3）全书所有实验与课程设计的在Visual C++ 6.0、Visual C++ 2017、Dev-C++ v5.11和CodeBlocks v16.01开发环境中的测试程序。

（4）全书所有实验与课程设计的测试视频。

（5）提供数据结构与算法相关的其它资料（例如Dev-C++v5.11与CodeBlocks v16.01软件等免费C++编译器）。

唐宁九，四川大学计算机学院教授，硕导，主持、参与“863项目”“九.五攻关项目”五项，主持、参与横向科研课题6项，在核心期刊上发表论文三十余篇，主编专著一本，主编教材一本，参加编写教材3本。