MergeSort與鏈接列表 - 拆分函數C++

Question

我遇到了我的MergeSort類中的拆分函數的問題。它適用於前幾個，但後來我得到了分段錯誤。我認爲這是我的循環，並選擇正確的中間節點，但我無法弄清楚。

任何幫助表示讚賞，這裏是我的代碼：

頁眉：

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

Answer 1

有你在調試器中運行，如GDB或dbx查看它在哪裏進行分割？