例如要存储一下有向图：
当输入6个顶点，8条弧
1 2
1 3
2 4
3 4
3 5
4 1
4 6
5 6
建立的邻接表的流程图为：
实现代码：
~~~
/*
用邻接表存储n个顶点m条弧的有向图
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 10005
typedef struct ArcNode
{
int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode
{
int vertex;
ArcNode * firstarc;
}VNode;
int n,m;
VNode V[MAX];
void init()
{
ArcNode * p;
for(int i=1;i<=n;i++)
{
V[i].vertex=i;
V[i].firstarc=NULL;
}
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=b;
p->nextarc=V[a].firstarc;
V[a].firstarc=p;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
init();
ArcNode * p;
ArcNode * q;
for(int i=1;i<=n;i++)
{
printf("%d",V[i].vertex);
p=V[i].firstarc;
while(p!=NULL)
{
printf(" %d",p->adjvex);
q=p;
p=p->nextarc;
free(q);
}
printf("\n");
}
}
return 0;
}
~~~
- 前言
- The 12th Zhejiang Provincial Collegiate Programming Contest - D
- 用邻接表存储n个顶点m条弧的有向图
- hdu 5289 Assignment（给一个数组，求有多少个区间，满足区间内的最大值和最小值之差小于k）
- hdu 1358 Period（给定一个字符串，求有多少个前缀（包括自己本身），它是由k（k&gt;2,并且尽量大）个循环节组成的）
- hdu 1806 Frequent values(给定一个非降序数组，求任意区间内出现次数最多的数的次数)
- poj 3264 Balanced Lineup（查询区间最大值与最小值的差）
- HDU 1010 Tempter of the Bone（DFS+奇偶剪枝）
- HDU 1015 Safecracker(第一次用了搜索去遍历超时,第二次用for循环可以了,思路一样的)
- HDU 1016 Prime Ring Problem(DFS)
- HDU 1026 Ignatius and the Princess I(BFS+记录路径)
- HDU 1072 Nightmare（BFS）
- HDU 1237 简单计算器（后缀式+栈）