链接列表和（字母）气泡排序

Question

我有一个问题与链接列表的气泡排序。几个小时后，我还没有在我的简单代码中发现错误。你可以看看吗？

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 

    for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 
    } 

    return 0; 
} 

和这里的交换功能（但它似乎很好地工作，因为我测试了手动将所有边界情况）：

int listSwapWithNext(node_t **_list, size_t first) 
{ 
    node_t *pointer = *_list; 
    node_t *ptr_b; 
    node_t *ptr_c; 
    node_t *ptr_d; 

    if(!first) 
      ptr_b = pointer; 

    for(size_t i = 0; pointer->next->next; i++, pointer = pointer->next) 
    { 
      if(i == first - 1 || first == 0) 
      { 
       if(first) 
        ptr_b = pointer->next; 

       ptr_c = ptr_b->next; 
       ptr_d = ptr_c->next; 

       if(first) 
        pointer->next = ptr_c; 
       else 
        *_list = ptr_c; 

       ptr_c->next = ptr_b; 
       ptr_b->next = ptr_d; 

       break; 
      } 
    } 

    return 0;  
} 

它会导致此崩溃（上线229）：

当我在分类功能中将内环的限制修改为：

for(int j = 0; j < size - 1 && pointer->next; j++) 

为防止读取不好的地址，我注意到奇怪的事情。内部循环的运行时间比它应该少一次。

谢谢！

编辑： 这里的修改排序功能的版本与内环（（）与printf的制作）防止病情和我的调试指标：

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

这里的结果控制台。看，它并不是每个周期都做，所以它给了不好的排序。

EDIT2： 这里的问题essention。 http://pastebin.com/e5K6C1A2

仍无法解决此问题。

Answer 1

pointer = pointer->next在进行交换的情况下不正确。如果您进行了交换，pointer应保持为pointer，因为它已经向前移动了一个元素。

编辑：我的意思是这样：

if(strcmp(pointer->title, pointer->next->title) > 0) 
    listSwapWithNext(_list, j); 
else 
    pointer = pointer->next; 

Answer 2

根据您所说的我相信我可以帮助您识别代码中的几个问题。我相信你所描述的问题是由你发布的第一块代码引起的，特别是这一部分。

for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 

的问题是由该行抛出：

if(strcmp(pointer->title, pointer->next->title) > 0) 

，因为如何内环在这里建造：

for(int j = 0 ; j < size - 1; j++) 

所以，你占的事实，因为我们交换我们需要1比列表的总大小。但问题在于，这导致您试图在最后一次运行时通过它解引用空指针。链表中的节点包含指向某些数据的指针和指向下一个对象的指针。因此，让我们想象一下第二次到最后一次for循环执行时会发生什么。如果strcmp为真，它会进行交换，然后它将指针指向引用链接列表中的下一个元素。这是你出错的地方。因为你这样做，当我们再次执行循环，这条线：

if(strcmp(pointer->title, pointer->next->title) > 0) 

明确这部分内容： pointer->next->title 将失败，因为当前对象是链表中的最后一个元素。由于这个原因，它的下一个指向NULL，你试图获得一个NULL元素的标题对象，它不存在。

现在让我们看看您的修改后的代码。

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

你不会遭受同样的错误，但你得到不正确的结果。这不是由排序功能引起的，这同样是由施工引起的for循环在这里：

for(j = 0 ; j < size - 1 && pointer->next; j++) 

一个for循环将只要指定条件为真执行。再次让我们想象第二个到最后一个执行。我们在我们的大小范围内，所以第一个条件是真实的，在这之后存在另一个元素，所以第二个条件也是如此。循环运行并将指针前进到下一个元素。现在我们仍然在我们的尺寸限制内，所以这是真的，但是在此之后没有更多元素在列表中，因此pointer->next是NULL。这意味着循环将不会运行，因此不会对所有数据进行排序，从而给您带来不好的结果。