《结构化程序设计综合训练.ppt》由会员分享,可在线阅读,更多相关《结构化程序设计综合训练.ppt(65页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、结构化程序设计综合训练结构化程序设计综合训练一、本课程的教学目的 结构化程序设计和面向对象程序设计是程序设计的两种典型结构化程序设计和面向对象程序设计是程序设计的两种典型的思想和方法。目前高校开设的程序设计课程也基本据此划的思想和方法。目前高校开设的程序设计课程也基本据此划分为两大系列。分为两大系列。C C语言以其支持结构化的设计和固有的语言特色语言以其支持结构化的设计和固有的语言特色兼具高兼具高级语言和低级语言的功能、丰富灵活的控制和数据结构、简级语言和低级语言的功能、丰富灵活的控制和数据结构、简洁而高效的语句表达、清晰的程序结构和良好的可移植性,洁而高效的语句表达、清晰的程序结构和良好的可
2、移植性,保持着旺盛的生命力,广泛应用于系统软件和应用软件的开保持着旺盛的生命力,广泛应用于系统软件和应用软件的开发中。发中。因此,本课程以因此,本课程以C C语言为工具,通过布置一些程序,进行结语言为工具,通过布置一些程序,进行结构化程序化设计的综合训练,该课程是计算机专业的一门实构化程序化设计的综合训练,该课程是计算机专业的一门实验课,通过该课程的学习,验课,通过该课程的学习,达到以下目的:达到以下目的:2 2课程目的课程目的1在软件工程生命周期开发方法的指导下,深入理解和真正掌握自顶向下、逐步求精的结构化程序设计方法;2.掌握良好的程序设计编码风格;3学习常用的算法设计的技术;4进一步提高
3、学生的程序调试能力;5提高学生的程序编程兴趣。3 3二、教材:本课程是实验课程,主要以学生三性实验为本课程是实验课程,主要以学生三性实验为主。主。实验指导书:实验指导书:ftp:/ 5班班6班班 7班班8班班4 4三、课时的安排序号内 容讲授(学时)实验1结构化程序方法的开发流程1.52管理系统的开发0.53.53游戏程序的开发0.53.54筛选的算法设计技术0.53.55归纳的算法设计技术0.53.56分治的算法设计技术0.53.57最优的算法设计技术0.53.58综合程序开发0.549总结2合计7255 5四、其它说明综合每个实验考核成绩(综合每个实验考核成绩(综合每个实验考核成绩(综合每
4、个实验考核成绩(80%80%),平时的考勤情),平时的考勤情),平时的考勤情),平时的考勤情况(况(况(况(20%20%)等,作为期末的成绩,成绩用五级制。)等,作为期末的成绩,成绩用五级制。)等,作为期末的成绩,成绩用五级制。)等,作为期末的成绩,成绩用五级制。从三个方面考核每个实验的成绩:功能完成情况、从三个方面考核每个实验的成绩:功能完成情况、从三个方面考核每个实验的成绩:功能完成情况、从三个方面考核每个实验的成绩:功能完成情况、实验报告以及程序风格、界面设计以及操作方便实验报告以及程序风格、界面设计以及操作方便实验报告以及程序风格、界面设计以及操作方便实验报告以及程序风格、界面设计以及
5、操作方便性。性。性。性。6 6结构化的开发方法 主要讲述结构化软件开发方法和流程,重点在于自顶向下、逐步求精的结构化程序设计方法和良好的程序设计编码风格,这些是一个优秀的软件开发人员应该具备的基本素质。具备这样的基本素质,无论采用何种程序设计语言,都能够写出结构清晰、易读易懂的好程序。1、结构化开发方法2、结构化方法的开发流程7 71、结构化开发方法 软件开发历史上的诸多惨痛教训使人们逐渐认识到,软件不软件开发历史上的诸多惨痛教训使人们逐渐认识到,软件不等于源代码,大型软件系统的开发与其他工程项目如建造桥等于源代码,大型软件系统的开发与其他工程项目如建造桥梁、制造飞机、轮船等一样,必须有计划进
6、行。梁、制造飞机、轮船等一样,必须有计划进行。软件工程正是随着软件的发展而诞生的一门学科,以提高软软件工程正是随着软件的发展而诞生的一门学科,以提高软件质量、降低开发成本为目的。软件工程将软件的开发视为件质量、降低开发成本为目的。软件工程将软件的开发视为一项工程,借鉴传统工程的原则和方法,将正确的管理方法一项工程,借鉴传统工程的原则和方法,将正确的管理方法和当前能够得到的最好的开发技术结合起来。和当前能够得到的最好的开发技术结合起来。软件工程采用的方法有两种:结构化开发方法和面向对象的软件工程采用的方法有两种:结构化开发方法和面向对象的开发方法,本课程主要介绍结构化开发方法。开发方法,本课程主
7、要介绍结构化开发方法。8 8软件有自己的“生命周期”。一个软件从定义、开发、使用和维护,直到最终被废弃,要经历一个漫长的时期,这就如同一个人要经历胎儿、儿童、青年、中年、老年,直到最终死亡的漫长时期一样。通常把软件经历的这个漫长的时期成为生命周期。9 9 人类在解决复杂问题时普遍采用的一个策略就是人类在解决复杂问题时普遍采用的一个策略就是“各个击破各个击破”,也就是对问题进行分解然后再分别解决各个子问题。,也就是对问题进行分解然后再分别解决各个子问题。结构化的开发方法就是从时间角度对复杂的软件问题进行分结构化的开发方法就是从时间角度对复杂的软件问题进行分解,把软件漫长的生命周期依次分为若干个阶
8、段,每个阶段解,把软件漫长的生命周期依次分为若干个阶段,每个阶段有独立的任务,然后逐步完成每个阶段的任务。前一个阶段有独立的任务,然后逐步完成每个阶段的任务。前一个阶段任务的完成是进行后一个阶段工作的前提和基础,而后一个任务的完成是进行后一个阶段工作的前提和基础,而后一个阶段任务的完成通常使前一个阶段提出的解法更进一步具体阶段任务的完成通常使前一个阶段提出的解法更进一步具体化,增加了更多的实现细节。在每一个阶段结束之前都必须化,增加了更多的实现细节。在每一个阶段结束之前都必须进行正式严格的技术审查和管理复审,若审查通不过,则必进行正式严格的技术审查和管理复审,若审查通不过,则必须进行必要的返工
9、,返工后还要进行审查。审查的一个主要须进行必要的返工,返工后还要进行审查。审查的一个主要标志就是每个阶段都应该提交与所开发的软件完全一致的高标志就是每个阶段都应该提交与所开发的软件完全一致的高质量的文档资料,从而保证在软件开发工程结束时有一个完质量的文档资料,从而保证在软件开发工程结束时有一个完整准确的软件配置交付使用。文档不仅是前后阶段的通信工整准确的软件配置交付使用。文档不仅是前后阶段的通信工具,而且是软件交付使用后进行维护的依据。具,而且是软件交付使用后进行维护的依据。采用结构化的开发方法,使软件开发的全过程以一种有条不采用结构化的开发方法,使软件开发的全过程以一种有条不紊的方式进行,保
10、证了软件的质量,特别是提高了软件的可紊的方式进行,保证了软件的质量,特别是提高了软件的可维护性。维护性。10102、结构化方法的开发流程 在结构化开发中,编码只是软件开发的一个很小的阶段,而在结构化开发中,编码只是软件开发的一个很小的阶段,而且是处在实现阶段。对于且是处在实现阶段。对于c c语言的初学者,由于没有正式接语言的初学者,由于没有正式接受系统化的开发方法的指导,往往会形成一个错误地认识:受系统化的开发方法的指导,往往会形成一个错误地认识:程序的开发就是编码。也就是说,拿到问题后,马上就开始程序的开发就是编码。也就是说,拿到问题后,马上就开始写程序。这种做法的不良后果初学者还无法体会,
11、因为他们写程序。这种做法的不良后果初学者还无法体会,因为他们所面临的需要解决的问题都比较小,但对于复杂的现实问题所面临的需要解决的问题都比较小,但对于复杂的现实问题的解决,即软件项目的开发是绝对行不通的。实际上,在初的解决,即软件项目的开发是绝对行不通的。实际上,在初学者直接编写程序的过程中,大脑已经让初学者无意识地完学者直接编写程序的过程中,大脑已经让初学者无意识地完成了对问题的分析和设计过程,只是没有文档化而已。但对成了对问题的分析和设计过程,只是没有文档化而已。但对于大型软件项目的开发,按步骤形成相应的文档是非常重要于大型软件项目的开发,按步骤形成相应的文档是非常重要的。的。结构化的开发
12、流程可以用如图的瀑布模型来模拟:结构化的开发流程可以用如图的瀑布模型来模拟:1111瀑布模型1212软件生命周期各阶段的主要任务 (1 1 1 1)问题定义:确定系统的目标、规模和基本任务。)问题定义:确定系统的目标、规模和基本任务。)问题定义:确定系统的目标、规模和基本任务。)问题定义:确定系统的目标、规模和基本任务。(2 2 2 2)可行性研究:从经济、技术、法律等方面分析确定系)可行性研究:从经济、技术、法律等方面分析确定系)可行性研究:从经济、技术、法律等方面分析确定系)可行性研究:从经济、技术、法律等方面分析确定系统是否值得开发,及时建议停止项目开发,避免人力、物力、统是否值得开发,
13、及时建议停止项目开发,避免人力、物力、统是否值得开发,及时建议停止项目开发,避免人力、物力、统是否值得开发,及时建议停止项目开发,避免人力、物力、时间的浪费。时间的浪费。时间的浪费。时间的浪费。(3 3 3 3)需求分析:确定软件系统应具备的具体功能。通常用)需求分析:确定软件系统应具备的具体功能。通常用)需求分析:确定软件系统应具备的具体功能。通常用)需求分析:确定软件系统应具备的具体功能。通常用数据流图、数据字典和简明算法描述表示系统的逻辑模型,数据流图、数据字典和简明算法描述表示系统的逻辑模型,数据流图、数据字典和简明算法描述表示系统的逻辑模型,数据流图、数据字典和简明算法描述表示系统的
14、逻辑模型,防止系统的设计与用户的实际需求不相符的后果。防止系统的设计与用户的实际需求不相符的后果。防止系统的设计与用户的实际需求不相符的后果。防止系统的设计与用户的实际需求不相符的后果。(4 4 4 4)概要设计:确定系统设计方案,软件的体系结构。确)概要设计:确定系统设计方案,软件的体系结构。确)概要设计:确定系统设计方案,软件的体系结构。确)概要设计:确定系统设计方案,软件的体系结构。确定软件由哪些模块组成以及这些模块之间的相互关系。定软件由哪些模块组成以及这些模块之间的相互关系。定软件由哪些模块组成以及这些模块之间的相互关系。定软件由哪些模块组成以及这些模块之间的相互关系。(5 5 5
15、5)详细设计:描述应该如何具体地实现系统。详细设计)详细设计:描述应该如何具体地实现系统。详细设计)详细设计:描述应该如何具体地实现系统。详细设计)详细设计:描述应该如何具体地实现系统。详细设计每个模块,确定实现模块所需要的算法和数据结构。每个模块,确定实现模块所需要的算法和数据结构。每个模块,确定实现模块所需要的算法和数据结构。每个模块,确定实现模块所需要的算法和数据结构。1313(6 6 6 6)软件实现阶段:进行程序设计(编码)和模块测试。)软件实现阶段:进行程序设计(编码)和模块测试。)软件实现阶段:进行程序设计(编码)和模块测试。)软件实现阶段:进行程序设计(编码)和模块测试。(7
16、7 7 7)综合测试阶段:通过各种类型的测试,查出软件设计)综合测试阶段:通过各种类型的测试,查出软件设计)综合测试阶段:通过各种类型的测试,查出软件设计)综合测试阶段:通过各种类型的测试,查出软件设计中的错误并改正,确保软件质量;还要在用户的参与下进行中的错误并改正,确保软件质量;还要在用户的参与下进行中的错误并改正,确保软件质量;还要在用户的参与下进行中的错误并改正,确保软件质量;还要在用户的参与下进行验收,才可交付使用。验收,才可交付使用。验收,才可交付使用。验收,才可交付使用。(8 8 8 8)软件运行、维护:软件运行期间,通过各种必要的维)软件运行、维护:软件运行期间,通过各种必要的
17、维)软件运行、维护:软件运行期间,通过各种必要的维)软件运行、维护:软件运行期间,通过各种必要的维护使系统改正错误、或修改扩充功能使软件适应环境变化,护使系统改正错误、或修改扩充功能使软件适应环境变化,护使系统改正错误、或修改扩充功能使软件适应环境变化,护使系统改正错误、或修改扩充功能使软件适应环境变化,以便延长软件的使用寿命,提高软件的效益。每次维护的要以便延长软件的使用寿命,提高软件的效益。每次维护的要以便延长软件的使用寿命,提高软件的效益。每次维护的要以便延长软件的使用寿命,提高软件的效益。每次维护的要求及修改步骤都应详细准确地记录下来,作为文档保存。求及修改步骤都应详细准确地记录下来,
18、作为文档保存。求及修改步骤都应详细准确地记录下来,作为文档保存。求及修改步骤都应详细准确地记录下来,作为文档保存。本课程虽然不是进行大型软件项目的开发,只是针对于较大本课程虽然不是进行大型软件项目的开发,只是针对于较大本课程虽然不是进行大型软件项目的开发,只是针对于较大本课程虽然不是进行大型软件项目的开发,只是针对于较大型的综合程序的开发,开发过程也应该遵循结构化的瀑布模型的综合程序的开发,开发过程也应该遵循结构化的瀑布模型的综合程序的开发,开发过程也应该遵循结构化的瀑布模型的综合程序的开发,开发过程也应该遵循结构化的瀑布模型的开发流程,遵循问题定义、程序分析、程序设计、编码、型的开发流程,遵
19、循问题定义、程序分析、程序设计、编码、型的开发流程,遵循问题定义、程序分析、程序设计、编码、型的开发流程,遵循问题定义、程序分析、程序设计、编码、测试和维护几个阶段,培养结构化方法的能力。测试和维护几个阶段,培养结构化方法的能力。测试和维护几个阶段,培养结构化方法的能力。测试和维护几个阶段,培养结构化方法的能力。14142.1 2.1 问题定义问题定义 问题定义阶段是整个过程中占用时间最少的阶段,在这个步问题定义阶段是整个过程中占用时间最少的阶段,在这个步骤中任务是明确要解决的问题是什么。在本课程中,要解决骤中任务是明确要解决的问题是什么。在本课程中,要解决的问题可以由教师提供或由学生自行选题
20、。在自行选题中,的问题可以由教师提供或由学生自行选题。在自行选题中,学生可以动动脑筋,寻找身边有哪些事情可以用计算机解决,学生可以动动脑筋,寻找身边有哪些事情可以用计算机解决,然后确定一个可行的题目,例如扫雷游戏、迷宫游戏等。有然后确定一个可行的题目,例如扫雷游戏、迷宫游戏等。有时可以对该题目进行一个简要的说明。例如迷宫游戏的问题时可以对该题目进行一个简要的说明。例如迷宫游戏的问题描述如下:描述如下:心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多墙壁,对前进方向形成了多处障碍,心宫。迷宫中设置很多墙壁,对前进方向形成了
21、多处障碍,心理学家在迷宫的唯一出口放置了一块奶酪,吸引老鼠在迷宫理学家在迷宫的唯一出口放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。用计算机求解迷宫中的一条路径。中寻找通路以到达出口。用计算机求解迷宫中的一条路径。15152.2 2.2 程序分析程序分析这个阶段的任务仍然不是具体地解决问题,而是理解问题和分析问题,主要是确定目标系统必须具备哪些功能,以及目标系统可能的输入和输出数据是什么。我们在问题定义阶段得到的问题,有时仅仅是一个抽象的题目,有时除了题目外还附一段简要的说明。无论问题以何种形式出现,都需要做进一步的分析,以获得系统必须实现哪些功能。1616例如对于迷宫游戏,可以分析系统
22、需要以下几个功能:1迷宫的设置,为了系统的适用性,迷宫不能固定,应该可以变化。2迷宫路径的寻找,该功能可以扩展,寻找一条路径、全部路径、最短路径。3迷宫路径的输出。到这里,程序分析的工作结束,接下来进入下一个阶段:程序设计。17172.3 2.3 程序设计程序设计经过程序分析阶段的工作,程序必须经过程序分析阶段的工作,程序必须“做什么做什么”已已经清楚了,现在是决定经清楚了,现在是决定“怎么做怎么做”的时候了。程序的时候了。程序这个阶段的设计工作,应该对要解决的问题设计出这个阶段的设计工作,应该对要解决的问题设计出具体的解决方案,得出对目标系统的精确描述,从具体的解决方案,得出对目标系统的精确
23、描述,从而在编码阶段可以把这个描述直接翻译成用而在编码阶段可以把这个描述直接翻译成用C C语言语言书写的程序。程序设计将采用结构化程序设计方法,书写的程序。程序设计将采用结构化程序设计方法,自顶向下逐步求精地设计出程序的实现自顶向下逐步求精地设计出程序的实现“蓝图蓝图”。下面,首先介绍结构化程序设计方法,然后列举描下面,首先介绍结构化程序设计方法,然后列举描述算法的常用工具,接着以迷宫游戏为例,详细说述算法的常用工具,接着以迷宫游戏为例,详细说明设计阶段的工作和结构化程序设计方法的应用。明设计阶段的工作和结构化程序设计方法的应用。18182.3.1结构化程序设计方法结构程序设计的概念最早是由结
24、构程序设计的概念最早是由E.W.DijkstraE.W.Dijkstra提出来的,提出来的,是为了解决程序可读性差的问题,创立一种新的程是为了解决程序可读性差的问题,创立一种新的程序设计思想、方法和风格,以显著提高软件生产率序设计思想、方法和风格,以显著提高软件生产率和质量。和质量。在软件发展的早期,即在软件发展的早期,即2020世纪世纪6060年代末到年代末到7070年代初,年代初,虽然科技在高速发展,程序规模越来越大,但是当虽然科技在高速发展,程序规模越来越大,但是当时的编程技术却停留在手工作业的方式:设计各自时的编程技术却停留在手工作业的方式:设计各自为政、滥用为政、滥用GOTOGOTO
25、语句造成程序效率低下、可读性语句造成程序效率低下、可读性差、无章可循、错误百出、调试困难。差、无章可循、错误百出、调试困难。在这种局面下,在这种局面下,DijkstraDijkstra提出结构化程序设计的理论。提出结构化程序设计的理论。经过多年的实践,结构化程序设计的理论和实践日经过多年的实践,结构化程序设计的理论和实践日益完善,成为现代程序设计的主流方法之一。益完善,成为现代程序设计的主流方法之一。1919那么什么是结构化程序设计呢?结构化程序设计是一种设计程序的技术,采用自顶结构化程序设计是一种设计程序的技术,采用自顶向下逐步求精的设计方法和单入口单出口的顺序、向下逐步求精的设计方法和单入
26、口单出口的顺序、选择和循环三种基本控制结构。它提出的原则可归选择和循环三种基本控制结构。它提出的原则可归纳为纳为3232字:字:“自顶向下,逐步细化;清晰第一,效自顶向下,逐步细化;清晰第一,效率第二;书写规范,缩进格式;基本结构,组合而率第二;书写规范,缩进格式;基本结构,组合而成。成。”自顶向下,逐步求精方法符合人们解决复杂问题的自顶向下,逐步求精方法符合人们解决复杂问题的普遍规律,可提高软件开发的成功率和生产率,这普遍规律,可提高软件开发的成功率和生产率,这种方法采用先全局后局部、先整体后细节、先抽象种方法采用先全局后局部、先整体后细节、先抽象后具体的逐步求精过程,开发出来的程序具有清晰
27、后具体的逐步求精过程,开发出来的程序具有清晰的层次结构,因此程序容易阅读和理解。的层次结构,因此程序容易阅读和理解。2020例如设计房屋就采用了这种方法,先进行整体规划,然后确定建筑物的方案,在进行各部分的设计,最后进行门窗、楼道等的细节设计。例:要求用筛选法求100 以内的素数(筛选法为:从2到100中去掉2,3,9,10的倍数,剩下的就是100以内的素数)。2121步骤一:建立2到100的数组A,其中Ai=i;_1建立2到10的素数表B,其中存放2到10以内的素数;_ _2 Ai=i 是B 中的任一数的倍数,则剔除Ai;_ _3输出A 中所没有被剔除的数;_42222步骤二:前述框架中每一
28、个加工语句都可进一步细化。/*/*建立建立2 2到到100100的数组的数组A A,其中,其中AiAi=i*/=i*/_1_1 for(i=2;i =100;i+)for(i=2;i =100;i+)AiAi=i;=i;/*/*建立建立2 2到到1010的素数表的素数表B B,其中存放,其中存放2 2到到1010以内的素数以内的素数*/_2/_2 B1=2;B2=3;B3=5;B4=7;B1=2;B2=3;B3=5;B4=7;/*/*若若AiAi=i=i 是是B B 中的任一数的倍数,则剔除中的任一数的倍数,则剔除AiAi*/_3*/_3 for(j=1;j =4;j+)for(j=1;j =
29、4;j+)检查检查A A 所有的数能否被所有的数能否被BjBj 整除,并将能被整除的数从整除,并将能被整除的数从A A 中中剔除;剔除;_3.1_3.1/*/*输出输出A A 中所有没有被剔除的数中所有没有被剔除的数*/_4_4 for(i=2;i =100;i+)for(i=2;i =100;i+)若若AiAi 没有被剔除,则输出之;没有被剔除,则输出之;_4.1_4.12323步骤三:将3.1,4.1进一步细化形成程序。24242.3.2 常用设计工具自然语言在语法和语义上具有多义性,常常要依赖上下文才能把问题交代清楚,而且即使可以描述,也需要大量的篇幅,非常繁琐。所以必须用简洁的方法表达
30、整体结构,约束性强的方式表达算法。设计工具可以对设计进行无歧义的描述,能指明控制流程、处理流程以及其他方面的实现细节。下面介绍三种常用的图形方式的设计工具。2525层次图层次图用来描述软件的层次结构,图中的一个矩形框代表一个模块,方框之间的连线表示调用关系。层次图很适合在自顶向下设计软件的过程中使用。26262727程序流程图程序流程图是历史最悠久使用最广泛的描述软件设计的方法。是历史最悠久使用最广泛的描述软件设计的方法。它的主要优点是对控制流程的描述很直观,便于初它的主要优点是对控制流程的描述很直观,便于初学者掌握。学者掌握。但这种用箭头代表控制流的方法,容易使程序员不但这种用箭头代表控制流
31、的方法,容易使程序员不受任何约束,可以完全不顾结构化程序设计的精神,受任何约束,可以完全不顾结构化程序设计的精神,随意转移控制。另外,程序流程图不易表示数据结随意转移控制。另外,程序流程图不易表示数据结构。因此,程序流程图不是逐步求精的工具。构。因此,程序流程图不是逐步求精的工具。下图是国家标准下图是国家标准GB1526-1989GB1526-1989程序流程图中常用的程序流程图中常用的符号,与通用不同之处,在于取消了箭头。符号,与通用不同之处,在于取消了箭头。28282929盒图盒图是一种很好的支持结构化程序设计思想的图形工具。盒图上能明确表达功能域,不可能任意转移控制,很容易确定局部和全局
32、数据的作用域,很容易表现嵌套关系,而且也可以表示模块的层次结构。所以坚持使用盒图作为设计工具,可以使程序员逐步养成用结构化的方式思考问题和解决问题的习惯。3030顺序结构顺序结构块块1块块2块块3块块4条件条件T F块块1块块2选择结构选择结构Case I=1,2,3T块块1块块2多分支选择结构多分支选择结构F块块3块块当条件成立时当条件成立时当型循环当型循环块块直到条件成立时直到条件成立时直到型循环直到型循环3131伪代码图形工具表示设计比较直观,但画起来比较费劲,图形工具表示设计比较直观,但画起来比较费劲,所以描述设计还可以使用伪代码这个常用的语言工所以描述设计还可以使用伪代码这个常用的语
33、言工具。伪代码是一种具。伪代码是一种“混合混合”语言,它使用一种语言语言,它使用一种语言通常是某种自然语言的词汇,同时却使用某种通常是某种自然语言的词汇,同时却使用某种结构化程序设计的语法。这样,它具有严格的关键结构化程序设计的语法。这样,它具有严格的关键字外部语法,而表示实际操作和条件的内部语法又字外部语法,而表示实际操作和条件的内部语法又是灵活自由的,书写方便,也比较好懂。是灵活自由的,书写方便,也比较好懂。“用筛选法求用筛选法求100 100 以内的素数以内的素数”的算法描述就是伪的算法描述就是伪代码方式。代码方式。32322.3.3 迷宫游戏的设计现阶段的设计任务是自顶向下逐步求精,具
34、体要完成以下几点:继续分析已有功能,直到精化出所有子功能,确继续分析已有功能,直到精化出所有子功能,确定模块之间的接口。定模块之间的接口。描述精化后每个模块的处理过程。描述精化后每个模块的处理过程。确定主要的数据以及数据结构。确定主要的数据以及数据结构。确定输入输出数据的内外部形式。确定输入输出数据的内外部形式。进行界面的设计。进行界面的设计。以下将展示迷宫游戏的设计。33331)数据结构的设计(1 1)迷宫的表示)迷宫的表示 设迷宫为设迷宫为mm行行n n列,利用二维数组列,利用二维数组mazemnmazemn 来表来表示一个迷宫,其中入口点为(示一个迷宫,其中入口点为(1 1,1 1),出
35、口为),出口为(mm,n n),),mazeijmazeij=0=0或或1 1,其中,其中0 0表示通路,表示通路,1 1表示不通。当从某点试探时,有表示不通。当从某点试探时,有8 8个方向可以试探个方向可以试探,而四个角点有,而四个角点有3 3个方向,其他边缘点有个方向,其他边缘点有5 5个方向,个方向,为使问题简单化为使问题简单化,在迷宫的四周加了一层,表示墙在迷宫的四周加了一层,表示墙壁,这样每个点的试探方向为壁,这样每个点的试探方向为8 8。#define m 6 /*#define m 6 /*迷宫行数迷宫行数迷宫行数迷宫行数*/#define n 8 /*#define n 8 /
36、*迷宫列数迷宫列数迷宫列数迷宫列数*/typedeftypedef structstruct intint x,y;itemx,y;item;/*;/*坐标坐标坐标坐标*/intint mzem+2n+2 mzem+2n+2;/*/*迷宫迷宫迷宫迷宫*/3434(2)试探方向的表示在上述表示迷宫的情况下,每个点有在上述表示迷宫的情况下,每个点有8 8个方向可以试个方向可以试探,设当前点的坐标为(探,设当前点的坐标为(x x,y y),与其相邻的),与其相邻的8 8个个点的坐标可根据与该点的相邻方位得到。为了方便点的坐标可根据与该点的相邻方位得到。为了方便求出新点的坐标,将从正东开始沿顺时针进行
37、的这求出新点的坐标,将从正东开始沿顺时针进行的这8 8个方向的坐标增量放在一个结构数组个方向的坐标增量放在一个结构数组move8move8中,中,其中其中x x表示横坐标增量,表示横坐标增量,y y表示纵坐标增量。表示纵坐标增量。typedeftypedef structstruct intint x,y;itemx,y;item;/*;/*坐标坐标*/item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;-1,0,-1,1;3535(3)保存到达的每一点的位置及试探方向的
38、数据结构利用回溯法,从入口处出发,按某一方向不断试探,利用回溯法,从入口处出发,按某一方向不断试探,若能走通,则到达新点,否则试探另一未试探过的若能走通,则到达新点,否则试探另一未试探过的方向。若所有的方向均没有通路,则沿原路返回前方向。若所有的方向均没有通路,则沿原路返回前一点,换一个未试探过的通路继续试探,直到找到一点,换一个未试探过的通路继续试探,直到找到出口,或所有的通路都试探过,未找到一条通路回出口,或所有的通路都试探过,未找到一条通路回到出口点。在试探过程中,为保证在到达某一点无到出口点。在试探过程中,为保证在到达某一点无路时,能正确返回前一点,需要用一个数据结构路时,能正确返回前
39、一点,需要用一个数据结构(栈)来保存到达的每一点的位置及试探方向。(栈)来保存到达的每一点的位置及试探方向。当到达了某点无路可走,需从前一点的下一个方向当到达了某点无路可走,需从前一点的下一个方向试探。因此,压入栈中的不仅是顺序到达的各点的试探。因此,压入栈中的不仅是顺序到达的各点的坐标,而且还有从前一点到达本点的方向序号。坐标,而且还有从前一点到达本点的方向序号。3636#define MAXSIZE 20typedef struct int x,y,d;datatype;typedef struct datatype dataMAXSIZE;int top;SeqStack;37372)功
40、能求精在前面已经分析出系统的目标和主要功能,但这仅仅是程序层次结构中最上层的部分,划分的功能比较抽象,需要进一步的精化。下面用层次图表示各部分的功能以及功能之间的调用关系。38383939对每个功能还需要进一步说明完成的主要功能、输入输出以及内部的数据结构和算法。下面只针对主控模块和找路径模块进行详细说明。4040主控模块main():用来进行各个数据的初始化,并进行功能的选择。主控模块的流程图如下:4141ny开始设置迷宫找路径输出路径继续?关闭游戏结束4242迷宫设置模块int setmaze(mazestruct *maze):用来设置迷宫以及出入口,其中出入口在迷宫中的值必须为1,否则
41、重新设置。成功返回1,失败返回0。Maze为设置的迷宫。(算法略)4343找路径int findpath(mazestruct *maze,SeqStack *path):用来选择路径,找到返回1,否则返回0。找到的路径存储在path中。算法的设计如下:防止重复到达某点的考虑:为避免发生死循环,防止重复到达某点的考虑:为避免发生死循环,当到达某点(当到达某点(i i,j j)后,使)后,使mazeijmazeij 置置-1-1,以便,以便区分未到达过的顶点。算法结束前可恢复原迷区分未到达过的顶点。算法结束前可恢复原迷宫。宫。算法描述算法描述4444 栈初始化;栈初始化;将入口点坐标及初始试探方
42、向(设为将入口点坐标及初始试探方向(设为-1-1)入栈)入栈,并将入口点并将入口点设置为已走过;设置为已走过;设置未找到设置未找到found=0found=0;whilewhile(未找到(未找到&栈非空)栈非空)*从栈顶元素位置出发寻找下一个可以走的方位;从栈顶元素位置出发寻找下一个可以走的方位;if(if(找到方位找到方位)修改栈顶元素的方位值修改栈顶元素的方位值;计算新点计算新点,并设置为已走过并设置为已走过;将新点位置及初始试探方位值进栈将新点位置及初始试探方位值进栈;if(if(新点是结束点新点是结束点)结束结束;else /else /没找到可走的方位没找到可走的方位,说明从该点出
43、发已无路可走说明从该点出发已无路可走 出栈出栈;if(if(找到找到)打印路径打印路径;else;else 打印打印”该迷宫无路径该迷宫无路径”;4545路径输出void printpath(SeqStack *path):将找到的路径输出。(算法略)46463)界面设计软件界面设计应该以使用软件的人为中心,尽量从使用软件的角度出发设计界面。迷宫游戏的界面比较简单,一开始显示系统的功能、设计者、系统使用说明。然后询问“是否开始游戏?”,回答“y”则开始。在进行迷宫设置的界面中要提供帮助说明。47472.4 2.4 编码编码编码就是用高等语言表示设计阶段产生的算法。在编码就是用高等语言表示设计阶
44、段产生的算法。在编码阶段,可以使我们再次体会到使用结构化程序编码阶段,可以使我们再次体会到使用结构化程序设计技术的主要优点:设计技术的主要优点:用先全局后局部、先整体后细节、先抽象后具体的逐步用先全局后局部、先整体后细节、先抽象后具体的逐步求精过程开发出的程序有清晰的层次结构,容易阅读和求精过程开发出的程序有清晰的层次结构,容易阅读和理解;理解;不使用不使用GOTOGOTO语句仅使用单入口单出口的控制结构,使得语句仅使用单入口单出口的控制结构,使得程序的静态结构和它的动态执行情况比较一致,容易保程序的静态结构和它的动态执行情况比较一致,容易保证程序开发时的正确性和易纠错性;证程序开发时的正确性
45、和易纠错性;控制结构有确定的逻辑模式,编写程序代码只限于使用控制结构有确定的逻辑模式,编写程序代码只限于使用很少的几种直截了当的方式,使程序容易测试;很少的几种直截了当的方式,使程序容易测试;程序清晰和模块化使得在修改和重新设计一个软件时可程序清晰和模块化使得在修改和重新设计一个软件时可以重用的代码量最大等。以重用的代码量最大等。4848因此,结构化程序设计技术能够保证我们得到结构化程序。这种程序便于编写、阅读、修改和维护,减少了程序出错的机会,提高了程序的可靠性,保证了程序的质量。下面讲述在程序编码时应该注意的几个问题:49492.4.1 全局变量 全局变量的作用增加了函数间数据联系的渠道。
46、但是全局变量使函数的全局变量的作用增加了函数间数据联系的渠道。但是全局变量使函数的通用性降低了,因为函数在执行时要依赖于其所在的全局变量。如果将通用性降低了,因为函数在执行时要依赖于其所在的全局变量。如果将一个函数移到另一个文件中,还要将有关的全局变量以及其值一起移过一个函数移到另一个文件中,还要将有关的全局变量以及其值一起移过去。但若该全局变量与其它文件的全局变量同名时,就会出现问题,降去。但若该全局变量与其它文件的全局变量同名时,就会出现问题,降低了程序的可靠性和通用性。在程序设计中,在划分模块时要求模块的低了程序的可靠性和通用性。在程序设计中,在划分模块时要求模块的“内聚性内聚性”强,与
47、其他模块的强,与其他模块的“耦合性耦合性”弱。即模块的功能单一,与其弱。即模块的功能单一,与其他模块的相互影响要尽量少,而用全局变量是不符合这个原则的。他模块的相互影响要尽量少,而用全局变量是不符合这个原则的。一般一般要求把要求把c c程序中的函数作成一个封闭体,除了可以通过程序中的函数作成一个封闭体,除了可以通过“实参实参-形参形参”与与外界发生联系外,没有其他渠道。这样的程序移植性好,可读性强外界发生联系外,没有其他渠道。这样的程序移植性好,可读性强。另外使用全局变量过多,会降低程序的清晰性,人们往往难以清楚地判另外使用全局变量过多,会降低程序的清晰性,人们往往难以清楚地判断出每个瞬间每个
48、全局变量的值。在各个函数执行时都可能改变全局变断出每个瞬间每个全局变量的值。在各个函数执行时都可能改变全局变量的值,程序容易出错。量的值,程序容易出错。对于大型程序,模块多,常常由不同的人来完成不同的模块,如果全局对于大型程序,模块多,常常由不同的人来完成不同的模块,如果全局变量随意使用,更容易出现问题,造成程序的混乱。因此,更应该限制变量随意使用,更容易出现问题,造成程序的混乱。因此,更应该限制使用全局变量。使用全局变量。50502.4.2 风格结构化程序的一大特征就是清晰可读。风格的作用结构化程序的一大特征就是清晰可读。风格的作用主要就是使代码容易读,无论是对程序员本人,还主要就是使代码容
49、易读,无论是对程序员本人,还是对其他人,代码应该是清晰的和简单的,具有直是对其他人,代码应该是清晰的和简单的,具有直截了当的逻辑、自然的表达式、通用的语言使用方截了当的逻辑、自然的表达式、通用的语言使用方式、有意义的名字和有帮助作用的注释等。一致性式、有意义的名字和有帮助作用的注释等。一致性是非常重要的,如果大家都坚持同样的风格,代码是非常重要的,如果大家都坚持同样的风格,代码就容易读懂。就容易读懂。下面将对比一些小程序设计例子来说明与风格有关下面将对比一些小程序设计例子来说明与风格有关的规则,其中用灰色标记的代码段代表了不好风格的规则,其中用灰色标记的代码段代表了不好风格的代码段。的代码段。
50、5151(1)名字 一个名字应该是非形式的、简练的、易记忆的,若可能的话,一个名字应该是非形式的、简练的、易记忆的,若可能的话,最好是能够拼读的。一个变量等作用域越大,它的名字所携最好是能够拼读的。一个变量等作用域越大,它的名字所携带的信息就应该越多。全局变量使用具有说明性的语言,局带的信息就应该越多。全局变量使用具有说明性的语言,局部变量使用短名字。全局变量可出现在整个程序的任何地方,部变量使用短名字。全局变量可出现在整个程序的任何地方,因此其名字应具有足够的说明性,以便使读者能够记住它们因此其名字应具有足够的说明性,以便使读者能够记住它们是干什么的。给每个全局变量声明附一个简短的注释也是非