本书作为王红梅等编著、清华大学出版社出版的《数据结构（C++版）》配套教学参考书，针对数据结构课程的特点以及学生学习数据结构课程的认知规律，研究每个知识点的教学方法，将教材中无法表达的教学思路、教学设计和教学方法展现出来，对于每一章的教学内容按“本章教学要点→教学专题→教案和讲稿”组织。

本书可供从事数据结构及相关课程教学的教师作为教学参考书，也可供计算机专业的学生作为学习参考书，同时也为大学教案的编写提供了一个可参考的模板。

本书封面贴有清华大学出版社防伪标签，无标签者不得销售。

我国高等教育逐步实现大众化后，越来越多的高等学校将会面向国民经济发展的第一线，为行业、企业培养各级各类高级应用型专门人才。为此，教育部已经启动了“高等学校教学质量和教学改革工程”，强调要以信息技术为手段，深化教学改革和人才培养模式改革。如何根据社会的实际需要，根据各行各业的具体人才需求，培养具有特色显著的人才，是我们共同面临的重大问题。具体地说，培养具有一定专业特色的和特定能力强的计算机专业应用型人才则是计算机教育要解决的问题。

为了适应21世纪人才培养的需要，培养具有特色的计算机人才，急需一批适合各种人才培养特点的计算机专业教材。目前，一些高校在计算机专业教学和教材改革方面已经做了大量工作，许多教师在计算机专业教学和科研方面已经积累了许多宝贵经验。将他们的教研成果转化为教材的形式，向全国其他学校推广，对于深化我国高等学校的教学改革是一件十分有意义的事情。 

清华大学出版社在经过大量调查研究的基础上，决定组织出版一套“普通高校本科计算机专业特色教材精选”。本套教材是针对当前高等教育改革的新形势，以社会对人才的需求为导向，主要以培养应用型计算机人才为目标，立足课程改革和教材创新，广泛吸纳全国各地的高等院校计算机优秀教师参与编写，从中精选出版确实反映计算机专业教学方向的特色教材，供普通高等院校计算机专业学生使用。

本套教材具有以下特点。

1. 编写目的明确

本套教材是在深入研究各地各学校办学特色的基础上，面向普通高校的计算机专业学生编写的。学生通过本套教材，主要学习计算机科学与技术专业的基本理论和基本知识，接受利用计算机解决实际问题的基本训练，培养研究和开发计算机系统，特别是应用系统的基本能力。

2. 理论知识与实践训练相结合

根据计算学科的三个学科形态及其关系，本套教材力求突出学科的理论与实践紧密结合的特征，结合实例讲解理论，使理论来源于实践，又进一步指导实践。学生通过实践深化对理论的理解，更重要的是使学生学会理论方法的实际运用。在编写教材时突出实用性，并做到通俗易懂，易教易学，使学生不仅知其然，知其所以然，还要会其如何然。

3. 注意培养学生的动手能力

每种教材都增加了能力训练部分的内容，学生通过学习和练习，能比较熟练地应用计算机知识解决实际问题。既注重培养学生分析问题的能力，也注重培养学生解决问题的能力，以适应新经济时代对人才的需要，满足就业要求。

4. 注重教材的立体化配套

大多数教材都将陆续配套教师用课件、习题及其解答提示，学生上机实验指导等辅助教学资源，有些教材还提供能用于网上下载的文件，以方便教学。

由于各地区各学校的培养目标、教学要求和办学特色均有所不同，所以对特色教学的理解也不尽一致，我们恳切希望大家在使用教材的过程中，及时地给我们提出批评和改进意见，以便我们做好教材的修订改版工作，使其日趋完善。

我们相信经过大家的共同努力，这套教材一定能成为特色鲜明、质量上乘的优秀教材。同时，我们也希望通过本套教材的编写出版，为“高等学校教学质量和教学改革工程”做出贡献。

在我国，数据结构与算法的课程设置基本上有三种情况：

（1）只开设《数据结构》课程，没有开设算法课程；

（2）开设《数据结构与算法》课程，将数据结构与算法的内容在一门课程中讲授；

（3）同时开设《数据结构》和《算法设计与分析》（或《算法基础》）两门课程。

目前的发展趋势是越来越倾向于第三种方式。无论哪种课程设置方法，数据结构在整个课程体系中都是处于承上启下的核心地位。作为程序设计语言后续课程的数据结构课程是对程序设计语言的重要补充和发展，同时为进一步学习操作系统、编译原理、数据库等专业课奠定坚实的基础。它所讨论的知识内容、蕴含的技术方法、体现的思维方式，无论对进一步学习计算机科学与技术专业的其他课程，还是从事计算机领域的各项工作，都有着不可替代的作用。

立体化教材是一种新型的整体教学解决方案，它突破了以纸介质教材为知识传播载体的局限，是教材建设的一种创新。由清华大学出版社出版的数据结构立体化教材包括《数据结构（C++版）》、《数据结构（C++版）学习辅导和实验指导》、《数据结构（C++版）教师用书》、《数据结构（C++版）》教学课件和《数据结构（C++版）》教学网站。这套立体化教材提供了一种综合性、全方位的教学资源，最大限度地满足了教学需要。

本书作为《数据结构（C++版）》的配套教学参考书，针对数据结构课程的特点以及学生学习数据结构课程的认知规律，研究每个知识点的教学方法，将教材中无法表达的教学思路、教学设计和教学方法展现出来，对于每一章的教学内容按“本章教学要点→教学专题→教案和讲稿”组织，将“授之以渔”的教学目标揉在教学内容里、含在教学方法中、穿在教学过程中，达到“细雨润无声”的效果。用计算机术语讲，本章教学要点是对这一章的教学内容进行总体设计，教学专题是对这一

章的教学内容进行模块化处理，教案是对教学专题进行详细设计，讲稿是教学专题的具体实现。

需要声明的是，不同的学校有着不同的培养目标和定位，不同的教师有着不同的教学风格和方法，不同的学生有着不同的知识基础和能力，因此，本书只能起到“抛砖引玉”的作用，希望引起关于如何组织数据结构课程教学的讨论，并从讨论中获得更多的教学经验与体会。

参加本书编写的还有于德海、赵凤全、逄焕利、刘刚、陈志雨、徐立新、许家骐、李洋、李东明、金慧侠、许家成等老师，李万龙教授对本书的编写提出了很多有益的建议，在此表示感谢。

作者将多年的教学心得与体会总结出来，一方面希望能够指导年轻教师的数据结构课程教学，另一方面也希望和国内的同行们有一个交流的机会。欢迎同行专家和读者批评和指正，作者的电子邮件地址是wanghm@mail.ccut.edu.cn。

第0章  数据结构课程的教学组织 1

0.1  数据结构课程的特点 1

0.2  数据结构立体化教材 2

0.2.1 《数据结构（C++版）》 3

0.2.2 《数据结构（C++版）学习辅导和实验指导》 3

0.2.3 《数据结构（C++版）教师用书》 4

0.2.4 《数据结构（C++版）》教学课件 5

0.2.5 《数据结构（C++版）》教学网站 5

0.3  数据结构课程的教学方法 6

0.3.1  关于开课的讨论 6

0.3.2  数据结构课程的教学主线 7

0.3.3  基本概念的网状理解教学法 8

0.3.4  算法的抽象分级教学法 9

0.4  教学专题——开课 10

0.4.1  教案 10

0.4.2  讲稿 11

第1章  绪论 13

1.1  本章教学要点 13

1.2  教学专题1——数据结构的研究对象 14

1.2.1  教案 14

1.2.2  讲稿 15

1.3  教学专题2——数据结构的基本概念 19

1.3.1  教案 19

1.3.2  讲稿 20

1.4  教学专题3——算法的基本概念 25

1.4.1  教案 25

1.4.2  讲稿 26

1.5  教学专题4——算法分析 29

1.5.1  教案 29

1.5.2  讲稿 30

第2章  线性表 35

2.1  本章教学要点 35

2.2  教学专题1——线性表的逻辑结构 37

2.2.1  教案 37

2.2.2  讲稿 38

2.3  教学专题2——线性表的顺序存储结构及实现 40

2.3.1  教案 40

2.3.2  讲稿 41

2.4  教学专题3——线性表的链接存储结构及实现 49

2.4.1  教案 49

2.4.2  讲稿 50

2.5  教学专题4——线性表的其他存储方法 61

2.5.1  教案 61

2.5.2  讲稿 62

2.6  教学专题5——线性表的应用举例（约瑟夫环） 67

2.6.1  教案 67

2.6.2  讲稿 68

第3章  特殊线性表 73

3.1  本章教学要点 73

3.2  教学专题1——栈 75

3.2.1  教案 75

3.2.2  讲稿 77

3.3  教学专题2——队列 85

3.3.1  教案 85

3.3.2  讲稿 86

3.4  教学专题3——串 93

3.4.1  教案 93

3.4.2  讲稿 94

3.5  教学专题4——栈的应用举例（递归） 101

3.5.1  教案 101

3.5.2  讲稿 103

第4章  广义线性表 107

4.1  本章教学要点 107

4.2  教学专题1——数组 109

4.2.1  教案 109

4.2.2  讲稿 110

4.3  教学专题2——矩阵的压缩存储 113

4.3.1  教案 113

4.3.2  讲稿 114

4.4  教学专题3——广义表 122

4.4.1  教案 122

4.4.2  讲稿 123

4.5  教学专题4——数组的应用举例（幻方） 127

4.5.1  教案 127

4.5.2  讲稿 128

第5章  树和二叉树 131

5.1  本章教学要点 131

5.2  教学专题1——树的逻辑结构 132

5.2.1  教案 132

5.2.2  讲稿 134

5.3  教学专题2——树的存储结构 138

5.3.1  教案 138

5.3.2  讲稿 139

5.4  教学专题3——二叉树的逻辑结构 145

5.4.1  教案 145

5.4.2  讲稿 146

5.5  教学专题4——二叉树的存储结构及实现 152

5.5.1  教案 152

5.5.2  讲稿 154

5.6  教学专题5——线索链表 164

5.6.1  教案 164

5.6.2  讲稿 165

5.7  教学专题6——树、森林与二叉树之间的转换 170

5.7.1  教案 170

5.7.2  讲稿 171

5.8  教学专题7——二叉树的应用举例（哈夫曼树及哈夫曼编码） 174

5.8.1  教案 174

5.8.2  讲稿 175

5.9  教学专题8——树的应用举例（八枚硬币问题） 180

5.9.1  教案 180

5.9.2  讲稿 181

第6章  图 185

6.1  本章教学要点 185

6.2  教学专题1——图的逻辑结构 186

6.2.1  教案 186

6.2.2  讲稿 188

6.3  教学专题2——图的邻接矩阵存储结构及实现 195

6.3.1  教案 195

6.3.2  讲稿 197

6.4  教学专题3——图的邻接表存储结构及实现 201

6.4.1  教案 201

6.4.2  讲稿 202

6.5  教学专题4——图的其他存储结构及实现 207

6.5.1  教案 207

6.5.2  讲稿 208

6.6  教学专题5——图的连通性 210

6.6.1  教案 210

6.6.2  讲稿 211

6.7  教学专题6——图的应用举例（最小生成树） 214

6.7.1  教案 214

6.7.2  讲稿 215

6.8  教学专题7——图的应用举例（最短路径） 219

6.8.1  教案 219

6.8.2  讲稿 221

6.9  教学专题8——图的应用举例（AOV网与拓扑排序） 226

6.9.1  教案 226

6.9.2  讲稿 227

6.10  教学专题9——图的应用举例（AOE网与关键路径） 230

6.10.1  教案 230

6.10.2  讲稿 231

第7章  查找技术 235

7.1  本章教学要点 235

7.2  教学专题1——查找的基本概念 236

7.2.1  教案 236

7.2.2  讲稿 237

7.3  教学专题2——线性表的查找技术 240

7.3.1  教案 240

7.3.2  讲稿 241

7.4  教学专题3——二叉排序树 246

7.4.1  教案 246

7.4.2  讲稿 248

7.5  教学专题4——平衡二叉树 254

7.5.1  教案 254

7.5.2  讲稿 256

7.6  教学专题5——散列表的查找技术 259

7.6.1  教案 259

7.6.2  讲稿 261

第8章  排序技术 271

8.1  本章教学要点 271

8.2  教学专题1——排序的基本概念 272

8.2.1  教案 272

8.2.2  讲稿 274

8.3  教学专题2——直接插入排序 276

8.3.1  教案 276

8.3.2  讲稿 278

8.4  教学专题3——希尔排序 280

8.4.1  教案 280

8.4.2  讲稿 281

8.5  教学专题4——起泡排序 283

8.5.1  教案 283

8.5.2  讲稿 285

8.6  教学专题5——快速排序 288

8.6.1  教案 288

8.6.2  讲稿 289

8.7  教学专题6——简单选择排序 293

8.7.1  教案 293

8.7.2  讲稿 294

8.8  教学专题7——堆排序 296

8.8.1  教案 296

8.8.2  讲稿 297

8.9  教学专题8——归并排序 302

8.9.1  教案 302

8.9.2  讲稿 303

8.10  教学专题9——各种排序方法的比较 308

8.10.1  教案 308

8.10.2  讲稿 309

第9章  索引技术 311

9.1  本章教学要点 311

9.2  教学专题1——索引的基本概念 312

9.2.1  教案 312

9.2.2  讲稿 313

9.3  教学专题2——线性索引技术 314

9.3.1  教案 314

9.3.2  讲稿 316

9.4  教学专题3——2-3树 319

9.4.1  教案 319

9.4.2  讲稿 321

9.5  教学专题4——B－树和B＋树 324

9.5.1  教案 324

9.5.2  讲稿 326

参考文献 331

XII

IX

XI