第11章数据结构课程实训.

2011年5月11日星期三1第11章目录•11.1系统设计的要求•11.2文件的包含处理•11.3数据结构课程实训任务书本章的主要目的是指导学生以本书精选的、难度适当的60个左右的典型算法为基础，组装一个数据结构实验系统。在此基础上，指导学生扩充自主设计的其它算法，完成一个数据结构实训课题。通过本章学习，可以复习数据结构的基本算法，学习数据结构实验系统开发的全过程，了解系统设计的一般要求；掌握文件包含处理的基本方法；提高程序编写和程序调试的能力。11.1系统设计的要求1．系统总体设计系统总体设计包括系统总体结构设计；计算机系统配置方案的设计等。其中，系统总体结构设计包括整个系统分成几个模块，各个模块选择多少个算法，整体上要达到什么样的目标等。计算机系统配置包括硬件和软件两个方面。在硬件上选择何种类型的计算机及必要的外围设备；在软件上采用何种操作系统和程序设计语言等。对于本章的数据结构实验系统而言，由于使用的是C（或C++）语言，所以对硬件的要求比较低，一般的微型计算机或笔记本电脑都可以胜任。至于软件，可以使用Windows各种版本的操作系统和MicrosoftVisualC++等系统软件。2.系统详细设计系统详细设计包括逻辑结构设计、存储结构设计和算法设计；用户界面设计；以及用何种程序设计语言实现等。对于数据的逻辑结构、存储结构和算法在前面各章已经有了详细的介绍，所以，这里主要考虑的是用户界面的设计，比如采用什么样的菜单，如何设计人机交互的信息等等。3.系统调试和维护系统调试的方法和常规的调试手段是每个学习计算机技术的学生必须掌握的，我们所以增加这一章的内容主要目的也是要加强学生编写程序和调试程序的能力。另外一个好的系统还必须考虑其运行以后的可维护性，也就是系统的修改、扩充、维护是否方便。11.1.1系统总体结构设计1．结构化设计的基本思想（1）模块化程序的设计思想•将系统按一定规则构造成相对独立的模块，每个模块完成一个独立功能，是模块化设计的基本思想。•模块化主要目的是将一个复杂系统划分为一些具有特定功能的模块，使整个系统设计、测试、维护更加简单。•从逻辑上看，模块就是处理功能，给它一定的输入信息，它能对之进行加工处理，并输出结果信息。•从物理上看，它是可用名字来表示的一组程序。模块的功能应当简单明确，易于理解，模块之间的联系应尽可能减少。•可以共用某些模块。•给每一个模块一个固定的编号或命名，以便整个系统的整合和系统的维护。（2）自顶向下，逐步求精的设计方法系统划分模块的工作应按层次进行：•把整个系统看作一个模块，然后按功能分解成若干第一层模块，每个模块各担负一定的局部功能，互相配合，共同完成整个系统的功能。•每个上一层的模块又可以进一步分解成更为简单（具体）的下一层模块，越下层的模块，其功能越具体，越单一。模块化的层次结构具有简明性，设计者容易思考，阅读者容易理解。只要保证每个模块能完成其自身的功能，尽量减少模块之间的联系，整个系统的正确性和可修改性就可以得到保证。另外，模块化的设计方法也使系统的可扩充性得到了保证。（3）上层模块分解为下层模块的三种结构形式结构化程序设计是采用科学化、标准化的规定所设计、编写的程序，它既是一种自上而下的程序设计方法，也是一种模块化的程序设计方法。顺序结构（SequenceConstruct）在顺序结构的程序处理中，一组语句序列，只有一个入口和一个出口。选择结构（SelectionConstruct）（a）单分支选择结构：IF（表达式）语句（b）两分支选择结构：IF（表达式）语句1ELSE语句序列2（c）多分支选择结构（SWITCH或CASE等）循环结构（IterationConstruct）（a）直到型循环直到型循环先执行循环体的程序，然后再判断是否要继续执行。这种循环结构至少使循环体内的程序执行一次。（b）当型循环当型循环首先判断循环条件是否成立，如果条件成立，则执行循环体内的语句序列；如果条件不成立，则结束循环。由于是先判断后执行，所以循环体内的语句序列也可能一次也不执行。无论多么复杂的系统，都可以分解为三种基本形式的组合。大部分程序设计语言都支持这三种结构形式。2．模块分解的规则模块的分解应使每个模块相对独立，因此使模块内部自身联系紧密，模块外部相互之间的信息联系尽可能减少，是设计物理模型的两项基本原则。若以本教材第二章至第九章各子系统，作为数据结构实验系统的第一层模块，其结构如图11-1所示。在数据结构教材中，每一章又有很多算法，在系统设计时就要进行分析、筛选，以确定系统中选用各章的那些算法。有时，在一个小节中就有多个算法，以查找子系统为例，其第二层的模块结构，如图11-2所示。在第二层的二叉排序树中还包含有许多重要的算法，于是我们可以进一步分解为更为深入的第三层模块，如图11-3二叉排序树子系统。以此类推，完成整个模块的设计。并且各模块功能要求相对独立，这对将来系统维护、和系统扩充将是十分有利的。假定系统中选用和设计的算法是完全独立的，那么在VC++环境中开发一个下拉式的菜单，然后通过下拉式菜单去调用这些算法将是十分方便的。11.1.2系统详细设计1．用户界面设计（1）菜单设计通过屏幕显示下一步程序可能执行的方向和目标，用户根据屏幕提示，指定一个所期望的执行方向，这种方式好象在菜单上点菜一样，称为菜单方式。早期的选择式菜单设计。随着面向对象的程序设计软件的出现，下拉式的菜单已成为当前菜单设计的主流，人们只要在菜单开发工具上，按照屏幕的提示，经过简单的操作就能完成功能完善的菜单设计。本书从锻炼学生编程的基本能力出发，在数据结构实验系统的菜单设计中仍然使用比较原始的选择式菜单。（2）人机对话设计当程序进行到一定阶段时，系统通过显示屏幕向用户提出一个问题，等待用户回答“是”或“否”，然后根据用户的回答，决定程序下一步的走向。例如：还要继续演示吗（Y/N）？用户只要按照屏幕提示回答“Y”或“N”，就能控制程序的方向。（3）输入设计在计算机处理过程中，数据输入是用户与计算机的重要接口。信息处理的基本原则是：按正确的程序，用正确的操作，去处理正确的数据。只有遵循这一原则才能获得正确的信息。因此，保证数据正确性的关键就是要保证输入的正确性。这就要求：•在进行输入设计时，对用户的输入数据进行必要的提示，比如：请输入10个整数；•对输入的数据的正确性进行必要的确认；•有一定的容错能力，即使输入数据错误，应该能给出适当的提示，并允许改正错误，而不发生滚屏或死循环的现象。（4）输出设计输出设计的好坏，将直接影响系统的使用效果。因此，如何针对用户的特点和要求，以最适当的方式，输出最适合需要的信息，是输出设计所要解决的主要问题。比如：对于冒泡排序有单向冒泡和双向冒泡之分，从排序的结果来看是一样的。如果输出设计使之能显示每一趟排序的结果，这对加深排序算法的理解，比较排序质量的优劣将是十分有益的。2．处理过程设计处理过程设计是对每一个模块的内部过程进行具体的描述，从而在程序编制阶段可以将这个描述直接翻译成用某种程序设计语言编写的程序。处理过程设计的结果，对应用程序的质量起着决定性的作用，同时也是系统测试和系统维护的重要依据。处理过程设计的工具很多，可以分为流程图（如程序流程图、N—S图），表格（决策树、决策表）和程序设计语言工具三类。这三类工具都能指明控制流程、处理功能、数据流等实现细则。11.1.3系统调试和维护程序和系统调试的目的是发现程序和系统中的错误并及时予以纠正。1．程序调试程序调试包括程序的语法调试和程序的逻辑检查。程序的调试除了采用正常的数据外，还应该选用一些异常的和错误的数据，用来考验程序的正确性。具体检查内容如下：（1）输入错误键值时，能否及时发出出错信息，并允许修改；（2）输入错误数据时，能否及时检查出错误数据，并允许修改；（3）操作失误时，能否及时发出警告信息，并允许改正。2．分调由于系统是按处理功能分成模块的，一个处理功能由一个或一个以上的程序构成，所以在单个程序调试成功以后，就可以进行分调。所谓分调是将一个功能内的所有程序按次序串联起来进行调试，相当于一个子系统的调试。目的是保证模块内部控制关系的正确和数据内容的正确。3．总调（1）主控制和调度程序的调试这部分程序的语句不多，主要是要求逻辑控制正确。调试时可以将所有控制程序与各功能模块相连的接口用“短路”程序替代原来的功能模块。调试的目的不是处理结果的正确性，而是控制来往通路和参数传递的正确性，发现并解决模块调度中的问题。（2）程序总调程序总调是将主控制调度程序和功能模块联结起来调试，对系统各种可能的使用情况，进行可行性测试。4．编写文档编写文档的内容主要包括：（1）编写操作说明书；（2）完成程序框图；（3）打印出源程序代码。5．系统维护系统完成以后，很少能一字不改的一直沿用下去。软件开发人员应该根据外界环境的变更及时对系统进行维护。维护的内容包括：（1）程序的维护——根据系统运行出现的问题改写一部分甚至全部程序，使系统日益完善。（2）系统的扩充——根据需要，扩充新的功能和新的模块。（3）根据软件和硬件的发展，使系统升级换代，完成更新设计。比如：把选择式菜单换成下拉式菜单，以图形界面的显示替代DOS界面的显示等等。应该指出的是，本节涉及的内容，并不仅仅局限于数据结构实验系统的开发，而且也适用于一般系统的开发。11.2文件的包含处理11.2.1什么是文件包含文件的包含处理是指一个源文件可以将另一个源文件的全部内容包含进来，即将另外的文件包含到本文件之中。C（或C++）语言提供了#include命令来实现“文件包含”的操作。其一般形式为：#include“文件名”或#include文件名图11-4是“文件包含”以前两个独立文件file1.cpp和file2.h的示意图。其中图（a）为文件file1.cpp，它有一个#includefile2.h命令，然后还有其它内容的命令，以S1表示。图（b）为另一个文件file2.h，文件内容以S2表示。在编译预处理时，要对#include命令进行“文件包含”处理，即将文件file2.h的全部内容复制插入到#includefile2.h命令处，也就是将file2.h的内容包含到file1.cpp中，于是得到图11-5所示的结果。在编译中，将“包含”以后的file1.cpp作为一个源文件单位进行编译。“文件包含”在程序设计中是十分有用的。例如，在程序设计中往往需要使用一组固定的符号常量，如e=2.718，pi=3.1415926等，可以把这些宏定义命令组成一个文件，然后各人都可以用#include命令将这些符号常量包含到自己的源文件中。这样，就可以不必定义这些符号常量，而直接进行引用，相当于工业上的标准零件，其作用是大大节省了程序设计人员的重复劳动。【例11-1】利用宏定义将程序中的“输出格式”定义好，作为一个输出格式文件format.h,然后将它包含在一个file.cpp的文件中。（1）format.h#definePRprintf#defineNL“\n”#defineD“%d”#defineD1DNL#defineD2DDNL#defineD3DDDNL#defineD4DDDDNL#defineS“%s”（2）file.cpp#include“format.h”main(){inta,b,c,d；charstring[]=”上海东方明珠”；a=1；b=2；c=3；d=4；PR(D1,a)；PR(D2,a,b)；PR(D3,a,b,c)；PR(D4,a,b,c,d)；PR(S,string)；}程序运行后输出如下结果：1121231234上海东方明珠值得注意的是，在编译时以上两个文件并不是作为两个文件进行连接的，而是作为一个源程序编译，得到也只有一个目标文件。这种常用在文件头部被包含的文件，称为头部（head）文件，一般以“h”为后缀名。如果需要修改一些常数，不必修改每个程序，只需修改一个头文件就可以了。但是应当注意，被包含的文件修改以后，凡包含该文件的所有文件都必须