데이터 구조의 토폴로지 정렬
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.