第1章 概 论
数据结构实训系统开发及说明
1 系统设计
学习完了数据结构整本书内容，我们选取本书各章中难度适当的典型算法为基础，组装成一个数据结构实训系统。通过本系统的开发，让学生了解如何将多个功能模块组合成为一个应用程序的过程。
1 系统设计
10.1 系统设计
10.1.1 系统模块设计规则
模块的分解应使每个模块相对独立，因此使模块内部自身联系紧密，模块外部相互之间的信息联系尽可能减少，是设计物理模型的两项基本原则。我们选取本教材中各章里典型的算法，经过简单修改，最后合成整个数据结构实训系统。
作为数据结构实训系统的第一层模块，其结构如图1所示。
系统设计
图1 实训系统框架
1 系统设计
其第二层的模块结构如图2 所示。
图2
1 系统设计
以此类推，完成整个模块的设计。并且各模块功能要求相对独立，这对将来系统维护、和系统扩充将是十分有利的。假定系统中选用和设计的算法是完全独立的，那我们设计一个菜单，通过选择菜单来执行各模块是十分方便的。
1 系统设计
1.2 系统中的文件包含
1．什么是文件包含
文件的包含处理是指一个源文件可以将另一个源文件的全部内容包含进来，即将另外的文件包含到本文件之中。C语言提供了#include命令来实现“文件包含”的操作。其一般形式为：
#include “文件名” 或
#include <文件名>
1 系统设计
说明如下:
（1）一个include命令只能指定一个被包含的文件。要包含n个文件，必须用n个include命令。
（2）若file1.cpp包含 file2.h，而 file2.h中又要用到file3.h 的内容，则可在file1.cpp中用两个include命令分别包含file2.h和file3.h，而且 file3.h 必须出现在file2.h之前。定义如下：
#include “file3.h”
#include “file2.h”
这样，file1.cpp和file2.h都可以使用file3.h的内容，且file2.h也不必使用：#include “file3.h”命令了。
1 系统设计
（3）在一个被包含文件中又可以包含另一个被包含的文件，即文件包含是可以嵌套的。
（4）在#include命令中，文件名可以用双引号或尖括号括起来。两者的区别是：
用尖括号（如#include
用双引号（如#include “file2.h”）形式时，系统先在用户当前目录寻找要包含的文件，若找不到，再按标准方式查找。
（5）被包含文件（file2.h）与其所在的文件（即用#include命令的源文件file1.cpp）在预编译后，已成为同一个文件。所以，如果在file2.h中有全局静态变量，它也在file1.cpp文件中有效，不必另外声明。
1 系统设计
2．对“数据结构实训系统”进行文件包含
设本书前述各章的子系统分别命名为：linklist.h、linkstack.h、linkqueue.h、string.h、btree.h、graph.h、search.h、sort.h，现在我们用这八个子系统为基础来组成一个数据结构的实训系统。因为在C语言中只允许有一个主函数，所以在组成整个系统前，我们必须把原来各子系统的主函数进行改名，表1是各子系统的函数名和头文件名的对照表。
1 系统设计
数据结构实训系统中包含的所有函数如表2所示。读者可自行将书中所有函数都加到本系统中。
表1
10.1 系统设计
通过这些文件包含命令，设计出主调函数，在主调函数中调用这些子函数，即完成了该实训系统的任务。
表12
2 系统实现
2.1 主调函数的设计与实现
下面我们新建一个C源程序文件，在里面使用文件包含命令将前面各头文件包含进去，再编写菜单来实现对各子模块的调用。
因为要使用菜单进行选择，所以设一个循环变量ch用来判断进行哪一操作。在循环体中用switch来选择进行哪个操作，再进入下一级的子菜单。
2 系统实现
主函数设计如下：
2 系统实现
2 系统实现
2 系统实现
2.2 实训报告
1．实训报告题目名称
数据结构实训系统
2．系统包括的基本算法
如表2中的所有算法。
3．要求
（1）整个系统全部采用菜单控制。
（2）一级菜单为每个数据结构的名称，二级菜单为基础算法（需要的话，还可以在二级菜单之下建立三级菜单）。
（3）系统全部采用中文提示的人机交互方式工作。
（4）完成程序设计和程序调试。
（5）撰写课程设计报告。
10.2 系统实现
4．实训（课程设计）报告要求
（1）“数据结构实训系统”设计的意义和作用。
（2）系统总框图（把自主设计的算法反映出来）。
（3）完成系统菜单的设计（可以用选择式菜单，也可以使用菜单设计工具）。
（4）完成程序设计（除了教材提供的实验中算法，必须扩充若干自主设计的算法）。
（5）列出全部模块和算法名称（包括扩充的自主设计算法）的对照表。
（6）调试程序（包括系统调试步骤、程序调试中碰到的问题及解决方法）。
（7）程序源代码（自主扩充和自主设计的算法）。
（8）对自主设计的算法进行时间复杂度和空间复杂度的分析。
（9）操作举例（主要针对自主设计的算法，把输入数据及程序运行结果写到报告中）。
（10）参考文献。
10.2 系统实现
10.2 系统实现
10.2 系统实现