《程序设计课程设计》指导书

《《程序设计课程设计》指导书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序设计课程设计指导书计算机科学与技术学院软件工程系2011年6月27日28一．课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下七项：1．需求分析简要说明程序设计的任务，程序要做什么。明确规定以下内容：（1）输入的形式和输入值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2．概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。3．详细设计实现概要设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和

2、其他模块也写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。4．测试结果列出测试结果，包括输入和输出。测试数据应该完整、严格。5．测试分析内容包括：（1）测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析；（2）算法的时空分析和改进设想；（3）经验和体会。6．使用说明说明如何使用该程序，列出每一步的操作步骤。7．附录列出程序文件名的清单以及带注释的源程序。二．迷宫问题示例【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没

3、有通路的结论。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标,d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）……【测试数据】迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。28001000100010001000001101011100100001000001000101011110011100010111000000【实现提示】计算机解迷宫通常用的是“穷举

4、求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。【选作内容】（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。课程设计报告示例：迷宫问题题目：编制一个求解迷宫通路的程序。一．需求分析（1）以二维数组MAZE[M+2][

5、N+2]表示迷宫，其中：MAZE[0][J]和MAZE[M+1][J]（0≤J≤N+1）及MAZE[I][0]和MAZE[I][N+1]（0≤I≤M+1）为添加的一圈障碍。数组中以元素值为0表示通路，1表示障碍。限定迷宫的大小M，N≤10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数M和列数N；从第2行至第M+1行（每行N个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“

6、@”表示“死胡同”，即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。（6）测试数据见原题，当入口位置为（1，1），出口位置为（9，8）时，输出数据应为：**#@@@#*#@@@#**@@###*####@***#***@28#***#*#####*####*###**（7）程序执行的命令为：1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二．概要设计1．设定栈的抽象数据类型定义为：ADTstack{数据对象：D={ai

7、ai∈charset,i=1,2,……,n

8、,n≥0}数据关系：R1={

9、ai-1,ai∈D,i=2……,n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(&S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(&S)初始条件：栈