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

6. What is Race condition? How to prevent it? [2 marks] 7. How many synchronization methods do you know and compare the differences. [2 marks] 8. Explain what are the “mutual exclusion”, “deadlock”, “livelock”, and “eventual entry”, with the traffic intersection as an example like dinning philosophy. [2 marks] 9. For memory allocation, what are the difference between internal fragmentation and external fragmentation. Explain with an example. [2 marks] 10. How can the virtual memory map to the physical memory. Explain with an example. [2 marks]

Your answers normally have 50 words. Less than 50 words will not get marks. 1. What is context switch between multiple processes? [2 marks] 2. Draw the memory layout for a C program. [2 marks] 3. How many states does a process has? [2 marks] 4. Compare the non-preemptitve scheduling and preemptive scheduling. [2 marks] 5. Given 4 process and their arrival times and next CPU burst times, what are the average times and average Turnaround time, for different scheduling algorithms including: a. First Come, First-Served (FCFS) Scheduling [2 marks] b. Shortest-Job-First (SJF) Scheduling [2 marks] c. Shortest-remaining-time-first [2 marks] d. Priority Scheduling [2 marks] e. Round Robin (RR) [2 marks] Process Arrival Time Burst Time P1 0 8 P2 1 9 P3 3 2 P4 5 4

a database with multiple tables from attributes as shown above that are in 3NF, showing PK, non-key attributes, and FK for each table? Assume the tables are already in 1NF. [Hint: 3 tables will result after deducing 1NF -> 2NF -> 3NF]

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