202716.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 DeleteVex(ALGraph &G,VexType v)
{
	int i,j;bool found;
	ArcPtr p,q;
	i=LocateVex(G,v); 
	if(i<=0) return;
	p=G.vexs[i].firstarc;
	while(p)        
	{
		q=p;
		p=p->nextarc ;
		delete q;
		G.arcnum --;  
	}
	G.vexs [i] =G.vexs [G.vexnum ];
	G.vexs[G.vexnum].data ='X';
	G.vexnum --;      
	for(j=1;j<=G.vexnum ;j++) //删除弧操作    
	{
		found=false;
		p=NULL;q=G.vexs[j].firstarc ;
		while(q&&!found)
		{   
			if(q->adjvex==i)found=true;
			else 
			{
				if(q->adjvex==G.vexnum +1)q->adjvex =i; 
				else p=q;q=q->nextarc ;
			}
		}
		
		if(!found)continue;   
		if(p)p->nextarc=q->nextarc  ;  
		else G.vexs[j].firstarc =q->nextarc ;
		delete q;
		G.arcnum --;   
	}	
	for(j=1;j<=G.vexnum ;j++)
	{
		p=NULL;q=G.vexs[j].firstarc ;
		while(q)
		{   
			if(q->adjvex==G.vexnum +1)q->adjvex =i; 
			else
			{
				p=q;q=q->nextarc ;
			}	
		}
	}
} 
//输出图函数==============================================================================================
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;
	}
	
}

//主函数===================================================================================================
void main()
{
	ALGraph G;
	cout<<"邻接表形式存储的图结构："<<endl;
	CreateGraph(G,"716.txt");
	OutputGraph(G); 
	cout<<endl<<endl;
	cout<<"删除节点后图结构："<<endl;
	DeleteVex(G,'A');
	OutputGraph(G);
}