北大“数据结构”上机考试题(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);
}
- 热门课程
- 报名咨询
- 2022年10月自考西方政治制度知识点:宪政
- 2022年10月自考马克思主义哲学原理知识点:唯心主义和存在的根源
- 2022年10月自考马克思主义哲学原理知识点:马克思主义哲学的产生是哲学发展中的伟大变革
- 2022年10月自考马克思主义哲学原理知识点:唯物主义
- 2022年10月自考马克思主义哲学原理知识点:哲学与科学的分化
- 2022年10月自考马克思主义哲学原理知识点:马克思主义哲学的历史发展
- 2022年10月自考马克思主义哲学原理知识点:马克思主义哲学与中国的社会主义事业
- 2022年10月自考马克思主义哲学原理知识点:对世界统一性的不同认识
- 2022年10月自考马克思主义哲学原理知识点:意识是物质的产物
- 2022年10月自考马克思主义哲学原理知识点:意识的能动作用