鏈接列表的單個函數mergesort中的段錯誤

我在使用在線C++編譯器時遇到了分段錯誤，同時整天執行此單一函數mergesort，而我無法找到它可能存在的位置。另一個問題是，我不明白這種找到鏈表中間的方法，爲什麼它是賦值運算符，有沒有更好的方法來做到這一點？任何幫助將不勝感激。鏈接列表的單個函數mergesort中的段錯誤

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

struct listnode { struct listnode * next; int key; }; 

struct listnode * sort(struct listnode * a) 
{ 
    struct listnode *fast, *slow, *mid, *left, *right; 
    fast = a; left = a; right = NULL; mid = NULL; 

    //data is null or one node 
    if (!a || !a->next) 
    { 
     return a; 
    } 

    //find mid by declaring a pointer skipping throw an extra node for each loop 

    while (fast) 
    { 
     if (fast = fast->next) { fast = fast->next; } 
     mid = slow; 
     slow = slow->next; 
    } 

    //split the list in recursion 
    if (mid != NULL) { mid->next = NULL; } 

    a = sort(a); slow = sort(slow); 

    //merge 
    while (left != NULL && slow != NULL) 
    { 
     if (left->key < right->key) { left->next = mid; right = left; } 
     else 
     { 
      if (!right) 
       a = slow; 
      else 
      { 
       right = slow; right->next = slow; slow = slow->next; right->next = left; 
      } 
     } 

    } 
    if (left == NULL) { right->next = slow; } 
    return(a); 

} 


//test 


int main() 
{ 
    long i; 
    struct listnode *node, *tmpnode, *space; 
    space = (struct listnode *) malloc(500000 * sizeof(struct listnode)); 
    for (i = 0; i< 500000; i++) 
    { 
     (space + i)->key = 2 * ((17 * i) % 500000); 
     (space + i)->next = space + (i + 1); 
    } 
    (space + 499999)->next = NULL; 
    node = space; 
    printf("\n prepared list, now starting sort\n"); 
    node = sort(node); 
    printf("\n checking sorted list\n"); 
    for (i = 0; i < 500000; i++) 
    { 
     if (node == NULL) 
     { 
      printf("List ended early\n"); exit(0); 
     } 
     if (node->key != 2 * i) 
     { 
      printf("Node contains wrong value\n"); exit(0); 
     } 
     node = node->next; 
    } 
    printf("Sort successful\n"); 
    exit(0); 
}

來源

2016-09-15 user6820297

你應該學會如何使用調試器，它會告訴你分段故障在哪裏，你可以用它來遍歷程序，看看出了什麼問題。這也是C，而不是C++。沒有'免費'的'malloc'幾乎肯定是一個問題，但至少是非常不好的習慣。 – user4407569

...請使用適當的C++代碼和容器。這種濫用指針會讓我至少一週的噩夢。 –

...或使用C標籤。這段代碼似乎是用普通的C語言編寫的，並且可以用C編譯器編譯。 – Sergey

的至少一個問題是：

while (fast) 
{ 
    if (fast = fast->next) { fast = fast->next; } 
    mid = slow; 
    slow = slow->next; // <-------- HERE! 
}

fast此循環前被分配到非空值，所以控制進入循環並嘗試讀取slow->next，這是無效的。 slow指針沒有分配給循環之前的任何內容，因此它保存垃圾值並且不指向有效的內存位置。因此，用這個指針讀取內存很可能違反進程地址空間。從語言的角度來看，讀取未初始化的指針就是undefined behavior的一個例子。

另請參閱this問題的一個很好的解釋。

來源

2016-09-15 02:46:19 Sergey

是的，我已經固定那部分。我忘了把它分配給 – user6820297

@ user6820297 OK，現在如果在這種情況下指針處於「if（left-> key < right-> key」），現在它無法讀取內存。它發生在'sort'的第12次遞歸調用中。請使用調試器和/或內存分析器來修復此類錯誤。 – Sergey

鏈接列表的單個函數mergesort中的段錯誤

回答

相關問題