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

Question

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

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

Ex。输入：4->7->1->10->NULL输出：-1->10->1->7->-1->4->NULL

我不明白这个递归函数是如何跟踪最终的*头的，由于函数通过引用调用自己，这个头每次都会更改。

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

以下是带有以下声明的代码：

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;
}  
}

有了这段代码，可以更容易地看到代码一直自我递归地调用它，直到它到达末尾。在返回的过程中，即当函数调用return时，代码检查是否需要插入"-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;
}  
}

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