Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- sort one linked list of strings
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define MAX_WLEN 1000
- struct list {
- struct list *next;
- char *name;
- };
- struct list *
- get_list ()
- {
- char str[MAX_WLEN];
- struct list *lst = 0, *tail = 0;
- while (scanf("%s", str) == 1) {
- struct list *elem = (struct list *)malloc(sizeof(*elem));
- elem->next = 0;
- elem->name = strdup(str);
- if (!lst)
- lst = elem;
- else
- tail->next = elem;
- tail = elem;
- }
- return lst;
- }
- void
- print_list (struct list *lst)
- {
- while (lst) {
- puts(lst->name);
- lst = lst->next;
- }
- }
- struct list *
- sort_list (struct list *lst)
- {
- struct list *slst = 0, *tail;
- while (lst) {
- // search min
- struct list *min = lst, *p = lst, *prev = 0, *cur = lst->next;
- while (cur) {
- if (strcmp(cur->name, min->name) < 0) {
- prev = p;
- min = cur;
- }
- p = cur;
- cur = cur->next;
- }
- // remove min
- if (prev)
- prev->next = min->next;
- else
- lst = lst->next;
- // add min to sorted list
- min->next = 0;
- if (!slst)
- slst = min;
- else
- tail->next = min;
- tail = min;
- }
- return slst;
- }
- int
- main (int ac, char *av[])
- {
- struct list *list = get_list();
- puts("source:");
- print_list(list);
- if (list) {
- list = sort_list(list);
- puts("sorted:");
- print_list(list);
- }
- return puts("End") == EOF;
- }
Add Comment
Please, Sign In to add comment