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 回答