第6次-图的应用实验-实验题目与报告书

1、精选优质文档-倾情为你奉上淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 实验六：图的应用实验 求关键路径及其应用 班 级： 网络072 学 号： 姓 名： 田静 评语：成绩： 指导教师： 朱敏 批阅时间：2008 年11 月 17 日专心-专注-专业图的应用实验报告要求1目的与要求:1）掌握AOE网的邻接表存储结构表示及创建算法的c语言实现；2）理解AOE网的拓扑排序算法(算法7.12)的实现原理及应用；3）掌握AOE网关键路径的计算算法（算法7.13，7.14）及C语言实现与应用；4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写

2、实验报告,并按时提交。2 实验内容或题目题目： 图的应用实验计算AOE网的关键路径内容：按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图1所示AOE网的关键路径。图1 AOE网876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=43 实验步骤与源程序#define INFINITY 32768 #define True 1#define False 0#define Error -1#define NULL 0#define Ok 1#define MAX_VERTEX_NUM 9 typedef enumDG

3、, DN, UDG, UDN GraphKind; typedef int VertexData;typedef struct ARCNNODEint adjvex; int weight; struct ARCNNODE *nextarc; typedef struct VERTEXNODEVertexData data; ArcNode *firstarc; VertexNode;typedef struct VertexNode vertexMAX_VERTEX_NUM; int vexnum,arcnum; GraphKind kind; AdjList; #include "

4、;AdjList.h"#include "STACK.h"#include <stdio.h>int veMAX_VERTEX_NUM; int VN9=3,1,1,1,2,1,1,1,0;int AN112=1,6, 2,4, 3,5, 4,1, 4,1, 5,2, 6,9, 7,7, 7,4, 8,2, 8,4;CreateAdjList(AdjList *G)int i,j;int arc=0;ArcNode *arcn,*pre;G->vexnum=9;for( i=0;i<G->vexnum;i+) G->vertex

5、i.data=i; G->vertexi.firstarc=NULL; if(VNi>0) arcn=(ArcNode*)malloc(sizeof(ArcNode); arcn->nextarc=NULL; arcn->adjvex=ANarc0; arcn->weight=ANarc1; G->vertexi.firstarc=arcn; pre=arcn; arc+; for(j=1;j<VNi;j+) arcn=(ArcNode*)malloc(sizeof(ArcNode); arcn->nextarc=NULL; arcn->a

6、djvex=ANarc0; arcn->weight=ANarc1; pre->nextarc=arcn; pre=arcn; arc+; printAdjList(AdjList *G)int i,j;int arc=0;ArcNode *arcn;printf("vexnum is %d: ",G->vexnum);for( i=0;i<G->vexnum;i+) printf("vertex%d's data is :%dn",i,G->vertexi.data); arcn=G->vertexi.

7、firstarc; while(arcn!=NULL) printf("%d->%d,weight:%d ",i,arcn->adjvex,arcn->weight); arcn=arcn->nextarc; printf("n");void FindID(AdjList G,int indegreeMAX_VERTEX_NUM) int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; for(i=0;i<G.vexnum;i+) p=G.vertexi.first

8、arc; while(p!=NULL) indegreep->adjvex+; p=p->nextarc; /* for */int TopoOrder(AdjList G,Stack *T) int count,i,j,k; ArcNode *p;int indegreeMAX_VERTEX_NUM; Stack S; InitStack(T); InitStack(&S); FindID(G,indegree); for(i=0;i<G.vexnum;i+) if(indegreei=0) Push(&S,i); count=0; for(i=0;i<

9、;G.vexnum;i+) vei=0; while(!IsEmpty(&S)Pop(&S,&j);Push(T,j);count+;p=G.vertexj.firstarc;while(p!=NULL) k=p->adjvex;if(-indegreek=0) Push(&S,k); if(vej+p->weight>vek) vek=vej+p->weight; p=p->nextarc; if(count<G.vexnum) return(Error); elsereturn(Ok);int CriticalPath(A

10、djList G) ArcNode *p; int i,j,k,dut,ei,li; char tag;int vlMAX_VERTEX_NUM; Stack T;if(!TopoOrder(G,&T) return(Error); for(i=0;i<G.vexnum;i+) vli=veG.vexnum-1; while(!IsEmpty(&T) Pop(&T,&j); p=G.vertexj.firstarc; while(p!=NULL) k=p->adjvex; dut=p->weight; if(vlk-dut<vlj) vl

11、j=vlk-dut; p=p->nextarc;for(j=0;j<G.vexnum;j+) p=G.vertexj.firstarc; while(p!=NULL) k=p->adjvex; dut=p->weight; ei=vej;li=vlk-dut; tag=(ei=li)?'*':' 'printf("%d,%d,%d,%d,%d,%cn",G.vertexj.data,G.vertexk.data,dut,ei,li,tag); p=p->nextarc; return(Ok); int main(

12、)AdjList G; CreateAdjList(&G);printAdjList(&G); CriticalPath(G);return 0;#include <malloc.h>#define OVERFLOW -1#define OK 0#define ERROR 1#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 1000#define STACKINCREMENT 10typedef int SElemType;typedef int Status;typedef struct STACK SEle

13、mType *base; SElemType *top; int stacksize;Stack;typedef struct STACK SqStack;typedef struct STACK *pSqStack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack *S);int StackLength(SqStack *S);SElemType GetTop(SqStack *S);Status Push(S

14、qStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status InitStack(SqStack *S) S->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S->base) return(OVERFLOW); S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK;Status DestroyStack(SqStack *S) free(S->bas

15、e); return OK;Status ClearStack(SqStack *S) S->top=S->base; return OK;Status IsEmpty(SqStack *S) if(S->top=S->base) return TRUE; else return FALSE;int StackLength(SqStack *S) int i; SElemType *p; i=0; p=S->top; while(p!=S->base) p+; i+; return i;SElemType GetTop(SqStack *S) if(S-&g

16、t;top=S->base) return ERROR; return *(S->top-1);Status Push(SqStack *S,SElemType e) *(S->top+)=e; return OK;Status Pop(SqStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*(-(S->top); return OK;4 测试数据与实验结果（可以抓图粘贴）5 结果分析与实验体会在对图遍历时，对于连通图，无论是广度优先还是深度优先搜索，仅需要调用一次搜索过程，即从任一顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连同分量中的顶点集。在图的应用问题中，常常需要找从一个顶点到另一个顶点的简单