图状数据结构实验

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：图状数据结构实验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告-1-图状数据结构实验报告要求1目的与要求:1）掌握图和网的存储结构（邻接矩阵和邻接表）；2）掌握构造最小生成树的普利姆算法和C语言程序实现；3）掌握关键路径的计算算法和C语言程序实现；4）掌握拓扑序列的计算算法C语言程序实现；5）掌握最短路径的计算算法和C语言程序实现；6）按照实验题目要求独立完成实验内容（不统一安排实验时间，自行利用课余时间到实验室或自己宿舍做实验）；7）认真书写实验报告,并于13周周5前按时提交。2实验内容或题目（重要实验，分析参考程序，按照自己兴趣选择一个题目做实验）1）连通网的最小生成树及其应用实验内容：对下图1所示通信连通网，按照普里姆算法实现其最小生成树。2）AOE的关键路径计算：计算和标注下图2AOE网中的关键路径，同时列出图中各个事件（顶点）的VE、VL，各活动的最早、最晚开始时间、松弛时间等信息。图1通信连通网（权值单位：百万元）V1v6v5v4v3V226513566425《数据结构》实验报告-2-3）根据自己的专业课程学习计划或培养方案（在网上查），添加和完善书上P180表7-2中的课程（至少20门）和对应学习顺序图7.21（AOV网），然后依据拓扑序列计算算法，确定一个课程学习计划（即拓扑序列）。4）绘一个含有江苏省著名旅游点的（含10个景点）的旅游图，而后依据最短路径算法，计算出从连云港出发旅游各个景点的最短路径（路程）。3实验步骤与源程序#includestdio.h#includestdlib.h#includeiomanip.h#includeprocess.h//#definePROJECTNUMBER9//10//#definePLANNUMBER11//13intSearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);voidCreateGraphic(Graphicmap,projectnumber,activenumber);typedefstructnode{intadjvex;intdut;structnode*next;}edgenode;typedefstruct{intprojectname;intid;edgenode*link;1254367分析3概要设计3详细设计4测试计划2测试方案设计3文档整理2产品测试4编码40图1某简单软件项目开发工作工程网络图1254367分析3概要设计3详细设计4测试计划2测试方案设计3文档整理2产品测试4编码40图2某简单软件项目开发AOE网（单位月）《数据结构》实验报告-3-}vexnode;//vexnodeGraphicmap[PROJECTNUMBER];voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber){intbegin,end,duttem;inti,k;edgenode*p;for(i=0;iprojectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id=0;Graphicmap[i].link=NULL;}printf(某项目的开始到结束在图中的节点输入vi,vj,dut\n);printf(如：3,4,9回车表示第三节点到第四节点之间的活动用了9个单位时间\n);for(k=0;kactivenumber;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;}}intSearchMapPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,inttotaltime){inti,j,k,m=0;intfront=-1,rear=-1;int*topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列int*vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间int*ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间int*l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间int*e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间edgenode*p;totaltime=0;for(i=0;iprojectnumber;i++)ve[i]=0;for(i=0;iprojectnumber;i++){if(Graphicmap[i].id==0){《数据结构》实验报告-4-topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link;while(p){k=p-adjvex;Graphicmap[k].id--;if(ve[j]+p-dutve[k])ve[k]=ve[j]+p-dut;if(Graphicmap[k].id==0)topologystack[++rear]=k;p=p-next;}}if(mprojectnumber){printf(\n本程序所建立的图有回路不可计算出关键路径\n);printf(将退出本程序\n);return0;}totaltime=ve[projectnumber-1];for(i=0;iprojectnumber;i++)vl[i]=totaltime;for(i=projectnumber-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;jprojectnumber;j++){《数据结构》实验报告-5-p=Graphicmap[j].link;while(p){k=p-adjvex;e[++i]=ve[j];l[i]=vl[k]-p-dut;printf(|%4d|%4d|%4d|%4d|%4d|,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;}voidseekkeyroot(){intprojectnumber,activenumber,totaltime=0;vexnode*Graphicmap;system(cls);printf(请输入这个工程的化成图形的节点数:);scanf(%d,&projectnumber);printf(请输入这个工程的活动个数:);scanf(%d,&activenumber);Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));CreateGraphic(Graphicmap,projectnumber,activenumber);SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);printf(整个工程所用的最短时间为：%d个单位时间\n,totaltime);system(pause);}intmain(){charch;inti;for(;;){do{system(cls);printf(|欢迎进入求关键路径算法程序|);for(i=0;i80;i++)printf(*);printf(%s,(S)tart开始输入工程的节点数据并求出关键路径\n);printf(%s,(E)xit退出\n);《数据结构》实验报告-6-printf(%s,请输入选择:);scanf(%c,&ch);ch=toupper(ch);}while(ch!='S'&&ch!='E');switch(ch){case'S':seekkeyroot();break;case'E':return1;}}}4测试数据与实验结果（可以抓图粘贴）5结果分析与实验体会通过这次实验更加深入了解了图的运用，尤其是关键路径，在实际问题中很有用。同时也进一步理解拓扑排序和关键路径的算法