欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

邻接表

程序员文章站 2022-04-28 12:25:02
用邻接表存储有向图,并输出各顶点的出度和入度 题目来源图论算法例1.3首先我们需要定义一些结构体,其用法在注释中使用# define maxn 100struct ArcNode{ int adjvex;//有向边的另一个邻接点的序号ArcNode *nextarc; //指向下一个边节点的指针};... ......


用邻接表存储有向图,并输出各顶点的出度和入度
题目来源图论算法
例1.3
首先我们需要定义一些结构体,其用法在注释中使用

# define maxn 100
struct arcnode{
 int adjvex;
//有向边的另一个邻接点的序号
arcnode *nextarc; 
//指向下一个边节点的指针};
struct vnode{
int data;
arcnode *head1; //出边表的表头指针
arcnode *head2;// 入边表的表头指针};
struct lgraph{ vnode vertex[maxn];
 int vexnum, arcnum; };lgraph lg;


接下来我们需要定义邻接表创建函数

void createlg()
{
   int i=0;  // for
   arcnode *pi;
    int v1,v2; //顶点
   for(i=0;i<lg.vexnum;i++)        //初始化表头指针
      lg.vertex[i].head1=lg.vertex[i].head2=null;
    for(i=0;i<lg.arcnum;i++)
    {
      scanf("%d%d",&v1,&v2);
      v1--,v2--;
      pi=new arcnode;
      pi->adjvex=v2;
     pi->nextarc=lg.vertex[v1].head1;    //插入链表
     lg.vertex[v1].head1=pi;
      pi=new arcnode;
      pi->adjvex=v1;
      pi->nextarc=lg.vertex[v2].head2;    //插入链表
     lg.vertex[v2].head2=pi; 
    }
 }


我们定义这个创建函数后,要有释放内存函数
void deletelg()
{
   int i;  // for
   arcnode *pi;
   for(i=0;i<lg.vexnum;i++)
    {
       pi=lg.vertex[i].head1;
       //释放第i个顶点的出边表各节点所占的存储空间
      while(pi!=null)
       {
          lg.vertex[i].head1=pi->nextarc;
          delete pi;
          pi=lg.vertex[i].head1;
       }
      pi=lg.vertex[i].head2;
         //释放第i个顶点的入边表各节点所占的存储空间
      while(pi!=null)
       {
          lg.vertex[i].head2=pi->nextarc;
          delete pi;
          pi=lg.vertex[i].head2;
       }
   
    }

}


完整代码如下:

#include<cstdio>
 #include<cstdlib>
 # define maxn 100

struct arcnode{
     
     int adjvex;           //有向边的另一个邻接点的序号
    arcnode *nextarc;    //指向下一个边节点的指针
};

struct vnode
 {
     int data;
     arcnode *head1;    //出边表的表头指针
    arcnode *head2;    // 入边表的表头指针
};


struct lgraph
 {
     vnode vertex[maxn];
     int vexnum, arcnum;
 };
 lgraph lg;

void createlg()
 {
    int i=0;  // for
    arcnode *pi;
    int v1,v2; //顶点
   for(i=0;i<lg.vexnum;i++)        //初始化表头指针
      lg.vertex[i].head1=lg.vertex[i].head2=null;
    for(i=0;i<lg.arcnum;i++)
    {
      scanf("%d%d",&v1,&v2);
      v1--,v2--;
      pi=new arcnode;
      pi->adjvex=v2;
      pi->nextarc=lg.vertex[v1].head1;    //插入链表
     lg.vertex[v1].head1=pi;
      pi=new arcnode;
      pi->adjvex=v1;
      pi->nextarc=lg.vertex[v2].head2;    //插入链表
     lg.vertex[v2].head2=pi; 
    }
 }

void deletelg()
 {
    int i;  // for
    arcnode *pi;
    for(i=0;i<lg.vexnum;i++)
    {
       pi=lg.vertex[i].head1;
       //释放第i个顶点的出边表各节点所占的存储空间
      while(pi!=null)
       {
          lg.vertex[i].head1=pi->nextarc;
          delete pi;
          pi=lg.vertex[i].head1;
       }
       pi=lg.vertex[i].head2;
         //释放第i个顶点的入边表各节点所占的存储空间
      while(pi!=null)
       {
          lg.vertex[i].head2=pi->nextarc;
          delete pi;
          pi=lg.vertex[i].head2;
       }
    
    }

}
 int main()
 {
   int i;
   int id,od;
   arcnode *pi;
   while(1)
   {
   lg.vexnum=lg.arcnum=0;
   scanf("%d%d",&lg.vexnum,&lg.arcnum);
   if(lg.vexnum==0)  break;
   createlg();
   for(i=0;i<lg.vexnum;i++)
   {
   od=0;
   pi=lg.vertex[i].head1;
   while(pi!=null)
   {
      od++;
      pi=pi->nextarc;
   }if(i==0) printf("%d",od);

  else printf("%d",od);
   }printf("\n");
   for(i=0;i<lg.vexnum;i++)
   {
   id=0;
   pi=lg.vertex[i].head2;
   while(pi!=null)
   {
      id++;
     pi=pi->nextarc;
   }if(i==0) printf("%d",id);

  else printf("%d",id);
   }printf("\n");
    deletelg();
   }
 return 0;
 }