The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

数据结构作业之-拓扑排序(C++实现)

//张宏数据结构作业之__拓扑排序
//Get Guidance by Mr ZhangHong
//Student:abilitytao

#include
<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
#include
<stack>
using namespace std;
#define MAX 9999

stack
<int>mystack;
int indegree[MAX];

struct node 
{
    
int adjvex;
    node
* next;
}
adj[MAX];

int Create(node adj[],int n,int m)//邻接表建表函数,n代表定点数,m代表边数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{
        
        adj[i].adjvex
=i;
        adj[i].next
=NULL;
    }

    
for(i=1;i<=m;i++)
    
{
        cout
<<"请输入第"<<i<<"条边:";
        
int u,v;
        cin
>>u>>v;
        p
=new node;
        p
->adjvex=v;
        p
->next=adj[u].next;
        adj[u].next
=p;
    }

    
return 1;
}



void print(int n)//邻接表打印函数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{
        p
=&adj[i];
        
while(p!=NULL)
        
{
            cout
<<p->adjvex<<' ';
            p
=p->next;
        }

        cout
<<endl;
    }

}


void topsort(node adj[],int n)
{

    
int i;
    node 
*p;
    memset(indegree,
0,sizeof(indegree));
    
for(i=1;i<=n;i++)
    
{

        p
=adj[i].next;
        
while(p!=NULL)
        
{
            indegree[p
->adjvex]++;
            p
=p->next;
        }

    }

    
for(i=1;i<=n;i++)
    
{

        
if(indegree[i]==0)
            mystack.push(i);
    }

    
int count=0;
    
while(mystack.size()!=0)
    
{

        i
=mystack.top();
        mystack.pop();
        cout
<<i<<' ';
        count
++;
        
for(p=adj[i].next;p!=NULL;p=p->next)
        
{
            
int k=p->adjvex;
            indegree[k]
--;
            
if(indegree[k]==0)
                mystack.push(k);
        }

    }

    cout
<<endl;
    
if(count<n)cout<<"有回路"<<endl;
}




int main()
{
    
int n;
    
int m;
    cout
<<"请输入顶点数及边数:";
    cin
>>n>>m;
    Create(adj,n,m);
    cout
<<"输入的邻接表为:"<<endl;
    print(n);
    cout
<<"拓扑排序结果为:"<<endl;
    topsort(adj,n);
    system(
"pause");
    
return 0;
}


posted on 2009-04-01 17:45 abilitytao 阅读(3777) 评论(2)  编辑 收藏 引用

评论

# re: 数据结构作业之-拓扑排序(C++实现) 2010-07-02 13:18 EIIy

博主 能不能画出这个程序的流程图啊! 急需  回复  更多评论   

# re: 数据结构作业之-拓扑排序(C++实现)[未登录] 2010-07-03 10:48 abilitytao

@EIIy
联系我QQ吧  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理