Advertisement
drankinatty

doubly linked-list ins in-order, reverse, delete

Apr 12th, 2021
1,260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.47 KB | None | 0 0
  1. /*
  2.  *  for: https://stackoverflow.com/a/66997713/3422102
  3.  *
  4.  *  example inut file:
  5. John 12345
  6. Sam 54321
  7. Daivd 1000
  8. Mike 5391
  9. Lion 43222
  10. Phil 8332
  11. Bill 2853
  12.  *
  13.  *  then:
  14.  *
  15.  *    add (&list, "Zylon", "12");
  16.  *  
  17.  *  defines:
  18.  *    DEBUG - output:  "previous current next" pointers for each node
  19.  *
  20.  */
  21.  
  22. #include <stdio.h>
  23. #include <string.h>
  24. #include <stdlib.h>
  25.  
  26. #define NAMENUM 20
  27.  
  28. typedef struct person {
  29.   char  *firstName,
  30.         *age;
  31.   struct person *previous,
  32.                 *next;
  33. } Person;
  34.  
  35. void print (Person* list)
  36. {
  37.   while (list) {
  38.     printf ("%s %s\n",list->firstName,list->age);
  39.     list = list->next;
  40.   }
  41. }
  42.  
  43. void prnptrs (Person *list)
  44. {
  45.     while (list) {
  46.         printf ("%p  %p  %p\n", (void*)list->previous, (void*)list, (void*)list->next);
  47.         list = list->next;
  48.     }
  49. }
  50.  
  51. void reverseList (Person **list) {
  52.  
  53.   Person *current = *list;
  54.   Person *last = current;
  55.  
  56.   if (!current || !current->next)
  57.     return;
  58.  
  59.   do {
  60.     Person *temp = current->previous;
  61.     current->previous = current->next;
  62.     current->next = temp;
  63.     last = current;
  64.   } while ((current = current->previous));
  65.   *list = last;
  66. }
  67.  
  68. Person *createnode (const char *firstName, const char *age)
  69. {
  70.   size_t len;
  71.   Person *node = malloc (sizeof *node);   /* allocate node, use dereference ptr for size */
  72.  
  73.   if (!node) {                            /* validate EVERY allocation */
  74.     perror ("malloc-node");
  75.     return NULL;
  76.   }
  77.   node->next = node->previous = NULL;     /* initialize next and previous NULL */
  78.  
  79.   len = strlen (firstName);                         /* get length of firstName */
  80.   if (!(node->firstName = malloc (len + 1))) {      /* allocate/validate */
  81.     perror ("malloc-node->firstName");
  82.     free (node);                                    /* free node before return */
  83.     return NULL;
  84.   }
  85.   memcpy (node->firstName, firstName, len + 1);     /* copy firstName to node */
  86.  
  87.   len = strlen (age);                               /* get length of age */
  88.   if (!(node->age = malloc (len + 1))) {            /* allocate/validate */
  89.     perror ("malloc-node->age");
  90.     free (node->firstName);                         /* free node->firstName, and */
  91.     free (node);                                    /* free node before return */
  92.     return NULL;
  93.   }
  94.   memcpy (node->age, age, len + 1);                 /* copy age to node */
  95.  
  96.   return node;
  97. }
  98.  
  99. /* add node to list using address of list and pointer to list
  100.  * returns pointer to new node on success, NULL otherwise.
  101.  */
  102. Person *add (Person **list, const char *firstName, const char *age)
  103. {
  104.   Person **ppn = list,                            /* address of list */
  105.           *pn = *list,                            /* pointer to list */
  106.           *node = createnode (firstName, age);    /* initialize & validate new node */
  107.  
  108.   if (!node)                /* node creation failed, return list */
  109.     return NULL;
  110.  
  111.   while (pn) {  /* loop over each node */
  112.     if (strcmp (firstName, pn->firstName) <= 0) { /* compare sorts before pn->firstName */
  113.       node->previous = (*ppn)->previous;          /* if so, insert new before pn */
  114.       node->next = pn;
  115.       pn->previous = node;
  116.       *ppn = node;          /* update node at address of current node to new node */
  117.       return node;
  118.     }
  119.     if (!pn->next) {        /* if pn is last node, insert at end */
  120.       pn->next = node;
  121.       node->previous = pn;
  122.       break;
  123.     }
  124.     ppn = &pn->next;        /* advamce address to address of next node */
  125.     pn = pn->next;          /* advance pointer to next */
  126.   }
  127.  
  128.   return pn ? node : (*list = node);  /* if not 1st node, return node, else *list=node */
  129. }
  130.  
  131. /** delete node where firstName equals name
  132.  *  returns 1 if node found/deleted, 0 otherwise
  133.  */
  134. int delete (Person **list, const char *name)
  135. {
  136.   if (!*list) {             /* list-empty */
  137.     puts ("List Empty");
  138.     return 0;               /* return 0 - no replacement */
  139.   }
  140.  
  141.   Person **ppn = list,      /* address of node (pointer-to-pointer-to-node) */
  142.           *pn  = *list;     /* pointer to node */
  143.  
  144.   for (; pn; ppn = &pn->next, pn = pn->next) {    /* loop over all nodes */
  145.     if (strcmp (pn->firstName, name) == 0) {      /* if node with name found */
  146.       *ppn = pn->next;                    /* replace node at current address with next */
  147.       if (pn->next)                       /* if not last node (*ppn now NULL) */
  148.         (*ppn)->previous = pn->previous;  /* update node at address w/exiting previous */
  149.      
  150.       free (pn->firstName); /* free all memory for existing node */
  151.       free (pn->age);
  152.       free (pn);
  153.      
  154.       return 1;             /* return 1 - replacement made */
  155.     }
  156.   }
  157.  
  158.   fprintf (stderr, "warning: name not found '%s'.\n", name);
  159.  
  160.   return 0;
  161. }
  162.  
  163. /** delete all nodes in list */
  164. void del_list (Person *list)
  165. {
  166.   while (list) {
  167.     Person *victim = list;
  168.     list = list->next;
  169.     free (victim->firstName);
  170.     free (victim->age);
  171.     free (victim);
  172.   }
  173. }
  174.  
  175. int main (int argc, char **argv) {
  176.  
  177.   char name[NAMENUM], num[NAMENUM];
  178.   Person *list = NULL;
  179.   /* use filename provided as 1st argument (stdin by default) */
  180.   FILE *in = argc > 1 ? fopen(argv[1], "r") : stdin;
  181.  
  182.   if (!in) {    /* validate file open for reading */
  183.     perror ("fopen-in");
  184.     return 1;
  185.   }
  186.  
  187.   while (fscanf (in, "%s %s",name, num) == 2)
  188.     add (&list, name, num);
  189.  
  190.   fclose (in);
  191.  
  192.   add (&list, "Zylon", "12");
  193.  
  194.   printf ("Original List\n***\n");
  195.   print (list);
  196. #ifdef DEBUG
  197.   puts ("\nPointers\n***");
  198.   prnptrs (list);
  199. #endif
  200.  
  201.   printf ("\nReversed List\n***\n");
  202.   reverseList(&list);
  203.   print (list);
  204.  
  205.   puts ("\nRemoving Bill, Phil, Sam, bananas from reversed list\n***");
  206.   delete (&list, "Bill");
  207.   delete (&list, "Phil");
  208.   delete (&list, "Sam");
  209.   delete (&list, "bananas");
  210.   print (list);
  211.  
  212.   del_list (list);  /* free all allocated memory */
  213.  
  214.   return 0;
  215. }
  216.  
  217. /*
  218.  
  219. Example Input File:
  220.  
  221. $ cat dat/ypzgttvk.txt
  222. John 12345
  223. Sam 54321
  224. Daivd 1000
  225. Mike 5391
  226. Lion 43222
  227. Phil 8332
  228. Bill 2853
  229.  
  230. Example Use/Output
  231.  
  232. $ ./bin/ll_reverse_ptp dat/ypzgttvk.txt
  233. Original List
  234. ***
  235. Bill 2853
  236. Daivd 1000
  237. John 12345
  238. Lion 43222
  239. Mike 5391
  240. Phil 8332
  241. Sam 54321
  242. Zylon 12
  243.  
  244. Reversed List
  245. ***
  246. Zylon 12
  247. Sam 54321
  248. Phil 8332
  249. Mike 5391
  250. Lion 43222
  251. John 12345
  252. Daivd 1000
  253. Bill 2853
  254.  
  255. Removing Bill, Phil, Sam, bananas from reversed list
  256. ***
  257. warning: name not found 'bananas'.
  258. Zylon 12
  259. Mike 5391
  260. Lion 43222
  261. John 12345
  262. Daivd 1000
  263.  
  264. */
  265.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement