内容简介

本实验指导教程是配合计算机及相关专业的“数据结构”课程而编写的。在内容编排方面，按照循序渐进、由浅入深的顺序设计、选取案例。全书共分两个部分：第一部分为“数据结构实验”；第二部分为“数据结构课程设计”。

第一部分(包括第1～8章)针对每个知识点，首先给出明确的要求，随后设计基础实验，特别是前几章在基础实验之后，设计了若干应用案例。这样有利于学生明确知识点在应用中如何使用，消除迷茫感、增强学习兴趣。

第二部分(即第9章)是课程设计，介绍在一个项目中如何选择和使用多种基本的数据结构，介绍如何有效地将它们融合在一起，解决实际的复杂应用问题。

本书可作为高等院校计算机及相关专业数据结构课程的实验教材。

前    言

　　

　　数据结构是计算机及相关专业中一门重要的专业基础课程。用计算机解决实际问题时，就要涉及数据的表示及数据的处理，而这正是数据结构课程的主要研究对象。通过对数据结构知识内容的学习，可以为后续课程，尤其是软件方面的课程打下坚实的基础，同时，也提供了必要的技能训练。此课程的学习质量将直接影响计算机软件系列课程的学习效果，因此，数据结构课程在计算机专业中具有举足轻重的作用。

　　根据我们多年的教学经验，认为学生学习数据结构的主要困难在于解题。学生在解题中经常会出现错误，原因在于实践能力不足。

　　要学好数据结构，仅仅通过课堂教学或自学获取理论知识是远远不够的，还必须加强实际动手能力的训练。只有通过实验课调试和运行已有的各种典型算法和已编写的程序，从成功和失败的经验中得到锻炼，才能熟练掌握和运用理论知识解决软件开发中的实际问题，达到学以致用的目的。

　　本实验指导教程是配合计算机及相关专业数据结构课程而编写的。本书在内容编排方面，按照循序渐进、由浅入深的顺序设计、选取案例。根据教学内容，针对学生的实际情况，本书在内容编排上共分两个部分。第一部分为"数据结构实验"；第二部分为"数据结构课程设计"。

　　第一部分(包括第1～8章)针对每个知识点，首先给出明确的要求，随后设计基础实验，特别是前几章在基础实验之后，设计了若干应用案例。这样有利于学生明确知识点在应用中如何使用，消除学生的迷茫感、增强学生的学习兴趣。

　　第二部分(即第9章)是课程设计，介绍在一个项目中如何选择和使用多种基本数据结构，介绍如何有效地将它们融合在一起解决实际的复杂应用问题。这有利于学生更深层次地掌握数据结构原理及其应用范围和过程。

　　本书具有以下特点。

　　(1) 基于案例驱动的教学内容设计。在实验案例的选择方面，不仅有针对知识点的基础案例，而且有对应的应用案例，从而使学生能够消除畏难情绪。我们在该实验教材的编写过程中，选择案例时由浅入深并精心设计了应用案例，以确保应用的完整性。

　　(2) 提供大量的源代码和开发案例。在该实验教材的编写中，摒弃了伪代码的描述，全部采用C语言源代码，这些源代码都是经过调试并且在教学过程中已经应用的，学生可以直接分析和模仿。同时，在重要的章节，都提供了较为深入的设计案例，例如多项式的运算、括号匹配判断系统、迷宫求解系统、最短路径求解等，为学生提供了更为深入的源码讨论和模仿的机会，极大地提高了教材的全面性、深入性和综合性。

　　(3) 提供典型的课程设计内容。为了更好地提高学生的专业技能训练水平以及提高学生的学习兴趣，在本书的编写过程中，编写成员根据自己多年教学的积累，整理出了适合计算机专业学生实际情况的课程设计题目，并提供了相应的解决思路和源代码，为学生提供了很好的学习机会和训练机会。

　　本书提供案例程序的源代码(可运行)，并赠送C++版案例实验教程。读者可以从清华大学出版社的网站下载。 

　　本书可作为高等院校计算机及相关专业数据结构课程的实验教材。

　　由于编者水平有限，错误和不当之处在所难免，希望读者批评指正。 

　　

编  者

 

　　

目录

第1章  顺序表 1

实验1  顺序表的实现 2

　1．实验目的 2

　2．实验内容 2

　3．算法设计 2

　4．程序实现 3

　5．运行程序 5

实验2  顺序表的应用--集合运算 5

　1．实验目的 5

　2．实验内容 5

　3．算法设计 5

　4．程序实现 6

　5．运行程序 8

实验3  顺序表的应用--回文数猜想 8

　1．问题描述 8

　2．基本要求 8

　3．算法设计 8

　4．程序实现 9

　5．运行程序 10

第2章  链表 11

实验1  单链表的实现 12

　1．实验目的 12

　2．实验内容 12

　3．算法设计 12

　4．程序实现 13

　5．运行程序 15

实验2  单链表的应用--约瑟夫问题 16

　1．问题描述 16

　2．基本要求 16

　3．算法设计 16

　4．程序实现 16

　5．运行程序 17

实验3  单链表的应用--多项式求和 18

　1．问题描述 18

　2．基本要求 18

　3．算法设计 18

　4．实现程序 18

　5．运行程序 21

第3章  栈 23

实验1  顺序栈的实现 24

　1．实验目的 24

　2．实验内容 24

　3．算法设计 24

　4．程序实现 25

　5．运行程序 26

实验2  链栈的实现 26

　1．实验目的 26

　2．实验内容 26

　3．算法设计 27

　4．程序实现 27

　5．程序运行 28

实验3  栈的应用--数制转换 28

　1．问题描述 28

　2．基本要求 28

　3．算法设计 29

　4．程序实现 29

　5．运行程序 30

实验4  栈的应用--括号匹配问题 30

　1．问题描述 30

　2．基本要求 30

　3．算法设计 30

　4．程序实现 30

　5．运行程序 31

实验5  栈的应用--表达式求值 32

　1．问题描述 32

　2．基本要求 32

　3．算法设计 32

　4．程序实现 32

　5．运行程序 34

第4章  队列 35

实验1  循环队列的实现 36

　1．实验目的 36

　2．实验内容 36

　3．算法设计 36

　4．程序实现 37

　5．运行程序 38

实验2  链队列的实现 39

　1．实验目的 39

　2．实验内容 39

　3．算法设计 39

　4．程序实现 39

　5．运行程序 41

实验3  队列的应用--优先队列 41

　1．问题描述 41

　2．基本要求 41

　3．算法设计 41

　4．实现程序 42

　5．运行程序 44

实验4  队列的应用--双端队列 45

　1．问题描述 45

　2．基本要求 45

　3．算法设计 45

　4．程序实现 45

　5．运行程序 48

第5章  二叉树 49

实验1  二叉树的建立 50

　1．实验目的 50

　2．实验内容 50

　3．算法设计 50

　4．程序实现 51

　5．运行程序 51

实验2  二叉树的遍历 52

　1．实验目的 52

　2．实验内容 52

　3．算法设计 52

　4．程序实现 53

　5．运行程序 55

实验3  二叉树的高度、节点数、叶子

节点数 55

　1．实验目的 55

　2．实验内容 55

　3．算法设计 55

　4．程序实现 55

　5．运行程序 57

实验4  堆 57

　1．问题描述 57

　2．基本要求 57

　3．算法设计 57

　4．程序实现 58

　5．运行程序 60

第6章  图 61

实验1  图的邻接矩阵表示 62

　1．实验目的 62

　2．实验内容 62

　3．实现提示 62

　4．程序实现 62

　5．运行程序 64

实验2  图的邻接表表示 64

　1．实验目的 64

　2．实验内容 64

　3．实现提示 64

　4．程序实现 64

　5．运行程序 66

实验3  图的深度优先搜索 67

　1．问题描述 67

　2．基本要求 67

　3．实现提示 67

　4．程序实现 67

　5．运行程序 69

第7章  排序 71

实验1  冒泡排序 72

　1．实验目的 72

　2. 实验内容 72

　3．实现提示 72

　4．程序实现 73

　5．运行程序 74

实验2  插入排序、选择排序 74

　1．实验目的 74

　2．实验内容 74

　3．实现提示 75

　4．程序实现 75

　5．运行程序 76

实验3  归并排序 76

　1．实验目的 76

　2．实验内容 76

　3．实现提示 76

　4．实现程序 76

　5．运行程序 78

实验4  快速排序 78

　1．实验目的 78

　2．实验内容 79

　3．实现提示 79

　4．程序实现 79

　5．运行程序 80

实验5  堆排序 81

　1．实验目的 81

　2．实验内容 81

　3．实现提示 81

　4．程序实现 81

　5．运行程序 82

第8章  查找 83

实验1  折半查找 84

　1．实验目的 84

　2．实验内容 84

　3．实现提示 84

　4．程序实现 85

　5．运行程序 86

实验2  二叉排序树查找 87

　1．实验目的 87

　2．实验内容 87

　3．实现提示 87

　4．程序实现 87

　5．运行程序 89

实验3  哈希查找 89

　1．实验目的 89

　2．实验内容 89

　3．实现提示 90

　4．程序实现 90

　5．运行程序 91

第9章  课程设计 93

问题1  学生成绩管理 94

　1．问题描述 94

　2．任务要求 94

　3．程序实现 95

　4．运行结果 98

问题2  数据库管理系统 98

　1．问题描述 98

　2．任务要求 98

　3．分析与实现 99

　4．程序实现 101

　5．运行结果 116

问题3  马踏棋盘 117

　1．问题描述 117

　2．任务要求 117

　3．分析与实现 117

　4．运行结果 120

问题4  停车场管理 121

　1．问题描述 121

　2．任务要求 121

　3．分析与实现 122

　4．运行结果 126

问题5  大整数计算器 126

　1．问题描述 126

　2. 任务要求 127

　3．分析与实现 127

　4．运行结果 132

 

问题6  魔方阵 132

　1．问题描述 132

　2．任务要求 133

　3．分析与实现 133

　4．运行结果 134

问题7  本科生导师制问题 134

　1．问题描述 134

　2．任务要求 135

　3．分析与实现 135

　4．运行结果 144

问题8  电文的编码和译码 145

　1．问题描述 145

　2．任务要求 145

　3．分析与实现 145

　4．运行结果 148

问题9  家族关系查询系统 149

　1．问题描述 149

　2．任务要求 149

　3．分析与实现 149

　4．运行结果 161

问题10  地铁建设问题 162

　1．问题描述 162

　2．任务要求 162

　3．分析与实现 162

　4．运行结果 165

问题11  校园导航 165

　1．问题描述 165

　2．任务要求 165

　3．分析与实现 166

　4．运行结果 169

参考文献 170