5

私はCの新入生で、今すぐリンクリストを学びます。リンクリストをバブルソートすると、セグメンテーション違反が発生し、GDBは関数バブル（）、i =ptr->elemを指します。何が原因なのかわかりません。理解するのを手伝ってください。

`

#include    <stdio.h>
#include    <stdlib.h>
#include    <time.h>
#include    <string.h>

define      i_track(n)  printf ("The %s's is %d.\n", #n, (n))
define      s_track(n)  printf ("%s.\n", #n);


typedef struct tag_node
{
    int elem;
struct tag_node *next;
}NODE, *SLINK; 

void  node_track (SLINK list);
NODE *node_generate (void);
void init_list (SLINK *header, int len);
SLINK locate_cur (SLINK list, int target_elem);
void insert_node (SLINK *list, int new_elem, int tag_elem);
SLINK traverse_list (SLINK list);
void list_info (SLINK list, int node_elem);
void bubble (SLINK list);
void swap (int *a, int *b);

int main (int argc, char *argv[])
{
int len;
SLINK list = node_generate ();
printf ("Input a number for length of the link.\n");
scanf ("%d", &len);
s_track(init_start.);
init_list (&list, len);
s_track(init_end.);
traverse_list (list);
bubble (list);

return EXIT_SUCCESS;
}   /* ----------  end of function main  ---------- */          

NODE *node_generate (void) /* generate a node */
{
NODE *new_node = malloc (sizeof (NODE));
if (NULL == new_node)
{
    printf ("ERROR: malloc failed.\n");
    exit (EXIT_FAILURE);
}
memset (new_node, 0, sizeof(NODE));
return new_node;
}

void insert_node (SLINK *list, int new_elem, int tag_elem)
/* insert a node */
{
NODE *new_node = node_generate ();
NODE *cur = *list;
new_node->elem = new_elem;
if ((int)NULL == tag_elem)
{
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
else
{
    *list = locate_cur (cur, tag_elem);
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
}

void init_list (SLINK *header, int len)
/* generate a linked-list and assign it*/
{
srand ((unsigned) time(0));
int elem;
for (int i = 0; i < len; i++)
    /* skip number 4 since I dislike it */
    {
        elem = rand () % 100;

        if (4 == elem / 10)
        {
            elem = elem + 50;
        }
        if (4 == elem % 10)
        {
            elem = elem + 5;
        }
        if (0 == elem % 100)
        {
            elem = elem + 999;
        }
        insert_node (header, elem, (int)NULL);  
    }
}

SLINK traverse_list (SLINK list)
/*traverse list */
{
SLINK ptr = list;
for (int node_num = 0; ptr != NULL; ptr = ptr->next)
{
    ++node_num;
    list_info (ptr, node_num);
}
return list;
}

void list_info (SLINK list, int node_num)
/* used for traversed_list () */
{
if (1 == node_num % 10 && 11 != node_num)
{
    printf ("The %dst element is %d.\n", node_num, list->elem);
}
else if (2 == node_num % 10 && 12 != node_num)
{
    printf ("The %dnd element is %d.\n", node_num, list->elem);
}
else if (3 == node_num % 10 && 13 != node_num)
{
    printf ("The %drd element is %d.\n", node_num, list->elem);
}
else
{
    printf ("The %dth element is %d.\n", node_num, list->elem);
}
}

SLINK locate_cur (SLINK list, int target_elem)
/* locate previous of a node */
{
NODE *prev, *cur;
prev = node_generate ();
cur = node_generate ();
for (prev = list, cur = list->next; NULL != cur && target_elem != cur->elem; prev = cur, cur = cur->next)
    ;
return cur;
}

void node_track (NODE *flag)
{
printf ("The flag element is %d.\n", flag->elem);
}

void bubble (SLINK list) /* bubble sort */
{
s_track(bubble_start);
list = list->next;
SLINK ptr, header;
ptr = list; /*GDB point to here*/
int i =0, j = 0;
for (; NULL != list; list = list->next)
{
    for (ptr = list; NULL != ptr; ptr = ptr->next);
    {
        j = list->elem;
        i = ptr->elem;
    //  if (ptr->elem > list->elem)
        if (i > j)
            swap (&(ptr->elem), &(list->elem));
    }
}
s_track(bubble_end);
}

void swap (int *a, int *b)
{
*a = (*a)^(*b);
*b = (*a)^(*b);
*a = (*a)^(*b);
}

`

4

1 に答える 1

1

の目的tag_elemはinit_list()非常に不明確です。その変数を削除するようにコードを変更してから実行し、入力値として5を指定しました。それは与えます：

Input a number for length of the link.
5
init_start..
init_end..
The 1st element is 0.
The 2nd element is 12.
The 3rd element is 8.
The 4th element is 99.
The 5th element is 7.
The 6th element is 63.
bubble_start.
Segmentation fault: 11

5つが要求されたときに6つのアイテムが印刷されるのはなぜですか？繰り返し実行すると、最初の要素の値は常に0（3回の繰り返し）になります。

この問題は、次のように修正することで修正できますtraverse_list()。

SLINK traverse_list(SLINK list)
{
    assert(list != 0); 
    SLINK ptr = list->next;
    for (int node_num = 0; ptr != NULL; ptr = ptr->next)
        list_info(ptr, ++node_num);
    return list;
}

興味深いことに、のコードはbubble()すでにリストの最初の項目をスキップしています。

ただし、の内側のループにbubble()は誤りがあります。

for (ptr = list; NULL != ptr; ptr = ptr->next);
{
    j = list->elem;
    i = ptr->elem;
//  if (ptr->elem > list->elem)
    if (i > j)
        swap (&(ptr->elem), &(list->elem));
}

次のように書くと見やすくなるかもしれません。

for (ptr = list; NULL != ptr; ptr = ptr->next)
    ;
{
    j = list->elem;
    i = ptr->elem;  // When this is executed, ptr == NULL!
    if (i > j)
        swap (&(ptr->elem), &(list->elem));
}

そのセミコロンは必要ありません。これを修正すると、コードは正常に実行されます。

Input a number for length of the link.
5
init start.
init end.
The 1st element is 12.
The 2nd element is 19.
The 3rd element is 99.
The 4th element is 92.
The 5th element is 28.
traverse 1 end.
bubble_start.
bubble_end.
sort end.
The 1st element is 99.
The 2nd element is 92.
The 3rd element is 28.
The 4th element is 19.
The 5th element is 12.
traverse 2 end.

明らかに、わずかに変更された診断印刷のセットですが、データは降順で並べ替えられています。より大きなセットでも機能するようです。55を試してみましたが、クラッシュは発生せず、データが何度か繰り返され、出力は降順で並べ替えられました。

于 2012-11-19T05:55:22.263 に答える