北大“数据结构”上机考试题（04年11月18）

　　1、求拓朴排序后结果及用矩阵表示……输入形式为：n  1  2  1 3 ……（就是上机练习题上的哪个题，不过多加了一个用矩阵表示）……

　　2、输入一串整数，以相反次序输出

　　第1题我做的答案是这样的，第2题太简单就不用了。

　　//有的未加判断，矩阵输出及拓扑排序

#include <stdio.h>
#include <malloc.h>
#include <iostream.h>
#define MAX 100

typedef struct {
int arcs[MAX][MAX];
int vexnum;
}Mgraph;

void input(Mgraph *mgraph,int i,int *count1)
{
int a,b,c1=0;
for(int j=0;j<i;j++)
  for(int k=0;k<i;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<i;k++){
   int c=0;
   for(int m=0;m<i;m++){
    if(mgraph->arcs[m][k]==1)
     c++;
   }
    count1[k]=c;
  }
  printf("\n矩阵为：\n");
  for(int l=0;l<i;l++)
   for(int m=0;m<i;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<i;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<i;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);

}