结构化程序设计综合训练
一、本课程的教学目的
结构化程序设计和面向对象程序设计是程序设计的两种典型结构化程序设计和面向对象程序设计是程序设计的两种典型
的思想和方法。目前高校开设的程序设计课程也基本据此划的思想和方法。目前高校开设的程序设计课程也基本据此划
分为两大系列。分为两大系列。
CC语言以其支持结构化的设计和固有的语言特色语言以其支持结构化的设计和固有的语言特色————兼具高兼具高
级语言和低级语言的功能、丰富灵活的控制和数据结构、简级语言和低级语言的功能、丰富灵活的控制和数据结构、简
洁而高效的语句表达、清晰的程序结构和良好的可移植性，洁而高效的语句表达、清晰的程序结构和良好的可移植性，
保持着旺盛的生命力，广泛应用于系统软件和应用软件的开保持着旺盛的生命力，广泛应用于系统软件和应用软件的开
发中。发中。
因此，本课程以因此，本课程以CC语言为工具，通过布置一些程序，进行结语言为工具，通过布置一些程序，进行结
构化程序化设计的综合训练，该课程是计算机专业的一门实构化程序化设计的综合训练，该课程是计算机专业的一门实
验课，通过该课程的学习，验课，通过该课程的学习，
达到以下目的：达到以下目的：
22
课程目的
1．在软件工程生命周期开发方法的指导下，
深入理解和真正掌握自顶向下、逐步求精的
结构化程序设计方法；
2. 掌握良好的程序设计编码风格；
3．学习常用的算法设计的技术；
4．进一步提高学生的程序调试能力；
5．提高学生的程序编程兴趣。
33
二、教材：
本课程是实验课程，主要以学生三性实验为
主。
实验指导书：ftp:// 课件下载
/结构化程序设计训练
实验报告、源代码、可执行程序等发到
jsj080506 @ 5班6班
jsj080708@ 7班8班
44
mailto:jsj080708@
三、课时的安排
序号序号 内内 容容
讲讲授授
((学学时时))
实验实验
11 结构化程序方法的开发流程结构化程序方法的开发流程
22 管理系统的开发管理系统的开发
33 游游戏戏程序的程序的开发开发
44 筛选的算法设计技术筛选的算法设计技术
55 归纳归纳的算法的算法设计设计技技术术
66 分治的算法分治的算法设计设计技技术术
77 最最优优的算法的算法设计设计技技术术
88 综综合程序合程序开发开发 44
99 总结总结 22
合合计计 77 2525 55
四、其它说明
– 综合每个实验考核成绩（综合每个实验考核成绩（80%80%），平时的考勤情），平时的考勤情
况（况（20%20%）等，作为期末的成绩，成绩用五级制。）等，作为期末的成绩，成绩用五级制。
– 从三个方面考核每个实验的成绩：功能完成情况、从三个方面考核每个实验的成绩：功能完成情况、
实验报告以及程序风格、界面设计以及操作方便实验报告以及程序风格、界面设计以及操作方便
性。性。
66
结构化的开发方法
主要讲述结构化软件开发方法和流程，重点
在于自顶向下、逐步求精的结构化程序设计
方法和良好的程序设计编码风格，这些是一
个优秀的软件开发人员应该具备的基本素质。
具备这样的基本素质，无论采用何种程序设
计语言，都能够写出结构清晰、易读易懂的
好程序。
1、结构化开发方法
2、结构化方法的开发流程
77
1、结构化开发方法
软件开发历史上的诸多惨痛教训使人们逐渐认识到，软件不软件开发历史上的诸多惨痛教训使人们逐渐认识到，软件不
等于源代码，大型软件系统的开发与其他工程项目如建造桥等于源代码，大型软件系统的开发与其他工程项目如建造桥
梁、制造飞机、轮船等一样，必须有计划进行。梁、制造飞机、轮船等一样，必须有计划进行。
软件工程正是随着软件的发展而诞生的一门学科，以提高软软件工程正是随着软件的发展而诞生的一门学科，以提高软
件质量、降低开发成本为目的。软件工程将软件的开发视为件质量、降低开发成本为目的。软件工程将软件的开发视为
一项工程，借鉴传统工程的原则和方法，将正确的管理方法一项工程，借鉴传统工程的原则和方法，将正确的管理方法
和当前能够得到的最好的开发技术结合起来。和当前能够得到的最好的开发技术结合起来。
软件工程采用的方法有两种：结构化开发方法和面向对象的软件工程采用的方法有两种：结构化开发方法和面向对象的
开发方法，本课程主要介绍结构化开发方法。开发方法，本课程主要介绍结构化开发方法。
88
软件有自己的“生命周期”。一个软件从定
义、开发、使用和维护，直到最终被废弃，
要经历一个漫长的时期，这就如同一个人要
经历胎儿、儿童、青年、中年、老年，直到
最终死亡的漫长时期一样。通常把软件经历
的这个漫长的时期成为生命周期。
99
人类在解决复杂问题时普遍采用的一个策略就是人类在解决复杂问题时普遍采用的一个策略就是““各个击破各个击破
””，也就是对问题进行分解然后再分别解决各个子问题。，也就是对问题进行分解然后再分别解决各个子问题。
结构化的开发方法就是从时间角度对复杂的软件问题进行分结构化的开发方法就是从时间角度对复杂的软件问题进行分
解，把软件漫长的生命周期依次分为若干个阶段，每个阶段解，把软件漫长的生命周期依次分为若干个阶段，每个阶段
有独立的任务，然后逐步完成每个阶段的任务。前一个阶段有独立的任务，然后逐步完成每个阶段的任务。前一个阶段
任务的完成是进行后一个阶段工作的前提和基础，而后一个任务的完成是进行后一个阶段工作的前提和基础，而后一个
阶段任务的完成通常使前一个阶段提出的解法更进一步具体阶段任务的完成通常使前一个阶段提出的解法更进一步具体
化，增加了更多的实现细节。在每一个阶段结束之前都必须化，增加了更多的实现细节。在每一个阶段结束之前都必须
进行正式严格的技术审查和管理复审，若审查通不过，则必进行正式严格的技术审查和管理复审，若审查通不过，则必
须进行必要的返工，返工后还要进行审查。审查的一个主要须进行必要的返工，返工后还要进行审查。审查的一个主要
标志就是每个阶段都应该提交与所开发的软件完全一致的高标志就是每个阶段都应该提交与所开发的软件完全一致的高
质量的文档资料，从而保证在软件开发工程结束时有一个完质量的文档资料，从而保证在软件开发工程结束时有一个完
整准确的软件配置交付使用。文档不仅是前后阶段的通信工整准确的软件配置交付使用。文档不仅是前后阶段的通信工
具，而且是软件交付使用后进行维护的依据。具，而且是软件交付使用后进行维护的依据。
采用结构化的开发方法，使软件开发的全过程以一种有条不采用结构化的开发方法，使软件开发的全过程以一种有条不
紊的方式进行，保证了软件的质量，特别是提高了软件的可紊的方式进行，保证了软件的质量，特别是提高了软件的可
维护性。维护性。
1010
2、结构化方法的开发流程
在结构化开发中，编码只是软件开发的一个很小的阶段，而在结构化开发中，编码只是软件开发的一个很小的阶段，而
且是处在实现阶段。对于且是处在实现阶段。对于cc语言的初学者，由于没有正式接语言的初学者，由于没有正式接
受系统化的开发方法的指导，往往会形成一个错误地认识：受系统化的开发方法的指导，往往会形成一个错误地认识：
程序的开发就是编码。也就是说，拿到问题后，马上就开始程序的开发就是编码。也就是说，拿到问题后，马上就开始
写程序。这种做法的不良后果初学者还无法体会，因为他们写程序。这种做法的不良后果初学者还无法体会，因为他们
所面临的需要解决的问题都比较小，但对于复杂的现实问题所面临的需要解决的问题都比较小，但对于复杂的现实问题
的解决，即软件项目的开发是绝对行不通的。实际上，在初的解决，即软件项目的开发是绝对行不通的。实际上，在初
学者直接编写程序的过程中，大脑已经让初学者无意识地完学者直接编写程序的过程中，大脑已经让初学者无意识地完
成了对问题的分析和设计过程，只是没有文档化而已。但对成了对问题的分析和设计过程，只是没有文档化而已。但对
于大型软件项目的开发，按步骤形成相应的文档是非常重要于大型软件项目的开发，按步骤形成相应的文档是非常重要
的。的。
结构化的开发流程可以用如图的瀑布模型来模拟：结构化的开发流程可以用如图的瀑布模型来模拟：
1111
瀑布模型
1212
软件生命周期各阶段的主要任务
（（11）问题定义：确定系统的目标、规模和基本任务。）问题定义：确定系统的目标、规模和基本任务。
（（22）可行性研究：从经济、技术、法律等方面分析确定系）可行性研究：从经济、技术、法律等方面分析确定系
统是否值得开发，及时建议停止项目开发，避免人力、物力、统是否值得开发，及时建议停止项目开发，避免人力、物力、
时间的浪费。时间的浪费。
（（33）需求分析：确定软件系统应具备的具体功能。通常用）需求分析：确定软件系统应具备的具体功能。通常用
数据流图、数据字典和简明算法描述表示系统的逻辑模型，数据流图、数据字典和简明算法描述表示系统的逻辑模型，
防止系统的设计与用户的实际需求不相符的后果。防止系统的设计与用户的实际需求不相符的后果。
（（44）概要设计：确定系统设计方案，软件的体系结构。确）概要设计：确定系统设计方案，软件的体系结构。确
定软件由哪些模块组成以及这些模块之间的相互关系。定软件由哪些模块组成以及这些模块之间的相互关系。
（（55）详细设计：描述应该如何具体地实现系统。详细设计）详细设计：描述应该如何具体地实现系统。详细设计
每个模块，确定实现模块所需要的算法和数据结构。每个模块，确定实现模块所需要的算法和数据结构。
1313
（（66）软件实现阶段：进行程序设计（编码）和模块测试。）软件实现阶段：进行程序设计（编码）和模块测试。
（（77）综合测试阶段：通过各种类型的测试，查出软件设计）综合测试阶段：通过各种类型的测试，查出软件设计
中的错误并改正，确保软件质量；还要在用户的参与下进行中的错误并改正，确保软件质量；还要在用户的参与下进行
验收，才可交付使用。验收，才可交付使用。
（（88）软件运行、维护：软件运行期间，通过各种必要的维）软件运行、维护：软件运行期间，通过各种必要的维
护使系统改正错误、或修改扩充功能使软件适应环境变化，护使系统改正错误、或修改扩充功能使软件适应环境变化，
以便延长软件的使用寿命，提高软件的效益。每次维护的要以便延长软件的使用寿命，提高软件的效益。每次维护的要
求及修改步骤都应详细准确地记录下来，作为文档保存。求及修改步骤都应详细准确地记录下来，作为文档保存。
本课程虽然不是进行大型软件项目的开发，只是针对于较大本课程虽然不是进行大型软件项目的开发，只是针对于较大
型的综合程序的开发，开发过程也应该遵循结构化的瀑布模型的综合程序的开发，开发过程也应该遵循结构化的瀑布模
型的开发流程，遵循问题定义、程序分析、程序设计、编码、型的开发流程，遵循问题定义、程序分析、程序设计、编码、
测试和维护几个阶段，培养结构化方法的能力。测试和维护几个阶段，培养结构化方法的能力。
1414
问题定义
问题定义阶段是整个过程中占用时间最少的阶段，在这个步问题定义阶段是整个过程中占用时间最少的阶段，在这个步
骤中任务是明确要解决的问题是什么。在本课程中，要解决骤中任务是明确要解决的问题是什么。在本课程中，要解决
的问题可以由教师提供或由学生自行选题。在自行选题中，的问题可以由教师提供或由学生自行选题。在自行选题中，
学生可以动动脑筋，寻找身边有哪些事情可以用计算机解决，学生可以动动脑筋，寻找身边有哪些事情可以用计算机解决，
然后确定一个可行的题目，例如扫雷游戏、迷宫游戏等。有然后确定一个可行的题目，例如扫雷游戏、迷宫游戏等。有
时可以对该题目进行一个简要的说明。例如迷宫游戏的问题时可以对该题目进行一个简要的说明。例如迷宫游戏的问题
描述如下：描述如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷
宫。迷宫中设置很多墙壁，对前进方向形成了多处障碍，心宫。迷宫中设置很多墙壁，对前进方向形成了多处障碍，心
理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫
中寻找通路以到达出口。用计算机求解迷宫中的一条路径。中寻找通路以到达出口。用计算机求解迷宫中的一条路径。
1515
程序分析
这个阶段的任务仍然不是具体地解决问题，
而是理解问题和分析问题，主要是确定目标
系统必须具备哪些功能，以及目标系统可能
的输入和输出数据是什么。
我们在问题定义阶段得到的问题，有时仅仅
是一个抽象的题目，有时除了题目外还附一
段简要的说明。无论问题以何种形式出现，
都需要做进一步的分析，以获得系统必须实
现哪些功能。
1616
例如对于迷宫游戏，可以分析系统需要以下
几个功能：
1．迷宫的设置，为了系统的适用性，迷宫不
能固定，应该可以变化。
2．迷宫路径的寻找，该功能可以扩展，寻找
一条路径、全部路径、最短路径。
3．迷宫路径的输出。
到这里，程序分析的工作结束，接下来进入
下一个阶段：程序设计。
1717
程序设计
经过程序分析阶段的工作，程序必须经过程序分析阶段的工作，程序必须““做什么做什么””已已
经清楚了，现在是决定经清楚了，现在是决定““怎么做怎么做””的时候了。程序的时候了。程序
这个阶段的设计工作，应该对要解决的问题设计出这个阶段的设计工作，应该对要解决的问题设计出
具体的解决方案，得出对目标系统的精确描述，从具体的解决方案，得出对目标系统的精确描述，从
而在编码阶段可以把这个描述直接翻译成用而在编码阶段可以把这个描述直接翻译成用CC语言语言
书写的程序。程序设计将采用结构化程序设计方法，书写的程序。程序设计将采用结构化程序设计方法，
自顶向下逐步求精地设计出程序的实现自顶向下逐步求精地设计出程序的实现““蓝图蓝图””。。
下面，首先介绍结构化程序设计方法，然后列举描下面，首先介绍结构化程序设计方法，然后列举描
述算法的常用工具，接着以迷宫游戏为例，详细说述算法的常用工具，接着以迷宫游戏为例，详细说
明设计阶段的工作和结构化程序设计方法的应用。明设计阶段的工作和结构化程序设计方法的应用。
1818
结构化程序设计方法
结构程序设计的概念最早是由结构程序设计的概念最早是由提出来的，提出来的，
是为了解决程序可读性差的问题，创立一种新的程是为了解决程序可读性差的问题，创立一种新的程
序设计思想、方法和风格，以显著提高软件生产率序设计思想、方法和风格，以显著提高软件生产率
和质量。和质量。
在软件发展的早期，即在软件发展的早期，即2020世纪世纪6060年代末到年代末到7070年代初，年代初，
虽然科技在高速发展，程序规模越来越大，但是当虽然科技在高速发展，程序规模越来越大，但是当
时的编程技术却停留在手工作业的方式：设计各自时的编程技术却停留在手工作业的方式：设计各自
为政、滥用为政、滥用GOTOGOTO语句造成程序效率低下、可读性语句造成程序效率低下、可读性
差、无章可循、错误百出、调试困难。差、无章可循、错误百出、调试困难。
在这种局面下，在这种局面下，DijkstraDijkstra提出结构化程序设计的理论。提出结构化程序设计的理论。
经过多年的实践，结构化程序设计的理论和实践日经过多年的实践，结构化程序设计的理论和实践日
益完善，成为现代程序设计的主流方法之一。益完善，成为现代程序设计的主流方法之一。
1919
那么什么是结构化程序设计呢？
结构化程序设计是一种设计程序的技术，采用自顶结构化程序设计是一种设计程序的技术，采用自顶
向下逐步求精的设计方法和单入口单出口的顺序、向下逐步求精的设计方法和单入口单出口的顺序、
选择和循环三种基本控制结构。它提出的原则可归选择和循环三种基本控制结构。它提出的原则可归
纳为纳为3232字：字：““自顶向下，逐步细化；清晰第一，效自顶向下，逐步细化；清晰第一，效
率第二；书写规范，缩进格式；基本结构，组合而率第二；书写规范，缩进格式；基本结构，组合而
成。成。””
自顶向下，逐步求精方法符合人们解决复杂问题的自顶向下，逐步求精方法符合人们解决复杂问题的
普遍规律，可提高软件开发的成功率和生产率，这普遍规律，可提高软件开发的成功率和生产率，这
种方法采用先全局后局部、先整体后细节、先抽象种方法采用先全局后局部、先整体后细节、先抽象
后具体的逐步求精过程，开发出来的程序具有清晰后具体的逐步求精过程，开发出来的程序具有清晰
的层次结构，因此程序容易阅读和理解。的层次结构，因此程序容易阅读和理解。
2020
例如设计房屋就采用了这种方法，先进行整
体规划，然后确定建筑物的方案，在进行各
部分的设计，最后进行门窗、楼道等的细节
设计。
例：要求用筛选法求100 以内的素数（筛选
法为：从2到100中去掉2，3，…，9，10的
倍数，剩下的就是100以内的素数）。
2121
步骤一：
建立2到100的数组A[ ]，其中A[i] = i；_____1
建立2到10的素数表B[ ]，其中存放2到10以内
的素数； ___ _2
A[i]=i 是B[ ]中的任一数的倍数，则剔除A[i]；
__ _3
输出A[ ]中所没有被剔除的数； ______4
2222
步骤二：前述框架中每一个加工语句
都可进一步细化。
/* /* 建立建立22到到100100的数组的数组A[ ]A[ ]，其中，其中A[i] =i */ A[i] =i */ ______1______1
for (i=2 ; i < = 100 ;i++ ) for (i=2 ; i < = 100 ;i++ )
A[i] = i ; A[i] = i ;
/* /* 建立建立22到到1010的素数表的素数表B[ ]B[ ]，其中存放，其中存放22到到1010以内的素数以内的素数 */ __2 */ __2
B[1]=2 ; B[2]=3 ; B[3]=5 ; B[4]=7 ; B[1]=2 ; B[2]=3 ; B[3]=5 ; B[4]=7 ;
/* /* 若若A[i]=i A[i]=i 是是B[ ]B[ ]中的任一数的倍数，则剔除中的任一数的倍数，则剔除A[i] */ ___3A[i] */ ___3
for (j = 1 ; j < = 4 ; j++ ) for (j = 1 ; j < = 4 ; j++ )
检查检查A[ ]A[ ]所有的数能否被所有的数能否被B[j]B[j]整除，并将能被整除的数从整除，并将能被整除的数从A[ ]A[ ]中中
剔除；剔除；
/* /*输出输出A[ ]A[ ]中所有没有被剔除的数中所有没有被剔除的数 */ */ _____4_____4
for (i = 2 ; i < = 100 ; i++ ) for (i = 2 ; i < = 100 ; i++ )
若若A[i]A[i]没有被剔除，则输出之；没有被剔除，则输出之；
2323
步骤三：将，进一步细化形成
程序。
2424
常用设计工具
自然语言在语法和语义上具有多义性，常常
要依赖上下文才能把问题交代清楚，而且即
使可以描述，也需要大量的篇幅，非常繁琐。
所以必须用简洁的方法表达整体结构，约束
性强的方式表达算法。
设计工具可以对设计进行无歧义的描述，能
指明控制流程、处理流程以及其他方面的实
现细节。
下面介绍三种常用的图形方式的设计工具。
2525
层次图
用来描述软件的层次结构，图中的一个矩形
框代表一个模块，方框之间的连线表示调用
关系。层次图很适合在自顶向下设计软件的
过程中使用。
2626
2727
程序流程图
是历史最悠久使用最广泛的描述软件设计的方法。是历史最悠久使用最广泛的描述软件设计的方法。
它的主要优点是对控制流程的描述很直观，便于初它的主要优点是对控制流程的描述很直观，便于初
学者掌握。学者掌握。
但这种用箭头代表控制流的方法，容易使程序员不但这种用箭头代表控制流的方法，容易使程序员不
受任何约束，可以完全不顾结构化程序设计的精神，受任何约束，可以完全不顾结构化程序设计的精神，
随意转移控制。另外，程序流程图不易表示数据结随意转移控制。另外，程序流程图不易表示数据结
构。因此，程序流程图不是逐步求精的工具。构。因此，程序流程图不是逐步求精的工具。
下图是国家标准下图是国家标准GB1526-1989GB1526-1989程序流程图中常用的程序流程图中常用的
符号，与通用不同之处，在于取消了箭头。符号，与通用不同之处，在于取消了箭头。
2828
2929
盒图
是一种很好的支持结构化程序设计思想的图
形工具。
盒图上能明确表达功能域，不可能任意转移
控制，很容易确定局部和全局数据的作用域，
很容易表现嵌套关系，而且也可以表示模块
的层次结构。
所以坚持使用盒图作为设计工具，可以使程
序员逐步养成用结构化的方式思考问题和解
决问题的习惯。
3030
顺序结构
块1
块2
块3
块4
条件
T F
块1 块2
选择结构
Case I=1,2,3T
块1 块2
多分支选择结构
F
块3
块
当条件成立时
当型循环
块
直到条件成立时
直到型循环
3131
伪代码
图形工具表示设计比较直观，但画起来比较费劲，图形工具表示设计比较直观，但画起来比较费劲，
所以描述设计还可以使用伪代码这个常用的语言工所以描述设计还可以使用伪代码这个常用的语言工
具。伪代码是一种具。伪代码是一种““混合混合””语言，它使用一种语言语言，它使用一种语言
————通常是某种自然语言的词汇，同时却使用某种通常是某种自然语言的词汇，同时却使用某种
结构化程序设计的语法。这样，它具有严格的关键结构化程序设计的语法。这样，它具有严格的关键
字外部语法，而表示实际操作和条件的内部语法又字外部语法，而表示实际操作和条件的内部语法又
是灵活自由的，书写方便，也比较好懂。是灵活自由的，书写方便，也比较好懂。
““用筛选法求用筛选法求100 100 以内的素数以内的素数””的算法描述就是伪的算法描述就是伪
代码方式。代码方式。
3232
迷宫游戏的设计
现阶段的设计任务是自顶向下逐步求精，具
体要完成以下几点：
– 继续分析已有功能，直到精化出所有子功能，确继续分析已有功能，直到精化出所有子功能，确
定模块之间的接口。定模块之间的接口。
– 描述精化后每个模块的处理过程。描述精化后每个模块的处理过程。
– 确定主要的数据以及数据结构。确定主要的数据以及数据结构。
– 确定输入输出数据的内外部形式。确定输入输出数据的内外部形式。
– 进行界面的设计。进行界面的设计。
以下将展示迷宫游戏的设计。
3333
1）数据结构的设计
（（11）迷宫的表示）迷宫的表示
设迷宫为设迷宫为mm行行nn列，利用二维数组列，利用二维数组maze[m][n]maze[m][n]来表来表
示一个迷宫，其中入口点为（示一个迷宫，其中入口点为（11，，11），出口为），出口为
（（mm，，nn），），maze[i][j]=0maze[i][j]=0或或11，其中，其中00表示通路，表示通路，11
表示不通。当从某点试探时，有表示不通。当从某点试探时，有88个方向可以试探个方向可以试探
，而四个角点有，而四个角点有33个方向，其他边缘点有个方向，其他边缘点有55个方向，个方向，
为使问题简单化为使问题简单化,,在迷宫的四周加了一层，表示墙在迷宫的四周加了一层，表示墙
壁，这样每个点的试探方向为壁，这样每个点的试探方向为88。。
#define m 6 /*#define m 6 /*迷宫行数迷宫行数*/*/
#define n 8 /*#define n 8 /*迷宫列数迷宫列数*/*/
typedef structtypedef struct
{int x,y;}item; /* {int x,y;}item; /*坐标坐标*/*/
int mze[m+2][n+2]int mze[m+2][n+2]；；/*/*迷宫迷宫*/ */
3434
（2）试探方向的表示
在上述表示迷宫的情况下，每个点有在上述表示迷宫的情况下，每个点有88个方向可以试个方向可以试
探，设当前点的坐标为（探，设当前点的坐标为（xx，，yy），与其相邻的），与其相邻的88个个
点的坐标可根据与该点的相邻方位得到。为了方便点的坐标可根据与该点的相邻方位得到。为了方便
求出新点的坐标，将从正东开始沿顺时针进行的这求出新点的坐标，将从正东开始沿顺时针进行的这
88个方向的坐标增量放在一个结构数组个方向的坐标增量放在一个结构数组move[8]move[8]中，中，
其中其中xx表示横坐标增量，表示横坐标增量，yy表示纵坐标增量。表示纵坐标增量。
typedef structtypedef struct
{int x,y;}item; /* {int x,y;}item; /*坐标坐标*/*/
item move[8]={{0,1}, {1,1},{1,0},{1,-1},{0,-1}, {-1,-1},item move[8]={{0,1}, {1,1},{1,0},{1,-1},{0,-1}, {-1,-1},
{-1,0},{-1,1} };{-1,0},{-1,1} };
3535
（3）保存到达的每一点的位置及试
探方向的数据结构
利用回溯法，从入口处出发，按某一方向不断试探，利用回溯法，从入口处出发，按某一方向不断试探，
若能走通，则到达新点，否则试探另一未试探过的若能走通，则到达新点，否则试探另一未试探过的
方向。若所有的方向均没有通路，则沿原路返回前方向。若所有的方向均没有通路，则沿原路返回前
一点，换一个未试探过的通路继续试探，直到找到一点，换一个未试探过的通路继续试探，直到找到
出口，或所有的通路都试探过，未找到一条通路回出口，或所有的通路都试探过，未找到一条通路回
到出口点。在试探过程中，为保证在到达某一点无到出口点。在试探过程中，为保证在到达某一点无
路时，能正确返回前一点，需要用一个数据结构路时，能正确返回前一点，需要用一个数据结构
（栈）来保存到达的每一点的位置及试探方向。（栈）来保存到达的每一点的位置及试探方向。
当到达了某点无路可走，需从前一点的下一个方向当到达了某点无路可走，需从前一点的下一个方向
试探。因此，压入栈中的不仅是顺序到达的各点的试探。因此，压入栈中的不仅是顺序到达的各点的
坐标，而且还有从前一点到达本点的方向序号。坐标，而且还有从前一点到达本点的方向序号。
3636
#define MAXSIZE 20
typedef struct
{int x,y,d;
}datatype;
typedef struct
{datatype data[MAXSIZE];
int top;
}SeqStack;
3737
2）功能求精
在前面已经分析出系统的目标和主要功能，
但这仅仅是程序层次结构中最上层的部分，
划分的功能比较抽象，需要进一步的精化。
下面用层次图表示各部分的功能以及功能之
间的调用关系。
3838
3939
对每个功能还需要进一步说明完成的主要功
能、输入输出以及内部的数据结构和算法。
下面只针对主控模块和找路径模块进行详细
说明。
4040
主控模块main()：用来进行各个数据的初始
化，并进行功能的选择。主控模块的流程图
如下：
4141
n
y
开始
设置迷宫
找路径
输出路径
继续？
关闭游戏结束 4242
迷宫设置模块int setmaze(mazestruct
*maze)：用来设置迷宫以及出入口，其中出
入口在迷宫中的值必须为1，否则重新设置。
成功返回1，失败返回0。Maze为设置的迷宫。
（算法略）
4343
找路径int findpath(mazestruct *maze，
SeqStack *path)：用来选择路径，找到返
回1，否则返回0。找到的路径存储在path中。
算法的设计如下：
– 防止重复到达某点的考虑：为避免发生死循环，防止重复到达某点的考虑：为避免发生死循环，
当到达某点（当到达某点（ii，，jj）后，使）后，使maze[i][j]maze[i][j]置置-1-1，以便，以便
区分未到达过的顶点。算法结束前可恢复原迷区分未到达过的顶点。算法结束前可恢复原迷
宫。宫。
– 算法描述算法描述
4444
①① 栈初始化；栈初始化；
②②将入口点坐标及初始试探方向（设为将入口点坐标及初始试探方向（设为-1-1）入栈）入栈,,并将入口点并将入口点
设置为已走过；设置为已走过；
③③设置未找到设置未找到found=0found=0；；
④④whilewhile（未找到（未找到&&&&栈非空）栈非空）
{*{*从栈顶元素位置出发寻找下一个可以走的方位；从栈顶元素位置出发寻找下一个可以走的方位；
if( if(找到方位找到方位))
{ {修改栈顶元素的方位值修改栈顶元素的方位值;;
计算新点计算新点,,并设置为已走过并设置为已走过;;
将新点位置及初始试探方位值进栈将新点位置及初始试探方位值进栈;;
if(if(新点是结束点新点是结束点) ) 结束结束;;
}}
else //else //没找到可走的方位没找到可走的方位,,说明从该点出发已无路可走说明从该点出发已无路可走
出栈出栈;;
}}
⑤⑤if(if(找到找到))打印路径打印路径;else ;else 打印打印””该迷宫无路径该迷宫无路径”;”; 4545
路径输出void printpath(SeqStack *path)：
将找到的路径输出。（算法略）
4646
3）界面设计
软件界面设计应该以使用软件的人为中心，
尽量从使用软件的角度出发设计界面。
迷宫游戏的界面比较简单，一开始显示系统
的功能、设计者、系统使用说明。然后询问
“是否开始游戏？”，回答“y”则开始。在
进行迷宫设置的界面中要提供帮助说明。
4747
编码
编码就是用高等语言表示设计阶段产生的算法。在编码就是用高等语言表示设计阶段产生的算法。在
编码阶段，可以使我们再次体会到使用结构化程序编码阶段，可以使我们再次体会到使用结构化程序
设计技术的主要优点：设计技术的主要优点：
–– 用先全局后局部、先整体后细节、先抽象后具体的逐步用先全局后局部、先整体后细节、先抽象后具体的逐步
求精过程开发出的程序有清晰的层次结构，容易阅读和求精过程开发出的程序有清晰的层次结构，容易阅读和
理解；理解；
–– 不使用不使用GOTOGOTO语句仅使用单入口单出口的控制结构，使得语句仅使用单入口单出口的控制结构，使得
程序的静态结构和它的动态执行情况比较一致，容易保程序的静态结构和它的动态执行情况比较一致，容易保
证程序开发时的正确性和易纠错性；证程序开发时的正确性和易纠错性；
–– 控制结构有确定的逻辑模式，编写程序代码只限于使用控制结构有确定的逻辑模式，编写程序代码只限于使用
很少的几种直截了当的方式，使程序容易测试；很少的几种直截了当的方式，使程序容易测试；
–– 程序清晰和模块化使得在修改和重新设计一个软件时可程序清晰和模块化使得在修改和重新设计一个软件时可
以重用的代码量最大等。以重用的代码量最大等。
4848
因此，结构化程序设计技术能够保证我们得
到结构化程序。这种程序便于编写、阅读、
修改和维护，减少了程序出错的机会，提高
了程序的可靠性，保证了程序的质量。
下面讲述在程序编码时应该注意的几个问题:
4949
全局变量
全局变量的作用增加了函数间数据联系的渠道。但是全局变量使函数的全局变量的作用增加了函数间数据联系的渠道。但是全局变量使函数的
通用性降低了，因为函数在执行时要依赖于其所在的全局变量。如果将通用性降低了，因为函数在执行时要依赖于其所在的全局变量。如果将
一个函数移到另一个文件中，还要将有关的全局变量以及其值一起移过一个函数移到另一个文件中，还要将有关的全局变量以及其值一起移过
去。但若该全局变量与其它文件的全局变量同名时，就会出现问题，降去。但若该全局变量与其它文件的全局变量同名时，就会出现问题，降
低了程序的可靠性和通用性。在程序设计中，在划分模块时要求模块的低了程序的可靠性和通用性。在程序设计中，在划分模块时要求模块的
““内聚性内聚性””强，与其他模块的强，与其他模块的““耦合性耦合性””弱。即模块的功能单一，与其弱。即模块的功能单一，与其
他模块的相互影响要尽量少，而用全局变量是不符合这个原则的。他模块的相互影响要尽量少，而用全局变量是不符合这个原则的。一般一般
要求把要求把cc程序中的函数作成一个封闭体，除了可以通过程序中的函数作成一个封闭体，除了可以通过““实参实参--形参形参””与与
外界发生联系外，没有其他渠道。这样的程序移植性好，可读性强外界发生联系外，没有其他渠道。这样的程序移植性好，可读性强。。
另外使用全局变量过多，会降低程序的清晰性，人们往往难以清楚地判另外使用全局变量过多，会降低程序的清晰性，人们往往难以清楚地判
断出每个瞬间每个全局变量的值。在各个函数执行时都可能改变全局变断出每个瞬间每个全局变量的值。在各个函数执行时都可能改变全局变
量的值，程序容易出错。量的值，程序容易出错。
对于大型程序，模块多，常常由不同的人来完成不同的模块，如果全局对于大型程序，模块多，常常由不同的人来完成不同的模块，如果全局
变量随意使用，更容易出现问题，造成程序的混乱。因此，更应该限制变量随意使用，更容易出现问题，造成程序的混乱。因此，更应该限制
使用全局变量。使用全局变量。
5050
风格
结构化程序的一大特征就是清晰可读。风格的作用结构化程序的一大特征就是清晰可读。风格的作用
主要就是使代码容易读，无论是对程序员本人，还主要就是使代码容易读，无论是对程序员本人，还
是对其他人，代码应该是清晰的和简单的，具有直是对其他人，代码应该是清晰的和简单的，具有直
截了当的逻辑、自然的表达式、通用的语言使用方截了当的逻辑、自然的表达式、通用的语言使用方
式、有意义的名字和有帮助作用的注释等。一致性式、有意义的名字和有帮助作用的注释等。一致性
是非常重要的，如果大家都坚持同样的风格，代码是非常重要的，如果大家都坚持同样的风格，代码
就容易读懂。就容易读懂。
下面将对比一些小程序设计例子来说明与风格有关下面将对比一些小程序设计例子来说明与风格有关
的规则，其中用灰色标记的代码段代表了不好风格的规则，其中用灰色标记的代码段代表了不好风格
的代码段。的代码段。
5151
（1）名字
一个名字应该是非形式的、简练的、易记忆的，若可能的话，一个名字应该是非形式的、简练的、易记忆的，若可能的话，
最好是能够拼读的。一个变量等作用域越大，它的名字所携最好是能够拼读的。一个变量等作用域越大，它的名字所携
带的信息就应该越多。全局变量使用具有说明性的语言，局带的信息就应该越多。全局变量使用具有说明性的语言，局
部变量使用短名字。全局变量可出现在整个程序的任何地方，部变量使用短名字。全局变量可出现在整个程序的任何地方，
因此其名字应具有足够的说明性，以便使读者能够记住它们因此其名字应具有足够的说明性，以便使读者能够记住它们
是干什么的。给每个全局变量声明附一个简短的注释也是非是干什么的。给每个全局变量声明附一个简短的注释也是非
常有帮助的。按常规方式使用的局部变量可采用极短的名字，常有帮助的。按常规方式使用的局部变量可采用极短的名字，
如用如用ii、、jj作为循环变量，作为循环变量，pp、、qq作为指针，作为指针，ss、、tt表示字符串等。表示字符串等。
现实中存在许多命名约定或者本地习惯。常见的如：指针采现实中存在许多命名约定或者本地习惯。常见的如：指针采
用以用以ptrptr结尾的变量名；全局变量用大写开头变量名；常量用结尾的变量名；全局变量用大写开头变量名；常量用
完全由大写拼写的变量名等。命名约定能使代码更易理解。完全由大写拼写的变量名等。命名约定能使代码更易理解。
5252
（2）表达式和语句
同样，我们也应该以尽可能一目了然的形式
写好表达式和语句。
5353
采用缩进程序结构，是使程序呈现出
结构清晰的最省力的方法。比较：
for(n++;n<100;field[n++]for(n++;n<100;field[n++]
=’\0’)=’\0’)；；
*i=’\0’;return(‘\n*i=’\0’;return(‘\n
’);’);
或或
for(n++;n<100;field[n++]for(n++;n<100;field[n++]
=’\0’)=’\0’)
；；
*i=’\0’;*i=’\0’;
return(‘\n’); return(‘\n’);
for(n++;n < 100;n++) for(n++;n < 100;n++)
field[n]=’\0’ field[n]=’\0’；；
*i=’\0’;*i=’\0’;
return(‘\n’); return(‘\n’);
5454
使用表达式的自然形式。否定运算的
条件表达式比较难理解，比较：
if(!(block_id<actblks)||!(blif(!(block_id<actblks)||!(bl
ock_id>=unblocks))… ock_id>=unblocks))…
if((block_id>=actblks)||(blif((block_id>=actblks)||(bl
ock_id<unblocks))… ock_id<unblocks))…
5555
分解复杂的表达式。C有很丰富的表达式语法
结构和很丰富的运算符，因此应该避免将一大
堆东西塞进一个结构中。比较：
*xp+=(x=2*k < (n-m)?c[k+1]:d*xp+=(x=2*k < (n-m)?c[k+1]:d
[k--])); [k--]));
if(2*k < (n-m))if(2*k < (n-m))
x=c[k+1]; x=c[k+1];
elseelse
x=d[k--]; x=d[k--];
*xp += x; *xp += x;
5656
当心副作用。像++这一类运算符具有
副作用，它们除了返回一个值外，还
将隐含地改变变量的值。这类表达式
有时用起来很方便，但有时也会成为
问题，因为变量的取值操作和更新操
作可能不是同时发生。
5757
（3）宏
有些有些cc程序员喜欢把很短的而执行又频繁的计算写成程序员喜欢把很短的而执行又频繁的计算写成
宏，而不是定义为函数。人们这样做最根本的理由宏，而不是定义为函数。人们这样做最根本的理由
就是执行效率：宏可以避免函数调用的开销。就是执行效率：宏可以避免函数调用的开销。
实际上，编译程序发展到今天，宏的缺点远远超过实际上，编译程序发展到今天，宏的缺点远远超过
它能带来的好处，它带来的麻烦比解决的问题更多。它能带来的好处，它带来的麻烦比解决的问题更多。
宏最常见的一个严重问题是：若一个参数在定义中宏最常见的一个严重问题是：若一个参数在定义中
出现多次，它就可能被多次求值。若调用时的实际出现多次，它就可能被多次求值。若调用时的实际
参数带有副作用，结果就会产生一个难以琢磨的错参数带有副作用，结果就会产生一个难以琢磨的错
误。误。
如下面宏的意图是实现一种字符测试：如下面宏的意图是实现一种字符测试：
5858
#define isupper(c) ((c)>=’A’&&(c)<=’Z’)
但如果它在下面的上下文中使用：
while(isupper(ch=getchar( )))
…
那么，每当遇到一个大于等于A的字符，程序
就会丢掉它，而下一个字符将被读入并去与Z
做比较。因此，上面的实现是错误。
5959
除了这个问题外，由于宏是通过文本替换方式实现除了这个问题外，由于宏是通过文本替换方式实现
的，如果忘记给宏的体和参数加上括号，将产生错的，如果忘记给宏的体和参数加上括号，将产生错
误。如：误。如：
#define square(x) (x)*(x)#define square(x) (x)*(x)
……
1/square(x)1/square(x)
正确的宏应该是：正确的宏应该是：
#define square(x) ((x)*(x))#define square(x) ((x)*(x))
所以建议：除了定义符号常量外，最好避免使用宏。所以建议：除了定义符号常量外，最好避免使用宏。
6060
（4）注释
注释是帮助读者阅读程序的一种手段，它们澄清情况，不是注释是帮助读者阅读程序的一种手段，它们澄清情况，不是
添乱。注释要注意：添乱。注释要注意：不要琐谈明显的东西不要琐谈明显的东西。注释应该提供那。注释应该提供那
些不能一下子从代码中看到的东西，或者把那些散布在许到些不能一下子从代码中看到的东西，或者把那些散布在许到
代码里的信息收集到一起，否则没有价值。代码里的信息收集到一起，否则没有价值。要给函数和全局要给函数和全局
变量加注释变量加注释。对于函数、全局变量、常数定义、结构的成员。对于函数、全局变量、常数定义、结构的成员
等，以及任何其他加上简短说明就能够帮助理解的内容，都等，以及任何其他加上简短说明就能够帮助理解的内容，都
应该为之提供注释。应该为之提供注释。注释不要与代码矛盾注释不要与代码矛盾。这往往是修改代。这往往是修改代
码后没有及时对相关注释进行更改造成的。但是如果注释的码后没有及时对相关注释进行更改造成的。但是如果注释的
长度超过代码本身，可能就说明这个代码应该修改了。所以，长度超过代码本身，可能就说明这个代码应该修改了。所以，
不要注释差的代码，而要重写它。我们应该尽可能地把代码不要注释差的代码，而要重写它。我们应该尽可能地把代码
写得容易理解，在这方面做得越好，需要写的注释就越少。写得容易理解，在这方面做得越好，需要写的注释就越少。
6161
以上从几个方面谈论了程序设计风格，这里
最关键的结论是：
好风格应该成为一种习惯。
如果在开始写代码时就关心风格问题，花时
间去审视和改进它，就会逐渐养成一种好的
编程习惯。一旦这种习惯变成自动的东西，
潜意识就会起作用，写出的代码会更好。
6262
测试与调试
大量的资料统计表明，软件开发组织将大量的资料统计表明，软件开发组织将30%~40%30%~40%的工作量的工作量
花在测试上。而那些高可靠性、高安全性软件的测试所花的花在测试上。而那些高可靠性、高安全性软件的测试所花的
时间更是其它开发步骤总和的时间更是其它开发步骤总和的33到到55倍。测试的目的是以最小倍。测试的目的是以最小
的代价（耗费最少时间和最少工作量）发现尽可能多的不同的代价（耗费最少时间和最少工作量）发现尽可能多的不同
类型的错误。类型的错误。
真正实施测试之前要制定测试方案，测试方案包括预定要测真正实施测试之前要制定测试方案，测试方案包括预定要测
试的功能，应该输入的测试数据和预期的结果。试的功能，应该输入的测试数据和预期的结果。
测试和调试常常被说成是一个回事，实际上是测试阶段的不测试和调试常常被说成是一个回事，实际上是测试阶段的不
同任务。调试即排错，是在已经知道程序有问题时要做的事同任务。调试即排错，是在已经知道程序有问题时要做的事
情。测试则是在认为程序能工作的情况下，为发现问题而进情。测试则是在认为程序能工作的情况下，为发现问题而进
行的一整套确定的系统化的实验。行的一整套确定的系统化的实验。
6363
运行与维护
程序的运行与维护是整个程序开发流程的最
后一步。编写程序的目的就是为了应用，在
程序运行的早期，用户可能会发现在测试阶
段没有发现的错误，需要修改。而随着时间
的推移，原有程序可能已满足不了需要，这
是就需要对程序进行修改甚至升级。因此，
维护是一项长期而又重要的工作。
6464
实验报告格式
6565
