为了配合数据结构课程的教学，加强读者对数据结构算法实际应用技能的训练，提高读者分析问题和解决问题的能力，本书选取并讨论了多个方面应用的课程设计。全书共分10章，给出了与数据结构内容相关的知识解析、算法分析以及课程设计，描述了相关数据结构的存储表示及其实际应用的操作算法，对用类C语言描述的各种算法进行了详细的注释和性能分析，并对各应用的解题思路、方法进行了较详细的分析。全书特别注重对实践应用问题的分析和理解，内容丰富，概念清楚，通俗易懂。
独立于具体的数据结构教科书，重点放在数据的存储以及在此存储结构上所实现的各种重要和典型的算法上。
结合实际应用的要求，使课程设计既覆盖知识点，又接近工程实际需要。
通过详细的实例分析和循序渐进的描述，启发学生完成设计。
提供了几个较大的综合课程设计实例，以进一步锻炼学生的动手能力。
课程设计可以充分弥补课堂教学和实验中知识深度和广度有限的问题，更好地帮助学生系统掌握该门课程的主要内容。通过课程设计的综合训练，能培养学生实际分析问题、编程和动手的能力，帮助学生系统掌握该门课程的主要内容，更好地完成教学任务。
自2005年本书第1版出版以来，广获好评，多次重印，在听取了许多读者的意见之后，又出版了第2版。为了帮助学生理解数据结构中的算法知识，提高学生分析问题和解决问题的能力，第2版对数据结构中的主要知识进行了归纳和解析，对与课程设计相关的算法进行了实例分析。
本书特点
数据结构是计算机专业的必修、主干课程之一，它旨在使读者学会分析、研究计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中，解题能力和技巧的训练是一个重要的环节。为了指导和帮助读者更好地学习、实践数据结构这门课程，帮助教师讲授“数据结构”课程，满足指导和评价“课程设计”的需要，我们编写了这本书。
作者在长期讲授数据结构这门课程的过程中体会到，每次在布置课程设计或作业时，总是要冥思苦想，对选什么样的题、如何评分等难以定夺；而读者也对如何利用书本中的基本知识和方法解决一些实际问题，以及对问题的求解进行算法设计感到难以下手。实践证明，理解课程内容与较好地解决实际问题之间存在着明显差距，而算法设计完成的质量与基本的程序设计素质的培养是密切相关的。要想理解和巩固所学的基本概念、原理和方法，牢固地掌握所学的基本知识、基本技能，达到融会贯通、举一反三的目的，就必须多做、多练、多见（见多识广）。正是为了达到上述目的，本书中通过一些实际的应用，对一些重要的数据结构和算法进行解读。经过循序渐进地训练，就可以使读者掌握更多的程序设计技巧和方法，提高分析问题、解决问题的能力。
本书遵循数据结构课程的教学大纲要求，内容共分10章：第0章是绪论，简要介绍后9章中各课程设计的内容概要，以便作为后面学习的引导；第1章是链表的应用，用三个课程设计实例来讨论单链表和单循环链表的存储结构及相关算法的分析和应用；第2章是栈和队列的应用，用两个设计实例讨论栈和队列的存储结构以及栈、队列、回溯等概念的应用；第3章是文本文件的检索，本章用了一个文本检索的设计实例，将串的存储结构、串的各种操作都蕴涵其中；第4章有两个方面的内容，一个是稀疏矩阵的存储及运算，另一个是广义表的各种操作的实现；第5章是树结构的应用，本章主要涉及树、二叉树的存储结构及其遍历，以及赫夫曼树和赫夫曼编码的生成及其应用；第6章是图结构的应用，这一章中讨论了一个非常有实用价值的图结构应用实例，即交通网络中的最短路径问题；第7章用一个课程设计实例讨论了各种排序算法的具体实现和应用；第8章讨论排序和查找两个方面的应用实例；第9章是文件的应用，它是一个综合的应用设计，不仅用到文件的概念，还用到静态链表和数组等存储结构，也用到了排序、查找等概念。
为了提高学生分析问题和解决问题的能力，在每章中都对数据结构中的主要知识进行了归纳和解析，对与课程设计相关的算法进行了实例分析。而且，每章中都选择了一两个课程设计实例，这些设计内容丰富、涉及面广、难易适当，能给学习数据结构这门课程的读者以启发，达到让读者掌握相关知识和开阔视野的目的。因此，对书中大部分设计题目都做了解析，并给出了参考算法和源程序代码。
本书由苏仕华、魏韦巍、王敬生和刘燕君共同编写，魏韦巍还负责全书所有课程设计实例的程序调试和验证工作。为了确保程序质量，苏仕华和刘燕君又在春节期间对全部程序进行了验证与优化。
在本书的编写过程中，得到了中国科学技术大学计算机系黄刘生教授、自动化系刘振安教授的大力支持和帮助，他们对本书的编写提出了许多宝贵的意见。另外，本书还参考了大量作者的书籍和资料等，在此致以诚挚的谢意。
由于作者水平有限、时间仓促，书中难免存在缺点和错误，殷切希望广大读者及同行们批评指正。
编 者
2010年2月于合肥
计算机\数据结构
课程设计可以充分弥补课堂教学和实验中知识深度和广度有限的问题，更好地帮助学生系统地掌握该门课程的主要内容。通过课程设计的综合训练，能培养学生实际分析问题、编程和动手的能力，帮助学生系统掌握该门课程的主要内容，更好地完成教学任务。
自2005年本书第1版出版以来，广获好评，多次重印，在听取了许多读者的意见之后，又出版了第2版。为了帮助学生理解数据结构中的算法知识，提高学生分析问题和解决问题的能力，第2版对数据结构中的主要知识进行了归纳和解析，对与课程设计相关的算法进行了实例分析。
本书特点
? 独立于具体的数据结构教科书，重点放在数据的存储以及在此存储结构上所实现的各种重要和典型的算法上。
? 结合实际应用的要求，使课程设计既覆盖知识点，又接近工程实际需要。
? 通过详细的实例分析和循序渐进的描述，启发学生完成设计。
? 提供了几个较大的综合课程设计，以进一步锻炼学生的动手能力。
专家指导委员会
前言
第0章 绪论 1
0.1 课程设计特点 1
0.2 课程设计结构 1
第1章 链表的应用 5
1.1 知识解析 5
1.1.1 线性表的基础知识 5
1.1.2 线性表的基本运算 7
1.2 算法设计与分析 9
1.2.1 顺序表上的相关操作 9
1.2.2 线性链表上相关操作的算法
及其分析 11
1.3 一元多项式的运算 13
1.3.1 问题分析 14
1.3.2 算法解析 14
1.3.3 完整程序清单 17
1.3.4 程序运行测试 19
1.4 通讯录管理系统的设计与实现 20
1.4.1 问题分析 20
1.4.2 系统设计 21
1.4.3 完整程序清单 27
1.4.4 程序运行测试 32
1.5 约瑟夫生者死者游戏 35
1.5.1 问题分析 35
1.5.2 程序实现 37
1.5.3 程序运行测试 39
1.6 评价标准 39
第2章 栈和队列的应用 40
2.1 知识解析 40
2.1.1 栈和队列的基本概念 40
2.1.2 栈和队列的基本运算 41
2.1.3 栈和队列的存储结构 41
2.2 算法设计与分析 45
2.2.1 栈的特性 45
2.2.2 循环队列的特点 45
2.2.3 栈的应用举例 46
2.3 八皇后问题 48
2.3.1 设计要求与分析 48
2.3.2 算法求精 49
2.3.3 算法扩充 50
2.3.4 完整的算法实现 51
2.4 表达式求值问题 53
2.4.1 设计要求与分析 54
2.4.2 中缀表达式到后缀表达式的
转换 54
2.4.3 后缀表达式的计算 56
2.4.4 表达式运算算法的实现 57
2.5 评价标准 61
第3章 文本文件的检索 62
3.1 知识解析 62
3.1.1 串的概念 62
3.1.2 顺序串 62
3.1.3 链串 63
3.1.4 串运算的实现 63
3.2 算法设计与分析 65
3.3 串模式匹配算法的设计与实现 67
3.3.1 设计要求 67
3.3.2 算法分析与设计 67
3.3.3 调用算法实例 68
3.4 文本文件单词的检索与计数 69
3.4.1 设计要求与分析 69
3.4.2 设计实例的实现 70
3.5 评价标准 74
第4章 稀疏矩阵和广义表 75
4.1 知识解析 75
4.1.1 多维数组 75
4.1.2 特殊矩阵 76
4.1.3 广义表 77
4.2 算法设计与分析 78
4.2.1 矩阵运算 78
4.2.2 广义表运算 80
4.3 稀疏矩阵的压缩存储和运算 80
4.3.1 设计要求与分析 80
4.3.2 设计实例 81
4.3.3 完整的程序实现 83
4.4 广义表的运算 84
4.4.1 设计要求 84
4.4.2 算法分析 85
4.4.3 算法实现 87
4.4.4 运行测试实例 89
4.5 评价标准 92
第5章 树结构的应用 93
5.1 知识解析 93
5.1.1 树的概念和术语 93
5.1.2 二叉树概述 93
5.1.3 二叉树的运算 94
5.1.4 线索二叉树 96
5.1.5 树和森林 98
5.1.6 赫夫曼树 99
5.2 算法设计与分析 100
5.2.1 二叉树的遍历 100
5.2.2 赫夫曼树 101
5.2.3 二叉树上的其他运算 102
5.3 求二叉树上结点的路径 104
5.3.1 设计要求与分析 104
5.3.2 设计实例 105
5.3.3 算法运行实例 109
5.4 赫夫曼编码的应用 112
5.4.1 设计要求与分析 112
5.4.2 赫夫曼树的建立 112
5.4.3 赫夫曼编码 114
5.4.4 代码文件的译码 115
5.4.5 算法运行实例 116
5.5 评价标准 120
第6章 图结构的应用 121
6.1 知识解析 121
6.1.1 图的基本术语 121
6.1.2 图的存储表示方式 122
6.1.3 图的基本运算 123
6.1.4 拓扑排序法 126
6.2 算法设计与分析 126
6.2.1 图的存储表示 126
6.2.2 图的遍历 127
6.2.3 顶点之间的最短路径 129
6.3 交通咨询系统设计 130
6.3.1 设计要求与分析 130
6.3.2 设计功能的实现 131
6.3.3 主控程序 133
6.3.4 运行实例 134
6.4 评价标准 138
第7章 排序算法的应用 140
7.1 知识解析 140
7.1.1 排序的基本概念 140
7.1.2 常用排序方法 141
7.1.3 各种排序方法比较 142
7.2 算法实现思路 143
7.2.1 插入排序 143
7.2.2 交换排序 144
7.2.3 选择排序 146
7.2.4 分配排序 149
7.3 学生成绩处理 150
7.3.1 设计要求与分析 150
7.3.2 算法设计源程序 151
7.3.3 主控程序 156
7.3.4 运行实例 157
7.4 评价标准 159
第8章 查找算法的应用 160
8.1 知识解析 160
8.1.1 顺序表的查找 160
8.1.2 二叉排序树 162
8.1.3 散列表的查找 163
8.2 算法设计与分析 166
8.2.1 有序表上的顺序查找 167
8.2.2 查找算法分析 167
8.3 航班信息的查询与检索 168
8.3.1 设计要求 168
8.3.2 设计分析 169
8.3.3 算法实现 170
8.3.4 源程序清单 172
8.3.5 运行测试实例 177
8.4 评价标准 179
第9章 文件的应用 181
9.1 知识解析 181
9.1.1 文件的基本概念 181
9.1.2 常用的文件结构 182
9.2 文件实例分析 184
9.3 图书管理信息系统的设计与实现 186
9.3.1 设计要求 186
9.3.2 设计分析 187
9.3.3 设计的实现 191
9.3.4 主控菜单的设计 200
9.3.5 运行测试实例 202
9.4 评价标准 207
参考文献 208
