冒泡排序與鏈接列表

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

的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 

爲什麼打印6個項目時，請求5？重複執行時，第一個元素的值始終爲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)); 
} 

你不希望分號。用這個固定的代碼運行OK：

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，沒有崩潰，數據中有一些重複，輸出按降序排列。