createdg_2.cpp

c语言数据结构源代码（全）相当经典

//CreateDG.cpp 
//构造图的十字链表
# include <iostream.h>
# include <malloc.h>
# include <conio.h>

# define MAX_VERTEX_NUM 20
# define OK 1
typedef int VertexType;
typedef int InfoType;

typedef struct ArcBox		//定义 ArcBox
{  int tailvex,headvex;
   struct ArcBox *hlink,*tlink;
   InfoType info;
}ArcBox;

typedef struct VexNode		//定义 VexNode
{  VertexType data;
   ArcBox *firstin,*firstout;
}VexNode;

typedef struct				//定义 OLGraph
{  VexNode xlist[MAX_VERTEX_NUM];
   int vexnum,arcnum;
}OLGraph;

int LocateVex(OLGraph G,int v)	//确定v在G中的位置
{
	return(v);
}

int CreateDG(OLGraph &G)	//CreateDG() 子函数
{  int IncInfo,i,j,k,v1,v2;
   cout<<endl<<"Please input the number of G.vexnum 顶点数目 (eg, 4): ";
   cin>>G.vexnum;			//输入顶点数目
   cout<<"Please input the number of G.arcnum 弧的数目 (eg, 4): ";
   cin>>G.arcnum;			//输入弧的数目
   cout<<"Please input IncInfo 弧的信息 (0 for none)          : ";//输入弧的信息
   cin>>IncInfo;			//if no information, input 0
   for(i=0;i<G.vexnum;++i)				//构造表头向量
       {	G.xlist[i].data=i+1;		//输入顶点值
			G.xlist[i].firstin=NULL;	//初始化指针
			G.xlist[i].firstout=NULL;	//初始化指针
       }
   cout<<"Plese input 弧 arc(V1-->V2), For example: arc(1,3),arc(2,4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	//input arc(v1,v2)
   {	cout<<endl<<"Please input the "<<k+1<<"th arc's v1 弧头 [1.."<<G.vexnum<<"] :";
		cin>>v1;				//输入弧头
		cout<<"Please input the "<<k+1<<"th arc's v2 弧尾 [1.."<<G.vexnum<<"] :";
		cin>>v2;				//输入弧尾
		i=LocateVex(G,v1);	//确定v1在G中的位置
		j=LocateVex(G,v2);	//确定v2在G中的位置
		while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//如果弧头或弧尾不合法,重新输入
		{   cout<<"Please input Again the "<<k+1<<"th arc's v1 弧头[1.."<<G.vexnum<<"] :";
			cin>>v1;
			cout<<"Please input Again the "<<k+1<<"th arc's v2 弧尾[1.."<<G.vexnum<<"] :";
			cin>>v2;
			i=LocateVex(G,v1);	//确定v1在G中的位置
			j=LocateVex(G,v2);	//确定v2在G中的位置	
		} //while end
		ArcBox *p;
		p=(ArcBox *)malloc(sizeof(ArcBox));	//assign memory
		if(!p)
		{	cout<<"Overflow!";	//若没有足够空间则退出
			return (0);
		}
		p->tailvex=i;			//对弧结点的尾域赋值
		p->headvex=j;			//对弧结点的头域赋值
		p->hlink=G.xlist[j].firstin;	//对弧结点的链域赋值
		p->tlink=G.xlist[i].firstout;	//对弧结点的链域赋值
		p->info=NULL;			//对弧结点相关信息指针域赋值
		G.xlist[j].firstin=G.xlist[i].firstout=p;
		if(IncInfo)
		{	cout<<"Please input the info :";
			cin>>p->info;		//如果弧含有相关信息，则输入
		}
   } //for end
   return (OK);
} //CreateDG() end

void main()				//main() 函数
{   OLGraph G;
    cout<<endl<<endl<<"CreateDG.cpp";
    cout<<endl<<"============"<<endl;
    if(CreateDG(G))		//调用 CreateDG() 
       cout<<endl<<"Create OLGraph success!"; 
    cout<<endl<<endl<<"...OK!...";
    getch();
} //main() end