Question

Assignment:

Chapter 18 introduces you to linked lists. In this homework assignment you will use the algorithms presented in this chapter to implement a list of names that should be kept in alphabetical order.

Section 18.2 defines the Linked List Operations based on a list of numbers. You will change this code to work with a list of names.

struct ListNode

{

string firstNname;

string lastName;

struct ListNode *next;

};

Rename class NumberList to something more appropriate like StringList or NamesList. You will also need to change the methods to work with strings instead of numbers. You will only need two of the list operations: insertNode (should keep the list sorted by last name), and displayList (should display first followed by last name, one per line). Change them to work with the new type. Keep the constructor and destructor. Note that the destructor needs to delete one node at a time as shown in Destroying the List section.

Your main program should instantiate an object of the NamesList and ask the user to enter a list of names (first and last), which you will insert in alphabetical order by calling the insertNode method. When the user is done entering the names, call the displayList method to display the names, which should be in alphabetical order by last name.

Follow lab documentation guidelines and attach the output at the end of main.cpp.

Turn in main.cpp and list.h with the class interface and implementation.

Answer 1

The code for above program is given below, I have commented in line for the explanation, the output is attached below the code,

Code:-

#include <iostream>

using namespace std;

// struct to store datatype of ListNode
struct ListNode
{
string firstName;
string lastName;
struct ListNode* next;
};
// first pointer as null
ListNode* first=NULL;

// calss NameList where all the functions are stored
class NameList
{
public:
string firstName;// variable to store firstName
string lastName;// variable to store lastName
NameList(){} // empty constructor
// parametrized constructor
NameList(string firstName,string lastName)
{
this->firstName = firstName;
this->lastName = lastName;
}
public:
  
// function to store node
void insertNode(NameList n)
{
// create a node
ListNode* node = new ListNode();
node->lastName = n.lastName;// store first and last name in the node
node->firstName = n.firstName;
// if list is empty
if(first==NULL)
{
first = node;
node->next = NULL;
}
// if list is not empty
else{
ListNode* temp;// temparory pointers to traverse the list
ListNode* temp2;
// temp points to first node
temp = first;
  
// until we are not at the last or we don't find a greater lastName
while(temp!=NULL && temp->lastName<n.lastName)
{
temp2=temp; // store this node address
temp = temp->next;// move to next node
}
// if we reached the last node, it means there is no name greater lastName than this one
if(temp==NULL)
{
// our previous node is last node which will point to the new node
temp2->next = node;
// next of new node will be null
node->next = NULL;
}
// if we found a greater lastName at first place only
else if(temp==first)
{
// then new node will point to where temp is pointing,
// i.e. the node with greater lastName
node->next = temp;
first=node;// first will point to new node
  
}
// if we found a greater lastName
else
{
// then new node will point to where temp2 is pointing,
// i.e. the node with greater lastName
node->next =temp2->next;
// temp2 will point to new node
temp2->next = node;
  
}
}
}
// display method to display the llst
void display()
{
ListNode* temp = first;
// until we don't reach the end
while(temp!=NULL)
{
// display the current name
cout<<temp->firstName<<" "<<temp->lastName;
cout<<endl;
// then move to nex node
temp=temp->next;
}
}
// destructor
~NameList() {
cout<<"Destructor called!";
}
};

int main()
{
string lastName;
string firstName;
int N;
NameList obj;
  
cout<<"How many names do you want to enter?";
cin>>N;
cout<<"Enter the list of name: ";
for(int i=0;i<N;i++)
{
cout<<endl;
cout<<"Enter the first name of person "<<i+1<<" : ";
cin>>obj.firstName;
cout<<"Enter the last name of person "<<i+1<<" : ";
cin>>obj.lastName;
obj.insertNode(obj);// calling the insertNode method
  
}
  
cout<<"Names in alphabetical order of last name are: \n";
obj.display();// displaying the list
  
return 0;
}

Output:-

Hope it clears your doubt and you like it :)