c - 了解列表上通过引用调用的函数

Question

我想知道为什么下面给出的代码运行良好。

它应该递归地给定一个列表，在偶数前面放置 -1。

例如。输入:4->7->1->10->NULL 输出:-1->10->1->7->-1->4->NULL

我不明白这个递归函数如何跟踪最终的 *head，因为该函数通过引用调用自身，所以每次都会更改它。

最后，我没有得到的是，考虑到(对我来说)对引用递归函数如何工作的误解，输出如何正确。

这是带有以下声明的代码:

typedef struct El {
    int info;
    struct El *next;}ElementoLista;
typedef ElementoLista *ListaDiElementi;

void inserisci(ListaDiElementi *head) { 
    if((*head) != NULL && ((*head)->info)%2 == 0) {
        inserisci(&(*head)->next);
        ListaDiElementi aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *head;
        *head = aux;
    } else {    
        if((*head) != NULL) {               
            inserisci(&(*head)->next); 
        }  
    }  
}

Answer 1

我认为您对代码的麻烦是由于代码写得“有点糟糕”，即不太清晰。我看到三个问题。

1)“指针的typedef”使得很难理解涉及哪些类型。特别是当不清楚特定类型是指针时。像 ListaDiElementi 这样的名称并不能(至少对我来说)清楚地表明这是一个指针。更好的名称可能是 ElementoLista_ptr，但总的来说，最好避免使用指针 typedef。

2) 函数参数名为head。这很令人困惑，因为我们通常认为 head 是指向列表第一个元素的指针。但这不是这里发生的事情。该参数实际上是一个双指针，而且它并不指向第一个元素。它指向 next 指针。

3) if 构造隐藏了程序的逻辑。

因此，让我们重写代码以摆脱上述内容，同时仍保留相同的功能:

typedef struct El {
    int info;
    struct El *next;
} ElementoLista;

void inserisci(ElementoLista **pNext) { 
    if ((*pNext) == NULL) return;

    inserisci(&(*pNext)->next);

    if(((*pNext)->info)%2 == 0) {
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *pNext;
        *pNext = aux;
    }  
}

通过这段代码，可以更容易地看到代码不断递归地调用它自己，直到到达末尾。在返回的路上，即当函数调用返回时，代码检查是否需要插入“-1”节点。

相同的代码，带有一些注释来解释:

typedef struct El {
    int info;
    struct El *next;} ElementoLista;

// pNext is a pointer to the "next pointer" of the previous node
// Consequently (*pNext) is a pointer to the current node
void inserisci(ElementoLista **pNext) { 
    // Return if we have reached the end of the list
    if ((*pNext) == NULL) return;

    // Keep calling until the end is reached
    inserisci(&(*pNext)->next);

    // On the "way back" (i.e. as the recursive calls return) check
    // if we need to insert a "-1" node
    if(((*pNext)->info)%2 == 0) {
        // We need a new node
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;

        // Make the new node point to current node
        aux->next = *pNext;

        // Update the next pointer to point to the new node
        *pNext = aux;
    }  
}

当您理解这个简化版本的代码时，您也应该理解原始版本。