Created
May 10, 2017 11:27
-
-
Save clausecker/77e42dadea6f2c05d532d1871e340a51 to your computer and use it in GitHub Desktop.
Bubblesort on singly linked lists
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* bubble sort a linked list */ | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| static struct list *scan_list(void); | |
| static void sort_list(struct list **); | |
| static void print_list(struct list *); | |
| static void free_list(struct list *); | |
| struct list { | |
| struct list *next; | |
| int elem; | |
| }; | |
| int main() | |
| { | |
| struct list *l = scan_list(); | |
| sort_list(&l); | |
| print_list(l); | |
| free_list(l); | |
| } | |
| static struct list * | |
| scan_list(void) | |
| { | |
| struct list *l = NULL, **cell = &l; | |
| int val; | |
| while (scanf("%d", &val) == 1) { | |
| *cell = malloc(sizeof **cell); | |
| if (*cell == NULL) { | |
| perror("malloc"); | |
| exit(EXIT_FAILURE); | |
| } | |
| (*cell)->next = NULL; | |
| (*cell)->elem = val; | |
| cell = &(*cell)->next; | |
| } | |
| return (l); | |
| } | |
| static void | |
| print_list(struct list *l) | |
| { | |
| while (l != NULL) { | |
| printf("%d\n", l->elem); | |
| l = l->next; | |
| } | |
| } | |
| static void | |
| free_list(struct list *l) | |
| { | |
| struct list *ll; | |
| while (l != NULL) { | |
| ll = l->next; | |
| free(l); | |
| l = ll; | |
| } | |
| } | |
| /* sort list using bubble sort */ | |
| static void | |
| sort_list(struct list **l) | |
| { | |
| int swap; | |
| struct list **i, *a, *b; | |
| do { | |
| swap = 0; | |
| for (i = l; *i != NULL && (*i)->next != NULL; i = &(*i)->next) | |
| if ((*i)->elem > (*i)->next->elem) { | |
| swap = 1; | |
| a = *i; | |
| b = (*i)->next; | |
| a->next = b->next; | |
| b->next = a; | |
| *i = b; | |
| } | |
| } while (swap); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment