avp210159

Sort one linked list

Jan 8th, 2019
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.48 KB | None | 0 0
  1. /*
  2.   sort one linked list of strings
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8.  
  9. #define MAX_WLEN 1000
  10.  
  11. struct list {
  12.   struct list *next;
  13.   char *name;
  14. };
  15.  
  16. struct list *
  17. get_list ()
  18. {
  19.   char str[MAX_WLEN];
  20.   struct list *lst = 0, *tail = 0;
  21.  
  22.   while (scanf("%s", str) == 1) {
  23.     struct list *elem = (struct list *)malloc(sizeof(*elem));
  24.     elem->next = 0;
  25.     elem->name = strdup(str);
  26.    
  27.     if (!lst)
  28.       lst = elem;
  29.     else
  30.       tail->next = elem;
  31.     tail = elem;
  32.   }
  33.  
  34.   return lst;
  35. }
  36.  
  37. void
  38. print_list (struct list *lst)
  39. {
  40.   while (lst) {
  41.     puts(lst->name);
  42.     lst = lst->next;
  43.   }
  44. }
  45.  
  46. struct list *
  47. sort_list (struct list *lst)
  48. {
  49.   struct list *slst = 0, *tail;
  50.  
  51.   while (lst) {
  52.     // search min
  53.     struct list *min = lst, *p = lst, *prev = 0, *cur = lst->next;
  54.     while (cur) {
  55.       if (strcmp(cur->name, min->name) < 0) {
  56.         prev = p;
  57.         min = cur;
  58.       }
  59.       p = cur;
  60.       cur = cur->next;
  61.     }
  62.  
  63.     // remove min
  64.     if (prev)
  65.       prev->next = min->next;
  66.     else
  67.       lst = lst->next;
  68.  
  69.     // add min to sorted list
  70.     min->next = 0;
  71.     if (!slst)
  72.       slst = min;
  73.     else
  74.       tail->next = min;
  75.     tail = min;
  76.   }
  77.  
  78.   return slst;
  79. }
  80.  
  81. int
  82. main (int ac, char *av[])
  83. {
  84.   struct list *list = get_list();
  85.  
  86.   puts("source:");
  87.   print_list(list);
  88.   if (list) {
  89.     list = sort_list(list);
  90.     puts("sorted:");
  91.     print_list(list);
  92.   }
  93.  
  94.   return puts("End") == EOF;
  95. }
Add Comment
Please, Sign In to add comment