You have been provided with a linked list of several nodes, each containing two

Question

You have been provided with a linked list of several nodes, each containing two types of data: a name of type string, and a grade of type double.

First, display the list to the user as is (this is already finished for you).

Then, using any method of your choice (push onto stacks, put into vectors or arrays and sort via bubble, binary, etc.) EXCEPT explicitly reordering the linked list itself (i.e. change the order in which the nodes point; that would be too easy!), reorder and display the linked list (display both name and grade) to the user in:

1.Alphabetical order, by name

2.Descending order (highest to lowest), by grade

here is the code you need to work on

#include <iostream>

#include <string>

using namespace std;

class nodeType

{

public:

string name;

double grade;

nodeType *link;

nodeType() // Default constructor. Utilized below to skip printing anything for head node.

{

name = "";

grade = 0;

}

};

int main()

{

// (Declared linked list nodes)

nodeType *head, *name1, *name2, *name3, *name4, *current;

head = new nodeType;

name1 = new nodeType;

name2 = new nodeType;

name3 = new nodeType;

name4 = new nodeType;

// Node initializations

head->link = name1; // 'head' (first, or initial pointer in the linked list) points to the location of name1

// Notice that we did not initialize name or grade for it like the others in the list below,

// hence, (by default) it will get the default constructor data

name1->name = "John";

name1->grade = 98;

name1->link = name2;

name2->name = "Sarah";

name2->grade = 99;

name2->link = name3;

name3->name = "Amir";

name3->grade = 96;

name3->link = name4;

name4->name = "Ingrid";

name4->grade = 100;

name4->link = nullptr; // Final node in linked list is assigned the null pointer

current = head; // Temporary pointer that traverses the linked list

// (Sequentially, as connected above)

while (current != nullptr) // Traverse the linked list and print the name stored at each node.

{

if (current->name != "" && current->grade != 0) // Checks if node has does not have default data (only the head node does); This will avoid printing anything for the head node

{

cout << current->name << endl;

cout << current->grade << endl << endl;

}

current = current->link; // Redirect 'current' pointer to next address in linked list

}

}

Explanation / Answer

Given below is the completed code for the question.
Please do rate the answer if it was helpful. Thank you

#include <iostream>

#include <string>

using namespace std;
class nodeType
{

public:

string name;
double grade;
nodeType *link;

nodeType() // Default constructor. Utilized below to skip printing anything for head node.
{
name = "";
grade = 0;
}

};

int main()
{

// (Declared linked list nodes)

nodeType *head, *name1, *name2, *name3, *name4, *current;

head = new nodeType;
name1 = new nodeType;
name2 = new nodeType;
name3 = new nodeType;
name4 = new nodeType;

// Node initializations

head->link = name1; // 'head' (first, or initial pointer in the linked list) points to the location of name1
// Notice that we did not initialize name or grade for it like the others in the list below,
// hence, (by default) it will get the default constructor data

name1->name = "John";
name1->grade = 98;
name1->link = name2;
name2->name = "Sarah";
name2->grade = 99;
name2->link = name3;
name3->name = "Amir";
name3->grade = 96;
name3->link = name4;
name4->name = "Ingrid";
name4->grade = 100;
name4->link = nullptr; // Final node in linked list is assigned the null pointer

current = head; // Temporary pointer that traverses the linked list
// (Sequentially, as connected above)
while (current != nullptr) // Traverse the linked list and print the name stored at each node.
{
if (current->name != "" && current->grade != 0) // Checks if node has does not have default data (only the head node does); This will avoid printing anything for the head node
{
cout << current->name << endl;
cout << current->grade << endl << endl;
}
current = current->link; // Redirect 'current' pointer to next address in linked list
}

//=============================

//sort the list in Alphabetical order, by name, using selection sort technique
for(nodeType* i = head->link; i != nullptr; i = i -> link){
nodeType* min = i;
for(nodeType* j = i->link; j != nullptr; j = j -> link){
if(j->name < min->name)
min = j;
}

if(i != min){
//swap node contents, leaving the links as it is
string temp_name = i->name;
double temp_grade = i->grade;

i->name = min->name;
i->grade = min->grade;

min->name = temp_name;
min->grade = temp_grade;
}
}

//display the sorted list
cout << "Sorted in Alphabetical order, by name" << endl;
current = head; // Temporary pointer that traverses the linked list
// (Sequentially, as connected above)
while (current != nullptr) // Traverse the linked list and print the name stored at each node.
{
if (current->name != "" && current->grade != 0) // Checks if node has does not have default data (only the head node does); This will avoid printing anything for the head node
{
cout << current->name << endl;
cout << current->grade << endl << endl;
}
current = current->link; // Redirect 'current' pointer to next address in linked list
}

//=============================

//sort the list in Descending order (highest to lowest), by grade using selection sort technique
for(nodeType* i = head->link; i != nullptr; i = i -> link){
nodeType* max = i;
for(nodeType* j = i->link; j != nullptr; j = j -> link){
if(j->grade > max->grade)
max = j;
}

if(i != max){
//swap node contents, leaving the links as it is
string temp_name = i->name;
double temp_grade = i->grade;

i->name = max->name;
i->grade = max->grade;

max->name = temp_name;
max->grade = temp_grade;
}
}

//display the sorted list
cout << "Sorted in Descending order (highest to lowest), by grade" << endl;
current = head; // Temporary pointer that traverses the linked list
// (Sequentially, as connected above)
while (current != nullptr) // Traverse the linked list and print the name stored at each node.
{
if (current->name != "" && current->grade != 0) // Checks if node has does not have default data (only the head node does); This will avoid printing anything for the head node
{
cout << current->name << endl;
cout << current->grade << endl << endl;
}
current = current->link; // Redirect 'current' pointer to next address in linked list
}

}

------------
output
---------
John
98

Sarah
99

Amir
96

Ingrid
100

Sorted in Alphabetical order, by name
Amir
96

Ingrid
100

John
98

Sarah
99

Sorted in Descending order (highest to lowest), by grade
Ingrid
100

Sarah
99

John
98

Amir
96

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.