main.cpp

00001 /* mbed Microcontroller Library
00002  * Copyright (c) 2018 ARM Limited
00003  * SPDX-License-Identifier: Apache-2.0
00004  */
00005 
00006 #include "mbed.h"
00007 #include "ThisThread.h"
00008 #include "stats_report.h"
00009 
00010 
00011 #include <stdio.h>
00012 #include <stdlib.h>
00013 
00014 DigitalOut led1(LED1);
00015 
00016 #define SLEEP_TIME                  500 // (msec)
00017 #define PRINT_AFTER_N_LOOPS         20
00018 
00019 
00020  
00021 struct node
00022 {
00023     struct node *prev;
00024     int n;
00025     struct node *next;
00026 }*h,*temp,*temp1,*temp2,*temp4;
00027  
00028 void insert1();
00029 void insert2();
00030 void insert3();
00031 void traversebeg();
00032 void traverseend(int);
00033 void sort();
00034 void search();
00035 void update();
00036 void d_delete();
00037  
00038 int counter = 0;
00039  
00040 int main()
00041 {
00042     int ch;
00043  
00044     h = NULL;
00045     temp = temp1 = NULL;
00046  
00047     printf("\n 1 - Insert at beginning");
00048     printf("\n 2 - Insert at end");
00049     printf("\n 3 - Insert at position i");
00050     printf("\n 4 - Delete at i");
00051     printf("\n 5 - Display from beginning");
00052     printf("\n 6 - Display from end");
00053     printf("\n 7 - Search for element");
00054     printf("\n 8 - Sort the list");
00055     printf("\n 9 - Update an element");
00056     printf("\n 10 - Exit");
00057  
00058     while (1)
00059     {
00060         printf("\n Enter choice : ");
00061         scanf("%d", &ch);
00062         switch (ch)
00063         {
00064         case 1:
00065             insert1();
00066             break;
00067         case 2:
00068             insert2();
00069             break;
00070         case 3:
00071             insert3();
00072             break;
00073         case 4:
00074             d_delete();
00075             break;
00076         case 5:
00077             traversebeg();
00078             break;
00079         case 6:
00080             temp2 = h;
00081             if (temp2 == NULL)
00082                 printf("\n Error : List empty to display ");
00083             else
00084             {
00085                 printf("\n Reverse order of linked list is : ");
00086                 traverseend(temp2->n);
00087             }
00088             break;
00089         case 7:
00090             search();
00091             break;
00092         case 8:
00093             sort();
00094             break;
00095         case 9:
00096             update();
00097             break;
00098         case 10:
00099             exit(0);
00100         default:
00101             printf("\n Wrong choice menu");
00102         }
00103     }
00104 }
00105  
00106 /* TO create an empty node */
00107 void create()
00108 {
00109     int data;
00110  
00111     temp =(struct node *)malloc(1*sizeof(struct node));
00112     temp->prev = NULL;
00113     temp->next = NULL;
00114     printf("\n Enter value to node : ");
00115     scanf("%d", &data);
00116     temp->n = data;
00117     counter++;
00118 }
00119  
00120 /*  TO insert at beginning */
00121 void insert1()
00122 {
00123     if (h == NULL)
00124     {
00125         create();
00126         h = temp;
00127         temp1 = h;
00128     }
00129     else
00130     {
00131         create();
00132         temp->next = h;
00133         h->prev = temp;
00134         h = temp;
00135     }
00136 }
00137  
00138 /* To insert at end */
00139 void insert2()
00140 {
00141     if (h == NULL)
00142     {
00143         create();
00144         h = temp;
00145         temp1 = h;
00146     }
00147     else
00148     {
00149         create();
00150         temp1->next = temp;
00151         temp->prev = temp1;
00152         temp1 = temp;
00153     }
00154 }
00155  
00156 /* To insert at any position */
00157 void insert3()
00158 {
00159     int pos, i = 2;
00160  
00161     printf("\n Enter position to be inserted : ");
00162     scanf("%d", &pos);
00163     temp2 = h;
00164  
00165     if ((pos < 1) || (pos >= counter + 1))
00166     {
00167         printf("\n Position out of range to insert");
00168         return;
00169     }
00170     if ((h == NULL) && (pos != 1))
00171     {
00172         printf("\n Empty list cannot insert other than 1st position");
00173         return;
00174     }
00175     if ((h == NULL) && (pos == 1))
00176     {
00177         create();
00178         h = temp;
00179         temp1 = h;
00180         return;
00181     }
00182     else
00183     {
00184         while (i < pos)
00185         {
00186             temp2 = temp2->next;
00187             i++;
00188         }
00189         create();
00190         temp->prev = temp2;
00191         temp->next = temp2->next;
00192         temp2->next->prev = temp;
00193         temp2->next = temp;
00194     }
00195 }
00196  
00197 /* To delete an element */
00198 void d_delete()
00199 {
00200     int i = 1, pos;
00201  
00202     printf("\n Enter position to be deleted : ");
00203     scanf("%d", &pos);
00204     temp2 = h;
00205  
00206     if ((pos < 1) || (pos >= counter + 1))
00207     {
00208         printf("\n Error : Position out of range to delete");
00209         return;
00210     }
00211     if (h == NULL)
00212     {
00213         printf("\n Error : Empty list no elements to delete");
00214         return;
00215     }
00216     else
00217     {
00218         while (i < pos)
00219         {
00220             temp2 = temp2->next;
00221             i++;
00222         }
00223         if (i == 1)
00224         {
00225             if (temp2->next == NULL)
00226             {
00227                 printf("Node deleted from list");
00228                 free(temp2);
00229                 temp2 = h = NULL;
00230                 return;
00231             }
00232         }
00233         if (temp2->next == NULL)
00234         {
00235             temp2->prev->next = NULL;
00236             free(temp2);
00237             printf("Node deleted from list");
00238             return;
00239         }
00240         temp2->next->prev = temp2->prev;
00241         if (i != 1)
00242             temp2->prev->next = temp2->next;    /* Might not need this statement if i == 1 check */
00243         if (i == 1)
00244             h = temp2->next;
00245         printf("\n Node deleted");
00246         free(temp2);
00247     }
00248     counter--;
00249 }
00250  
00251 /* Traverse from beginning */
00252 void traversebeg()
00253 {
00254     temp2 = h;
00255  
00256     if (temp2 == NULL)
00257     {
00258         printf("List empty to display \n");
00259         return;
00260     }
00261     printf("\n Linked list elements from begining : ");
00262  
00263     while (temp2->next != NULL)
00264     {
00265         printf(" %d ", temp2->n);
00266         temp2 = temp2->next;
00267     }
00268     printf(" %d ", temp2->n);
00269 }
00270  
00271 /* To traverse from end recursively */
00272 void traverseend(int i)
00273 {
00274     if (temp2 != NULL)
00275     {
00276         i = temp2->n;
00277         temp2 = temp2->next;
00278         traverseend(i);
00279         printf(" %d ", i);
00280     }
00281 }
00282  
00283 /* To search for an element in the list */
00284 void search()
00285 {
00286     int data, counter = 0;
00287     temp2 = h;
00288  
00289     if (temp2 == NULL)
00290     {
00291         printf("\n Error : List empty to search for data");
00292         return;
00293     }
00294     printf("\n Enter value to search : ");
00295     scanf("%d", &data);
00296     while (temp2 != NULL)
00297     {
00298         if (temp2->n == data)
00299         {
00300             printf("\n Data found in %d position",counter + 1);
00301             return;
00302         }
00303         else
00304              temp2 = temp2->next;
00305             counter++;
00306     }
00307     printf("\n Error : %d not found in list", data);
00308 }
00309  
00310 /* To update a node value in the list */
00311 void update()
00312 {
00313     int data, data1;
00314  
00315     printf("\n Enter node data to be updated : ");
00316     scanf("%d", &data);
00317     printf("\n Enter new data : ");
00318     scanf("%d", &data1);
00319     temp2 = h;
00320     if (temp2 == NULL)
00321     {
00322         printf("\n Error : List empty no node to update");
00323         return;
00324     }
00325     while (temp2 != NULL)
00326     {
00327         if (temp2->n == data)
00328         {
00329  
00330             temp2->n = data1;
00331             traversebeg();
00332             return;
00333         }
00334         else
00335             temp2 = temp2->next;
00336     }
00337  
00338     printf("\n Error : %d not found in list to update", data);
00339 }
00340  
00341 /* To sort the linked list */
00342 void sort()
00343 {
00344     int i, j, x;
00345  
00346     temp2 = h;
00347     temp4 = h;
00348  
00349     if (temp2 == NULL)
00350     {
00351         printf("\n List empty to sort");
00352         return;
00353     }
00354  
00355     for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
00356     {
00357         for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
00358         {
00359             if (temp2->n > temp4->n)
00360             {
00361                 x = temp2->n;
00362                 temp2->n = temp4->n;
00363                 temp4->n = x;
00364             }
00365         }
00366     }
00367     traversebeg();
00368 }