202723.cpp

数据结构（清华版）

#include<iostream.h>
#include<fstream.h>
const MaxVexNum=20;
const Infinty=-1;
typedef char VexType;
typedef int ArcType;
//创建结构体======================================================================================
typedef struct ArcNode
{
	int adjvex;ArcType info;ArcNode *nextarc;
}*ArcPtr;

struct VexNode
{ VexType data;ArcPtr firstarc;};

struct ALGraph
{VexNode vexs[MaxVexNum+1];
int kind,vexnum,arcnum;
};
//创建顶点查找函数==================================================================================
int LocateVex(ALGraph &G,VexType V)
{
	int i;
	for(i=G.vexnum;i>0 && G.vexs[i].data!=V;i--);
	return i;
}


//邻接表存储结构创建图=================================================================================
void CreateGraph(ALGraph &G,char fn[])
{
	int i,j;VexType c,u,v;
	ArcPtr p;ifstream f;ArcType w;
	f.open(fn,ios::nocreate);
	if(!f){G.vexnum=0;return;}
	f>>G.kind;i=0;
	while(true)
	{
		f>>c;if(c=='#') break;
		i++;G.vexs[i].data=c;
		G.vexs[i].firstarc=NULL;
	}
	G.vexnum=i;
	G.arcnum=0;
	while(true)
	{
		f>>u>>v; if(u=='#'||v=='#') break;
		i=LocateVex(G,u);
		if(i==0) continue;
		j=LocateVex(G,v);
		if(j==0||j==i) continue;
		if(G.kind==1||G.kind==3) w=1;
		else f>>w;
		G.arcnum++;p=new ArcNode;
		p->adjvex=j;p->info=w;
		p->nextarc=G.vexs[i].firstarc;
		G.vexs[i].firstarc=p;
		if(G.kind<=2) continue;
		G.arcnum++;p=new ArcNode;
		p->adjvex=i;p->info=w;
		p->nextarc=G.vexs[j].firstarc;
		G.vexs[j].firstarc=p;
	}
	
	f.close ();
}

//输出图函数==============================================================================================
void OutputGraph(ALGraph &G)  
{
	int i,j;ArcPtr p;
	if(G.vexnum ==0)   
	{cout<<"空图"<<endl;return;}
	cout<<"          "<<"顶点数="<<G.vexnum <<"   弧数="<<G.arcnum <<"    顶点:";  
	for(i=1;i<=G.vexnum ;i++)cout<<G.vexs [i].data<<',';
	cout<<endl<<"各顶点的出弧:"<<endl;
	for(i=1;i<=G.vexnum ;i++)
	{
		cout<<"      "<<"顶点"<<G.vexs[i].data<<endl;
		for(p=G.vexs [i].firstarc;p;p=p->nextarc )
			cout<<"      "<<"  <"<<G.vexs [i].data<<','<<G.vexs [p->adjvex].data<<">:"<<p->info <<endl;
	}
	cout<<"      "<<"各顶点的入弧:"<<endl;
	for(i=1;i<=G.vexnum ;i++)
	{
		cout<<"      "<<"顶点"<<G.vexs[i].data <<endl;
		for(j=1;j<=G.vexnum ;j++)
			for(p=G.vexs [j].firstarc;p;p=p->nextarc)
				if(G.vexs[p->adjvex].data ==G.vexs[i].data )
					cout<<"      "<<"  <"<<G.vexs [j].data <<','<<G.vexs [i].data <<">:"<<p->info <<endl;
	}
	
}
//创建链队列结构体===================================================================
typedef int QElemtype;
typedef struct QNode
{
	QElemtype data;QNode *next;
} *LQueuePtr;
struct LQueue
{
	LQueuePtr front,rear;
};
void QueueInit(LQueue &Q)
{
	Q.front=new QNode;
	Q.front->next=NULL;
	Q.rear=Q.front;
}
//创建入列函数======================================================================
void Enqueue(LQueue &Q,QElemtype e)
{
    LQueuePtr p;
	p=new QNode;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
//创建出队函数======================================================================
bool Dequeue(LQueue &Q,QElemtype &e)
{
	LQueuePtr p;
	if (Q.front==Q.rear) return false;
	p=Q.front;
	Q.front=p->next;
	e=Q.front->data;
	delete p;
	return true;
}
//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
int PathBFS(ALGraph G,int i,int j)
{
	int u,k;LQueue Q;ArcPtr p;
	int visited[MaxVexNum+1];
	QueueInit(Q);
	Enqueue(Q,i);
	while(Dequeue(Q,u))
	{
		Dequeue(Q,u);
		visited[u]=1;
		for(p=G.vexs[i].firstarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			if(k==j) return 1;
			if(!visited[k]) Enqueue(Q,k);
		}
	}
	return 0;
}
//主函数===================================================================================================
void main()
{
	ALGraph G;
	cout<<"邻接表形式存储的图结构："<<endl;
	CreateGraph(G,"723.txt");
	OutputGraph(G); 
	cout<<endl<<endl;
	if(PathBFS(G,1,3)==1) cout<<"有路径"<<endl;
	else cout<<"没有路径"<<endl;
	
}