この単一の関数mergesortを終日行っている間に、オンラインC++コンパイラを使用してセグメンテーション違反に遭遇しています。もう1つの問題は、リンクされたリストの中間を見つけるこの方法を理解していない方法、なぜ代入演算子なのか、それを行う良い方法があるということです。どんな助けもありがとう。リンクされたリストの単一関数mergesort内のセグメントの障害
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);
}
デバッガの使い方を学ぶ必要があります。デバッガを使用すると、セグメンテーションフォルトがどこにあるのかがわかり、プログラムをステップ実行して何がうまくいかないかを知ることができます。これはC++ではなくCでもあります。そして、ほとんど確実に問題があるが、少なくとも極端に悪い習慣である 'free'なしの' malloc'があります。 – user4407569
...適切なC++コードとコンテナを使用してください。このポインタの乱用は、少なくとも1週間私に悪夢を与えるだろう。 –
...またはCタグを使用してください。このコードは普通のC言語で書かれており、Cコンパイラでうまくコンパイルされているようです。 – Sergey