在C中的另一个函数内定义递归函数

Question

我试图在另一个函数 (dijkstraSSSP) 中编写一个递归函数 (printPath)，但它给我一个编译器错误。

当我运行 gcc dijkstra.c WGraph.c PQueue.c 时，它编译得很好。但是，当我运行dcc -Wall -Werror -std=c11 -o dijkstra dijkstra.c WGraph.c PQueue.c。我收到此错误：

dijkstra.c:48:38: error: function definition is not allowed here
void printPath (int currentNode) {

我认为这是因为我在另一个函数中定义了一个函数。如果是这种情况，我应该如何修改代码？非常感谢！

void dijkstraSSSP(Graph g, Vertex source) {
    int  dist[MAX_NODES];
    int  pred[MAX_NODES];
    bool vSet[MAX_NODES];  // vSet[v] = true <=> v has not been processed
    int s, t;

    PQueueInit();
    int nV = numOfVertices(g);
    for (s = 0; s < nV; s++) {
        joinPQueue(s);
        dist[s] = VERY_HIGH_VALUE;
        pred[s] = -1;
        vSet[s] = true;
    }

    dist[source] = 0;  

    int relaxWeight;
    for (s = 0; s < numOfVertices(g); s++) {
        s = leavePQueue(dist);
        //printf("iterating with s = %d\n", s);
        //printf("updating vSet[%d] = false\n", s);
        vSet[s] = false;
        for (t = 0; t < numOfVertices(g); t++) {
            //printf("iterating with t = %d\n", t);
            //printf("checking if s = %d is adj to t = %d and vSet[%d] = true\n", s, t, t);
            if (adjacent(g, s, t) != 0 && vSet[t] == true) {
                //printf("YES\n");
                relaxWeight = adjacent(g, s, t);
                if (dist[t] > dist[s] + relaxWeight) {
                    //printf("updating dist[%d] = dist[%d] + adjWeight[%d]\n", t, s, relaxWeight);
                    dist[t] = dist[s] + adjacent(g, s, t);
                    //printf("updating pred[%d] = %d\n", t, s);
                    pred[t] = s;
                }
            }
        }
    }
 
    void printPath (int currentNode) {
        if (pred[currentNode] == -1) {
            printf("%d", currentNode);
            return;
        } else {
            printPath (pred[currentNode]);
            printf("-%d", currentNode);
        }
    }

    for (int i = 0; i < numOfVertices(g); i++) {
        if (dist[i] == VERY_HIGH_VALUE) {
            printf("%d: no path\n", i);
        } else{
            printf("%d: distance = %d, shortest path: ", i, dist[i]);
            printPath(i);
            printf("\n");
        }
    }
}

Answer 1

将 printPath 的定义移到 dijkstraSSSP 的主体之外，并使其能够访问 pred，将其更改为接受两个参数而不是一个。附加参数的类型应为 int * 并且应指向 pred.

的第一个元素

在调用中，为该新参数传递 pred。数组 pred 将自动转换为指向其第一个元素的指针。

Answer 2

在另一个函数中定义一个函数在 C 标准中没有定义。 gcc 允许它作为扩展，但大多数编译器不允许。

您应该将 printPath 的定义移到 dijkstraSSSP 函数体之外，在源代码中它之前，并将 pred 作为额外参数传递：

void printPath(const int *pred, int currentNode) {
    if (pred[currentNode] == -1) {
        printf("%d", currentNode);
    } else {
        printPath(pred, pred[currentNode]);
        printf("-%d", currentNode);
    }
}

void dijkstraSSSP(Graph g, Vertex source) {
    int  dist[MAX_NODES];
    int  pred[MAX_NODES];
    bool vSet[MAX_NODES];  // vSet[v] = true <=> v has not been processed
    int s, t;

    PQueueInit();
    int nV = numOfVertices(g);
    for (s = 0; s < nV; s++) {
        joinPQueue(s);
        dist[s] = VERY_HIGH_VALUE;
        pred[s] = -1;
        vSet[s] = true;
    }

    dist[source] = 0;  

    int relaxWeight;
    for (s = 0; s < numOfVertices(g); s++) {
        s = leavePQueue(dist);
        //printf("iterating with s = %d\n", s);
        //printf("updating vSet[%d] = false\n", s);
        vSet[s] = false;
        for (t = 0; t < numOfVertices(g); t++) {
            //printf("iterating with t = %d\n", t);
            //printf("checking if s = %d is adj to t = %d and vSet[%d] = true\n", s, t, t);
            if (adjacent(g, s, t) != 0 && vSet[t] == true) {
                //printf("YES\n");
                relaxWeight = adjacent(g, s, t);
                if (dist[t] > dist[s] + relaxWeight) {
                    //printf("updating dist[%d] = dist[%d] + adjWeight[%d]\n", t, s, relaxWeight);
                    dist[t] = dist[s] + adjacent(g, s, t);
                    //printf("updating pred[%d] = %d\n", t, s);
                    pred[t] = s;
                }
            }
        }
    }
 
    for (int i = 0; i < numOfVertices(g); i++) {
        if (dist[i] == VERY_HIGH_VALUE) {
            printf("%d: no path\n", i);
        } else{
            printf("%d: distance = %d, shortest path: ", i, dist[i]);
            printPath(pred, i);
            printf("\n");
        }
    }
}

在C中的另一个函数内定义递归函数

Defining a recursive function inside another function in C

c

recursion

function-definition