数据�l�构�W�七章填�I�题[7]_跨考网

1�Q�下面的���法完成囄���深度优先遍历�Q�请填空�?/span>

　　PROGRAM graph_traver;

　　CONST nl=max_node_number;

　　TYPE vtxptr=1..nl; vtxptr0=0..nl;

　　arcptr=^arcnode;

　　arcnode=RECORD vexi ,vexj: vtxptr; nexti, nextj: arcptr; END;;

　　vexnode=RECORD vexdata: char; firstin�Q?/span>firstout: arcptr; END;

　　graph=ARRAY[vtxptr0] OF vexnode ;

　　VAR ga:graph; n: integer;

　　visited: ARRAY[vtxptr0] OF boolean ;

　　FUNC order (g: graph; v: char): vtxptr;

　　(1)_______; i:=n;

　　WHILE g[i].vexdata<>v DO i:=i-1;

　　order:=i;

　　ENDF�Q?/span>

　　PROC creat(var g: graph);

　　readln(n,e);

　　FOR i:= 1 TO n DO {readln(g[i].vexdata); g[i].firstin :=NIL ; g[i].firstout:=NIL;}

　　FOR k:= 1 TO e DO {readln (vt,vh);

　　i:=order (g,vt); j:=order (g,vh); new (p); p^.vexi:=i ; p^.vexj:=j

　　p^.nextj:= ____(2)____; ___(3)____ :=p;

　　p^.nexti:=: ____(4)____; ___(5)____ :=p;}

　　ENDP;

　　FUNC firstadj(g:graph; v:char): vtxptr0;

　　i:=order(g,v); p:=g[i].firstout;

　　IF p<>NIL THEN firstadj:=(6)_______ELSE firstadj:=0;

　　ENDF;

　　FUNC nextadj(g:graph; v:char; w:char): vtxptr0;

　　i:=order(g,v); j:=order(g,w); p:=(7)_______;

　　WHILE(p<>NIL ) AND (p^.vexj<>j) DO(8)______;

　　IF (9)______AND(10)______THEN nextadj:=p^.nexti^.vexj ELSE nextadj:=0;

　　ENDF;

　　PROC dfs(g:graph; v0:char);

　　write(v0:2); visited[order(g,v0)]:=true; w:=(11)_______;

　　WHILE w<>0 DO

　　{IF (12)______ THEN dfs(g,g[w].vexdata);

　　w:=(13)_______;}

　　ENDP;

　　PROC traver(g:graph);

　　FOR i:=1 TO n DO visited[i]:=false;

　　FOR i:=1 TO n DO IF NOT visited[i] THEN dfs(g,g[i].vexdata);

　　ENDP;

　　BEGIN

　　creat(ga); traver(ga);

　　END. 【北方交通大�?/span> 1999 三（20分）�?/span>