Write a program for insertion sort in linked list in C
struct lnode {
char *str;
struct lnode *next;
};
struct lnode *insert(char *data, struct lnode *list);
void free_list(struct lnode *list);
void print_list(struct lnode *list);
int main(void) {
char line[1024];
struct lnode *list;
list = NULL;
while((fgets(line, 1024, stdin)) != NULL)
list = insert(line, list);
print_list(list);
free_list(list);
return 0;
}
struct lnode *insert(char *data, struct lnode *list) {
struct lnode *p;
struct lnode *q;
/* create a new node */
p = (struct lnode *)malloc(sizeof(struct lnode));
/* save data into new node */
p->str = strdup(data);
/* first, we handle the case where `data' should be the first element */
if(list == NULL || strcmp(list->str, data) > 0) {
/* apperently this !IS! the first element */
/* now data should [be|becomes] the first element */
p->next = list;
return p;
} else {
/* search the linked list for the right location */
q = list;
while(q->next != NULL && strcmp(q->next->str, data) < 0) {
q = q->next;
}
p->next = q->next;
q->next = p;
return list;
}
}
void free_list(struct lnode *list) {
struct lnode *p;
while(list != NULL) {
p = list->next;
free(list);
list = p;
}
}
void print_list(struct lnode *list) {
struct lnode *p;
for(p = list; p != NULL; p = p->next)
printf("%s", p->str);
}
Post a Comment