小程序55837.txt

文档介绍：求拓扑序列,用数组的indegree部分实现链栈。
解:
#include<iostream>
using namespace std;
const int MAX_VERTEX_NUM=20;
typedef struct ode{
int adjvex;
int weight; //弧的权直
struct ode *nextarc;
}ode; //邻结点的定义
typedef struct VNode{
int mark; //顶点是否被访问的标志,为1未访问
char data; //顶点信息
int indegree; //入度
ode *firstarc; //指向第一个邻结点
}VNode,AdjList[MAX_VERTEX_NUM]; //顶点结点的定义
typedef struct ALGraph{
AdjList vertices; //包含顶点结点的数组
int vexnum,um; //图的顶点数和弧数
int kind; //图的种类标志
}ALGraph;
void InitALGraph(ALGraph &G) //对图进行初始化
{
for(int i=0;i<MAX_VERTEX_NUM;i++)
{
[i].mark=1;
[i].firstarc=NULL;
[i].indegree=0;
}
=1;
=0;
=0;
}// InitALGraph
int LocateVex(ALGraph &G,char h)
{
for(int i=0;i<;i++)
if([i].data==h)
return i;
return -1;
}//LocateVex
int Build_AdjList(ALGraph &G)//建立有向有权图,即AOE-网的邻接表
{
InitALGraph(G); //对图初始化
cout<<"输入顶点数(小于"<<MAX_VERTEX_NUM<<"个):";
int v;
cin>>v;
getchar();
if(v<0) {
cout<<"顶点数不能为负!\n";
return 0;
}
=v;
cout<<"输入边数:";
int e;
cin>>e;
getchar();
if(e<0){
cout<<"边数不能为负!\n";
return 0;
}
=e;
cout<<"输入各顶点的符号\n";
for(int m=0;m<v;m++)
[m].data=getchar(); //输入顶点符号中间不能有间隙
getchar();
cout<<"输入图的弧和相应弧上的权值:\n";
int i,j;
char h,t;
ode *p;
for(m=0;m<e;m++) //弧的头在前,尾在后,弧头弧尾权值中间不能有空格
{

h=getchar();
t=getchar();
if((i=LocateVex(G,h))<0||(j=LocateVex(G,t))<0)
{
cout<<"输入顶点没有找到!\n";
return 0;
}
p=(ode*)malloc(sizeof(ode));
if(!p)
{
cout<<"空间分配不足!\n";
return 0;
}
cin>>p->weight;
getchar(); //消除空白符
p->adjvex=j;
p->nextarc=NULL;
if(![i].firstarc)
[i].firstarc=p;
else {
p->nextarc=[i].firstarc;
[i].firstarc=p;
}
}//for
return 1;
}// Build_AdjList
void GetIndegree(ALGraph &G) //获得各点的初始入度
{
for(int i=0;i<;i++) //搜寻各顶点
{
ode *p;
p=[i].firstarc;
while(p!=NULL) //搜寻第i个顶点的邻结点
{