Advertisement
drankinatty

Singly Linked List of Integers (example)

Aug 23rd, 2019
731
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.70 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #ifndef NNODES
  6. #define NNODES 10
  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 *next;
  46. } node_t;
  47.  
  48. typedef struct {            /* list wrapper with head & tail pointers */
  49.     node_t *head, *tail;
  50. } list_t;
  51.  
  52. /** add node at end of list, update tail to end */
  53. node_t *add (list_t *l, 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->next = NULL;
  62.    
  63.     if (!l->head)                   /* if 1st node, node is head/tail */
  64.         l->head = l->tail = node;
  65.     else {                          /* otherwise */
  66.         l->tail->next = node;       /* add at end, update tail pointer */
  67.         l->tail = node;
  68.     }
  69.    
  70.     return node;    /* return new node */
  71. }
  72.  
  73. /** add node in-order */
  74. node_t *add_ordered (list_t *l, int v)
  75. {
  76.     node_t **ppn = &l->head;    /* pointer to pointer */
  77.     node_t *pn = l->head;       /* pointer to node */
  78.    
  79.     node_t *node = malloc (sizeof *node);   /* allocate node */
  80.     if (!node) {                            /* validate allocation */
  81.         perror ("malloc-node");
  82.         return NULL;
  83.     }
  84.    
  85.     node->data = v;            /* initialize members values */
  86.     node->next = NULL;
  87.    
  88.     if (!l->head) {             /* if 1st node, node is head/tail */
  89.         l->head = l->tail = node;
  90.         return l->tail;
  91.     }
  92.    
  93.     while (pn) {                /* iterate over list */
  94.         if (v < pn->data) {     /* if new node goes before current */
  95.             *ppn = node;        /* set current address to node */
  96.             node->next = pn;    /* set next to current */
  97.             return node;
  98.         }
  99.         ppn = &pn->next;        /* get address of next node */
  100.         pn = pn->next;          /* get next node pointer */
  101.     }
  102.    
  103.     l->tail->next = node;       /* node goes at end, update tail pointer */
  104.     l->tail = node;
  105.    
  106.     return node;
  107. }
  108.  
  109. /** print all nodes in list */
  110. void prn (list_t *l)
  111. {
  112.     if (!l->head) {
  113.         puts ("list-empty");
  114.         return;
  115.     }
  116.     for (node_t *n = l->head; n; n = n->next)
  117.         printf (" %d", n->data);
  118.     putchar ('\n');
  119. }
  120.  
  121. /** delete node with value v from list (for loop) */
  122. void del_node (list_t *l, int v)
  123. {
  124.     node_t **ppn = &l->head;    /* pointer to pointer */
  125.     node_t *pn = l->head;       /* pointer to node */
  126.    
  127.     for (; pn; ppn = &pn->next, pn = pn->next) {
  128.         if (pn->data == v) {
  129.             *ppn = pn->next;    /* set address to next */
  130.             free (pn);
  131.             break;
  132.         }
  133.     }
  134. }
  135.  
  136. /** delete all nodes in list */
  137. void del_list (list_t *l)
  138. {
  139.     node_t *n = l->head;
  140.     while (n) {
  141.         node_t *victim = n;
  142.         n = n->next;
  143.         free (victim);
  144.     }
  145. }
  146.  
  147. int main (void) {
  148.    
  149.     list_t l = { NULL, NULL };      /* initialize list pointers NULL */
  150.     int a[NNODES];                  /* array to shuffle */
  151.    
  152.     srand (time (NULL));            /* seed random number generator */
  153.    
  154.     for (int i = 0; i < NNODES; i++) {  /* fill array 1 - 10 */
  155.         // add (&l, i+1);
  156.         a[i] = i+1;
  157.     }
  158.     shuffle (a, NNODES);            /* shuffle array */
  159.    
  160.     for (int i = 0; i < NNODES; i++) {  /* add shuffled values in order */
  161. #ifdef DEBUG
  162.         printf ("adding  : %d\n", a[i]);
  163. #endif
  164.         add_ordered (&l, a[i]);
  165.     }
  166.    
  167.     add (&l, NNODES + 1);       /* add at end for tail-pointer test */
  168.    
  169.     prn (&l);                   /* print list */
  170.    
  171.     del_node (&l, NNODES + 1);  /* delete tail node */
  172.    
  173.     shuffle (a, NNODES);        /* shuffle array again */
  174.    
  175.     for (int i = 0; i < NNODES; i++) {  /* remove nodes in random order */
  176. #ifdef DEBUG
  177.         printf ("deleting: %d\n", a[i]);
  178. #endif
  179.         del_node (&l, a[i]);
  180.     }
  181.     prn (&l);           /* print list ("list-empty") */
  182.        
  183.     del_list (&l);      /* delete list (does nothing list-empty) */
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement