#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
char data[2]; //顶点就设置和书上V1等等一样吧
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct
{
int data[MAX_VERTEX_NUM+10];
int front;
int rear;
}queue;
int visited[MAX_VERTEX_NUM];
queue q;
int main()
{
ALGraph G;
int CreateUDG(ALGraph &G);
int DeleteUDG(ALGraph &G);
int InsertUDG(ALGraph &G);
void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v));
int PrintElement(ALGraph G,ArcNode v);
void menu();
void depthfirstsearch(ALGraph *g,int vi);
void travel(ALGraph *g);
void breadfirstsearch(ALGraph *g);
int i;
G.arcnum = G.vexnum = 0;
while(1)
{
menu();
do
{
printf ( "请输入要进行的操作\n" );
scanf ("%d",&i);
if (i<1||i>6)
printf("错误数字，请重新输入\n");
}while (i<1||i>6);
switch (i)
{
case 1: CreateUDG(G); system("pause"); system("cls"); break;
case 2: DeleteUDG(G); system("pause"); system("cls"); break;
case 3: InsertUDG(G); system("pause"); system("cls"); break;
case 4: travel(&G); system("pause"); system("cls"); break;
case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;
case 6: exit(0); break;
}
}
return 1;
}
void enterqueue(int v)
{
q.data[q.rear]=v;
q.rear++;
}
int deletequeue()
{
int t;
t=q.data[q.front];
q.front++;
return(t);
}
int empty()
{
if(q.front==q.rear)
return 1;
return 0;
}
int LocateVex(ALGraph G,char node[2])
{
int i;
for(i = 0 ; i < G.vexnum ; i++)
{
if(strcmp(G.vertices[i].data,node)==0)
return i;
}
return -1;
}
int CreateUDG(ALGraph &G)
{
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
int i,j,k;
char node1[2],node2[2];
ArcNode *p,*q;
printf("请输入顶点数和弧数\n");
printf("例如:5,6\n");
scanf("%d,%d",&G.vexnum,&G.arcnum);
printf("请输入各顶点\n");
for(i = 0 ; i < G.vexnum ; i++)
{
printf("第%d个\n",i+1);
scanf("%s",&G.vertices[i]);
G.vertices[i].firstarc = NULL;
}
//这里开始构造边
printf("请输入边的信息\n");
printf("例如:v1 v2\n");
for(i = 0 ; i < G.arcnum ; i++)
{
printf("第%d条边\n",i+1);
scanf("%s %s",&node1,&node2);
j = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = j;
p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
int DeleteUDG(ALGraph &G)
{
int i,j;
ArcNode *p,*q;
char node[2];
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入要删除的节点\n");
scanf("%s",&node);
i = LocateVex(G,node);
if(i == -1)
{
printf("无此节点\n");
return 0;
}
else
{
G.vexnum--;
if((p = q = G.vertices[i].firstarc) != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
while(p != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
}
}
for(j = 0 ; j < G.vexnum ; j++ )
{
if(j >= i)
{
strcpy(G.vertices[j].data , G.vertices[j+1].data);
G.vertices[j].firstarc = G.vertices[j+1].firstarc;
}
if(G.vertices[j].firstarc->nextarc != NULL)
{
p = G.vertices[j].firstarc;
q = p->nextarc;
if(p->adjvex == i)
{
G.vertices[j].firstarc = q;
p = q;
q = q->nextarc;
continue;
}
else if(p->adjvex > i)
p->adjvex--;
while(q != NULL)
{
if(q->adjvex == i)
{
p->nextarc = q->nextarc;
free(q);
q = p->nextarc;
}
else if(q->adjvex > i)
q->adjvex--;
else
{
p = p->nextarc;
q = q->nextarc;
}
}
}
else if( (G.vertices[j].firstarc->nextarc == NULL) && (G.vertices[j].firstarc != NULL) )
if( G.vertices[j].firstarc->adjvex == i )
{
G.vertices[j].firstarc = NULL;
}
}
}
PrintUDG(G);
return 1;
}
int InsertUDG(ALGraph &G)
{
//默认一次插入一个节点吧,不然太麻烦
int i,j,k,l;
char node1[2],node2[2];
ArcNode *p,*q;
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入插入节点的名称\n");
printf("WARNING:绝不可以和之前的节点重名!\n");
scanf("%s",&G.vertices[G.vexnum].data);
G.vertices[G.vexnum].firstarc = NULL;
printf("请输入需要插入的边的数目\n");
scanf("%d",&i);
G.arcnum += i;
G.vexnum++;
printf("请输入边的信息\n");
printf("例如:v6 v2\n");
printf("WARNING:一定要包含刚加入的节点名称!\n");
for(j = 0 ; j < i ; j++)
{
printf("第%d条边\n",j+1);
scanf("%s %s",&node1,&node2);
l = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = l;
p->nextarc = G.vertices[l].firstarc;
G.vertices[l].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
void depthfirstsearch(ALGraph *g,int vi)
{
ArcNode *rear;
printf("%s\t",g->vertices[vi].data);
visited[vi]=1;
rear=g->vertices[vi].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex]))
{
depthfirstsearch(g,rear->adjvex);
rear=rear->nextarc;
}
}
void travel(ALGraph *g)
{
int v;
for(v=0;v<g->vexnum;v++)
if(!visited[v])
depthfirstsearch(g,v);
}
void breadfirstsearch(ALGraph *g)
{
int v,t,i;
ArcNode *rear;
for(i = 0 ; i <g->vexnum ; i++)
visited[i] = 0;
for(v=0;v<g->vexnum;v++)
{
if(!visited[v])
{
printf("%s",g->vertices[v].data);
visited[v]=1;
enterqueue(v);
}
while(!empty())
{
t=deletequeue();
rear=g->vertices[t].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex]))
{
printf("%s\t",g->vertices[rear->adjvex].data);
visited[rear->adjvex]=1;
enterqueue(rear->adjvex);
rear=rear->nextarc;
}
}
}
}
void menu()
{
printf("*********************************************\n");
printf("* 作者：Dick *\n");
printf("* 信计1001 xxxxxxxxxx *\n");
printf("*********************MENU********************\n");
printf("1 建立无向图\n");
printf("2 删除图中节点\n");
printf("3 插入节点\n");
printf("4 深度优先遍历图\n");
printf("5 广度优先遍历图\n");
printf("6 退出程序\n");
}
void PrintUDG(ALGraph G)
{
int i;
ArcNode *p;
for(i = 0 ; i < G.vexnum ; i++)
{
if(G.vertices[i].firstarc != NULL)
{
printf("与节点%s相邻的节点为:\n",G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p != NULL)
{
printf("%s\t",G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
else
printf("无与节点%s相邻的节点\n",G.vertices[i].data);
}
}
评论0