链表节点消除函数

Question

我只是想消除包含偶数的节点 x % 2 == 0。

我写了一个非常简单的函数，但是在我使用它之后，编译器不显示修改后的列表，我不明白为什么。

如果头部包含一个偶数元素，它可以正常工作（我在 main 中这样做），但是当我尝试从内部删除一些东西时，它确实不想工作...

我真的不知道我做错了什么

#include <stdio.h>
#include <stdlib.h>
struct test{
    int val;
    struct test *next;
};

void erase (struct test *x)
{ 
    struct test *t;
    t=x->next;
    x->next=t->next;
    free(t);
    return ;
}

int main ()
{
    
    struct test *head,*p,*q, *aux;
    int n,i;
    
    printf("Number of elements:");
    scanf("%d",&n);
    p=(struct test * )malloc(sizeof(struct test));
    
    printf("First value:");
    scanf("%d",&p->val);
    p->next=NULL;
    head=p;
    for(i=2;i<=n;i++)
    {
        q=(struct test * )malloc(sizeof(struct test));
        printf("Value %d:",i);
        scanf("%d",&q->val);
        q->next=NULL;
        p->next=q;
        p=q;
    }
    
    for(p=head;p!=NULL;p=p->next) {
        printf("%d ",p->val);
    }
    while((head->val)%2==0) {
        aux=head;
        head=head->next;
        free(aux);
    }
    
    for( p=head ; p!=NULL; p = p->next) {
        if((p->next->val)%2==0) {
            erase (p);
        }
    }
    printf("\n");
    for(p=head ;p!=NULL;p=p->next) {
        printf("%d ",p->val);
    }
}

Answer 1

while 循环后

while((head->val)%2==0) {
    aux=head;
    head=head->next;
    free(aux);
}

指针头可以等于NULL。所以下一个 for 循环可以调用未定义的行为。此外，在擦除具有偶数值的节点后，您正在冗余地推进指针 p。

将此替换为循环

for( p=head ; p!=NULL; p = p->next) {
    if((p->next->val)%2==0) {
        erase (p);
    }
}

对于以下代码

if ( head != NULL ) {
    for( p=head ; p->next!=NULL; ) {
       if((p->next->val)%2==0) {
           erase (p);
       }
       else {
           p = p->next;
       } 
   }
}

Answer 2

这里有一个错误：

for( p=head ; p!=NULL; p = p->next) {
    if((p->next->val)%2==0) {
        erase (p);
    }
}

列表中的最后一个元素发生了什么？

p 不是 NULL.

p->next 是 NULL。

p->next->val 将取消引用 NULL 指针。

Answer 3

让我们看看你的函数做了什么：

void erase (struct test *x)
{ 
    struct test *t;
    t=x->next;
    x->next=t->next;
    free(t);
    return ;
}

它获得一个指向您的结构之一的指针 x 并假定它不指向 NULL。

x -> [         ]

那个指向的结构指向另一个结构。

x-> [          ] -> [         ]

该函数创建一个指针，指向它。

x-> [          ] -> [NULL?  ]
t------------------>

t 现在可以指向 NULL，但函数不检查它。

然后它尝试重新指向 x 指向的内容，指向任何未检查的内容指向的内容，这可能会取消引用 NULL。

    [          ] -> [??NULL??  ] ??->?? ????[]????
t------------------>
x ----------------------------?-?-?-?-?-?-?-?-?->

此时您面临取消引用 NULL 的风险。

链表节点消除函数

Linked-list node eliminating function

c

struct

linked-list

singly-linked-list

function-definition