tu.cpp

/* 实现一个图类

#include "TU.h"

//初始化图，并建立一个顶点
TU::TU(void)

{
	 
      vnum=0;
         PNODE p;PLINK l;
		p=new NODE;l=new LINK;
     	p->next=NULL;
		l->next=NULL;
		p->link=l;
	
      top=p;


}

TU::~TU(void)
{
	PLINK m,n;
			PNODE s;
			while (top!=NULL)
			{
              s=top->next;
				m=top->link;
				while (m!=NULL)
				{
					n=m->next;
					delete m;
					m=n;
				
				}
			  delete top;
			  top=s;
			  
			}
}
//得到图的顶点数
int TU::getvnum() 
{
	return vnum;
}


//寻找IP的结点，未找到返回NULL
PNODE TU::searchdd(int ip)

{   
   PNODE p;
	p=top->next;  
 
	while ((p!=NULL)&&(p->ip!=ip)) p=p->next;
	return p;
   };
//当a为0表示无向边，为1表示有向边
//建立从IP1到IP2的关系，如果IP1或IP2不存在，则建立IP1或IP2结点,如果TOP为空,并修改TOP
//如果IP1到IP2的关系存在，则新的关系将覆盖旧的关系  q表示边的权
int TU::addgx(int ip1,int ip2,int q=1,int a=0) 
{
    if ((ip1==ip2) || (q<1)) return 0;//当IP1与IP2相等或权小于1的时候退出 返回假
	PNODE p1,p2;
	PLINK l,m;
	p1=searchdd(ip1);
 
	if (p1==NULL)   //在图里找IP1，如没找到，则新建IP1结点
	{
		p1=new NODE;
		p1->ip=ip1;
		p1->next=top->next;
		
		l=new LINK;
		l->next=NULL;
		p1->link=l; //添加一个空结点
         vnum++;
		top->next=p1;
	
	}
	
	p2=searchdd(ip2); 
	if (p2==NULL) //在图里找IP2，如没找到，则新建IP2结点
	{
		p2=new NODE;
		p2->ip=ip2;
		p2->next=top->next;

		l=new LINK;
		l->next=NULL;
		p2->link=l;//添加一个空结点
         vnum++;
		top->next=p2;
	
	}
  
  l=p1->link;
  while ((l->next!=NULL)&&(l->next->node->ip!=ip2)) l=l->next; //在IP1边里找IP2，
                                                     //如果没找到，则建立IP1与IP2的关系
  if (l->next==NULL) 
  {	
	  
	l= new LINK;
	l->node=p2;
	l->q=q;
	l->next=p1->link->next;
	p1->link->next=l;
  };



  l=p2->link;
  while ((l->next!=NULL)&&(l->next->node->ip!=ip1))  l=l->next; //在IP2边找IP1，
  
  if (l->next==NULL)  
  { if (a==0)  //当在IP2边没有找到IP1，并且 需要建立无向边时候，在IP2里增加IP1
    {
    l= new LINK;
	l->node=p1;
	l->q=q;
	l->next=p2->link->next;
	p2->link->next=l;
	}
  } 
   else
   if (a==1)  //当IP2边里找到IP1，并且需要建立有向边的时候，需要在IP2边里去掉IP1的信息
   {
    m=l->next;
	l->next=l->next->next;
	delete m;
   }
   return 1;
}

//打印图
void TU::printtu() 
{
	PNODE p;
	PLINK s;

	p=top->next;

   while (p!=NULL)
   {
  printf("%d ",p->ip);
  s=p->link->next;
    while (s!=NULL)
	{  
		printf("----%d",s->node->ip);
		s=s->next;
	}
	printf("\n");
	p=p->next;

   }
}
 //查找ip1与ip2的是否相通，如果不通，则返回0
int TU::isxt(int ip1,int ip2) 
{
	PNODE p1;
	p1=searchdd(ip1);
    if ((p1==NULL) || (searchdd(ip2)==NULL)) return 0;//如果不存在IP1或IP2则返回0失败
	if (ip1==ip2) return 0;//IP1与IP2不能相等，否则返回0失败  
   PNODE p;
   p=top->next;
   while (p!=NULL) {p->bz=0;p=p->next;}
   return (blt(p1,ip2));
 }
//增加一个顶点 ，标识别为ip, 如果顶点存在则什么也不做，
void TU::adddd(int ip) 
 {
	if (searchdd(ip)==NULL)
	{
		PNODE p;PLINK l;
		p=new NODE;l=new LINK;
		p->ip=ip;p->next=top->next;top->next=p;
		l->next=NULL;
		p->link=l;
		vnum++;

	}
 }



//递归 深度优先遍历图，//从IP1出发查找IP2，找到则返回1，失败返回假
int TU::blt(PNODE ip1, int ip2)

{
	PLINK s;
   
	if (ip1->bz==0)
		if (ip1->ip!=ip2)
	     { 
			// printf("%d \n" ,ip1->ip);
		   ip1->bz=1;
		   s=ip1->link->next;
		    while (s!=NULL) 
		     if (blt(s->node,ip2))
		     return 1;
		    else s=s->next;
	      return 0;
	     }
		else 
		
		{
			//printf("%d \n" ,ip1->ip);
			return 1;
		}
	else
	return 0;


}

// 删除一个顶点，删除成功返回，并取掉关联的边，返回1，未找到则返回0
int TU::deldd(int ip)
{
	PNODE p,q;
	PLINK a,b;
	p=top;
	
	while ((p->next!=NULL)&&(p->next->ip!=ip)) p=p->next;
	if (p->next==NULL) return 0;//不存在此顶点，返回1
	q=p->next; //记录顶点
	a=q->link;
	p->next=p->next->next;//从顶点链表中去掉该顶点
   while (a!=NULL)  //删除该顶点边表
   {
	   b=a->next;
	   delete a;
	   a=b;
   }

   p=top->next;
  
   while (p!=NULL)
   {
	   a=p->link;
	   while((a->next!=NULL)&&(a->next->node!=q)) a=a->next;
	   if (a->next!=NULL)
	   {
		   b=a->next;
		   a->next=a->next->next;
		   delete b;
	   }
	   p=p->next;

   }
   delete q;
   vnum--;
	return 1;
}

// 检查是否存在IP的顶点 
int TU::isczdd(int ip)
{
   if (searchdd(ip)==NULL)
	   return 0;
   else
    return 1;
}

// 检查IP1到IP2是否有连接
int TU::iszl(int ip1,int ip2)
{
	PNODE p1;
	p1=searchdd(ip1);
    if ((p1==NULL) || (searchdd(ip2)==NULL)) return 0;//如果不存在IP1或IP2则返回0失败
	if (ip1==ip2) return 0;//IP1与IP2不能相等，否则返回0失败  
   PLINK p;
   p=p1->link->next;
   while (p!=NULL)
	   if (p->node->ip==ip2) 
		   return 1;
	   else
		   p=p->next;
  return 0;
}



// 得到IP1到IP2边的权，如果IP1或IP2不存在，或边不存在则返回0
int TU::getq(int ip1, int ip2)
{
	PNODE p1;
	p1=searchdd(ip1);
    if ((p1==NULL) || (searchdd(ip2)==NULL)) return 0;//如果不存在IP1或IP2则返回0失败
	if (ip1==ip2) return 0;//IP1与IP2不能相等，否则返回0失败  
   PLINK p;
   p=p1->link->next;
   while (p!=NULL)
	   if (p->node->ip==ip2) 
		   return p->q;
	   else
		   p=p->next;
  return 0;


	
}