數據結構考研分類復習真題 第七章 圖[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  【復旦大學 三 (分)】

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23114.html