数据结构考研分类复习真题 第七章 图[23]

．下面的算法完成图的深度优先遍历请填空

PROGRAM graph_traver;

CONST nl=max_node_number;

TYPE vtxptr=nl; vtxptr=nl;

arcptr=^arcnode;

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

vexnode=RECORD vexdata: char; firstinfirstout: arcptr; END;

graph=ARRAY[vtxptr] OF vexnode ;

VAR ga:graph; n: integer;

visited: ARRAY[vtxptr] OF boolean ;

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

()_______; i:=n;

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

order:=i;

ENDF

PROC creat(var g: graph);

readln(ne);

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

FOR k:= TO e DO [readln (vtvh);

i:=order (gvt); j:=order (gvh); new (p); p^vexi:=i ; p^vexj:=j

p^nextj:= ____()____; ___()____ :=p;

p^nexti:=: ____()____; ___()____ :=p;]

ENDP;

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

i:=order(gv); p:=g[i]firstout;

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

ENDF;

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

i:=order(gv); j:=order(gw); p:=()_______;

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

IF ()______AND()______THEN nextadj:=p^nexti^vexj ELSE nextadj:=;

ENDF;

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

write(v:); visited[order(gv)]:=true; w:=()_______;

WHILE w<> DO

[IF ()______ THEN dfs(gg[w]vexdata);

w:=()_______;]

ENDP;

PROC traver(g:graph);

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

FOR i:= TO n DO IF NOT visited[i] THEN dfs(gg[i]vexdata);

ENDP;

BEGIN

creat(ga); traver(ga);

END 【北方交通大学 三(分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []