数据结构课程设计
2010-3
机械工业出版社
苏仕华 等 著
207
数据结构是计算机专业的必修、主干课程之一，它旨在使读者学会分析、研究计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中，解题能力和技巧的训练是一个重要的环节。为了指导和帮助读者更好地学习、实践数据结构这门课程，帮助教师讲授“数据结构”课程，满足指导和评价“课程设计”的需要，我们编写了这本书。 作者在长期讲授数据结构这门课程的过程中体会到，每次在布置课程设计或作业时，总是要冥思苦想，对选什么样的题、如何评分等难以定夺；而读者也对如何利用书本中的基本知识和方法解决一些实际问题，以及对问题的求解进行算法设计感到难以下手。实践证明，理解课程内容与较好地解决实际问题之间存在着明显差距，而算法设计完成的质量与基本的程序设计素质的培养是密切相关的。要想理解和巩固所学的基本概念、原理和方法，牢固地掌握所学的基本知识、基本技能，达到融会贯通、举一反三的目的，就必须多做、多练、多见（见多识广）。正是为了达到上述目的，本书中通过一些实际的应用，对一些重要的数据结构和算法进行解读。经过循序渐进地训练，就可以使读者掌握更多的程序设计技巧和方法，提高分析问题、解决问题的能力。 本书遵循数据结构课程的教学大纲要求，内容共分10章：第0章是绪论，简要介绍后9章中各课程设计的内容概要，以便作为后面学习的引导；第1章是链表的应用，用三个课程设计实例来讨论单链表和单循环链表的存储结构及相关算法的分析和应用；第2章是栈和队列的应用，用两个设计实例讨论栈和队列的存储结构以及栈、队列、回溯等概念的应用；第3章是文本文件的检索，本章用了一个文本检索的设计实例，将串的存储结构、串的各种操作都蕴涵其中；第4章有两个方面的内容，一个是稀疏矩阵的存储及运算，另一个是广义表的各种操作的实现；第5章是树结构的应用，本章主要涉及树、二叉树的存储结构及其遍历，以及赫夫曼树和赫夫曼编码的生成及其应用；第6章是图结构的应用，这一章中讨论了一个非常有实用价值的图结构应用实例，即交通网络中的最短路径问题；第7章用一个课程设计实例讨论了各种排序算法的具体实现和应用；第8章讨论排序和查找两个方面的应用实例；第9章是文件的应用，它是一个综合的应用设计，不仅用到文件的概念，还用到静态链表和数组等存储结构，也用到了排序、查找等概念。 为了提高学生分析问题和解决问题的能力，在每章中都对数据结构中的主要知识进行了归纳和解析，对与课程设计相关的算法进行了实例分析。而且，每章中都选择了一两个课程设计实例，这些设计内容丰富、涉及面广、难易适当，能给学习数据结构这门课程的读者以启发，达到让读者掌握相关知识和开阔视野的目的。因此，对书中大部分设计题目都做了解析，并给出了参考算法和源程序代码。 本书由苏仕华、魏韦巍、王敬生和刘燕君共同编写，魏韦巍还负责全书所有课程设计实例的程序调试和验证工作。为了确保程序质量，苏仕华和刘燕君又在春节期间对全部程序进行了验证与优化。 在本书的编写过程中，得到了中国科学技术大学计算机系黄刘生教授、自动化系刘振安教授的大力支持和帮助，他们对本书的编写提出了许多宝贵的意见。另外，本书还参考了大量作者的书籍和资料等，在此致以诚挚的谢意。 由于作者水平有限、时间仓促，书中难免存在缺点和错误，殷切希望广大读者及同行们批评指正。
为了配合数据结构课程的教学，加强读者对数据结构算法实际应用技能的训练，提高读者分析问题和解决问题的能力，《数据结构课程设计（第2版）》选取并讨论了多个方面应用的课程设计。全书共分10章，给出了与数据结构内容相关的知识解析、算法分析以及课程设计，描述了相关数据结构的存储表示及其实际应用的操作算法，对用类C语言描述的各种算法进行了详细的注释和性能分析，并对各应用的解题思路、方法进行了较详细的分析。全书特别注重对实践应用问题的分析和理解，内容丰富，概念清楚，通俗易懂。 《数据结构课程设计（第2版）》可作为高等院校各类相关专业本科生、专科生学习数据结构的辅助教材以及实验指导用书，也可作为广大从事计算机软件与应用的工作人员及社会大众学习数据结构的参考用书。
专家指导委员会前言第0章 绪论 10.1 课程设计特点 10.2 课程设计结构 1第1章 链表的应用 51.1 知识解析 51.1.1 线性表的基础知识 51.1.2 线性表的基本运算 71.2 算法设计与分析 91.2.1 顺序表上的相关操作 91.2.2 线性链表上相关操作的算法 及其分析 111.3 一元多项式的运算 131.3.1 问题分析 141.3.2 算法解析 141.3.3 完整程序清单 171.3.4 程序运行测试 191.4 通讯录管理系统的设计与实现 201.4.1 问题分析 201.4.2 系统设计 211.4.3 完整程序清单 271.4.4 程序运行测试 321.5 约瑟夫生者死者游戏 351.5.1 问题分析 351.5.2 程序实现 371.5.3 程序运行测试 391.6 评价标准 39第2章 栈和队列的应用 402.1 知识解析 402.1.1 栈和队列的基本概念 402.1.2 栈和队列的基本运算 412.1.3 栈和队列的存储结构 412.2 算法设计与分析 452.2.1 栈的特性 452.2.2 循环队列的特点 452.2.3 栈的应用举例 462.3 八皇后问题 482.3.1 设计要求与分析 482.3.2 算法求精 492.3.3 算法扩充 502.3.4 完整的算法实现 512.4 表达式求值问题 532.4.1 设计要求与分析 542.4.2 中缀表达式到后缀表达式的 转换 542.4.3 后缀表达式的计算 562.4.4 表达式运算算法的实现 572.5 评价标准 61第3章 文本文件的检索 623.1 知识解析 623.1.1 串的概念 623.1.2 顺序串 623.1.3 链串 633.1.4 串运算的实现 633.2 算法设计与分析 653.3 串模式匹配算法的设计与实现 673.3.1 设计要求 673.3.2 算法分析与设计 673.3.3 调用算法实例 683.4 文本文件单词的检索与计数 693.4.1 设计要求与分析 693.4.2 设计实例的实现 703.5 评价标准 74第4章 稀疏矩阵和广义表 754.1 知识解析 754.1.1 多维数组 754.1.2 特殊矩阵 764.1.3 广义表 774.2 算法设计与分析 784.2.1 矩阵运算 784.2.2 广义表运算 804.3 稀疏矩阵的压缩存储和运算 804.3.1 设计要求与分析 804.3.2 设计实例 814.3.3 完整的程序实现 834.4 广义表的运算 844.4.1 设计要求 844.4.2 算法分析 854.4.3 算法实现 874.4.4 运行测试实例 894.5 评价标准 92第5章 树结构的应用 935.1 知识解析 935.1.1 树的概念和术语 935.1.2 二叉树概述 935.1.3 二叉树的运算 945.1.4 线索二叉树 965.1.5 树和森林 985.1.6 赫夫曼树 995.2 算法设计与分析 1005.2.1 二叉树的遍历 1005.2.2 赫夫曼树 1015.2.3 二叉树上的其他运算 1025.3 求二叉树上结点的路径 1045.3.1 设计要求与分析 1045.3.2 设计实例 1055.3.3 算法运行实例 1095.4 赫夫曼编码的应用 1125.4.1 设计要求与分析 1125.4.2 赫夫曼树的建立 1125.4.3 赫夫曼编码 1145.4.4 代码文件的译码 1155.4.5 算法运行实例 1165.5 评价标准 120第6章 图结构的应用 1216.1 知识解析 1216.1.1 图的基本术语 1216.1.2 图的存储表示方式 1226.1.3 图的基本运算 1236.1.4 拓扑排序法 1266.2 算法设计与分析 1266.2.1 图的存储表示 1266.2.2 图的遍历 1276.2.3 顶点之间的最短路径 1296.3 交通咨询系统设计 1306.3.1 设计要求与分析 1306.3.2 设计功能的实现 1316.3.3 主控程序 1336.3.4 运行实例 1346.4 评价标准 138第7章 排序算法的应用 1407.1 知识解析 1407.1.1 排序的基本概念 1407.1.2 常用排序方法 1417.1.3 各种排序方法比较 1427.2 算法实现思路 1437.2.1 插入排序 1437.2.2 交换排序 1447.2.3 选择排序 1467.2.4 分配排序 1497.3 学生成绩处理 1507.3.1 设计要求与分析 1507.3.2 算法设计源程序 1517.3.3 主控程序 1567.3.4 运行实例 1577.4 评价标准 159第8章 查找算法的应用 1608.1 知识解析 1608.1.1 顺序表的查找 1608.1.2 二叉排序树 1628.1.3 散列表的查找 1638.2 算法设计与分析 1668.2.1 有序表上的顺序查找 1678.2.2 查找算法分析 1678.3 航班信息的查询与检索 1688.3.1 设计要求 1688.3.2 设计分析 1698.3.3 算法实现 1708.3.4 源程序清单 1728.3.5 运行测试实例 1778.4 评价标准 179第9章 文件的应用 1819.1 知识解析 1819.1.1 文件的基本概念 1819.1.2 常用的文件结构 1829.2 文件实例分析 1849.3 图书管理信息系统的设计与实现 1869.3.1 设计要求 1869.3.2 设计分析 1879.3.3 设计的实现 1919.3.4 主控菜单的设计 2009.3.5 运行测试实例 2029.4 评价标准 207参考文献 208
1.6 评价标准 本章的设计是练习使用单链表结构实现有关链表的应用。设计中分了三个实验：第一个是一元多项式的运算，第二个是通讯录管理系统设计，第三个是约瑟夫生者死者游戏的实现。本章的主要目的是使同学们进一步熟悉和掌握线性链表的存储结构以及链表的相关操作，学会完成一个完整的应用程序的设计（算法分析、算法设计到最后的算法实现等）。本设计比较容易，也相对比较简单，目的是训练学生利用链表的知识来解决实际问题的能力，为今后的学习打好基础。同学们可以从中选择一个或两个实验，只要能保证程序运行全部正确，即可获得80-84分。 如果学生有自己的见解或发挥，可以考虑给予加分，一般可以加到85分以上，但应严格控制90分以上的学生人数。如果学生的程序存在局部问题，但有些地方又具有一定的创造性，则可以酌情考虑给75-79分。 如果有一个算法程序错误很多，成绩不能高于74分；若两个算法程序都有错误，则不能给予及格。如果仅是菜单上有问题，则可得75-79分。 单链表的操作还有许多，如链表的插入、链表的删除以及链表的查找等，同学们可以将此加入到第二个实验的程序中；另外，约瑟夫生者与死者游戏也可以用顺序表实现，这作为选做实验，同时可以作为另外加分的依据。
课程设计可以充分弥补课堂教学和实验中知识深度和广度有限的问题，更好地帮助学生系统掌握该门课程的主要内容。通过课程设计的综合训练，能培养学生实际分析问题、编程和动手的能力。帮助学生系统掌握该门课程的主要内容，更好地完成教学任务。 自2005年《数据结构课程设计（第2版）》第1版出版以来。广获好评，多次重印，在听取了许多读者的意见之后，又出版了第2版。为了帮助学生理解数据结构中的算法知识，提高学生分析问题和解决问题的能力，第2版对数据结构中的主要知识进行了归纳和解析，对与课程设计相关的算法进行了实例分析。 《数据结构课程设计（第2版）》特点 独立于具体的数据结构教科书，重点放在数据的存储以及在此存储结构上所实现的各种重要和典型的算法上。 结合实际应用的要求，使课程设计既覆盖知识点，又接近工程实际需要。 通过详细的实例分析和循序渐进的描述.启发学生完成设计。 提供了几个较大的综合课程设计实例。以进一步锻炼学生的动手能力。
