链表逻辑错误

Question

我写了一个带头节点的链表代码。我在删除节点和查找节点时遇到逻辑错误，方法是使用列表中的属性（代码）。我试过调试，但没有太大帮助。我可以使用一些帮助来查找错误。谢谢。

错误：

我无法通过代码值找到产品节点。
当我尝试删除一些节点时，这些节点似乎不存在。

我的调试输出：对于此处显示的主程序，结果为 "NOT FOUND"。但代码值为“0000”的节点存在。

main.c

#include <stdio.h>
#include <stdlib.h>
#include "products.h"

void print_product(struct product *p)
{
    printf("%s (%s) -- stock: %d, price: %lf\n",
                p->title, p->code,
                p->stock, p->price);
}

int main()
{
    struct product_list list;
    struct product *p;
    init_list(&list);
    add_product(&list, "test", "1234", 1, 0.50);
    add_product(&list, "Product 1", "0000", 0, 10);
    add_product(&list, "Long name, isn't it", "1234567890", 10, 100);
    add_product(&list, "Product 3", "9999999", 0, 20);
    p = find_product(&list, "0000");
    if (p)
        print_product(p);
    else
        printf("Not found\n");
    int i=remove_product(&list, "0000");
    printf("Removed %d items\n", i);
    delete_list(&list);
}

products.h

struct product {
    char *title;  // Name of the product
    char code[8]; // Max. 7 characters of product ID
    int stock;  // Current stock (number of units)
    double price;  // Price of a single unit
    struct product *next; // pointer to next item in linked list
};

struct product_list {
    struct product *head;
    // could have other list specific elements, like length of the list, last update time, etc.
    };

void init_list(struct product_list *list);
struct product *add_product(struct product_list *start, const char *title, const char *code,
        int stock, double price);
struct product *find_product(struct product_list *start, const char *code);
int remove_product(struct product_list *start, const char *code);
int delete_list(struct product_list *start);

products.c

#include <stdlib.h>
#include "products.h"
#include <stdio.h>
#include<string.h>

void init_list (struct product_list *list)
{
  list->head = malloc(sizeof(struct product));
}

/* Add product */
/* Parameters:
 * start: start of the linked list
 * title, code, stock, price: to be copied as created structure content
 * 
 * Returns: pointer to the newly added node in the linked list
 */
struct product *add_product(struct product_list *start, const char *title, const char *code,
        int stock, double price) {
    while(start->head->next != NULL){
        start->head = start->head->next;
    }
    if(start->head->title == NULL){
        start->head->title = malloc(strlen(title) + 1);
        strcpy(start->head->title, title);
        strncpy(start->head->code, code, 7);
        start->head->code[7] = 0;
        start->head->stock = stock;
        start->head->price = price;
    }else{
        start->head->next = malloc(sizeof(struct product));
        start->head = start->head->next;
        start->head->title = malloc(strlen(title) + 1);
        strcpy(start->head->title, title);
        strncpy(start->head->code, code, 7);
        start->head->code[7] = 0;
        start->head->stock = stock;
        start->head->price = price;
    }
    return start->head;
}

/* Find product */
/* Parameters:
 * start: The head node
 * code: product code to be found
 * 
 * Returns: Pointer to the first instance of product, or NULL if not found
 */
struct product *find_product(struct product_list *start, const char *code) {
    while(start->head != NULL){
        if (!strcmp(start->head->code, code)) {
            return start->head;
        }else{
            start->head = start->head->next;
        }
    }
    return NULL;
}

/* Remove Product */
/* Parameters:
 * start: The head node
 * code: value to be removed
 *
 * Enough to remove first istance, no need to check for dublicates
 *
 * Returns: The number of removed items (0 or 1)
 */
int remove_product(struct product_list *start, const char *code) {
    if (!strcmp(start->head->code, code)) {
        free(start->head->title);
        free(start->head);
        start->head = start->head->next;
        return 1;
    }
    while(start->head->next !=NULL){
        if(!strcmp(start->head->next->code, code)){
            free(start->head->next->title);
            start->head->next = start->head->next->next;
            return 1;
        }else{
            start->head = start->head->next;
        }
    }
    return 0;
}

/* Delete list */
/* Parameters:
 * start: list head
 *
 * Returns: 1, when list has been deleted
 */
int delete_list(struct product_list *listhead) {
    while(listhead->head != NULL){
        free(listhead->head->title);
        listhead->head = listhead->head->next;
    }    
    return 1;
}

使用 VALGRIND 结果更新的代码：

#include <stdlib.h>
#include <stdio.h>
#include<string.h>

struct product {
    char *title;  // Name of the product
    char code[8]; // Max. 7 characters of product ID
    int stock;  // Current stock (number of units)
    double price;  // Price of a single unit
    struct product *next; // pointer to next item in linked list
};

struct product_list {
    struct product *head;
    // could have other list specific elements, like length of the list, last update time, etc.
    };

void init_list (struct product_list *list)
{
  list->head = malloc(sizeof(struct product));
}

/* Add product */
/* Parameters:
 * start: start of the linked list
 * title, code, stock, price: to be copied as created structure content
 * 
 * Returns: pointer to the newly added node in the linked list
 */
struct product *add_product(struct product_list *start, const char *title, const char *code,
        int stock, double price) {
    struct product_list *newStart = start;    
    while(newStart->head->next != NULL){
        newStart->head = newStart->head->next;
    }
    if(newStart->head->title == NULL){
        newStart->head->title = malloc(strlen(title) + 1);
        strcpy(newStart->head->title, title);
        strncpy(newStart->head->code, code, 7);
        newStart->head->code[7] = 0;
        newStart->head->stock = stock;
        newStart->head->price = price;
    }else{
        newStart->head->next = malloc(sizeof(struct product));
        newStart->head = newStart->head->next;
        newStart->head->title = malloc(strlen(title) + 1);
        strcpy(newStart->head->title, title);
        strncpy(newStart->head->code, code, 7);
        newStart->head->code[7] = 0;
        newStart->head->stock = stock;
        newStart->head->price = price;
    }
    return newStart->head;
}

/* Find product */
/* Parameters:
 * start: The head node
 * code: product code to be found
 * 
 * Returns: Pointer to the first instance of product, or NULL if not found
 */
struct product *find_product(struct product_list *start, const char *code) {
    struct product_list *newStart = start;
    while(newStart->head != NULL){
        if (!strcmp(newStart->head->code, code)) {
            return newStart->head;
        }else{
            newStart->head = newStart->head->next;
        }
    }
    return NULL;
}

/* Remove Product */
/* Parameters:
 * start: The head node
 * code: value to be removed
 *
 * Enough to remove first istance, no need to check for dublicates
 *
 * Returns: The number of removed items (0 or 1)
 */
int remove_product(struct product_list *start, const char *code) {
    struct product_list *newStart = start;
    if (!strcmp(newStart->head->code, code)) {
        free(newStart->head->title);
        free(newStart->head);
        newStart->head = newStart->head->next;
        return 1;
    }
    while(newStart->head->next !=NULL){
        if(!strcmp(newStart->head->next->code, code)){
            free(newStart->head->next->title);
            newStart->head->next = newStart->head->next->next;
            return 1;
        }else{
            newStart->head = newStart->head->next;
        }
    }
    return 0;
}

/* Delete list */
/* Parameters:
 * start: list head
 *
 * Returns: 1, when list has been deleted
 */
int delete_list(struct product_list *listhead) {
    while(listhead->head != NULL){
        free(listhead->head->title);
        listhead->head = listhead->head->next;
    }    
    return 1;
}

void print_product(struct product *p)
{
    printf("%s (%s) -- stock: %d, price: %lf\n",
                p->title, p->code,
                p->stock, p->price);
}

int main()
{
    struct product_list list;
    struct product *p;
    init_list(&list);
    add_product(&list, "test", "1234", 1, 0.50);
    add_product(&list, "Product 1", "0000", 0, 10);
    add_product(&list, "Long name, isn't it", "1234567890", 10, 100);
    add_product(&list, "Product 3", "9999999", 0, 20);
    p = find_product(&list, "0000");
    if (p)
        print_product(p);
    else
        printf("Not found\n");
    int i=remove_product(&list, "0000");
    printf("Removed %d items\n", i);
    delete_list(&list);
}

更新代码的 Valgrind 输出：

==20484== Memcheck, a memory error detector
==20484== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==20484== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==20484== Command: test
==20484== 
==20484== 
==20484== HEAP SUMMARY:
==20484==     in use at exit: 0 bytes in 0 blocks
==20484==   total heap usage: 31 allocs, 31 frees, 2,001 bytes allocated
==20484== 
==20484== All heap blocks were freed -- no leaks are possible
==20484== 
==20484== For counts of detected and suppressed errors, rerun with: -v
==20484== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Answer 1

您在此处的分配有效地从列表中删除了元素：

start->head = start->head->next;

您正在寻找的可能是获得一些指导

product* current;
product* nextEl = current->next;

并对其进行迭代：

while (nextEl != null) {
if (!strcmp(nextEl->code, code))  {
   product* current->next = nextEl->next;
   free (nextEl);
    return 1;
}
else {
   current = nextEl;
   nextEl = nextEl->next;
}

}
 return 0;

一般来说，你应该避免直接使用头指针，使用一些局部指针以防止损坏（比如在查找或添加函数中）

Answer 2

您更新后的代码存在完全相同的问题：

newStart->head = newStart->head->next;

newStart 只是起始指针的别名。

您应该在列表上迭代，而不仅仅是将其头部更新为下一个值。

例如列表

A -> B -> C

会像

一样关注您的第一次查找迭代

B -> C

由于分配不正确，您在头部丢失了一个元素。

应该是（例如）：

struct product *find_product(struct product_list *start, const char *code) {
    struct product_list *elem = start->head;
    while(elem  != NULL){
        if (!strcmp(elem->code, code)) {
            return elem;
        }else{
            elem = elem->next;
        }
    }
    return NULL;
}

链表逻辑错误

Error in Logic of linked list

c

debugging

valgrind

linked-list