Simanzen 发表于 2015-1-26 02:05:10

编程实现由偏序集合构造全序集合，最好能用C或C++编写，谢谢了

编程实现由偏序集合构造全序集合，最好能用C或C++编写，谢谢了

lixiaoshuai 发表于 2015-1-26 02:05:11

#include <iostream>
#include <fstream>
#include <stack>
using namespace std;

ifstream fin("in.txt");
#define MAX_VERTEX_NUM 26

stack<int> s;

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    ArcNode(){nextarc=0;}
//InfoType *info;
}ArcNode;

typedef struct VNode{
    int data;
    ArcNode *firstarc;
    VNode(){firstarc=0;}
}VNode,AdjList;

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
    int kind;
}ALGraph;

bool TopologicalSort(ALGraph G,int *indegree)
{
    int i,k;
    for(i=1;i<G.vexnum+1;i++)
    {
      if(!indegree){s.push(i);}
    }
    int count=0;
    ArcNode *p;
    while(!s.empty())
    {
      i = s.top();
      s.pop();
      cout<<G.vertices.data<<"-->";
      count++;
      for(p=G.vertices.firstarc;p;p=p->nextarc)
      {
            k = p->adjvex;
            indegree--;
            if(!indegree)s.push(k);
      }
    }
    if(count<G.vexnum) return false;
    return true;
}


int main()
{
    int i;
    ALGraph g;
    cout<<"输入节点数和边数： ";
    fin>>g.vexnum>>g.arcnum;
    for(i=1;i<g.vexnum+1;i++)
      g.vertices.data = i;

    int b,e;
    ArcNode *p;
    int *indegree = new int;      
    //注意 int *a=new int(n);申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间   
    //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));
    memset(indegree,0,sizeof(int)*(g.vexnum+1));
    cout<<"逐一输入边的顶点对，形如 3 5 "<<endl;
    for(i=1;i<g.arcnum+1;i++)
    {
      cout<<"第"<<i<<"条边：";
      fin>>b>>e;
      p = new ArcNode();
      p->adjvex = e;
      p->nextarc = g.vertices.firstarc;
      g.vertices.firstarc = p;
      indegree++;
      cout<<endl;
    }
    if(TopologicalSort(g,indegree))cout<<"正常完成！"<<endl;
    else cout<<"该有向图有回路！"<<endl;
    return 0;
}
其实是一个拓扑排序实现偏序。

阔怀 发表于 2015-8-9 10:36:34

{:1_1:}

飘渺463431810 发表于 2017-1-7 15:35:59

来看看，学习一下
页: [1]
查看完整版本: 编程实现由偏序集合构造全序集合，最好能用C或C++编写，谢谢了