pipei.cpp

自己编的一个教师课程匹配程序

#include <iostream.h>  
#include <string.h>  
#include <iomanip.h>
#include <stdlib.h>
//#include <mathx.h>
#define MAXVEX 100  
struct vertex
{
//	public:
	int num;
	char data[20];

//	vertex();
	vertex& operator =(vertex &a)
   {
	   this->num=a.num;
	   strcpy(this->data,a.data);
	   return *this;
   }
	int operator ==(vertex &a)
   {
	   if(this->num==a.num&&strcmp(this->data,a.data))
		   return 1;
	   else return 0;
   }

//	vertex *firstarc;
};
typedef struct graph
{
	int n;
	int tn;//教师数
	int sn;//课程数
	int e;
	vertex vexs[MAXVEX];
	int edges[MAXVEX][MAXVEX];
}Adj;
typedef struct arc
{
	vertex start;
	vertex end;
	
	struct arc& operator=(struct arc &D)
	{
		this->start=D.start;
		this->end=D.end;
		return *this;
	}
	
	static int k;//边数

}Arc;
int arc::k=0;
typedef struct node
{
	vertex v;
	//vertex end;
	struct node *next;
}Node;


   struct arc M[MAXVEX],Temp[MAXVEX];//S[MAXVEX],T[MAXVEX],Q[MAXVEX],;
   int i,j,l,m,n,v;
   Adj& creat(Adj);
   void display(Adj);
   void display1(Adj);
   Arc* Initial_M(struct graph);
   void display_M(Arc *M);
   int pipei(Adj adj,Arc *M);
   bool Isfull(vertex v,Arc *M);
 //  bool Isfull(vertex v,int k,vertex z);
   Arc* InitialM(Adj adj);
   

void main()
{

	Adj  adj;
	adj=creat(adj);
	display(adj);
	display1(adj);
	InitialM(adj);
	display_M(M);
	bool x=Isfull(adj.vexs[0],M);
	cout<<"full:"<<x<<endl;
	pipei(adj,M);
	display_M(M);

}

Adj& creat(Adj adj)
{
	int i,j,flag;
	char course[20];
	
	adj.e=0;
	cout<<"教师数：";
	cin>>adj.tn;
	cout<<"课程数：";
	cin>>adj.sn;
	adj.n=adj.sn+adj.tn;
	for(i=0;i<adj.sn;i++)
	{
		cout<<" 第"<<i+1<<"门课程是：";
		cin>>adj.vexs[i].data;
		adj.vexs[i].num=i;
	}
	for(i=0;i<adj.n;i++)
		for(j=0;j<adj.n;j++)
			adj.edges[i][j]=0;
	for(i=adj.sn;i<adj.n;i++)
	{
		cout<<"第"<<i+1-adj.sn<<"个教师：";
		cin>>adj.vexs[i].data;
		adj.vexs[i].num=i;
		do{
			cout<<"教师能上的课程（输入0结束）：";
			cin>>course;
			flag=0;
			for(j=0;j<adj.sn;j++)
			{
				if(strcmp(course,adj.vexs[j].data)==0)
				{
					adj.edges[i][j]=1;
					adj.edges[j][i]=1;
					
					adj.e++;
					flag=1;
				}				
			}
			if(flag==0&&course[0]!='0')
				cout<<"没有这个课程."<<endl;
		}while(course[0]!='0');
	}
	return(adj);
}
void display(Adj adj)
{
	int i,j,n,e;
	n=adj.n;
	e=adj.e;
	cout<<"输出："<<endl;
	cout<<"   ";
	for(i=0;i<n;i++)
		cout<<setw(3)<<adj.vexs[i].data;
	cout<<endl;
	for(i=0;i<n;i++)
	{
		cout<<setw(3)<<adj.vexs[i].data;
		for(j=0;j<n;j++)
			if(adj.edges[i][j]==0)
			cout<<setw(3)<<adj.edges[i][j];
			else
			cout<<setw(3)<<adj.edges[i][j];
			cout<<endl;
	}
}

void display1(Adj adj)
{
	int i,j,n,e;
	n=adj.n;
	e=adj.e;
	cout<<"display:"<<endl;
	cout<<"  ";
	for(i=adj.sn;i<n;i++)
	{
		cout<<adj.vexs[i].data<<"老师能上的课程是：";
		for(j=0;j<adj.sn;j++)
			if(adj.edges[i][j]==1)
				cout<<" "<<":"<<adj.vexs[j].data;
		cout<<endl;
	}
}

   Arc* Initial_M(struct graph adj)//初始化匹配M
   {
	   int flag1=0;//标识顶点是否M——饱和
	   M->k=0;
	   //n=adj.n;
	   
	   for(i=0;i<adj.sn;i++)
			for(j=adj.sn;j<adj.n;j++)
			{
			 
			  if(adj.edges[i][j]==1)
			  {
				    for(v=0;v<M->k;v++)          //标识M——饱和的点
				      if(M[v].end==adj.vexs[j])
					  flag1=1;
			        if(flag1==1)
					{
						flag1=0;
						break;//如果饱和,继续找下一个结点.
					}
			        else         //否则,把这边当成是M中的一个匹配.
					{
					  M[M->k].start=adj.vexs[i];
					  M[M->k].end=adj.vexs[j];
					  M->k++;//匹配对数递增
					  //cout<<"M["<<M[k].start.data<<","<<M[k].end.data<<"]";
					}
			  }
			}
			return (M);
	}
   Arc* InitialM(Adj adj)
   {
	   M[0].start=adj.vexs[adj.sn];
	   for(i=0;i<adj.sn;i++)
		   if(adj.edges[adj.sn][i]==1)
		   {
			   M[0].end=adj.vexs[i];
	           M->k=1;
			   break;
		   }
	   return(M);
   }
   void display_M(Arc *M)
   {
	   cout<<"匹配M："<<endl;
	   for(i=0;i<M->k;i++)
	   //for(i=0;i<MAXVEX&&!(M[i].start.data==NULL);i++)
		   cout<<"["<<M[i].start.data<<","<<M[i].end.data<<"]"<<endl;
   }

bool Isfull(vertex v,Arc *M)
{
	for(i=0;i<M->k;i++)
	{
		cout<<i+1<<endl;
		if(v.data==M[i].start.data||v.data==M[i].start.data)
			return 1;
	}
	return 0;
}
/*bool Isfull(vertex v,int k,vertex z)
{
	for(i=0;i<k;i++)
		if(v==M[i].start)
		{
			z=M[i].end;
			return 1;
		}
	return 0;
}



void Isin(Node *&T,vertex v)
{
	Node *p=new Node;
	for(p=T->next;p->next!=NULL;p=p->next)
		if(p->v.num==v.num)
			return 1;*/


int pipei(Adj adj,Arc *M)

{
	int fullnum=0;
	cout<<"here"<<endl;//
	vertex y,z;
	Node *S=new Node,*T=new Node,*N=new Node;
	
	Node *p=new Node;
	Node *q=new Node;
	for(i=0;i<adj.sn;i++)//第一步,
	{
		cout<<"di yi"<<endl;//
		if(!Isfull(adj.vexs[i],M))//是否M--饱和
		{
			//bool x=Isfull(adj.vexs[i],M->k);
			//cout<<"full:"<<x<<endl;//
			p=S->next;             //p为S的第一个点
			p->v=adj.vexs[i];p->next=NULL;//S的第一个点M--不饱和
			T->next=NULL;           //T为空
			for(j=0;j<adj.n;j++)
				if(adj.edges[i][j]=1)
				{
					N->next->v=adj.vexs[j];//N表示与S中结点邻接的所有结点集合
					break;
				}
		}
		else fullnum++;
	    if(fullnum==adj.sn)
		{
			cout<<"完全匹配！"<<endl;
			return 1;
		}
	}
	cout<<"S:"<<S->next->v.data<<endl;
	bool b;
	do{
		cout<<"do"<<endl;
		for(p=N->next,q=T->next;(p->v==q->v)&&p->next!=NULL&&q->next!=NULL;p=p->next,q=q->next);
		if(p->v==q->v)
		{
			cout<<"不能完全匹配！"<<endl;
			return 0;
		}
		else 
			for(p=N->next;p->next!=NULL;p=p->next)
			{
				int flag2=0;
				for(q=T->next;q->next!=NULL;q=q->next)
					if(p->v==q->v)
					{
						flag2=1;
						break;
					}
				if(flag2==0)break;
			}
		    y=p->v;
			for(p=T->next;p->next!=NULL;p=p->next);
				p->next->v=y;
			if(b=Isfull(y,M))
			{
				for(p=S->next;p->next!=NULL;p=p->next);
				for(i=0;i<M->k;i++)
	            if(y==M[i].start)
				z=M[i].end;
				p->next->v=z;	
			}
	}while(b);
	if(!b)
	{
		int flag3,l=0,flag4;
		for(i=0;i<M->k;i++)
		{   flag3=0;
		    flag4=0;
			for(p=S->next,q=T->next;p->next!=NULL;p=p->next,q=q->next)
			{
				if(M[i].start==p->v)
					flag3=1;
				if(M[i].end==q->v)
					flag4=1;
			}
			if(flag3==1&&flag4==1)continue;
			else  Temp[l++]=M[i];
		}
		for(p=S->next,q=T->next;p->next!=NULL;p=p->next,q=q->next)
		{
			flag3=0;
			flag4=0;
			for(i=0;i<M->k;i++)
			{
				if(M[i].start==p->v)
					flag3=1;
				if(M[i].end==q->v)
					flag4=1;
			}
			if(flag3==1&&flag4==1)continue;
			else  Temp[l++]=M[i];
		}
		for(i=0;!(i>M->k)&&!(i>l);i++)
			M[i]=Temp[i];
		display_M(M);
		pipei(adj,M);
	}
	return 1;
}