Starting from:

$35

Assignment 3 Linked Lists Communication Between Towers Solution




​OBJECTIVES




Create, traverse, add nodes to a linked list



Get practice implementing classes









Background




In the Lord of the Rings trilogy, there is a scene where a warning beacon is lit in the towers of Minas Tirith, which is seen by a second beacon, prompting them to light their own fire which a third beacon sees, and so forth. This was a rapid means of communication in the days before telegraphs were invented. In this assignment, you’re going to simulate a communications network using a linked list. Each node in the list will represent a country and you need to be able to send a message between nodes from one side of the world to the other.




Building your own communications network




You will be implementing a class to simulate a linear communication network between countries. There are three files in Moodle containing a code skeleton to get you started. ​Do not modify the header file or your code won’t work in Moodle!​You will have to complete both the class implementation in ​CountryNetwork.cpp​and the driver file ​main.cpp​.




The linked-list itself will be implemented using the following struct (already included in the header file):




struct​ ​Country


{
​// name of the country
​string​ ​name​;
​string message;​
​ // message this country has received
​int​ ​numberMessages​; ​// no. of messages passed through this country
​Country *next;​
​ // pointer to the next country
};






CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













Class Specifications




The ​CountryNetwork​class definition is provided in the file ​CountryNetwork.hpp​in Moodle. ​Do not modify this file or your code won’t work on Moodle! ​Fill in the file ​CountryNetwork.cpp according to the following specifications.




Country* head;




Points to the first node in the linked list



CountryNetwork();




Class constructor; set the head pointer to NULL



void insertCountry(Country* ​previous​, string ​countryName​); ​// Beware of edge cases

Insert a new country with name ​countryName​in the linked list after the country pointed to by ​previous​. If ​previous​is NULL, then add the new country to the beginning of the list. Print the name of the country you added according to the following format:






// If you are adding at the beginning use this:

cout << ​"adding: "​ << countryName << ​" (HEAD)"​ << endl;




// Otherwise use this:

cout << ​"adding: "​ << countryName << ​" (prev: "​ << previous-name << ")"​ << endl;




void loadDefaultSetup();




Add the following six countries, in order, to the network with ​insertCountry​: "United States", "Canada", "Brazil", "India", "China", "Austraila"



Country* searchNetwork(string ​countryName​);

Return a pointer to the node with name ​countryName​. If ​countryName ​cannot be found, return NULL



void transmitMsg(string​receiver​, string ​msg​);

Traverse the linked list from the head to the node with name ​receiver​. For each node in this path (including the head), set the node’s ​message​to ​msg​and increment the node’s numberMessages​field. If the list is empty, print "Empty list" and exit the function. If the node is not present, print “Country not found”.



As you traverse the list, at each node report the message received and the number of messages received using the following cout: (See the end of this document for example output)
CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley










cout << node-name << ​" [# messages received: "​ <<

node-numberMessages << "]​ received: "​ << node-message << endl;




void printPath();




Print the names of each node in the linked list. Below is an example of correct output using the default setup. (Note that you will ​cout << “NULL” ​at the end of the path)



CURRENT PATH ==






United States - Canada - Brazil - India - China - Australia - NULL ===




If the network is empty then print ​"nothing in path"









Main driver file




Your program will start by displaying a menu by calling the ​displayMenu​function included in main.cpp. The user will select an option from the menu to decide what the program will do, after which, the menu will be displayed again. The specifics of each menu option are described below.




Option 1: Build Network




This option calls the ​loadDefaultSetup​function, then calls the ​printPath ​function. You should get the following output:







adding: United States (HEAD)




adding: Canada (prev: United States)




adding: Brazil (prev: Canada)




adding: India (prev: Brazil)




adding: China (prev: India)




adding: Australia (prev: China)




== CURRENT PATH ==




United States - Canada - Brazil - India - China - Australia - NULL ===




Option 2: Print Network Path




Calls the ​printPath​function. Output should be in the format below:

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













Output for the default setup == CURRENT PATH ==



United States - Canada - Brazil - India - China - Australia - NULL




===




Output when the linked list is empty



== CURRENT PATH ==




nothing in path




===




Option 3: Transmit Message




Prompt the user for two inputs: a message to send, and the name of a country to receive the message ​(Hint: use ​getline​in case there are spaces in the user input)​. Pass the message and country name to the ​transmitMsg​function. Don’t forget to add a newline after the message is collected, and before the output is printed. This is done for better readability.




For example, the following should be the output if the linked-list contains the default setup from option (1) and the message “bom dia” is sent to “Brazil”:







Example 1:




Enter name of the country to receive the message:




Brazil




Enter the message to send:




bom dia




United States [# messages received: 1] received: bom dia




Canada [# messages received: 1] received: bom dia




Brazil [# messages received: 1] received: bom dia







If the user then decides to transmit the message “ni hao” to “China”, the output will be:







Example 2:




Enter name of the country to receive the message:




China




Enter the message to send:




ni hao




United States [# messages received: 2] received: ni hao




Canada [# messages received: 2] received: ni hao

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













Brazil [# messages received: 2] received: ni hao




India [# messages received: 1] received: ni hao




China [# messages received: 1] received: ni hao







If the user then decides to transmit the message “Sushi” to “Japan”, the output when the country is not present will be:







Example 3:




Enter name of the country to receive the message:




Japan




Enter the message to send:




Sushi




Country not found



















Option 4: Add Country




Prompt the user for two inputs: the name of a new country to add to the network, ​newCountry​, and the name of a country already in the network, ​previous​, which will precede the new country. Use the member functions ​searchNetwork​and ​insertCountry​to insert ​newCountry into the linked-list right after ​previous​.




If the user wants to add the new country to the head of the network then they should enter “First” instead of a previous country name.



If the user enters an invalid previous city (not present in the linked list), then you need to prompt the user with the following error message and collect input again until they enter a valid previous country name or “First”:






cout << ​"INVALID(previous country name)...Please enter a VALID previous country name!"​ << endl;




Once a valid previous country name is passed and the new country is added, call the function ​printPath​to demonstrate the new linked-list.



First letter of the country to be added should be ​Uppercase ​(sentence case) e.g. If you want to add “mexico, it should be stored as “​Mexico​” in linked-list.
CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley










For example, the following should be the output if the linked-list contains the default setup from option (1) and the user wants to add Colombia after Brazil:







Enter a new country name:




Colombia




Enter the previous country name (or First):




Brazil




adding: Colombia (prev: Brazil)




== CURRENT PATH ==




United States - Canada - Brazil - Colombia - India - China - Australia -




NULL




===






















Option 5: Quit




Print the following message:







cout << ​"Quitting..."​ << endl;




Finally, print the following before exiting the program:







cout << ​"Goodbye!"​ << endl;










Example run










Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit
CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













+-----------------------+




# 2




== CURRENT PATH ==




nothing in path




===




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 3




Enter name of the country to receive the message:




Japan




Enter the message to send:




Cherry Blossom




Empty list




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 1




adding: prev: [HEAD]




adding: United States (HEAD)




adding: Canada (prev: United States)




adding: Brazil (prev: Canada)




adding: India (prev: Brazil)




adding: China (prev: India)




adding: Australia (prev: China)




== CURRENT PATH ==




United States - Canada - Brazil - India - China - Australia - NULL ===




Select a numerical option:

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 2




== CURRENT PATH ==




United States - Canada - Brazil - India - China - Australia - NULL ===




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 3




Enter name of the country to receive the message:




Japan




Enter the message to send:




Sushi




Country not found




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 4




Enter a new country name:




Japan




Enter the previous country name (or First):




United States




adding: Japan (prev: United States)

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













== CURRENT PATH ==




United States - Japan - Canada - Brazil - India - China - Australia




- NULL




===




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 3




Enter name of the country to receive the message:




Australia




Enter the message to send:




Kangaroo




United States [# messages received: 1] received: Kangaroo




Japan [# messages received: 1] received: Kangaroo




Canada [# messages received: 1] received: Kangaroo




Brazil [# messages received: 1] received: Kangaroo




India [# messages received: 1] received: Kangaroo




China [# messages received: 1] received: Kangaroo




Australia [# messages received: 1] received: Kangaroo




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 3




Enter name of the country to receive the message:




Brazil




Enter the message to send:




Football




United States [# messages received: 2] received: Football

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













Japan [# messages received: 2] received: Football




Canada [# messages received: 2] received: Football Brazil [# messages received: 2] received: Football Select a numerical option: +=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 4




Enter a new country name:




Singapore




Enter the previous country name (or First):




First




adding: Singapore (HEAD)




== CURRENT PATH ==




Singapore - United States - Japan - Canada - Brazil - India - China




- Australia - NULL




===




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 4




Enter a new country name:




Australia




Enter the previous country name (or First):




Spain




INVALID(previous country name)...Please enter a VALID previous country




name!




Canada




adding: Australia (prev: Canada)




== CURRENT PATH ==




Singapore - United States - Japan - Canada - Australia - Brazil -

CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley













India - China - Australia - NULL




===




Select a numerical option:




+=====Main Menu=========+




Build Network



Print Network Path



Transmit Message



Add Country



Quit



+-----------------------+




# 5




Quitting... cleaning up path:




== CURRENT PATH ==




Singapore - United States - Japan - Canada - Australia - Brazil -




India - China - Australia - NULL




===




Goodbye!
















Appendix:




CountryNetwork::insertCountry()



cout << "adding: " << countryName << " (HEAD)" << endl;



cout << "adding: " << countryName << " (prev: " << previous-name << ")" << endl;



CountryNetwork::transmitMsg()



cout << "Empty list" << endl;



cout << "Country not found" << endl;



cout << sender-name << “ [# messages received: " <<



sender-numberMessages << "] received: " << sender-message << endl;




CountryNetwork::printPath()



cout << "== CURRENT PATH ==" << endl;



cout << "nothing in path" << endl;



cout << ptr-name << " - ";



cout << ptr-name << " - ";



cout << "NULL" << endl;
CSCI 2270 – Data Structures




Instructors: Maciej Zagrodzki, Christopher Godley







cout << "===" << endl;



main()



cout << "Enter name of the country to receive the message: "<< endl;



cout << "Enter the message to send: " << endl;



cout << endl;



cout << "Enter a new country name: " << endl;



cout << "Enter the previous country name (or First): " << endl;



cout << "INVALID(previous country name)...Please enter a VALID previous country name!" << endl;



cout << "Quitting..." << endl;



cout << "Invalid Input" << endl;



cout << "Goodbye!" << endl;









displayMenu()



cout << endl;



cout << "Select a numerical option:" << endl;



cout << "+=====Main Menu=========+" << endl;



cout << " 1. Build Network " << endl;



cout << " 2. Print Network Path " << endl;



cout << " 3. Transmit Message " << endl;



cout << " 4. Add Country " << endl;



cout << " 5. Quit " << endl;



cout << "+-----------------------+" << endl;



cout << "# ";

More products