C 创建AOV网进行拓扑排序
本帖最后由 ing 于 2020-3-1 19:21 编辑这有2个AOV的创建方法，下面这个是可运行的
这个创建AOV方法将会导致异常
我实在没看懂这有什么区别，为什么第二张图片将会导致异常
```
#include<malloc.h>
#include<stdio.h>
#include<stdbool.h>
#define VType int
#define MAX 20
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct
{
VType vertex;
ArcNode *firstArc;
}AdjList;
typedef struct
{
int arcNum, vertexNum;
AdjList vertices;
}MGraph;
int locate(MGraph **g, VType rear)
{
for (size_t i = 0; i < (*g)->vertexNum; i++)
{
if ((*g)->vertices.vertex == rear)
{
return i;
}
}
return -1;
}
void createAOV(MGraph **g)
{
printf("请输入顶点数和弧边数\n");
scanf("%d,%d", &(*g)->vertexNum, &(*g)->arcNum);
printf("请输入顶点元素\n");
for (size_t i = 0; i < (*g)->vertexNum; i++)
{
scanf("%d", &(*g)->vertices.vertex);
(*g)->vertices->firstArc = NULL;
}
printf("请输入弧尾和弧头\n");
VType arc_t, arc_h;
for (size_t i = 0; i < (*g)->arcNum; i++)
{
//存储弧头
scanf("%d,%d", &arc_t, &arc_h);
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = locate(g, arc_h);
int t_locate = locate(g, arc_t);
p->next = (*g)->vertices.firstArc;
(*g)->vertices.firstArc = p;
}
}
//void createAOV(MGraph **g)
//{
// printf("请输入顶点和弧边数\n");
// scanf("%d,%d", &(*g)->vertexNum, &(*g)->arcNum);
//
// printf("请输入顶点元素\n");
// for (int i = 0; i < (*g)->vertexNum; ++i) {
// scanf("%d", &(*g)->vertices.vertex);
// (*g)->vertices.firstArc = NULL;
// }
//
// printf("请输入弧尾和弧头\n");
// VType h, t;
// for (int j = 0; j < (*g)->arcNum; ++j) {
// scanf("%d,%d", &t, &h);
// //用结点存储弧头
// ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
// p->adjvex = locate(g, h);
//
// //弧尾结点的数据域存储弧头的数组下标
// int t_locate = locate(g, t);
// p->next = (*g)->vertices.firstArc;
// (*g)->vertices.firstArc = p;
// }
//}
typedef struct Stack
{
VType data;
struct Stack *next;
}Stack;
void init(Stack **s)
{
*s = (Stack*)malloc(sizeof(Stack));
(*s)->next = NULL;
}
void push(Stack *s, int index)
{
Stack *p = (Stack*)malloc(sizeof(Stack));
p->data = index;
p->next = s->next;
s->next = p;
}
void findInDegree(MGraph **g, int *indegree)
{
for (size_t i = 0; i < (*g)->vertexNum; i++)
{
indegree = 0;
}
for (size_t i = 0; i < (*g)->vertexNum; i++)
{
ArcNode *p = (*g)->vertices.firstArc;
//结点数据域存储了弧头数组下标，入度即为在数据域出现的次数
while (p)
{
++indegree;
p = p->next;
}
}
}
bool isEmpty(Stack *s)
{
if (s->next)
return false;
return true;
}
void pop(Stack *s, VType *d)
{
Stack *p = s->next;
*d = p->data;
s->next = s->next->next;
free(p);
}
void topological_sort(MGraph **g)
{
int n = (*g)->vertexNum;
int *indegree = (int*)malloc(n*sizeof(int));
findInDegree(g, indegree);
Stack *s;
init(&s);
//查找入度为0的顶点，作为起始点
for (int i = 0; i < (*g)->vertexNum; ++i) {
if (!indegree)
push(s, i);
}
int count = 0;
VType d;
while (!isEmpty(s))
{
pop(s, &d);
++count;
printf("%d ", (*g)->vertices.vertex);
//依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0
for (ArcNode *p = (*g)->vertices.firstArc; p; p = p->next) {
if (!(--indegree))
push(s, p->adjvex);
}
}
//如果count值小于顶点数量，表明该有向图有环
if (count < (*g)->vertexNum)
{
printf("AOV网有环");
return;
}
}
int main(int argc, char* argv[])
{
MGraph *g = (MGraph*)malloc(sizeof(MGraph));
createAOV(&g);
topological_sort(&g);
}
```
页:
[1]