リンクされたリストの単一関数mergesort内のセグメントの障害

Question

この単一の関数mergesortを終日行っている間に、オンラインC++コンパイラを使用してセグメンテーション違反に遭遇しています。もう1つの問題は、リンクされたリストの中間を見つけるこの方法を理解していない方法、なぜ代入演算子なのか、それを行う良い方法があるということです。どんな助けもありがとう。

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

fastこのループ前に、非ヌル値に割り当てられていたので、制御がループに入り、無効であるslow->nextを読み取ろう：

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

Answer 1

少なくとも一つの問題です。 slowポインタはループの前のものに割り当てられていないため、ガベージ値を保持し、有効なメモリ位置を指しません。したがって、このポインタによるメモリの読み取りは、プロセスアドレス空間に違反する可能性が非常に高いです。また、言語の観点からは、初期化されていないポインタの読み取りはundefined behaviorの例です。

また、this質問の良い説明も参照してください。