邻接表
程序员文章站
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; }
上一篇: 今儿我妈给我爹的洗脚水放了好多陈皮八角花椒干辣椒………好多佐料
下一篇: ADO SQL手写分页