aov.h-1.1

  1 //AOV网与拓扑排序类
  2 #ifndef _AOV_H_
  3 #define _AOV_H_
  4 #include<iostream>
  5 #include<cstdio>
  6 #include<malloc.h>
  7 #include<cstring>
  8 #include<queue>
  9 #include<algorithm>
 10 using namespace std;
 11 #endif
 12 
 13 struct point
 14 {
 15     int vertex;//顶点
 16     point* next;
 17 };
 18 
 19 class AOV
 20 {
 21     private:
 22     int* ok;
 23     int* indegree;//入度
 24     point* aim;//邻接表
 25     bool n_hasvalue;
 26     int n;
 27 
 28     public:
 29     int* ans;
 30     AOV(int maxn,int point_num);//构造函数原型
 31     AOV():AOV(50,50){};//直接构造函数
 32     AOV(int maxn);//容器型构造参数
 33     void maxpoint(int p);
 34     int readin();
 35     int* topo_sort();
 36 };
 37 
 38 void AOV::maxpoint(int p)
 39 {
 40     if(n_hasvalue==true)
 41     {
 42         printf("Sorry n had value,ERROR!
");
 43         return;
 44     }
 45     n=p;
 46     n_hasvalue=true;
 47     return;
 48 }
 49 
 50 AOV::AOV(int maxn)//容器型构造参数
 51 {
 52     ans=new int[maxn];
 53     ok=(int*)new int[maxn];
 54     memset(ok,0,sizeof(int)*maxn);
 55     //这里的重置不能写成sizeof(ok);
 56     indegree=new int[maxn];
 57     aim=new point[maxn];
 58     n_hasvalue=false;
 59 }
 60 
 61 AOV::AOV(int maxn,int point_num)
 62 {//maxn描述可能使用到的最大的顶点数量
 63     ans=new int[maxn];
 64     ok=(int*)new int[maxn];
 65     memset(ok,0,sizeof(int)*maxn);
 66     indegree=new int[maxn];
 67     aim=new point[maxn];
 68     n_hasvalue=true;
 69     n=point_num;
 70 }
 71 
 72 int AOV::readin()
 73 {
 74     if(n_hasvalue==false){printf("n do not has value!
");return 0;}
 75     memset(indegree,0,sizeof(int)*(n+1));
 76     for(int i=0;i<n;i++)
 77     {
 78         aim[i].next=NULL;
 79         aim[i].vertex=i;
 80     }
 81     //初始化
 82     int a,b;
 83     //printf("Please input pairs of numbers, which from 0 to n-1, to describe the relationship.
");
 84     //printf("When there is a pair of numbers consists of two 0,then input will stop.
");
 85     while(cin>>a>>b)
 86     {//a->b
 87         if(a==0&&b==0)break;
 88         if(a>=n||b>=n||a<0||b<0){printf("Data error
");continue;}
 89         indegree[b]++;//入度加1
 90         point* temp=&aim[a];
 91         while(temp->next!=NULL)temp=temp->next;
 92         //找到存有指向结点链表的末端
 93         temp->next=(point*)malloc(sizeof(point));
 94         temp=temp->next;//进入新的point点
 95         temp->vertex=b;//a->b
 96         temp->next=NULL;
 97     }//完成邻接表的构建
 98     return 0;
 99 }
100 
101 int* AOV::topo_sort()
102 {
103 //    for(int i=0;i<n;i++)
104 //    {
105 //        printf("vertex %d indegree %d points to:",aim[i].vertex,indegree[i]);
106 //        point* temp=&aim[i];
107 //        while(temp->next!=NULL)
108 //        {
109 //            temp=temp->next;
110 //            printf("%d ",temp->vertex);
111 //        }
112 //        printf("
");
113 //    }
114     queue<int> psd;
115     int cur=0;
116     int num=n;
117     while(1)
118     {
119         if(num)
120         {
121             for(int i=0;i<n;i++)
122             {
123                 if(ok[i])continue;
124                 if(indegree[i]==0)
125                 {
126                     psd.push(i);
127                     ok[i]=1;
128                     num--;
129                 }
130             }//检查所有入度0的顶点并入队,留下入队标记
131         }
132         if(psd.empty())break;//队列为空则排序结束
133         int p=psd.front();psd.pop();
134         point* temp=&aim[p];
135         ans[cur++]=p;//也可以写成ans[cur++]=aim[i].vertex;
136         //printf("%d ",p);
137         //提出结点并排序
138         while(temp->next!=NULL)
139         {
140             temp=temp->next;
141             indegree[temp->vertex]--;
142         }//去掉相关有向边
143     }
144     //printf("

cur->%d
",cur);
145     return ans;
146 }