リンクリスト付きバブルソート

Question

私はCの新入生で、リンク先を今すぐ学ぶことができます。リンクリストをバブルソートすると、セグメントエラーが発生し、GDBは関数bubble（）、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); 
} 

`

Answer 1

init_list()でtag_elemの目的は、非常に不明瞭です。その変数を削除するようにコードを修正し、それを実行して入力値として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; // When this is executed, ptr == NULL! 
    if (i > j) 
     swap (&(ptr->elem), &(list->elem)); 
} 

あなたはそのセミコロンをしたくない：

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)); 
} 

あなたのようにそれを書くかどうかを確認する方が簡単かもしれません。明らか

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. 

、診断印刷のわずかに変更セットが、データが降順にソートされる：それは固定で、コードが実行OK。より大きなセットでも動作するようです。私は、クラッシュなし、データ中の繰り返し、降順でソートされた出力を55回試しました。