完整word版图的应用的实验报告.docx
- 文档编号:15748145
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:19
- 大小:32.77KB
完整word版图的应用的实验报告.docx
《完整word版图的应用的实验报告.docx》由会员分享,可在线阅读,更多相关《完整word版图的应用的实验报告.docx(19页珍藏版)》请在冰点文库上搜索。
完整word版图的应用的实验报告
实验六图的应用及其实现
一、实验目的1.进一步功固图常用的存储结构。
2.熟练掌握在图的邻接表实现图的基本操作。
3.理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。
二、实验内容
[题目一]:
从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列.试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。
测试数据:
教材图7.28
[题目二]:
从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。
试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。
测试数据:
教材图7.29
三、实验步骤
㈠、数据结构与核心算法的设计描述
基本数据结构:
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
#defineINFINITYINT_MAX//定义无穷大∞
#defineMAX_VERTEX_NUM20
typedefintVertexType;
typedefintInfoType;
typedefstructArcNode//表结点定义
{
InfoTypeinfo;
intadjvex;//邻接点域,存放与Vi邻接的点在表头数组中的位置
ArcNode*nextarc;//链域,指示依附于vi的下一条边或弧的结点,
}ArcNode;
typedefstructVNode//表头结点
{
intdata;//存放顶点信息
structArcNode*firstarc;//指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{//图的结构定义
顶点向量//vertices;AdjList
intvexnum,arcnum;
intIsquan;//是否含有权值
}MGraph;
typedefstruct
{
int*top;
int*base;
intstacksize;
}Sqstack;
typedefintElemType;
StatusInitstack(Sqstack&s)
{
s.base=(int*)malloc(sizeof(int)*25);
if(!
s.base)
returnERROR;
s.top=s.base;
s.stacksize=25;
returnOK;
}
intindegree[MAX_VERTEX_NUM];
intve[MAX_VERTEX_NUM];//e各顶点的最早发生时间
intvl[MAX_VERTEX_NUM];//各顶点发生的最晚发生时间
调用的函数
StatusInitstack(Sqstack&s)
StatusPop(Sqstack&s,int&e)
//若栈不空,则删除S的栈顶元素,
//用e返回其值,并返回OK;否则返回ERROR
intPush(Sqstack&s,int&e)
intStackEmpty(Sqstacks)//若栈为空栈,则返回TRUE,否则返回FLASE
StatusCreateGraph(MGraph&G)
voidDisplay(MGraph&G)/*输出图G的信息*/
voidFindDegree(MGraphg,intindegree[])//对=图中的各个顶点的入度进行统计,并将第i
//个顶点的入度数放入indegree[i]
intLocateVex(MGraphG,VertexTypeu)
/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
StatusToopologicalSort(MGraphg)//对图进行拓扑排序,并输出拓扑排序的结果
StatusToopologicalOrder(MGraphg,Sqstack&T)//拓扑序列
关键路径StatusCriticalPath(MGraphg,SqstackT)//可用函数的调用关系图说明)㈡、函数调用及主函数设计(.
voidmain()
{
MGraphg;
SqstackT;
函Main:
\n;潣瑵?
创建图
CreateGraph(g);
创建图:
\n;输出图的信息潣瑵?
Display(g);
:
\n;拓扑排序潣瑵?
求最小路径ToopologicalSort(g);输出图信息拓扑排序
\n;潣瑵?
求关键历经:
ToopologicalOrder(g,T);
CriticalPath(g,T);
}
程序调试及运行结果分析㈢)在创建图的过程中需要考虑输入的方便,这就需要标记根据用户选择是(1否需要输入权值,选择不需要权值时就不会有关权值信息的操作。
所以这就在图表示无权值,其他表示有权值)标记(的结构体中加ISquan0()函数调用过程就是一个对邻接表遍历的过程,在遍历FindIndegree
(2)『』数Indegree过程中需要将弧指向的结点进行入度数组的标记。
便定义了一个组。
,)在求关键路径时,需要两次用到拓扑排序(其中一次是逆拓扑排序)(3在拓扑排序时还需要注意看看是否有环,若有环则输出提示信息。
实验总结㈣
通过对拓扑排序和求最小路径的操作,首先加强了对图的存储结构和图的遍历的进一步的熟悉和应用,在拓扑排序中还让我们去应用到以前学习的栈的知识,温故的同时也在实践的新的理论。
对图的应用是在生活中应用很广泛,同时图的知识点和算法也是我们这学期学习的精华,例如求关键路径,用到栈,拓扑排序等经典算法,让我们受益匪浅。
四、主要算法流程图及程序清单、主要算法流程图:
1
创建图拓扑排序
开始
开
输入顶点数和边的压入将入度
输入顶点信为
创建顶点向量的数
弹出栈顶元素,输出结点信息并将其
接结点入度减一,入度的入
输入弧的信
创建了图的邻接表结束结束
2、程序清单程序过长,可附主要部分)
#include
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
#defineINFINITYINT_MAX//定义无穷大∞
#defineMAX_VERTEX_NUM20
typedefintVertexType;
typedefintInfoType;
typedefstructArcNode//表结点定义
{
InfoTypeinfo;
intadjvex;//邻接点域,存放与Vi邻接的点在表头数组中的位置
ArcNode*nextarc;//链域,指示依附于vi的下一条边或弧的结点,
}ArcNode;
typedefstructVNode//表头结点
{intdata;//存放顶点信息
structArcNode*firstarc;//指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{//图的结构定义
AdjListvertices;//顶点向量
intvexnum,arcnum;
intIsquan;//是否含有权值
}MGraph;
intindegree[MAX_VERTEX_NUM];
intve[MAX_VERTEX_NUM];//e各顶点的最早发生时间
intvl[MAX_VERTEX_NUM];//各顶点发生的最晚发生时间
/*图的邻接表存储(存储结构定义)的基本操作*/
intLocateVex(MGraphG,VertexTypeu)
{
/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for(i=0;i if(u==G.vertices[i].data) returni; return-1; }; StatusCreateGraph(MGraph&G) {inti,j,k; InfoTypevc; VertexTypeva,vb; ArcNode*p; 潣瑵? 请输入图的顶点数,边数: ; cin>>G.vexnum>>G.arcnum; 潣瑵? 请输入< \n; for(i=0;i { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } 潣瑵? 是否含有权值: (若不含权值请输入0,否则输入1)\n; cin>>G.Isquan; if(! G.Isquan) 潣瑵? 请顺序输入每条弧的弧尾弧头< else 潣瑵? 请顺序输入每条弧的弧尾弧头以及弧的信息(以空格作为间隔): \n; for(k=0;k { if(! G.Isquan) cin>>va>>vb; else cin>>va>>vb>>vc; i=LocateVex(G,va);/*弧尾*/ j=LocateVex(G,vb);/*弧头*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; if(G.Isquan) p->info=vc; else p->info=0; p->nextarc=G.vertices[i].firstarc;/*插在表头*/ G.vertices[i].firstarc=p; }returnOK; } voidDisplay(MGraph&G) {/*输出图G的信息*/ inti; ArcNode*p; 潣瑵? ? 敶湸浵? 尼个顶点: \n; for(i=0;i cout< cout< \n; for(i=0;i { p=G.vertices[i].firstarc; while(p) {cout< p=p->nextarc; } } //system(pause); } //////////////////////////////////////////////////////////////////// // //建立栈相关的数据结构和函数// typedefstruct { int*top; int*base; intstacksize; }Sqstack; typedefintElemType; StatusInitstack(Sqstack&s) {s.base=(int*)malloc(sizeof(int)*25); if(! s.base) returnERROR; s.top=s.base; s.stacksize=25; returnOK; } intPush(Sqstack&s,int&e) {//向栈输入元素 if(s.top-s.base>=s.stacksize) { s.base=(ElemType*)realloc(s.base,(s.stacksize+10)*sizeof(ElemType)); if(! s.base)return0; else {s.top=s.base+s.stacksize; s.stacksize+=10; } } *s.top=e; s.top++; returnOK; } StatusPop(Sqstack&s,int&e) { //若栈不空,则删除S的栈顶元素, //用e返回其值,并返回OK;否则返回ERROR if(s.top==s.base) returnERROR; e=*--s.top; returnOK; }//Pop; intStackEmpty(Sqstacks) { //若栈为空栈,则返回TRUE,否则返回FLASE if(s.top==s.base) return1; elsereturn0; } ///////////////////////////////////////////////////////////////////////////// voidFindDegree(MGraphg,intindegree[]) { //对=图中的各个顶点的入度进行统计,并将第i个顶点的入度数放入indegree[i] ArcNode*p; inti; for(i=0;i indegree[i]=0; 潣瑵? 李星运是个SB< for(intj=0;j for(p=g.vertices[j].firstarc;p! =NULL;p=p->nextarc) indegree[p->adjvex]++; } //对图进行拓扑排序,并输出拓扑排序的结果 StatusToopologicalSort(MGraphg) {Sqstacks; inti; intcount=0; FindDegree(g,indegree); Initstack(s); for(i=0;i if(indegree[i]==0) Push(s,i);//将入度为0的顶点序号压入零入度栈 while(! StackEmpty(s))//如果零入度栈中还有结点 {Pop(s,i); 潣瑵? 第? 椼? 结点<<\< count++; for(ArcNode*p=g.vertices[i].firstarc;p;p=p->nextarc) {intk=p->adjvex; if(! (--indegree[k])) Push(s,k); } } if(count { 潣瑵? 不是连通图! < returnERROR; } else returnOK; } //拓扑序列 StatusToopologicalOrder(MGraphg,Sqstack&T) { Sqstacks; inti; intcount=0; FindDegree(g,indegree); Initstack(s);//用于存放零入度的结点栈 Initstack(T);//若g不为空,则用T存放柘扑序列 for(i=0;i if(indegree[i]==0) Push(s,i); //初始化数组各结点的最早时间为0 for(i=0;i ve[i]=0; while(! StackEmpty(s)) { Pop(s,i);//将零入度结点栈中的结点弹出一个结点 Push(T,i);//将弹出的结点序列压入拓扑序列栈T中 count++; for(ArcNode*p=g.vertices[i].firstarc;p;p=p->nextarc) { intk=p->adjvex; if(! (--indegree[k])) Push(s,k);//将入度为0的结点压入零入度栈中 if(ve[i]+(p->info)>ve[k]) ve[k]=ve[i]+(p->info); } } if(count returnERROR; else returnOK; } //关键路径 StatusCriticalPath(MGraphg,SqstackT) { inti; ArcNode*p; if(! ToopologicalOrder(g,T)) { 潣瑵? 拓扑排序不成功! \n; returnERROR; } for(i=0;i vl[i]=ve[i];//将各顶点的最晚发生时间都赋值为最早发生时间 while(! StackEmpty(T)) for(Pop(T,i),p=g.vertices[i].firstarc;p;p=p->nextarc) { intk=p->adjvex; intdut=p->info; if(vl[k]-dut vl[i]=vl[k]-dut;//如果顶点的最晚时间大于前一个顶点的最晚时间和其间权值的差 } for(intj=0;j for(p=g.vertices[i].firstarc;p;p=p->nextarc) {intk=p->adjvex; intdut=p->info; intee=ve[j],el=vl[k]-dut; cout< } returnOK; } voidmain() { MGraphg; SqstackT; : \n; 创建图潣瑵? CreateGraph(g); 潣瑵? 各条弧的信息: \n; Display(g); 潣瑵? 拓扑排序: \n; ToopologicalSort(g); 潣瑵? 求关键历经: \n; ToopologicalOrder(g,T); CriticalPath(g,T); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 版图 应用 实验 报告