图状数据结构实验

1、精选优质文档-倾情为你奉上淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 图状数据结构实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日专心-专注-专业图状数据结构实验报告要求1目的与要求:1）掌握图和网的存储结构（邻接矩阵和邻接表）；2）掌握构造最小生成树的普利姆算法和C语言程序实现；3）掌握关键路径的计算算法和C语言程序实现；4）掌握拓扑序列的计算算法C语言程序实现；5）掌握最短路径的计算算法和C语言程序实现；6）按照实验题目要求独立完成实验内容（不统一安排实验时间，自行利用课余时间到实验室或自己宿舍做实验）；7）认真书写实验报告,并于13周

2、周5前按时提交。2 实验内容或题目（重要实验，分析参考程序，按照自己兴趣选择一个题目做实验）1）连通网的最小生成树及其应用实验内容：对下图1所示通信连通网，按照普里姆算法实现其最小生成树。图1 通信连通网（权值单位：百万元）V1v6v5v4v3V2265135664252）AOE的关键路径计算：计算和标注下图2 AOE网中的关键路径，同时列出图中各个事件（顶点）的VE、VL，各活动的最早、最晚开始时间、松弛时间等信息。1254367分析3概要设计3详细设计4测试计划2测试方案设计3文档整理2产品测试4编码40图1 某简单软件项目开发工作工程网络图1254367分析3概要设计3详细设计4测试计划

3、2测试方案设计3文档整理2产品测试4编码40图2 某简单软件项目开发AOE网（单位月）3）根据自己的专业课程学习计划或培养方案（在网上查），添加和完善书上P180表7-2中的课程（至少20门）和对应学习顺序图7.21（AOV网），然后依据拓扑序列计算算法，确定一个课程学习计划（即拓扑序列）。4）绘一个含有江苏省著名旅游点的（含10个景点）的旅游图，而后依据最短路径算法，计算出从连云港出发旅游各个景点的最短路径（路程）。3 实验步骤与源程序#include<stdio.h> #include<stdlib.h> #include<iomanip.h> #inc

4、lude <process.h> /#define PROJECTNUMBER 9/10 /#define PLANNUMBER 11/13 int SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); void CreateGraphic(Graphicmap,projectnumber,activenumber); typedef struct node int adjvex; int dut; struct node *next; edgenode; typedef struct int project

5、name; int id; edgenode *link; vexnode; /vexnode GraphicmapPROJECTNUMBER; void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) int begin,end,duttem; int i,k; edgenode *p; for(i=0;i<projectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(

6、"某项目的开始到结束在图中的节点输入<vi,vj,dut>n"); printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间n"); for(k=0;k<activenumber;k+) scanf("%d,%d,%d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode); p->adjvex =end-1; p->dut =duttem; Graphicmapend-1.id +; p-

7、>next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int totaltime) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int);/用来保存拓扑排列 int* vl=(int*)malloc(projectnumber*sizeof(int

8、);/用来表示在不推迟整个工程的前提下，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;i<projectnumber;i+) vei=0; for(i=0;i<projectnum

9、ber;i+) if(Graphicmapi.id=0) topologystack+rear=i; m+; while(front!=rear) front+; j=topologystackfront; m+; p=Graphicmapj.link ; while(p) k=p->adjvex ; Graphicmapk.id -; if(vej+p->dut >vek) vek=vej+p->dut ; if(Graphicmapk.id =0) topologystack+rear=k; p=p->next ; if(m<projectnumber)

10、 printf("n本程序所建立的图有回路不可计算出关键路径n"); printf("将退出本程序n"); return 0; totaltime=veprojectnumber-1; for(i=0;i<projectnumber;i+) vli=totaltime; for(i=projectnumber-2;i>=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p->adjvex ; if(vlk-p->dut )<vlj) vlj=vlk-p->d

11、ut ; p=p->next ; i=0; printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |n"); for(j=0;j<projectnumber;j+) p=Graphicmapj.link; while(p) k=p->adjvex ; e+i=vej; li=vlk-p->dut; printf("| %4d | %4d | %4d | %4d | %4d |",Gjectname +1,Gjectname +1,ei,l

12、i,li-ei); if(li=ei) printf(" 关键活动 |"); printf("n"); p=p->next ; return 1; void seekkeyroot() int projectnumber,activenumber,totaltime=0; vexnode* Graphicmap; system("cls"); printf("请输入这个工程的化成图形的节点数:"); scanf("%d",&projectnumber); printf("

13、请输入这个工程的活动个数:"); scanf("%d",&activenumber); Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode); CreateGraphic(Graphicmap,projectnumber,activenumber); SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); printf("整个工程所用的最短时间为：%d个单位时间n",totaltime); system(

14、"pause"); int main() char ch; int i; for(;) do system("cls"); printf("| 欢迎进入求关键路径算法程序 |"); for(i=0;i<80;i+)printf("*"); printf("%s","(S)tart开始输入工程的节点数据并求出关键路径n"); printf("%s","(E)xit退出n"); printf("%s","请输入选择:"); scanf("%c",&ch); ch=tou