北大04年“數據結構”上機考試題

　　求拓樸排序後結果及用矩陣表示……輸入形式為n ……(就是上機練習題上的哪個題不過多加了一個用矩陣表示)……

　　輸入一串整數以相反次序輸出

　　第題我做的答案是這樣的第題太簡單就不用了

　　//有的未加判斷矩陣輸出及拓撲排序

　　#include

　　#include

　　#include

　　#define MAX

　　typedef struct {

　　int arcs[MAX][MAX];

　　int vexnum;

　　}Mgraph;

　　void input(Mgraph *mgraphint iint *count)

　　{

　　int abc=;

　　for(int j=;j

　　for(int k=0;k

　　mgraph->arcs[j][k]=0;

　　while(1){

　　printf("輸入(i j)，(-1 -1)結束:");

　　scanf("%d%d",&a,&b);

　　if(a==-1 && b==-1)

　　break;

　　else

　　{

　　mgraph->arcs[a][b]=1;continue;

　　}

　　}

　　for (int k=0;k

　　int c=0;

　　for(int m=0;m

　　if(mgraph->arcs[m][k]==1)

　　c++;

　　}

　　count1[k]=c;

　　}

　　printf("\n矩陣為：\n");

　　for(int l=0;l

　　for(int m=0;m

　　printf("%3d",mgraph->arcs[l][m]);

　　c1=c1+1;

　　if(c1==i){

　　printf("\n");

　　c1=0;

　　}

　　}

　　}

　　//拓撲排序

　　void topsort(Mgraph * mgraph,int i,int *count){

　　int a,b,c=0,s=-1;

　　for(a=0;a

　　if(count[a]==0){

　　count[a]=s;

　　s=a;

　　}

　　}

　　while(s!=-1){

　　printf("V(%d) ",s);

　　c++;

　　a=s;

　　s=count[a];

　　for(b=0;b

　　if(mgraph->arcs[a][b]){

　　count[b]--;

　　if (count[b]==0){

　　count[b]=s;

　　s=b;

　　}

　　}

　　}

　　}

　　}

　　void main(){

　　Mgraph mgraph;

　　int i;

　　printf("輸入頂點個數:");

　　scanf("%d",&i);

　　int count1[MAX];

　　input(&mgraph,i,count1);

　　topsort(&mgraph,i,count1);

　　}

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