/* An example C program that alphabetically sorts its input lines. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* We use a linked list because it's the easiest way
 * to create a limitless container.
 */
struct linenode
{
    char *line;
    struct linenode *next;
};

/* A comparison function for lines */
static int compare(const void *a, const void *b)
{
    return strcmp(*(const char **)a, *(const char **)b);
}

int main(void)
{
    /* Declare the variables used by this function */
    struct linenode *tree = NULL;
    struct linenode *node, *next;
    unsigned count, i;
    char Buf[2048];
    char **lines;

    /* While stdin is not EOF, read lines.                 */
    /* Maximum line length is 2047 bytes + nul-terminator. */
    for(count=0; fgets(Buf, sizeof Buf, stdin) != NULL; ++count)
    {
        strtok(Buf, "\n"); /* deletes \n from the line */

        /* Allocate a new node and put the line there */
        node = (struct linenode *)malloc(sizeof(*tree));
        node->line = (char *)malloc(strlen(Buf)+1);
        strcpy(node->line, Buf);
        node->next = tree;
        tree = node;
    }

    /* Now allocate a temporary vector for sorting the lines */
    lines = (char **)malloc(count * sizeof(*lines));

    /* Put each line to the vector and dispose of them */
    i = 0;
    for(node = tree; node != NULL; node = next)
    {
        lines[i++] = node->line;
        next = node->next;
        free(node);
    }

    /* Sort the lines */
    qsort(lines, count, sizeof(lines[0]), compare);

    /* Write them out. */
    for(i = 0; i < count; ++i)
        puts(lines[i]);

    /* Dispose of the temporary vector */
    free(lines);

    /* Did you notice that this function leaks memory? Where? */

    return 0;
}