简单拓扑排序算法C语言

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std

//////////////////////举碧/////////////////////////////////////////////////////////////////////////////////////////////////

// Description: 表示图的结点的邻接边

struct Edge

{

int dest

Edge *next

} **graph

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Description: 添加一个边

// Input: e - 要添加边的结点, p - 目的地

// Output: e - 添加边后的结点

void AddEdge(Edge *&e, int p)

{

if(!e)

{

e = new Edge

e->dest = p

e->next = 0

}

else

{

Edge *tail = e

while (tail->next) tail = tail->next

tail->next = new Edge

tail = tail->next

tail->dest = p

tail->next = 0

}

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Description: 输入结点之间的边

// Input: Console下用户输入,起点和终点m - 边的个数

// Output: graph - 图

void Input(int &m)

{

int i, a, b // a->b存在边(有向)

for (i = 0i <mi++)

{

scanf("%d %d", &a, &b)

AddEdge(graph[a], b)

}

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Description: 获得每个结点的入度

// Input: n - 结点的个数

// Output: degree - 每个结点的入度

void GetDegree(int *degree, int n)

{

int i = 0

Edge *edge

memset(degree, 0, sizeof(int) * n)

for (i = 0i <ni++)

{

edge = graph[i]

while(edge)

{

degree[edge->dest]++

edge = edge->next

}

}

}

////////////////////////////////////////////////////////////////迹答汪///////////////////////////////////////////////////////

// Description: 拓扑排序

// Input: n - 结点个数

// Output: console下姿仔输出一个正确的拓扑序

void TopoSort(int n)

{

int *degree = new int[n] // 初始化所有结点的入度

GetDegree(degree, n)

stack<int>s // 获得入度为0的结点,并入栈

int i = 0

for (i = 0i <ni++)

if (degree[i] == 0)

s.push(i)

int index = 0 // 结点的下标

Edge *edge // 当前结点邻接表

while (!s.empty())

{

index = s.top()

printf("%d", index)

s.pop()

edge = graph[index]

while (edge)

{

if (--degree[edge->dest] == 0)

s.push(edge->dest)

edge = edge->next

}

}

delete []degree

}

int main()

{

int n, m // 结点个数、边个数

scanf("%d %d", &n, &m)

int i

graph = new Edge*[n]

for(i = 0i <ni++) graph[i] = 0

Input(m)

TopoSort(n)

return 0

}

指针作为函数参数的问题。。备让

void init_stack(struct linkstack *top) 参数是一个指针，也就是你需要传一个地址进去，当你调用这个函数的时候，比如

struct linkstack *myTop

init_stack(myTop)

没错仿迅局，myTop指向的地址传进去了，但是，在你函数体里面的top和myTop虽然它们的值一样，也就是它们指向的地址一样，但是这两个指针是两个不同的指针，你改变的是top这个形参的值，也就是说top被指向了一个新的地址，是你malloc出来的地址，但是myTop所指的地方还是没有变的，所以初始化就失败了。（注意函数的形参是实参copy的一份，是一个新的变量，只是这个变量的值和实参一样，但是它们的地址和作用域都不一样）

这里需要传指向指针的指针作为参数:

void init_stack(struct linkstack **top){

*top = (struct linkstack *)malloc(sizeof(struct linkstack))

(*top)->next = NULL

}

调用的时候把myTop的昌液地址传进去，比如：

struct linkstack *myTop

struct linkstack ** p = &myTop

init_stack(p)

这样，在init_stack函数里面修改的就是*p，也就是【p所指的地址的内容】，这里的p和参数里面的形参top，它们虽然是两个不同的指针，但是它们指向一个地址，修改了top所指的内容也就修改了p所指的内容。

#include <bits/stdc++.h>

using namespace std

  int n,m,x,y,b[61][61],flag,in[61]

  int main(){

   scanf("%d%d",&n,&m)

   for (int 芦散i=1i<=mi++){

     int x,y

  scanf("%d%d",&x,&y)

  b[x][y]=1

}

for (int k=1k<=nk++)

  for (int i=1i<=ni++)

    for (int j=1j<=nj++)

   神毁   b[i][j]|=b[i][k]&&b[k][j]

    int tot=0

    while (tot!=n){

   陪瞎氏   for (int i=1i<=ni++) if (!in[i]){

       flag=1

       for (int j=1j<=nj++)

         if (b[j][i]&&!in[j])

           flag=0

       if (flag){

         tot++printf("%d\n",i)

  in[i]=1

}

  }

}

  }

---