데이터 구조의 토폴로지 정렬

4319 단어 데이터 구조
/*
    :
4 5
a b c d
1 0 1
1 2 5
1 3 6
0 2 8
0 3 2
  :
1 0 2 3
*/ 
#include
#include
#include
#include
#include
using namespace std;
#define MVNum 100   //      
#define OK 1
#define INIT_SIZE 100 
#define STACKINCREMENT 10 
#define Error 0 
#define True 1 
#define False 0 
typedef int SElemType;
typedef int Status;
typedef int ElemType;
typedef int OtherInfo;
typedef char VerTexType;

//         
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	OtherInfo info;  //   
}ArcNode;

typedef struct VNode{
	VerTexType data;
	ArcNode *firstarc;
}VNode, AdjList[MVNum];

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

//    
typedef struct{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SqStack;
//int topo[MVNum];     ,       

Status InitStack(SqStack *s);
Status ClearStack(SqStack *s);
Status StackEmpty(SqStack *s);
Status Destroy(SqStack *s);
Status GetTop(SqStack *s, SElemType &e);
Status Push(SqStack *s, SElemType e);
Status Pop(SqStack *s, SElemType *e);

Status  CreateALGraph(ALGraph &G)
{
	int i, j, k;
	ArcNode *e;
	cout << "        :" << endl;
	cin >> G.vexnum >> G.arcnum;
	cout << "      " << endl;
	for (i = 0; i < G.vexnum; i++) /*       ,      */
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	cout << "   i  j   ( 0  ):" << endl;
	for (k = 0; k < G.arcnum; k++)/*      */
	{
		int quan;
		cin >> i >> j >> quan; /*    (vi,vj)       */
		e = new ArcNode; /*        ,       */
		e->adjvex = j; /*      j */
		e->info = quan;
		e->nextarc = G.vertices[i].firstarc;    /*  e                */
		G.vertices[i].firstarc = e;   /*           e */
	}
	return OK;
}

void FindInDegree(ALGraph G, int indegree[])
{
	int i;
	for (int i = 0; i < G.vexnum; i++)
	{
		indegree[i] = 0;
	}
	for (i = 0; i < G.vexnum; i++)
	{
		while (G.vertices[i].firstarc)
		{
			indegree[G.vertices[i].firstarc->adjvex]++;
			G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
		}
	}
}

void Toposort(ALGraph G)
{
	int indegree[MVNum];
	int i , k ,b, j = 0;
	ArcNode *p;
	SqStack S;
	FindInDegree(G, indegree);
	InitStack(&S);
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!indegree[i])
			Push(&S, i);
	}
	int m = 0;
	while (!StackEmpty(&S))
	{
		Pop(&S, &i);
		topo[m] = i;
		++m;
		//count++;
		p = G.vertices[i].firstarc;
		while (p != NULL)
		{
			k = p->adjvex;
			--indegree[k];
			if (indegree[k] == 0) Push(&S, k);
			p = p->nextarc;
		}
	}
	if (m < G.vexnum)
	{
		cout << "      !" << endl;
	}
	else
	{
		cout << "      ,     :";
		for (b = 0; b < m; b++)
		{
			cout << topo[b] << " ";
		}
		cout << endl;
	}
}

int  main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	ALGraph G;
	CreateALGraph(G);
	Toposort(G);
	return 0;
}


//     
Status InitStack(SqStack *s)
{
	s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
	if (!s->base)
	{
		puts("        !");
		return Error;
	}
	s->top = s->base;
	s->stacksize = INIT_SIZE;
	return OK;
}

//    
Status ClearStack(SqStack *s)
{
	s->top = s->base;
	return OK;
}

//      
Status StackEmpty(SqStack *s)
{
	if (s->top == s->base)
		return True;
	else
		return False;
}

//    
Status Destroy(SqStack *s)
{
	free(s->base);
	s->base = NULL;
	s->top = NULL;
	s->stacksize = 0;
	return OK;
}

//       
Status GetTop(SqStack *s, SElemType &e)
{
	if (s->top == s->base) return Error;
	e = *(s->top - 1);
	return OK;
}

//   
Status Push(SqStack *s, SElemType e)
{
	if (s->top - s->base >= s->stacksize)//   
	{
		s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!s->base)
		{
			puts("        !");
			return Error;
		}
		s->top = s->base + s->stacksize;//       
		s->stacksize += STACKINCREMENT;//      

	}
	*s->top++ = e;
	return OK;
}

//   
Status Pop(SqStack *s, SElemType *e)
{
	if (s->top == s->base) return Error;
	--s->top;
	*e = *(s->top);
	return OK;
}

좋은 웹페이지 즐겨찾기