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

1、IKWWiUNIVEB&riYOFTECHMOLOCV程序设计课程设计指导书软件学院计算机工程系2015年6月15日、八_刖曰程序设计课程设计是计算机科学与技术专业的重要实践性课程。目的在于培养学生分析问题和解决问题的能力，为学生提供了一个既动手又动脑，独立实践的机会。将课本上的数据结构、离散数学和C语言的理论知识和实际应用问题进行有机结合，提高学生程序设计、程序调试及项目开发能力。为后续课程：操作系统、软件工程，编译原理等课程的学习奠定必要的实践基础。本课程设计是利用数据结构、离散数学、C语言理论和实验课中学到的编程知识和编程技巧，通过布置具有一定难度、一定编程量的课程设计题目，利用

2、C语言作为开发工具，使学生通过课程设计掌握高级编程语言的知识和编程技术，掌握程序设计的思想和方法，初步具备利用计算机求解实际问题的能力。通过程序设计课程设计课程的学习，能够帮助学生加深理解数据结构、离散数学、C语言基本概念，达到培养学生良好程序设计的习惯和运用C语言编写程序解决实际问题的能力。使学生学会把书本知识用于解决实际问题，起到深化理解和灵活掌握教学内容的目的。同时使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。通过该课程设计，学生应该掌握C或C+语言程序设计的方法、数据结构和离散数学理论知识，熟悉C或C+程序的开发环境及C或C+程序的调试过程，巩固和加深

3、对理论课中知识的理解，提高学生对所学知识的综合运用能力；学生应该具有如下基本技能：培养学生查阅参考资料、手册的白学能力，通过独立思考深入钻研问题，学会白己分析、解决问题。通过对所选题目方案分析比较，确立方案，编制程序与调试程序。能熟练调试程序，在教师的指导下，完成课题任务。根据个人的设计调试过程，按课程设计报告的要求撰写设计报告。选用教材及主要参考书：1教材呼克佑.C语言程序设计电子工业出版社,2013严蔚敏.数据结构（C语言版）清华大学出版社，20122、主要参考书1 谭浩强.程序设计题解与上机指导（三版）.清华大学出版社，20052 邱仲潘.C语言参考手册.机械工业出版社，20043 谭浩

4、强.C语言程序设计（三版）.清华大学出版社，20054丁亚涛.C语言程序设计.高等教育出版社，2003目录、八一±刖目1一课程设计报告要求1课程设计报告示例迷宫问题（参考）2设计题目（6选4）9.谁拿了最多奖学金9.统计数字10.文本文件单词的计数11.构造可以使n个城市连接的最小生成树13.交通咨询系统（最短路径问题）146.学生管理系统18一.课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下五项：1.【问题描述】简要描述问题，然后说明程序设计的任务，程序要做什么。明确规定以下内容：(1) 输入的形式和输入值的范围；(

5、2) 输出的形式；(3) 程序所能达到的功能；测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2.【设计需求及分析】说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。实现设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也写出伪码算法(伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。?【设计功能的实现】(用C或C+描述)说明：用C或C+实现代码设计。?【实例测试及运行结果】列出测试结果，包括输入和输出。测试数据应该完整、严格。测试分析内容包括：(1) 测试过程中遇

6、到的问题是如何解决的以及对设计与实现的回顾讨论与分析；(2) 算法的时空分析和改进设想；(3) 经验和体会。3 ?【使用说明】说明如何使用程序，列出每一步的操作步骤。4 ?【心得体会】谈谈在设计和调试过程中的收获。(1)以二维数组MAZEM+2N+2表示迷宫，其中：MAZE0J和MAZEM+1J(0<J<N+1)0表示通路,MN<10。M和列数N;从第2行至第M+1行(每行N个数)为迷宫值，同一行中的两个数字之间用空白字符相隔。(3) 迷宫的入口位置和出口位置可由用户随时设定。(4) 若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件终端)上，其中，字符&q

7、uot;#"表示障碍，字符"*”表示路径上的位置，字符"即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应(5) 本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得(即表示"死胡同”，信息。全部路径。二?课程设计报告示例迷宫问题(参考)专业：班级：姓名：学号：完成日期：【问题描述】编制一个求解迷宫通路的程序。以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编

8、写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2)【设计需求及分析】及MAZEl0和MAZElN+1(0<I<M+1为添加的一圈障碍。数组中以元素值为1表示障碍。限定迷宫的大小用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数【设计功能的实现】(用C或C+语言描述)设计如下:坐标位置类型typedefstruct(intr,c;/迷宫中行、列的范围PosType;迷宫

9、类型typedefstruct(intm,n;chararrRANGERANGE;/各位置取值','#','或'MazeType;0或1)voidInitMaze(MazeType&maze,inta,introw,intcol);按照用户输入的row行和col列的二维数组(元素值为设置迷宫的初值，包括加上边缘一圈的值boolMazePath(MazeType&maze,PosTypestart,PosTypeend);求解迷宫maze中，从入口start到出口end的一条路径若存在，则返回TRUE否则返回FALSEvoidPrintMa

10、ze(MazeTypemaze);/将迷宫以字符型方阵的形式输出到标准输出文件上3.栈类型typedefstructintstep;/typedefstructLinkTypetop;intsize;PosTypeseat;/Stack;/栈类型栈的基本操作directiveTypedi;/设置如下:/当前位置在路径上的“序号当前的坐标位置往下一坐标位ElemType;typedefstructNodeTypeElemTypedata;置的方向栈的元素类型NodeType*next;NodeType,*LinkType;/结点类型，指针类型voidInitStack(Stack&S)/

11、初始化，设S为空栈(S.top=NULL)voidDestroyStack(stack&S)/销毁栈S,并释放所占空间voidClearStack(Stack&S)/将S清为空栈intstackLength(StackS)/返回栈S的长度S.sizeStatusStackEmpty(StackS)若S为空栈(S.top=NULL)，则返回TRUE;否则返回FALSEStatusGetTop(Stacks,ElemTypee)/若栈S不空，则以e带回栈顶元素并返回TRUE否则返回FALSE;StatusPush(Stack&S,ElemTypee)/若分配空间成功，则在S

12、的栈顶插入新的栈顶元素e,并返回TRUE,/否则栈不变，并返回FALSEStatusPop(Stack&S,ElemType&e)若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE/否则返回FALSEvoidStackTraverse(Stacks,Status(*visit)(ElemTypee)/从栈底到栈顶依次对S中的每个结点调用函数visit其中部分操作的算法：StatusPush(Stack&S,ElemTypee)/若分配空间成功，则在S的栈顶插入新的栈顶元素e,并返回TRUE/否则栈不变，并返回FALSEif(MakeNode(p,e)p->

13、next=s.top;s.top=p;s.size+;returnTRUE;elsereturnFALSE;StatusPop(Stack&S,ElemType&e)若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE/否则返回FALSE且e无意义if(StackEmpty(S)returnFALSE;else(p=S.top;S.top=S.top->next;e=p->date;S.size-;returnTRUE;4. 求迷宫路径的伪码算法:StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend)/若迷宫中

14、存在从入口start到出口end的通道,则求得一条存入在栈中/(从栈底到栈顶为从入口到出口的路径)InitStack(S);curpos=start;curstep=1;found=FALSE;doif(Pass(maze,curpos)/当前位置可以通过，/，并返回TRUE否则返回FALSE设定“当前位置”为“入口位置”探索第一即是未曾走到过的通道块留下足迹FootPrint(maze,curpos);e=(curstep,curpos,1);Push(S,e);/加入路径if(Same(curpos,end)found=TRUE;/到达终点(出口)elsecurpos=NextPos(cu

15、rpos,1);/下一位置是当前位置的东邻curstep+;/探索下一步/else/if当前位置不能通过else/if(!StackEmpty(S)Pop(S,e);while(e.di=4&&!StackEmpty(S)MarkPrint(maze,e,seat);Pop(S,e);curstep-;/留下不能通过的标记，并退回一步/whileif(e.di<4)e.di+;Push(S.e);/换下一个方向探索curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻块/if/ifwhile(!StackEmpty(S)&&

16、;!found);returnfound;/MazePath5.主函数和其他函数的伪码算法/主程序Initialization();/doReadCommand(cmd);/Interpret(cmd);/while(cmd!=/mainvoidInitialization()/系统初始化clrscr();/清屏在屏幕上方显示操作命令清单：CreatMazecMazePath在屏幕下方显示操作命令提示框：/InitializationvoidReadCommand(char&cmd)voidmain()初始化读入一个操作命令符解释执行操作命令符q'&&cmd!=

17、'Q');mPrintMazepQuit-q;/读入操作命令符显示键入操作命令符的提示信息；docmd=getche()while(cmdP,'C','m','M','p',F,'q','Q');voidInterpret(charcmd)/解释执行操作命令switch(cmd)case'c','C':提示用户输入“迷宫数据的文件名filename”从文件读入数据分别存储在rnum,cnum和二维数组a2中；InitMaze(ma,a2,rnum,cn

18、um);/创建迷宫输出迷宫建立完毕的信息break;case'm','M':提示用户输入迷宫的入口from和出口if(MazePath(ma,from,term)/存在路径提示用户察看迷宫；else输出该迷宫没有从给定的入口到出口的路径的信息;break；/ReadCommandterm的坐标位置;/switchcase'p',T':PrintMaze(ma):/将标记路径信息的迷宫输出到终端/InterPret附录：源程序文件名清单:base.H/公用的常量和类型stkpas.H/栈类型maze.H/迷宫类型testmaze.C/主程序

19、【实例测试及运行结果】迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口001000100010001000001101011100100001000001000101011110011100010111000000提示：当入口位置为（1,1）,出口位置为（9,8）时，输出数据应为*#*#*#*#*#*r:#*#*#*#*#*测试结果示例：三组测试数据和输出结果分别如下：1.输入文件名为：m1.dat,其中迷宫数据为00入口位置：11出口位置：32求解路径后输出的迷宫*2?输入文件名：m2.dat,其中迷宫数据为34000000110000入口位置：11出口位置：34求解路径后

20、输出的迷宫：*#*3?输入文件名：m3.dat,其中迷宫数据同题目中的测试数据。入口位置：11出口位置：98求解路径后输出的迷宫正确，并和需求分析中所列相同4?输入文件名：m.dat:,其中迷宫数据为449000000100010001000001110011001110100入口位置：11出口位置：49输出信息为：此迷宫从入口到出口没有路径【使用说明】(1)本程序的运行环境为DOS操作系统，执行文件为：TestMaze.exe(2)进入演示程序后，即显示文本方式的用户界面：*CreatMaze-cPrintMaze-pOperation:(3)进入“产生迷宫(CreatMaze)”的命令后，

21、即提示键入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫已建成”(4)进入“求迷宫路径(MazePath)”的命令后，即提示键入入口位置(行号和列号，中间用空格分开，结束符为“回车符”)和出口位置(行号和列号，中间用空格分开，结束符为“回车符”)，该命令执行之后输出相应信息。若迷宫中存在路径，则执行此命令后，迷宫状态已改变，若要重复执行此命令，无论是否改变出口和入口的位置，均需重新输入迷宫数据。(5)输入“显示迷宫”的命令后，随即输出当前的迷宫，即迷宫的初始状态或求出路径之后的状态。心得体会：1.本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利，只在调试

22、MazePath算法时，遇到两个问题：其一是，起初输出的迷宫中没有加上'的记号，后发现是因为在MarkPrint函数中的迷宫参数丢失“变参”的原因；其二是，由于回退时没有将curpos随之减一，致使栈中路径上的序号有错。2. 栈的元素中的step域没有太多用处，可以省略。3. StackTraverse在调试过程中很有用，它可以插入在MazePath算法中多处，以察看解迷宫过程中走的路径是否正确，但对最后的执行版本没有用。4. 本题中三个主要算法：InitMaze,MazePath和PrintMaze的时间复杂度均5. 为0(m*n),本题的空间复杂度亦为0(m*n)(栈所占最大空间)

23、经验体会：借助DEBUG调试器和数据观察窗口，可以加快找到程序中疵点。【选作内容】(1) 编写递归形式的算法，求得迷宫中所有可能的通路；(2) 以方阵形式输出迷宫及其通路。1. L设计题目（6选4）谁拿了最多奖学金i.i【问题描述】某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各白不同：80分（80），并且在本学期内发表1篇或85分（85），并且班级评议成绩高于8090分（90）的学生均可获得；85分（85）的西部省份学生均可获得；80分（80）的学生干部均可获得；1）院士奖学金，每人1篇以上论文的学生均可获得;2）五四奖学金，每人3）成绩优秀奖，每人4）西部奖

24、学金，每人5）班级贡献奖，每人8000元，期末平均成绩高于分408评白摺毒纳峰f于2000元，期末平均成绩高于1000元，期末平均成绩高于850元，班级评议成绩高于只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。1.2【基本要求】现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。输入数据格式格式：输入的第一行是一个整数N（1=N=100），表示学生的总数。接下来的N行

25、每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）;是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。输出数据格式：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第

26、三行是这N个学生获得的奖学金的总数。样例输入：4YaoLin8782YN0ChenRuiyi8878NY1LiXin9288NN0ZhangQin8387YN1样例输出：2. ChenRuiyi900028700统计数字2.1【问题描述】某次科研调查时得到了n个白然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些白然数各白出现的次数，并按照白然数从小到大的顺序输出统计结果。2.2【基本要求】原始数据保存在文件count.in中，文件包含n+1行。第1行是整数n（1<=n<=200000），表示白然数的个数；第2n+1行每行

27、一个白然数。结果保存在文件count.out中，文件count.out包含m行（m为n个白然数中不相同数的个数），按照白然数从小到大的顺序输出。每行输出两个整数，分别是白然数和该数出现的次数,其间用一个空格隔矛【测试数据】count.incount.out1002100100由于数据量可能很大，要注意程序的运行效率。2.3【实现提示】1）白己建立输入文件count.in。使用TC或VC或Word等编辑器等编辑样例输入内容，按文本格count.out中2）定义顺序表，元素类型为:Element,顺序表类型为：SeqList,用顺序表的数组data记录白然式存盘。程序从该文件中读取数据处理，最后将

28、统计结果写入文件数和该数出现的次数。定义如下:typedefstructdatalongintnumber;longintcount;Element;*/typedefstructlistElementdata10000;/*存储白然数和该数出现的次数intlength;/*存储不同白然数的个数,即顺序表的长度*/SeqList;3）从文件中每读出一个数据，就在顺序表中查找，若存在，则该数出现次数增1,否则将该数插入数组中，出现次数为1,插入后使顺序表中的数据按白然数有序。文本文件单词的计数3.1【问题描述】假设有如下的英文文本文档：(此处为太原理工大学学校简介英文版)TAIYUANUNIVE

29、RSITYOFTECHNOLOGYTaiyuanUniversityofTechnology(TUT)hasitshistorytracedallthewaybacktotheWesternLearningSchoolofShanxiGrandAcademy(1902),whichwasoneofthethreeearliestnationaluniversitiesinChina.Withthetraditionanddevelopmentofover100years,TUTisnowageneraluniversitywithengineeringasthemajor,sciencesan

30、dtechnologyintegratedandcoordinatedevelopmentofmultipledisciplines.Itisauniversitythatisincludedinthe-Project211thenationalhighereducationpromotionprogramfor100topuniversitiesinChina.Recollectingthecentennialhistory,generationsofTUThavecreateditsmissionandgloryofacenturywithresponsibilityandconfiden

31、ce;expectingthepromisingtomorrow,over30,000TUTstudentsandfacultyareproducingsplendorandperspectivesbytheirwisdomanddiligence.Inthenewera,TaiyuanUniversityofTechnology,followingtheConceptionofScientificDevelopment,isdeterminedtofurtherthereformationoneducation,toreinforcetheteachingmanagementsoastoup

32、gradeitsteachingandresearchinglevels.TaiyuanUniversityofTechnologywillbeturningitselfintoaresearch-baseduniversity.设计C或C+程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字)，单词之间用空格或标点符号分隔。3.2【设计需求及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储

33、。线性表的顺序存储结构如下：#defineLIST_INIT_SIZE100/#defineLISTINCREMENT10/typedefstructcharword21/intcount;/ElemType;typedefstructElemType*elem;/intlength;/intlistsize;/线性表存储空间的初始分配量线性表存储空间的分配增量存储单词，不超过20个字符单词出现的次数存储空间基址当前长度当前分配的存储容量Seqlist;3.3【设计功能】3.3.1实现顺序表的基本操作顺序表的初始化:InitList(SqList&L)顺序表上查找指定的单词：Locat

34、eElem(SqList&L,char*s)若找到，单词的出现次数增1,返回0,否则返回该单词的插入位置。在顺序表上插入新的单词：InsertList(SqList&L,inti,char*s)要求按字典顺序有序。新单词的出现次数为1.输出顺序表上存储的单词统计信息：PrintList(SqList&L)输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。3.3.2统计单词数统计过程如下：(1) 输入要统计单词的文本文件名，打开相应的文件；初始化顺序表；从文本文件中读取字符，直到文件结束。具体描述如下：while(读文件没有结束结束)(过滤单词前的非字母

35、字符；读取一个单词，以字符串形式存储在一个字符数组中；在线性表中查找该单词，若找至叭单词的出现次数加1,否则返回其插入位置；上一步中，若没找到，则进行插入操作；处理下一个单词。(2) 关闭文件，输出统计结果。3.4【测试数据】参考给定的文件：tyut.txt,或学生白己找一些英文文本文件。3. 构造可以使n个城市连接的最小生成树4.1【问题描述】给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。4.2【基本要求】1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路,则将相应边的权

36、值设为白己定义的无穷大值。2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。3、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。4.3【测试数据】学生白主确定或参考下图图4-1一个带权图（网络）5?交通咨询系统（最短路径问题）5.1【问题描述】在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以

37、回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少A到顶点B的所含边B就终止。由此A与B之类的等等的路径选择问题。的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。5.2【设计需求及分析】（里需费用。现任

38、两个城市顶点之间的最短设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实路径问题。5.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵:设G=（V,E）是一个图，结点集为VVi"MJnn，当（Vj）或Vi,VjEG的邻接矩阵A（aj）nn,aj0或，当（Vj,Vj）或Vj,VjE当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。

39、图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definfMVNum50/最大顶点数typedefstructVertexTypevexsMVNum;/顶点数组，类型假定为char型AdjmatrixarcsMVNumMVNum;/邻接矩阵，假定为int型MGraph;5.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路

40、径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V,巳是一个有向图，结点集为，VVi,V2,Vn,cost是表示G的邻接矩阵，costij表示有向边vi,j的权。若不存在有向边vi,j，贝Ucostij的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点vi为源点，集合S的初态只包含一个元素，即顶点vi。数组dist记录从源点到其他顶点当前的最

41、短距离，其初值为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,置空最短

42、路径终点集，置初始的最短路径值；Svi=TRUE;Dvi=0;强集初始时只有源点，源点到源点的距离为0While（S集中顶点数vn）开始循环，每次求得Vi到某个v顶点的最短路径，并加v到S集中；Sv=TRUE;更新当前最短路径及距离；5.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V,E），要对G中任意一对顶点有序对"v,w（vw）”，找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。

43、费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点vi到vj的最短路径。如果从vi到w存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径Vvi,v1和Vvi,vj是否存在。如果存在，则比较Vvi,vj和vi,vl,vj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径VV,v2,vj，若没有，贝IJ说明从v到v的当前最短路径就是前一步求出的；若有，那么Vvi,v2,vj可分解为vvi,v2和v2,vj，而这两条路径是前一次找到的中间顶点序号不大于1的最短路

44、径，将这两条路径长度相加就得到路径Vvi,v2,vj的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点Vn加入当前从Vi到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n,所以Vi到w的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是Vi到Vj的最短路径。5.3【设计功能】（用C或C+语言描述）1.建立有向图的存储结构.迪杰斯特拉算法.费洛伊德算法5.4【测试实例及运行结果】运行实例一，求

45、给定有向图5-1的最短路径ka/99Akb10rc）qXI。"21e一j/图5-1一个有向图求顶点a到其余顶点的最短路径；分别求顶点b到顶点d之间的最短路径、顶点a到顶点d之间的最短路径。提示：为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作：女口a用1来代替，。运行实例二，求给定有向图5-2的最短路径。图5-2一个简单的交通网络图图5-2是一个简单的交通网络图。求顶点“北京”到其余各城市之间的最短路径;并分别求“成都”到“上海”之间以及“上海”到“西安”之间的最短路径。提示：为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的城市名称就用其对应

46、的编号来操作：如北京用1来代替，。6.学生管理系统6.1【问题描述】大学里有各种类型的学生，校方需要对这些学生的信息进行计算机管理。所开发的软件应包括各类学生的添加、修改、删除和查找等功能。考虑到软件的可重用性、可扩展性和可维护性，校方决定采用面向对象的程序设计方法来开发系统。学生信息需要以文件方式保存到计算机硬盘中。另外，系统的用户界面应该尽可能友好，方便用户使用。6.2【设计需求及分析】（1）使用C+语言开发，充分利用面向对象程序设计的类、对象、继承、封装和多态性等（2）概念来设计和实现该管理系统。（3）设计一个Person（人员）类，考虑到通用性，只抽象出所有类型人员都具有的属性：nam

47、e（姓名），id（身份证号），gender（性别），birthday（出生日期）等等。其中“出生日期”为内嵌子对象，是一个Date（日期）类型，Date类具有属性：year（年），month（月），day（日）。用成员函数实现对人员信息的录入和显示等必要功能操作。（4）从Person类派生出Student（学生）类，添加属性：studentNo（学号），schoolName（学校），classln（班级）。从Person类派生出Teacher（教师）类，添加属性：teacherNo（教师编号），schoolName（学校），department（部门）。（5）从Student类中派生出Unde

48、rGraduate（本科生）类，添加属性：major（专业）。从Student类中派生出Graduate（研究生）类，添加属性：direction（研究方向），adviserName（导师姓名）。（6）从Graduate类和Teacher类派生出TA（助教博士生）类。（7）写程序测试上述各类，看能否正常运行。（8）构建必要的辅助类，实现对本科生、研究生和助教博士生的添加、修改、删除、查询管理。（9）根据需要定义类的构造函数、析构函数、拷贝构造函数、成员函数。必要时重载函数。（10）要求将Person类设置为虚基类，以消除其派生类成员访问的二义性问题（注意在虚基类各级派生类的构造函数实现时调用虚

49、基类的构造函数）。（11）要求在Person类中定义虚函数displayDetails（），用于显示当前对象的信息；同时定义虚函数inputData（），用于从键盘获取当前对象的信息。Person类所有派生类也要定义同名虚函数，使程序可以实现动态多态性。（12）用菜单方式设计主控模块程序。（13）对程序源代码要给出各部分的详细注释，这也是该题目的考核重点之一。（14）用UML语言描述系统用到的类及其关系。6.3【设计功能的实现】（用C或C+语言描述）说明：此内容由学生白己设计完成。以下代码仅供参考。程序框架：/*Copyright(C),2010,TyutFilename:main.cppAu

50、thor:gaobaoluVersion:1.0Date:2010.6.28Description:应用程序主函数*#include<cstdlib>#include<iostream>#include"date.h"#include"person.h"#include"student.h"#include"teacher.h"#include"undergraduate.h"#include"graduate.h"#include"ta.h

51、"#include"undergraduateManager.h"usingnamespacestd;intmain(intargc,char*argv)intchoiceN;UndergraduateManagerunMan;cout<<"1*"<<endl;cout<<”*|*|*|*"<<endl;cout<<"*|*|欢迎您使用学生管理系统|*|*"<<endl;cout<<"*|*|*|*"<&l

52、t;endl;cout<<"1*"<<endl;docout<<"<>"<<endl;cout<<"ntt1:本科生管理”；cout<<"ntt2:研究生管理”；cout<<"ntt3.助教博士生管理”；cout<<"ntt0:离开"cout<<endl;cout<<"<>"<<endl;cout<<"请选择：

53、"<<endl;cin>>choiceN;switch(choiceN)case1:unMan.dataManage();break;case2:/break;case3:/break;default:break;while(choiceN!=0);cout<<*“<<endl;cout<<"*|*|感谢使用学生管理系统|*|*"<<endl;cout<<"*a"<<endl;/*Copyright(C),2010,TyutFilename:unde

54、rgraduateManager.hAuthor:gaobaoluVersion:1.0Date:2010.6.28Description:本科生管理类*/#ifndefUNDERGRADUATE_MANAGER_H#defineUNDERGRADUATE_MANAGER_H#include<iostream>#include<string>#include<fstream>#include"undergraduate.h"usingnamespacestd;/*DefineaClass:UndergraduateManager本科生管理

55、类*/classUndergraduateManager(private:inttop;/记录指针Undergraduateundergraduates100;/本科生记录public:UndergraduateManager();构造函数，将Undergraduate.txt读至Uundergraduates中intqueryByNo(stringsno);/按本科生号查找/找到：返回数组下标/没找到：返回-1voidclearStudent();/删除所有本科生信息intaddStudent(Undergraduates);/添加本科生，需要先查找是否存在intmodifyStudent(

56、stringsno);/修改学生信息,需要先查找是否存在intdeleteStudent(stringsno);/删除本科生，删除前先查找其是否存在intqueryStudent(stringsno);/查找本科生，查至则显示，否则提示未查至voiddisplayAll();/输出所有本科生信息voiddataManage();/本科生库维护voiddataSave();voiddataRead();UndergraduateManager();析构函数，将undergraduates写入Undergraduate.txt文件中;构造函数将Undergraduate.txt读至ijunderg

57、raduates中UndergraduateManager:UndergraduateManager()dataRead();按本科生号查找/找到：返回数组下标没找到：返回-1intUndergraduateManager:queryByNo(stringsno)(for(inti=0;i<=top;i+)if(undergraduatesi.getStudentNo()=sno)returni;return-1;/删除所有本科生信息voidUndergraduateManager:clearStudent()(top=-1;/添加本科生，需要先查找是否存在intUndergraduateManager:addStudent(Undergraduates)(intp=queryByNo(s.getStudentNo();if(p=-1)(top+;undergraduatestop=s;dataSave();保存return1;else(cout<<