cgraph.cpp

我写的,画出最短路径,及最小生成树 Prim Dijistra算法+ GDI实现

// cList.cpp: implementation of the cList class.
//
//////////////////////////////////////////////////////////////////////

#include "cList.h"
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

cList::cList()
{
    Head=new(Point);
	Head->Next=0;
	Latest=new(Point);
	PathValue=1000;
	Start=0;
}

cList::~cList()
{
    Now=Head;
	while(Now!=0)
	{
		Bridge=Now;
		Now=Now->Next;
		delete(Bridge);
	}
}

void cList::AddNew()
{
	int a=0;
	Max=0;
	do
	{
    	Now=new(struct Point);
		Now->First=0;
		switch(a)
		{
		case 0:
			{
			Now->x=20;
			Now->y=5;
			};break;
		case 1:
			{
			Now->x=20;
			Now->y=10;
			};break;
			case 2:
			{
			Now->x=20;
			Now->y=15;
			};break;
			case 3:
			{
			Now->x=20;
			Now->y=20;
			};break;
			case 4:
			{
			Now->x=20;
			Now->y=25;
			};break;
			case 5:
			{
			Now->x=20;
			Now->y=30;
			};break;
		}  
        
		
		Now->Index=Max++;
		if(Head->Next==0)
		{
		   Head->Next=Now;
		   Latest=Now;
		}
		else
		{
			Latest->Next=Now;
			Latest=Now;
		}
		Now->Next=0;
		//getchar();
		cout<<"Go on?(1/0)"<<endl;
	//	cin>>a;
	a++;
	}while(a<6);

}
void cList::SetAdj()
{
	Now=new(struct Point);
	SNow=new(struct Point);
	int a;
	int Index1,Index2;
	double weight;

	do
	{
		cout <<"Please set the index "<<endl;
        cin>>Index1>>Index2;
	    Now=Head->Next;
		SNow=Head->Next;
        do
		{
				if(Now->Index==Index1)
				{
                   break;
				}
				Now=Now->Next;

		}while(Now!=0);
		do
		{
                if(SNow->Index==Index2)
				{
                   break;
				}
                SNow=SNow->Next;

		}while(SNow!=0);
         
	 	weight=sqrt(pow((Now->x-SNow->x),2)+pow((Now->y-SNow->y),2));
		if(Now->First==0)
		{
			 Now->First=new(Point::Adj);
		     Now->First->Address=SNow;
             Now->First->Next=0;
			 Now->First->Weight=weight;
			 Now->First->Visited=false;
		}
		else
		{
			 Now->AjNow=new(Point::Adj);
			 Now->AjNow->Address=SNow;
			 Now->AjNow->Visited=false;
			 Now->AjNow->Weight=weight;
             Now->AjNow->Next=Now->First;
			 Now->First=Now->AjNow;
		}
       /* 	if(SNow->First==0)
		{
			 SNow->First=new(Point::Adj);
		     SNow->First->Address=Now;
             SNow->First->Next=0;
			 SNow->First->Weight=weight;
			 SNow->First->Visited=false;
		}
		else
		{
			 SNow->AjNow=new(Point::Adj);
			 SNow->AjNow->Address=Now;
			 SNow->AjNow->Visited=false;
			 SNow->AjNow->Weight=weight;
             SNow->AjNow->Next=SNow->First;
			 SNow->First=SNow->AjNow;
		}*/
        cout<<"Continue(0/1)"<<endl;
		cin>>a;
	}while(a!=0);
}

void cList::SearchPath()
{
    int v=0,w=0,i;
	Now=Head->Next;
	while(Now->Index!=Start)
	{
		 Now=Now->Next;
	}
	for(v=0;v<Max;++v)
	{
		Final[v]=false;
		Now->AjNow=Now->First;
		while(Now->AjNow!=0)
		{
			if(Now->AjNow->Address->Index!=v)
			{
				Now->AjNow=Now->AjNow->Next;
			}     
			else
			{
					if(Now->AjNow->Address->Index==v)
					{
						D[v]=Now->AjNow->Weight;
						P[v]=Start;
						
					}
					break;
			}
		}
		if(Now->AjNow==0)
		{
			D[v]=1000000;
			P[v]=-2;
		}
	
	}
	 P[Start]=-1;
	 D[Start]=0;
	 Final[Start]=true;
	 for(i=0;i<Max;++i)
	 {
		 Min=10000;
		 for(w=0;w<Max;++w)
		 {
			 if(!Final[w])
				 if(D[w]<Min)
				 {
					 v=w;
					 Min=D[w];
				 }
		 }

		 	 Final[v]=true;
			 Now=Head->Next;
            while(Now->Index!=v)
			{
        	 Now=Now->Next;
			}		
		 for(w=0;w<Max;++w)
		 {
			 Now->AjNow=Now->First;
			 while(Now->AjNow!=0)
			 {
				 if(Now->AjNow->Address->Index!=w)
                   Now->AjNow=Now->AjNow->Next;
				 else
				 {
         
					if(!Final[w]&&((Min+Now->AjNow->Weight)<D[w]))
					{
			        	 D[w]=Min+Now->AjNow->Weight;
			        	 P[w]=v;
					} 
					break;
				 }	
			 }
			 
		 }
	 }
	 getchar();
}