//第二题
#include <stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
typedef enum {DG} GraphKind; //有向图
typedef struct ArcNode{
int adjvex; //该弧头的位置
struct ArcNode *nextarc; //下一条出弧
int info; //附加信息
}ArcNode; //弧结点
typedef char VertexType ;
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *firstarc; //第一条出弧
}VNode, AdjList[MAX_VERTEX_NUM]; //邻接表头指针向量
typedef struct {
AdjList vertices; //邻接表头指针向量
int vexnum,arcnum; //顶点数目和弧的数目
GraphKind kind; //图的种类
}ALGraph;
//返回顶点u在图中的位置,未找到返回-1
int LocateVex(ALGraph G,VertexType u)
{ int i;
for(i = 0; i < G.vexnum; i++)
if(G.vertices[i].data == u) return i;
return -1;
}
//创建有向图
void CreateDG(ALGraph &G)
{ int i,j,k,info;
char c;
VertexType v1,v2;
ArcNode * p;
printf("\n下面分步输入创建有向图的信息:"); G.kind = DG;
printf("\n1.请输入图的顶点个数:"); scanf("%d", &G.vexnum);
printf("\n2.请输入图的弧的个数:"); scanf("%d", &G.arcnum);
printf("\n3.请连续输入%d个顶点(字符型):",G.vexnum);
scanf("%c",&c); //滤掉换行字符
for(k = 0; k < G.vexnum; k++) //邻接表头指针向量初始化
{ scanf("%c", &G.vertices[k].data);
G.vertices[k].firstarc = NULL;
}
for(k = 0; k < G.arcnum; k++) //建立弧结点<v,w>
{ printf("\n建立弧%d,请输入弧的信息,格式为v w info:",k+1);
scanf("%c",&c); //滤掉换行字符
scanf("%c %c %d", &v1, &v2, &info);
i = LocateVex(G,v1); j = LocateVex(G,v2); //确定v1,v2在图中的位置
if(i == -1 || j == -1)
{ printf("\n输入弧信息非法,程序退出!"); break; }
p = (ArcNode *) malloc( sizeof(ArcNode) );
p->adjvex = j;
p->info = info;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
}
//按邻接表的形式输出有向图
void PrintDG(ALGraph G)
{ ArcNode *p;
printf("\n有向图G的邻接表形式:");
for(int i = 0; i < G.vexnum; i++)
{ printf("\n %c",G.vertices[i].data);
if( G.vertices[i].firstarc )
{ printf("-->");
for(p = G.vertices[i].firstarc; p; p = p->nextarc)
{ printf("%c",G.vertices[p->adjvex].data);
if(p->nextarc) printf("-->");
}
}
}
printf("\n");
}
//在邻接表表示的有向图G上插入顶点v
int InsertVex(ALGraph &G,VertexType v)
{
for(int i = 0; i < G.vexnum; i++)
if(G.vertices[i].data == v)
{ printf("该顶点已存在,拒绝插入!");
return ERROR;
}
G.vertices[G.vexnum].data = v;
G.vertices[G.vexnum].firstarc = NULL;
G.vexnum++;
return OK;
}
//在邻接表表示的有向图G上插入弧(v,w)
int InsertArc(ALGraph &G,VertexType v,VertexType w,int info)
{ ArcNode * p;
int i,j;
i = LocateVex(G,v); j = LocateVex(G,w); //确定v1,v2在图中的位置
if(i == -1 || j == -1 || i == j) { printf("\n输入弧的顶点信息非法,拒绝插入!");
return ERROR; }
for(p = G.vertices[i].firstarc; p; p = p->nextarc)
if(p->adjvex == j){ printf("该弧已存在,拒绝插入!");return ERROR; }
p = (ArcNode * )malloc( sizeof(ArcNode) );
p->adjvex = j;
p->info = info;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
G.arcnum++;
return OK;
}
//在邻接表表示的有向图G上删除一个顶点v
int DeleteVex(ALGraph &G,VertexType v)
{ ArcNode *p, *q;
int DelNo,k;
DelNo = LocateVex(G,v); //确定v在图中的位置
if(DelNo == -1 ) { printf("\n输入顶点信息非法,拒绝删除!"); return ERROR; }
for(p = G.vertices[DelNo].firstarc; p; ) //删除出弧<DelNo, >
{ q = p->nextarc; free(p); p = q;}
G.vertices[DelNo].firstarc = NULL;
for(k = 0; k < G.vexnum; k++)
{ if(!G.vertices[k].firstarc) continue;
for(p = G.vertices[k].firstarc; p; q = p,p = p->nextarc) //寻找入弧<k,i>
if(p->adjvex == DelNo) //找到
if(p == G.vertices[k].firstarc)
{ G.vertices[k].firstarc = p->nextarc; free(p);break;}
else
{ q->nextarc = p->nextarc; free(p); break;}
}
G.vertices[DelNo] = G.vertices[G.vexnum-1];//把待删除顶点DelNo和最后一个顶点G.vexnum-1进行交换
for(k = 0; k < G.vexnum - 1; k++) //把邻接表中adj的G.vexnum-1内容修改为DelNo
{ if(!G.vertices[k].firstarc) continue;
for(p = G.vertices[k].firstarc; p; p = p->nextarc) //寻找入弧<k,G.vexnum-1>
if(p->adjvex == G.vexnum-1) //找到
{ p->adjvex = DelNo; break;}
}
G.vexnum--;
//G.arcnum处理
return OK;
}
//在邻接表表示的有向图G上删除弧(v,w)
int DeleteArc(ALGraph &G,VertexType v,VertexType w)
{ ArcNode *p, *q;
int i,j,arcnum;
i = LocateVex(G,v); j = LocateVex(G,w); //确定v1,v2在图中的位置
if(i == -1 || j == -1) { printf("\n输入弧的顶点信息非法,拒绝删除!"); return ERROR; }
arcnum = G.arcnum;
for(p = G.vertices[i].firstarc; p; q = p,p = p->nextarc) //寻找入弧<k,i>
if(p->adjvex == j) //找到
if(p == G.vertices[i].firstarc) //如果删除的是第一条弧
{ G.vertices[i].firstarc = p->nextarc; free(p); G.arcnum--; break;}
else
{ q->nextarc = p->nextarc; free(p); G.arcnum--; break;}
if(G.arcnum == arcnum)
{ printf("\n输入的弧不存在,拒绝删除!"); return ERROR; }
return OK;
}
void main()
{ VertexType v,w;
int info,QuitId = 0;
ALGraph G;
CreateDG(G);
PrintDG(G);
while(!QuitId)
{ int choice;
printf("操作菜单:\n");
printf("1. 插入一条弧\n");
printf("2. 插入一个顶点\n");
printf("3. 删除一条弧\n");
printf("4. 删除一个顶点\n");
printf("5. 打印有向图G\n");
printf("0. 退出\n");
printf("请输入你的选择:");
scanf("%d",&choice);
switch (choice)
{ case 1:
printf("\n插入一条弧,请输入弧的信息,格式为v,w,info:");
scanf("%c",&v); //滤掉换行字符
scanf("%c %c %d", &v, &w, &info);
if(InsertArc(G,v,w,info) == OK) PrintDG(G);
break;
case 2:
printf("\n请输入要插入的顶点信息(字符型):");
scanf("%c",&v); //滤掉换行字符
scanf("%c", &v);
if(InsertVex(G,v) == OK) PrintDG(G);
break;
case 3:
printf("\n请输入要删除的弧的信息,格式为v,w:");
scanf("%c",&v); //滤掉换行字符
scanf("%c,%c", &v, &w);
if(DeleteArc(G,v,w) == OK) PrintDG(G);
break;
case 4:
printf("\n请输入要删除的顶点信息(字符型):");
scanf("%c",&v); //滤掉换行字符
scanf("%c", &v);
if(DeleteVex(G,v) == OK) PrintDG(G);
break;
case 5:
PrintDG(G);
break;
case 0:
QuitId = 1;
break;
default:;
}
printf("\n");
}
}
评论0