链接列表不会删除列表中的第二 (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("\t\tBefore:\n");
    printList( head );

    if ( deleteInList( &head, remove ) == -1 ){
        printf("No result found!\n\t\tNothing here to be deleted\n");
    }else{
        printf("\t\tAfter:\n");
        printList( head );
    }

    freeList( &head );
}

void printList( struct node *head ){
    struct node *current = head;

    while ( current != NULL ){
        printf("Data = %d\n",  current->data );
        current = current->next;
    }
    printf("\n\n");
}

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 相同。

顺便说一句：searchInList 函数并不像它的名字所暗示的那样。

Answer 2

[文体]

您使用的变量太多，需要全部保留 in-sync。
您正在为 *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;
}

链接列表不会删除列表中的第二 (2) 条记录，但适用于所有其他记录

Linked list does not remove the second (2) record in list but works fine for all others

c

linked-list

valgrind

gcc7