本书作为《数据结构——从概念到C++实现》的配套教师用书，针对数据结构课程的特点以及学生学习数据结构课程的认知规律，展现教材中无法表达的教学思路、教学设计和教学方法。按“本章教学要点→教学专题→教案和讲稿”组织，将“授之以渔”的教学目标揉在教学内容里、含在教学方法中、穿在教学过程中，达到“细雨润无声”的效果。为了便于教师开展混合式教学，书中提供了随堂练习、作业、课件等电子资源，扫描二维码即可使用。

前

言

《数据结构（C++版）》（王红梅编著，清华大学出版社）第1 版于2005 年7 月出版，第2 版于2011 

年6 月出版，第3 版更名为《数据结构——从概念到C++实现》于2019 年5 月出版，国内有超过100 

所院校将《数据结构（C++版）》或《数据结构——从概念到C++实现》作为主讲教材。本书是《数据

结构——从概念到C++实现》的配套教学参考书。本书的编写者长期从事算法与程序设计课程群，尤其

是数据结构课程的研究和教学，深切理解学生在学习数据结构过程中遇到的问题和困惑，深入探究掌握

数据结构的有效途径和方法，深刻思考数据结构对培养程序设计和计算思维的地位与作用，深度把握课

程的教学目标和重点难点，编写的教材能够切实把握数据结构的知识脉络，讲解深入浅出，教师易教学

生易学。

这本教师用书针对数据结构课程的特点以及学生学习数据结构课程的认知规律，研究每个知识点的

教学方法，对于每一章的教学内容按“本章教学要点→教学专题→教案（教学过程设计）→课件及教学

设计”的路径逐步展开，将教材中无法表达的教学思路、教学设计和教学方法展现出来，将“授之以渔”

的教学目标揉在教学内容中，含在教学方法中，穿在教学过程中，达到“润物细无声”的效果。用计算

机术语讲，“本章教学要点”是对这一章的教学内容进行总体设计，“教学专题”是对这一章的教学内容

进行模块化处理，“教案”体现的教学过程设计是对教学专题进行详细设计，“课件及教学设计”是教学

专题的具体实现。

需要声明的是，不同的学校有着不同的培养目标和定位，不同的教师有着不同的教学风格和方法，

不同的学生有着不同的知识基础和能力，因此，本书只能起到“抛砖引玉”的作用，希望引起关于如何

组织数据结构课程教学的讨论，并从讨论中获得更多的教学经验与体会。

参加本书编写的还有刘钢、王涛、肖巍、党源源、刘冰等老师，李万龙教授对本书的编写提出了很

多有益的建议，在此表示感谢。

作者将多年的教学心得与体会总结出来，一方面希望能够指导年轻教师的数据结构课程教学，另一

方面也希望和国内的同行有一个交流的机会。欢迎同行专家和读者批评指正，作者的电子邮箱是

wanghongmei@mail.ccut.edu.cn 。

作 者 

2020 年1 月于长春

目

录

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

0.1 数据结构课程的教学内容及特点.1

0.1.1 数据结构课程的教学内容 1

0.1.2 数据结构课程的教学特点 .2

0.2 数据结构课程的教学方法3

0.2.1 关于开课的讨论3 

0.2.2 数据结构课程的教学主线 4 

0.2.3 基本概念的网状理解教学法 .5 

0.2.4 算法的抽象分级教学法 6 

0.3 教学专题——开课7

0.3.1 教学过程设计

7 

0.3.2 课件及教学设计

8 

0.3.3 教学大纲 . 11

第1 章绪论 . 17

1.1 本章教学要点 . 17

1.1.1 知识点的组织结构17

1.1.2 教学提示 . 17

1.2 教学专题1——问题求解与程序设计.18

1.2 1 教学过程设计18

1.2.2 课件及教学设计19

1.2.3 随堂小测验26

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

1.3.1 教学过程设计26

1.3.2 课件及教学设计27

1.3.3 随堂小测验32

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

1.4.1 教学过程设计33

1.4.2 课件及教学设计34

1.4.3 随堂小测验38

1.5 教学专题4——算法分析.39

1.5.1 教学过程设计39

1.5.2 课件及教学设计40



数据结构（从概念到C++实现）教师用书

1.5.3 随堂小测验45

1.6 本章课后作业 . 46

第2 章线性表 48

2.1 本章教学要点 . 48

2.1.1 知识点的组织结构48

2.1.2 教学提示 . 48

2.2 教学专题1——引言.49

2.2.1 教学过程设计49

2.2.2 课件及教学设计50

2.3 教学专题2——线性表的逻辑结构.52

2.3.1 教学过程设计52

2.3.2 课件及教学设计53

2.3.3 随堂小测验55

2.4 教学专题3——线性表的顺序存储结构及实现.55

2.4.1 教学过程设计55

2.4.2 课件及教学设计56

2.4.3 随堂小测验61

2.5 教学专题4——线性表的链接存储结构及实现.61

2.5.1 教学过程设计61

2.5.2 课件及教学设计63

2.5.3 随堂小测验74

2.6 教学专题5——顺序表和链表的比较.75

2.6.1 教学过程设计75

2.6.2 课件及教学设计76

2.6.3 随堂小测验77

2.7 本章课后作业 . 77

第3 章栈和队列  80

3.1 本章教学要点 . 80

3.1.1 知识点的组织结构80

3.1.2 教学提示 . 81

3.2 教学专题1——引言.82

3.2.1 教学过程设计82

3.2.2 课件及教学设计83

3.3 教学专题2——栈.86

3.3.1 教学过程设计86

3.3.2 课件及教学设计87



3.3.3 随堂小测验91

3.4 教学专题3——队列.92

3.4.1 教学过程设计92

3.4.2 课件及教学设计93

3.4.3 随堂小测验99

3.5 本章课后作业 . 100

第4 章字符串和多维数组.101 

4.1 本章教学要点 . 101

4.1.1 知识点的组织结构101 

4.1.2 教学提示101 

4.2 教学专题1——引言.102

4.2.1 教学过程设计102 

4.2.2 课件及教学设计103 

4.3 教学专题2——字符串.106

4.3.1 教学过程设计106 

4.3.2 课件及教学设计107 

4.3.3 随堂小测验115

4.4 教学专题3——多维数组.115

4.4.1 教学过程设计115

4.4.2 课件及教学设计116

4.4.3 随堂小测验119

4.5 教学专题4——矩阵的压缩存储.119

4.5.1 教学过程设计119

4.5.2 课件及教学设计120 

4.5.3 随堂小测验124 

4.6 本章课后作业 . 125

第5 章树和二叉树  126 

5.1 本章教学要点 . 126

5.1.1 知识点的组织结构126 

5.1.2 教学提示126 

5.2 教学专题1——引言.127

5.2.1 教学过程设计127 

5.2.2 课件及教学设计128 

5.3 教学专题2——树的逻辑结构.130

5.3.1 教学过程设计130 

5.3.2 课件及教学设计131 



数据结构（从概念到C++实现）教师用书

5.3.3 随堂小测验135 

5.4 教学专题3——树的存储结构.136

5.4.1 教学过程设计136 

5.4.2 课件及教学设计137 

5.4.3 随堂小测验141 

5.5 教学专题4——二叉树的逻辑结构.142

5.5.1 教学过程设计142 

5.5.2 课件及教学设计143 

5.5.3 随堂小测验149 

5.6 教学专题5——二叉树的存储结构及实现.149

5.6.1 教学过程设计149 

5.6.2 课件及教学设计151 

5.6.3 随堂小测验155 

5.7 教学专题6——森林.157

5.7.1 教学过程设计157 

5.7.2 课件及教学设计158 

5.7.3 随堂小测验161 

5.8 教学专题7——最优二叉树.161

5.8.1 教学过程设计161 

5.8.2 课件及教学设计163 

5.8.3 随堂小测验167 

5.9 本章课后作业 . 168 

第6 章图 . 170 

6.1 本章教学要点 . 170

6.1.1 知识点的组织结构170 

6.1.2 教学提示170 

6.2 教学专题1——引言.171

6.2.1 教学过程设计171 

6.2.2 课件及教学设计172 

6.3 教学专题2——图的逻辑结构.174

6.3.1 教学过程设计174 

6.3.2 课件及教学设计175 

6.3.3 随堂小测验182 

6.4 教学专题3——图的邻接矩阵存储结构及实现.183

6.4.1 教学过程设计183 

6.4.2 课件及教学设计185 

6.4.3 随堂小测验189 



VII 

6.5 教学专题4——图的邻接表存储结构及实现.190

6.5.1 教学过程设计190 

6.5.2 课件及教学设计191 

6.5.3 随堂小测验196 

6.6 教学专题5——Prim 算法 197

6.6.1 教学过程设计197 

6.6.2 课件及教学设计198 

6.6.3 随堂小测验202 

6.7 教学专题6——Kruskal 算法 .204

6.7.1 教学过程设计204 

6.7.2 课件及教学设计205 

6.7.3 随堂小测验209 

6.8 教学专题7——Dijkstra 算法.210

6.8.1 教学过程设计210 

6.8.2 课件及教学设计211 

6.8.3 随堂小测验214 

6.9 教学专题8——Floyd 算法 216

6.9.1 教学过程设计216 

6.9.2 课件及教学设计217 

6.9.3 随堂小测验219 

6.10 教学专题9——拓扑排序.219 

6.10.1 教学过程设计219

6.10.2 课件及教学设计221

6.10.3 随堂小测验223

6.11 教学专题10——关键路径.225

6.11.1 教学过程设计 225 

6.11.2 课件及教学设计 226 

6.11.3 随堂小测验 229 

6.12 本章课后作业 . 230 

第7 章查找技术  233 

7.1 本章教学要点 . 233

7.1.1 知识点的组织结构233 

7.1.2 教学提示233 

7.2 教学专题1——查找概述.234

7.2.1 教学过程设计234 

7.2.2 课件及教学设计235 

7.2.3 随堂小测验237 



数据结构（从概念到C++实现）教师用书

7.3 教学专题2——顺序查找.237

7.3.1 教学过程设计237 

7.3.2 课件及教学设计238 

7.3.3 随堂小测验240 

7.4 教学专题3——折半查找.240

7.4.1 教学过程设计240 

7.4.2 课件及教学设计241 

7.4.3 随堂小测验244 

7.5 教学专题4——二叉排序树.245

7.5.1 教学过程设计245 

7.5.2 课件及教学设计246 

7.5.3 随堂小测验251 

7.6 教学专题5——平衡二叉树.252

7.6.1 教学过程设计252 

7.6.2 课件及教学设计253 

7.6.3 随堂小测验257 

7.7 教学专题6——B 树 .258

7.7.1 教学过程设计258 

7.7.2 课件及教学设计259 

7.7.3 随堂小测验265 

7.8 教学专题7——散列表.266

7.8.1 教学过程设计266 

7.8.2 课件及教学设计267 

7.8.3 随堂小测验275 

7.9 本章课后作业 . 276 

第8 章排序技术  278 

8.1 本章教学要点 . 278

8.1.1 知识点的组织结构278 

8.1.2 教学提示278 

8.2 教学专题1——排序概述.279

8.2.1 教学过程设计279 

8.2.2 课件及教学设计280 

8.2.3 随堂小测验282 

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

8.3.1 教学过程设计282 

8.3.2 课件及教学设计283 

8.3.3 随堂小测验286 



IX 

8.4 教学专题3——希尔排序.287

8.4.1 教学过程设计287 

8.4.2 课件及教学设计288 

8.4.3 随堂小测验291 

8.5 教学专题4——起泡排序.291

8.5.1 教学过程设计291 

8.5.2 课件及教学设计292 

8.5.3 随堂小测验295 

8.6 教学专题5——快速排序.296

8.6.1 教学过程设计296 

8.6.2 课件及教学设计297 

8.6.3 随堂小测验300 

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

8.7.1 教学过程设计301 

8.7.2 课件及教学设计302 

8.7.3 随堂小测验304 

8.8 教学专题7——堆排序.305

8.8.1 教学过程设计305 

8.8.2 课件及教学设计306 

8.8.3 随堂小测验310 

8.9 教学专题8——归并排序.312

8.9.1 教学过程设计312 

8.9.2 课件及教学设计313 

8.9.3 随堂小测验316 

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

8.10.1 教学过程设计317

8.10.2 课件及教学设计318

8.10.3 随堂小测验320

8.11 本章课后作业 . 320

l定位准确  本书定位于普通高校数据结构课程的教学，依据普通高校计算机专业培养方案，紧扣课程教学大纲。

l体例独创  教案以课题为单位，分为教案（简案）和讲稿（详案）两部分。教案承载的是课堂教学的组织管理信息，其思路的形成受教学过程的管理逻辑支配；讲稿承载的是知识信息，其思路的形成受教学过程的知识逻辑支配。

l突出教学设计  在教案中通过教学过程设计，从宏观上管理教学过程；在讲稿中通过教学设计，从教学细节上指导教学过程。

l贯穿教学方法  启发式教学方法贯穿始终，在教学设计中设计了大量的问题，通过分析问题、提出问题、解决问题的过程，培养学生逻辑思维和抽象思维能力。

l集作者的观念、知识、经验之大成  本书作者是省级教学名师，长期从事数据结构的教学，是“数据结构”省级精品课的主讲教师，“数据结构课程改革与实践” 省级优秀教学成果奖的获得者，有丰富的第一线教学经验和体会，对教学有较深刻的理解和把握，对教师的教学需要和学生的认知规律有较深刻的理解和把握。对数据结构课程的教学更是研究深，造诣高。本书中，作者把其经验、体会无私奉献给同行和读者。

王红梅，女，50岁，教授，硕士生导师，省级教学名师，吉林省巾帼建功标兵，长春工业大学计算机科学与工程学院院长，长春工业大学教学卓越奖获得者，从事计算机专业教学工作22年，出版了《数据结构（C++版）》、《计算机学科概论》、《程序设计基础》、《算法设计与分析》等教材，均被评为“十二五”国家级规划教材，获省级教学成果奖一等奖1项、二等奖2项、三等奖2项，发表学术论文30余篇。