北大自考<<数据结构>>上机题

Question

1 编一C程序，它能根据读入的数据构造有向图G，图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2...Vi Vin -1 -1（-1 -1是输入结束标记），它们都是整数，且100>n>0，其余的值都>=0且<n,输出图G的拓扑序列。 
（注：程序的可执行文件名必须是 e1.exe）
2.编一C程序，能根据输入的数字建立有序二叉树,(以-9999为结束标志),并以前序和中序输出结果
(三个小时完成)我刚考完,大家试试自已!欢迎接贴!

Answer 1

int G[100][100]; 
int n; void CreatG() /*建立图的邻接矩阵G[][]*/ 
{
int i,j; 
printf("Input the number of the node:"); 
scanf("%d",&n); 
printf("\n"); 
for (i=0;i<n;i++) 
for (j=0;j<n;j++) 
G[i][j]=0; 
do{ 
scanf("%d %d",&i,&j); 
G[i][j]=1; 
}while ((i!=-1)&&(j!=-1)); 
} 
void Topsort()
{
int i,j,k,t;
int nDegree[100],bVisit[100];
for(i=0;i<n;i++)
{
nDegree[i]=0;
bVisit[i]=0;
}
int nHaveVisit=0;
printf("The top sort result is :\n");
while(nHaveVisit<n)
{
for(i=0;i<n;i++)//计算每个点的入度
{
nDegree[i]=0;
for(j=0;j<n;j++)
nDegree[i]+=G[j][i];
}
for(i=0;i<n;i++)//输出入度为0的点
{
if(nDegree[i]==0 && bVisit[i]==0)
{
printf("%d ",i);
bVisit[i]=1;
nHaveVisit++;
for(j=0;j<n;j++)
G[i][j]=0;
}
}
}
}int main(int argc, char* argv[])
{
CreatG(); 
topsort(); 
return 0;
}//第二题 
// trd.cpp : Defines the entry point for the console application.
//#include "stdafx.h"#include "stdafx.h"
#include"conio.h"
#include"malloc.h"
#include"string.h"struct BINTREE 
{
int  data;
struct BINTREE *left;
struct BINTREE *right;
};void AddBinTree(struct BINTREE **pRoot,int n)
{
if((*pRoot)==NULL)
{
*pRoot=(struct BINTREE *)malloc(sizeof(struct BINTREE));
(*pRoot)->data=n;
(*pRoot)->left=NULL;
(*pRoot)->right=NULL;
return ; }
if(n>(*pRoot)->data)
AddBinTree(&((*pRoot)->right),n);
else
AddBinTree(&((*pRoot)->left),n);
}void DisplayFrontOrder(struct BINTREE *pRoot)
{
if(pRoot==NULL)
return;
printf("%c",pRoot->data);
DisplayFrontOrder(pRoot->left);
DisplayFrontOrder(pRoot->right);
}void DisplayMidOrder(struct BINTREE *pRoot)
{
if(pRoot==NULL)
return;
DisplayFrontOrder(pRoot->left);
printf("%c",pRoot->data);
DisplayFrontOrder(pRoot->right);
}void DeleteBinTree(struct BINTREE *pRoot)
{
if(pRoot==NULL)
return;
DeleteBinTree(pRoot->left);
DeleteBinTree(pRoot->right);
delete pRoot;
}int main(int argc, char* argv[])
{
int n;
struct BINTREE *pRoot=NULL;
printf("please input number:");
scanf("%s",&n);
while(n!=-9999)
{
AddBinTree(&pRoot,n);
scanf("%d",&n);
} printf("the front sort is :\n");
DisplayFrontOrder(pRoot);
printf("\n the mid sort is:\n");
DisplayMidOrder(pRoot); DeleteBinTree(pRoot); getch();
return 0;
}