数据结构及算法的设计与实现

数据结构及算法的设计与实现沈阳工程学院课程设计设计题目:数据结构及算法的设计与实现系别信息系班级学生姓名学号指导教师职称数据结构及算法的设计与实现全文共45页，当前为第1页。起止日期:2009年12月数据结构及算法的设计与实现全文共45页，当前为第1页。沈阳工程学院计算机组成原理课程设计成绩评定表系（部）：信息工程系班级：学生姓名：指导教师评审意见评价内容具体要求权重评分加权分调研论证能独立查阅文献，收集资料；能制定课程设计方案和日程安排。0。15432工作能力态度工作态度认真,遵守纪律,出勤情况是否良好,能够独立完成设计工作,0。25432工作量按期圆满完成规定的设计任务，工作量饱满,难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺,技术用语准确，符号统一，编号齐全,图表完备，书写工整规范。0。55432指导教师评审成绩（加权分合计乘以8）分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具体要求权重评分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0。25432工作量工作量饱满,难度适中.0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理,文字通顺,技术用语准确,符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4)分加权分合计评阅教师签名：年月日答辩小组评审意见评价内容具体要求权重评分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0。55432答辩小组评审成绩（加权分合计乘以8)分加权分合计答辩小组教师签名：年月日数据结构及算法的设计与实现全文共数据结构及算法的设计与实现全文共45页，当前为第2页。数据结构课程设计任务书设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段,要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告.严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用.二、设计要求1、课程设计题目每组三题，每个学生必须独立完成;2、课程设计时间为2周;3、设计语言C（C++）不限;4、课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。上机时带上源程序、数据结构教材、C语言教材.5、上机任务1）选择合适的数据结构，并定义数据结构的结构体；2）根据程序所要完成的基本要求，设计出完整的算法;3）设计出主程序（main函数）,使其成为完整的程序。6、上机时间：按照实验室上机时间安排计划执行7、无论在校外、校内，都要严格遵守学校和所在单位的学习和劳动纪律、规章制度,学生有事离校必须请假。课程设计期间，无故缺席按旷课处理;缺席时间达四分之一以上者,其成绩按不及格处理。三、报告书写格式1．封皮2．成绩单3．任务书4．目录5．正文6．参考文献四、成绩评定数据结构及算法的设计与实现全文共数据结构及算法的设计与实现全文共45页，当前为第3页。评定成绩根据课程设计表现、成绩测验、课程设计报告等进行综合评定。评定等级：不及格、及格、中、良好、优秀。五、设计题目设计题目一教学计划安排检验程序（拓扑排序）【问题描述】针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划,并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。(1）输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。（2）程序所能达到的功能：按照用户的输入，给出每学期应学的课程。（3）测试数据：输入:学期数：５，课程数:12，课程间的先后关系数：16,课程的代表值：v1,v2，v3，v4,v5,v6，v7,v8，v9,v10,v11,v12。课程间两两间的先后关系：v1v2,v1v3,v1v4，v1v12，v2v3，v3v5，v3v7，v3v8，v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12，v11v6输出：第1学期应学的课程：v1v9第2学期应学的课程：v2v4v10v11第3学期应学的课程：v3v6v12第4学期应学的课程：v5v8第5学期应学的课程：v7设计题目二停车场问题【基本要求】停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端,最先到达的第一辆车停在最北端)若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时,停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场,每两停在车场的车要按时间长短缴费。要求：以栈模拟停车场,以队列车场外的便道，按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现.设计题目三编写一个猜数字游戏,有一定的容错功能,界面友好，功能齐全。游戏规则: 数据结构及算法的设计与实现全文共45页，当前为第4页。数据结构及算法的设计与实现全文共45页，当前为第4页。b，按以下提示猜出这个四位数。 c，每次猜测输入的数据给出类似的提示＊A＊B。d,其中A前的＊代表你本次猜对了多少个数字。 e，其中B前的＊代表你本次猜对的数字并且位置正确的个数。设计题目四设计实现关键路径的程序设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书进度安排设计工作4学时实现与调试12学时课程设计说明书4学时设计考核要求考勤20%课程设计说明书50％答辩30%五、参考书目[1]佟伟光，杨政《实用数据结构》（第二版）科学出版社[2］严蔚敏《数据结构》(C语言版）清华大学出版社[3]李保春编著,《数据结构习题与解析》，清华大学出版2001年第一版[4]徐孝凯编著，《数据结构课程实验》，清华大学出版2002年第一版[5]张乃笑编著，《数据结构与算法》，电子工业出版社2004年10月[6］王卫东编著,《数据结构辅导课》，西安电子科技大学出版社2001年［7]陈文博朱青著，《数据结构与算法》，机械工业出版社1996年［8］赵文静等编，《数据结构辅导》，西安交通大学出版社1999年数据结构及算法的设计与实现全文共数据结构及算法的设计与实现全文共45页，当前为第5页。摘要“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术.另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路,学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重。点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序.一定要把重点放在解题的思路上，通过思考，和大量的阅读,来构造一个完整的程序.请记住：重要的是学会编程,而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法,进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上,学好基本功。最后,感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。数据结构及算法的设计与实现全文共45页，当前为第6页。关键词：数据结构及算法的设计与实现全文共45页，当前为第6页。 目录数据结构及算法课程设计成绩评定表………。。。….。。Ⅰ课程设计任务书…………...…….….。Ⅱ摘要………………………。……。。。。..。。。Ⅴ1.停车场问题……………………。21.1问题分析.。…………………21.2数据结构与算法分析..…………21。3。核心代码………………。。…41。4运行结果…………………112。关键路径的程序………………………。..。..。。.142.1问题分析。.……………。.…142.2数据结构与算法分析.。………………。..142.3核心代码………………………152.4运行结果…………………193。教学计划安排检验程序（拓扑排序)………….…213.1问题分析.。…………………。.…213。2数据结构与算法分析………。.213。3核心代码………………………223。4运行结果…………….。。…27数据结构及算法的设计与实现全文共45页，当前为第7页。4.猜数字游戏……………….。。…数据结构及算法的设计与实现全文共45页，当前为第7页。4。1问题分析.,……………….。294。2数据结构与算法分析.。……………...…294.3核心代码……………。.。…294。4运行结果…………………33结论…………….。。.35数据结构及算法的设计与实现全文共45页，当前为第8页。致谢…………………………....。.。.3数据结构及算法的设计与实现全文共45页，当前为第8页。1停车场问题1。1问题分析停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端)若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要按时间长短缴费。要求：以栈模拟停车场，以队列车场外的便道,按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达"或“离去"信息、汽车牌照号码、以及到达或离去的时刻.对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费)。栈以顺序结构实现，队列以链表结构实现。1。2数据结构与算法分析本任务要求应用动态存储结构,并且需要两个栈和一个队列，栈用来模拟停车场，队列模拟便道。栈的特点是后进先出，队列的特点是先进先出。本任务应用了C语言中的类来自定义头文件，将任务分成多个的模块,增强了可读性和简单性，同时为日后的编写,调试,维护提供了极大地方便。该程序的基本流程图如图1-1所示。主要流程图如图1—2所示。数据结构及算法的设计与实现全文共数据结构及算法的设计与实现全文共45页，当前为第9页。图1—1基本流程图图1-2主流程图数据结构及算法的设计与实现全文共45页，当前为第10页。数据结构及算法的设计与实现全文共45页，当前为第10页。1.3核心代码＃include<stdio。h〉#include〈stdlib.h>#include〈string.h〉＃defineMAX2//车库容量为了便于观察这里把车库容量设置为2#defineprice0.05//每分钟每辆车的费用typedefstructtime｛inthour;intmin;}Time;//时间结点typedefstructnode{charnum[10］;Timereach；Timeleave；｝CarNode;//车辆信息结点typedefstructNODE｛CarNode*stack[MAX+1];inttop；｝SeqStackCar;//模拟车站typedefstructcar{CarNode*data；structcar*next；}QueueNode;typedefstructNode｛QueueNode*front；QueueNode＊rear;｝LinkQueueCar；//模拟通道///////////////////////////////////////////////////*定义方法＊/voidInitStack（SeqStackCar＊）;//初始化车站intInitQueue（LinkQueueCar＊）；//初始化便道intArrival（SeqStackCar*，LinkQueueCar*);//车辆到达voidLeave（SeqStackCar＊,SeqStackCar＊,LinkQueueCar＊）；//车辆离开voidList（SeqStackCar，LinkQueueCar）；//显示存车信息/////////////////////////////////////////////＊主函数＊/voidmain(）数据结构及算法的设计与实现全文共45页，当前为第11页。｛数据结构及算法的设计与实现全文共45页，当前为第11页。SeqStackCarEnter，Temp;LinkQueueCarWait；intch；InitStack（&Enter）；//构造一个空栈InitStack（＆Temp）；//InitQueue（&Wait);//构造一个空队列while（1）｛//printf（”\n请选择：1234\n”）；printf（"\n＆&＆&＆＆＆&＆＆＆＆＆&＆&＆＆＆＆&&&＆＆&1。车辆到达&＆&&＆&&＆&＆＆＆＆＆&&＆&&&&＆＆&");printf（”\n&＆&&＆&＆&&＆&＆&&＆＆＆&&&＆＆&＆&＆2.车辆离开&&＆＆&＆&&&&＆&＆&＆&＆＆&＆＆&&＆"）；printf("\n＆＆＆＆&&&&&&&&&＆＆&&&&&＆&＆＆&&3.列表显示&＆＆＆&＆&＆&&&＆&＆&&＆＆&&&&&&")；printf（"\n&&&&＆＆&＆＆&&&＆＆&＆＆&&&＆＆&&&＆4。退出系统＆&&＆＆＆&&＆＆＆＆&&＆&&&＆&＆&＆＆\n”);scanf（”％d”,＆ch)；if（ch〈1&&ch〉4)//当不符合要求时重新进行选择｛break;｝else｛//否则则进行方法的操作switch(ch）｛case1:Arrival（&Enter,&Wait)；break；//车辆到达的操作case2：Leave(&Enter,&Temp,&Wait）;break；//车辆离开的操作case3:List(Enter,Wait）;break;//列表显示的操作case4:exit（0）;//退出系统的操作default：break;｝}}｝///////////////////////////////////////////＊车场的初始化栈＊/数据结构及算法的设计与实现全文共45页，当前为第12页。voidInitStack（SeqStackCar＊s)//数据结构及算法的设计与实现全文共45页，当前为第12页。{inti;s-〉top=0；//栈为空for(i=0;i〈=MAX;i++）s-〉stack[s->top］=NULL;//初值为空}///////////////////////////////////////////////＊便道的初始化队列的链式结构*/intInitQueue(LinkQueueCar＊Q）{Q->front=（QueueNode*）malloc(sizeof（QueueNode））;if（Q—〉front!=NULL）｛Q—〉front->next=NULL;//队列头结点为空Q—〉rear=Q—〉front；return(1）;｝else｛return（0）；｝}///////////////////////////////////////////////*离站所进行的操作*/voidPRINT（CarNode*p,introom）｛intA1，A2，B1，B2;printf（”\n请输入离开的时间："）；scanf（”%d:％d”，&（p—〉leave。hour）,&（p->leave。min)）；printf（”\n离开车辆的车牌号为：”）;puts(p—〉num）;printf（”\n其到达时间为:%d:%d"，p->reach.hour,p—〉reach。min）;printf（”离开时间为：％d：％d",p->leave。hour,p-〉leave。min);A1=p—〉reach。hour;A2=p—〉reach.min；B1=p—〉leave.hour;B2=p—>leave.min;printf("\n应缴费用为：%2。1f元",(（B1—A1）*60+（B2—A2))＊price）;free（p)；｝数据结构及算法的设计与实现全文共45页，当前为第13页。数据结构及算法的设计与实现全文共45页，当前为第13页。//////////////////////////////////////////////*车辆到达＊/intArrival(SeqStackCar*Enter，LinkQueueCar*W）{CarNode＊p;QueueNode*t；p=（CarNode＊）malloc（sizeof（CarNode））；//生成结点//flushall（）；//清除所有缓冲区printf（"\n请输入车牌号:”）；scanf（"%s”，&p->num）；//得到车牌号if（Enter—〉top<MAX）{//判断如果停车场未满则进入Enter->top++；//top指针加一printf（"\n车辆在停车场内的第％d位置”,Enter-〉top)；printf（”\n请输入到达时间：")；scanf（"％d:％d",＆（p—〉reach。hour）,＆（p->reach.min)）；Enter—>stack［Enter->top］=p;//车辆进栈return（1）；}else{printf(”\n该车须在便道等候！”）;t=(QueueNode＊）malloc（sizeof（QueueNode)）;t—〉data=p；//把车辆信息存入队列的结点即车辆停在便道t—>next=NULL；//t结点的下一个结点为空W->front-〉next=t；//头指针的下一个为tW->rear=t;//尾指针指向treturn（1）;}}//////////////////////////////////////////*出栈＊/voidLeave（SeqStackCar＊Enter，SeqStackCar＊Temp，LinkQueueCar*W）｛inti，room;CarNode＊p，＊t；QueueNode＊q;/＊判断车场内是否有车＊/if（Enter->top>0）｛while(1）数据结构及算法的设计与实现全文共45页，当前为第14页。{数据结构及算法的设计与实现全文共45页，当前为第14页。printf(”\n请输入车在车场的位置:"，Enter->top）;scanf(”％d"，＆room）;if(room〈1&&room>=Enter—〉top）{break;}while(Enter-〉top〉room）｛Temp—>top++；//top指针加一Temp—>stack［Temp—>top］=Enter-〉stack［Enter—>top］；//把停车场里的车放入temp中Enter—>stack［Enter—>top］=NULL；//把停车场里的位置清空Enter->top--;//top指针减一同时}p=Enter—〉stack［Enter—〉top]；Enter->stack［Enter—〉top]=NULL;Enter-〉top——；while（Temp—〉top〉=1）{Enter—>top++；//当车出去后原来的车回到停车场Enter-〉stack［Enter-〉top]=Temp—>stack［Temp—〉top]；Temp-〉stack［Temp—>top］=NULL;Temp—〉top-—；｝PRINT(p，room）；//离开停车场的信息if((W->front!=W->rear）&＆Enter-〉top<MAX）//如果便道上有车,并且停车里有空位｛q=W->front-〉next；//把便道里的车赋给qt=q—>data；//车的信息赋给tEnter->top++;printf（"\n便道的％s号车进入车场第%d位置。",t—>num，Enter-〉top）;printf（"\n请输入现在的时间：”）;scanf（"％d：%d"，＆(t-〉reach。hour），&(t-〉reach.min)）；W—>front—〉next=q—>next;//头指针指向q的下一个if(q==W—〉rear）//如果便道里没车数据结构及算法的设计与实现全文共45页，当前为第15页。{数据结构及算法的设计与实现全文共45页，当前为第15页。W—>rear=W-〉front;//清空Enter—〉stack[Enter->top]=t；//进入停车场printf（"\n便道里没车\n"）；free（q）；｝break;｝else｛printf（"\n车场里没车。”);}break;｝}}//////////////////////////////////////////////////*列表的显示信息*/voidList1（SeqStackCar*s）｛inti;if(s—>top〉0）｛printf（"\n车场")；printf（"\n位置到达时间车牌号\n”）；for(i=1;i〈=s—〉top；i++）｛printf(”％d%10d：％d%s\n",i,s->stack[i]—>reach.hour，s—〉stack［i］-〉reach.min,s-〉stack［i]-〉num）；//puts(s-〉stack[i]-〉num）;}｝elseprintf（”\n车场里没车”)；}/////////////////////////////////////＊便道里的信息＊/voidList2（LinkQueueCar＊w）{数据结构及算法的设计与实现全文共45页，当前为第16页。QueueNode*p;数据结构及算法的设计与实现全文共45页，当前为第16页。p=w—〉front—〉next；if（w—>front!=w—〉rear）｛printf（”\n等待的车辆的号码为:"）；while（p!=NULL）{puts（p->data->num）;printf（”\n"）；p=p—〉next；｝｝elseprintf("\n便道里没有车。”）；｝//////////////////////////////////////////////////////voidList(SeqStackCars，LinkQueueCarw）｛intflag，m;flag=1;while(flag）｛printf（"\n请选择123"）;printf("\n1。车场\n2.便道\n3.返回”）;while(1)｛scanf（”％d",＆m)；if（m>=1||m〈=3）break；elseprintf("\n”）;｝switch（m){case1：List1（&s);break；case2：List2（&w）;break;case3:flag=0;break;default：break；｝数据结构及算法的设计与实现全文共45页，当前为第17页。数据结构及算法的设计与实现全文共45页，当前为第17页。｝1.4运行结果1。运行程序，打开停车场主菜单，如图1—3所示。图1-3主菜单2。根据菜单提示，输入“1”，然后输入停车车牌“辽A888888”和时间“8:图1—4输入停车信息数据结构及算法的设计与实现全文共45页，当前为第18页。数据结构及算法的设计与实现全文共45页，当前为第18页。 3.程序默认两个车道，当要求继续停车时，就停入便道里，如图1—5所示。图1—5便道停车4.根据提示,输入“3"后，再分别输入“1”和“2图1—6车道信息数据结构及算法的设计与实现全文共45页，当前为第19页。数据结构及算法的设计与实现全文共45页，当前为第19页。图1—7便道信息5.返回主菜单后，输入“2"，然后输入车离开的位置和时间,便显示车离开的信息费用以及便道的车进入车道要求输入信息,如图1—8所示，完成后便显示便道车的信息,如图1—图1—8车离开数据结构及算法的设计与实现全文共45页，当前为第20页。图1—9便道车进入停车场数据结构及算法的设计与实现全文共45页，当前为第20页。2关键路径2。1问题分析关键路径（CPM）是管理科学中的一个重要方法,广泛应用于大型工程计划工作，也称之为“统筹法”。关键路径法采用边表示活动的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件，事件说明某些活动或某些活动的完成，即阶段的结果。通常，利用AOE网络可以研究一下两个问题：⑴完成整个工程至少需要多少时间⑵哪些活动是影响工程进度的关键但是完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大路径称作为关键路径.2.2数据结构与算法分析首先得构造一个图来存储整个工程的顶点数和活动数。在描述关键路劲的算法时,设a活动由弧(j，k）表示，要确定如下几个相关的量：⑴事件V的最早出现时间和活动的最早开始时间，从源点v1到顶点v的最长路径长度称作事件j的最早出现时间，表示成e［j]。⑵活动a的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成L［i］。只要某活动a有L[i]=e[i]的关系，就称a为关键活动。事件j的最迟出现时间：事件j在不延误整个工程的前提下允许发生的最迟时间，表示为L［j］。对某条指向顶点V的边所代表的活动a可得到L[i]=L［j]—（活动a所需时间）。该程序的主要流程图如图2-1所示.数据结构及算法的设计与实现全文共45页，当前为第21页。数据结构及算法的设计与实现全文共45页，当前为第21页。图2—1关键路径主要流程图2。3核心代码#include〈stdio。h>#include<stdlib。h>＃include〈iomanip。h>＃include〈process。h>typedefstructnode｛intadjvex；intdut;structnode*next;｝edgenode；typedefstruct数据结构及算法的设计与实现全文共45页，当前为第22页。｛数据结构及算法的设计与实现全文共45页，当前为第22页。intprojectname；intid；edgenode*link;}vexnode;voidCreateGraphic（vexnode＊,int，int）；intSearchPath（vexnode＊，int，int,int&）；intmain（){intflag,projectnum，activenum,totaltime=0； printf（"请输入这个工程的化成图形的结点数:”)；scanf（"%d",＆projectnum）；printf("请输入这个工程的活动个数：")；scanf（"％d"，&activenum）;vexnode*Graphicmap=（vexnode*）malloc(projectnum*sizeof（vexnode)）；CreateGraphic(Graphicmap,projectnum，activenum）;flag=SearchPath（Graphicmap，projectnum,activenum，totaltime)； if（flag==0） printf("\n本程序所建立的图有回路不可计算出关键路径\n"）； else printf（"\n全工程可以完成的最早时间为：％d个单位时间\n"，totaltime）;system（"pause"）；}voidCreateGraphic（vexnode＊Graphicmap,intprojectnum,intactivenum）//创建图的函数{intbegin，end,duttem;edgenode＊p;for（inti=0;i〈projectnum;i++）｛ Graphicmap［i］。projectname=i；Graphicmap[i].id=0；Graphicmap[i］。link=NULL;｝printf（”某项目的开始到结束在图中的节点输入〈vi，vj，dut〉\n");数据结构及算法的设计与实现全文共45页，当前为第23页。printf（”如：1，2，3回车表示第1结点到第2结点之间的活动用了3个单位时间\n"）;数据结构及算法的设计与实现全文共45页，当前为第23页。for(intk=0；k〈activenum;k++）｛scanf（”％d，％d,%d"，＆begin，&end,&duttem）；p=（edgenode*）malloc（sizeof(edgenode）)；p-〉adjvex=end—1;p—>dut=duttem;Graphicmap[end-1］.id++;p->next=Graphicmap［begin-1］.link；Graphicmap[begin—1］.link=p；}}intSearchPath（vexnode*Graphicmap，intprojectnum,intactivenum，int&totaltime）//查找关键路径｛inti，j，k，m=0；intfront=-1,rear=-1;int＊topologystack=(int*)malloc(projectnum＊sizeof(int））;//保存拓扑排列int*vl=（int*）malloc(projectnum*sizeof（int）);//表示在不推迟整个工程的前提下，Vj允许最迟发生的时间int＊ve=（int＊)malloc（projectnum＊sizeof(int）)；//表示Vj最早发生时间int*l=（int*)malloc(activenum*sizeof（int））;//表示活动Ai最迟完成开始时间int*e=（int＊）malloc（activenum＊sizeof(int）);//表示活动最早开始时间edgenode＊p;totaltime=0；for（i=0;i<projectnum；i++）ve［i]=0;for（i=0；i<projectnum;i++）｛if（Graphicmap[i]。id==0）{topologystack［++rear]=i；m++;}}while（front!=rear)｛front++;数据结构及算法的设计与实现全文共45页，当前为第24页。j=topologystack［front］;数据结构及算法的设计与实现全文共45页，当前为第24页。m++;p=Graphicmap［j］.link；while（p）{k=p->adjvex；Graphicmap[k].id-—；if(ve［j]+p—>dut〉ve[k])ve［k]=ve[j］+p->dut；if（Graphicmap[k］。id==0）topologystack［++rear]=k；p=p-〉next;}}if(m〈projectnum）｛ return0；}totaltime=ve［projectnum—1];for（i=0；i<projectnum；i++）vl[i］=totaltime;for（i=projectnum-2;i〉=0；i-—）{j=topologystack[i]；p=Graphicmap［j].link;while（p）｛k=p->adjvex;if(（vl[k］-p-〉dut)<vl[j］）vl［j]=vl［k］—p—>dut；p=p-〉next；｝｝i=0；printf（"起点终点最早开始时间最迟完成时间差值是否为关键活动(*）\n")；for（j=0;j<projectnum；j++)｛数据结构及算法的设计与实现全文共45页，当前为第25页。p=Graphicmap[j].link;数据结构及算法的设计与实现全文共45页，当前为第25页。while（p）{k=p-〉adjvex；e［++i］=ve[j］;l［i]=vl[k］—p—>dut;printf（"%6d％8d％13d%18d%12d",Graphicmap[j].projectname+1,Graphicmap[k]。projectname+1，e[i］,l[i］，l［i］—e［i]);if（l[i］==e［i］)printf（”＊”）;printf("\n");p=p->next；}} return1；}2.4运行结果1。运行该程序，打开如图2-2所示,并输入这个工程的化成图形的结点数。图2—2输入结点数2。根据上图提示输入结点数后然后输入活动个数，如图2-3所示。 数据结构及算法的设计与实现全文共45页，当前为第26页。数据结构及算法的设计与实现全文共45页，当前为第26页。图2—3输入结点数和活动数 3。根据图2—3所示，输入9个节点之间的活动关系和时间，如图2—4所示。图2-4输入结点的关系和活动时间 4.输完11个活动后,即显示该工程关键活动信息，如图2-5所示。数据结构及算法的设计与实现全文共45页，当前为第27页。图2-5关键活动信息数据结构及算法的设计与实现全文共45页，当前为第27页。3教学计划安排检验程序（拓扑排序）3.1.问题分析针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。(1）输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符.（2）程序所能达到的功能：按照用户的输入，给出每学期应学的课程。（3)测试数据：输入：学期数：５,课程数：12，课程间的先后关系数：16，课程的代表值：v1，v2,v3,v4,v5，v6,v7，v8，v9,v10，v11,v12。课程间两两间的先后关系：v1v2,v1v3,v1v4，v1v12,v2v3,v3v5，v3v7，v3v8，v4v5,v5v7,v6v8,v9v10，v9v11，v9v12，v10v12,v11v6输出：第1学期应学的课程：v1v9第2学期应学的课程：v2v4v10v11第3学期应学的课程：v3v6v12第4学期应学的课程：v5v8第5学期应学的课程：v73。2数据结构与算法分析拓扑排序时有向图的一种重要运算.在课表排序中，每门课都有多种关系：先后关系，即必须在一类门课学完后，才能开始学习另一门课；②在一类课之间没有次序要求，即两门课可以同时嘘唏，互不影响.将AOV网络中的各个顶点排列成一个线性有序序列，使得所有要求的前趋、后趋关系都能得到满足。在AOV网络进行拓扑排序的方法：⑴在网络中选择一个没有前趋的顶点，并把它输出；⑵从网络中删去该顶点和从该顶点出发的所有有向边；⑶重复执行上述两步，直到网中所有的顶点都被输出。该程序的主要流程图如图3-1所示：数据结构及算法的设计与实现全文共45页，当前为第28页。数据结构及算法的设计与实现全文共45页，当前为第28页。图3—1拓扑排序流程图3.3核心代码＃include"malloc。h”＃include"stdio.h"#defineOK1#defineERROR0＃defineTRUE1＃defineFALSE0＃defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineMAX_VERTEX_NUM20typedefintStatus；typedefintSElemType;数据结构及算法的设计与实现全文共45页，当前为第29页。typedefstruct{数据结构及算法的设计与实现全文共45页，当前为第29页。 SElemType*base；//在栈构造之前和销毁之后,base的值为NULL SElemType＊top；//栈顶指针 intstacksize；//当前已分配的存储空间,以元素为单位｝SqStack；typedefstructArcNode{ intadjvex;//该弧所指向的顶点的位置 structArcNode＊nextarc；//指向第一条依附该顶点的弧的指针｝ArcNode;typedefstructVNode｛ chardata[10]； ArcNode＊firstarc；｝VNode，AdjList［MAX_VERTEX_NUM］;typedefstruct{ AdjListvertices; intvexnum，arcnum；//图的当前顶点数和弧数｝ALGraph;intindegree［20］=｛0}；//存储图的入度的全局变量数组StatusInitStack（SqStack&S）｛ //构造一个空栈S S。base=(SElemType*）malloc（STACK_INIT_SIZE*sizeof(SElemType））; if（!S.base) returnERROR；//内存分配失败 S.top=S。base； S.stacksize=STACK_INIT_SIZE; returnOK；｝//InitStackStatusPush(SqStack&S，SElemTypee){ if（！S。base) returnERROR；//存储分配失败 ＊S.top++=e；returnOK；｝//Push数据结构及算法的设计与实现全文共45页，当前为第30页。StatusPop（SqStack&S，SElemType&e）数据结构及算法的设计与实现全文共45页，当前为第30页。{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if（S.top==S。base) returnERROR； e=＊—-S。top； returnOK;}//PopStatusStackEmpty(SqStackS）{//判断栈是否为空，为空返回TRUE,否则返回FALSE if（S.top==S.base） returnTRUE; elsereturnFALSE；}StatusCreateDG（ALGraph&G){//建立邻接表 inti,v，w,vex； printf（”请输入课程数目（课程数必须小于20）:"）； scanf（"%d"，＆vex）; if（vex〉=20） { printf("请重新输入课程数目(课程数必须小于20）：”）； scanf（"％d",&vex）; }G.vexnum=vex; printf（”请输入课程间的先后关系数："）; scanf（"%d"，&G。arcnum）; printf（”请输入课程的代表值（课程名的长度小于等于10个字符）:"）； for（i=0；i〈G.vexnum；i++） {printf(”\n请输入第％d门课程名:”,i+1）； scanf（"％s"，&G。vertices［i］.data）；printf（”这门课对应的编号是％d”,i+1）; G。vertices［i].firstarc=NULL； ｝//输入顶点信息 printf(”\n请输入课程间两两间的先后关系(用对应编号表示中间用空格隔开，比如12）：”）; for（i=0;i<G.arcnum;i++）{//输入边的信息数据结构及算法的设计与实现全文共45页，当前为第31页。 scanf(”％d%d”,&v，&w)；//形式2数据结构及算法的设计与实现全文共45页，当前为第31页。 ArcNode*p=newArcNode;//建立结点 if（！p)returnERROR； p—>adjvex=w-1； p—>nextarc=G.vertices［v-1］。firstarc;//顶点v的链表 G。vertices[v-1］。firstarc=p;//添加到最左边 } returnOK;}voidFindInDegree（ALGraphG）{//求图的入度 ArcNode＊p; for（inti=0；i<G.vexnum；i++) { p=G。vertices［i］。firstarc; while(p) { for（intj=0；j〈G.vexnum;j++） if（p->adjvex==j） indegree[j］++; p=p-〉nextarc； } ｝｝StatusTopologicalSort（ALGraphG）｛//拓扑排序//有向图G采用邻接表存储结构SqStackS1,S2； ArcNode*p； inti，count,k； FindInDegree(G）; InitStack（S1)； InitStack（S2）; for（i=0；i<G。vexnum；++i) if（！indegree［i]) Push（S1,i）;//把入度为0的压入栈S1 count=0；//对输出顶点计数 while（!StackEmpty（S1））数据结构及算法的设计与实现全文共45页，当前为第32页。 {数据结构及算法的设计与实现全文共45页，当前为第32页。 printf（"第%d学期应学的课程："，count+1）; while（！StackEmpty（S1)) { Pop（S1，i); printf("%s”，G.vertices［i］.data）;//输出i号顶点 Push（S2,i）;//把i号顶点压入栈S2 } printf（”\n”）;count++；//计数 while（！StackEmpty（S2）) { Pop（S2,i）; for(p=G。vertices［i］。firstarc；p;p=p-〉nextarc) { k=p—>adjvex;//对i号顶点的每个邻接点的入度减1 if（!(—-indegree[k]）)//若入度减为0，则入栈 Push（S1，k); } ｝ } if（count<G。vexnum）//该有向图有回路 returnERROR； elsereturnOK；｝//TopologicalSortintmain（）｛ALGraphG； CreateDG（G); TopologicalSort（G）； return0;}数据结构及算法的设计与实现全文共45页，当前为第33页。数据结构及算法的设计与实现全文共45页，当前为第33页。3.4运行结果1.运行程序打开界面如图3-2所示,并根据提示，输入课程数目。图3-2开始界面2.根据界面提示,输入课程见的先后关系数及课程代表值，如图3—3所示。图3—3输入课程关系数和课程名数据结构及算法的设计与实现全文共45页，当前为第34页。数据结构及算法的设计与实现全文共45页，当前为第34页。3。根据界面提示，输入课程间的先后关系,如图3-4所示.图3-4输入课程间的先后关系4.输入完课程间的先后关系后，便显示出5个学期的课程名，如图3—5所示.图3-5各个学期的课程数据结构及算法的设计与实现全文共45页，当前为第35页。数据结构及算法的设计与实现全文共45页，当前为第35页。4猜数字游戏4。1问题分析编写一个猜数字游戏，有一定的容错功能，界面友好,功能齐全。游戏规则: a，一个四位数，各位上的数字不重复，从1到9.b，按以下提示猜出这个四位数. c，每次猜测输入的数据给出类似的提示*A*B.d,其中A前的＊代表你本次猜对了多少个数字. e，其中B前的*代表你本次猜对的数字并且位置正确的个数.4。2数据结构与算法分析本程序多次利用到了调用函数参数，for循环等，通过比较输入的四个数字和电脑随机的数字值大小来判断猜对的数字正确与否。5、函数间的调用关系图如下:显示玩家积分函数:display()新记录者函数;显示玩家积分函数:display()新记录者函数;breakrecord()随机产生4个数函数;getnumber(_)记录积分函数:record()记录积分函数:record()主函数;主函数;intmain()初始化记录者函数;初始化记录者函数;newest()自定义清屏函数自定义清屏函数myclear()读取破纪录者函数:读取破纪录者函数:goread()图4—2数据结构及算法的设计与实现全文共45页，当前为第36页。数据结构及算法的设计与实现全文共45页，当前为第36页。6、流程图比较输入的数和随机生成的数.给出提示.A表示数对位置也对,B表示数对位置不对1Main()纪录判断结果和积分youareright比较输入的数和随机生成的数.给出提示.A表示数对位置也对,B表示数对位置不对1Main()纪录判断结果和积分youareright输入四位不相同的数字,如果输入的不是数字或者输入的数字有重复,则重新输入输入四位不相同的数字,如果输入的不是数字或者输入的数字有重复,则重新输入退出退出恭喜正确恭喜正确查看积分查看积分图4-3数据结构及算法的设计与实现全文共45页，当前为第37页。4。3核心代码数据结构及算法的设计与实现全文共45页，当前为第37页。#include〈stdio。h〉＃include〈math。h>＃include<stdlib.h>#include〈time。h〉intRnd（)//产生十以内的随机整数。{intRteger;Rteger=rand（）％10;returnRteger;｝voidGet_b（intb［]）//得到用户输入的四位数，存储到数组b［4]中。{inti,j，m,n=10000;scanf（”％d"，&m)；if（m〉9999||m<999）｛printf（”输入错误请重新输入："）;scanf（"％d”，&m）；}for（i=0；i<=3；i++）｛b［i］=m/（n/10）；m=m-b［i]＊（n/10）;n=n/10；｝for（i=0;i〈=3；i++)for(j=0;j〈=3；j++）if（b[i］==b［j]&＆i！=j）｛printf("输入重复请重新输入”）;Get_b(b）;｝}voidIswantplay（char＊wantplay）//判断用户还想不想玩。{printf（”再来一局（y)，我不想玩了（n）"）；scanf（”%c",wantplay)；scanf（"%c",wantplay);printf("======================================================\n\n\n”);数据结构及算法的设计与实现全文共45页，当前为第38页。}数据结构及算法的设计与实现全文共45页，当前为第38页。voidReset（intA[］，intB[］,int*score,int＊a，int*b）//用来初始化一些变量.｛inti=0，t=0,j;(＊score）=0;//得分清零。(＊a）=0；(＊b）=0;//所猜对的数字的个数的计数器清零for（j=0;j<10;j++）A［j］=j；//初始化数组，为产生无重复随机数做准备。while（i<4）｛t=Rnd（）;if（A[t］）B[i]=A［t],A[t]=0,i++；｝//利用扑克牌中抽牌的思想，来产//生无重复随机数,存储到B［］（在main函数中为b[］)中.printf(”输入一个四位数开始吧！\n”）；printf（”-—-——-—-—--—-———-—--—--———-——\n"）；}voidCheck_ab（inta［］，intb[］，int＊A，int*B）//此函数用来检查用户所输入的四位数与系｛//统产生的四位数的相同情况.inti，j;for(i=0;i<=3;i++）//用两个嵌套的for循环来逐个比较a[］与b[]for（j=0;j<=3;j++）{if（a[i］==b[j]）//如果数字相同。｛if（i==j）//如果位置也相同。(*A）++；//A自加。if（！（i==j）)//如果位置不同。(＊B）++；//B自加。｝}}voidWelcome（）//打印程序的开始界面。｛数据结构及算法的设计与实现全文共45页，当前为第39页。printf（"＊＊*＊＊＊＊＊****＊＊*＊＊＊**＊＊*****＊*＊**＊*＊＊*＊*＊**＊＊＊*＊＊＊＊＊*＊*****＊*＊＊＊＊***＊**＊*\n”);数据结构及算法的设计与实现全文共45页，当前为第39页。printf（"*－－－－－－－－－－－－－－－－－*\n”);printf（"*=======＝===========猜数字游戏＝＝＝＝＝＝＝=======＊\n");printf（”＊－－－－－－－－－－－－－－---*\n”）；printf（”＊－－－－programedbywxl*\n”）;printf("***＊＊******＊＊＊＊*＊＊*＊＊＊＊＊**＊*＊**＊＊＊*＊＊*＊*＊****＊＊＊＊＊＊＊＊＊*＊＊*＊＊＊＊**＊****＊＊＊\n\n\n\n”）；}voidUsage（)//显示程序的用法.{printf("===============用法================================\n");printf（”1。计算机随机产生一个无重复数字的四位数由你来猜。\n")；printf（”2.若所猜的数位置与数字均正确,会显示一个A，若数字对位置不对,会显示一个B.\n”）；printf（"===========================================================================\n\n”）；｝voidPrintscore（intn)//显示用户的得分。｛switch（n){case0:printf（"你真是撞大运了！!恭喜！!恭喜！!加十分！\n”);break；case1：printf（"恭喜你!猜对了!你真是天才！加九分!\n”）；break;case2：printf（”不错!不错！猜对了！你真够聪明！加八分！\n"）；break;case3：pr