schoolguide.cpp

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

#include  <iostream.h>     //引用标准头文件
#include  <stdlib.h>       //引用标准头文件
#include  <fstream.h>      //引用标准头文件
#include  <conio.h>        //引用标准头文件
#include  <iomanip.h>      //引用标准头文件
#include  <string.h>       //引用标准头文件
#include <windows.h>       //引用标准头文件
#include <wincon.h>        //引用标准头文件
#include  "ADT_Graph.h"    //引用自定义头文件
typedef int QElemType;     // 队列类型
#include  "LinkQueue.cpp"
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
//设置颜色所需要的

void InitGraph(ALGraph &G,fstream &file);
//从文件中读出信息并将其建成无向图
int  InsertVex(ALGraph &G,VNode v);
//向图中插入顶点
void InsertArc(ALGraph &G,ArcNode *a,int i);
//向图中第i+1个元素后插入边的信息a
int  LocateVex(ALGraph G,char u[]);
//定位名称为u的顶点，成功返回其下标，失败则返回-1
void DestroyGraph(ALGraph &G);
//销毁图，释放图中所有指针变量
void DeleteVex( ALGraph &G, VNode v );
//删除顶点，删除后对应的信息全部删除
void DeleteArc( ALGraph &G,int v,int w);
//单向删除边，即v->w的边
void DeleteGraph(ALGraph &G);
//根据用户的需要来删除信息
void InsertGraph(ALGraph &G);
//根据用户的需要来添加信息
void WriteToFile(ALGraph &G,fstream &file);
//将图的信息保存到文件中
void PrintGraph(ALGraph G);
//输出图中所有顶点名称
void  Initialization();
//输出界面
void  ShortestPath(ALGraph G,int v0,int v1);
//输出最短路径
void  AllPath(ALGraph G);
//输出所有路径


int main(void)
{
	//主函数
	char choice,scname[20],name1[20],name2[20];
	int i=0,w,v;
	ALGraph G;
	fstream  file;

    file.open("schgu.dat",ios::in|ios::out|ios::binary);
	file.clear();

    InitGraph(G,file);

    //从文件中读出信息并将其建成无向图
	HANDLE   hStdout,hStdin;     
	COORD    coord ;   
    hStdin=GetStdHandle(STD_INPUT_HANDLE);     
    hStdout=GetStdHandle(STD_OUTPUT_HANDLE);

	while(1)
	{
		system("cls");
		Initialization();

	    coord.X = 2;
	    coord.Y = 6;
        SetConsoleCursorPosition(hStdout,coord);

	    cout<<"Operation:";
        cin>>choice;
		choice = toupper(choice);

		switch(choice)
		{
		case 'L':
				PrintGraph(G);
				//输出图中所有顶点名称
				system("pause");
				break;
		case 'R':
		
			cout<<"请输入你要详细查询的景点名称：";		
			cin>>scname;        
			i = LocateVex(G,scname);
            //定位名称为u的顶点，成功返回其下标，失败则返回-1
			if( i == -1 )		
			{			
				cerr<<"暂时无该风景点!"<<endl;		
			}
		
			else		
			{			
				cerr<<G.vertices[i].data<<": "<<G.vertices[i].info<<endl;
				//输出顶点简介
			}
			system("pause");
			break;
		case 'M':		
			DeleteGraph(G);//根据用户的需要来删除信息		
			break;
		case 'I':		
			InsertGraph(G);//根据用户的需要来插入信息
			break;
		case 'S':
			cout<<"起点：";
			cin>>name1;
			w = LocateVex(G,name1);
			cout<<"终点：";
			cin>>name2;
			v = LocateVex(G,name2);
          
			if( w == -1 || v == -1 )		
			{			
				cerr<<"暂时无该风景点!"<<endl;		
			}
			else
			{
				ShortestPath(G,w,v);
			}
			system("pause");
			break;
		case 'A':
            AllPath(G);
			system("pause");
             break;
		case 'Q':
                WriteToFile(G,file);
				DestroyGraph(G);
				file.close();
				return 0;
				//将图的信息保存到文件中，并销毁图，退出程序
		}
	}
}//main()


void InitGraph(ALGraph &G,fstream &file)
{   //从文件中读出信息并将期间为原始的图
	VNode  v;
	ArcNode *a=NULL;

	G.vertices = new VNode[GRAPH_INIT_SIZE];
	G.vexnum = 0;
	G.graphsize = GRAPH_INIT_SIZE;
	//为图分配空间，并进行初始化
	file.clear();
	file.flush();

	while(!file.eof())
	{
		if( file.read( ( char* )&v,sizeof( VNode ) ) )
		{
			v.firstarc = NULL;
			InsertVex(G,v);
            //读出一个顶点信息，并将其插入到图中
			for( int i = 1; i <= v.arcnum; i++)
			{
				a = new ArcNode[1];	
				file.read( ( char* )a, sizeof( ArcNode ) );
				a->nextarc = NULL;
				InsertArc( G,a,G.vexnum-1 );
				//读出该顶点所有的边的信息，并将其插入到该节点后
			}
		}
	}
}//void InitGraph(ALGraph &G,fstream &file)


int InsertVex(ALGraph &G,VNode v)
{
	//向图中插入顶点v
	ALGraph G1;
	if(LocateVex(G,v.data) != -1)
	{
		//存在该点则插入不成功
		cout<<"改点已存在!"<<endl;
		return 0;
	}
    
	if( G.vexnum < G.graphsize )
	{
		strcpy( G.vertices[G.vexnum].data,v.data );
		strcpy( G.vertices[G.vexnum].info,v.info );
		G.vertices[G.vexnum].arcnum=0;
		G.vertices[G.vexnum].firstarc=NULL;
		G.vexnum++;
	}
	//当此时顶点个数小于此时分配的空间时，直接插入

	if( G.vexnum == G.graphsize )
	{
		G1.vertices = new VNode[GRAPHINCREMENT+G.graphsize];

		for(int i = 0;i < G.graphsize; i++)
		{
			strcpy( G1.vertices[i].data,G.vertices[i].data );
			strcpy( G1.vertices[i].info,G.vertices[i].info );
			G1.vertices[i].arcnum = G.vertices [i].arcnum;
            G1.vertices[i].firstarc = G.vertices [i].firstarc;
		}

 		strcpy( G1.vertices[G.vexnum].data,v.data );
		strcpy( G1.vertices[G.vexnum].info,v.info );
		G1.vertices[G.vexnum].arcnum=0;
		G1.vertices[G.vexnum].firstarc=NULL;
		
		delete( G.vertices );
		G.graphsize = GRAPHINCREMENT+G.graphsize;
		G.vexnum++;
		G.vertices = G1.vertices;
	}
	//当此时顶点个数等于此时分配的空间时，则需重新申请空间，然后插入插入

	return 1;
}//InsertVex(ALGraph &G,VNode v)


void InsertArc(ALGraph &G,ArcNode *a,int i)
{ //向图中第i+1个元素后插入边的信息a

	ArcNode *p=G.vertices[i].firstarc,*q=NULL;
	
	while( p )
	{
		if( p->adjvex > a->adjvex )
		{
			break;
		}
		else
		{
			if(p->adjvex == a->adjvex)
			{
				cerr<<"该边已存在！"<<endl;
				return;
			}
			q = p;
			p = p->nextarc;
		}
	}//寻找应当插入的位置

	a->nextarc = p;
	if(q != NULL)
	{
		q->nextarc=a;
	}
	else
	{
		G.vertices[i].firstarc=a;
	}
	//插入
	G.vertices[i].arcnum++;
	//该顶点的边数加一
}//InsertArc(ALGraph &G,ArcNode *a,int i)


int LocateVex(ALGraph G,char u[])
{ 
	//定位名称为u的顶点，成功返回其下标，失败则返回-1
	if(!G.vertices){
		return -1;
	}

	for(int i=0;i<G.vexnum;i++)
	{
		if(strcmp(G.vertices[i].data,u)==0)
			return i;
	}
	return  -1;
}// LocateVex(ALGraph G,char u[])


void  DestroyGraph(ALGraph &G)
{
	//销毁图，释放图中所有指针变量  
	if(!G.vertices)   return;

	ArcNode  *p1,*p2;

	for(int i=0;i<G.vexnum;i++){
		p1=G.vertices[i].firstarc;

		while(p1 != NULL){
			p2=p1->nextarc;
			delete(p1);
			p1=p2;
		}
	}//释放所有顶点后边的边指针

	delete(G.vertices);
    //释放指向所有顶点的指针
}//DestroyGraph(ALGraph &G)
 

void DeleteVex( ALGraph &G, char v[] )
{
	//删除顶点，删除后对应的信息全部删除
	int i,k;
	ArcNode *p;
	i=LocateVex( G,v);
    k=i;
	if(i == -1)
	{
		cout<<"该风景点不存在！删除失败！"<<endl;
		return;
	}

	ArcNode *a = G.vertices[i].firstarc;
	
	if(i != -1)
	{
		while(a != NULL)
		{
			DeleteArc(G,a->adjvex,i);
			G.vertices[i].firstarc = a->nextarc;
			delete( a );
			a = G.vertices[i].firstarc;
		}//删与之有关系的边

		for(;i < G.vexnum; i++)
		{
			G.vertices[i]=G.vertices[i+1];
		}
		G.vexnum--;//删点

		for(int j=0; j < G.vexnum; j++)
		{
			p = G.vertices[j].firstarc;
			while(p)
			{
				if(p->adjvex > k)
				{
					p->adjvex--;
				}
				p = p->nextarc;
			}
		}
	}
}//DeleteVex( ALGraph &G, char v[] )


void DeleteArc( ALGraph &G,int v,int w)
{
	//单向删除边，即v->w的边
	ArcNode  *p = G.vertices[v].firstarc,*q=NULL;
	if(p == NULL )
	{
		return;
	}

	while( p != NULL )
	{
		if(p->adjvex == w)
		{
			break;
		}
		else
		{
			q=p;
			p=p->nextarc;           
		}
	}
    //找边
	if(p != NULL ){
		
		if(q != NULL )	
		{		
			q->nextarc = p->nextarc;	
		}
	
		else	
		{		
			G.vertices[v].firstarc = p->nextarc;	
		}
		
		G.vertices[v].arcnum--;	
		delete(p);
	}
	//删边
}//DeleteArc( ALGraph &G,int v,int w)


void WriteToFile(ALGraph &G,fstream &file)
{
	//将图的信息保存到文件中
	ArcNode *p;
	file.close();
	file.open("schgu.dat",ios::out|ios::binary);
	//清空以前的信息

	file.clear();
	file.flush();
	file.seekp(0,ios::beg);
	if( G.vexnum == 0)  return;
	for( int i = 0;i < G.vexnum;i++)
	{
		file.write((char*)&G.vertices[i],sizeof(VNode));
		//将顶点信息写入文件
		p = G.vertices[i].firstarc;