1

我有一个通用的双向链表实现，并且正在插入。插入后，我尝试从脚开始向后迭代列表，但出现总线错误。为了测试代码并尝试隔离我在其中添加了打印语句的错误（这不是最好的调试过程，但有助于一目了然地告诉我我的代码在做什么）。为了尝试查看问题出在哪里，每次插入后，我都会询问列表中倒数第二个元素的值。我总是按 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);
}

还有更多内容，但这就是我现在正在测试的全部内容。

感谢列表-> 大小提示，我不太确定我最初在想什么。

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

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

4

1 回答 1

1

一些东西：

正如已经说过的， list->size = sizeof(list);可能不会像你想的那样

传递的size_t sizeas 参数可能是您的主要问题并且看起来很危险（当您调用函数时这个变量值是什么？）

使用dlnode_t * newnode = safe_malloc(size);错误的尺寸可以解释您的问题

dlnode_t * newnode = safe_malloc(size);

可能应该被替换为

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

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

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

于 2011-08-11T20:11:29.303 回答