Advertisement
drankinatty

Singly Linked List of Strings With Sorted Insertion

Aug 6th, 2019
401
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.66 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAXC 1024   /* if you need a constant, #define one (or more) */
  6.  
  7. typedef struct node_t {     /* list node */
  8.     char *s;
  9.     struct node_t *next;
  10. } node_t;
  11.  
  12. /** helper function to allocate node, and storage for string.
  13.  *  copies string to node and initializes node->next pointer NULL.
  14.  *  returns pointer to allocated node on success, NULL otherwise.
  15.  */
  16. node_t *create_node (const char *s)
  17. {
  18.     size_t len = strlen (s);                        /* get string length */
  19.     node_t *node = malloc (sizeof *node);           /* allocate node */
  20.    
  21.     if (!node) {    /* validate EVERY allocation */
  22.         perror ("create_node: malloc node");
  23.         return NULL;
  24.     }
  25.    
  26.     if (!(node->s = malloc (len + 1))) {            /* allocate for string */
  27.         perror ("create_node: malloc node->s");
  28.         free (node);        /* on failure, free node before returning NULL */
  29.         return NULL;
  30.     }
  31.    
  32.     memcpy (node->s, s, len+1); /* copy string to node */
  33.     node->next = NULL;          /* initialze next NULL */
  34.    
  35.     return node;    /* return allocated & initialized node */
  36. }
  37.  
  38. /** add node in sort order to list.
  39.  *  returns pointer to new node on success, NULL otherwise.
  40.  */
  41. node_t *add_node (node_t **head, const char *s)
  42. {
  43.     node_t *node = create_node (s);             /* allocate/initialze node */
  44.    
  45.     if (!node)                                  /* validate */
  46.         return NULL;
  47.    
  48.     node_t **ppn = head,                        /* ptr2ptr to node - current */
  49.             *pn = *head;                        /* pointer to iterate - next */
  50.    
  51.     /* iterate over each node checking sort order */
  52.     while (pn && strcmp (node->s, pn->s) > 0) {
  53.         ppn = &pn->next;                        /* ppn to address of next */
  54.         pn = pn->next;                          /* advance pointer to next */
  55.     }
  56.    
  57.     node->next = pn;                            /* set node->next to next */
  58.     *ppn = node;                                /* set current to node */
  59.    
  60.     return node;                                /* return node */
  61. }
  62.  
  63. /** print all nodes in list */
  64. void prn_list (node_t *head)
  65. {
  66.     if (!head) {    /* check if list is empty */
  67.         puts ("list-empty");
  68.         return;
  69.     }
  70.    
  71.     for (node_t *pn = head; pn; pn = pn->next)  /* iterate over each node */
  72.         puts (pn->s);                           /* printing string */
  73. }
  74.  
  75. /** delete all nodes in list */
  76. void del_list (node_t *head)
  77. {
  78.     node_t *pn = head;              /* pointer to iterate */
  79.    
  80.     while (pn) {                    /* iterate over each node */
  81.         node_t *victim = pn;        /* set victim to current */
  82.         pn = pn->next;              /* advance pointer to next */
  83.         free (victim->s);           /* free current string */
  84.         free (victim);              /* free current node */
  85.     }
  86. }
  87.  
  88. int main (int argc, char **argv) {
  89.    
  90.     char buf[MAXC];         /* read buffer */
  91.     node_t *list = NULL;    /* pointer to list (must initialize NULL */
  92.     /* use filename provided as 1st argument (stdin by default) */
  93.     FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;
  94.  
  95.     if (!fp) {  /* validate file open for reading */
  96.         perror ("file open failed");
  97.         return 1;
  98.     }
  99.    
  100.     while (fgets (buf, MAXC, fp)) {
  101.         buf[strcspn(buf, "\r\n")] = 0;
  102.         add_node (&list, buf);
  103.     }
  104.    
  105.     if (fp != stdin)    /* close file if not stdin */
  106.         fclose (fp);
  107.    
  108.     prn_list (list);    /* pring contents of list */
  109.     del_list (list);    /* free all list memory */
  110.    
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement