-1

I'm having issues with my split function in my MergeSort class. It works for the first few, but then I get a segmentation fault. I think it's my for loop and choosing the correct middle node, but I can't figure it out.

Any help is appreciated, here is my code:


Header:

#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

Source: 

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

1 に答える 1

0

gdb や dbx などのデバッガーで実行して、セグメンテーション違反が発生している場所を確認しましたか?

于 2012-04-17T23:42:50.507 に答える