createdg_1.cpp

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

//CreatDG.cpp
//构造图的邻接表
# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

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

typedef struct ArcNode		//定义 ArcNode
{  int adjvex;
   struct ArcNode *nextarc;
   InfoType info;
}ArcNode;

typedef struct VNode		//定义 VNode
{  VertexType data;
   ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct				//定义 ALGraph
{  AdjList vertices;
   int vexnum,arcnum;
   int kind;
}ALGraph;

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

int CreateDG(ALGraph &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.vertices[i].data=i+1;		//初始化顶点值
			G.vertices[i].firstarc=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;
	   //cout<<"Please input Again the "<<k+1<<"th arc's weight 权      :";
	   //cin>>w;
	   i=LocateVex(G,v1);	//确定v1在G中的位置
       j=LocateVex(G,v2);	//确定v2在G中的位置	
       } //while end
	   ArcNode *p;
       p=(ArcNode *)malloc(sizeof(ArcNode));	//分配内存
       if(!p)
       {	cout<<"Overflow!";					//如果没有足够的空间,则退出
			return (0);
       }
       p->adjvex=j;					//对弧结点的弧顶点数据域赋值
       p->nextarc=G.vertices[i].firstarc;	//对弧结点下一条弧指针域赋值
       p->info=NULL;				// 对弧结点相关信息指针域赋值
       G.vertices[i].firstarc=p;	// 将弧结点插入到对应的单链表
       if(IncInfo)
	   {	//printf("Please input the info :");	
			//scanf("%d%",&p->info);
			cout<<"Please input the info :";
			cin>>p->info;
		}
   } //for end
   return (OK);
} //CreateDG() end

void ShowMGraph(ALGraph G)	//输出图 G
{	int i;
	ArcNode *p;
	for(i=0;i<G.vexnum;++i)
		{	for(p->nextarc=G.vertices[i].firstarc;p->nextarc!=NULL;p=p->nextarc)
				printf("\narc(%d,%d)  ",i+1,p->adjvex);
		}
}

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