链式前向星【转帖】

普通前向星好是好，可是如果数据规模大，排序他也不是O(1)时间，也许你排个序就把时间耽误了，不合适，这时候 用邻接矩阵存不下，你还不会写邻接链表，怎么办呢？链式前向星！ 先介绍一下链式前向星的组成： HEAD数组：记录每个顶点的起点位置 E数组：记录每条边的终点 NEXT数组：记录下一条边的位置 其他的诸如权值什么的，自己往上加，这三个数组是必须的。 假设有向图边的输入顺序为： 1 2 2 3 3 4 1 3 4 1 1 5 4 5 那么我们来WATCH一下三个数组的状态 head[1]=6 head[2]=2 head[3]=3 head[4]=7 head[5]=0 e[1]=2 e[2]=3 e[3]=4 e[4]=3 e[5]=1 e[6]=5 e[7]=5 next[1]=0 next[2]=0 next[3]=0 next[4]=1 next[5]=0 next[6]=4 next[7]=5 恩，大致看懂了吧，这就是链式前向星的存储方式，下面讲一下查询方法 假设你要查与1相连的边，那么你先访问head[1]=6 根据e[6]你得到了边1 5 继续访问next[6]=4,得到了边1 3,继续访问next[4]=1,这时候你得到了边1 2,next[1]=0,访问结束. 如果你想访问第N条边，你可以加个计数器，想怎么发挥就随意咯~ 我们来简单的代码实现一下 [php] procedure insertedge(a,b,i:longint); //将边(a,b)插入到第I个位置 begin next[i]:=head[a]; //记录NEXT[I] e[i]:=b; //记录终点 head[a]:=i; //将HEAD[A]替换成新的 end; [/php] 下面是查询操作，以输出与定点V连接的点为例 [php] procedure print(v:longint); //过程名随意改,你改成main什么的都行 var i:longint; begin i:=head[v]; while i <> 0 do begin write(e[i],’ ’); //在这里想对边干什么都可以…注意分寸= = i:=next[i]; end; end; [/php] 下面来介绍一下无向边存储，其实很简单，最简单的方法是把刚才插入有向边的过程调用两遍 [php] procedure insertundirectededge(a,b,i:longint); //将第I条无向边加入前向星数组 begin insertedge(a,b,i shl 1-1); //i shl 1 = i << 1 = i*2 insertedge(b,a,i shl 1);//这就是猥琐地调用给过的程序的方法= =BS我吧- - end; [/php]