0

If someone could help point me in the right direction, it would be much appreciated. My problem is merge sorting a list from a text file and outputting the sort into a different text file that the user chooses. The text file that's inputted is about a 20 item list of random integers that I created myself. The program builds and compiles, yet it doesn't merge sort at all. The mergeSort function is located in LinkedList.cpp. The way I used the .txt file to create nodes was implemented in LinkedList::createList. Is my implementation of the merge sort function itself wrong?

Here is the full code:

Node.H

#ifndef NODE_H
#define NODE_H
#include <string>
#include <iostream>

using namespace std;

class Node
{
    friend ostream& operator<<(ostream& o, Node n);
    friend ostream& operator<<(ostream& o, Node* nPtr);
    public:
        Node();
        Node(string data, Node* next) {myData = data; myNext = next;}

        void setData(string d){myData=d;}
        string getData(){return myData;}

        void setNext(Node *n){myNext=n;}
        Node* getNext(){return myNext;}
    protected:
    private:
        string myData;
        Node* myNext;
};

#endif // NODE_H

Node.cpp

#include "node.h"

Node::Node()
{
    //ctor
}

// print the data for a single node
ostream& operator<<(ostream& o, Node n)
{
    return o;
}

// print the data for a list (as pointed to by nPtr)
ostream& operator<<(ostream& o, Node* nPtr)
{
    if (nPtr)   /// if the list isn't empty
    {
        o << nPtr->getData() << " ";
        o << nPtr->getNext();
    }
    return o;
}

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include <cstdlib>
#include <fstream>
#include "node.h"

using namespace std;

class LinkedList
{
    friend ostream& operator<<(ostream&, LinkedList);
public:
    LinkedList()
    {
        myHead = myTail = 0;
    };
    virtual ~LinkedList();
    void pushBack(string s);
    void pushFront(string s);
    string popFront();
    bool isEmpty();
    void printRecursive();
    void mergeSort();
    void createList();
    string getFront() {return myHead->getData();} // needs error checking!!!!
    string getBack() {return myTail->getData();} // needs error checking!!!!
protected:
private:
    void split(LinkedList &l1, LinkedList &l2);
    void merge(LinkedList &l1, LinkedList &l2);

    Node *myHead;
    Node *myTail;
};

#endif // LINKEDLIST_H

LinkedList.cpp

#include "linkedlist.h"

LinkedList::~LinkedList()
{
    //dtor
}

ostream& operator<<(ostream& o, LinkedList ll)
{
    Node *ptr = ll.myHead;
    o << "[ ";
    while (ptr)
    {
        o << "(" << ptr->getData() << ") ";
        ptr = ptr->getNext();
    }
    o << "]";
    return o;
}

void LinkedList::pushBack(string data)
{
    if (isEmpty())
    {
        myHead = myTail = new Node(data, 0);
    }
    else
    {
        Node *ptr = new Node(data, 0);
        myTail->setNext(ptr);
        myTail = ptr;
    }
}

void LinkedList::pushFront(string data)
{
    if (isEmpty())
    {
        myHead = myTail = new Node(data, 0);
    }
    else
    {
        myHead = new Node(data, myHead);
    }
}

bool LinkedList::isEmpty()
{
    return (!myHead);
}

string LinkedList::popFront()
{
    if (isEmpty())
    {
        cerr << "ERROR ... POPPING FROM AN EMPTY LIST!" << endl;
        exit(1);
    }
    string temp = myHead->getData();
    myHead = myHead->getNext();
    return temp;
}

void LinkedList::printRecursive()
{
    cout << "[" << myHead << "]" << endl;
}

void LinkedList::mergeSort()
{
    if (myHead != myTail) // more than one element
    {
        LinkedList l1,l2;
        split(l1,l2);
        l1.mergeSort();
        l2.mergeSort();
        merge(l1,l2);
    }
}

// deal the current list into two new lists
void LinkedList::split(LinkedList &l1, LinkedList &l2)
{
    while (!isEmpty())
    {
        l1.pushBack(popFront());
        if (!isEmpty())
        {
            l2.pushBack(popFront());
        }
    }
}

// take the lowest element from one of the two lists
// and add it to the back of the current list
void LinkedList::merge(LinkedList &l1, LinkedList &l2)
{
    while (!l1.isEmpty() && !l2.isEmpty())
    {
        if (l1.getFront() < l2.getFront())
        {
            pushBack(l1.popFront());
        }
        else
        {
            pushBack(l2.popFront());
        }
    }
    // one list is empty at this point
    while (!l1.isEmpty())
    {
        pushBack(l1.popFront());
    }

    while (!l2.isEmpty())
    {
        pushBack(l2.popFront());
    }
}

void LinkedList::createList()
{
    ifstream fin;
    ofstream fout;
    string inputBuffer, inputFile, outputFile;

    cout << "Please enter the name of the file you wish"
         << " to merge sort: ";
    cin >> inputFile;
    cout << "Please enter the name of the file you wish"
         << " to output data into: ";
    cin >> outputFile;
    fin.open(inputFile.c_str());
    fout.open(outputFile.c_str());
    if (!fin)
    {
        cout << "File cannot be found" << endl;
        exit(1);
    }
    fin.ignore(1000, '\n');
    do{
        getline(fin, inputBuffer);
        fout << inputBuffer << endl;
    }while (!fin.eof());

    for (Node *temp = myHead; temp; temp = temp->getNext())
    {
        string tempString;
        tempString = temp->getData();
        fout << tempString << endl;
    }

    fout.close();
    fin.close();
}
2
Contributors
1
Reply
6
Views
4 Years
Discussion Span
Last Post by Ancient Dragon
0

CreateList just copies the input file to the output file, it does not retain any of the data or create a linked list. The loop starting on line 146 will do nothing because myHead is NULL.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.