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

程序设计课程设计指导书计算机科学与技术学院软件工程系2011年6月27日一课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下七项：1 需求分析简要说明程序设计的任务，程序要做什么。明确规定以下内容：（1） 输入的形式和输入值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2 概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。3 详细设计实现概要设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。4 测试结果列出测试结果，包括输入和输出。测试数据应该完整、严格。5 测试分析内容包括：（1） 测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析；（2） 算法的时空分析和改进设想；（3） 经验和体会。6 使用说明说明如何使用该程序，列出每一步的操作步骤。7 附录列出程序文件名的清单以及带注释的源程序。二迷宫问题示例【问题描述】以一个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）【测试数据】迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。001000100010001000001101011100100001000001000101011110011100010111000000【实现提示】计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。【选作内容】（1） 编写递归形式的算法，求得迷宫中所有可能的通路；（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个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“”表示“死胡同”，即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。（6）测试数据见原题，当入口位置为（1，1），出口位置为（9，8）时，输出数据应为： *#*#*#*#*#*#*#*#*#*#* （7）程序执行的命令为：1）创建迷宫； 2）求解迷宫； 3）输出迷宫的解。二概要设计1设定栈的抽象数据类型定义为：ADT stack数据对象：D=ai|aicharset,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(&S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit( )初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit( ).ADT stack2设定迷宫的抽象数据类型为：ADT maze数据对象：D=ai,j|ai,j 、#、*，0im+1,0jn+1,m,n10数据关系：R=ROW，COLROW=|ai-1,j，ai,jD,i=1,，m+1,j=0,，n+1COL=|ai,j-1,ai,jD,i=0,，m+1,j=1,，n+1基本操作：InitMaze(&M,a,row,col)初始条件：二维数组arow+2col+2已存在，其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符#表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以字符“*”表示路径上的位置，字符“”表示“死胡同”；否则迷宫的状态不变。PrintMaze(M)初始条件：迷宫M已存在。操作结果：以字符形式输出迷宫。ADT maze;3.本程序包含三个模块1）主程序模块void main( ) 初始化do接受命令；处理命令；while(命令！=“退出”)；2）栈模块-实现栈抽象数据类型3）迷宫模块-实现迷宫抽象数据类型各模块之间的调用关系如下：主程序模块迷宫模块栈模块4求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do若当前位置可通，则 将当前位置插入栈顶； /纳入路径 若该位置是出口位置，则结束； /求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置；否则若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置； /后退一步，从路径中删去该通道块， 若栈不空，则重新测试新的栈顶位置， 直到找到一个可通的相邻块或出栈至栈空；while(栈不空)；栈空说明没有路径存在三详细设计1坐标位置类型typedef structint r,c; /迷宫中行、列的范围PosType;2迷宫类型typedef struct int m,n; char arrRANGERANGE; /各位置取值 ,#,或*MazeType;void InitMaze(MazeType &maze,int a,int row,int col)/按照用户输入的row行和col列的二维数组（元素值为0或1）/设置迷宫的初值，包括加上边缘一圈的值bool MazePath(MazeType &maze,PosType start,PosType end)/求解迷宫maze中，从入口start到出口end的一条路径/若存在，则返回TRUE；否则返回FALSEvoid PrintMaze(MazeType maze)/将迷宫以字符型方阵的形式输出到标准输出文件上3栈类型typedef structint step; /当前位置在路径上的“序号”PosType seat; /当前的坐标位置directiveType di; /往下一坐标位置的方向ElemType; /栈的元素类型typedef struct NodeTypeElemType data;NodeType *next;NodeType,*LinkType; /结点类型，指针类型typedef structLinkType top;int size;Stack; /栈类型栈的基本操作设置如下：void InitStack(Stack &S)/初始化，设S为空栈（S.top=NULL）void DestroyStack(stack &S)/销毁栈S，并释放所占空间void ClearStack(Stack &S)/将S清为空栈int stackLength(Stack S)/返回栈S的长度S.sizeStatus StackEmpty(Stack S)/若S为空栈（S.top=NULL）,则返回TRUE;否则返回FALSEStatus GetTop(Stack s,ElemType e)/若栈S不空,则以e带回栈顶元素并返回TRUE,否则返回FALSE;Status Push(Stack &S,ElemType e) /若分配空间成功,则在S的栈顶插入新的栈顶元素e,并返回TRUE,/否则栈不变,并返回FALSEStatus Pop(Stack &S,ElemType &e)/若栈不空,则删除S的栈顶元素并以e带回其值，且返回TRUE /否则返回FALSEvoid StackTraverse(Stack s,Status(*visit)(ElemType e)/从栈底到栈顶依次对S中的每个结点调用函数visit其中部分操作的算法：Status Push(Stack &S,ElemType e)/若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；/否则栈不变，并返回FALSEif (MakeNode(p,e)p-next=s.top; s.top=p;s.size+; return TRUE;else return FALSE;Status Pop(Stack &S,ElemType &e)/若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，/否则返回FALSE，且e无意义if(StackEmpty(S) return FALSE;elsep=S.top; S.top=S.top-next;e=p-date; S.size-; return TRUE; 4.求迷宫路径的伪码算法：Status MazePath(MazeType maze,PosType start,PosType end)/若迷宫中存在从入口start到出口end的通道,则求得一条存入在栈中/（从栈底到栈顶为从入口到出口的路径），并返回TRUE；否则返回FALSEInitStack(S); curpos=start; /设定“当前位置”为“入口位置”curstep=1; found=FALSE; /探索第一步doif (Pass(maze,curpos) /当前位置可以通过，即是未曾走到过的通道块留下足迹FootPrint(maze,curpos); e=(curstep,curpos,1);Push(S,e); /加入路径if(Same(curpos,end) found=TRUE; /到达终点（出口）else curpos=NextPos(curpos,1); /下一位置是当前位置的东邻 curstep+; /探索下一步 /else/ifelse /当前位置不能通过if(!StackEmpty(S) Pop(S,e); while(e.di=4&!StackEmpty(S)MarkPrint(maze,e,seat); Pop(S,e); curstep-; /留下不能通过的标记，并退回一步/whileif(e.di0。采用怎样的装包方法才会使装入背包物品的总效益最大 。【问题分析】首先建立该问题的数学模型：极大化： (1)约束条件： (2) 其中，(1)式是目标函数，(2)和(3)是约束条件。满足约束条件的任一集合(x1xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。例1. 考虑下列背包问题：n=3，M=20，(p1，p2，p3)(25，24，15)，(w1,w2,w3)(18，15，10)。其中的四个可行解是 (xl，x2，x3) 总容量 总效益v (1) (12，13，14) 16.5 24.25v (2) (1，215，0) 20 28.2v (3) (0，23，1) 20 31v (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)。x- 0 /将解向量初始化为零 cum ; /cu是背包剩余容量 for icu then exit endifxi - 1; cu - cu-w(i);repeatif in then x（i）cuw(i);endifend greedy-knaPsack【测试数据】测试数据自定，要求物品的个数n，背包总容量M和每种物品的重量值及效益值。在程序运行过程中由用户从键盘输入。【实现提示】 采用静态数组存储。6学生管理系统【问题描述】大学里有各种类型的学生，校方需要对这些学生的信息进行计算机管理。所开发的软件应包括各类学生的添加、修改、删除和查找等功能。考虑到软件的可重用性、可扩展性和可维护性，校方决定采用面向对象的程序设计方法来开发系统。学生信息需要以文件方式保存到计算机硬盘中。另外，系统的用户界面应该尽可能友好，方便用户使用。【基本要求】(1) 使用C+语言开发，充分利用面向对象程序设计的类、对象、继承、封装和多态性等概念来设计和实现该管理系统。(2) 设计一个Person（人员）类，考虑到通用性，只抽象出所有类型人员都具有的属性：name（姓名）, id（身份证号），gender（性别），birthday（出生日期）等等。其中“出生日期”为内嵌子对象，是一个Date（日期）类型，Date类具有属性: year(年)，month（月），day（日）。用成员函数实现对人员信息的录入和显示等必要功能操作。(3) 从Person类派生出Student（学生）类，添加属性： studentNo（学号），schoolName（学校），classIn (班级)。从Person类派生出Teacher（教师）类，添加属性：teacherNo（教师编号），schoolName（学校），department（部门）。(4) 从Student类中派生出UnderGraduate（本科生）类，添加属性：major（专业）。从Student类中派生出Graduate（研究生）类，添加属性：direction（研究方向），adviserName（导师姓名）。(5) 从Graduate类和Teacher类派生出T（助教博士生）类。(6) 写程序测试上述各类，看能否正常运行。(7) 构建必要的辅助类，实现对本科生、研究生和助教博士生的添加、修改、删除、查询管理。(8) 根据需要定义类的构造函数、析构函数、拷贝构造函数、成员函数。必要时重载函数。(9) 要求将Person类设置为虚基类，以消除其派生类成员访问的二义性问题（注意在虚基类各级派生类的构造函数实现时调用虚基类的构造函数）。(10) 要求在Person类中定义虚函数displayDetails（），用于显示当前对象的信息；同时定义虚函数inputData( )，用于从键盘获取当前对象的信息。Person类所有派生类也要定义同名虚函数，使程序可以实现动态多态性。(11) 用菜单方式设计主控模块程序。(12) 对程序源代码要给出各部分的详细注释，这也是该题目的考核重点之一。(13) 用UML语言描述系统用到的类及其关系。【测试数据】输入多个本科生、研究生和助教博士生的数据。 【实现提示】程序框架:/*Copyright (C), 2010, TyutFile name: main.cppAuthor: gaobaolu Version: 1.0 Date: 2010.6.28Description: 应用程序主函数 */#include #include #include date.h#include person.h#include student.h#include teacher.h#include undergraduate.h#include graduate.h#include ta.h#include undergraduateManager.husing namespace std;int main(int argc, char *argv) int choiceN;UndergraduateManager unMan; cout*endl; cout*|*| |*|*endl; cout*|*| 欢迎您使用学生管理系统 |*|*endl; cout*|*| |*|*endl; cout*endl; do cout endl; cout n tt 1:本科生管理 ; cout n tt 2:研究生管理 ; cout n tt 3.助教博士生管理 ; cout n tt 0:离开 ; cout endl; cout endl; cout 请选择： choiceN; switch(choiceN) case 1: unMan.dataManage(); break; case 2: / break; case 3: / break; default: break; while(choiceN!=0); cout *endl; cout*|*| 感谢使用学生管理系统 |*|*endl; cout *aendl;/*Copyright (C), 2010, TyutFile name: undergraduateManager.hAuthor: gaobaolu Version: 1.0 Date: 2010.6.28Description: 本科生管理类 */#ifndef UNDERGRADUATE_MANAGER_H#define UNDERGRADUATE_MANAGER_H#include #include #include #include undergraduate.husing namespace std;/* Define a Class : UndergraduateManager 本科生管理类*/class UndergraduateManager private: int top; /记录指针 Undergraduate undergraduates100; /本科生记录 public: UndergraduateManager();/构造函数,将Undergraduate.txt读到undergraduates中 int queryByNo(string sno);/按本科生号查找 /找到：返回数组下标/没找到：返回-1 void clearStudent(); /删除所有本科生信息 int addStudent(Undergraduate s); /添加本科生,需要先查找是否存在 int modifyStudent(string sno); /修改学生信息 ,需要先查找是否存在 int deleteStudent(string sno);/删除本科生，删除前先查找其是否存在 int queryStudent(string sno);/查找本科生,查到则显示,否则提示未查到 void displayAll();/输出所有本科生信息 void dataManage(); /本科生库维护 void dataSave(); void dataRead(); UndergraduateManager();/析构函数,将undergraduates写入Undergraduate.txt文件中;/构造函数,将Undergraduate.txt读到undergraduates中 UndergraduateManager:UndergraduateManager() dataRead(); /按本科生号查找/找到：返回数组下标/没找到：返回-1 int UndergraduateManager:qu