C-链接列表不会删除列表中的第二(2)个记录，但对所有其他列表都可以效果正常

Question

我真的不明白我的程序会发生什么，因为当我尝试删除链接列表中发现的任何记录时，它似乎可以正常工作。

当我尝试删除记录2时，问题出现了，它不会删除它，而是打印0。

这是可以验证的工作程序：

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node *next;
};
void printList( struct node  *head );
void freeList ( struct node **head );
void createList ( struct node **head, const int val );
int searchInList( struct node **head);
int deleteInList( struct node **head, const int val );
int main ( void ){
    struct node *head = NULL;
    int listLen = 5;
    int remove = 3;
    createList ( &head , listLen );
    printf("ttBefore:n");
    printList( head );
    if ( deleteInList( &head, remove ) == -1 ){
        printf("No result found!nttNothing here to be deletedn");
    }else{
        printf("ttAfter:n");
        printList( head );
    }
    freeList( &head );
}
void printList( struct node *head ){
    struct node *current = head;
    while ( current != NULL ){
        printf("Data = %dn",  current->data );
        current = current->next;
    }
    printf("nn");
}
void freeList ( struct node **head ){
    struct node *current = *head;
    while ( current != NULL ){
        struct node *tmp = current->next;
        free( current );
        current = tmp;
    }
}
void createList ( struct node **head, const int val ){
    struct node *current;
    for( int i = val ; i > 0 ; i-- ) {
        current = malloc( sizeof( struct node ) );
        current->data = i;
        current->next  = *head;
        *head = current;
    }
}
int searchInList( struct node ** head) {
    int retval = -1;
    struct node *next = NULL;
    if (*head == NULL) {
        return -1;
    }
    next = (*head)->next;
    retval = (*head)->data;
    free(*head);
    *head = next;
    return retval;
}
int deleteInList( struct node ** head, const int val ) {
    struct node *previous, *current;
    if (*head == NULL) {
        return -1;
    }
    if ( ( *head )->data == val ) {
        return searchInList( head );
    }
    current = ( *head )->next;
    previous = current;
    while ( current ) {
        if ( current->data == val ) {
            previous->next = current->next;
            free( current );
            return val;
        }
        previous = current;
        current  = current->next;
    }
    return -1;
}

输出：

        Before:
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5

        After:
Data = 1
Data = 2
Data = 4
Data = 5

，该程序看起来不错，但是如果我用int remove = 2;替换int remove = 3;，则因为我得到：

Data = 1
Data = 2
Data = 3
Data = 4
Data = 5

        After:
Data = 1
Data = 0
Data = 3
Data = 4
Data = 5

当预期输出应为：

时

        After:
Data = 1
Data = 3
Data = 4
Data = 5

看着Valgrind，我注意到我还有一个free：

==9107== HEAP SUMMARY:
==9107==     in use at exit: 0 bytes in 0 blocks
==9107==   total heap usage: 6 allocs, 7 frees, 1,104 bytes allocate

我无法弄清楚发生了什么。

这是整个Valgrind报告：

==9107== Memcheck, a memory error detector
==9107== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9107== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==9107== Command: ./program
==9107== 
        Before:
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5

        After:
Data = 1
==9107== Invalid read of size 4
==9107==    at 0x400714: printList (program.c:39)
==9107==    by 0x4006D2: main (program.c:29)
==9107==  Address 0x5204130 is 0 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
Data = 2
==9107== Invalid read of size 8
==9107==    at 0x40072B: printList (program.c:40)
==9107==    by 0x4006D2: main (program.c:29)
==9107==  Address 0x5204138 is 8 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
Data = 3
Data = 4
Data = 5

==9107== Invalid read of size 8
==9107==    at 0x400764: freeList (program.c:48)
==9107==    by 0x4006DE: main (program.c:32)
==9107==  Address 0x5204138 is 8 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
==9107== Invalid free() / delete / delete[] / realloc()
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x400777: freeList (program.c:49)
==9107==    by 0x4006DE: main (program.c:32)
==9107==  Address 0x5204130 is 0 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
==9107== 
==9107== HEAP SUMMARY:
==9107==     in use at exit: 0 bytes in 0 blocks
==9107==   total heap usage: 6 allocs, 7 frees, 1,104 bytes allocated
==9107== 
==9107== All heap blocks were freed -- no leaks are possible
==9107== 
==9107== For counts of detected and suppressed errors, rerun with: -v
==9107== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)

我在Linux Mint 18.3上使用GCC-7

Answer 1

deleteInList：

  ...
  if ((*head)->data == val) {
    return searchInList(head);
  }
  current = (*head)->next;
  //  previous = current;   << this is wrong
  previous = *head;         // this is correct
  while (current) {
    if (current->data == val) {
  ...

在您的原始代码中，previous与第一次迭代期间的current相同。

btw： searchInList函数没有其名称所暗示的。

Answer 2

[风格]

• 您使用的变量太多，所有变量都需要将其保存在同步中。
• 您正在为*head节点创建特殊情况，导致多个代码路径。

避免特殊情况会将代码减少到一个循环，并具有一个额外的条件和一个额外的变量：

---

int deleteInList( struct node ** head, const int val ) 
{
struct node *current;
for( ; (current = *head); head = &current->next) {
        if (current->data != val) continue;
        *head = current->next;
        free(current);
        return val;
        }
return -1;
}