Program Plan: Defines a class IndexedList which has following data members and member functions. node *head = NULL; map<char, node&*gt;list_index; member functions node* getNewNode (string); void searchIndexedList (string); void insertInIndexedList (string); void deleteFromIndexedList (string); void createIndex (); void displayList (); A map is defined to keep a map of starting alphabet of names and their node address. Define main to use the above function of a linked list. Program Description: The main objective of this program is to improve search and deletion for a node from the linked list. In this implementation, we will keep starting point of search from the node which is available in the previously created map. With this approach, the search will improve to great extent. Program: #include<iostream> #include<map> usingnamespace std; /* structure of a single linked list node*/ typedefstructlist_node{ string studentName; structlist_node*next;// pointer to next node in the list }node; classIndexedList{ node *head =NULL; map<char, node&*gt;list_index; public: node*getNewNode(string); voidsearchIndexedList(string); voidinsertInIndexedList(string); voiddeleteFromIndexedList(string); voidcreateIndex(); voiddisplayList(); IndexedList() { head =NULL; } }; /* create new node */ node*IndexedList::getNewNode(string name){ node *new_node=new node; new_node->studentName= name; new_node->next =NULL; returnnew_node; } /* displays the list elements */ voidIndexedList::displayList(){ cout<<"Displaying List : "; node *new_node=new node; new_node=this->head; while(new_node!=NULL){ cout<<new_node->studentName<<" -> "; new_node=new_node->next; } cout<<"NULL "<<endl; } /* Search the node with the element as data Return the pointer to the node if found else return NULL */ voidIndexedList::searchIndexedList(string name){ node *new_node=new node; if(this->list_index.find(name.at(0))!=this->list_index.end()){ new_node=this->list_index.at(name.at(0)); if(new_node!=NULL) { while(new_node!=NULL){ if(new_node->studentName== name) { cout<<"Name found in list"; break; } else { new_node=new_node->next; } } }else{ cout<<"List is empty"; } } else{ cout<<"Name NOT found in list"; } if(new_node==NULL){ cout<<"Name NOT found in list"; } } voidIndexedList::createIndex(){ cout<<"Creating Index : "; node *new_node=new node; new_node=this->head; while(new_node!=NULL){ cout<<new_node->studentName<<" -> "; cout<<new_node->studentName.at(0)<<endl; if(this->list_index.find(new_node->studentName.at(0))==this->list_index.end()){ this->list_index.insert(pair<char,node&*gt;(new_node->studentName.at(0),new_node)); } new_node=new_node->next; } cout<<"Print Index"<<endl; for(auto it =this->list_index.cbegin(); it !=this->list_index.cend();++it) { cout<< it->first <<" "<< it->second <<"\n"; } } voidIndexedList::deleteFromIndexedList(string name){ node *new_node=new node; node *temp_node=new node; if(this->list_index.find(name.at(0))!=this->list_index.end()){ new_node=this->list_index.at(name.at(0)); temp_node=new_node; if(new_node!=NULL) { while(new_node!=NULL){ if(new_node->studentName== name) { cout<<"Name found in list"; temp_node->next =new_node->next; deletenew_node; break; } else { temp_node=new_node; new_node=new_node->next; } } }else{ cout<<"List is empty"; } }else{ cout<<"Name NOT found in list"; } } /* insert a node at the end of the list */ voidIndexedList::insertInIndexedList(string name){ node *ptr=getNewNode(name); if(this->head ==NULL){//if list is empty this->head =ptr; } else{ node *temp =this->head; while(temp->next !=NULL){// move to the last node temp = temp->next; } temp->next =ptr;// insert node at the end } } intmain(){ string name; IndexedList list; int choice =0; while(1) { cout<<"-----------------"<<endl; cout<<"Operations on Linked List"<<endl; cout<<"-----------------"<<endl; cout<<"1.Insert Element to Indexed List "<<endl; cout<<"2.Remove Element from Indexed List "<<endl; cout<<"3.Search List"<<endl; cout<<"4.Display List"<<endl; cout<<"5.Display Index"<<endl; cout<<"6.Quit"<<endl; cout<<"Enter your choice : "; cin>>choice; switch(choice) { case1: cout<<" Enter Name to insert to Linked List >> "; cin>> name; list.insertInIndexedList(name);// 9 -> 4 -> 12 -> 3 -> 11 -> 6 break; case2: cout<<" Enter Name to be removed from Linked List >> "; cin>> name; list.deleteFromIndexedList(name);// 9 -> 4 -> 12 -> 3 -> 11 -> 6 break; case3: cout<<" Enter Name to search in Linked List >> "; cin>> name; list.searchIndexedList(name); break; case4: list.displayList(); break; case5: list.createIndex(); break; case6: return1; default: cout<<"Wrong choice"<<endl; } } return0; } Sample Output: ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>california ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>pittsburgh ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>newyork ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>seattle ----------------- Operations on Linked List ----------------- 1.Insert Element to Indexed List 2.Remove Element from Indexed List 3.Search List 4.Display List 5.Display Index 6.Quit Enter your choice : 1 Enter Name to insert to Linked List >>microsoft ----------------- Operations on Linked List ----------------- 1.Insert Element to Indexed List 2.Remove Element from Indexed List 3.Search List 4.Display List 5.Display Index 6.Quit Enter your choice : 1 Enter Name to insert to Linked List >>samsung ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 4 Displaying List: california ->pittsburgh ->newyork ->seattle ->microsoft ->samsung -> NULL ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 3 Enter Name to search in Linked List >>newyork Name NOT found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 5 Creating Index: california -> c pittsburgh -> p newyork -> n seattle -> s microsoft -> m samsung -> s Print Index c 0x9f4440 m 0x9f4500 n 0x9f44a0 p 0x9f4470 s 0x9f44d0 ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 3 Enter Name to search in Linked List >>newyork Name found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 2 Enter Name to be removed from Linked List >>newyork Name found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 4 Displaying List: california ->pittsburgh -> ->seattle ->microsoft ->samsung -> NULL ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice:

C++ How to Program (Early Objects Version)

10th Edition

ISBN: 9780134448824

Author: Paul Deitel; Harvey M. Deitel

Publisher: Pearson Education (US)

See similar textbooks

Videos

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 19, Problem 19.27E

Chapter 20, Problem 20.5E

Students have asked these similar questions

Dijkstra's Algorithm (part 1). Consider the network shown below, and Dijkstra’s link-state algorithm. Here, we are interested in computing the least cost path from node E (note: the start node here is E) to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 0" row in the table below showing the link state algorithm’s execution by matching the table entries (i), (ii), (iii), and (iv) with their values. Write down your final [correct] answer, as you‘ll need it for the next question.

4. |z + 5 - 5i| = 7

14. dz, C: |z❘ C: |z❘ = 0.6 ze² - 2iz H

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Solution Summary: The author explains the purpose of the program, which is to improve search and deletion for a node from the linked list.

Videos

Want to see the full answer?

Chapter 19 Solutions