导游.cpp

数据结构课设做的

		   vfile<<"$";
		   p=p->NextV;
		}
		vfile<<"&\n";

	}
   Afile.close();
   vfile.close();

}
/************************************************************************************************/


void AddVnode(Algraph &J)//添加结点pass
{
	fstream Afile,vfile;
    int n,t;
	char v;
    J=Revert(J);
	Open(Afile,vfile);
	cout<<"\t\t\t下面请输入要加入的详细信息"<<endl;
	cout<<"\t\t>>-----------------------------------------<<"<<endl<<endl;

	cout<<"\t输入要添加多少个景点:"<<"\t";
	cin>>n;
	cin.ignore();

	for(int i=1;i<=n;i++)
	{  
        cout<<"\t下面是第"<<J.vexnum+i<<"个景点的信息"<<endl;
		cout<<"\t输入标志"<<endl<<"\t\t";
		cin>>J.vert[J.vexnum+i].title.sign;
		cin.ignore();
		cout<<"\t输入名称"<<endl<<"\t\t";
		cin.getline(J.vert[J.vexnum+i].title.Name,10,'\n');
	    cout<<"\t输入简介"<<endl<<"\t\t";
		cin.getline(J.vert[J.vexnum+i].Intro,1000,'@');
	}
	J.vexnum=J.vexnum+n;
	for(int w=J.vexnum-n+1;w<=J.vexnum;w++)
	{
		system("cls");
		int h;
		cout<<"\t请输入与"<<J.vert[w].title.sign<<"相邻的结点个数"<<endl<<"\t\t\t";
		cin>>h;
		if(h==0)
		{
			J.vert[w].firstarc=NULL;
		}
		else
		{
	       cout<<"\t请按字母顺序输入与"<<J.vert[w].title.sign<<"结点相邻的第1个结点和两者之间的边权值"<<endl;  
		   cout<<"\t\t输入结点编号:"<<"\t";
		   cin.ignore();
           cin.get(v);
		   for(int m=1;m<=J.vexnum;m++)
		   {
               if(J.vert[m].title.sign==v)
				   break;
		   }
		   if(m>J.vexnum)
		   {
			   exit(0);
		   }
		   cout<<"\t\t输入边权值:"<<"\t";
		   cin.ignore();
           cin>>t;
		   J.vert[w].firstarc=new Vision;
	       J.vert[w].firstarc->NextV=NULL;
		
	       J.vert[w].firstarc->Position=locate(J,v); 
		  
           J.vert[w].firstarc->adj=t;
		   
		   Vision *p,*q;
	       q=J.vert[w].firstarc;
		    
	       for (int j=1;j<h;j++)
		   {
		      cout<<"请按字母顺序输入与"<<J.vert[w].title.sign<<"结点相邻的第"<<j+1<<"个结点和两者之间的边权值"<<endl;
              cout<<"\t\t输入结点编号:"<<"\t";
			  cin.ignore();
			  cin.get(v);
			  cout<<"\t\t输入边权值:"<<"\t";
			  cin.ignore();
			  cin>>t;

		      p=(Vision *)malloc(sizeof(Vision));
		      p->NextV=NULL;
		
		      p->Position=locate(J,v); 
			  p->adj=t;
			  q->NextV=p;
		      q=p;
		      
		   }
		}
		 
	} 
  
	for(int k=J.vexnum-n+1;k<=J.vexnum;k++)
	{
		Vision *w,*p,*q;
		w=J.vert[k].firstarc;
		int x;
		while(w!=NULL)
		{
			x=w->Position;
			
			if(J.vert[x].firstarc==NULL)
			{
                 J.vert[x].firstarc=new Vision;
	             J.vert[x].firstarc->NextV=NULL;
                 J.vert[x].firstarc->Position=locate(J,J.vert[k].title.sign);
				 J.vert[x].firstarc->adj=locfind(J, k,x);
			}
			else
			{
	            p=J.vert[x].firstarc;
	           while(p->NextV!=NULL)
			   {
		           p=p->NextV;
			   }
               q=(Vision *)malloc(sizeof(Vision));
	           q->NextV=NULL;
	           q->Position=locate(J,J.vert[k].title.sign);
	           q->adj=locfind(J, k,x);
	           p->NextV=q;
			}

		    w=w->NextV;
		}
	}
	
	Refur(J);
	Afile.close();
	vfile.close();
	cout<<"Ok"<<endl;

}
/*********************************************************************************************************************/
void Addside(Algraph &J)//添加边pass
{
	fstream Afile,vfile;
	char wh,ch;
	Vision *p,*q;
	int w,c,route;
	J=Revert(J);
    Open(Afile,vfile);
    cout<<"\t下面将显示该学校的景点名称,请按编号选择想要添加边的两个的景点"<<endl;
    show(J);
	cout<<"\t输入第一个景点:"<<endl<<"\t\t";
    cin>>ch;
	cout<<"\t输入第二个景点:"<<endl<<"\t\t";
	cin>>wh;
    c=locate(J,ch);
	w=locate(J,wh);
	
    int u=1;
	p=J.vert[c].firstarc;
	while(p!=NULL)
	{
		if(p->Position==w)
		{
			cout<<"\t两点已经存在路线了"<<endl;
            u=2;
			break;
		}
		p=p->NextV;
	}
	
	if(u==1)
	{
		 cout<<"\t输入两点间的距离:"<<endl<<"\t\t";
	     cin>>route;
		 int m;
	     int sign[2]={c,w};
	     for(int i=0;i<2;i++)
		 {
		       if(sign[i]==c)
			   {m=w;}
			   if(sign[i]==w)
			   {m=c;}
	      	    p=J.vert[sign[i]].firstarc;
		        while(p!=NULL)
				{
		        	if(p->Position>m)
					{
						q=new Vision;
						q->Position=m;
						q->adj=route;
						q->NextV=p->NextV;
						J.vert[sign[i]].firstarc=q;
						break;

					}
					
					if(p->Position<m && p->NextV!=NULL && p->NextV->Position>m)
					{
						q=new Vision;
						q->Position=m;
						q->adj=route;
						q->NextV=p->NextV;
						p->NextV=q;
						break;
					}
					if(p->Position<m && p->NextV==NULL)
					{
                        q=new Vision;
						q->Position=m;
						q->adj=route;
						p->NextV=q;
						q->NextV=NULL;
						break;
					}
					p=p->NextV;

				}
			

		 }

	}
	Refur(J);
	Afile.close();
	vfile.close();
	cout<<"OK"<<endl;
}
/*********************************************************************************************************************/

void DeleteVnode(Algraph &J)//删除结点pass
{
	fstream Afile,vfile;
	char ch;
	int c,v;
    J=Revert(J);
    Open(Afile,vfile);
    
	cout<<"\t下面将显示该学校的景点名称,请按编号选择想要删除的景点"<<endl;
    show(J);
	cout<<endl<<"\t输入:";
	cin>>ch;
    c=locate(J, ch);
	
    strcpy(J.vert[c].title.Name,"Noname");
	strcpy(J.vert[c].Intro,"Nothing");
    Vision *p;
	p=J.vert[c].firstarc;
	while(p!=NULL)
	{
		v=p->Position;
		Vision *q,*w;
		w=q=J.vert[v].firstarc;
		
		while(w!=NULL)
		{
          if(w->Position==c)
		  {
            if(w==J.vert[v].firstarc && w->NextV==NULL)
			{
				J.vert[v].firstarc=NULL;
				break;
			}
			 else
			 {
				 if(w==J.vert[v].firstarc && w->NextV!=NULL)
				 {
				      J.vert[v].firstarc=w->NextV;
			          delete w;
				      break;
				 }
				 if(w!=J.vert[v].firstarc)
				 {
					 q->NextV=w->NextV;
					 delete w;
					 break;
				 }
			 }
		  }
		  q=w;
          w=w->NextV;
		}
		p=p->NextV;
	}
	if(p==NULL)
	{
		cout<<"^@^"<<endl;
	}
	Vision *s,*q;
	p=J.vert[c].firstarc;
	while(p!=NULL)
	{
		s=p;
		if(J.vert[c].firstarc->NextV==NULL)
		{
            J.vert[c].firstarc=NULL;
			break;
		}
		while(s->NextV!=NULL)
		{
			q=s;
			s=s->NextV;
		}
		if(s!=NULL && s->NextV==NULL)
		{
			delete s;
			q->NextV=NULL;
			s=q;
		}
		p=p;
       
	}
   Refur(J);
   cout<<"删除结束"<<endl;
   Afile.close();
   vfile.close();

}
/************************************************************************************************/
void Deleteside(Algraph &J)//删除边pass
{
    fstream Afile,vfile;
    char wh,ch;
    int w,c;
    J=Revert(J);
    Open(Afile,vfile);
    cout<<"下面将显示该学校的景点名称,请按编号选择想要删除边的两个的景点"<<endl;
    show(J);
	cout<<endl<<"输入第一个景点:"<<"\t";
    cin>>ch;
	cout<<"输入第二个景点:"<<"\t";
	cin.ignore();
    cin.get(wh);
    c=locate(J,ch);
	w=locate(J,wh);

	int u=1;
	Vision *p,*q;
	p=J.vert[c].firstarc;
	while(p!=NULL)
	{
		if(p->Position==w) 
		{
			cout<<"\t两点间存在路线可以删除"<<endl;
            u=2;
			break;
		}
	  p=p->NextV;
	}
	if(p==NULL)
	{
		cout<<"\t两点间不存在边，不能进行删除操作"<<endl;
	}
	
	if(u==2)
	{
         int m;
	     int sign[2]={c,w};
	     for(int i=0;i<2;i++)
		 {
		       if(sign[i]==c)
			   {m=w;}
			   if(sign[i]==w)
			   {m=c;}  
               q=p=J.vert[sign[i]].firstarc;
	           while(p!=NULL)
			   {
		           
				   if(p->Position==m)
				   {
                        if(p==J.vert[sign[i]].firstarc && p->NextV==NULL)
						{
				             J.vert[sign[i]].firstarc=NULL;
				             break;
						}
			            else
						{
				             if(p==J.vert[sign[i]].firstarc && p->NextV!=NULL)
							 {
				                 J.vert[sign[i]].firstarc=p->NextV;
			                     delete p;
				                 break;
							 }
				             if(p!=J.vert[sign[i]].firstarc)
							 {
					             q->NextV=p->NextV;
					             delete p;
					             break;
							 }
						}
				   }
				   q=p;
				   p=p->NextV;
			   }
		 }
	}

    Refur(J);
	Afile.close();
	vfile.close();
	 
}
/*********************************************************************************************************************/
void UpdateInfo(Algraph &J)//更新信息包含边和结点
{
    fstream Afile,vfile;
	char ch,wh,bh;
	int w,b,longs;
    J=Revert(J);
    Open(Afile,vfile);
    cout<<endl<<endl<<endl<<endl<<"\t\t请选择需要更新的数据"<<endl<<endl;
	cout<<"\t\t\ta  景点"<<endl<<endl;
	cout<<"\t\t\tb  距离"<<endl<<endl;
	cout<<"\t\t输入:\t";
    cin>>ch;
	system("pause");
	system("cls");
   switch(ch)
   {	
 
	 case 'a':
	{
	   cout<<"\t下面将显示该学校的景点名称,请按编号选择想要更新数据的景点"<<endl;
       show(J);
	   cout<<endl<<"\t输入:"<<"\t";
	   cin>>wh;
       w=locate(J,wh);
	   system("cls");
	   cout<<endl<<"\t\t请选择要更新部分:"<<endl<<endl;
	   cout<<"\t\ta  名称"<<endl<<endl;
	   cout<<"\t\tb  简介"<<endl;
	   cout<<endl<<"\t输入:\t";
	   cin>>ch;
	   if(ch=='a')
	   {
	    cout<<"\t输入名称"<<endl<<"\t\t";
		cin.ignore();
		cin.getline(J.vert[w].title.Name,10,'\n');
	   }
	   if(ch=='b')
	   {
	    cout<<"\t输入简介"<<endl<<"\t\t";
		cin.ignore();
		cin.getline(J.vert[w].Intro,1000,'@');
	   }
	   
	}
	  break; 
	   
	 case 'b':
	{		 
		 cout<<"\t下面将显示该学校的景点名称,请按编号选择想要更新距离的两个的景点"<<endl;
         show(J);
		 cout<<endl<<"\t第一个景点:"<<"\t";
		 cin.ignore();
		 cin.get(wh);
		 cout<<"\t第二个景点:"<<"\t";
		
		 cin.ignore();
		 cin.get(bh);
		 w=locate(J,wh);
         b=locate(J,bh);
		
         Vision *p;
	     p=J.vert[w].firstarc;
	     while(p!=NULL)
		 {
		   if(p->Position==b) 
		   {
			  cout<<"\t存在路径,可以进行更新"<<endl<<endl;
			   break;
		   }
	       p=p->NextV;
		 }
	     if(p==NULL)
		 {
		    cout<<"\t两点间不存在边，不能进行更新操作"<<endl;
			break;
		 }
         cout<<"\t输入新的距离:"<<endl<<"\t";
		 cin>>longs;
		 int sign[2]={w,b};
		 for(int i=0;i<2;i++)
		 {
			 int m;
			 if(sign[i]==w)
			 {m=b;}
			 if(sign[i]==b)
			 {m=w;}
			 p=J.vert[sign[i]].firstarc;
			 while(p!=NULL)
			 {
				 if(p->Position==m)
				 {
					
					 p->adj=longs;
					 break;
				 }
				 p=p->NextV;
			 }
		 }
		 
	}
	break;
	 default:cout<<"error"<<endl;
	
   }
   Refur(J);
   cout<<"\t\t更新结束"<<endl;
   Afile.close();
   vfile.close();
}

/**********************************************************************************************************/
void Floyd(int cost[100][100],int n,int weight[100][100],int path[50][50],int s,int t)
{
	int i,j,k;
	fstream fp;
	fp.open("sp.txt",ios::in|ios::out|ios::trunc);
    if(fp.fail())
	{
		cout<<"打开sp文件出错"<<endl;
		exit(0);
	}
	for( i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			
			{
			   weight[i][j]=cost[i][j];
			   path[i][j]=0;
			}
	    

		for(k=1;k<=n;k++)
		{  
			for(i=1;i<=n;i++)
				
			{   
				for(j=1;j<=n;j++)