用邻接表存储有向图，并输出各顶点的出度和入度
题目来源图论算法
例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; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
