graph2.h

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

      }

  boolean un_cover(adjhlink& t,int x0,int y0)
    { boolean un_cover=boolean((t->x-x0)*(t->x-x0)+(t->y-y0)*(t->y-y0)>4*(rdx)*(rdx));
    return un_cover;  }

  boolean un_cover_nodes(datagraph& g ,int x0,int y0)
    {adjhlink t1;
       boolean xx=true;

	       t1=g.firsthead->nexthead;
	       while ((xx)&&(t1!=nil))
	       { xx= boolean(xx &&(un_cover(t1,x0,y0)));
		 t1=t1->nexthead;
	       }

      boolean	  un_cover_nodes=xx;
      return un_cover_nodes;
      }
   boolean  graph_cover_node(datagraph& g ,int  gnode)
   {adjhlink t1,t2; int x0,y0;
       boolean xx=true;
      //function un_cover(var t:adjhlink;x0,y0:integer):boolean;
	//  { un_cover:=sqr(t^.x-x0)+sqr(t^.y-y0)>4*sqr(rdx) };
      t2=get_ver_head(g,gnode);x0=t2->x; y0=t2->y;
       //	with g do
	  t1=g.firsthead->nexthead;
	       while (xx && (t1!=nil)&&(t1!=t2))
	       { xx=boolean(xx&&un_cover(t1,x0,y0));
	       t1=t1->nexthead;
	       }

	  boolean graph_cover_node=boolean(!xx);
	  return graph_cover_node;
      }
     adjhlink  get_ver_head(datagraph& g,int v)
      {adjhlink h1;
	 h1=g.firsthead;
	 while ( (h1!=nil)&&(h1->nodenum!=v))
		 h1=h1->nexthead;

	 adjhlink     get_ver_head=h1;
	 return get_ver_head;
      }


    adjlink   firstadjp(datagraph& g,int  v)
     {adjhlink h1;adjlink a1;
	h1=get_ver_head(g,v);
       adjlink	firstadjp=h1->firstadj->nextadj;
       return firstadjp;
      }

   adjlink  nextadjp(datagraph& g ,int v, adjlink adj)
    {adjhlink h1;
      adjlink a1;
      adjlink nextadjp;
      h1=get_ver_head(g,v);
      a1=h1->firstadj->nextadj;
      while((a1!=nil)&&(a1->nextadj!=adj))
		  a1=a1->nextadj;
	      if( (a1==nil)|| (a1->nextadj==nil))
		     nextadjp=nil ;
	      else
		  nextadjp=adj->nextadj;
       return nextadjp;
	 }

    int   firstadj(datagraph& g ,int v)
    {adjlink a;
    int firstadj;
	a=firstadjp(g,v);
	if( a==nil)  firstadj=0;
	  else firstadj=a->nodenum;
     return firstadj;
       }
    int   nextadj(datagraph& g ,int v,int w)
      {adjlink a;
	 int nextadj;
	a=firstadjp(g,v);
	 while ((a!=nil)&&(a->nodenum!=w))
		  a=a->nextadj;
	     if( (a==nil)|| (a->nextadj==nil))
		     nextadj=0 ;
	      else
		  nextadj=a->nextadj->nodenum;
       return nextadj;
       }
  void setnull_graph(datagraph& g ,boolean  isweight,boolean  isdirect)
    {  g.nodes=0;
       g.haveweight=isweight;
       g.direct=isdirect;
       g.firsthead=new adjhead;
	   ///with g.firsthead^ do
	     g.firsthead->nodenum=0;
	     g.firsthead->nexthead=nil;
	     g.firsthead->firstadj=nil;
    }
 int   nodes(datagraph& g )
       { int nodes=g.nodes ;
       return nodes;}
boolean is_digraph(datagraph& g )
    { boolean is_digraph=g.direct;
    return is_digraph; }
boolean  have_weight(datagraph& g )
    { boolean have_weight=g.haveweight;
    return have_weight; }
  void print_graph(datagraph& g )
  {   adjhlink h1;adjlink a2;
      // window(1,1,80,25); { clrscr;}
      cout<<" graph :"<<endl;
	cout<<setw(6)<<g.nodes;
	  h1=g.firsthead;
	  while (h1!=nil)
	     {cout<<"node "<<h1->nodenum<<" to: ";
		    a2=h1->firstadj;
		  while (a2!=nil)
		    { cout<<"("<<a2->nodenum<<" "<<a2->weight<<" )  ";
			    a2=a2->nextadj;
		    }
		    cout<<endl;
		    h1=h1->nexthead;
	     }

       getch();
     }




       void insert_vertex(datagraph& g ,int num,int cx,int cy)
     {adjhlink h1;
       g.nodes=num;h1=get_ver_head(g,num-1);
	h1->nexthead=new adjhead;
	h1=h1->nexthead;
	     h1->x=cx;h1->y=cy;
	     h1->nodenum=num;
	     h1->firstadj=new adjnode;
	     h1->nexthead=nil;
	       { h1->firstadj->nodenum=0;
		 h1->firstadj->nextadj=nil;
	      }
      }




   void put_edge_weight(datagraph& g ,int  v1,int v2,int w)
    {
    if(!is_digraph(g) )
    {
      adjhlink h1;
      adjlink a1,a2,a3;
      string ss;
      if(  (v1<1||v1>g.nodes)&& (v2<1&&v2>g.nodes) )
	   {
	    ss="顶点 ";
	    Convs(v1,st);
	    strcat(ss,st);
	    strcat(ss," 或 ");
	    Convs(v2,st);
	    strcat(ss,st);
	    strcat(ss," 不存在 ");
	    Error(ss);
	    }
     else  if (!have_edge(g,v1,v2) )
	   {
	   ss="边 <";
	   Convs(v1,st);
	   strcat(ss,st);
	   strcat(ss,",");
	   Convs(v2,st);
	   strcat(ss,st);
	   strcat(ss,">不存在, 不能赋权值");
	   Error(ss);
	  }
	   else  {   h1=get_ver_head(g,v1);
		    if (h1==nil)
			{
			ss="没有 ";
			Convs(v1,st);
			strcat(ss,"顶点 ");
			Error(ss);
			}
		    else
		       { a1=h1->firstadj;
			 a2=a1->nextadj;
			 while ( (a2!=nil)&&(a2->nodenum!=v2) )
			       {   a1=a2;
				   a2=a2->nextadj;
				 }
			    if ( (a2!=nil)&&(a2->nodenum==v2) )
				 a2->weight=w;
			    else
				 {
				 ss="边 <";
				 Convs(v1,st);
				 strcat(ss,",");
				 Convs(v2,st);
				 strcat(ss,st);
				 strcat(ss,">不存在, 不能赋权");
				   }
			    }
	 }
    }

}

    void insert_edge_weight(datagraph& g ,int v1,int v2,int w)
      {
       adjhlink h1; adjlink a1,a2,a3;
	if (!( (v1>=1&&v1<=g.nodes)&&(v2>=1&&v2<=g.nodes)) )

	     cout<<"顶点 "<<v1<<" 或 "<<v2<<" 不存在 "<<endl;
	else
	  {   h1=get_ver_head(g,v1);
	       if (h1==nil)
		      cout<<"没有 "<<v1<< "顶点 ";

		else { a1=h1->firstadj;
		       a2=a1->nextadj;
		       while ((a2!=nil)&&(a2->nodenum<v2))
			   { a1=a2;
			   a2=a2->nextadj;
			   }
		      if ((a2!=nil)&&(a2->nodenum==v2))
			  cout<<"边 <"<<v1<<","<<v2<<">已存在, 不能插入 ";
			else  {
			     a2=new adjnode;a2->nextadj=a1->nextadj;
			      a2->nodenum=v2;a1->nextadj=a2;a2->weight=w;
				}
		 }
	 }
    }

  void insert_edge(datagraph& g ,int v1,int v2)
    { insert_edge_weight(g,v1,v2,1); }
  int  edge_weight(datagraph& g ,int v1,int v2)
      {  adjhlink h1;adjlink a1;
	  h1=get_ver_head(g,v1);
	   a1=h1->firstadj;
	   while ((a1!=nil)&&(a1->nodenum!=v2)) a1=a1->nextadj;
	 int  edge_weight=a1->weight;
	 return edge_weight;
     }
  boolean  have_edge(datagraph& g ,int v1,int v2)
    {adjhlink h1;
      adjlink a1;
      h1=get_ver_head(g,v1); a1=h1->firstadj;
	   while( (a1!=nil)&&(a1->nodenum!=v2))
	    a1=a1->nextadj;
	boolean   have_edge=boolean(a1!=nil);
      return have_edge;
     }
  void join(datagraph& g ,adjhlink h1,adjhlink h2,int& sx,int& sy,int& ex,int&ey,int& wx,int& wy)
     { if (g.direct&&(have_edge(g,h2->nodenum,h1->nodenum)))
		 join_double_edge(h1,h2,sx,sy,ex,ey,wx,wy);
	   else  join_single_edge(h1,h2,sx,sy,ex,ey,wx,wy);
      }
  void display_edge(datagraph& g ,int& v1,int& v2)
    {adjhlink h1,h2; adjlink a1; string ss;
      int  sx,sy,ex,ey,wx,wy,w;
      if(! (have_edge(g,v1,v2)))
	     exit(1);
       h1=get_ver_head(g,v1);
       h2=get_ver_head(g,v2);
	join(g,h1,h2,sx,sy,ex,ey,wx,wy);
	if (g.direct)
	      Arrow(sx,sy,ex,ey);
	 else
	      line(sx,sy,ex,ey);
	   if (g.haveweight)
	      {      Convs(edge_weight(g,v1,v2),st);
		     outtextxy(wx,wy,"  ");
		     outtextxy(wx,wy,st) ;
	      }
	 }
  void display_all_edge(datagraph& g )
     {adjhlink h;adjlink a;
      int v1,v2,w;
      h=g.firsthead->nexthead;
	   while( h!=nil)
	   { v1=h->nodenum;a=h->firstadj->nextadj;
	       while (a!=nil)
	       { v2=a->nodenum;
		    if (!(!g.direct &&(v1>v2)))
		      display_edge(g,v1,v2);
		   a=a->nextadj;
	       }  h=h->nexthead;
	   }
     }
  void display_vertex(adjhlink& h)
     { putimage(h->x,h->y,nilnd,1);
	disnodedat(h);
       }
  void display_all_vertex(datagraph& g )
    {int xl,yl,xr,yr;
     adjhlink h;
     graph_range(g,xl,yl,xr,yr);
     Clear_range(xl,yl,xr,yr);
     xl=xl+8; yl=yl+18; xr=xr-8; yr=yr-8;
     rectangle(xl,yl,xr,yr);
     h=g.firsthead->nexthead;
       while (h!=nil)
	   {   display_vertex(h);
	       h=h->nexthead;
	       }
     }
  void copy_all_vertex(datagraph& g,datagraph& g1,int dx,int dy)
     {adjhlink  h,h1;
      g1.nodes=g.nodes;
      g1.haveweight=g.haveweight;
      g1.direct=g.direct;

      g1.firsthead=new adjhead;
      h1=g1.firsthead;
      h1->x=0;
      h1->y=0;
      h1->nodenum=0;
      h1->firstadj=nil;
      h=g.firsthead->nexthead;
      while (h!=nil)
	  {  h1->nexthead=new adjhead;
	      h1=h1->nexthead;
	      { h1->x=h->x+dx;h1->y=h->y+dy;
		h1->nodenum=h->nodenum;
		h1->firstadj=new adjnode;
		h1->nexthead=nil;
		  //with firstadj^ do
		  { h1->firstadj->nodenum=0;
		    h1->firstadj->weight=0;
		    h1->firstadj->nextadj=nil; }
		    }
	     h=h->nexthead;
	  }
     }
  void copy_edge(datagraph& g ,int v1,int v2,datagraph& g1)
    {int w;
       w=edge_weight(g,v1,v2);
       insert_edge_weight(g1,v1,v2,w);
      if(!g.direct)
	 insert_edge_weight(g1,v2,v1,w);
      }
  void copy_all_edge(datagraph& g,datagraph& g1)
     {adjhlink  h;adjlink a;int v1,v2,w;
      h=g.firsthead->nexthead;
	   while (h!=nil)
	   { v1=h->nodenum;
	      a=h->firstadj->nextadj;
	       while (a!=nil)
	       { v2=a->nodenum;
		if (!(!g.direct&&(v1>v2)) )
		      copy_edge(g,v1,v2,g1);
		      a=a->nextadj;
		 }
		  h=h->nexthead;
	   }
     }
   void graph_range(datagraph& g ,int&  xl,int& yl,int& xr,int& yr)
     {adjhlink h;
	h=g.firsthead->nexthead;
	xl=h->x;yl=h->y;xr=xl;yr=yl;
	 while (h!=nil)
	      { if (h->x<xl)
		     xl=h->x;
		if (h->y<yl)
		      yl=h->y;
		if (h->x>xr)
		      xr=h->x;
		if (h->y>yr)
		       yr=h->y;
		h=h->nexthead;
	      }
	 xl=xl-2*rdx-10;  yl=yl-2*rdy-20;
	 xr=xr+4*rdx+10;  yr=yr+4*rdy+10 ;
      }
   void clear_graph_range(datagraph& g )
     {int xl,yl,xr,yr;
       graph_range(g,xl,yl,xr,yr);
       Clear_range(xl,yl,xr,yr);
       }

   void disp_graph(string s, datagraph& g )
    {int xl=0,yl=0,xr=0,yr=0;
	 display_all_vertex(g);
	 display_all_edge(g);
	 graph_range(g,xl,yl,xr,yr);
	 xl=xl+8;
	 yl=yl+18;
	 xr=xr-8;
	 yr=yr-8;
	 Outtextxy((xl+xr)/2/8, (yl-5)/20,s);
     }

   void display_graph(string s,datagraph& g )
     { initial_graph();
       for (int i=0;i< 4 ;i++)
       visitegraphmodes[i]=onevisitemode;
       initial_visitemode(visitegraphmodes);

	disp_graph(s,g);
	 }


   void dismenu(int ll)
   {
     unsigned char  ss[100],s[100],s1[100],space[100],ms1[100],mss[100];
     setfillstyle(1,0);

     bar(2,2,getmaxx()-2,startrow-2);
     strcpy(s," ctrl w : return , ");
	switch(ll)
	{
	case  -1:{  strcpy(ss," Main menu ");
		    strcpy(s1, "^W, V, E, M, C, Arrow ");
		    strcpy(mss,"主菜单:");
		    strcpy(ms1,"^W:返回; V:产生新顶点; E:输入边; M:移动顶点; C:修改边权值; 方向键:移光标");
		  }break;
	case  1: { strcpy(ss," Insert Edges ");
		   strcpy(s1,"SPACE bar: New Edge");
		   strcpy(mss,"输入边;");
		   strcpy(ms1,"空格键: 以输入另外新边");
		  }break;
       case   d:  { strcpy(ss," Insert Vertex ");
		    strcpy(s1,"v,V: New Vertex ");
		    strcpy(mss,"");
		    strcpy(ms1,"v,V: 产生新顶点 ");
		}  break;
       case	 m: { strcpy(ss," Locate Vertex ");
		      strcpy(mss,"顶点定位: ");
		      strcpy(ms1,"←,^←: 左移;  →,^→: 右移; ↑:上移; ↓:下移; ESC:取消顶点; 回车结束");
		      strcpy(s1,ms1);
		   }break;
       case	 3: { strcpy(ss," Move Cursor ");
		      strcpy(s," ");
		      strcpy(s1," ←,→,V,^,^→,^← ");
		      strcpy(ms1,"←,^←: 左移;  →,^→: 右移; ↑:上移;↓:下移; 回车: 结束");
		      strcpy(mss," 移动光标: ");
		   }break;
	     }
	strcat(ss,s);
	setfillstyle(1,0);
	bar(1,1,getmaxx(),startrow+7 );
	Displaytextxy(10,1,ss);
	Displaytextxy(10,2,s1);
	rectangle(1,1,getmaxx(),startrow+7);
	strcat(mss,ms1);
	Menu(mss);
     }

    void calnew(int& x,int& y,int key)
      {int  i,x0,y0;
	i=0;
	    while ( (i<dirnum)&&(key!=mv[i][2] ) )
			i=i+1;
		x0=x+mv[i][0]*mvstep;
		y0=y+mv[i][1]*mvstep;
		if ( (x0>getmaxx()-4*rdx) || (x0<2*rdx) ||
		    (y0>getmaxy()-4*rdy)||(y0<startrow) )
		       cout<<'\007'<<endl;
		else  { x=x0;y=y0; }
	 }
   void move_cursor(int& curx,int& cury,int key,boolean&  funckey)
     {int x,y;
       dismenu(3);
	do
	{
	  //(key== in dir_keyset then
	    if( key==up||key==down||key==left||key==right||key==bigleft||key==bigright)
		 {     putimage(curx,cury,cursor,1);
		       calnew(curx,cury,key);
		       putimage(curx,cury,cursor,1);
		  }
		    else if(!(key==10||key==13) )
		    cout<<'\007';

	  Getkey(key,funckey);
	  }
      while( !(key==10||key==13) ); //until key in [10,13];       {menu(" ");}

      }

   void locttnod(adjhlink& t, ffield1& ff)
     {int  key;
      boolean funckey;
	dismenu(m);
       //with t^ do
	putimage(t->x,t->y,ff,2);
	do
	{
	 Getkey(key,funckey);
	 if(!(key==10||key==13||key==esc) )
	  {
	    if ( key==up||key==down||key==left||key==right||key==bigleft||key==bigright)
		{  putimage(t->x,t->y,ff,1);
		   calnew(t->x,t->y,key);
		   putimage(t->x,t->y,ff,1);
		 }
	    else
		  cout<<'\007';
	   }
	}