数据结构（C++版）教师用书

定　　价：29 元

丛书名：普通高校本科计算机专业特色教材精选·算法与程序设计

• 作者：王红梅、胡明、王涛
• 出版时间：2007/10/1
• ISBN：9787302151289
• 出 版 社：清华大学出版社

• 中图法分类：TP311.12 
• 纸张：胶版纸
• 版次：1
• 开本：16
• 字数：(单位：千字)

内容简介

本书作为王红梅等编著、清华大学出版社出版的《数据结构（C++版）》配套教学参考书，针对数据结构课程的特点以及学生学习数据结构课程的认知规律，研究每个知识点的教学方法，将教材中无法表达的教学思路、教学设计和教学方法展现出来，对于每一章的教学内容按“本章教学要点→教学专题→教案和讲稿”组织。
本书可供从事数据结构及相关课程教学的教师作为教学参考书，也可供计算机专业的学生作为学习参考书，同时也为大学教案的编写提供了一个可参考的模板。
本书封面贴有清华大学出版社防伪标签，无标签者不得销售。

序 言

我国高等教育逐步实现大众化后，越来越多的高等学校将会面向国民经济发展的第一线，为行业、企业培养各级各类高级应用型专门人才。为此，教育部已经启动了“高等学校教学质量和教学改革工程”，强调要以信息技术为手段，深化教学改革和人才培养模式改革。如何根据社会的实际需要，根据各行各业的具体人才需求，培养具有特色显著的人才，是我们共同面临的重大问题。具体地说，培养具有一定专业特色的和特定能力强的计算机专业应用型人才则是计算机教育要解决的问题。
为了适应21世纪人才培养的需要，培养具有特色的计算机人才，急需一批适合各种人才培养特点的计算机专业教材。目前，一些高校在计算机专业教学和教材改革方面已经做了大量工作，许多教师在计算机专业教学和科研方面已经积累了许多宝贵经验。将他们的教研成果转化为教材的形式，向全国其他学校推广，对于深化我国高等学校的教学改革是一件十分有意义的事情。
清华大学出版社在经过大量调查研究的基础上，决定组织出版一套“普通高校本科计算机专业特色教材精选”。本套教材是针对当前高等教育改革的新形势，以社会对人才的需求为导向，主要以培养应用型计算机人才为目标，立足课程改革和教材创新，广泛吸纳全国各地的高等院校计算机优秀教师参与编写，从中精选出版确实反映计算机专业教学方向的特色教材，供普通高等院校计算机专业学生使用。
本套教材具有以下特点。
1. 编写目的明确
本套教材是在深入研究各地各学校办学特色的基础上，面向普通高校的计算机专业学生编写的。学生通过本套教材，主要学习计算机科学与技术专业的基本理论和基本知识，接受利用计算机解决实际问题的基本训练，培养研究和开发计算机系统，特别是应用系统的基本能力。

2. 理论知识与实践训练相结合
根据计算学科的三个学科形态及其关系，本套教材力求突出学科的理论与实践紧密结合的特征，结合实例讲解理论，使理论来源于实践，又进一步指导实践。学生通过实践深化对理论的理解，更重要的是使学生学会理论方法的实际运用。在编写教材时突出实用性，并做到通俗易懂，易教易学，使学生不仅知其然，知其所以然，还要会其如何然。
3. 注意培养学生的动手能力
每种教材都增加了能力训练部分的内容，学生通过学习和练习，能比较熟练地应用计算机知识解决实际问题。既注重培养学生分析问题的能力，也注重培养学生解决问题的能力，以适应新经济时代对人才的需要，满足就业要求。
4. 注重教材的立体化配套
大多数教材都将陆续配套教师用课件、习题及其解答提示，学生上机实验指导等辅助教学资源，有些教材还提供能用于网上下载的文件，以方便教学。
由于各地区各学校的培养目标、教学要求和办学特色均有所不同，所以对特色教学的理解也不尽一致，我们恳切希望大家在使用教材的过程中，及时地给我们提出批评和改进意见，以便我们做好教材的修订改版工作，使其日趋完善。
我们相信经过大家的共同努力，这套教材一定能成为特色鲜明、质量上乘的优秀教材。同时，我们也希望通过本套教材的编写出版，为“高等学校教学质量和教学改革工程”做出贡献。
在我国，数据结构与算法的课程设置基本上有三种情况：
（1）只开设《数据结构》课程，没有开设算法课程；
（2）开设《数据结构与算法》课程，将数据结构与算法的内容在一门课程中讲授；
（3）同时开设《数据结构》和《算法设计与分析》（或《算法基础》）两门课程。
目前的发展趋势是越来越倾向于第三种方式。无论哪种课程设置方法，数据结构在整个课程体系中都是处于承上启下的核心地位。作为程序设计语言后续课程的数据结构课程是对程序设计语言的重要补充和发展，同时为进一步学习操作系统、编译原理、数据库等专业课奠定坚实的基础。它所讨论的知识内容、蕴含的技术方法、体现的思维方式，无论对进一步学习计算机科学与技术专业的其他课程，还是从事计算机领域的各项工作，都有着不可替代的作用。
立体化教材是一种新型的整体教学解决方案，它突破了以纸介质教材为知识传播载体的局限，是教材建设的一种创新。由清华大学出版社出版的数据结构立体化教材包括《数据结构（C++版）》、《数据结构（C++版）学习辅导和实验指导》、《数据结构（C++版）教师用书》、《数据结构（C++版）》教学课件和《数据结构（C++版）》教学网站。这套立体化教材提供了一种综合性、全方位的教学资源，最大限度地满足了教学需要。
本书作为《数据结构（C++版）》的配套教学参考书，针对数据结构课程的特点以及学生学习数据结构课程的认知规律，研究每个知识点的教学方法，将教材中无法表达的教学思路、教学设计和教学方法展现出来，对于每一章的教学内容按“本章教学要点→教学专题→教案和讲稿”组织，将“授之以渔”的教学目标揉在教学内容里、含在教学方法中、穿在教学过程中，达到“细雨润无声”的效果。用计算机术语讲，本章教学要点是对这一章的教学内容进行总体设计，教学专题是对这一
章的教学内容进行模块化处理，教案是对教学专题进行详细设计，讲稿是教学专题的具体实现。
需要声明的是，不同的学校有着不同的培养目标和定位，不同的教师有着不同的教学风格和方法，不同的学生有着不同的知识基础和能力，因此，本书只能起到“抛砖引玉”的作用，希望引起关于如何组织数据结构课程教学的讨论，并从讨论中获得更多的教学经验与体会。
参加本书编写的还有于德海、赵凤全、逄焕利、刘刚、陈志雨、徐立新、许家骐、李洋、李东明、金慧侠、许家成等老师，李万龙教授对本书的编写提出了很多有益的建议，在此表示感谢。
作者将多年的教学心得与体会总结出来，一方面希望能够指导年轻教师的数据结构课程教学，另一方面也希望和国内的同行们有一个交流的机会。欢迎同行专家和读者批评和指正，作者的电子邮件地址是[e-mail]。

目 录

第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