SHARE
TWEET

Untitled

a guest Dec 3rd, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ////////////////////////////////////////////////////////////////////////////////
  2. // Faculty of Computing, Universiti Teknologi Malaysia
  3. // SCSJ2013- Data Structures and Algorithms
  4. // Semester 1, 2018/2019
  5. // Assignment 1  - Program 1 Linked List
  6. ////////////////////////////////////////////////////////////////////////////////
  7.  
  8. #include<iostream>
  9. using namespace std;
  10.  
  11. class Node{
  12.     private:
  13.         char id;
  14.     public:
  15.         Node *next;
  16.        
  17.         Node(char anId=0)
  18.         { id = anId;
  19.           next =NULL;
  20.         }
  21.        
  22.         char getId() const
  23.         { return id; }
  24. };
  25.  
  26.  
  27. // To print the list of nodes from first to last
  28. void print(Node *first,  Node *last)
  29. {
  30.     Node *node = first;
  31.     while (node){
  32.         cout << node->getId() << "\t";
  33.         node=node->next;
  34.     }
  35.     cout << endl;
  36. }
  37.  
  38.  
  39. int main()
  40. {
  41.     Node *first, *last;
  42.    
  43.     first = last = new Node('A');
  44.    
  45.     for (char ch='B'; ch <='G'; ch++){
  46.         last->next = new Node(ch);
  47.         last = last->next;
  48.     }
  49.  
  50.     print(first, last);
  51.     cin.get();
  52.    
  53.     Node *node;
  54.    
  55.     // Task 1 : Insert a new node (with the id of 'X') in front of the list
  56.     node = new Node('X');
  57.     node->next = first;
  58.     first = node;
  59.    
  60.  
  61.  
  62.     print(first, last);
  63.     cin.get();
  64.     //-------------------------------------------------
  65.    
  66.    
  67.     // Task 2 Insert a new node (with the id of 'Y') between node 'C' and node 'D'
  68.  
  69.     //  X--->A--->B--->C--->D--->E--->F--->G--->NULL
  70.     Node* current = first;
  71.     while (current->next != NULL)     // keep looping through all the linked list; 2nd condition is for making sure you don't go beyond list boundries
  72.     {
  73.         if(current->getId() == 'C')
  74.         {
  75.             Node* newnode = new Node('Y');   // creat a new node X
  76.             newnode->next = current->next;   // X-->next = C--->next which is D, we connect to preserve the connection, then we break in the next statment
  77.             current->next = newnode;         // we now break C--->next from being D to be the newnode we created which is X
  78.            
  79.            
  80.             /* supposingly here we add break because it's uncesseary to loop anymore. */
  81.             break;
  82.         }
  83.        
  84.         current = current->next;    // update statment like i++
  85.     }
  86.  
  87.  
  88.  
  89.     print(first, last);
  90.     cin.get();
  91.     //-------------------------------------------------
  92.  
  93.  
  94.     // Task 3 Insert a new node (with the id of 'Z') at the end of the list
  95.     current = first;                  // re-intiating current to start at the beggining of the linked list. no need for new pointer.
  96.     while (current->next != NULL)     // 2nd condition is for making sure you don't go beyond list boundries
  97.     {
  98.         current = current->next;      // after we arrive at the end of the linked list, loop will autmatically break;
  99.     }                                 // current will be now pointing to the last element in the linked list.
  100.    
  101.     current->next = new Node('Z');    // last element Next ----> our new inserted 'Z';
  102.     last = current->next;             // updating the value of last
  103.    
  104.  
  105.     print(first, last);
  106.     cin.get();
  107.     //-------------------------------------------------
  108.  
  109.    
  110.     // Task 4   (Swap first and last elements)
  111.    
  112.     current = first;
  113.     while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
  114.     {
  115.         current = current->next;
  116.     }
  117.     // current is now the element before the last.
  118.        
  119.     last->next = first->next;      // last is now connected to the 2nd elemnt in the list    
  120.     current->next = first;        // element before the last is connected to the new last which is the beggining of the array. 
  121.     first = last;                 // updating first and last;
  122.     last = current->next;         // since current is the element before the last.
  123.     last->next = NULL;            // not to forget to make the last pointing to null, otherwise it will be closed(infinite)loop for print
  124.  
  125.  
  126.     print(first, last);
  127.     cin.get();
  128.     //-------------------------------------------------
  129.  
  130.    
  131.     // Task 5 : Swap the positions of the node ‘D’ and ‘E’
  132.     // i assume the I already know D and E are going be adjacent !!
  133.    
  134.    
  135.    
  136.     current = first;
  137.     while(current->next->getId() != 'D' && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
  138.     {
  139.         current = current->next;
  140.     }
  141.     // current is now the one before d
  142.     Node* temp = current->next->next;      // tmp = the one after D which is E
  143.     current->next->next = temp->next;           // D-->next = E-->next;
  144.     temp->next = current->next;            // E next is D    
  145.     current->next = temp;                   // D next is E
  146.    
  147.     print(first, last);
  148.     cin.get();
  149.     //-------------------------------------------------
  150.    
  151.    
  152.     // Task 6 : Delete the last node from the list
  153.  
  154.  
  155.     current=first;
  156.     while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
  157.     {
  158.         current = current->next;
  159.     }
  160.     // current now is poiting on the element befor the last
  161.     delete current->next;
  162.     current->next = NULL;
  163.  
  164.  
  165.  
  166.     print(first, last);
  167.     cin.get();
  168.     //-------------------------------------------------
  169.  
  170.     // Z       A       B       C       Y       E       D       F       G
  171.     // Task 7 : Delete the node ‘C’ from the list
  172.     current = first;
  173.     Node* temp1;
  174.     while(current->next->getId() != 'C' && current->next != NULL) // 2nd condition is for making sure you don't go beyond list boundries
  175.     {
  176.         current = current->next;
  177.     }
  178.     // current is now the element just before C
  179.    
  180.     temp1 = current->next;
  181.     current->next = current->next->next;  // the one before C point to the thing that C orginally points to
  182.     delete temp1;
  183.    
  184.     print(first, last);
  185.     cin.get();
  186.     //-------------------------------------------------
  187.    
  188.    
  189.     // Task 8 : Delete the first node from the list
  190.  
  191.    
  192.     current = first->next;        // make the current to be the 2nd element.
  193.     first->next = NULL;          // breaking connection between first node and 2nd node
  194.     delete first->next;          // deleting the pointer
  195.     first = current;            // putting first at the beggining of the new linked list.
  196.  
  197.  
  198.  
  199.     print(first, last);
  200.     cin.get();
  201.     //-------------------------------------------------
  202.    
  203.    
  204.    
  205.    
  206.     // Find any number from the list (based on input entered by the user)
  207.  
  208.     cout <<"What character position you would like to find?  enter the once character only: ";
  209.     char c;           // character input
  210.     cin>>c;              
  211.     current = first;
  212.     int currentElementIndex = 1;
  213.     while(current->getId() != c && current->next != NULL)  // looping untill you find the character & making sure you don't go beyond list boundries
  214.     {
  215.         current = current->next;
  216.         currentElementIndex++;
  217.     }
  218.    
  219.     cout <<"Your Element is the element number \"" << currentElementIndex <<"\" in the list. \n \n";
  220.  
  221.  
  222.  
  223.     print(first, last);
  224.     cin.get();
  225.     //-------------------------------------------------
  226. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top