05180220刘议庠无向图.cpp

图的数据结构的实现。本内容提纲了完整的代码。

/*图实验报告
姓名:刘议庠  学号:05180220    专业:05级  信息与计算科学
一．	实验内容：建立一个图，实现其存储功能，并通过土求出其最小生成树。
二．	实验体会：
1.	本程序主要参照书本完成。
2.	本实验采用邻接表对图进行存储，建立一个顶点类，一个边类，
每一个顶点定义一个边指针，从而以链表的形式将于这个结点相连的边连起来。
3.	图的插入操作是关键，通个插入建立多条链表，以后的操作就于链表相似。
4.	该图以深度遍历的方式实现图的遍历。
5.	最小生成树的建立比较难实现，其中含有多重循环，比较难实现，而书本
又是以邻接距阵的形式的讲解的，不易参考，故该函数比较混乱，其中还有不少问题。
6.	要实验图的遍历和最小生成树，必须保证该图为连通图，但由于时间有限，
该程序没有实现判断是否为连通图的函数。
*/
//本程序采用邻接表完成
//以顶点为表头指针建立的多条链表很关键
//最小生成树的最难实现(????????/?)
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<iomanip.h>
#include<stdlib.h>
//static	int numvertex=0;//当前顶点数
const int defaultsize=10;//缺省顶点个数
class graph;//图的前视定义
class edge//边的定义
{
	friend class graph;
	int dest;//边的一个顶点位置，即为数组中下标
	int cost;//权值
	edge *link;//将这些边通过指针连接起来，就成了一个顶点发出的一条链
	edge(){}//！！！！！！！！！！！所以在顶点里定义了一个edge指针
	edge(int a,int b): dest(a),cost(b),link(NULL){}
	int operator !=(const edge &a)const{return dest!=a.dest;}//不考虑自循环这种情况
};
class vertex//顶点的定义
{
	friend class graph;
	friend class edge;
	char data;//顶点的名字
	edge *adj;//顶点里定义了一个edge指针
};
class graph
{
private:
	vertex *nodetable;//顶点表
	int maxvertex;//最大顶点数
	int numvertex;//当前顶点数
	int numedge;//当前边数
public:
	graph(){}
	graph(int sz);
	~graph();
	int graphemphy()const{return numvertex==0;}//pan kong 
    int graphfull()const{return numvertex==maxvertex;}//pan man 
	int numberofvertex(){return numvertex;}
	int numberofedge(){return numedge;}
	char getvalue(int i)//取位置为i的顶点的值
	{return i>=0&&i<numvertex?nodetable[i].data:NULL;}
	int getvertexpos(const char &a);//找到a在图中的位置，即相当于在数组中的下标值
	void insertvertex(const char &a);//在图中插入一个顶点
	void removevertex(int v);//删除一个顶点
	edge * insertedge(int v1,int v2,int weight);//插入一条边
	void removevertex(int v1,int v2);//删除一条边
	int getweight(int v1,int v2);//得到一条边上的权值
	int getfirstneighbor(int v);//取顶点v的第一个邻接点
	int getnextneighbor(int v1,int v2);//取顶点v1的某邻接点v2的下一个邻接点
	//*****************************************
	void DFS();
	void DFS(int a,int b[]);//连通图的深度搜索遍历
	void prim();
};
graph::graph(int a=defaultsize):maxvertex(a),numedge(0),numvertex(0)//构造函数
{
   int n,e,k,j,weight;char name,tail,head;
   nodetable =new vertex[maxvertex];cout<<"请输入插入顶点的个数!!"<<endl;
   cin>>n;//插入的顶点个数
   for(int i=0;i<n;i++)
   {cout<<"第  "<<i+1<<"条顶点的名字"<<endl;cin>>name;insertvertex(name);}
   cout<<"边的条数"<<endl;cin>>e;//插入边的条数
   for(i=0;i<e;i++)
   {cout<<"第"<<i+1<<"条边"<<endl;
	   cin>>tail>>head;cout<<"请输入权值!!!"<<endl;
	   cin>>weight;
	   k=getvertexpos(tail);j=getvertexpos(head);
	   insertedge(k,j,weight);
   }
}
graph::~graph()//析构函数
{
    for(int i=0;i<numvertex;i++)//删除各顶点链表中的结点
	{
		edge *p=nodetable[i].adj;
		while(p!=NULL)
		{nodetable[i].adj=p->link;delete p;p=nodetable[i].adj;}
	}//头指针指向的边随着边的一个一个删除在逐步往后移,从而将这条边的所以结点删除
	delete[] nodetable;//删除顶点数组
}
int graph::getvertexpos(const char&vertex)//找一个给定顶点的位置
{
	for(int i=0;i<numvertex;i++)
		if(nodetable[i].data==vertex) return i;
		return -1;
}
int graph::getfirstneighbor(int v)//给出一个顶点的位置,找其链表第一个结点(第一条边)的位置
{
	if(v!=-1)
	{
		edge *p=nodetable[v].adj;
		if(p!=NULL) return p->dest;
	}
	return -1;
}
int graph::getnextneighbor(int v1,int v2)//给出一个顶点的位置和起一条边的位置,
{                                       //找其下一个结点(下一条边)的位置
	if(v1!=-1)
	{
		edge *p=nodetable[v1].adj;
		while(p!=NULL)
		{
			if(p->dest==v2&&p->link!=NULL) return p->link->dest;
			else p=p->link;
		}
	}
	return -1;
}
int graph::getweight(int v1,int v2)//返回顶点为v1和v2的边的权值
{
	if(v1!=-1&&v2!=-1)
	{
		edge *p=nodetable[v1].adj;//cout<<"进入权值"<<endl;
		while(p!=NULL)
		{//cout<<"进入权值"<<endl;
			if(p->dest==v2){return p->cost;}
			else p=p->link;
		}
	}
    return 0;
}
void graph::insertvertex(const char &a)//插入一个顶点
{//cout<<"进入插入顶点函数"<<endl;
	nodetable[numvertex].data=a;
	nodetable[numvertex].adj=NULL;
	numvertex++;
}
edge * graph::insertedge(int a,int b,int c)//插入一条边,需在两个顶点的链表中加入边
{//cout<<"进入插入边函数"<<endl;
//	cout<<a<<b<<endl;//*****************
    if(a<=numvertex&&b<=numvertex&&a>=0&&b>=0)
		{
            edge *pt=nodetable[a].adj;  edge *pr=nodetable[b].adj;
		    edge *pointer1=nodetable[a].adj;edge *pointer2=nodetable[b].adj;
			edge *p1=new edge;p1->dest=b;p1->cost=c;p1->link=NULL;
			edge *p2=new edge;p2->dest=a;p2->cost=c;p2->link=NULL;
			if(nodetable[a].adj==NULL)
			{
				nodetable[a].adj=p1;//cout<<"p  kong";
			}
			else
			{
				while(pointer1->link!=NULL)
				{
					pointer1=pointer1->link;//cout<<"p  buwei kong";
				}
				pointer1->link=p1;
			}
			if(nodetable[b].adj==NULL)
			{
				nodetable[b].adj=p2;//cout<<"p  kong";
			}
			else
			{
				while(pointer2->link!=NULL)
				{
					pointer2=pointer2->link;//cout<<"p  buwei kong";
				}
				pointer2->link=p1;
			}

		/*	{p=p1;}
		    int i=0,j=0;
		    edge *p1=new edge;//p1->dest=b;p1->cost=c;p1->link=NULL;
		     whilwhile(nodetable[a].adj!=NULL)
			 {i=1;nodetable[a].adj=nodetable[a].adj->link;cout<<"*****88888888888";}
			 nodetable[a].adj=p1;nodetable[a].adj->dest=b;nodetable[a].adj->cost=c;
			 nodetable[a].adj->link=NULL;
			 if(i==0){cout<<"头指针不为空"<<endl;}//p=nodetable[a].adj;}
			 else  {cout<<"头指针还原"<<endl;nodetable[a].adj=pt;}
		     //edge *pp=nodetable[b].adj;
		     edge *p2=new edge;
			 p2->dest=a;p2->cost=c;p2->link=NULL;
		      while(nodetable[b].adj!=NULL)
			 {j=1;nodetable[b].adj=nodetable[b].adj->link;cout<<"*****88888888888";}
			 nodetable[b].adj=p2;
			 if(j==0){cout<<"头指针不为空"<<endl;}//p=nodetable[a].adj;}
			 else  {cout<<"头指针还原"<<endl;nodetable[b].adj=pr;}
			  //if(nodetable[a].adj!=NULL)cout<<"jflskjf";*/
		}
	return nodetable[a].adj;
}
void graph::DFS()
{
	int *a=new int[numvertex];
	for(int i=0;i<numvertex;i++) a[i]=0;
	DFS(0,a);
	delete []a;
}
void graph::DFS(int a,int b[])
{
	cout<<getvalue(a)<<"    ";
	b[a]=1;
	int w=getfirstneighbor(a);
	while(w!=-1)
	{
		if(!b[w])DFS(w,b);
		w=getnextneighbor(a,w);
	}
}
void graph::prim()
{
	int *a=new int[numvertex];
	int *b=new int[numvertex];
	int v=0;int key=0;char *mintree=new char[numvertex];
    mintree[0]= nodetable[0].data;
	for(int e=1;e<numvertex;e++){mintree[e]='\0';}
	//edge *p=nodetable[v].adj;
	for(int i=0;i<numvertex;i++)//将两个数组初始化
	{b[i]=0;}b[0]=-1;
	for(int j=1;j<numvertex;j++)
	{
    //	edge *p=nodetable[key].adj;
	     for(int i=0;i<numvertex;i++)//将两个数组初始化
		 {a[i]=1000;}int tt=1;
    	while(nodetable[key].adj!=NULL)
		{
           a[nodetable[key].adj->dest]=getweight(key,nodetable[key].adj->dest);
		   cout<<"%%%"<<a[nodetable[key].adj->dest]<<"//以便理解最小二叉树的生成!!"<<endl;
		   nodetable[key].adj=nodetable[key].adj->link;tt=0;
		}
	//	if(tt){}
		int t=1000;
     	for(i=1;i<numvertex;i++)
		{
	    	if(t>a[i]&&b[i]==0)
			{t=a[i];key=i;}
		}cout<<key<<endl;
	    if(key){mintree[j]= nodetable[key].data;b[key]=-1;}
	}
	for(int k=0;k<numvertex;k++)cout<<mintree[k]<<"    ";
}
void main()
{
	cout<<"首先建立一个图!!!!"<<endl;
    	graph tu(100);
//	cout<<"这条边的权值为    "<<tu.getweight(1,0);//得到一条边的权值
//	cout<<"这条边的权值为    "<<tu.getweight(0,2);
	
	cout<<endl;
	//插入边函数连续的问题,lianbiao meiwancheng
	char a,b;
	do{
	    cout<<"              １．建立一个图"<<endl;
	    cout<<"　　　　　　　２. 深度遍利"<<endl;
	    cout<<"　　　　　　　３．输出边的权值"<<endl;
	    cout<<"　　　　　　　４．显示土图的状态"<<endl;
    	cout<<"　　　　　　　５．输出最小生成树(首先保证图连通!!!)"<<endl;
    	cout<<"              ６．退出"<<endl;
 		int i;cin>>i;
		switch(i)
		{
        	case 1:
	          cout<<"图已经建立!!!"<<endl;
			break;			
    	case 2:
			tu.DFS();//深度优先遍利
			cout<<endl;
			break;
    	case 3: 
			cout<<"请输入要输出的顶点值"<<endl;
			cin>>a;cin>>b;
			cout<<"这条边的权值为    "<<tu.getweight(tu.getvertexpos(a),tu.getvertexpos(b));
			cout<<endl;
			break;
    	case 4:
			if(tu.graphemphy())cout<<"图为空!!!        ";
			else cout<<"图不为空!!!";
			if(tu.graphfull())cout<<"图为满!!!"<<endl;
			else cout<<"图没有满!!!"<<endl;
				break;
    	case 5:
			tu.prim();//输出最小生成树
			cout<<endl;
            break;
    	case 6:
			exit(0);
			break;
		}
	}while(1);
}