e7_14.cpp

邻接表的建立以及各种功能的源代码

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define ING 100
int visited[10];             /*访问标志数组*/
typedef struct ArcCell{
int adj;               /*顶点关系类型，用1表示相邻，0表示不相邻*/
}ArcCell,**AdjMatrix;       /*邻接矩阵*/

typedef struct type{	
	char data[3];        /*顶点值*/
	struct type *next;   /*顶点的下一个指针*/
}VertexType;

typedef struct{
	VertexType *vexs;   /*顶点向量*/
	AdjMatrix arcs;     /*邻接矩阵*/
	int vexnum,arcnum;  /*图的顶点数和边数*/
}MGraph;

void InitGraph(MGraph *G)       /*初始图*/
{ int i,nu,mu;
 printf("\n输入顶点的个数和（边）弧的个数：");
  scanf("%d%d",&nu,&mu);
 G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
  for(i=0;i<nu;i++)                            /*分配邻接矩阵空间*/
      G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
 G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/
 G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/
}

void InsertGraph(MGraph *G,int i,VertexType e)
{
 if(i<0||i>G->vexnum) 
return;
  G->vexs[i].next=e.next;
  strcpy(G->vexs[i].data,e.data);
}


int Locate(MGraph G,VertexType v1)        /*确定v1在图顶点中的位置*/
{ int i;
	for(i=0;i<G.vexnum;i++)
		 if(strcmp(v1.data,G.vexs[i].data)==0)
 return i;
  return -1;
}

void CreateUND(MGraph *G)   /*采用数组（邻接矩阵）和邻接表表示无向图*/
{
int i,j,k,*p,d,w;
 VertexType v1,v2,*q2,*q;
 p=(int *)malloc(G->vexnum*sizeof(int)); 
 for(i=0;i<10;i++) p[i]=0;
    for(i=0;i<G->vexnum;++i)             /*初始邻接表*/
 {
 for(j=0;j<G->vexnum;++j) G->arcs[i][j].adj=ING;}
    for(k=0;k<G->arcnum;++k)
    {
printf("\n输入第 %d 条（边）弧相对的两个顶点值:\n",k+1);
       d=0;
  scanf("%s%s",v1.data,v2.data);        /*输入相邻的两个点值*/
  printf("输入它们的权值: ");
  scanf("%d",&w);
  i=Locate(*G,v1);j=Locate(*G,v2);       /*用i 和j来确定它们的位置*/
  G->arcs[i][j].adj=w;
  q2=(VertexType *)malloc(sizeof(VertexType));/*分配一个空间*/
  strcpy(q2->data,G->vexs[j].data);
  q2->next=NULL;             /*以便连接在每个顶点后*/
  if(p[i]==0) {G->vexs[i].next=q2;p[i]++;} 
     else 
{
q=&(G->vexs[i]);/*i顶点后面有了*/
	  while(d!=p[i]) {d++;q=q->next;}  
	  p[i]++;
	  q->next=q2;   
  }
 }
}
void Pint(MGraph G)             /*输出邻接矩阵*/
{
int i,j;
 for(i=0;i<G.vexnum;i++)
	{
	  for(j=0;j<G.vexnum;j++)
	  {if(G.arcs[i][j].adj!=ING)
			printf(" %d ",G.arcs[i][j].adj);
	   else printf(" ∞ ");
	  }
      printf("\n");
 }
}
void main()
{
 MGraph G;
 VertexType e,*p;
 int i;
 InitGraph(&G);
 for(i=0;i<10;i++) visited[i]=0;          /*初始为0，表示没被访问过*/
 printf("顶点值： \n");
 for(i=0;i<G.vexnum;++i)       /*给图顶点向量赋值*/
 {
scanf("%s",e.data);e.next=NULL;InsertGraph(&G,i,e);}
CreateUND(&G);                  /*构造图结构*/
printf("邻接矩阵为：\n");
Pint(G);                 /*输出邻接矩阵*/
printf("邻接表为：\n");
  for(i=0;i<G.vexnum;i++)         /*输出邻接表*/
  {
printf(" *%s* ",G.vexs[i].data);p=G.vexs[i].next;
  while(p) {printf(" *%s* ",p->data);p=p->next;}
  printf("\n");
  }
  getch();
}