在C中，由于递归调用使用了与声明不同的参数，因此无法证明递归函数行为的正当性

Question

我用以下方式定义了我的链接列表：

typedef struct node {
int data;
struct node* link;
} Node;
typedef struct list {
int a;
Node* root;
} List;

当从上面的列表中删除值为"x"的节点时，我使用以下递归函数：

void pop(List *l, int x) {
Node* temp = l->root;
printf("Enteredn");
if (temp == NULL) {
return;
}
else if ((l->root)->data == x) {
pophead(l);
pop(l, x);
}
else {
Node* previous;
while (temp->data != x) {
if (temp->link == NULL) {
break;
}

previous = temp;
temp = temp->link;
}
if (temp->link == NULL) {    //last element has been reached
if (temp->data == x) {
previous->link = NULL;
free(temp);
}
else {
return;                                    }
}
else {
previous->link = temp->link;
free(temp);
temp = previous->link;
List* templist = create();
templist->root = temp;
pop(&temp, x);  //**can replace with pop(templist,x)**
}
}
}

pop函数中的最后一行(粗体(可以很好地使用两种变体：

变体1。pop(templist,x)：这将List*指针作为参数。

变体2。pop(&temp,x)：传递链表中节点的地址。

变体2不应理想工作，原因有二：

1. 函数参数不是List*类型
2. C中的指针是强类型的，带有它们所指向的数据类型的地址

以下是完整的代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node* link;
}Node;
typedef struct list{
int a;
Node* root;
}List;
List* create(){
List* temp=(List*)malloc(sizeof(List));
temp->root=NULL;
return temp;
}
void push(List* l,int x){
Node* temp=l->root;
Node* n=(Node*)malloc(sizeof(Node));
n->data=x;
n->link=NULL;
if(temp==NULL)
{
l->root=n;
}
else{
while(temp->link!=NULL){
temp=temp->link;
}
temp->link=n;
}
}
void pophead(List * l){
Node* temp=l->root;
if(temp==NULL){
return;
}
else{
l->root=l->root->link;
free(temp);
}
}
void pop(List *l,int x){
Node* temp=l->root;
printf("Enteredn");
if(temp==NULL){
return;
}
else if((l->root)->data==x){
pophead(l);
pop(l,x);

}
else{
Node* previous;
while(temp->data!=x){
if(temp->link==NULL){
break;
}
previous =temp;
temp=temp->link;
}
if(temp->link==NULL) {    //last element has been reached
if(temp->data==x){
previous->link=NULL;
free(temp);
}
else{
return;
}
}
else{
previous->link=temp->link;
free(temp);
temp=previous->link;
List* templist=create();
templist->root=temp;
pop(templist,x);
}

}
}
void display(List* l){
Node* temp=l->root;
while(temp!=NULL){
printf("%dn",temp->data);
temp=temp->link;
}
}
void main(){
List* l1=create();
push(l1,10);
push(l1,20);
push(l1,30);
push(l1,40);
pophead(l1);
pop(l1,30);
display(l1);
}

Answer 1

您的代码实际上有很多编译错误和警告。确保您知道如何查看编译器报告的所有错误和警告。在假设您的代码是有效的C代码之前，请确保您修复了所有这些问题。

我看到的第一个错误与您错误地使用struct Node有关：该结构没有在任何地方定义，但struct node(小写(是.

当我在godbolt.org上与GCC一起使用你的代码时，我确实收到了你担心的行的警告：

<source>:55:33: warning: passing argument 1 of 'pop' from incompatible pointer type [-Wincompatible-pointer-types]
55 |                             pop(&temp,x);  //**can replace with pop(templist,x)**
|                                 ^~~~~
|                                 |
|                                 Node ** {aka struct node **}        ~~~~~~^