数据结构 - 链表 C 的分段错误

Question

我正在为一个类创建一个链表，但在搜索和打印时不断出现分段错误。我认为这与数据结构未正确定位有关，但是我已经尝试了很多方法，但都遇到了相同的错误。任何帮助都会很棒

    struct LList_data {
        int x;
        int y;
    }
    struct LList {
        struct LList_data * data;
        // data=(struct LList_data *)malloc(sizeof(struct LList_data));
        struct LList * next;
    }
struct LList * LList_create()
{
        struct LList * list;
        list = (struct LList *)malloc(sizeof(struct LList));
        list->next = NULL;
        return list;
}
    void LList_push_front(struct LList * list, struct LList_data newdata)
    {
        struct LList * node;
        struct LList_data * data;
        node = (struct LList *)malloc(sizeof(struct LList));
        data = (struct LList_data *)malloc(sizeof(struct LList_data));
        node->data = data;
        node->data->x = newdata.x;
        node->data->y = newdata.y;
        node->next=list->next;
        list->next=node;
        return;
    }
    int LList_find(struct LList * list, int x, struct LList_data * data)
    {
            struct LList * node;
    //      if(list == NULL)
    //      printf("list empty");
    //      if(!list->next==NULL)
    //      printf("list next empty");
            for(node=list->next; node!= NULL; node=node->next){
              if(x == node->data->x){
                node->data=data;
                return 1;
                }
            }
            return 0;
    }
    int LList_update(struct LList * list, struct LList_data newData)
    {
            struct LList * node;
            node = list->next;
            while(node)
            {
              if(node->data->x == newData.x)
              {
              node->data = &newData;
              return 1;
              }
              node=node->next;
            }
            return 0;
    }
    int LList_remove(struct LList * list, int x, struct LList_data * data)
    {
            struct LList * node;
            struct LList * prev;
            node = list->next;
            while(node)
            {
              prev = node;
              node = node->next;
            }
            if(node == NULL)
              return 0;
            prev->next = node->next;
            return 1;
    }
    void LList_destroy(struct LList * list)
    {
            struct LList * temp = list->next;
            struct LList * next;
            while(temp)
            {
              next = temp->next;
              free(temp);
              temp = next;
            }
            free(list);
    }
    void LList_print(struct LList * list)
    {
            struct LList * temp;
            temp=list;
            if(temp!=NULL){
            while(temp!=NULL)
              {
              printf("%d,%d",temp->data->x, temp->data->y);
              temp=temp->next;
              }
            temp->next = (struct LList *)malloc(sizeof(struct LList));
            temp->next = NULL;
            }
    }

这是使用列表的内容

#include"llist.h"
#include<stdio.h>
#include<stdlib.h>
void menu();
void a(struct LList * list);
void c(struct LList * list);
void f(struct LList * list);
void r(struct LList * list);
void p(struct LList * list);
int main(){
        menu();
        return 0;
}

void menu()
{
        char choice;
        struct LList * list;
        list = LList_create();
        scanf(" %c", &choice);
        switch(choice){
          case 'a':
          case 'A':
                a(list);
                break;
          case 'C':
          case 'c':
                c(list);
                return;
                break;
          case 'f':
          case 'F':
                f(list);
                return;
                break;
          case 'r':
          case 'R':
                r(list);
                return;
                break;
          case 'p':
          case 'P':
                p(list);
                return;
                break;
          default:
                fprintf(stderr, "Invalid choice n");
                menu();
                return;
        }
}
void a(struct LList * list)
{
        int x;
        struct LList_data data;
        scanf(" %d", &x);
        data.x = x;
        data.y = 0;
        LList_push_front(list,data);
        printf("%d,%d n", data.x,data.y);
        menu();
        return;
}
void c(struct LList * list)
{
        LList_destroy(list);
        list =  LList_create();
        menu();
        return;
}
void f(struct LList * list)
{
        int x;
        struct LList_data * data;
        data=NULL;
        scanf(" %d", &x);
        LList_find(list, x, data);
        data->y += 1;
        printf("%d,%d", data->x,data->y);
        menu();
        return;
}
void r(struct LList * list)
{
        int x;
        struct LList_data * data;
        scanf(" %d", &x);
        data=NULL;
        LList_find(list, x, data);
        printf("%d,%d", data->x,data->y);
        LList_remove(list, x, data);
        menu();
       return;
}
void p(struct LList * list)
{
        LList_print(list);
        menu();
        return;
}

Answer 1

几件事...

从子函数递归调用menu（例如 p）不是一件好事。在main中循环menu要好得多

打印功能正在添加新元素？！

find 函数只返回 0/1，但从未返回指向"found"元素的指针。

我已经注释并修复了[大多数]错误。当我这样做时（在可能的情况下），我将原始代码留在#if 0中，并将更正后的代码留在相应的#else部分中。注释更详细地说明了一些问题是什么。我希望比较原始代码和修改后的代码会有所启发。

我不得不更改一些链表函数参数/返回值，以便它们有意义。

无论如何，这是代码，为了简单起见，我将其合并到一个文件中[请原谅无端的样式清理]：

//#include "llist.h"
#include <stdio.h>
#include <stdlib.h>
struct LList_data {
    int x;
    int y;
};
struct LList {
    struct LList_data *data;
    // data=(struct LList_data *)malloc(sizeof(struct LList_data));
    struct LList *next;
};
struct LList *
LList_create()
{
    struct LList *list;
    list = (struct LList *) malloc(sizeof(struct LList));
    list->next = NULL;
    return list;
}
void
LList_push_front(struct LList *list, struct LList_data newdata)
{
    struct LList *node;
    struct LList_data *data;
#if 0
    node = (struct LList *) malloc(sizeof(struct LList));
    data = (struct LList_data *) malloc(sizeof(struct LList_data));
#else
    node = malloc(sizeof(*node));
    data = malloc(sizeof(*data));
#endif
    node->data = data;
    node->data->x = newdata.x;
    node->data->y = newdata.y;
    node->next = list->next;
    list->next = node;
    return;
}
#if 0
int
LList_find(struct LList *list, int x, struct LList_data *data)
{
    struct LList *node;
    // if(list == NULL)
    // printf("list empty");
    // if(!list->next==NULL)
    // printf("list next empty");
    // NOTE/BUG: this entire function is just to _find_ a node [to be used by
    // other functions], so it should _not_ try to change anything
    for (node = list->next; node != NULL; node = node->next) {
        // NOTE/BUG: this replaces node->data without freeing it first (i.e.
        // this is a memory leak)
        if (x == node->data->x) {
            node->data = data;
            return 1;
        }
    }
    return 0;
}
#else
struct LList_data *
LList_find(struct LList *list, int x)
{
    struct LList *node;
    struct LList_data *data;
    data = NULL;
    for (node = list->next; node != NULL; node = node->next) {
        if (x == node->data->x) {
            data = node->data;
            break;
        }
    }
    return data;
}
#endif
int
LList_update(struct LList *list, struct LList_data newData)
{
    struct LList *node;
    node = list->next;
    while (node) {
        // NOTE/BUG: newData is on the _stack_ and when this function returns
        // newData will go out of scope (i.e. node->data will become invalid)
#if 0
        if (node->data->x == newData.x) {
            node->data = &newData;
            return 1;
        }
#else
        // NOTE/FIX: reuse the existing data cell and populate with new data
        if (node->data->x == newData.x) {
            *node->data = newData;
            return 1;
        }
#endif
        node = node->next;
    }
    return 0;
}
int
LList_remove(struct LList *list, /*-int x,-*/ struct LList_data *data)
{
    struct LList *node;
    struct LList *next;
    struct LList *prev;
    prev = NULL;
    // NOTE: passing "x" really not required since "data" points to the node
    // to be removed
    for (node = list->next;  node != NULL;  node = next) {
        next = node->next;
        if (node->data == data)
            break;
        prev = node;
    }
    if (node != NULL) {
        if (prev != NULL)
            prev->next = next;
        else
            list->next = next;
        free(node->data);
        free(node);
    }
}
void
LList_destroy(struct LList *list)
{
    struct LList *temp = list->next;
    struct LList *next;
#if 0
    // NOTE/BUG: this does _not_ free the data associated with each list
    // element (i.e. a memory leak)
    while (temp) {
        next = temp->next;
        free(temp);
        temp = next;
    }
#else
    while (temp) {
        next = temp->next;
        free(temp->data);
        free(temp);
        temp = next;
    }
#endif
    free(list);
}
void
LList_print(struct LList *list)
{
    struct LList *temp;
    // NOTE/BUG: a list print function has no need to add to or change the
    // list
#if 0
    temp = list;
    if (temp != NULL) {
        while (temp != NULL) {
            printf("%d,%d", temp->data->x, temp->data->y);
            temp = temp->next;
        }
        temp->next = (struct LList *) malloc(sizeof(struct LList));
        temp->next = NULL;
    }
#else
    for (temp = list->next;  temp != NULL;  temp = temp->next)
        printf("%d,%dn", temp->data->x, temp->data->y);
#endif
}
void menu(void);
void a(struct LList *list);
struct LList *c(struct LList *list);
void f(struct LList *list);
void r(struct LList *list);
void p(struct LList *list);
struct LList *mainlist;
int
main()
{
    mainlist = LList_create();
    while (1) {
        menu();
    }
    return 0;
}
void
menu(void)
{
    struct LList *list;
    char choice;
    list = mainlist;
    printf("a -- a new elementn");
    printf("c -- recreate empty listn");
    printf("f -- find list element and incrementn");
    printf("r -- remove element from listn");
    printf("p -- print listn");
    printf("menu> ");
    fflush(stdout);
    scanf(" %c", &choice);
    switch (choice) {
    case 'a':
    case 'A':
        a(list);
        break;
    case 'C':
    case 'c':
        mainlist = c(list);
        //return;
        break;
    case 'f':
    case 'F':
        f(list);
        //return;
        break;
    case 'r':
    case 'R':
        r(list);
        //return;
        break;
    case 'p':
    case 'P':
        p(list);
        //return;
        break;
    default:
        fprintf(stderr, "Invalid choice n");
#if 0
        menu();
        return;
#endif
        break;
    }
}
void
a(struct LList *list)
{
    int x;
    struct LList_data data;
    printf(" Enter value to add: ");
    fflush(stdout);
    scanf(" %d", &x);
    data.x = x;
    data.y = 0;
    LList_push_front(list, data);
    printf("%d,%d n", data.x, data.y);
#if 0
    menu();
    return;
#endif
}
struct LList *
c(struct LList *list)
{
    LList_destroy(list);
    // NOTE/BUG: "list" goes out of scope, so recreating it here has no useful
    // effect without returning the value
    list = LList_create();
#if 0
    menu();
    return;
#endif
    return list;
}
void
f(struct LList *list)
{
    int x;
    struct LList_data *data;
    data = NULL;
    printf(" Enter value to find/increment: ");
    fflush(stdout);
    scanf(" %d", &x);
    data = LList_find(list, x);
    if (data != NULL) {
        data->y += 1;
        printf("%d,%dn", data->x, data->y);
    }
#if 0
    menu();
    return;
#endif
}
void
r(struct LList *list)
{
    int x;
    struct LList_data *data;
    printf(" Enter value to remove: ");
    fflush(stdout);
    scanf(" %d", &x);
    data = NULL;
    // NOTE/BUG: "data" will always be null because LList_find never set it
    // to anything
#if 0
    LList_find(list, x, data);
    printf("%d,%dn", data->x, data->y);
#else
    data = LList_find(list, x);
    if (data != NULL) {
        printf("%d,%dn", data->x, data->y);
        LList_remove(list, data);
    }
#endif
#if 0
    menu();
    return;
#endif
}
void
p(struct LList *list)
{
    LList_print(list);
#if 0
    menu();
    return;
#endif
}