冒泡排序与链接列表

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，没有崩溃，数据中有一些重复，输出按降序排列。