schoolguide.cpp

校园导游参考 运用DIJKSTRA等算法实现

		while( p != NULL )
		{
			file.write((char*)p,sizeof(ArcNode));
			p=p->nextarc;
		}
		//将与该顶点有关的边全部写入文件
	}
	file.flush();
}//WriteToFile(ALGraph &G,fstream &file)


void InsertGraph(ALGraph &G)
{
	//根据用户的需要来添加信息
	VNode  v;
	ArcNode *a1,*a2;
	char name[20],name1[20],name2[20],choice;
	int num,weight,k,w;
	v.firstarc = NULL;
	cout<<"插入点(v)OR边(a)";
	cin>>choice;
    choice = toupper(choice);

	if( choice == 'V' )
	{	  
		cout<<"请输入你要插入的风景点名称: " ;	
		cin>>v.data;	
		cout<<"请输入风景点的简介:";	
		cin>>v.info;	
		v.arcnum=0;   
		if(InsertVex(G,v) == 1)	
		{	 		
			cout<<"请输入与之有联系的风景点个数: ";	    
			cin>>num;
			cin.ignore();
			
			for(int i=1;i<=num;i++)			
			{	    			
				cout<<"请输入与之有联系的风景点名称: ";	     		
				cin>>name;		 
		 			
				k=LocateVex(G,name); 			
			
				if( k != -1 )		 			
				{				
					a1=new ArcNode[1];				
					a2=new ArcNode[1];
				
					cout<<"请输入它们之间的距离: ";		     				
					cin>>weight;			 				
					a1->weight=weight;             				
					a1->adjvex = k;					
					a2->weight=weight;			 				
					a2->adjvex = G.vexnum-1;	
			
					InsertArc(G,a2,k);								
					InsertArc(G,a1,G.vexnum-1);			 		
				}		 
			
				else			
				{							
					cout<<"该风景点不存在！"<<endl;		 			
				}	
			}
		}
	}

	if( choice == 'A' )
	{
		cout<<"请输入你要插入的边对应起始风景点名称名称！"<<endl;
		cout<<"点1： ";
		cin>>name1;
		cin.ignore();
		k=LocateVex(G,name1);

		if(k == -1)
		{
			cout<<"该风景点不存在！插入失败！"<<endl;
			return;
		}

		cout<<"点2： ";
		cin>>name2;
		cin.ignore();
		w=LocateVex(G,name2);

		if(w == -1)
		{
			cout<<"该风景点不存在！插入失败！"<<endl;
			return;
		}
	    cout<<"请输入它们之间的距离: ";		     				
		cin>>weight;

		a1=new ArcNode[1];				
		a2=new ArcNode[1];
		a1->adjvex = k;
		a2->adjvex = w;
		a1->weight = weight;
		a2->weight = weight;
		a1->nextarc = NULL;
		a2->nextarc = NULL;
        InsertArc(G,a1,w);
        InsertArc(G,a2,k);
	}
}//InsertGraph(ALGraph &G)


void DeleteGraph(ALGraph &G)
{
	//根据用户的需要来删除信息
	char c,name1[20],name2[20];
	int   v,w;
	
	cout<<"删除风景点还是边(点v，边a):";
	cin>>c;
	cin.ignore();

	if(c == 'V'|| c== 'v')
	{
		cout<<"请输入你要删除的风景点名称：";
		cin>>name1;
		DeleteVex(G,name1);
	}
	if(c == 'A'|| c == 'a')
	{
		cout<<"请输入你要删除的边对应起始风景点名称名称！"<<endl;
		cout<<"点1： ";
		cin>>name1;
		cin.ignore();
		v=LocateVex(G,name1);

		if(v == -1)
		{
			cout<<"该风景点不存在！删除失败！"<<endl;
			return;
		}

		cout<<"点2： ";
		cin>>name2;
		cin.ignore();
		w=LocateVex(G,name2);

		if(v == -1)
		{
			cout<<"该风景点不存在！删除失败！"<<endl;
			return;
		}
		DeleteArc(G,v,w);
		DeleteArc(G,w,v);
		cout<<"删除成功！"<<endl;
	}
}//DeleteGraph(ALGraph &G)

void PrintGraph(ALGraph G)
{
	//输出图中所有顶点名称
	if(G.vexnum == 0)
	{
		cout<<"  暂时无风景点!"<<endl;
	}

	for(int i=0; i < G.vexnum;i++)
	{
		cout<<i+1<<":";
		cout<<G.vertices[i].data<<endl;
	}
}// PrintGraph(ALGraph G)


void  ShortestPath(ALGraph G,int v0,int v1)
{
	ArcNode *p = G.vertices[v0].firstarc;
	int *weight = new int[G.vexnum],*vinfo = new int [G.vexnum],*result = new int[G.vexnum];
	int v = v0, minest = 0, num=0,j=0;
	bool  *flag = new bool[G.vexnum];
	for(int n = 0; n<G.vexnum; n++)
	{
		weight[n] = -1;
		vinfo[n] = -1;
		if( n != v0 )
		{
			flag[n] = false;
		}
		else
		{
			flag[n] = true;
		}
	}

	for( int i = 0; i < G.vexnum; i++ )                         
	{
		while(p)
		{
			if(p->adjvex != v0 && (weight[p->adjvex] == -1 || weight[p->adjvex] > minest + p->weight) )
			{
				weight[p->adjvex] = minest + p->weight;
				vinfo[p->adjvex] = v;
				
			}
			p = p->nextarc;
		}
		j=0;
        while( flag[j] == true || weight[j] == -1)
		{
			j++;
		}

		minest = weight[j];
		v=j;
		for(; j <G.vexnum ;j++ )
		{
			if( flag[j] != true && minest > weight[j] && weight[j] !=-1 )
			{
				minest = weight[j];
				v = j;
			}
		}

		flag[v] = true;
		
		p = G.vertices[v].firstarc;
	}
	if(vinfo[v1] == -1)
	{
		cerr<<"两点之间没有路径！"<<endl;
	}
	else
	{
		v = v1;
		while(v != v0)
		{
			result[num++] = vinfo[v];
			v = vinfo[v];
		}
	    cerr<<"距离："<<weight[v1]<<"   路径: ";
	    for(int j = num-1 ;j >=0; j--)		
			cerr<<G.vertices[result[j]].data<<"->";	
		cerr<<G.vertices[v1].data<<endl;
	}
	delete(weight);
	delete(vinfo);
	delete(result);
	
}//ShortestPath(ALGraph G,int v0,int v1)

void  AllPath(ALGraph G)
{
	int v, w, u, *range = new int[G.vexnum];
	int num = 0;
	char name1[20],name2[20];
	LinkQueue Q;
	bool  *visited = new bool[G.vexnum];  
	ArcNode *p;

	for(v=0;v<G.vexnum;++v)
	{
		visited[v]=false; // 置初值
	}
    

	InitQueue(Q); // 置空的辅助队列Q
	cout<<"起点：";			
	cin>>name1;			
	v = LocateVex(G,name1);

	if( v == -1 )					
	{							
		cerr<<"暂时无该风景点!"<<endl;
		delete(range);
		return;
	}			
	cout<<"终点：";
	cin>>name2;			
	w = LocateVex( G,name2 );          
			
	if( w == -1 )					
	{							
		cerr<<"暂时无该风景点!"<<endl;
		delete(range);
		return;
	}
     
	visited[w] = true;

     if(!visited[v]) // v尚未访问
     {        
		 visited[v]=true;
         EnQueue(Q,v); // v入队列


		 while( !QueueEmpty(Q) ) // 队列不空
		 {         
			 DeQueue(Q,u); // 队头元素出队并置为u

			 p = G.vertices[u].firstarc;
             range[num++] = u;
			 while( p )
			 { 
				 u=p->adjvex;

				 if(!visited[u]) // u为u的尚未访问的邻接顶点           
				 {           
					 visited[u] = true;  
					 EnQueue(Q,u); // u入队 
					 p=p->nextarc;					 					 
				 }
				 else
				 {				 
					 p = p->nextarc;
				 }
				     
				 if( u == w )									 
				 {						 		 					  						 
					 for (int j=0; j<num; j++)			 						 
					 {				 							
						   cerr<<G.vertices[ range[j] ].data<<"->";			 
					 }			 					 
					cerr<<G.vertices[w].data<<endl;
				}
			 }     
		 }   
	 }
}

//DFS(ALGraph G,int v1, int v2)
void  Initialization()
{
   //设置输出界面
	HANDLE   hStdout,hStdin;     
	COORD    coord ;   
    int i;
	SetConsoleTextAttribute(hCon,FOREGROUND_RED);

    hStdin=GetStdHandle(STD_INPUT_HANDLE);     
    hStdout=GetStdHandle(STD_OUTPUT_HANDLE);     
    coord.X=0;
	coord.Y=4;
    SetConsoleCursorPosition(hStdout,   coord);

    cerr<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━";

	for(i=5;i<=24;i++)
	{
		    coord.X=58;
	        coord.Y=i;
	        SetConsoleCursorPosition(hStdout,   coord);
		    cerr<<"┃";
	}
	SetConsoleTextAttribute(hCon,FOREGROUND_GREEN);	
    coord.X=23;
	coord.Y=2;
    SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"南京航空航天大学校园导游系统";
	cerr<<"\n\t\t\t(作者:040630127 李长刚)";
	coord.X=62;
	coord.Y=7;
	SetConsoleCursorPosition(hStdout,   coord);
	
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"显示景点名称(L)";
	coord.X=62;
	coord.Y=9;
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"景点简介(R)";
	coord.X=62;
	coord.Y=11;
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"最短路径查询(S)";
	coord.X=62;
	coord.Y=13;
	SetConsoleCursorPosition(hStdout,   coord);
    cerr<<"所有路径查询(A)";
	coord.X=62;
	coord.Y=15;
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"插入(I)";
	coord.X=62;
	coord.Y=17;
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"删除(M)";
	coord.X=62;
	coord.Y=19;
	SetConsoleCursorPosition(hStdout,   coord);
	cerr<<"退出(Q)";

}//Initialization()