#include<iostream>
using namespace std;
typedef int elementype;
#define MAXSIZE 100
#define MVNum 100 //最大顶点信息
#define OK 1
typedef char vertextype;
typedef int otherinfo;
//----------图的邻接变存储表示-----------
typedef struct arcnode { //边结点
int adjvex; //该边所指向顶点的位置
struct arcnode *nextarc; //指向下一条边的指针
char *info; //和边相关的信息
}arcnode;
typedef struct vnode {
char data; //顶点信息
arcnode *firstarrc; //指向第一条依附该顶点
}vnode,adjlist[MVNum];
typedef struct {
adjlist vertices; // 邻接表
int vexnum; //图的当前顶点数
int arcnum; //图的当前边数
}algraph;
typedef struct node
{
int *base;
int *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base =new int[MAXSIZE];
if( !S.base ) return 0;
S.top = S.base;
S.stacksize = MAXSIZE;
return 1;
}
int StackEmpty(SqStack S)//判断是否为空
{
if(S.top == S.base) return 1;
else return 0;
}
int Push(SqStack &S,int i) //入度为 0者进栈
{
algraph g;
*S.top=i;
S.top++;
}
int Pop(SqStack &S,int i) //i是顶点位置
{
algraph g;
i= *S.top;
S.top=S.top-2;
}
int located(algraph g,char v)
{
int i;
for(i=0;i<g.vexnum;i++){
if(v==g.vertices[i].data){
return i;
}
}
}
int indegree[MVNum];
void creat(algraph &g)
{
arcnode *p1,*p2;
char v1,v2;
int i,k,j;
cout<<"输入点数和边数:\n";
cin>>g.vexnum>>g.arcnum;
for(i=0;i<g.vexnum;i++){
indegree[i]=0;//初始化各个顶点的入度都为 0
}
cout<<"输入各个顶点:"<<endl;
for(i=0;i<g.vexnum;i++){
cin>>g.vertices[i].data;
g.vertices[i].firstarrc=NULL;
}
cout<<"输入一个顶点与其指向的顶点:"<<endl;
for(k=0;k<g.arcnum;k++){
cin>>v1>>v2;
i=located(g,v1);
j=located(g,v2);//v2是被指向的顶点
indegree[j]+=1;
p1=new arcnode;
p1->adjvex=j;
p1->info=NULL;
p1->nextarc=g.vertices[i].firstarrc;
g.vertices[i].firstarrc=p1;
}
cout<<"ok have created."<<endl;
cout<<"各个顶点的入度为:";
for(i=0;i<g.vexnum;i++){
cout<<indegree[i]<<" ";
}
}
void bianli(algraph g)
{
arcnode *p;
int i;
cout<<endl;
cout<<"共有"<<g.vexnum<<"个顶点:"<<endl;
for(i=0;i<g.vexnum;i++){
cout<<g.vertices[i].data<<" ";
}
cout<<"\n\n共有"<<g.arcnum<<"条边:";
for (i = 0; i < g.vexnum;i++)
{
p=g.vertices[i].firstarrc;
while(p){
cout<<g.vertices[i].data << "→" <<g.vertices[p->adjvex].data << " ";
p=p->nextarc;
}
cout<<endl;
}
}
int tuopu(algraph g,int topo[])//topo[]数组为保存拓扑序列数组
{
arcnode *p;
int m;
int i,k;
SqStack S;
InitStack(S);
for(i=0;i<g.vexnum;++i)
if(!indegree[i]) Push(S,i);
m=0;
while(!StackEmpty(S))
{
Pop(S,i);
topo[m]=i;
++m;
p=g.vertices[i].firstarrc;
while(p!=NULL)
{
k=p->adjvex;
--indegree[k];
if(indegree[k]==0) Push(S,k);
p=p->nextarc;
}
}
if(m<g.vexnum) {
cout<<"图有回路!"<<endl;
return 0;
}
}
int main()
{
int v,i;
algraph g;
creat(g);
bianli(g);
int topo[50];
tuopu(g,topo);
}
具体在代码第148行至第153行之间出现错误,求解答
测试数据:
6 7
A B C D E F
A B
B D
D F
A C
C D
C E
E F