《数据结构习题解析与实训 第一章.doc》由会员分享，可在线阅读，更多相关《数据结构习题解析与实训 第一章.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 绪论本书对应数据结构教材上的章节,给出每一章的习题分析及程序解答。习题中所有的程序都用C语言编写并上机调试通过,并在本书所配的光盘中提供了程序的源文件。考虑到函数调用的共享性,有的章节中还给出一些汇总性的习题及其解答和源程序。每一章的习题程序放在光盘同名目录下。所有习题用到的数据结构类型说明定义都放在头文件“datastru.h”中,头文件“datastru.h”在光盘根目录下。程序中的输入、输出和注释均以中文描述和表达。程序可以在Windows98操作系统(或DOS操作系统)、TurboC软件环境下编译运行,也可以在Windows98操作系统、VisualC+60软件环境下编译运行,
2、因为程序的源代码用的全是VisualC+中的语句,所以源程序不作任何修改就可以在VisualC+下编译运行。本书中有几个程序和教材上应用举例中的程序相同,这是为了方便手中无教科书的读者可从本书中学到比较多的数据结构应用程序。下面介绍在3种不同的运行环境下编译运行C语言源程序的过程,供上机练习时参考。1.1Windows98操作系统、VisualC+6.0软件环境下编译运行VisualC+6.0是Microsoft公司推出的、目前使用非常广泛的可视化编程环境,为使用者提供了强大的开发能力。本书中的每一个程序的源代码用的全是VisualC+中的C语言语句,所以可以不作任何修改就可在VisualC+
3、下编译运行。只要使用中文版的Windows98操作系统,程序就可在中文版或英文版VisualC+6.0环境下编译运行。在运行程序前,应先安装MicrosoftVisualC+6.0的开发环境。在运行每个程序时,请先阅读这个程序的题目要求、结构说明及有关的分析和解释。下面以第6章的“二叉树中序遍历”习题为示例,说明运行程序的操作步骤。(1)在硬盘上建立一个C+程序运行的目录,如“c:temp数据结构”。(2)把附带光盘“二叉树”子目录下的“二叉树中序遍历.c”源程序及有关文件包括l2数据结构习题解析与实训“二叉树.c”源程序、根目录下的“datastru.h”头文件复制到上面建立的“c:temp
4、数据结构”目录之下。(3)进入MicrosoftVisualC+6.0开发环境,如图11所示。这是对应运行每一个数据结构习题最基本的VisualC+6.0开发环境界面。屏幕的最上端是标题栏,标题栏用于显示应用程序名和所打开的文件名。标题栏下面是菜单栏和工具栏。工具栏左下方是工作区窗口,右下方是编辑窗口,因为数据结构的习题是用C语言编写的,所以工具栏下方的工作区窗口没有用到,可将其关闭。最下方是状态栏。状态栏上面是输出窗口,用于显示程序编译、连接、运行过程中的有关信息。图1.1VisualC+6.0(中文版)开发环境界面(4)打开源程序:选择“文件”(File)“打开”(Open),选择“c:t
5、emp数据结构”目录下的“二叉树中序遍历.c”文件。在编辑窗口即可观察到这个文件的源代码,如图12所示。(5)对源程序进行编译操作:选择“编译”(Build)“编译二叉树中序遍历.c”(Compile)执行编译。编译过程中出现的错误会显示在下面的输出窗口,根据错误信息提示,修改程序错误,直至错误和警告信息为0,如图13所示。(6)程序运行:选择“编译”“执行二叉树中序遍历.exe”(Execute)执行连接和运行操作。当程序运行时,将会弹出一个窗口,运行程序,显示信息,或等待用户的输入数据。程序运行的结果也显现在同一窗口内,如图14所示。第1章绪论l3图1.2打开源程序图1.3对源程序进行编译
6、操作l4数据结构习题解析与实训图1.4程序运行显示(7)本习题集中全部程序均在Windows98操作系统、MicrosoftVisualC+6.0软件环境下调试通过。(8)有关MicrosoftVisualC+6.0软件本身的内容,请读者参考相关的书籍。(9)最后需要说明的一点是:程序主要是在功能和逻辑上实现了题目的要求,而没有对输入数据的合法性进行严格的判断和校验,输入数据的合法性由用户保证。因而如果发生用户输入数据不当时,程序可能会呈现出错的异常情况,遇到这种情况发生,只需重新运行源程序即可。1.2Windows操作系统、TurboC软件环境下编译运行在运行程序前,应安装TurboC软件。
7、有关TurboC软件本身的内容,请读者参考相关的书籍。在运行每个程序时,请先阅读这个程序的题目要求、结构说明及有关的分析和解释。下面以第2章的“顺序表并集运算”题目为示例,说明程序运行的操作步骤。(1)在硬盘上建立一个TurboC程序运行的目录如“c:tempsjjg”。(2)把附带光盘“线性表”子目录下的“顺序表并集.c”源程序及根目录下的“datastru.h”头文件复制到“c:tempsjjg”所在的目录之下。(3)进入MicrosoftTurboC开发环境,如图15所示。在这个开发环境下,程序中的中文输入和中文输出以及源程序中的中文注释均可正常显示。(4)打开源程序:选择FileLod
8、e打开“c:tempsjjg顺序表并集.c”文件。在编辑第1章绪论l5图1.5Windows操作系统、MicrosoftTurboC开发环境图1.6打开源程序窗口即可观察到这个文件的源代码,如图16所示。(5)对源程序进行编译操作:选择CompileCompiletoOBJ执行编译。编译中出现的错误会显示在下方Message窗口中,当编译通过,TC窗口显示如图17所示。(6)编译通过后选择RunRun执行连接和运行操作。当程序运行时,将会弹出一l6数据结构习题解析与实训图1.7程序进行编译操作图1.8TC程序运行窗口显示个窗口,运行程序,显示信息,或等待用户的输入数据。程序运行的结果数据显示在
9、另一窗口内,如图18所示。(7)本习题集中全部程序均在Windows98操作系统、TurboC软件环境下调试通过。要注意的是,在Windows98操作系统、TurboC软件环境下编译运行时,程序中包第1章绪论l7含的头文件均应改为;包含的“二叉树.c”文件须改为包含完整路径的英文文件名方可。1.3DOS操作系统、TurboC软件环境下编译运行程序如果在DOS操作系统、TurboC软件环境下编译运行,则程序的中文名、程序的中文输入、输出及中文注释的正确显示都依赖于DOS操作系统的汉化,DOS操作系统的汉化工作由用户处理。基于以上3种环境下编译运行的介绍,建议使用第一种即在Windows98操作系
10、统、VisualC+6.0软件环境下编译运行各源程序。1.4习题解析【习题1】分析下面语句段执行的时间复杂度。(1)for(i=1;i=n;i+)for(j=1;j=n;j+)s+;【解答】双重for循环语句,其中外循环n次,对每一次外循环,内循环s+;语句执行n次。总的s+;语句共执行n2次,时间复杂度为O(n2)。(2)for(i=1;i=n;i+)for(j=i;j=n;j+)s+;【解答】双重for循环语句,其中外循环n次,对每一次外循环,内循环s+;语句执行次数都在变化。第一次外循环时,内循环s+;语句执行次数为n次;第二次外循环时,内循环s+;语句执行次数为n-1次;第三次外循环时
11、,内循环s+;语句执行次数为n-2次;第n次外循环时,内循环s+;语句执行次数为1次;总的s+;语句共执行n+(n-1)+(n-2)+2+1=n(n+1)2次,时间复杂度为O(n2)。l8数据结构习题解析与实训(3)for(i=1;i=n;i+)for(j=1;j=i;j+)s+;【解答】双重for循环语句,其中外循环n次,对每一次外循环,内循环s+;语句执行次数都在变化。第一次外循环时,内循环s+;语句执行次数为1次;第二次外循环时,内循环s+;语句执行次数为2次;第三次外循环时,内循环s+;语句执行次数为3次;第n次外循环时,内循环s+;语句执行次数为n次;总的s+;语句共执行1+2+3+
12、(n-2)+(n-1)+n=n(n+1)2次,时间复杂度为O(n2)。(4)i=1;k=0;while(i=n-1)k+=10i;i+;【解答】i=1;语句执行1次;k=0;语句执行1次;while循环语句在(i=n-1)条件满足时,执行k+=10i;和i+;两条语句。当n=1时;while循环条件(i=n-1)不满足,k+=10i;和i+;两条语句不执行。当n=2时;while循环条件(i=n-1)满足一次,k+=10i;和i+;两条语句执行一次。当n=3时;while循环条件(i=n-1)满足二次,k+=10i;和i+;两条语句执行二次。以此类推,总的语句执行次数为1+1+2(n-1)次,时间复杂度为O(n)。【习题2】试画出与下列程序段等价的框图。(1)p=1;i=1;while(i=n)p=i;i+;第1章绪论l9【解答】(2)i=0;doi+;while(i!=n)&(ai!=x);【解答】【习题3】写一算法,从大至小依次输出顺序读入的3个整数X、Y和Z的值。【解答】voidorder(intx,inty,intz)nta;if(xy)a=x;x=y;y=a;if(xz)a=x;x=z;z=a;if(yz)a=y;y=z;z=a;printf(从大至小依次输出顺序读入的3个整数X、Y和Z:%d%d%dnn,x,y,z);