Sorting a List With Nodes

[recursionexcursion]

Hello All,

I am working on a small program for classes in C++. For the program, we have to write a program that creates a sorted linked list from a data file. Each line of data should be stored in a class object called node that contains a First Name, Last Name, Age, and a pointer to the next node in the list.
Create a container class called list to store the nodes in a sorted linked list. As nodes are created, insert them into the list in alphabetical order. The list class should clean up memory when it is destroyed.


I am stuck on a portion where I need to use a user-defined function called insert. When given a first name, last name, and age, insert should add a node to the list in sorted order. While insert does add the user details, it doesn't sort them in order based on my current approach. When I need to then call a remove function to remove details when found, I can accomplish that but I am still left with an unsorted list. I am stuck under some constraints as well not to change the Node.h and Main.cpp files as well.

I think it may have something to do with how I am referencing objects (or that I am completely wrong). This is one of my first C++ programming courses and we covered nodes, pointers, and objects within the space of a week. My code is below. If any pointers (pun not intended) can push me in the right direction, I am all ears.



List. h:

#include "Node.h"
//class node;
class list 
{
private:
	node* head;
	int cnt;
public:
	list();
	void insert(string, string, int);
	int length();
	node* find(string, string);
	bool remove(string, string);
	void forwards(ostream& out);
	void backwards(ostream& out);
	int findall(string, string, node_ptr* arr, int sz);
};

List.cpp (problem):

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#include "List.h"
list::list()
{
    head = NULL;
    cnt = 0;
}
void list::insert(string first, string last, int age)
{
    node_ptr newNode = new node();
    newNode->first = first;
    newNode->last = last;
    newNode->age = age;
    newNode->next = NULL;
    if (head == NULL || *head > *newNode)
    {
        newNode->next = head;
        head = newNode;
        cnt++;
        return;
    }

    //Locate the node before insertion
    else
    {
        struct node* current = head;
        while (current->next != NULL && current->next < newNode)
        {
            current = current->next;
        }
            newNode->next = current->next;
            current->next = newNode;
            cnt++;
    }
}
int list::length()
{
    return cnt;
}
node* list::find(string first, string last)
{
    node_ptr curr = head;
    while (curr != NULL)
    {
        if (curr->first == first && curr->last == last)
        {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}
bool list::remove(string first, string last)
{
    // set temp to head and prev to null
    node* temp = head;
    node* prev = NULL;

    // loop over the list until node with given first and last name is not found
    while (temp != NULL)
    {
        if (temp->first == first && temp->last == last)
        {
            // node found, exit the loop
            break;
        }
        prev = temp;
        temp = temp->next;
    }

    if (temp != NULL) // People found
    {
        if (prev == NULL)
        {
            // remove head node
            head = head->next;
        }
        else
        {
            // else middle or end node
            prev->next = temp->next;
        }

        cnt--; // decrement count by 1

        // delete temp
        delete temp;
        return true; // removal successful
    }

    return false; // removal failed
}
void list::forwards(ostream& out)
{
    node_ptr curr = head;
    while (curr != NULL)
    {
        curr->fore(out);
        curr = curr->next;
    }
}
void list::backwards(ostream& out)
{
    struct node* temp = NULL;
    struct node* prev = NULL;
    struct node* current = head;
    while (current != NULL)
    {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    while (prev != NULL)
    {
        while (prev != NULL)
        {
            prev->back(out);
            prev = prev->next;
        }
    }
}
int list::findall(string first, string last, node_ptr* arr, int sz)
{
    node_ptr curr = head;
    int i = 0;
    while (curr != NULL && i < sz)
    {
        if (curr->first == first && curr->last == last)
        {
            arr[i++] = curr;
        }
        curr = curr->next;
    }
    return sz;
}

Main.cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136

#include <iostream> #include <fstream> #include <string> using namespace std; #include "List.h" void extra(list&); /*********************************** * Main * Test function - DO NOT CHANGE ***********************************/ void main() { int age; list a; node* p; string fname, first, last; fstream infile; // Get file name cout << "Enter file name: "; cin >> fname; // Open file infile.open(fname, ios::in); // Loop through file while (!infile.eof()) { infile >> first >> last >> age; // Process if okay if (infile.good()) a.insert(first, last, age); }; // Close infile.close(); cout << endl << a.length() << " nodes" << endl; // Find node cout << endl; cout << "Enter First and Last name: "; cin >> first >> last; cout << endl << "Find: "; p = a.find(first, last); if (p != NULL) { cout << "Found!" << endl; p->put(cout); } else cout << "Not found" << endl; // Remove from list cout << endl << "Remove: "; if (a.remove(first, last)) { cout << "Success!" << endl; cout << a.length() << " nodes" << endl; } else cout << "Fail" << endl; // Display forwards cout << endl; cout << "Forwards List\n--------------\n"; a.forwards(cout); cout << endl; // Display backwards cout << "Backwards List\n--------------\n"; a.backwards(cout); cout << endl; // Extra credit // extra(a); } /*********************************** * Extra Credit * Test function - DO NOT CHANGE ***********************************/ /* void extra(list &a) { int i,n; node_ptr map[4]; string first,last; // Find node cout << endl; cout << "Enter First and Last name: "; cin >> first >> last; n = a.findall(first,last,map,4); // Display forwards cout << endl; cout << "Find List\n--------------\n"; for(i=0;i<n;i++) map[i]->put(cout); } */ Expected Output: Enter file name: People.txt 10 nodes Enter First and Last name: Mark Bowman Find: Found! Bowman Mark 13 Remove: Success! 9 nodes Forwards List

Bowman David 45 Bowman Frank 37 Bowman John 30 Bowman Mark 42 Bowman Richard 47 Christensen Ann 70 Cox Susan 36 Gueller Kathleen 34 Morales Carlos 68 Backwards List -------------- Morales Carlos 68 Gueller Kathleen 34 Cox Susan 36 Christensen Ann 70 Bowman Richard 47 Bowman Mark 42 Bowman John 30 Bowman Frank 37 Bowman David 45 Resulting Output: Enter file name: People.txt 10 nodes Enter First and Last name: Mark Bowman Find: Found! Bowman Mark 13 Remove: Success! 9 nodes Forwards List -------------- Bowman John 30 Bowman Frank 37 Bowman David 45 Morales Carlos 68 Christensen Ann 70 Gueller Kathleen 34 Bowman Mark 42 Bowman Richard 47 Cox Susan 36 Backwards List -------------- Cox Susan 36 Bowman Richard 47 Bowman Mark 42 Gueller Kathleen 34 Christensen Ann 70 Morales Carlos 68 Bowman David 45 Bowman Frank 37 Bowman John 30

[recursionexcursion]

Additionally, Node.h and Node.cpp are here. Had to post separately due to space constraints:

Node.h:

class list;

class node
{
    friend list;
public:
    node(string argf = "", string argl = "", int arga = 0);  // Default constructor
    ~node();                                         // Destructor 
    void put(ostream& out);                          // Put
    void fore(ostream& out);                         // Output list forwards
    void back(ostream& out);                         // Output list backwards
    void insert(node* p);                            // Recursive insert
    bool operator == (const node&);                 // Equal
    bool operator < (const node&);                  // Less than
    bool operator > (const node&);                  // Greater than
private:
    string first, last;
    int age;
    node* next;
};

typedef node* node_ptr;

Node.cpp:

//Implementation of Node class
//Implementation of Node class

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
#include <cctype>
#include "Node.h"


//Constructor

node::node(string argf, string argl, int arga)
{
    first = argf;
    last = argl;
    age = arga;
    next = NULL;
}
//Destructor
node::~node()
{
 //   delete this; <----literally kept my code from running: no dynamic memory allocated (silly)
}
// Put
void node::put(ostream& out) 
{
    out << last << " " << first << " " << age << endl;
}
// Output list forwards
void node::fore(ostream& out)
{
    out << last << " " << first << " " << age << endl;
    //put(out);
}
// Output list backwards
void node::back(ostream& out)
{
    out << last << " " << first << " " << age << endl;
    //put(out);
}
// Recursive insert
void node::insert(node* p) 
{
    //optional

}
// Equal
bool node::operator == (const node& n) 
{
    return last == n.last && first == n.first && age == n.age;
}
// Less than
bool node::operator < (const node& n) 
{
    if (last < n.last) 
    {
        return true;
    }
    else if (first < n.first) 
    {
        return true;
    }
    else if (age < n.age) 
    {
        return true;
    }
    return false;
}
// Greater than
bool node::operator > (const node& n) 
{
    if (last > n.last) 
    {
        return true;
    }
    else if (first > n.first) 
    {
        return true;
    }
    else if (age > n.age) 
    {
        return true;
    }
    return false;
}

[TheIdeasMan]

* Main
 * Test function - DO NOT CHANGE
 ***********************************/
void main()
{

BS

while (!infile.eof())
{

More BS

Try using a debugger.

[nuderobmonkey]

....
// Less than
bool node::operator < (const node& n)
{
    if (last < n.last) return true;
    if (last == n.last && first < n.first) return true;
    if (last == n.last && first == n.first && age < n.age) return true;
    return false;
}
// Greater than
bool node::operator > (const node& n)
{
    if (last > n.last) return true;
    if (last == n.last && first > n.first) return true;
    if (last == n.last && first == n.first && age > n.age) return true;
    return false;
}
...

Producing a sorted list:

....
list::~list()
{
   while (head != nullptr)
   {
       node_ptr tmp = head;
       head = head->next;
       delete tmp;
   }
}
void list::insert(const string& first, const string& last, int age)
{
    node_ptr newNode = new node();
    newNode->first = first;
    newNode->last = last;
    newNode->age = age;
    newNode->next = nullptr;


    // The list is empty:
    if (head == nullptr)
    {
        head = newNode;
    }

    // The new node is the smallest element:
    else if (*newNode < *head)
    {
        newNode->next = head;  // Insert before head
        head = newNode;        // Set the new head
    }

    // Insert the new node somewhere but not at begin:
    else
    {
        node_ptr current = head;

        // Locate the node before insertion.
        while (current->next != nullptr && *(current->next) < *newNode)
        {
            current = current->next;
        }

        // Insert the new node
        if (current->next != nullptr)
        {
            newNode->next = current->next->next;
        }
        current->next = newNode;
    }
    ++ cnt;
}
...

[seeplus]

Also don't use NULL in C++ - use nullptr. List needs a destructor - and a copy constructor/operator = (although these can be marked as deleted).

Pass string by ref - not by value. Set default values when a class variable is defined. There's no need to initialise string to "".

There's also design issues. fore, back and insert() are not usually part of node - but part of List (although the implementation for fore, back just displays node info). Why is List a friend of node?? node doesn't need to know anything about List.

and change main() to be correct! - if your professor thinks that main() is fine, then they shouldn't be teaching!

[ne555]

bool node::operator > (const node& n)
{
  return n < *this;
}

but even that's too much
https://www.cplusplus.com/reference/utility/rel_ops/