tu.cpp

键盘输入数据

#define M 20 
#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
/*定义图*/ 
typedef struct{ 
int V[M]; 
int R[M][M]; 
int vexnum; 
}Graph; 
typedef struct ArcBox{
 int tail,head;
    struct ArcBox *headlink;
 struct ArcBox *taillink;
}ArcBox;//定义链元素
typedef struct VexNode{
 int data;
 ArcBox *firstin;
 ArcBox *firstout;
}VexNode;//定义接点元素
typedef struct {
 VexNode xlist[M];//表向量
    int vexnum,arcnum;
}OlGraph;
/*创建图*/ 
void creatgraph(Graph *g,int n) 
{ 
	int i,j,r1,r2; 
	g->vexnum=n; 
	/*顶点用i表示*/ 
	for(i=1;i<=n;i++) 
	{ 
		g->V[i]=i; 
	} 
/*初始化R*/ 
	for(i=1;i<=n;i++) 
	for(j=1;j<=n;j++) 
	{ 
		g->R[i][j]=0; 
	} 
/*输入R*/ 
	printf("Please input R(0,0 END):\n"); 
	scanf("%d,%d",&r1,&r2); 
	while(r1!=0&&r2!=0) 
	{ 
		g->R[r1][r2]=1; 
		g->R[r2][r1]=1; 
		scanf("%d,%d",&r1,&r2); 
	} 
} 



/*打印图的邻接矩阵*/ 
void printgraph(Graph *g) 
{ 
	int i,j; 
	for(i=1;i<=g->vexnum;i++) 
	{ 
		for(j=1;j<=g->vexnum;j++) 
		{ 
			printf("%2d ",g->R[i][j]); 
		} 
		printf("\n"); 
	} 
} 
/*全局变量：访问标志数组*/ 
int visited[M]; 
/*访问顶点*/ 
void visitvex(Graph *g,int vex) 
{ 
	printf("%d ",g->V[vex]); 
} 



/*获取第一个未被访问的邻接节点*/ 
int firstadjvex(Graph *g,int vex) 
{ 
	int w,i; 
	for(i=1;i<=g->vexnum;i++) 
	{ 
		if(g->R[vex][i]==1&&visited[i]==0) 
		{ 
			w=i; 
			break; 
		} 
		else 
		{ 
			w=0; 
		} 
	} 
	return w; 
} 
/*获取下一个未被访问的邻接节点(深度遍历)*/ 
int nextadjvex(Graph *g,int vex,int w) 
{ 
	int t; 
	t=firstadjvex(g,w); 
	return t; 
} 
/*深度递归遍历*/ 
void dfs(Graph *g,int vex) 
{ 
	int w; 
	visited[vex]=1; 
	visitvex(g,vex); 
	for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) 
	if(!visited[w]) 
	{ 
		dfs(g,w); 
	} 
} 



void dfstraverse(Graph *g) 
{ 
	int i; 
	for(i=1;i<=g->vexnum;i++) 
	visited[i]=0; 
	for(i=1;i<=g->vexnum;i++) 
	if(!visited[i]) 
	{dfs(g,i);} 
} 
/*定义队列*/ 
typedef struct{ 
int V[M]; 
int front; 
int rear; 
}Queue; 
/*初始化队列*/ 
void initqueue(Queue *q) 
{ 
	q->front=0; 
	q->rear=0; 
} 
/*判断队列是否为空*/ 
int quempty(Queue *q) 
{ 
	if(q->front==q->rear) 
	{ 
		return 0; 
	} 
	else 
	{ 
		return 1; 
	} 
} 
/*入队操作*/ 
enqueue(Queue *q,int e) 
{ 
	if((q->rear+1)%M==q->front) 
	{ 
		printf("The queue is overflow!\n"); 
		return 0; 
	} 
	else 
	{ 
		q->V[q->rear]=e; 
		q->rear=(q->rear+1)%M; 
		return 1; 
	} 
} 
/*出队操作*/ 
dequeue(Queue *q) 
{ 
	int t; 
	if(q->front==q->rear) 
	{ 
		printf("The queue is empty!\n"); 
		return 0; 
	} 
	else 
	{ 
		t=q->V[q->front]; 
		q->front=(q->front+1)%M; 
		return t; 
		} 
} 
/*广度遍历*/ 
void BESTraverse(Graph *g) 
{ 
	int i; 
	Queue *q=(Queue *)malloc(sizeof(Queue)); 
	for(i=1;i<=g->vexnum;i++) 
	{ 
		visited[i]=0; 
	} 
	initqueue(q); 
	for(i=1;i<=g->vexnum;i++) 
	{ 
		if(!visited[i]) 
		{ 
			visited[i]=1; 
			visitvex(g,g->V[i]); 
			enqueue(q,g->V[i]); 
			while(!quempty(q)) 
			{ 
				int u,w; 
				u=dequeue(q); 
				for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w)) 
				{ 
					if(!visited[w]) 
					{ 
						visited[w]=1; 
						visitvex(g,w); 
						enqueue(q,w); 
					} 
				} 
			} 
		} 
	} 
} 

void Create_Graph(OlGraph& GL)//创建用十字链表存放的图.
{  int vexnum,arcnum;
   scanf("%d,%d",&vexnum,&arcnum);//输入图中的节点和边条数
   GL.vexnum=vexnum;
   GL.arcnum=arcnum;
   for(int i=0;i<M;i++)
   {GL.xlist[i].firstin=NULL;
   GL.xlist[i].firstout=NULL;}
   for(i=0;i<GL.vexnum;i++)
   {   printf("%d:",i);
    scanf("%d",&GL.xlist[i].data);
   }
    printf("input the head and tail num:\n");
  for(i=1;i<=GL.arcnum;i++)//插入新的链边
  {
     ArcBox *p=(ArcBox*)malloc(sizeof(ArcBox));
     scanf("%d,%d",&(p->head),&(p->tail));
     p->headlink=GL.xlist[p->tail].firstin;
  p->taillink=GL.xlist[p->head].firstout;
  GL.xlist[p->tail].firstin=GL.xlist[p->head].firstout=p;
  }
}

/*主程序*/ 
void main() 
{ 
	int n; 
	char menu; 
	int choose;
	OlGraph GL;
	Graph *g=(Graph *)malloc(sizeof(Graph)); 
	for(;;)
	{
		printf("*****************************************************************\n");
		printf("请选择想要的操作:\n");
		printf("1.键盘输入数据，建立一个有向图的邻接表。\n");
		printf("2.输出该邻接表。\n");
		printf("3.建立一个有向图的十字链表。\n");
		printf("4.采用邻接表存储实现无向图的深度优先遍历。\n");
		printf("5.采用邻接表存储实现无向图的广度优先遍历。\n");
		printf("0.退出\n");
		printf("******************************************************************\n");
		scanf("%d",&choose);
		getchar();
		if(choose!=0)
		{
			switch(choose)
			{
			case 1:{
						printf("请输入图顶点数:\n"); 
						scanf("%d",&n); 
						creatgraph(g,n); 
				   }break;
			case 2:	{
						printf("该邻接矩阵表为:\n"); 
						printgraph(g); 
					}break;
			case 3:{					
						Create_Graph(GL);
				   }break;
			case 4:{
						printf("Depth_first:\n"); 
						dfstraverse(g); 
						printf("\n"); 
				   }break;
			case 5:{
						printf("Breadth_first:\n"); 
						BESTraverse(g); 
						printf("\n"); 
				   }break;
			default:printf("输入错误，请重新输入\n");break;
			}
		}
		else break;
	}
}