マージソートエラー

Question

私はいくつかのテキストファイルを持っています。私はそれらを読んでリンクリストに各行を挿入するコードを持っています。次に、マージソートを使用してリンクリストをソートします。
これは小さなテキストファイルでは問題ありませんが、非常に大きなファイルではスタックオーバーフローエラーが発生します。複数の試験後

#include <iostream> 
#include <cstdio> 
#include <string> 
#include <cstdlib> 
#include <fstream> 
using namespace std; 
struct node 
{ 
    string data; 
    int num; 
    struct node* next; 
}; 
struct node* SortedMerge(node* a, node* b); 
void FrontBackSplit(node* source, node** frontRef, node** backRef); 
/* sorts the linked list by changing next pointers (not data) */ 
void MergeSort(struct node** headRef) 
{ 
    node* head = *headRef; 
    node* a; 
    node* b; 
    if ((head == NULL) || (head->next == NULL)) 
    { 
     return; 
    } 
    FrontBackSplit(head, &a, &b); 
    MergeSort(&a); 
    MergeSort(&b); 
    *headRef = SortedMerge(a, b); 
} 
/* merge the sorted linked lists */ 
node* SortedMerge(struct node* a, struct node* b) 
{ 
    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; 
} 
    /* Split the nodes of the given list into front and back halves*/ 
void FrontBackSplit(node* source, node** frontRef, node** backRef) 
{ 
    node* fast; 
    node* slow; 
    if (source==NULL || source->next==NULL) 
    { 
     *frontRef = source; 
     *backRef = NULL; 
    } 
    else 
    { 
     slow = source; 
     fast = source->next; 
     while (fast != NULL) 
     { 
      fast = fast->next; 
      if (fast != NULL) 
      { 
       slow = slow->next; 
       fast = fast->next; 
      } 
     } 
     *frontRef = source; 
     *backRef = slow->next; 
     slow->next = NULL; 
    } 
} 
/* print nodes in a given linked list */ 
void printList(node *node) 
{ 
    while (node != NULL) 
    { 
     cout<<node->data<<endl; 
     node = node->next; 
    } 
} 
/* insert a node at the beginging of the linked list */ 
void push(node** head_ref, string new_data) 
{ 
    node *new_node = new node; 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 
/* Main */ 
int main() 
{ 
    int num; 
    string file_name; 
    string file; 
    ifstream infile; 
    node* res = NULL; 
    node* a = NULL; 
    cout << "What file would you like to open: "; 
    getline(cin, file_name); 
    infile.open(file_name); 
    while(infile >> num && (getline(infile, file))) 
    { 
     push(&a, file); 
    } 
    MergeSort(&a); 
    cout<<"\n Sorted Linked List is: \n"; 
    printList(a); 
    system("Pause"); 
    return 0; 
} 

Answer 1

ファイル以上50.000行を含み、MergeSort()、SortedMerge()とFrontBackSplit()関数の再帰呼び出しに基づいて主にソートアルゴリズムの使用によるものである場合、スタックオーバーフローエラーが発生します。

注：struct nodeは何typedef ... nodeを持っていないので、 node *代わりにstruct node *の使用は推奨されません。

1. あなたの再帰的なソートアルゴリズムと呼ばれる別の強力なソートアルゴリズムを使用し
2. 、（より複雑かつ長い）非再帰的なものに変換します：2つの方法がありますあなたの問題を解決するために

クイックソート（リンクされたリストが1つでも簡単に書ける）。

ここでは、MergeSort(&a);の呼び出しをQuickSort(&a);に置き換える2番目の方法があります。考え方は、struct node *という一時的な配列を作成して、リンクされたリストの各ノードを単純な項目として管理することです。

私は QuickSort()その機能を数秒でランダムな文字列の5.000.000を行っています。

ステップ1 - リンクされたリストの項目数を数える関数を追加します。

NodeCount()関数を使用して、テーブルのサイズを にソートするように定義されています。

size_t NodeCount(struct node* pnode) 
{ 
    size_t iNodeNum = 0; 
    struct node* ntmp; 

    ntmp = pnode; 
    while (ntmp!=NULL) { 
     iNodeNum++; 
     ntmp = ntmp->next; 
    } 
    return (iNodeNum); 
} 

ステップ2 - テーブルを作成し、各項目を初期化します。

new[..]の操作後、テーブルは リンクリストを調べることで初期化されます。

void QuickSort(struct node** headRef) 
{ 
    struct node **table; 
    int iNumNode,i; 
    struct node *tmp; 

    iNumNode = NodeCount(*headRef); // sizeof table 
    table = new struct node*[iNumNode]; 
    tmp = *headRef;i=0; // start for the first node 
    while(tmp!=NULL) { 
     table[i++]=tmp; // store each node pointer 
     tmp = tmp->next; 
    } 

ステップ3 - std::string.compare()の使用署名比較 （-1、0、1）を戻すことができqsort()

に使用される比較関数を作成します。 NULLの比較は決して行われません。

int NodeCompare(const void * a, const void * b) 
{ 
    struct node *node_a = *((node **)a); 
    struct node *node_b = *((node **)b); 

    if (node_b==NULL) return (-1); // force 'node_a' 
    if (node_a==NULL) return (+1); // force 'node_b' 
    // use the std::string.compare() function 
    return (node_a->data.compare(node_b->data)); 
} 

ステップ4 - QuickSort()機能でソートされたリンクリストを復元し、その後std::qsort()を呼び出します。

リンクされたリストの復元は、（関数*headRef = table[0];に送られた最初のノードを置換する 最初除く） 前のtable[i-1]->next = table[i];で各アイテムを連結することにより行うことが容易です。 table[i]->next = NULL;本当に最後 項目のために必要とされる...

qsort(table, iNumNode, sizeof(struct node *), NodeCompare); 
for(i=1;i<iNumNode;i++) { 
    table[i-1]->next = table[i]; 
    table[i]->next = NULL; 
} 
*headRef = table[0]; 

ステップ5 - ソートされたリンクリストが復元されたときに、テーブルを削除します。

delete[] table; 
} 

ここでは、5.000.000のシミュレートされた行の出力例を示します。 qsort前

：

5000000 DTWGOIEWQP(5000000)-Your first problem is excess whitespace. 
4999999 OPGSMWHYTQ(4999999)-This works fine for smaller text files but it gene 
4999998 XAJMZKBJVS(4999998)-Then I sort the linked list using merge sort. 
4999997 QFHKGMIUAH(4999997)-I have code that reads through them and inserts ea 
4999996 QGVCCSUFNY(4999996)-I have several text files. 
... 
5 XWWVJHQXVU(000005)-Your first problem is excess whitespace. 
4 UFQTLXQIIE(000004)-This works fine for smaller text files but it gener 
3 LBNJRSBGQJ(000003)-Then I sort the linked list using merge sort. 
2 RLMTAEIZSE(000002)-I have code that reads through them and inserts eac 
1 JGSFXDTYAR(000001)-I have several text files. 

のqsort後：

3035815 AAAAAOLVMQ(3035815)-Your first problem is excess whitespace. 
1339979 AAAABLKIKQ(1339979)-This works fine for smaller text files but it gene 
1461662 AAAACBKFOJ(1461662)-I have code that reads through them and inserts ea 
1752055 AAAAGFJUMV(1752055)-Your first problem is excess whitespace. 
4455773 AAAAGXHHYJ(4455773)-Then I sort the linked list using merge sort. 
... 
4403969 ZZZZVVOZOZ(4403969)-This works fine for smaller text files but it gene 
3165910 ZZZZVYWVPM(3165910)-Your first problem is excess whitespace. 
527416 ZZZZWOUBVK(527416)-I have several text files. 
3652947 ZZZZYKRHLJ(3652947)-I have code that reads through them and inserts ea 
4283129 ZZZZZIECPD(4283129)-This works fine for smaller text files but it gene