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

．假设给定的有向图是用邻接表表示作为输入的是图中顶点个数n和边的个数m 以及图的m条边在下面的程序中我们用readdata程序过程输入图的信息并建立该图的邻接表利用topol程序过程获得图中顶点的一个拓扑序列

PROGRAM topol_order(input output) ;

CONST maxn= ;

TYPE nodeptr=^nltype ;

nltype=RECORD num : integer ; link : nodeptr END ;

chtype=RECORD count : integer ; head : nodeptr END ;

VAR ch : ARRAY [ maxn] OF chtype ; m n top : integer ;

PROCEDURE readdata ;

VAR i j u v : integer ; p : nodeptr ;

BEGIN

write (′input vertex number n= ′); readln (n) ;

write (′input edge number m= ′); readln(m) ;

FOR i:= TO n DO BEGIN ch[i]count:= ; ch[i]head:=NIL END;

writeln(′input edges :′);

FOR j:= TO m DO

BEGIN write( j : ′: ′) ; readln( u v ) ; new( p ) ;

ch[v]count:=ch[v]count+; p^num:=v; () ___ ; () __; END

END ;

PROCEDURE topol ;

VAR i j k: integer; t: nodeptr ;

BEGIN

top:= ;

FOR i := TO n DO

IF ch[i]count= THEN BEGIN ch[i]count := top ;top := i END;

i:= ;

WHILE () ___ DO

BEGIN () __; () __ ; write(j : ) ;i:= i + ;t:=ch[j]head ;

WHILE t<>NIL DO

BEGIN k := t^num ; ch[k]count:=ch[k]count ;

IF ch[k]count= THEN BEGIN ch[k]count:=top; top:=k END;

() ______ ; END

END ; writeln;

IF i<n THEN writeln (′the network has a cycle!′)

END;

BEGIN

readdata ; writeln (′output topol order : ′); topol

END 【复旦大学 三 (分)】

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