1

私は一般的な二重リンクリストの実装を持っており、挿入に取り組んでいました。挿入後、リストの末尾から逆方向に反復しようとすると、バス エラーが発生します。コードをテストし、print ステートメントを散りばめたエラーを分離しようとします (最適なデバッグ手順ではありませんが、コードが何を行っているかを一目で確認するのに役立ちます)。問題がどこで発生するかを確認するために、挿入のたびに、リストの最後から 2 番目の要素の値を要求します。私は常に 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 は、単純な 'is a greater than 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 (上記を参照) を要求する行に到達します。

最終編集: ノード データに十分なスペースを適切に malloc することで問題を解決しました。助けてくれた人に感謝します。私のコードには他にも問題がありますが、それは別の質問、および別のコード スニペットに関するものに最適です。

4

1 に答える 1

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は、コピーではなく直接使用しています。したがって、この関数を常に同じブロックで呼び出さないと、問題が発生します

同じ関数シグネチャを使用して、サイズパラメーターは値パラメーターのサイズを表し、malloc / memset を作成してリストに保存する必要があると思います

于 2011-08-11T20:11:29.303 に答える