C++

Forum

 
Sorting a List With Nodes

recursionexcursion (3)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#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):

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
137
138
139
140
 
#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

Last edited on
recursionexcursion (3)
Additionally, Node.h and Node.cpp are here. Had to post separately due to space constraints:

Node.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
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:
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
 
//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 (6817)
1
2
3
4
5
 
* Main
 * Test function - DO NOT CHANGE
 ***********************************/
void main()
{


BS

while (!infile.eof())
{

More BS

Try using a debugger.
Last edited on
nuderobmonkey (640)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
....
// 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:
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
 
....
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;
}
...
Last edited on
seeplus (6589)
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 (10692)
1
2
3
4
 
bool node::operator > (const node& n)
{
  return n < *this;
}
but even that's too much
https://www.cplusplus.com/reference/utility/rel_ops/
Topic archived. No new replies allowed.