-1
У меня проблемы с моей функцией split в классе MergeSort. Он работает для первых нескольких, но затем я получаю ошибку сегментации. Я думаю, что это мой цикл for и выбор правильного среднего узла, но я не могу понять это.MergeSort со связанным списком - функция разделения C++
Любой помощь ценятся, вот мой код:
Заголовок:
#ifndef MERGE_LIST
#define MERGE_LIST
#include <iostream>
using namespace std;
class mergeList {
public:
struct node {
int data;
struct node* next;
};
mergeList();
void push(struct node** head_ref, int new_data);
void printList(struct node * nptr);
//void merge(struct node** headRef);
struct node* SortedMerge(struct node* a, struct node* b);
void merge(struct node** headRef);
private:
int size;
//void merge(struct node** headRef, int s);
//void split(struct node* headRef, struct node** a, struct node** b, int mid);
void split(struct node* source, struct node** frontRef, struct node** backRef, int s);
void merge(struct node** headRef, int s);
};
#endif
Источник:
#include "mergeList.h"
#include "stdlib.h"
mergeList::mergeList() {
size = 0;
}
void mergeList::push(struct node** head_ref, int new_data) {
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
size++;
}
void mergeList::printList(struct node * nptr) {
while(nptr) {
cout << nptr->data << " ";
nptr=nptr->next;
}
cout << endl;
}
void mergeList::merge(struct node** headRef) {
merge(headRef, size);
}
void mergeList::merge(struct node** headRef, int s)
{
if(s < 2)
return;
struct node* a;
struct node* b;
struct node* head = *headRef;
bool addOne = false;
int mid = s/2;
if(s % 2 != 0)
addOne = true;
cout << "B4 SPLIT!" << endl;
cout << "AddOne: " << addOne << endl;
cout << "s: " << s << endl;
split(head, &a, &b, s);
merge(&a, mid);
//if(addOne)
// mid++;
merge(&b, mid);
*headRef = SortedMerge(a, b);
}
//Use a pointer to split the list
void mergeList::split(struct node* headRef, struct node** _a, struct node** _b, int s) {
struct node* a;
//struct node* b;
if (s < 2) {
*_a = headRef;
*_b = NULL;
}
else {
a = headRef;
if(s != 2) {
for(int i = 0; i < s/2; i++)
a = a->next;
}
*_a = headRef;
*_b = a->next;
a->next = NULL;
}
}
struct mergeList::node* mergeList::SortedMerge(struct node* a, struct node* b) {
struct node* result = NULL;
if (a == NULL)
return b;
else if (b == NULL)
return a;
if(a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
}
else {
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
Я не знаю, как его использовать, но я знаю его где-то в цикле for или после цикла – dajee
@David. Тогда вы должны подумать, что это хорошая возможность научиться использовать инструменты отладки. Если вы продолжите программирование, вам нужно будет научиться в какой-то момент. – kappamaki
Те же чувства, что и каппамаки. Они очень просты в использовании, чтобы делать простые вещи, такие как поймать segfault или выяснить, где бесконечный цикл. Google "gdb cheat sheet", чтобы начать. Вам нужно будет скомпилировать флажок -g, чтобы сообщить компилятору оставить информацию об отладке. Это точно скажет вам, в какой строке находится ваша проблема, и сэкономьте часы, проливая исходный код или даже добавляя отладочные заявления. Использование отладчика = хороший вид ленивого, откладывание обучения = плохой вид ленивого. – djechlin