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

程序设计课程设计指导书软件学院 计算机工程系2013年6月17日前 言程序设计课程设计是计算机科学与技术专业的重要实践性课程。目的在于培养学生分析问题和解决问题的能力，为学生提供了一个既动手又动脑，独立实践的机会。将课本上的数据结构、离散数学和C语言的理论知识和实际应用问题进行有机结合，提高学生程序设计、程序调试及项目开发能力。为后续课程： 操作系统、软件工程，编译原理等课程的学习奠定必要的实践基础。本课程设计是利用数据结构、离散数学、C语言理论和实验课中学到的编程知识和编程技巧，通过布置具有一定难度、一定编程量的课程设计题目，利用C语言作为开发工具，使学生通过课程设计掌握高级编程语言的知识和编程技术，掌握程序设计的思想和方法，初步具备利用计算机求解实际问题的能力。通过程序设计课程设计课程的学习，能够帮助学生加深理解数据结构、离散数学、C语言基本概念，达到培养学生良好程序设计的习惯和运用 C 语言编写程序解决实际问题的能力。使学生学会把书本知识用于解决实际问题，起到深化理解和灵活掌握教学内容的目的。同时使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。通过该课程设计，学生应该掌握C或C+语言程序设计的方法、数据结构和离散数学理论知识，熟悉C或C+程序的开发环境及C或C+程序的调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力；学生应该具有如下基本技能：培养学生查阅参考资料、手册的自学能力，通过独立思考深入钻研问题，学会自己分析、解决问题。通过对所选题目方案分析比较，确立方案，编制程序与调试程序。能熟练调试程序，在教师的指导下，完成课题任务。根据个人的设计调试过程，按课程设计报告的要求撰写设计报告。选用教材及主要参考书：1 教材呼克佑. C语言程序设计. 电子工业出版社,2013严蔚敏. 数据结构(C语言版) 清华大学出版社，20122、主要参考书1 谭浩强. 程序设计题解与上机指导(三版) . 清华大学出版社，20122 邱仲潘. C语言参考手册. 机械工业出版社，20043 谭浩强. C语言程序设计（三版）. 清华大学出版社，20124 方世昌. 离散数学.西安电子科技大学出版社，20035 丁亚涛. C语言程序设计.高等教育出版社，2003目 录前 言1一课程设计报告要求1二课程设计报告示例迷宫问题2三设计题目121文本文件单词的检索与计数122停车场管理163交通咨询系统设计（最短路径问题）174学生管理系统21 一课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下五项：1【问题描述】简要描述问题，然后说明程序设计的任务，程序要做什么。明确规定以下内容：（1） 输入的形式和输入值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2【设计需求及分析】说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。实现设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。3【设计功能的实现】（用C或C+描述）/说明：用C或C+实现代码设计。4【实例测试及运行结果】列出测试结果，包括输入和输出。测试数据应该完整、严格。测试分析内容包括：（1） 测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析；（2） 算法的时空分析和改进设想；（3） 经验和体会。5【实现提示】使用说明：说明如何使用该程序，列出每一步的操作步骤。附录：列出程序文件名的清单以及必要的带注释的源程序。心得体会等等。二课程设计报告示例迷宫问题专业： 班级： 姓名： 学号： 完成日期： 【问题描述】编制一个求解迷宫通路的程序。以一个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）以二维数组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）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。【设计功能的实现】（用C或C+语言描述）说明：此内容由学生自己设计完成。提示：程序应包含的执行命令有：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.di4) e.di+; Push(S.e); /换下一个方向探索 curpos=NextPos(e.seat,e.di); /设定当前位置是该新方向上的相邻块 /if /ifwhile(!StackEmpty(S)&!found); return found;/MazePath5主函数和其他函数的伪码算法void main( ) /主程序 Initialization(); /初始化 do ReadCommand(cmd);/读入一个操作命令符 Interpret(cmd); /解释执行操作命令符 while(cmd!=q&cmd!=Q);/mainvoid Initialization() /系统初始化 clrscr();/清屏在屏幕上方显示操作命令清单： CreatMazec MazePathm PrintMazep Quitq;在屏幕下方显示操作命令提示框：/Initializationvoid ReadCommand(char &cmd) /读入操作命令符显示键入操作命令符的提示信息； do cmd=getche()while(cmdc,C，m,M,p,P,q,Q)；/ReadCommandvoid Interpret(char cmd)/解释执行操作命令switch(cmd) case c,C:提示用户输入“迷宫数据的文件名filename”；从文件读入数据分别存储在rnum，cnum和二维数组a2中； InitMaze(ma,a2,rnum,cnum); / 创建迷宫 输出迷宫建立完毕的信息 break;casem,M:提示用户输入迷宫的入口from和出口 term的坐标位置； if(MazePath(ma,from,term)/存在路径提示用户察看迷宫；else 输出该迷宫没有从给定的入口到出口的路径的信息；break；casep,P:PrintMaze(ma): /将标记路径信息的迷宫输出到终端/switch/InterPret6函数的调用关系图反映了演示程序的层次结构：主程序Initialization ReadCommand InterPretInitMaze MazePath PrintMazeInitStack Push Pop StackEmpty StackTraverseFootPrint MarkPrint Pass NextPos Same附录：源程序文件名清单：base.H /公用的常量和类型stkpas.H /栈类型maze.H /迷宫类型testmaze.C /主程序【实例测试及运行结果】迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。001000100010001000001101011100100001000001000101011110011100010111000000提示：当入口位置为（1，1），出口位置为（9，8）时，输出数据应为： *#*#*#*#*#*#*#*#*#*#*测试结果示例：三组测试数据和输出结果分别如下：1输入文件名为：m1.dat，其中迷宫数据为：3 20 00 00 0入口位置：1 1出口位置：3 2求解路径后输出的迷宫：*2输入文件名：m2.dat，其中迷宫数据为：3 40 0 0 0 0 0 1 1 0 0 0 0入口位置：1 1出口位置：3 4求解路径后输出的迷宫：*#*3输入文件名：m3.dat，其中迷宫数据同题目中的测试数据。入口位置：1 1出口位置：9 8求解路径后输出的迷宫正确，并和需求分析中所列相同。4输入文件名：m4.dat，其中迷宫数据为：4 90 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 00 0 1 1 1 0 0 1 10 0 1 1 1 0 1 0 0入口位置：1 1出口位置：4 9输出信息为：此迷宫从入口到出口没有路径。【实现提示】计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。用户手册：（1）本程序的运行环境为DOS操作系统，执行文件为：TestMaze.exe（2）进入演示程序后，即显示文本方式的用户界面：*CreatMaze-c MazePath-m PrintMaze-p Quit-q * Operation:-*Enter a operation code: c，m，p OR q * *键入操作命令符操作命令清单操作提示信息（3）进入“产生迷宫（CreatMaze）”的命令后，即提示键入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫已建成”。（4）进入“求迷宫路径（MazePath）” 的命令后，即提示键入入口位置（行号和列号，中间用空格分开，结束符为“回车符”）和出口位置（行号和列号，中间用空格分开，结束符为“回车符”），该命令执行之后输出相应信息。若迷宫中存在路径，则执行此命令后，迷宫状态已改变，若要重复执行此命令，无论是否改变出口和入口的位置，均需重新输入迷宫数据。（5）输入“显示迷宫”的命令后，随即输出当前的迷宫，即迷宫的初始状态或求出路径之后的状态。心得体会：1本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利，只在调试MazePath算法时，遇到两个问题：其一是，起初输出的迷宫中没有加上的记号，后发现是因为在MarkPrint函数中的迷宫参数丢失“变参”的原因；其二是，由于回退时没有将curpos随之减一，致使栈中路径上的序号有错。2栈的元素中的step域没有太多用处，可以省略。3StackTraverse在调试过程中很有用，它可以插入在MazePath算法中多处，以察看解迷宫过程中走的路径是否正确，但对最后的执行版本没有用。4本题中三个主要算法：InitMaze,MazePath和PrintMaze的时间复杂度均为0（m*n），本题的空间复杂度亦为0（m*n）（栈所占最大空间）5经验体会：借助DEBUG调试器和数据观察窗口，可以加快找到程序中疵点。【选作内容】（1） 编写递归形式的算法，求得迷宫中所有可能的通路；（2） 以方阵形式输出迷宫及其通路。三设计题目1 文本文件单词的检索与计数专业： 班级： 姓名： 学号： 完成日期： 1.1【问题描述】假设有如下的英文文本文档：(此处为太原理工大学学校简介英文版)TAIYUAN UNIVERSITY OF TECHNOLOGYTaiyuan University of Technology (TUT) has its history traced all the way back to the Western Learning School of Shanxi Grand Academy (1902), which was one of the three earliest national universities in China. With the tradition and development of over 100 years, TUT is now a general university with engineering as the major, sciences and technology integrated and coordinate development of multiple disciplines. It is a university that is included in the “Project 211” - the national higher education promotion program for 100 top universities in China.Recollecting the centennial history, generations of TUT have created its mission and glory of a century with responsibility and confidence; expecting the promising tomorrow, over 30,000 TUT students and faculty are producing splendor and perspectives by their wisdom and diligence. In the new era, Taiyuan University of Technology, following the Conception of Scientific Development, is determined to further the reformation on education, to reinforce the teaching management so as to upgrade its teaching and researching levels. Taiyuan University of Technology will be turning itself into a research-based university.设计C或C+程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为是单词(不包括数字)，单词之间用空格或标点符号分隔。 1.2【设计需求及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。线性表的顺序存储结构如下：#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct char word21 /存储单词，不超过20个字符 int count; /单词出现的次数 ElemType;typedef struct ElemType *elem; /存储空间基址 int length; /当前长度int listsize; /当前分配的存储容量 Sqlist;1.3【设计功能的实现】（用C或C+语言描述）/说明：要求由学生来完成代码的编写。1.3.1 实现顺序表的基本操作顺序表的初始化：InitList(SqList &L)顺序表上查找指定的单词：LocateElem(SqList &L,char *s) 若找到，单词的出现次数增1，返回0，否则返回该单词的插入位置。在顺序表上插入新的单词：InsertList(SqList &L,int i，char *s) 要求按字典顺序有序。新单词的出现次数为1.输出顺序表上存储的单词统计信息：PrintList(SqList &L) 输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。1.3.2 统计单词数统计过程如下：（1）输入要统计单词的文本文件名，打开相应的文件；（2）初始化顺序表；（3）从文本文件中读取字符，直到文件结束。具体描述如下：While (读文件没有结束结束) 过滤单词前的非字母字符； 读取一个单词，以字符串形式存储在一个字符数组中； 在线性表中查找该单词，若找到，单词的出现次数加1，否则返回其插入位置； 上一步中，若没找到，则进行插入操作； 处理下一个单词。（4）关闭文件，输出统计结果。1.4【实例测试及运行结果】1.4.1 运行实例一（说明：由学生自己来给出）1.4.1 运行实例二（说明：由学生自己来给出）2停车场管理专业： 班级： 姓名： 学号： 完成日期： 2.1【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.2【设计需求及分析】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。2.3【设计功能的实现】（用C或C+语言描述）/说明：此内容由学生自己设计完成。2.4【实例测试及运行结果】设n=2，输入数据为：（A,1,5）,（A,2,10）,（D,1,15）,（A,3,20）,（A,4,25）,（A5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中：A表示到达（arrival）；D表示离去（departure）；E表示输入结束（end）。2.5【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。/说明：要求由学生来补充。3交通咨询系统设计（最短路径问题）专业： 班级： 姓名： 学号： 完成日期： 3.1【问题描述】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。3.2【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;3.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为disti=costv1i,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数n)开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；3.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(vw)”,找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。3.3【设计功能的实现】（用C或C+语言描述）3.3.1 建立有向图的存储结构/说明：要求由学生来完成代码的编写。3.3.2 迪杰斯特拉算法/说明：要求由学生来完成代码的编写。3.3.3 费洛伊德算法/说明：要求由学生来完成代码的编写。3.3.4 运行主控程序/说明：要求由学生来完成代码的编写。3.4【实例测试及运行结果】3.4.1 运行实例一（求给定有向图3-1的最短路径）图3-1 一个有向图具体要求之一：求顶点到其余顶点的最短路径；分别求顶点b到顶点d之间的最短路径、顶点到顶点d之间的最短路径。提示：为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作：如用1来代替，。3.4.2 运行实例二（求给定有向图3-2的最短路径）图3-2 一个简单的交通网络图图3-2 是一个简单的交通网络图。具体要求之一：求顶点“北京”到其余各城市之间的最短路径；并分别求“成都”到“上海”之间以及“上海”到“西安”之间的最短路径。提示：为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的城市名称就用其对应的编号来操作：如北京用1来代替，。3.5【实现提示】/说明：学生自己补充。4学生管理系统专业： 班级： 姓名： 学号： 完成日期： 4.1【问题描述】大学里有各种类型的学生，校方需要对这些学生的信息进行计算机管理。所开发的软件应包括各类学生的添加、修改、删除和查找等功能。考虑到软件的可重用性、可扩展性和可维护性，校方决定采用面向对象的程序设计方法来开发系统。学生信息需要以文件方式保存到计算机硬盘中。另外，系统的用户界面应该尽可能友好，方便用户使用。4.2【设计需求及分析】(1) 使用C+语言开发，充分利用面向对象程序设计的类、对象、继承、封装和多态性等(2) 概念设计和实现该管理系统。(3) 设计一个Person（人员）类，考虑到通用性，只抽象出所有类型人员都具有的属性：name（姓名）, id（身份证号），gender（性别），birthday（出生日期）等等。其中“出生日期”为内嵌子对象，是一个Date（日期）类型，Date类具有属性: year(年)，month（月），day（日）。用成员函数实现对人员信息的录入和显示等必要功能操作。(4) 从Person类派生出Student（学生）类，添加属性： studentNo（学号），schoolName（学校），classIn (班级)。从Person类派生出Teacher（教师）类，添加属性：teacherNo（教师编号），schoolName（学校），department（部门）。(5) 从Student类中派生出UnderGraduate（本科生）类，添加属性：major（专业）。从Student类中派生出Graduate（研究生）类，添加属性：direction（研究方向），adviserName（导师姓名）。(6) 从Graduate类和Teacher类派生出T（助教博士生）类。(7) 写程序测试上述各类，看能否正常运行。(8) 构建必要的辅助类，实现对本科生、研究生和助教博士生的添加、修改、删除、查询管理。(9) 根据需要定义类的构造函数、析构函数、拷贝构造函数、成员函数。必要时重载函数。(10) 要求将Person类设置为虚基类，以消除其派生类成员访问的二义性问题（注意在虚基类各级派生类的构造函数实现时调用虚基类的构造函数）。(11) 要求在Person类中定义虚函数displayDetails（），用于显示当前对象的信息；同时定义虚函数inputData( )，用于从键盘获取当前对象的信息。Person类所有派生类也要定义同名虚函数，使程序可以实现动态多态性。(12) 用菜单方式设计主控模块程序。(13) 对程序源代码要给出各部分的详细注释，这也是该题目的考核重点之一。(14) 用UML语言描述系统用到的类及其关系。4.3【设计功能的实现】（用C或C+语言描述）/说明：此内容由学生自己设计完成。/以下代码仅供参考。程序框架:/*Copyright (C), 2013, TyutFile name: main.cppAuthor: gaobaolu Version: 1.0 Date: 2013.6.10Description: 应用程序主函数 */#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;