实验报告六.docx
- 文档编号:6692592
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:29
- 大小:134.48KB
实验报告六.docx
《实验报告六.docx》由会员分享,可在线阅读,更多相关《实验报告六.docx(29页珍藏版)》请在冰点文库上搜索。
实验报告六
实验编号:
6四川师大《数据结构》实验报告2015年12月28日
计算机科学学院2014级4班实验名称:
实验六:
图及其应用
姓名:
张俊学号:
2014110454指导老师:
_廖雪花_实验成绩:
_____
实验六图及其应用
一.实验目的及要求
(1)通过完成本实验,掌握图的两种基本的存储结构(邻接矩阵、邻接表),以及图的基本算法实现(建立、遍历),并能运用图结构分析解决一些实际问题。
(2)本实验训练的要点是:
图的两种基本存储结构,及各种操作的算法实现(建立、遍历、图的典型应用)。
二.实验内容
(1)建立无向图和有向图的邻接矩阵存储,计算顶点的度,并输出图的基本信息。
(2)建立有向图的邻接表存储表示,并根据存储计算顶点的出度和入度,然后输出图的基本信息。
(3)编写完整的程序实现AOV网的拓扑排序。
(4)编程求AOE网的关键路径。
(5)编程实现单源点最短路径的Dijkstra算法。
注:
(1)~
(2)必做,(3)~(5)选做。
三.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)
(1)建立无向图和有向图的邻接矩阵存储,计算顶点的度,并输出图的基本信息。
Ø程序代码部分:
//main.cpp
#include
#include
#include"c.h"
intmain()
{
MGraphG;
Creat_MGraph(G);
TD_MGraphnum(G);
system("pause");
return0;
}
//b.cpp
#include
#include
#include"c.h"
StatusCreat_MGraph(MGraph&G)
{
inti,j;
intkind;
printf("1-建立有向图\n");
printf("2-建立无向图\n");
scanf_s("%d",&kind);
if(kind==1)
{
G.kind=1;
}
elseif(kind==2)
{
G.kind=0;
}
else
{
printf("输入错误,请重新输入\n");
while(kind!
=1||kind!
=2)
{
scanf_s("%d",&kind);
}
}
printf("请输入顶点数\n");
scanf_s("%d",&G.vexnum);
printf("请输入%d个字母顶点,不要输入空格隔开\n",G.vexnum);
scanf_s("%d",&G.vexnum);
for(i=0;i { scanf_s("%c",&G.vexs[i]); } printf("请输入0或1表示是否相邻,以空格隔开(默认自身到自身不可达)\n"); for(i=0;i { for(j=0;j { scanf_s("%d",&G.arcs[i][j].adj); } } printf("创建成功\n"); returnOK; } StatusTD_MGraphnum(MGraphG)//度数 { inti,j,k; intv1,v2; if(G.kind==0)//无向图 { for(i=0;i { k=0; for(j=0;j { if(G.arcs[i][j].adj==1) { k++; } } printf("第%d个顶点即%c的度为: %d\n",i+1,G.vexs[i],k); } } elseif(G.kind==1)//有向图 { for(i=0;i { v1=v2=0; for(j=0;j { if(G.arcs[i][j].adj==1) { v1++; } if(G.arcs[j][i].adj==1) { v2++; } } printf("第%d个顶点即%c的出度为: %d;入度为%d\n",i+1,G.vexs[i],v1,v2); } } returnOK; } //c.h #ifndefc_h #definec_h #defineOK1 #defineERROR0 #defineOVERFLOW-1 #defineMAX_VERTEX_NUM20//最大顶点数 typedefintStatus; typedefcharVertexType; typedefintVRType; typedefintGraphKind; /* 邻接矩阵定义 */ typedefstructArcCell{ VRTypeadj;//用1和0表示是否相邻 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { VertexTypevexs[MAX_VERTEX_NUM];//顶点一位数组 AdjMatrixarcs;//邻接矩阵二维数组 intvexnum;//顶点数 intarcnum;//弧的条数 GraphKindkind;//弧的类型 }MGraph; //邻接矩阵 StatusCreat_MGraph(MGraph&G);//用邻接矩阵构造有向图或无向图 StatusTD_MGraphnum(MGraphG);//度数 #endif Ø运行结果: (2)建立有向图的邻接表存储表示,并根据存储计算顶点的出度和入度,然后输出图的基本信息。 Ø程序代码部分: //main.cpp #include #include #include"c.h" intmain() { ALGraphA; Creat_ALGraph(A); Toposort(A); TD_ALGraphnum(A); system("pause"); return0; } //a.cpp #include #include #include"c.h" StatusCreat_ALGraph(ALGraph&A)//用邻接表构造有向图或无向图 { inti,j,kind; charc; ArcNode*q,*p; printf("1-建立有向图2-建立无向图\n"); scanf_s("%d",&kind); if(kind==1) { A.kind=1; } elseif(kind==2) { A.kind=0; } else { printf("输入错误,请重新输入\n"); while(kind! =1||kind! =2) { scanf_s("%d",&kind); } } printf("请输入顶点数\n"); scanf_s("%d",&A.vexnum); printf("请输入%d个顶点(不以空格隔开)\n",A.vexnum); scanf_s("%d",&A.vexnum); for(i=0;i { scanf_s("%c",&A.vertices[i].data); } for(j=0;j { printf("请输入第%d个字母顶点即%c指向的第一个结点,以#表示空\n",j+1,A.vertices[j].data); getchar(); scanf_s("%c",&c); p=(ArcNode*)malloc(sizeof(ArcNode)); if(c! ='#') { p->adjvex=c; p->nextarc=NULL; A.vertices[i].firstarc=p; printf("请继续输入第%d个顶点后面的结点,以#表示结束\n",j+1); getchar(); scanf_s("%c",&c); q=(ArcNode*)malloc(sizeof(ArcNode)); p=A.vertices[i].firstarc; while(c! ='#') { q=(ArcNode*)malloc(sizeof(ArcNode)); q->adjvex=c; q->nextarc=NULL; p->nextarc=q; p=p->nextarc; scanf_s("%c",&c); } p->nextarc=NULL; } else { A.vertices[i].firstarc=NULL; } } returnOK; } StatusTD_ALGraphnum(ALGraphA) { inti,j,k; intv1[100],v2[200]; ArcNode*p; if(A.kind==0)//无向图 { for(i=0;i { k=0; //for(k=0,p=A.vertices[i].firstarc;p;p=p->nextarc,k++); p=A.vertices[i].firstarc; while(p->nextarc! =NULL) { k++; p=p->nextarc; } printf("第%d个顶点即%c的度为%d\n",i+1,A.vertices[i].data,k); } } elseif(A.kind==1)//有向图 { for(i=0;i { v1[i]=0; if(A.vertices[i].firstarc==NULL) { v1[i]=0; } else { v1[i]=1; p=A.vertices[i].firstarc; while(p->nextarc! =NULL) { v1[i]++; p=p->nextarc; } } } for(i=0;i { v2[i]=0; } for(i=0;i { if(A.vertices[i].firstarc! =NULL) { for(j=0;j { if(A.vertices[i].firstarc->adjvex==A.vertices[i].data) { v2[j]++; } } } } for(i=0;i { p=A.vertices[i].firstarc; if(p) { while(p->nextarc) { for(j=0;j { if(A.vertices[i].data==p->nextarc->adjvex) { v2[j]++; } } p=p->nextarc; } } } for(i=0;i { printf("第%d个顶点即%c的出度是%d,入度是%d\n",i+1,A.vertices[i].data,v1[i],v2[i]); } } returnOK; } voidToposort(ALGraphA)//邻接表实现 { inti,j,k; inttop,m=0; ArcNode*p; int*d;//建栈用于存储入度为0的顶点 d=(int*)malloc((A.vexnum)*sizeof(int)); for(i=0;i { d[i]=0; } //利用数组d中的对应元素统计出每个顶点的入度 for(i=0;i { p=A.vertices[i].firstarc; while(p! =NULL) { j=p->adjvex; d[j]++; p=p->nextarc; } } //初始化用于链接入度为0的元素的栈的栈顶指针为-1 top=-1; //建立初始化栈 for(i=0;i { if(d[i]==0) { d[i]=top; top=i; } } //每循环一次删除一个顶点及所有出边 while(top! =-1) { j=top;//j值为一个入度为0的顶点序号 top=d[top];//删除栈顶元素 printf("%d",j);//输出一个顶点 m++;//输出顶点个数加1 p=A.vertices[j].firstarc;//p指向Vj邻接表的第一个结点 while(p! =NULL) { k=p->adjvex;//Vk是Vj的一个临接点 d[k]--;//Vk的入度减1 if(d[k]==0)//将入度为0的元素入栈 { d[k]=top; top=k; } p=p->nextarc;//p指向邻接表中下一个结点 } } printf("\n"); if(m { printf("有回路\n"); } } //c.h #ifndefc_h #definec_h #defineOK1 #defineERROR0 #defineOVERFLOW-1 #defineMAX_VERTEX_NUM20//最大顶点数 typedefintStatus; typedefcharVertexType; typedefintVRType; typedefintGraphKind; /* 邻接表定义 */ typedefstructArcNode{ VertexTypeadjvex;//该弧所指向的顶点的位置 structArcNode*nextarc;//指向下一条弧的指针 }ArcNode; typedefstructc{ VertexTypedata;//顶点信息 ArcNode*firstarc;//指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdjListvertices;//顶点一维数组 intvexnum;//顶点数 intarcnum;//弧的条数 GraphKindkind;//弧的类型 }ALGraph; //邻接表 StatusCreat_ALGraph(ALGraph&A);//用邻接表构造有向图或无向图 StatusTD_ALGraphnum(ALGraphA); voidToposort(ALGraphA);//邻接表实现 #endif (3)编写完整的程序实现AOV网的拓扑排序。 Ø代码: //main.cpp #include #include #include"c.h" voidmain() { printf("——拓扑排序: TOPOSOR算法——\n"); vexnodedig[n];//顶点表数组 creatgraph(dig); inti; edgenode*s; printf("【输出AOV网的邻接表】\n"); for(i=0;i { printf("|%c%d|",dig[i].vertex,dig[i].id); s=dig[i].link; while(s) { printf("——>%d",s->adjvex); s=s->next; } printf("\n"); } printf("【输出拓扑序列】\n"); toposort(dig); printf("\n"); system("pause"); } voidcreatgraph(vexnodedig[])//建立有向网络的邻接表 { inti;//循环变量 charch;//记录顶点元素 intin;//记录每次的入度 inta,b;//记录边的始点与终点 edgenode*newnode; printf("【输入顶点元素及入度(顶点元素与入度之间用空格隔开)】\n"); for(i=0;i { printf("第%d个顶点的元素及入度: ",i+1); cin>>ch>>in; dig[i].vertex=ch; dig[i].id=in; dig[i].link=NULL; } printf("【输入有向边的始点与终点(中间用空格隔开)】\n"); for(i=0;i { printf("第%d条边的始点与终点: ",i+1); cin>>a>>b; newnode=(edgenode*)malloc(sizeof(edgenode)); newnode->adjvex=b; newnode->next=dig[a-1].link; dig[a-1].link=newnode; } } voidtoposort(vexnodedig[])//AOE网的邻接表 { inti,j,k,m=0,top=-1;//m为输出顶点个数计数器,top为栈指针 edgenode*p; for(i=0;i { if(dig[i].id==0) { dig[i].id=top; top=i; } } while(top! =-1)//栈非空 { j=top; top=dig[top].id;//第j+1个顶点退栈 printf("%c\t",dig[j].vertex);//输出退栈顶点 m++;//为输出顶点计数 p=dig[j].link;//p指向v(j+1)的出边表结点的指针 while(p)//删去所有以v(j+1)为起点的出边 { k=p->adjvex-1;//k为边(v(j+1),v(k+1))的终点v(k+1)在dig中的下标 dig[k].id--;//v(k+1)入度减1 if(dig[k].id==0)//将新入度为0的顶点入栈 { dig[k].id=top; top=k; } p=p->next;//找v(j+1)的下一条边 } } if(m printf("\nAOV网有回路\n"); }//toposprt //c.h #include #include usingnamespacestd; #definen6//顶点个数 #definee8//边的条数 typedefintdatatype; typedefcharvextype; typedefstructnode { intadjvex;//邻接点域 structnode*next;//链域 }edgenode;//边表结点 typedefstruct { vextypevertex;//顶点信息 intid;//入度 edgenode*link;//边表头指针 }vexnode;//顶点表结点 voidcreatgraph(vexnodedig[]);//建立有向网络的邻接表 voidtoposort(vexnodedig[]);//AOE网的邻接表 Ø运行截图: (4)编程求AOE网的关键路径。 Ø代码: //main.cpp #include #include"c.h" #include usingnamespacestd; voidmain() { printf("——AOE网的关键路径——\n"); vexnode1dig[n]; creatgraph(dig); printf("【输出AOE网的邻接表】\n"); inti; edgenode1*s; for(i=0;i { printf("|%c%d|",dig[i].vertex,dig[i].id); s=dig[i].link; while(s) { printf("——>%d%d",s->adjvex+1,s->dut); s=s->next; } printf("\n"); } printf("【输出关键活动】\n"); printf("每行分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量\n"); criticalpath(dig); system("pause"); } //a.cpp #i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告