picture.cpp

有向图的插入

#include<iostream>
using namespace std;
# define M 100
# define inf 100
void print(int a)
{
	switch(a) {
	case 1:cout<<"a ";
		break;
	case 2:cout<<"b ";
		break;
	case 3:cout<<"c ";
		break;
	case 4:cout<<"d ";
		break;
	case 5:cout<<"e ";
		break;
	case 6:cout<<"f ";
		break;
	case 7:cout<<"g ";
		break;
	default:break;
	}
}
int char2num(char x)
{
	switch(x)
	{
		case 'a':return 1;
			break;
		case 'b':return 2;
			break;
		case 'c':return 3;
			break;
		case 'd':return 4;
			break;
		case 'e':return 5;
			break;
		case 'f':return 6;
			break;
		case 'g':return 7;
			break;
		case '@':case '#':return 8;
			break;
		default:cout<<"输入错误!"<<endl;return 0;	
	}
}
int push(int  *p,int x,int top)
{
	if(top==M-1)printf("overflow");	//如栈满提示错误信息
	else	{
		top++;					//调整栈顶指针
		*(p+top)=x;	    		//元素x进栈
	}
	return(top);
}
int pop(int  *p,int *x,int top)
{
	if(top<0)printf("overflow");	//如栈空提示错误信息
	else	{
		*x=*(p+top);    		    //出栈
		top--;	                //调整栈顶指针
	}
	return(top);
}
void DFS(int array[9][9])
{
	int i,j=1,k,stack[M],top=-1;
	bool is=true;
	for(k=1;k<=7;k++)
	{
		i=k;
		print(i);
		 array[i][i]=23;
		top=push(stack,i,top);
		while (j<=7) 
		{
			if ((array[i][j]>=0)&&(array[i][j]<inf)&&(array[j][j]==0)) //判断是否满足连接且未被打印的条件
			{
				print(j);
				array[j][j]=23;//标记 入栈
				top=push(stack,i,top);
				i=j;
				
				j=0;
			}
			j++;
			if(j>7)
			{
				if (top==-1) 
				{
					break;
				}
				top=pop(stack,&i,top);//出栈
				j=1;
			}
		}
		for(int q=1;q<=7;q++)//检验是否所有的节点都已经打印完毕
		{
			if(array[q][q]==0)
			{
				is=false;
				break;
			}
		}
		if (is) {
			break;
		}
	}
}
int queue_in(int front,int *rear,int *Q,int x)
{
	if(((*rear + 1) % M)==front)return(-1);		// 队列上溢错误
	Q[*rear]=x;
	*rear=(*rear+1) % M;			//rear指向当前队中最末一个元素后的空单元
	return(0);
}
int queue_out(int *front,int rear,int *Q,int *x)
{
	if(rear==*front)return(-1); // 队列下溢错误
	*x=Q[*front];
	Q[*front]=0;				//清除为零
	*front=(*front + 1) % M;	//front指向当前队头元素的位置
	return(0);
}
void LFS(int array[9][9])
{
	int i,j=1,k,Q[M],front=0,rear=0;
	bool is=true;
	for(k=1;k<=7;k++)
	{
		i=k;
		print(i);
		array[i][i]=23;
		queue_in(front,&rear,Q,i);
		while (j<=7) 
		{
			if ((array[i][j]>=0)&&(array[i][j]<inf)&&(array[j][j]==0)) 
			{
				print(j);
				array[j][j]=23;
				queue_in(front,&rear,Q,j);
			}
			j++;
			if(j>7)
			{
				if (queue_out(&front,rear,Q,&i)==-1) 
				{
					break;
				}
		
				j=1;
			}
		}
		for(int q=1;q<=7;q++)
		{
			if(array[q][q]==0)
			{
				is=false;
				break;
			}
		}
		if (is) {
			break;
		}
	}
}
void IN(int array[9][9])//输入函数
{
	for(int i=1;i<=7;i++)
	{
		for(int j=1;j<=7;j++)
		{
			 array[i][j]=inf;
		}
	}
	
	char x,y;
	int X,Y;
	do {
		cout<<"请输入相连的两条边,以@、#结束"<<endl;
		cin>>x;
		cout<<"—>";
		cin>>y;
		cout<<endl;
		X=char2num(x);
		Y=char2num(y);
		array[X][Y]=1;
		array[X][X]=array[Y][Y]=0;
	} while((X!=8)&&(Y!=8));

}
int main()
{	
	int array[9][9],array2 [9][9];
	int w=0;
	do {
		cout<<"请输入您的选择:"<<endl;
		cout<<"1、使用系统自带的图"<<endl;
		cout<<"2、自己输入图结构(节点不多于7个)"<<endl;
		cin>>w;
		switch(w) {
		case 1:
			{
			
				for(int i=1;i<=7;i++)
				   {
					   for(int j=1;j<=7;j++)
					   {
						   if (i==j) {
							   array[i][j]=0;
						   }
						   else array[i][j]=inf;
					   }
				   }
				array[1][2]=array[1][4]=array[1][5]=array[1][6]=1;
				array[2][3]=1;
				array[3][6]=1;
				array[4][3]=1;
				array[5][7]=1;
				array[7][3]=array[7][6]=1;
				break;
			}
		case 2:
			{
			
				IN(array);
				break;
			}
		default:
			cout<<"输入错误，请重新输入"<<endl;
			w=4;
			break;
		}
		
	} while(w==4);
	for(int i=1;i<=7;i++)
		 for(int j=1;j<=7;j++)
			 array2[i][j]=array[i][j];
		
			
	
	cout<<"深度优先遍历结果为:"<<endl;
	DFS(array);
	cout<<endl;
	cout<<"宽度优先遍历结果为:"<<endl;
	LFS(array2);
	cout<<endl;
	return 0;
}