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 阅读(3788) 评论(2)  编辑 收藏 引用

评论

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

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

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

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


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