数据结构习题解实训 第一章.doc

第 1 章绪　　论 本书对应《数据结构》教材上的章节,给出每一章的习题分析及程序解答。习题中所 有的程序都用C语言编写并上机调试通过,并在本书所配的光盘中提供了程序的源文 件。考虑到函数调用的共享性,有的章节中还给出一些汇总性的习题及其解答和源程序。 每一章的习题程序放在光盘同名目录下。所有习题用到的数据结构类型说明定义都放在 头文件“datastru.h”中,头文件“datastru.h”在光盘根目录下。 程序中的输入、输出和注释均以中文描述和表达。程序可以在Windows98操作系 统(或DOS操作系统)、TurboC软件环境下编译运行,也可以在Windows98操作系统、 VisualC++6．0软件环境下编译运行,因为程序的源代码用的全是VisualC++中的语 句,所以源程序不作任何修改就可以在VisualC++下编译运行。 本书中有几个程序和教材上应用举例中的程序相同,这是为了方便手中无教科书的 读者可从本书中学到比较多的数据结构应用程序。 下面介绍在3种不同的运行环境下编译运行C语言源程序的过程,供上机练习时 参考。 　 1.1 　 Windows98 操作系统、 VisualC ++ 6.0 　 软件环境下编译运行　 　　VisualC++6.0是Microsoft公司推出的、目前使用非常广泛的可视化编程环境,为 使用者提供了强大的开发能力。本书中的每一个程序的源代码用的全是VisualC++中 的C语言语句,所以可以不作任何修改就可在VisualC++下编译运行。只要使用中文版 的Windows98操作系统,程序就可在中文版或英文版VisualC++6.0环境下编译运行。 在运行程序前,应先安装MicrosoftVisualC++6.0的开发环境。在运行每个程序 时,请先阅读这个程序的题目要求、结构说明及有关的分析和解释。下面以第6章的“二 叉树中序遍历”习题为示例,说明运行程序的操作步骤。 (1)在硬盘上建立一个C++程序运行的目录,如“c:\temp\数据结构”。 (2)把附带光盘“二叉树”子目录下的“二叉树中序遍历.c”源程序及有关文件包括 l2 　　　　数据结构习题解析与实训 “二叉树.c”源程序、根目录下的“datastru.h”头文件复制到上面建立的“c:\temp\数据结 构”目录之下。 (3)进入MicrosoftVisualC++6.0开发环境,如图1．1所示。这是对应运行每一个 数据结构习题最基本的VisualC++6.0开发环境界面。屏幕的最上端是标题栏,标题栏 用于显示应用程序名和所打开的文件名。标题栏下面是菜单栏和工具栏。工具栏左下方 是工作区窗口,右下方是编辑窗口,因为数据结构的习题是用C语言编写的,所以工具栏 下方的工作区窗口没有用到,可将其关闭。最下方是状态栏。状态栏上面是输出窗口,用 于显示程序编译、连接、运行过程中的有关信息 。 图1.1　VisualC++6.0(中文版)开发环境界面 (4)打开源程序:选择“文件”(File)→“打开”(Open),选择“c:\temp\数据结构”目录 下的“二叉树中序遍历.c”文件。在编辑窗口即可观察到这个文件的源代码,如图1．2 所示。 (5)对源程序进行编译操作:选择“编译”(Build)→“编译二叉树中序遍历.c” (Compile)执行编译。编译过程中出现的错误会显示在下面的输出窗口,根据错误信息提 示,修改程序错误,直至错误和警告信息为0,如图1．3所示。 (6)程序运行:选择“编译”→“执行二叉树中序遍历.exe”(Execute)执行连接和运行 操作。当程序运行时,将会弹出一个窗口,运行程序,显示信息,或等待用户的输入数据。 程序运行的结果也显现在同一窗口内,如图1．4所示。 第1章　绪论 l3 　　　　 图1.2　打开源程序 图1.3　对源程序进行编译操作 l4 　　　　 数据结构习题解析与实训 图1.4　程序运行显示 　　(7)本习题集中全部程序均在Windows98操作系统、MicrosoftVisualC++6.0软 件环境下调试通过。 (8)有关MicrosoftVisualC++6.0软件本身的内容,请读者参考相关的书籍。 (9)最后需要说明的一点是:程序主要是在功能和逻辑上实现了题目的要求,而没有 对输入数据的合法性进行严格的判断和校验,输入数据的合法性由用户保证。因而如果 发生用户输入数据不当时,程序可能会呈现出错的异常情况,遇到这种情况发生,只需重 新运行源程序即可。 　 1.2 　 Windows 操作系统、 TurboC 软件　 环境下编译运行　 　　在运行程序前,应安装TurboC软件。有关TurboC软件本身的内容,请读者参考 相关的书籍。在运行每个程序时,请先阅读这个程序的