c - 排序的双向链表在反向访问时给出总线错误

Question

我有一个通用的双向链表实现，并且正在研究插入。插入后，我尝试从 footer 开始向后遍历列表，但出现总线错误。为了测试代码并尝试隔离错误，我在其中添加了打印语句(不是最好的调试过程，但有助于让我一目了然地告诉我我的代码在做什么)。为了尝试查看问题出在哪里，每次插入后我都会询问列表中倒数第二个元素的值。我总是按 5、2、10、80、4、1、7、8 的顺序插入元素，在将 4 插入列表后，它一直卡住。程序的完整代码如下。

dlist_t *
insert_in_order (dlist_t *list, void *value, size_t size,
    int (*cmp_fptr)(const void *, const void *))
{
dlnode_t * prev = NULL;
dlnode_t * current = list->head;
dlnode_t * newnode = safe_malloc(sizeof(dlnode_t));

newnode->data = value;
newnode->next = NULL;
newnode->prev = NULL;

printf("Beginning list loop for %d.\n", *(int *) newnode->data);
while (current != NULL && cmp_fptr(newnode->data, current->data) != -1)
{
    prev = current;
    current = current->next;
}
printf("Insertion point found.\n");

newnode->next = current;
newnode->prev = prev;

if (prev == NULL)
{
    printf("Setting for new head\n");
    list->head = newnode;
}
else
{
    printf("Setting previous next to new node\n");
    prev->next = newnode;
}

if (current == NULL)
{
    printf("setting for new foot.");
    list->foot = newnode;
}
else
{
    printf("Setting for new current previous\n");
    current->prev = newnode;
}

list->list_len++;
list->size = sizeof(list);
printf("Insertion compete for %d\n\n", *(int *) newnode->data);
printf("Data for surrounding:\n");
if(newnode->next !=NULL)
{
    printf("Next is %d \n", *(int *) newnode->next->data);
}
if(newnode->prev != NULL)
{
    printf("Prev is %d \n\n", *(int *) newnode->prev->data);
}

if(list->foot->prev != NULL)
{
    printf("Gonna print secondlast!\n");
    printf("secondlast is%d \n\n", *(int *)list->foot->prev->data);
}

return list;
}

列表定义很基础，就

struct dlnode
{
  void *data;     /* A pointer to a generic satellite data payload */ 
  dlnode_t *next; /* A pointer to the next item in the list */
  dlnode_t *prev; /* A pointer to the previous item in the list */
};

typedef struct
{
  dlnode_t *head; /* A pointer to the head node of the list */
  dlnode_t *foot; /* A pointer to the foot node of the list */
  int list_len;   /* Total number of items in the list */
  int size;       /* Size of the list in bytes */
} dlist_t;

您可以根据需要更改函数定义，而 safe_malloc 只是 malloc 的一种快捷方法，如果您自己测试代码，可以替换它。 cmp_fptr 是指向简单“大于 b”方法的函数指针。

编辑:更新 线路

printf("secondlast is%d \n\n", *(int *)list->foot->prev->data);

是导致程序停止的原因，我使用了调试器。将项目插入列表时，它会在插入几次后停在该行。 以下是我现在正在使用的测试工具代码。

int *
alloc_data (int val)
{
  int *rv = safe_malloc (sizeof (int));
  *rv = val;
  return (rv);
}

int
main (void) 
{
  dlist_t *list = NULL;
  int *num = NULL, *rv = NULL;
  dlnode_t *tnode = NULL;

  list = make_empty_list ();

  list = insert_in_order (list, alloc_data (5), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (2), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (10), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (80), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (4), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (1), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (7), sizeof(int), cmp_int); 
  list = insert_in_order (list, alloc_data (8), sizeof(int), cmp_int);
  return(EXIT_SUCCESS);
}

还有更多内容，但我目前正在测试的就是这些。

感谢 list->size 提示，我不太确定我最初是怎么想的。

edit2:感谢 safe_malloc 错误发现，我认为这是问题的原因，但我仍然遇到同样的错误。调试器在插入 4 后给了我一个 sigsegv(段错误)，它到达了我要求 list->foot->prev->data(见上文)的理智行。

最终编辑:通过为节点数据正确分配足够的空间来解决问题。感谢那些提供帮助的人。我的代码中还有其他问题，但这最适合另一个问题，并且关于不同的代码片段。

Answer 1

一些事情:

正如已经说过的那样， list->size = sizeof(list); 可能不会按照您的想法行事

作为参数传递的 size_t size 可能是您的主要问题并且看起来很危险(调用函数时这个变量值是多少？)

使用错误的大小执行 dlnode_t * newnode = safe_malloc(size); 可以解释您的问题

dlnode_t * newnode = safe_malloc(size);

应该替换为

dlnode_t * newnode = safe_malloc(sizeof(dlnode_t));

最后，在您的列表中，您直接使用 void *value 而不是它的副本。 所以如果你不总是在同一个 block 中调用这个函数，你就会遇到问题

使用相同的函数签名，我认为 size 参数应该代表 value 参数的大小，以便制作它的 malloc/memset 并将其保存在您的列表中