数据结构B上机实验四图.docx
- 文档编号:10480321
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:31
- 大小:101.90KB
数据结构B上机实验四图.docx
《数据结构B上机实验四图.docx》由会员分享,可在线阅读,更多相关《数据结构B上机实验四图.docx(31页珍藏版)》请在冰点文库上搜索。
数据结构B上机实验四图
数据结构上机实验六
实验内容:
图的基本操作
实验要求:
1)图的遍历与基本操作要作为函数被调用.
2)把自己使用的图结构明确的表达出来.
3)基本上实现每个实验题目的要求.
分组要求:
可单独完成,也可两人一组。
实验目的:
1)熟悉C/C++基本编程,培养动手能力.
2)通过实验,加深对图的理解.
评分标准:
1)只完成第一和第二题,根据情况得4,5分;
2)完成前3题,根据情况得5,6分;
3)在2)基础上,选做四)中题目,根据情况得7到10分。
题目:
一)建立一个无向图+遍历+插入
(1)以数组表示法作为存储结构,从键盘依次输入顶点数、弧数与各弧信息建立一个无向图;
(2)对
(1)中生成的无向图进行广度优先遍历并打印结果;
(3)向
(1)中生成的无向图插入一条新弧并打印结果;
二)建立一个有向图+遍历+插入+删除
(1)以邻接表作为图的存储结构,从键盘输入图的顶点与弧的信息建立一个有向图;
(2)对
(1)中生成的有向图进行深度优先遍历并打印结果;
(3)在
(1)中生成的有向图中,分别插入与删除一条弧并打印其结果;
(4)在
(1)中生成的有向图中,分别插入与删除一个顶点并打印结果;
(5)在
(1)中生成的有向图中,各顶点的入度与出度并打印结果;
三)基本应用题
(1)编写算法,判断图中指定的两个顶点是否连通。
(2)编写算法,判断图的连通性。
如果不连通,求连通分量的个数
(3)编写算法,判断图中任意两个顶点的连通性
(4)编写算法,判断图中是否存在回路。
(5)实现图的广度优先搜索算法。
四)高级应用题
(1)实现Prim算法
(2)实现Kruskal算法
(3)实现迪杰斯特拉算法
(4)实现拓扑排序算法
(5)实现关键路径算法
#include
#include
#include
//……………………宏定义……………………
#defineint_max1000
#defineintf999
#definemax20
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineStatusint
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
//……………………标志矩阵定义……………………
intvisited[max];//访问标记
intparent[max];
intindegree[max];//入度
intoutdegree[max];//初度
intve[max];
intfinal[max];
intwe;
//…………邻接矩阵定义………………………
typedefstructArcCell
{
intadj;//权值
char*info;//相关信息
}ArcCell,AdjMatrix[20][20];
typedefstruct
{
charvexs[20];//顶点向量
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图当前顶点数和弧数
}MGraph_L;
//……………邻接链表表示……………………
typedefstructArcNode//弧结点
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
int*info;//该弧相关信息的指针
}ArcNode;
typedefstructvnode//邻接链表顶点头接点
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}vnode,adjlist;
typedefstruct//图的定义
{
adjlistvertices[max];
intvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
//…………………………队列定义……………………
typedefstructQnode
{
intdata;//队列数据
structQnode*next;//队列指针
}Qnode,*Queueptr;
typedefstruct
{
Queueptrfront;//队首指针
Queueptrrear;//队尾指针
}Linkqueue;
//……………………………堆栈定义……………………
typedefstructStack
{
int*base;//栈底指针
int*top;//栈顶指针
Statusstacksize;
}SqStack;
//…………………………………最小生成树……………………
typedefstruct{
charadjvex;//顶点信息
intlowcost;//权值
}minside[max];
//…………………………队列基本操作……………………
StatusInitqueue(Linkqueue&q)//初始化队列
{
q.rear=(Queueptr)malloc(sizeof(Qnode));
q.front=q.rear;
if(!
q.front)
return0;
q.front->next=NULL;
return1;
}
StatusEnqueue(Linkqueue&q,inte)//入队
{
Queueptrp;
p=(Queueptr)malloc(sizeof(Qnode));
if(!
p)return0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return1;
}
StatusDequeue(Linkqueue&q,int&e)//出队
{
Queueptrp;
if(q.front==q.rear)return0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)q.rear=q.front;
free(p);
return1;
}
StatusQueueempty(Linkqueueq)//判断队为空
{
if(q.front==q.rear)
return1;
return0;
}
//……………………………堆栈基本操作……………………
StatusCreatStack(SqStack&S)//创建空栈
{
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(structStack));
if(!
S.base)return0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}
StatusPush(SqStack&S,inte)//元素入栈
{
if(S.top-S.base>=S.stacksize)//栈满,追加存储空间
{
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(structStack));
if(!
S.base)return0;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return1;
}
StatusPop(SqStack&S,inte)//出栈元素
{
if(S.top==S.base)return0;
e=*--S.top;
returne;
}
//……………………………数组表示图函数…………………
intLocateVex(MGraph_LG,charv)//查找顶点v的序号
{
inti;
for(i=0;i if(v==G.vexs[i]) returni; return-1; } intcreateMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示 { charv1,v2; inti,j,w; printf("--------------创建无向图--------------\n"); printf("请输入无向图G的顶点数和弧数: "); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i { printf("输入顶点%d\n",i); fflush(stdin); scanf("%c",&G.vexs[i]); } for(i=0;i for(j=0;j { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } printf("输入一条边依附的顶点和权: \n"); for(intk=0;k! =G.arcnum;++k) { fflush(stdin); scanf("%c%c%d",&v1,&v2,&w);//输入一条边依附的两点及权值 i=LocateVex(G,v1);//确定顶点V1和V2在图中的位置 j=LocateVex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } printf("图G邻接矩阵创建成功! \n"); returnG.vexnum; } voidMGraph_Lprint(MGraph_LG)//打印邻接矩阵 { inti,j; for(i=0;i! =G.vexnum;++i) { for(j=0;j! =G.vexnum;++j) { if(G.arcs[i][j].adj! =1000)printf("%d",G.arcs[i][j].adj); else{printf("∞");} } printf("\n"); } } intFirstAdjVex(MGraph_LG,charv)//顶点V的第一个连接向量 { inti,j=1000,k; k=LocateVex(G,v);//k为顶点v在图G中的序号 for(i=0;i if(G.arcs[k][i].adj! =j) returni; return-1; } intNextAdjVex(MGraph_LG,charv,charw)//顶点V的下一个连接向量 { inti,j=1000,k1,k2; k1=LocateVex(G,v);//k1为顶点v在图G中的序号 k2=LocateVex(G,w);//k2为顶点w在图G中的序号 for(i=k2+1;i if(G.arcs[k1][i].adj! =j) returni; return-1; } voidInsertvex(MGraph_L&G,charv1,charv2,intw)//在两个顶点间插入弧 { inti,j; i=LocateVex(G,v1);//确定顶点V1和V2在图中的位置 j=LocateVex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } //……………………………无向图的应用……………………… voidConnected(MGraph_LG,charv1,charv2,int&flag)//判断任意两个顶点是否连接 { intk1,k2; charw; k1=LocateVex(G,v1);//k1为顶点v在图G中的序号 k2=LocateVex(G,v2);//k2为顶点w在图G中的序号 if(k1<0||k2<0){printf("不存在这样的两个顶点\n");} else { if(k1==k2)flag=1; elseif(flag! =1)flag=-1; visited[k1]=TRUE; for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,G.vexs[w])) if(! visited[w])Connected(G,G.vexs[w],v2,flag); } } intDfs(MGraph_LG,inti)//深度遍历无向图 { visited[i]=1; intwe1; printf("%c",G.vexs[i]); for(we=FirstAdjVex(G,G.vexs[i]);we>=0;we=NextAdjVex(G,G.vexs[i],G.vexs[we])) { we1=we; if(visited[we]==0) Dfs(G,we); we=we1; } return0; } intDfstra(MGraph_LG) { inti,j,num=0; for(i=0;i! =G.vexnum;++i) {visited[i]=0;} for(j=0;j! =G.vexnum;++j) { if(visited[j]==0) {Dfs(G,j);num++;} } returnnum; } intFindCycle(MGraph_LG,charv0)//判断图是否有回路 { intk1; k1=LocateVex(G,v0); visited[k1]=TRUE; for(we=FirstAdjVex(G,v0);we>=0;we=NextAdjVex(G,v0,G.vexs[we])) { if(! visited[we]) { parent[we]=k1; returnFindCycle(G,G.vexs[we]); } elseif(we! =parent[k1])returnTRUE; } returnFALSE; } //……………………………无向图的高级应用……………………… intminimum(minsideSZ,MGraph_LG) { inti=0,j,k,min; while(! SZ[i].lowcost)i++; min=SZ[i].lowcost;/*将最小权值记在min中*/ k=i;/*把与边关联的生成树外的顶点序号记在k中*/ for(j=i+1;j if(SZ[j].lowcost>0&&min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } returnk; } voidMiniSpanTree_PRIM(MGraph_LG,charu)//Prim最小生成树 { inti,j,k; minsideclosedge; k=LocateVex(G,u); for(j=0;j { closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j].adj; } closedge[k].lowcost=0;/*将顶点vk加入生成树中*/ printf("最小代价生成树的各条边为: \n"); for(i=1;i { k=minimum(closedge,G); printf("(%c-%c)\n",closedge[k].adjvex,G.vexs[k]);/*输出最小边及权值*/ closedge[k].lowcost=0; for(j=0;j if(G.arcs[k][j].adj { closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j].adj; } } } //……………………………有向图的链表表示……………………… intlocateVex(ALGraphG,charu)//查找顶点v的序号 { inti; for(i=0;i if(u==G.vertices[i].data) returni; return-1; } intCreateUDG(ALGraph&G1)//用邻接表存储图 { inti,j,k; intw; charva=NULL,vb=NULL; ArcNode*p; printf("请输入图的顶点数,弧数: "); scanf("%d%d",&G1.vexnum,&G1.arcnum); for(i=0;i { printf("输入顶点%d\n",i); fflush(stdin); scanf("%c",&G1.vertices[i].data); G1.vertices[i].firstarc=NULL; } printf("请顺序输入每条弧边的弧头,弧尾和权值: \n"); for(k=0;k { fflush(stdin); scanf("%c%c%d",&va,&vb,&w);//输入一条边依附的两点及权值); i=locateVex(G1,va);//弧头 j=locateVex(G1,vb);//弧尾 p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=(int*)malloc(sizeof(int)); *(p->info)=w; p->nextarc=G1.vertices[i].firstarc;//插在表头 G1.vertices[i].firstarc=p; } printf("图G1邻接链表创建成功! \n"); returnG1.vexnum; } voidUDGprint(ALGraphgra)//打印指向 { inti; for(i=0;i! =gra.vexnum;++i) { ArcNode*p; printf("顶点%d指向的点的位置: \n",i); p=gra.vertices[i].firstarc; while(p! =NULL) { printf("%d",p->adjvex); p=p->nextarc;} printf("\n"); } } intfirstAdjVex(ALGraphG,charv)//顶点V的第一个连接向量 { ArcNode*p; intv1; v1=locateVex(G,v);//v1为顶点v在图G中的序号 p=G.vertices[v1].firstarc; if(p) returnp->adjvex; else return-1; } intnextAdjVex(ALGraphG,charv,intw)//顶点V的第二个连接向量 { ArcNode*p; intv1,w1; v1=locateVex(G,v);//v1为顶点v在图G中的序号 w1=locateVex(G,w);//w1为顶点w在图G中的序号 p=G.vertices[v1].firstarc; while(p&&p->adjvex! =w1)p=p->nextarc; if(! p||! p->nextarc)//没找到w或w是最后一个邻接点 return-1; else//p->adjvex==w returnp->nextarc->adjvex; } voidinsertVex(ALGraph&G,charv)//插入一个顶点 { G.vertices[G.vexnum].data=v;//构造新顶点向量 G.vertices[G.vexnum].firstarc=NULL; G.vexnum++;//图G的顶点数加1 } voiddeletevex(ALGraph&G,charv)//删除一个顶点 { inti,j; ArcNode*p,*q; j=locateVex(G,v); if(j<0)printf("没有该顶点! \n"); p=G.vertices[j].firstarc;//删除以v为出度的弧或边 while(p) { q=p; p=p->nextarc; free(q->info); free(q); G.arcnum--;//弧或边数减1 } G.vexnum--;//顶点数减1 for(i=j;i G.vertices[i]=G.vertices[i+1]; for(i=0;i { p=G.vertices[i].firstarc;//指向第1条弧或边 while(p)//有弧 { if(p->adjvex==j) { if(p==G.vertices[i].firstarc)//待删结点是第1个结点 {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 上机 实验