How do you solve QUESTION #4 in the book data structures using c++ by D.S. Malik

Question

How do you solve QUESTION #4 in the book data structures using c++ by D.S. Malik in Visiual Studios using the linked list below with the requirements being asked in the screen shot?
Linked list :

#include <iostream> #include <cstdlib> using namespace std; struct nodeType { int info; nodeType *link; };  void createList(nodeType*& first, nodeType*& last); void printList(nodeType*& first); void insertFront(nodeType*& first); void insertBack(nodeType*& last); void deleteFirst(nodeType*& first); void deleteLast(nodeType*& last, nodeType* first);  int main() {  nodeType *first, *last; int num;  createList(first, last); int choice; while(true) { cout<<"1. Insert Front. 2. Insert Last. 3. Delete Front. 4. Delete Last. 5. Print List. 6. Exit. "; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: insertFront(first); break; case 2: insertBack(last); break; case 3: deleteFirst(first); break; case 4: deleteLast(last, first); break; case 5: printList(first); break; case 6: return 0; default: cout<<"Invalid menu option. Try again."<<endl; } }    system("PAUSE"); return 0; }  void createList(nodeType*& first, nodeType*& last) { int number; nodeType *newNode;  first = NULL; last = NULL;  cout<<"Enter an integer (-999 to stop): "; cin>>number;  while (number != -999) { newNode = new nodeType; // create new node newNode->info = number; newNode->link = NULL;  if (first == NULL) { first = newNode; last = newNode; } else { last->link = newNode; last = newNode; } cout<<"Enter an integer (-999 to stop): "; cin>>number; } // end of while-loop  } // end of build list function        void deleteFirst(nodeType*& first) { nodeType *temp; temp= first; first= temp->link; delete temp; return; }  void deleteLast(nodeType*& last, nodeType* current) { nodeType *temp; while(current->link != NULL) { temp=current; current=current->link; } temp=last; current->link=NULL; delete temp; last = current; return; }  void insertFront(nodeType*& front) { int num; cout<<"  Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= front; front= newNode; return; }  void insertBack(nodeType*& last) { int num; cout<<"  Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= NULL; last->link= newNode; last = newNode; return; }  void printList(nodeType*& first) {  cout<<"Inside printList...printing linked list... "<<endl; nodeType *current; current = new nodeType; current = first;      while (current != NULL) { cout << current->info << " "; current = current->link; } cout<<endl; }

Page 349-350 #4 and #5 Use the "Linked List lab" you have been working on in class and add the two functions the questions are asking you to develop: divideMid and divideAt. Be sure to include comments Use meaningful identifier names (constants where appropriate) Do not work together; no two people should have identical work!?!? Turn in .cpp file AND Turn in a "print-screen' of your output (press "print-screen' on keyboard, then 'paste' in MS-Word)

Explanation / Answer

For divideMin , first maintain a counter variable to count the number of nodes in the list. Traverse the list using pointer and at each node increment the counter value starting at zero. So, after the complete traversal, you will get the number no nodes in the list. So for divide min function, you again traverse the list till the middle (i.e. till half the number of nodes of the total list) of the list and then create a head node and assign the address of mid+1 th noode in the new header header node. Thus, the original list gets divided at the middle to generate to separate nodes.

For divideAt function, take the position n to divide from the user. Traverse that many nodes in the original list using pointers. If that many nodes are not present, show a message that insufficient nodes to divide list, to the user. If you had more than that many nodes, then assign the address of n + 1 th node to a newly created header node. thus the list gets divided at position n. If the list contains n nodes only, then print insufficient number of nodes to create new list.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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