Advertisement
drankinatty

Doubly-Linked List of Integers - Remove Rand Nodes Check

Feb 29th, 2020
394
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 5.85 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #ifndef NNODES
  6. #define NNODES 16
  7. #endif
  8.  
  9. /*
  10.  * non-list misc functions
  11.  */
  12.  
  13. /** rand_int for use with shuffle */
  14. static int rand_int (int n)
  15. {
  16.     int limit = RAND_MAX - RAND_MAX % n, rnd;
  17.  
  18.     rnd = rand();
  19.     for (; rnd >= limit; )
  20.         rnd = rand();
  21.  
  22.     return rnd % n;
  23. }
  24.  
  25. /** shuffle integer array of size 'n'
  26.  *  (using fisher-yates method)
  27.  */
  28. void shuffle (int *a, int n)
  29. {
  30.     int i, tmp;
  31.     while (n-- > 1) {
  32.         i = rand_int (n + 1);
  33.         tmp  = a[i];
  34.         a[i] = a[n];
  35.         a[n] = tmp;
  36.     }
  37. }
  38.  
  39. /*
  40.  * list structs and functions
  41.  */
  42.  
  43. typedef struct node_t {     /* list node */
  44.     int data;
  45.     struct node_t *prev, *next;
  46. } node_t;
  47.  
  48. typedef struct {            /* list wrapper with head & tail pointers */
  49.     node_t *head, *tail;
  50. } list_t;
  51.  
  52. /** create new node initialize all members */
  53. node_t *createnode (int v)
  54. {
  55.     node_t *node = malloc (sizeof *node);   /* allocate node */
  56.     if (!node) {                            /* validate allocation */
  57.         perror ("malloc-node");
  58.         return NULL;
  59.     }
  60.     node->data = v;                         /* initialize members values */
  61.     node->prev = node->next = NULL;
  62.    
  63.     return node;    /* return new node */
  64. }
  65.  
  66. /** add node at end of list, update tail to end */
  67. node_t *add (list_t *l, int v)
  68. {
  69.     node_t *node = createnode (v);      /* allocate node */
  70.     if (!node)                          /* validate allocation */
  71.         return NULL;
  72.    
  73.     if (!l->head)                       /* if 1st node, node is head/tail */
  74.         l->head = l->tail = node;
  75.     else {                              /* otherwise */
  76.         node->prev = l->tail;           /* set prev to tail */
  77.         l->tail->next = node;           /* add at end, update tail pointer */
  78.         l->tail = node;
  79.     }
  80.    
  81.     return node;    /* return new node */
  82. }
  83.  
  84. /** add node in-order */
  85. node_t *add_ordered (list_t *l, int v)
  86. {
  87.     node_t **ppn = &l->head;            /* pointer to pointer */
  88.     node_t *pn = l->head;               /* pointer to node */
  89.    
  90.     node_t *node = createnode (v);      /* allocate node */
  91.     if (!node)                          /* validate allocation */
  92.         return NULL;
  93.    
  94.     if (!l->head) {                 /* if 1st node, node is head/tail */
  95.         l->head = l->tail = node;
  96.         return l->tail;
  97.     }
  98.    
  99.     while (pn) {                        /* iterate over list */
  100.         if (v < pn->data) {             /* if new node goes before current */
  101.             node->prev = (*ppn)->prev;  /* set node prev to current prev */
  102.             *ppn = node;                /* set current address to node */
  103.             pn->prev = node;            /* set next->prev to current */
  104.             node->next = pn;            /* set current->next to next */
  105.             return node;
  106.         }
  107.         ppn = &pn->next;            /* get address of next node */
  108.         pn = pn->next;              /* get next node pointer */
  109.     }
  110.    
  111.     node->prev = l->tail;
  112.     l->tail->next = node;           /* node goes at end, update tail pointer */
  113.     l->tail = node;
  114.    
  115.     return node;
  116. }
  117.  
  118. /** print all nodes in list */
  119. int prn (list_t *l)
  120. {
  121.     if (!l->head) {
  122.         puts ("list-empty");
  123.         return 0;
  124.     }
  125.     for (node_t *n = l->head; n; n = n->next)
  126.         printf (" %d", n->data);
  127.     putchar ('\n');
  128.    
  129.     return 1;
  130. }
  131.  
  132. /** print all nodes in list in reverse */
  133. int prnrev (list_t *l)
  134. {
  135.     if (!l->tail) {
  136.         puts ("list-empty");
  137.         return 0;
  138.     }
  139.     for (node_t *n = l->tail; n; n = n->prev)
  140.         printf (" %d", n->data);
  141.     putchar ('\n');
  142.    
  143.     return 1;
  144. }
  145.  
  146. /** delete node with value v from list (for loop) */
  147. int del_node (list_t *l, int v)
  148. {
  149.     if (!l->head) {
  150.         puts ("list-empty");
  151.         return 1;
  152.     }
  153.     node_t **ppn = &l->head;    /* pointer to pointer */
  154.     node_t *pn = l->head;       /* pointer to node */
  155.    
  156.     for (; pn; ppn = &pn->next, pn = pn->next) {
  157.         if (pn->data == v) {
  158.             *ppn = pn->next;            /* set node at address to next */
  159.            
  160.             if (pn != l->tail)          /* prev is next prev */
  161.                 (*ppn)->prev = pn->prev;
  162.             else                        /* deleting tail, set tail to prev */
  163.                 l->tail = pn->prev;
  164.            
  165.             free (pn);                  /* free current */
  166.             pn = NULL;
  167.            
  168.             break;
  169.         }
  170.     }
  171.    
  172.     return 0;
  173. }
  174.  
  175. /** delete all nodes in list */
  176. void del_nodes (list_t *l)
  177. {
  178.     node_t *n = l->head;
  179.    
  180.     while (n) {
  181.         node_t *victim = n;
  182.         n = n->next;
  183.         free (victim);
  184.     }
  185.    
  186.     l->head = l->tail = NULL;
  187. }
  188.  
  189. int main (void) {
  190.    
  191.     list_t l = { NULL, NULL };              /* initialize list pointers NULL */
  192.     int a[NNODES];                          /* array to shuffle */
  193.    
  194.     srand (time (NULL));                    /* seed random number generator */
  195.    
  196.     for (int i = 0; i < NNODES; i++) {      /* fill array with NNODES int */
  197.         add (&l, i+1);
  198.         a[i] = i+1;
  199.     }
  200.     shuffle (a, NNODES);                    /* shuffle array for random removal */
  201.    
  202.     prn (&l);                               /* print list forward */
  203.     prnrev (&l);                            /* print list reverse */
  204.     putchar ('\n');
  205.    
  206.     for (int i = 0; i < NNODES; i++) {      /* remove all nodes in random order */
  207.         printf ("deleting : %d\n", a[i]);
  208.         del_node (&l, a[i]);                /* delete node with random value a[i] */
  209.        
  210.         if (prn (&l)) {         /* print list forward if nodes remain */
  211.             prnrev (&l);        /* print list reverse if nodes remain */
  212.             putchar ('\n');     /* tidy up with a '\n' */
  213.         }
  214.     }
  215. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement