《《程序设计课程设计》指导书》由会员分享，可在线阅读，更多相关《《程序设计课程设计》指导书（28页珍藏版）》请在金锄头文库上搜索。
1、1程序程序设计课设计课程程设计设计指指导书导书计算机科学与技术学院软件工程系计算机科学与技术学院软件工程系20112011 年年 6 6 月月 2727 日日2一课程设计报告要求一课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出 题目，内容包括以下七项： 1 需求分析需求分析 简要说明程序设计的任务，程序要做什么。明确规定以下内容： （1）输入的形式和输入值的范围； （2）输出的形式； （3）程序所能达到的功能； （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2 概要设计概要设计 说明本程序中用到的所有抽象数据类型的定义
2、、主程序的流程以及各程序模块之间的层次 （调用）关系。 3 详细设计详细设计 实现概要设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也 写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计 语言程序） ；画出函数的调用关系图。 4 测试结果测试结果 列出测试结果，包括输入和输出。测试数据应该完整、严格。 5 测试分析测试分析 内容包括： （1）测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析； （2）算法的时空分析和改进设想； （3）经验和体会。 6 使用说明使用说明 说明如何使用该程序，列出每一步的操作步骤。 7 附录附录
3、列出程序文件名的清单以及带注释的源程序。二迷宫问题示例二迷宫问题示例【问题描述问题描述】 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任 意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通 路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标,d 表示走到下 一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为： （1，1，1） ， （1，2，2） ， （2，2，2） ， （3，2，3） ， （3，1，2） 【
4、测试数据测试数据】 迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。3【实现提示实现提示】 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若 能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通 路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1） ，出口点的下标为（m,n） 。 为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、 北四个方向可通。 【选作内容选作内容】 （1 1）编写递归形式的算法，
5、求得迷宫中所有可能的通路； （2 2）以方阵形式输出迷宫及其通路。课程设计报告示例：迷宫问题课程设计报告示例：迷宫问题题目：编制一个求解迷宫通路的程序。 一需求分析一需求分析 （1）以二维数组 MAZEM+2N+2表示迷宫，其中：MAZE0J和 MAZEM+1J （0JN+1）及 MAZEI0和 MAZEIN+1（0IM+1）为添加的一圈障碍。数组中以元素 值为 0 表示通路，1 表示障碍。限定迷宫的大小 M，N10。 （2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数 M 和列数 N；从 第 2 行至第 M+1 行（每行 N 个数）为迷宫值，同一行中的两个数字之间用空白字符
6、相隔。 （3）迷宫的入口位置和出口位置可由用户随时设定。 （4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即 终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“”表示“死胡同” ， 即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应 信息。 （5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求 得全部路径。 （6）测试数据见原题，当入口位置为（1，1） ，出口位置为（9，8）时，输出数据应为：*#*#*#*#*#*001000100010001000001101011100100001
7、0000010001010111100111000101110000004#*#*#*#*#*（7）程序执行的命令为： 1）创建迷宫； 2）求解迷宫； 3）输出迷宫的解。 二概要设计二概要设计 1设定栈的抽象数据类型定义为：ADTADT stack 数据对象：D=ai|aicharset,i=1,2,n,n0 数据关系：R1=|ai-1,aiD,i=2,n 基本操作：InitStack( 3.本程序包含三个模块 1）主程序模块void main( ) 初始化do 接受命令； 处理命令； while(命令！=“退出”)； 2）栈模块-实现栈抽象数据类型 3）迷宫模块-实现迷宫抽象数据类型 各模块
8、之间的调用关系如下： 主程序模块迷宫模块栈模块 4求解迷宫中一条通路的伪码算法： 设定当前位置的初值为入口位置；do 若当前位置可通， 则 将当前位置插入栈顶； /纳入路径若该位置是出口位置，则结束； /求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；6否则 若栈不空且栈位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置； /后退一步，从路径中删去该通道块，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空； while(栈不空)； 栈空说明没有路径存在 三详细设计三详
9、细设计 1坐标位置类型typedef struct int r,c; /迷宫中行、列的范围PosType; 2迷宫类型typedef structint m,n;char arrRANGERANGE; /各位置取值 ,#,或*MazeType; void InitMaze(MazeType /当前位置在路径上的“序号” PosType seat; /当前的坐标位置 directiveType di; /往下一坐标位置的方向 ElemType; /栈的元素类型typedef struct NodeType ElemType data; NodeType *next; NodeType,*Link
10、Type; /结点类型，指针类型typedef struct LinkType top; int size; Stack; /栈类型 栈的基本操作设置如下：7void InitStack(Stack 否则返回 FALSEStatus GetTop(Stack s,ElemType e) /若栈 S 不空,则以 e 带回栈顶元素并返回 TRUE,否则返回 FALSE;Status Push(Stack s.top=p; s.size+; return TRUE; else return FALSE; Status Pop(Stack else p=S.top; S.top=S.top-next;
11、 e=p-date; S.size-; return TRUE; 4.求迷宫路径的伪码算法：Status MazePath(MazeType maze,PosType start,PosType end) /若迷宫中存在从入口 start 到出口 end 的通道,则求得一条存入在栈中 /（从栈底到栈顶为从入口到出口的路径） ，并返回 TRUE；否则返回 FALSE8InitStack(S); curpos=start; /设定“当前位置”为“入口位置” curstep=1; found=FALSE; /探索第一步do if (Pass(maze,curpos)/当前位置可以通过，即是未曾走到过
12、的通道块留下足迹FootPrint(maze,curpos); e=(curstep,curpos,1); Push(S,e); /加入路径 if(Same(curpos,end) found=TRUE; /到达终点（出口）elsecurpos=NextPos(curpos,1); /下一位置是当前位置的东邻curstep+; /探索下一步/else /if else /当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4 Pop(S,e);curstep-; /留下不能通过的标记，并退回一步/while if(e.di0。采用怎样的装包方法才会使装入背
13、 包物品的总效益最大 。 【问题分析问题分析】 首先建立该问题的数学模型：极大化： niPiXi1(1)约束条件： niMWiXi1 (2)3(, 2 , 1, 10niXiL15其中，(1)式是目标函数，(2)和(3)是约束条件。满足约束条件的任一集合(x1xn)是一个可行 解(即能装下)，使目标函数取最大值的可行解是最优解。 例 1. 考虑下列背包问题：n=3，M=20，(p1，p2，p3)(25，24，15)，(w1,w2,w3) (18，15，10)。其中的四个可行解是(xl，x2，x3) 总容量 总效益 (1) (12，13，14) 16.5 24.25 (2) (1，215，0)
14、20 28.2 (3) (0，23，1) 20 31 (4) (0，1，12) 20 31.5 每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装 人次序按 piwi 比值的非增次序来考虑。在这种策略下的量度是已装物品的累计效益值与所用容 量之比。其量度标准是每次装入要使累计效益值与所用容量的比值有最多的增加或最少的减小(第 二次和以后的装入可能使此比值减小)。将此贪心策略应用于例 1 的数据，得到解。如果将物体 事先按 piwi 的非增次序分好类，则过程 greedyknaPsack 就得出这一策略下背包问题的解。 【算法描述算法描述】procedure greedy-knaPsack(P，w，m，x，n) real P(1:n)，w(1：n)，x(1：n)，m，cu；/M 是背包的容量大小，而 x(1：n)是解向量 integer i，n； Sort(p,w); /按 P(i)wiP（i+1)w(i+1)排序的 n 件物品的效益值和重量,并且形成新的 P(1：n)和 w(1；n)。 xcu then exit endif xi #include #include “date.h“ #include “person.h“ #include “s
