本书是高职高专精品课程系列教材《数据结构》的配套教材，适合计算机及相关专业数据结构课程设计或实训教学使用。

    书中全面地介绍了不同数据结构的应用，从实际例子出发，分析逻辑结构和存储结构，分析如何应用数据操作解决实际问题和完成相应的功能。不同的数据结构配有实例，每个实例都从问题出发，分析数据结构和算法操作步骤，然后给出设计过程，并完成代码设计与调试。分析中配合了流程图、操作步骤分解图和测试结果图等，力求使学习者能深入理解并提升数据结构的设计和应用能力。

    本书内容共有两篇，第一篇为实训篇，针对数据结构课程设计内容，叙述了几种不同数据结构的应用和实例，有线性表、栈、队列、二叉树、树、图、查找和排序这几种不同实例的设计过程。第二篇为习题分析与解答，针对《数据结构》教材中的习题做出全面分析和解答。

    书中第一篇中的所有实例代码均调试通过，并配有电子版代码。

　　

前    言

　　数据结构实训是数据结构课程和程序训练的重要环节。用计算机求解任何问题都离不开程序设计，而程序设计的实质是数据表示和数据处理。在程序的设计中，如何选择数据结构是设计考虑的基本因素，最优的数据结构的选择是系统实现的困难程度和构造的质量的关键问题，因此学会数据结构的应用是非常重要的。数据结构的理论抽象、难理解，算法复杂，使学习者感到学习困难，至于应用，更无从下手。因此以实际例子将数据结构应用的设计过程展示出来，不仅能深化对数据结构的理解，也能提升数据结构的应用能力。

　　数据的逻辑结构可分为线性结构、树型结构、图(网)和集合四种，其中线性结构又可分为线性表、栈、队列。当逻辑结构确定后，根据实际需要，可以采用顺序或链式存储结构存放数据，复杂的存储结构还可以采用两种不同存储结构的结合方式。当数据的逻辑结构和存储结构确定后，就可以编写算法实现，对数据进行操作。本书《数据结构实训与案例分析》是以引导数据结构的应用为导向，一般先提出一个实例，然后从逻辑结构、存储结构和算法三方面设计。先选择数据结构，然后是问题的分析与实现，最后给出完整可运行的源程序和测试结果，通过这样一种方式，将不同数据结构实例的设计过程展示出来。

　　本书是高职高专精品课程系列教材《数据结构》的配套教材，也是数据结构课程实训或软件实训的教学用书，是理想的软件方面实训的教材。利用数据结构实训过程，使学生能够以问题求解方法、程序设计方法及一些典型的数据结构算法为研究对象，学会分析数据对象的特征，掌握数据组织的方法和在计算机中的表示方法，培养良好的程序设计风格、程序设计的技能及创造性思维的方法，从而达到应用知识解决复杂问题的目的。

　　本书第一篇主要为数据结构实训内容，包括线性表、栈、队列、树与二叉树、图、查找和排序中的不同例子。每个例子都有完整的设计过程，将问题分析、数据结构定义、功能函数设计、主要算法分析、完整代码、测试过程逐一给出，所有的代码均已调试通过(在Turbo C环境下)。第二篇为针对配套教材《数据结构》中的习题的答案，答案中有分析有算法。

　　《数据结构》和《数据结构实训与案例分析》这两本配套教材将数据结构的理论、实验、实训或课程设计、习题与习题解答、案例分析等内容完整地结合在一起。有理论、有实验、有提出的问题，也有解答的方案，不论是作为教材或自学，都是理想的选择。

　　本书作为高职教材，如果用于数据结构实训或计算机软件实训，参考学时为2~4周。

　　本书是作者在多年从事C语言、数据结构以及计算机软件课程教学工作和计算机软件开发工作的基础上编写的，由沈阳理工大学教师李筠、姜学军主编，王艳梅、陈腾蛟副主编，宋洪波、田悦、徐志勇、苑擎飏、姚旭东、袁凤莲、马永轩、许亮、王海涛等参编。

　　由于作者水平有限，书中难免存在错误之处，欢迎读者提出宝贵意见。

　　

　　

　　编  者    

　　

　　

　　

　　

　　

　　

　　

　　

　　

目    录

第一篇  实训与案例分析

第1章  概述 1

1.1  课程实训的作用 1

1.2  课程实例的编写过程 2

1.3  课程实训的实施 2

第2章  线性结构 4

2.1  线性表应用 4

2.1.1  线性表在顺序结构上的基本

操作的设计 6

2.1.2  线性表在链式结构上的基本

操作设计 16

2.1.3  学生信息管理系统的设计 24

2.1.4  航班信息管理设计 35

2.2  栈的应用 46

2.3  队列应用 57

第3章  树的应用 65

3.1  二叉树基本操作 65

3.1.1  在顺序结构上二叉树的

基本操作的设计 66

3.1.2  在链式存储结构上二叉树

基本操作的设计 78

3.2  哈夫曼编码应用 90

3.2.1  夫曼树和哈夫曼编码 90

3.2.2  哈夫曼编码的应用 91

第4章  图的应用 102

4.1  图的存储结构和基本操作 102

4.1.1  邻接矩阵表示法 102

4.1.2  邻接表表示法 103

4.1.3  图的基本操作 103

4.2  图的最短路径应用 105

4.3  图的拓扑排序在排课中的应用 115

第5章  查找和排序的应用 129

5.1  查找与排序基本操作 129

5.1.1  查找表 129

5.1.2  排序 130

5.2  通信录的设计 131

　　

第二篇  配套教材习题解答

第1章  “绪论”习题答案 157

第2章  “线性表”习题答案 160

第3章  “栈和队列”习题答案 173

第4章  “串”习题答案 182

第5章  “数组”习题答案 187

第6章  “树与二叉树”习题答案 193

第7章  “图”习题答案 202

第8章  “查找”习题答案 207

第9章  “排序”习题答案 214

参考文献 222