没人理你……
我找不到简单的版本的……
只找到一个还算简单的……
#include
#include
#include
#include
#define MaxVerNum 50
#define OK 1
#define NULL 0
typedef int Status;
int visited[MaxVerNum];
typedef struct Arcnode{
int adjvex;
struct Arcnode *next;
int info;
}ArcNode;
typedef struct vnode{
char data;
ArcNode *firstedge;
}VNode;
typedef VNode AdjList[MaxVerNum];
typedef struct {
AdjList adjlist;
int vexnum,arcnum;
} ALGraph;
Status Visit(char e)//输出一个字母
{
printf("%2c",e);
return OK;
}
void Get(char *e)//输入一个字母
{
scanf("%c",e);
while(!('A' <= *e && *e<= 'Z')||('a' <= *e && *e <= 'z'))
scanf("%c",e);
}
void TGet(int *e)//输入一个数字
{
scanf("%d",e);
while(scanf("%d", e) <= 0)
{
getchar();
}
}
void InIt(ALGraph *G,int S[])//数组初始化
{
for(int i=0;ivexnum;i++)
S[i]=0;
}
void FindD(ALGraph *G,char arch,int *a)// 找到顶点的下标
{
int m;
for(m=0;mvexnum;m++)
{
if(arch == G->adjlist[m].data)
*a = m;
}
}
void Find(ALGraph *G,char arch,char arce,int *a,int *b)// 找到弧头和弧尾的下标
{
FindD(G,arch,a);
FindD(G,arce,b);
}
Status IsBe(ALGraph *G,char arch)// 判断顶点是否已存在
{
for(int m=0;mvexnum;m++)
{
if(arch == G->adjlist[m].data)
{
return OK;
}
}
return 0;
}//IsBe
Status AIsBe(ALGraph *G,int i,int j) //判断弧是否存在
{
ArcNode *s;
s = G->adjlist[i].firstedge;
while(s)
{
if(s->adjvex == j)
{
return OK;
}
s = s->next;
}
return 0;
}//AIsBe
Status GetIn(ALGraph *G,char arch,char arce) //得到弧的权值
{
int i,j;
ArcNode *s;
Find(G,arch,arce,&i,&j);
s = G->adjlist[i].firstedge;
while(s)
{
if(s->adjvex == j)
{
return (s->info);
}
s = s->next;
}
return 0;
}//AIsBe
void CreatALGraph(ALGraph *G)// 建立图的邻接表
{
int i,j,k,m;
char a,arch,arce;
ArcNode *s;
printf("请输入顶点数:");
scanf("%d",&G->vexnum);
printf("请输入弧的条数:");
scanf("%d",&G->arcnum);
printf("下面请输入图中的%d个顶点:\n",G->vexnum);
for(i=0;ivexnum;i++)
{
fflush(stdin);
printf("输入第%d个顶点:",i+1);
Get(&a);
if(!IsBe(G,a))
{
G->adjlist[i].data = a;
G->adjlist[i].firstedge = NULL;
}
else
{
printf("顶点%c已存在，请重新",a);
i--;
}
}
printf("下面请输入图中的%d条弧：\n",G->arcnum);
for(k=0;karcnum;k++)
{
fflush(stdin);
printf("输入第%d条弧:",k+1);
Get(&arch);Get(&arce);TGet(&m);
Find(G,arch,arce,&i,&j);
if(!AIsBe(G,i,j))
{
fflush(stdin);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = j;
s->info = m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge = s;
}
else
{
printf("弧%c,%c已存在，请重新",arch,arce);
k--;
}
}
printf("图的邻接表储存结构创建成功!\n");
}//CreatALGraph
void ACreateALGraph(FILE *fp,ALGraph *G)// 从文件读取图的邻接表
{
int i,j,k,m;
char a,arch,arce;
ArcNode *s;
fscanf(fp, "%d", &G->vexnum);
fscanf(fp, "%d", &G->arcnum);
for(i=0;ivexnum;i++)
{
fflush(stdin);
fscanf(fp, "%c", &a);
G->adjlist[i].data = a;
G->adjlist[i].firstedge = NULL;
}
for(k=0;karcnum;k++)
{
fscanf(fp, "%c", &arch);
fscanf(fp, "%c", &arce);
fscanf(fp, "%d", &m);
Find(G,arch,arce,&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = j;
s->info = m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge = s;
}
}//ACreateALGraph
void save(ALGraph *G)//保存文件
{
FILE *fp;
int i,j,k;
ArcNode *p;
// 打开文件
if((fp=fopen("AL.dat", "wb"))==NULL)
{
printf("数据文件打开失败，保存不成功，程序异常退出！\n");
exit(-1);
}
fprintf(fp, "%d", G->vexnum);
fprintf(fp, " ");
fprintf(fp, "%d", G->arcnum);
for(i=0;ivexnum;i++)
{
fprintf(fp, "%c", G->adjlist[i].data);
}
for(i=0;ivexnum;i++)
{
p = G->adjlist[i].firstedge;
while(p != NULL)
{
j = p->adjvex;
k = p->info;
fprintf(fp, "%c", G->adjlist[i].data);
fprintf(fp, "%c", G->adjlist[j].data);
fprintf(fp, "%d", k);
p = p->next ;
}
}
// 关闭文件
fclose(fp);
printf("图中的数据已经成功写入文件!\n");
}//save
void Traverse(ALGraph *G) //输出邻接表
{
int i,j,k;ArcNode *p;
for(i=0;ivexnum;i++)
{
printf("%2d|",i);
Visit(G->adjlist[i].data);
p = G->adjlist[i].firstedge;
while(p != NULL)
{
j = p->adjvex;
k = p->info;
printf(" ★-->%2d %2d",j,k);
p = p->next ;
}
printf(" △\n");
}
}//Traverse
void DFSM(ALGraph *G,int i)//深度优先遍历
{
ArcNode *p;
Visit(G->adjlist[i].data);
visited[i]=1;
p=G->adjlist[i].firstedge;
while(p)
{
if(! visited[p->adjvex])
DFSM(G,p->adjvex);
p = p->next;
}
}//DFSM
void DFSTraverse(ALGraph *G)
{
InIt(G,visited);
for(int j=0;jvexnum;j++)
if(!visited[0])
DFSM(G,0);
}//DFSTraverse
void BFSTraverse(ALGraph *G) //广度优先遍历
{
int k=0;
int i,f=0,r=0;
ArcNode *p;
int cq[MaxVerNum];
InIt(G,visited);
for(i=0;i<=G->vexnum;i++)
cq[i]=-1;
Visit(G->adjlist[k].data);
visited[k]=1;
cq[f]=k;
while(cq[r]!=-1)
{
i=cq[r];
r=r+1;
p=G->adjlist[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
Visit(G->adjlist[p->adjvex].data);
visited[p->adjvex]=1;
f=f+1; cq[f]=p->adjvex;
}
p=p->next;
}
}
} // BFSTraverse
Status InArc(ALGraph *G,int i,int j,int k) //插入一条弧
{
ArcNode *s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = j;
s->info = k;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge = s;
return OK;
}//InArc
Status InAr(ALGraph *G) //插入一条弧
{
int i,j,k;
char arch,arce;
printf("输入要增加的弧<弧尾，弧头，权值>:\n");
fflush(stdin);
Get(&arch);Get(&arce);TGet(&k);
Find(G,arch,arce,&i,&j);
if(!AIsBe(G,i,j))
{
InArc(G,i,j,k);
printf("弧%c,%c,%d添加成功!\n",arch,arce,k);
return OK;
}
else
{
k = GetIn(G,arch,arce);
printf("已存在弧%c,%c,%d，请重新",arch,arce,k);
InAr(G);
return OK;
}
}//InAr
Status DeArc(ALGraph *G,int i,int j) //删除一条弧
{
ArcNode *s,*ss;
ss = G->adjlist[i].firstedge;
if(ss->adjvex == j)
{
G->adjlist[i].firstedge = ss->next ;
free(ss);
return OK;
}
else
{
while(ss->next)
{
if(ss->next->adjvex != j)
{
ss = ss->next ;
}
else
{
s = ss->next ;
ss->next = s->next ;
free(s);
return OK;
}
}
}
return OK;
}//DeArc
Status DelArc(ALGraph *G)
{
int i,j,h;
char arch,arce;
fflush(stdin);
printf("输入要删除的弧<弧尾，弧头>:\n");
Get(&arch);Get(&arce);h = GetIn(G,arch,arce);
Find(G,arch,arce,&i,&j);
if(AIsBe(G,i,j))
{
DeArc(G,i,j);
printf("弧%c,%c,%d已被删除\n",arch,arce,h);
return OK;
}
else
{
printf("弧%c,%c不存在，请重新",arch,arce);
DelArc(G);
return 0;
}
}//DelArc
Status ModifyArc(ALGraph *G) //修改一条弧
{
int i,j,k,i2,j2,k2,m = 1;
char arch,arce,arch2,arce2;
ArcNode *s;
printf("输入要修改的弧<弧尾，弧头>:\n");
fflush(stdin);
Get(&arch);Get(&arce);k=GetIn(G,arch,arce);
Find(G,arch,arce,&i,&j);
if(AIsBe(G,i,j))
{
while(m)
{
printf("输入修改后的弧<弧尾，弧头，权值>:\n");
fflush(stdin);
Get(&arch2);Get(&arce2);TGet(&k2);
Find(G,arch2,arce2,&i2,&j2);
if(!AIsBe(G,i2,j2)||(i == i2&&j ==j2))
{
if(i != i2)
{
DeArc(G,i,j);
InArc(G,i2,j2,k2);
}
else
{
s = G->adjlist[i].firstedge;
while(s->adjvex != j)
{
s = s->next ;
}
s->adjvex = j2;
s->info = k2;
}
printf("已将弧%c,%c,%d修改为%c,%c,%d!\n",arch,arce,k,arch2,arce2,k2);
m = 0;
}
else
{
k2 = GetIn(G,arch,arce);
printf("已存在弧%c,%c,%d，请重新",arch2,arce2,k2);
}
}
return OK;
}
else
{
printf("弧%c,%c不存在，请重新",arch,arce);
ModifyArc(G);
return OK;
}
}//ModifyArc
Status InTop(ALGraph *G) //增加一个顶点
{
int i;char a;
printf("输入要添加的顶点:\n");
fflush(stdin);
Get(&a);
if(!IsBe(G,a))
{
i = G->vexnum++;
G->adjlist[i].data = a;
G->adjlist[i].firstedge = NULL;
printf("已成功将顶点%c加入图中!",a);
return OK;
}
else
{
printf("顶点%c已存在，请重新",a);
InTop(G);
return OK;
}
}//InTop
Status DeTop(ALGraph *G) //删除一个顶点
{
int i,m;char a;
ArcNode *s;
printf("输入要删除的顶点:\n");
fflush(stdin);
Get(&a);
if(IsBe(G,a))
{
FindD(G,a,&m);
for(i = 0;i < G->vexnum ;i++)
{
if(AIsBe(G,i,m))
DeArc(G,i,m);
}
for(i = m;i < (G->vexnum)-1 ;i++)
{
G->adjlist[i].data = G->adjlist[i+1].data;
G->adjlist[i].firstedge = G->adjlist[i+1].firstedge ;
}
G->vexnum--;
for(i = 0;i < G->vexnum ;i++)
{
s = G->adjlist[i].firstedge;
if(s != NULL)
while( s->next!= NULL)
{
if(s->adjvex >= m)
(s->adjvex)--;
s = s->next ;
}
}
printf("成功将顶点%c删除!",a);
return OK;
}
else
{
printf("顶点%c不存在，请重新",a);
DeTop(G);
return OK;
}
}//DeTop
Status ModifyTop(ALGraph *G)
{
int m;
char a,b;
printf("输入要修改的顶点：");
fflush(stdin);
Get(&a);
if(IsBe(G,a))
{
FindD(G,a,&m);
printf("请输入修改后的顶点：");
Get(&b);
while(IsBe(G,b))
{
printf("不能修改为已有顶点!请重新输入:");
Get(&b);
}
G->adjlist[m].data = b;
printf("已将顶点%c修改为%c",a,b);
return OK;
}
else
{
printf("顶点%c不存在，请重新",a);
ModifyTop(G);
}
return OK;
}//ModifyTop
Status Destroy(ALGraph *G)
{
for(int i=0;ivexnum;i++)
{
G->adjlist[i].data =0;
G->adjlist[i].firstedge =NULL;
}
G->arcnum = 0;
G->vexnum = 0;
return OK;
}//Destroy
void menu()
{
printf("\n");
printf("\t***********0233唐明邻接表****************\n");
printf("\t* 1 创建图的邻接表储存结构 *\n");
printf("\t* 2 读取图的邻接表储存结构 *\n");
printf("\t* 3 储存图的邻接表储存结构 *\n");
printf("\t* 4 输出邻接表数据 *\n");
printf("\t* 5 深度优先遍历图（DFS） *\n");
printf("\t* 6 广度优先遍历图（BFS） *\n");
printf("\t* 7 弧的修改 *\n");
printf("\t* 8 顶点的修改 *\n");
printf("\t* 9 销毁整个图 *\n");
printf("\t* 10 清 屏 *\n");
printf("\t* 0 退 出 程 序 *\n");
printf("\t*****************************************\n");
printf("\t请选择菜单项：");
}
int main()
{
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
FILE *fp;
int choice,choice2,choice3;
int is = 0;
while(1)
{
start:
menu();
fflush(stdin);
scanf("%d", &choice);
switch(choice)
{
case 1:
if(!is)
{
CreatALGraph(G);
is = 1;
}
else
{
printf("请先将图销毁，再创建新图");
}
break;
case 2:
if(!is)
{
fp = fopen("AL.dat", "r");
if(fp==NULL)
{
fp = fopen("AL.dat", "w+");
printf("尚未建立AL.dat，图创建失败！\n");
printf("现已建立AL.dat，请先存入数据！\n");
break;
}
ACreateALGraph(fp,G);
fclose(fp);
is = 1;
printf("图的邻接表储存结构创建成功!\n");
}
else
{
printf("请先将图销毁，再创建新图");
}
break;
case 3:
save(G);
break;
case 4:
if(is)
{
printf("邻接表中的数据如下：\n");
printf("下标 顶点 链表结点（弧头下标，弧的权值，指针）\n");
Traverse(G);
}
else
printf("尚未创建图，请先创建");
break;
case 5:
if(is)
{
printf("深度优先遍历如下\n");
DFSTraverse(G);
}
else
printf("尚未创建图，请先创建");
break;
case 6:
if(is)
{
printf("广度优先遍历如下\n");
BFSTraverse(G);
}
else
printf("尚未创建图，请先创建");
break;
case 7:
if(is){
printf("(1 增加 2 删除 3 修改)");
scanf("%d",&choice2);
switch(choice2)
{
case 1:
InAr(G);
goto start;break;
case 2:
DelArc(G);
goto start;break;
case 3:
ModifyArc(G);
goto start;break;
default: goto start;break;}
}
else
printf("尚未创建图，请先创建");
break;
case 8:
if(is){
printf("(1 增加 2 删除 3 修改)");
scanf("%d",&choice3);
switch(choice3)
{
case 1:
InTop(G);
goto start;break;
case 2:
DeTop(G);
goto start;break;
case 3:
ModifyTop(G);
goto start;break;
default: goto start;break;}
}
else
printf("尚未创建图，请先创建");
break;
case 9:
if(is)
{
Destroy(G);
is = 0;
printf("图已销毁!");
}
else
printf("尚未创建图，请先创建");
break;
case 10:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("\t您输入的菜单项不存在，请重新选择!\n");
}
}
return OK;
}
这是在我大一的草稿文件中找到的……完美的被我直接放U盘上，交了之后删了。不过你应该够用了，如果嫌功能多了……自己删吧，我记得我交上去的有十几项选项，几十条功能。你第一次运行，要么下我传上去的，要么你先输入图，再储存。因为没有AL.dat文件所以不能直接读取。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024