202715.cpp

数据结构（清华版）

#include<iostream.h>
#include<fstream.h>
const MaxVexNum=20;
const Infinty=-1;
typedef char VexType;
typedef int ArcType;
//创建邻接矩阵存储结构的结构体=======================================
struct MGraph
{
	VexType vexs[MaxVexNum+1];
	ArcType arcx[MaxVexNum+1][MaxVexNum+1];
	int kind,vexnum,arcnum;
};
//创建顶点查找函数===================================================
int LocateVex(MGraph &G,VexType V)
{
	int i;
	for(i=G.vexnum;i>0&&G.vexs[i]!=V;i--);
	return i;
}
//邻接矩阵存储结构创建图=============================================
void CreateGraph(MGraph &G,char fn[])
{
	int i,j;VexType c,u,v;ArcType w;
	ifstream f;
	f.open(fn,ios::nocreate);
	if(!f){G.vexnum=0;return;}
	f>>G.kind;G.vexnum=0;
	while(true)
	{
		f>>c;if(c=='#') break;
		G.vexnum++;
		G.vexs[G.vexnum]=c;
	}
	for(i=1;i<=G.vexnum;i++)
		for(j=1;j<=G.vexnum;j++)
			G.arcx[i][j]=Infinty;
		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++;G.arcx[i][j]=w;
		if(G.kind>=3){ G.arcx[j][i]=w;G.arcnum++;}
		
	}
	f.close();
}
//创建删除节点函数===================================================
void DeleteVex(MGraph &G,VexType v)
{
	int m,n,i,j;
	char t;
	n=G.vexnum;
    if((m=LocateVex(G,v))<0) return ;
	for ( j=1;j<=G.vexnum;j++)//改变弧数
	{
		if(G.arcx[m][j]!=Infinty) G.arcnum--;
		if(G.arcx[j][m]!=Infinty) G.arcnum--;
	}
    t=G.vexs[m];G.vexs[m]=G.vexs[n]; G.vexs[n]=t;//将删除顶点交换到最后一个顶点
    for( i=1;i<=n;i++)
	{
   
		G.arcx[i][m]=G.arcx[i][n];
        G.arcx[m][i]=G.arcx[n][i]; //改变变得位置
	}
    G.arcx[m][m]=Infinty;
    G.vexnum--;

	/*int i,j,k;
	i=LocateVex(G,v);
	cout<<i<<endl;
	for (j=1;j<=G.vexnum;j++)
	{
		if(G.arcx[i][j]!=Infinty) G.arcnum--;
		if(G.arcx[j][i]!=Infinty) G.arcnum--;
	}
	for (j=i+1;j<=G.vexnum;j++)
		for(int m=0;m<G.vexnum;m++)
		{
			G.arcx[j-1][m]=G.arcx[j][m];
			G.arcx[m][j-1]=G.arcx[m][j];
		    G.arcx[j-1][j-1]=-1;
		}
	for (j=i+1;j<=G.vexnum;j++) G.vexs[j-1]=G.vexs[j];
	G.vexnum--;*/
}
//
void OutputGraph(MGraph &G)
{
	int i, j;
	if (G.vexnum==0)
	{
		cout<<"   "<<endl;
		return;
	}
	cout<<"           "<<"  顶点数="<<G.vexnum<<"   弧数为="<<G.arcnum<<"     顶点：";
	for (i=1;i<=G.vexnum;i++) cout<<G.vexs[i]<<' ';
	cout<<endl<<"各顶点的出弧："<<endl;
	for (i=1;i<=G.vexnum;i++)
	{
		cout<<"           "<<"顶点"<<G.vexs[i]<<endl;
		for(j=1;j<=G.vexnum;j++)
			if(G.arcx[i][j]!=Infinty)
				cout<<"           "<<"<"<<G.vexs[i]<<','<<G.vexs[j]<<">  "<< G.arcx[i][j]<<endl;
	}
}


//创建主函数 ========================================================
void main()
{
	MGraph G;
	CreateGraph(G,"715.txt");
	cout<<"图结构为："<<endl;
	OutputGraph(G);
	cout<<endl<<endl;
    cout<<"删除节点后图结构为： "<<endl;
	DeleteVex(G,'a');
	OutputGraph(G);
}