Clist Insertion Sort Tutorial ... and also see a recursive merge sort of a list

[David]

Update!   FREE homework help NOW available via e-mail ... (or in person if in Toronto Ontario Canada region.)

You can contact me via:
http://sites.google.com/site/securejoules/securetransportservices
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes

A fairly frequent student request goes something like this:

How do I get an insertion sort to work in a (simple single link) linked-list in my C program?

The solution to this problem is often complicated by the problems of using C strings.

The following series of example programs attempts to smooth out many of the issues students may have getting an insertion sort of C strings to work ... and then to work well.

It starts with inputting strings into a large buffer, but of a fixed length, and then copying these strings into dynamic memory C strings of the required length and inserting these into a list in ABC...abd... sorted order.

It prgresses to using readLine (readLine.h) so that you may easily input strings of any length (limited only by available memory).

It finally reaches a level where the code that deals with a list of strings and sorting (processing) a list of strings, is separated into its own header file, 'myNode.h' ... And ... also in a separate header file, myClist.h, is the code that deals with creating the list, initializing it, basic functions like push_front and push_back ... and cleaning up the list (freeing the dynamic memory) when you are done with it.


At the '0' entry level, we begin with ...

0. Using fgets and a buffer fixed at compile time to input C strings a insert into a list in sorted order.

Code: [Select]

/* ListOfStringInsertSorted_via_buffer.c */


#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* re. strlen, strcpy, strcmp ... */


#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char text[] )
{
    if( !condition )
    {
        fprintf(stderr, "%s\n", text );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif


/* make this big enough so ALL C strings DO have the 'fgets' '\n' char at end */
#define BUFFER_SIZE 1024

typedef char* CString;
typedef struct ListOfStr
{
    CString str;                /* 'str' holds the address of a new C string */
    struct  ListOfStr* next;    /* points to the next C string ... */
}ListOfStr;

typedef ListOfStr* pListOfStr;  /* to hold address of (a node in) a List ... */


/* prototypes ... */

/* INSERTS into 'list' in 'ABC...abc...' order the CString 's' */
pListOfStr insertSorted( pListOfStr head, const CString s );

/* erase/free up all memory in list */
pListOfStr erase( pListOfStr head );

/* show all the (insert sorted) 'text lines' in the 'list' */
void show( pListOfStr head );

/* utility function to return a copy of 's' in NEWly allocated memory */
CString newCopy( const CString s );


int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    char buffer[BUFFER_SIZE];
   
    /* in the following ... list is decalred as a pointer to ListOfStr */
    pListOfStr list = NULL; /* address of the list 'head' MUST be NULL to start */
   
    puts( "Enter line of text to insert sorted into list (Ctrl Z to end) ..." );
    fputs( "> ", stdout );
    while( fgets( buffer, sizeof buffer, stdin )) /*  i.e. while != NULL  */
    {
        char* pch = strchr( buffer, '\0' );
        if( pch > buffer && *(pch-1) == '\n'  ) *(pch-1) = 0; /* strip away '\n' */
        list = insertSorted( list, buffer );
        fputs( "> ", stdout );
    }
   
    show( list );
   
    list = erase( list ); /* ... and re-sets list to NULL ... */
   
    show( list );
   
    printf( "\nPress 'Enter' ... to continue ... " );
    getchar();
    return 0;
   
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */



/* pass in the address of the 'head' ...
   and the (address of) CString to insert in the list ...*/
pListOfStr insertSorted( pListOfStr head, const CString s )
{   
    /* first ... create a new node ...
      Note: cast below is not needed unless you are compiling as C++  */
    pListOfStr p = (pListOfStr) malloc( sizeof( ListOfStr ));
    myAssert( ( p != NULL ), "ERROR! malloc failed in 'insertSorted' ..." );
   
    /* save address of new memory (start of new CString) into the new node ... */
    p->str = newCopy( s );
   
    /* firstly, we handle most common case where 's' is NOT the first element */
    if( head != NULL && strcmp( s, head->str ) >= 0 ) /* need >= so equal
                                                        value comes 'after all',
                                                        and not before, below */
    {
        /* search the linked list for the right (stablesort) location to insert */
        pListOfStr cur = head;
        while( cur->next != NULL && strcmp( cur->next->str, s ) <= 0 )
        {
            cur = cur->next;
        }
        p->next = cur->next;
        cur->next = p;
        return head;       
    }

    /* apparently this IS the first node ... */
    p->next = head;     /* so set this node in first position ... */
    return p;           /* and return new 'head' address */
   
}
   
pListOfStr erase( pListOfStr head )
{
    while( head != NULL )
    {
        pListOfStr nextNode = head->next;
        free( head->str );
        free( head );
        head = nextNode;
    }
    return head; /* i.e. return NULL; */
}

void show( pListOfStr head ) /* Note: 'head' is a local copy ... */
{
    for( ; head != NULL; head = head->next ) printf( "%s ", head->str );
}

/* utility function to return a copy ... in NEWly allocated memory */
CString newCopy( const CString s )
{
    CString nCopy = (CString) malloc( strlen(s)+1 );
    myAssert( ( nCopy != NULL ), "ERROR! malloc failed in 'newCopy' ..." );
    strcpy( nCopy, s );
    return nCopy; /* REMEMBER to *free* this new string when done with it */
}

At a litle more advanced stage to make facile inputing C strings of any length, and ...

1. Avoiding the problems with fgets by using readLine (readLine.h) ...

Code: [Select]

/* ListOfStringInsertSorted_readLine.c */


#include "readLine.h" /* also includes, stdio.h, stdlib.h, string.h,
                         myAssert( .. ) and newCopy( .. ) */

typedef char* CString;
typedef struct ListOfStr
{
    CString str;                /* 'str' holds the address of a new C string */
    struct  ListOfStr* next;    /* points to the next C string ... */
}ListOfStr;

typedef ListOfStr* pListOfStr;  /* to hold address of (a node in) a List ... */


/* prototypes ... */

/* INSERTS into 'list' in 'ABC...abc...' order the CString 's' */
pListOfStr insertSorted( pListOfStr head, const CString s );
pListOfStr clear( pListOfStr head ); /* erase/free up all memory in list */
void show( pListOfStr head ); /* show all 'text lines' in the 'list' ... */


int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
   
    /* in the following ... list is decalred as a pointer to ListOfStr */
    pListOfStr list = NULL; /* address of the list 'head' MUST be NULL to start */
    CString s;
    puts( "Enter line of text to insert sorted into list ('Ctrl Z' to end) ..." );
    fputs( "> ", stdout );
    while( (s = readLine( stdin )) ) /*  i.e. while s != NULL  */
    {
        list = insertSorted( list, s );
        fputs( "> ", stdout );
    }
   
    puts( "\nYour list now is ..." );
    show( list );
   
    printf( "\nEnter an other line to insert > " ); fflush( stdout );
    s = readLine( stdin );
    list = insertSorted( list, s );
   
    puts( "\nYour list now is:" );
    show( list );   
   
    list = clear( list ); /* Note: re-sets list to NULL */
    puts( "\nAfter 'erase( list )' ... your list now is:" );
    show( list );   
 
    printf( "\nPress 'Enter' ... to continue ... " );
    getchar();
    return 0;
   
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */



/* pass in the address of the 'head' ...
   and the (address of) CString to insert in the list ...*/
pListOfStr insertSorted( pListOfStr head, const CString s )
{   
    /* first ... create a new node ...
      Note: cast below is not needed unless you are compiling as C++  */
    pListOfStr p = (pListOfStr) malloc( sizeof( ListOfStr ));
    myAssert( ( p != NULL ), "ERROR! malloc failed in 'insertSorted' ..." );
   
    /* save address of new memory of start of this CString) into the new node */
    p->str = s;
   
    /* firstly, we handle most common case where 's' is NOT the first element */
    if( head != NULL && strcmp( s, head->str ) >= 0 ) /* NEED >= 0 */
    {
        /* so search the linked list for the right location */
        pListOfStr cur = head;
        while( cur->next != NULL && strcmp( cur->next->str, s ) <= 0 )
        {
            cur = cur->next;
        }
        p->next = cur->next;
        cur->next = p;
        return head;       
    }

    /* apparently this IS the first node ... */
    p->next = head;     /* so set this node in first position ... */
    return p;           /* and return new 'head' address */
   
}
   
pListOfStr clear( pListOfStr head )
{
    while( head != NULL )
    {
        pListOfStr nextNode = head->next;
        free( head->str );
        free( head );
        head = nextNode;
    }
    return head; /* i.e. return NULL; */
}

void show( pListOfStr head ) /* Note: 'head' is a 'local copy' of the pointer */
{
    if( head )
    {
        int i;
        for( i = 0; head != NULL; head = head->next, ++i )
            printf( "line %d: %s\n", i+1, head->str ); /* note added '\n' at str end */
    }
    else puts( "'Your list is empty'" );
}

2. Progressing next in steps 2. 3. 4. to making your code more reusable when ever you may have to code for processing C strings ... or lists of C strings ... or lists (of any struct) ...

Note: by the time you reach version 4 of this code, you will have 3 header files that are ready to plug in for future coding of lists, or lists of strings, with some basic functions, all ready to go ... myNode.h, myClist.h and readLine.h

This ... ver.2 file has two struct's ... Node and List, where List holds members that track the front, back and size of the list.  Node is where you define just what kind of list you want ...And here the Node's hold one dynamic C string (and of course a pointer to the next Node in the list)

Code: [Select]

/* ListOfStringInsertSorted_readLine_ver2.c */


#include "readLine.h" /* also includes, stdio.h, stdlib.h, string.h,
                        myAssert( .. ) and newCopy( .. ) */
#define testing 1 /* set to 0 to turn extra printing off and recompile ... */                       

typedef struct myNode
{
    char*  str;           /* 'str' holds the address of a new C string */
    struct myNode* next;  /* points to the next C string ... */
} Node;


typedef struct myList     /* to hold (data for) a List ... */
{
    Node* front;
    Node* back;
    int size;
} List;


/* prototypes ... */

/* INSERTS into 'list' in 'ABC...abc...' order the CString 's' */
void init( List* );
void insertSorted( List* , Node* );
void clear( List* ); /* erase/free up all memory in list */
void show( List* );  /* show all 'text lines' in the 'list' ... */
void showFrontBackSize( List* ); /* to aid testing front, back, size*/


int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    Node n;   
    List list;
    init( &list );
   
    puts( "Enter line of text to insert sorted into list ('Ctrl Z' to end) ..." );
    fputs( "> ", stdout );
    while( (n.str = readLine( stdin )) ) /*  i.e. while s != NULL  */
    {
        insertSorted( &list, &n );
        fputs( "> ", stdout );
    }
   
    puts( "\nYour list now is ..." );
    show( &list );
   
    printf( "\nEnter an other line to insert > " ); fflush( stdout );
    n.str = readLine( stdin );
    insertSorted( &list, &n );
   
    puts( "\nYour list now is:" );
    show( &list );   
   
    clear( &list ); /* Note: re-sets list to NULL */
    puts( "\nAfter 'erase( list )' ... your list now is:" );
    show( &list );   
 
    printf( "\nPress 'Enter' ... to continue ... " );
    getchar();
    return 0;
   
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */


void init( List* list )
{
    list->front = list->back = NULL;
    list->size = 0;
}


/* pass in the address of the 'List' ...
   and the (address of) CString to insert in the list ...*/
void insertSorted( List* list, Node* n )
{   
    /* first ... create a new node ...
      Note: cast below is not needed unless you are compiling as C++  */
    Node* head = list->front,
        * p    = (Node*) malloc( sizeof( Node ));
    myAssert( ( p != NULL ), "ERROR! malloc failed in 'insertSorted' ..." );
   
    /* copy address of this C string in the recycled node passed in ... */
    p->str = n->str;  /* to the new node */
   
    /* firstly, we handle most common case where 'n' is NOT the first element */
    if( head != NULL && strcmp( n->str, head->str ) >= 0 ) /* NEED >= 0 */
    {
        /* so search the linked list for the right location */
        Node* cur = head;
        while( cur->next != NULL && strcmp( cur->next->str, n->str ) <= 0 )
        {
            cur = cur->next;
        }
        if( cur == list->back ) list->back = p;
        p->next = cur->next;
        cur->next = p;
        // list->front = head; // unchanged
        ++ list->size;
#if testing
        putchar( '\n' ); showFrontBackSize( list ); putchar( '\n' );
#endif       
        return;
    }

    /* apparently this IS the first node ... */
    p->next = head;     /* so set this node in first position ... */
    list->front = p;
    ++ list->size;
    if( list->size == 1 ) list->back = p;
#if testing   
    putchar( '\n' ); showFrontBackSize( list ); putchar( '\n' );
#endif   
}
   
void clear( List* list )
{
    Node* head = list->front;
    while( head != NULL )
    {
        Node* nextNode = head->next;
        free( head->str );
        free( head );
        head = nextNode;
    }
    list->size = 0;
    list->front = list->back = NULL ;
}

void show( List* list ) /* Note: 'head' is a 'local copy' of the pointer */
{
    if( list->size )
    {
        Node* head = list->front;
        int i;
        for( i = 0; head != NULL; head = head->next, ++i )
            printf( "list (%d): %s\n", i+1, head->str ); /* note added '\n' at str end */
        printf( "size = %d\n", list->size );
    }
    else puts( "'Your list is empty'" );
}

void showFrontBackSize( List* list )
{
    if( list->size )
        printf( "front = %s, back = %s, size = %d\n",
        list->front->str, list->back->str, list->size );
    else puts( "'Your list is empty'" );     
}

[David]

Here we have added push_front, push_back, isort, and we have also separated out into a function the task of creating a newNode ... so that now we may code Node* n = newNode();  This becomes important when we want to use the insert_sorted function to isort (insertion sort) an unsorted list.

3. Here, with added push_front, push_back and insertion sort of an unsorted list ...

Code: [Select]

/* ListOfStringInsertSorted_readLine_ver3.c */


#include "readLine.h" /* also includes, stdio.h, stdlib.h, string.h,
                        myAssert( .. ) and newCopy( .. ) */                     

typedef struct myNode
{
    char*  str;             /* 'str' holds the address of a new C string */
    struct myNode* next;    /* points to the next C string ... */
} Node;


typedef struct myList       /* to hold (data for) a List ... */
{
    Node* front;
    Node* back;
    int size;
    int isSorted;           /* NEW here compared to previous version */
} List;

Node* newNode()
{
    Node* n = (Node*) malloc( sizeof( Node ));
    myAssert( ( n != NULL ), "ERROR! malloc failed in 'createNode'" );
    n->next = NULL;
    return n;
}

/* prototypes ... */

/* INSERTS into 'list' in 'ABC...abc...' order the CString 's' */
void init( List* );
void insert_sorted( List*, Node* );
void isort( List* );                /* NEW here ... */
void push_front( List*, Node* );    /* NEW here ... */
void push_back( List*, Node* );     /* NEW here ... */
void clear( List* );                /* erase/free up all memory in list */
void show( List* );                 /* show all 'text lines' in the 'list' */


int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    char* s;
    Node* n;   
    List list;
    init( &list );
   
    puts( "Enter line of text to push_front in your list ('Ctrl Z' to end) ..." );
    fputs( "> ", stdout );
    while( (s = readLine( stdin )) )    /*  i.e. while s != NULL */
    {
        n = newNode();
        n->str = s;
        push_front( &list, n );
        fputs( "> ", stdout );
    }
   
    puts( "\nYour list now is ..." );
    show( &list );
   
    isort( &list );
    puts( "\nAfter isort ... show( &list ) is ..." );
    show( &list );
   
    printf( "\nEnter an other line to insert > " ); fflush( stdout );
    s = readLine( stdin );
    n = newNode();
    n->str = s;
    insert_sorted( &list, n );
   
    puts( "\nYour list now is:" );
    show( &list );   
 
    clear( &list );                     /* Note: re-sets list to NULL */
    puts( "\nAfter clear( &list ) ... your list now is:" );
    show( &list );   

    printf( "\nPress 'Enter' ... to continue ... " );
    getchar();
    return 0;
   
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */


void init( List* list )
{
    list->front = list->back = NULL;
    list->size = 0;
    list->isSorted = 1;
}


/* passing in the address (a reference) of both the 'List' and the 'Node' */
void insert_sorted( List* list, Node* n )
{   
    Node* head = list->front;   
    /* firstly, we handle most common case where 'n' is NOT the first Node */
    if( head != NULL && strcmp( n->str, head->str ) >= 0 ) /* NEED >= */
    {
        /* so search the linked list for the right location */
        Node* cur = head;
        while( cur->next != NULL && strcmp( cur->next->str, n->str ) <= 0 )
        {
            cur = cur->next;
        }
        if( cur == list->back ) list->back = n;
        n->next = cur->next;
        cur->next = n;
        /* list->front = head; // unchanged */
        ++ list->size;
    }
    else /* apparently this IS the first node ... */
    {
        n->next = head; /* set this node in first position, head could be NULL */
        list->front = n;
        ++ list->size;
        if( list->size == 1 ) list->back = n;
    }
}

void isort( List* list )
{
    Node* cur,
        * nextNode;
    List nList;
    init( &nList );   
    for( cur = list->front; cur != NULL; cur = nextNode )
    {
        nextNode = cur->next; /* get a copy of 'next' before changed below ... */
        insert_sorted( &nList, cur );
    }
       
    /* now ... update old list with new front and back ... */
    list->front = nList.front;
    list->back = nList.back;
    list->isSorted = 1;
    /* size hasn't changed */
}

void push_front( List* list, Node* n )
{
    n->next = list->front;  /* make old front 2nd positon in list, old=NULL is ok */
    list->front = n;        /* update front ...*/
   
    ++ list->size;
    if( list->size == 1 ) list->back = n;
    if( list->size > 1 ) list->isSorted = 0;
}

void push_back( List* list, Node* n )
{
    n->next = NULL; /* to signal that the end of the list is reached */
   
    if( list->size > 0 )list->back->next = n; /* place at end */
    else list->front = n;
    list->back = n; /* update back ...*/
   
    ++ list->size;
    if( list->size > 1 ) list->isSorted = 0;
}
   
void clear( List* list )
{
    Node* head = list->front;
    while( head != NULL )
    {
        Node* nextNode = head->next;
        free( head->str );
        free( head );
        head = nextNode;
    }
    list->size = 0;
    list->isSorted = 1;
    list->front = list->back = NULL ;
}

void show( List* list ) /* Note: 'head' is a 'local copy' of the pointer */
{
    if( list->size )
    {
        Node* head = list->front;
        int i;
        for( i = 0; head != NULL; head = head->next, ++i )
            printf( "list (%d): %s\n", i+1, head->str ); /* note added '\n' at str end */
        printf( "size = %d\n", list->size );
    }
    else puts( "'Your list is empty'" );
}

(Note: all 3 header files, readLine.h, myClist.h and myNode.h follow this ...ver.4 test program)

4. And finally ... adding msort (merge sort) ... and having now 2 more header files beside readLine.h ... ready to re-use ...

Code: [Select]

/* ListOfStringInsertSorted_ver4.c */ /* 2011-03-27 */


#include "myNode.h" /*  also includes readLine.h that includes ...
                             stdio.h, stdlib.h, string.h and has
                             myAssert( .. ) and newCopy( .. )
                        also includes myClist.h
                        myNode.h also has msort, isortClist, insert_sortedClist
                    */
                                           
int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    char* s;
    Node* n;   
    Clist list;
    initClist( &list );
   
    puts( "Enter lines of text to push_back into list ('Ctrl Z' to end) ..." );
    fputs( "> ", stdout ); fflush( stdout );
    while( (s = readLine( stdin )) )    /*  i.e. while s != NULL */
    {
        n = newNode();                  /* get new memory for this node ... */
        n->str = s;
        push_backClist( &list, n );
        fputs( "> ", stdout ); fflush( stdout );
    }
    puts( "\nYour list now is ..." );
    showClist( &list );
 
    msort( &list );
    puts( "\nASfter msort ... your list now is ..." );
    showClist( &list );
   
    printf( "\nEnter a line to insert in sorted order > " ); fflush( stdout );
    n = newNode();
    n->str = readLine( stdin );
    insert_sortedClist( &list, n );
    puts( "\nYour list now is:" );
    showClist( &list );   
   
    clearClist( &list );                 /* Note: re-sets list to NULL */
    puts( "\nAfter clearClist( &list ) ... your list now is:" );
    showClist( &list );

    puts( "Enter lines of text to push_front into list ('Ctrl Z' to end) ..." );
    fputs( "> ", stdout ); fflush( stdout );
    while( (s = readLine( stdin )) )    /*  i.e. while s != NULL */
    {
        n = newNode();                  /* get new memory for this node ... */
        n->str = s;
        push_frontClist( &list, n );
        fputs( "> ", stdout ); fflush( stdout );
    }
    puts( "\nYour list now is:" );
    showClist( &list );   
   
    printf( "\nEnter a line to insert in sorted order > " ); fflush( stdout );
    n = newNode();
    n->str = readLine( stdin );
    insert_sortedClist( &list, n );
   
    puts( "\nYour list now is:" );
    showClist( &list );   


    clearClist( &list );                 /* Note: re-sets list to NULL */
    puts( "\nAfter clearClist( &list ) ... your list now is:" );
    showClist( &list ); 
   
       
    printf( "\nPress 'Enter' to continue/exit ... " ); fflush( stdout );
    getchar();
    return 0;
   
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */


[David]

Code: [Select]

/* readLine.h */ /* this version 2011-03-27 */

/* http://developers-heaven.net/forum/index.php/topic,46.0.html */

/*
    Safe string data entry from file ... to replace gets and fgets
    BUT free new memory ... when done! Don't forget that C strings are
    pointers to a block of char, with a '\0' char at the terminal end ...

    Call like this:

        char* line = readLine( stdin );

        or ...

        while( (line = readLine( FILEp )) )
        {
            // process line ...
        }
*/

/* includes stdio.h, stdlib.h, string.h and myAssert and newCopy functions */

#ifndef dwREADLINE_H
#define dwREADLINE_H

/* can re-set/adjust here to best match your line-length */
#ifndef LINECHUNK
#define LINECHUNK 256
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char msg[] )
{
    if( !condition )
    {
        fprintf(stderr, "%s\n", msg );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif

#ifndef dwNEWCOPY
#define dwNEWCOPY
char* newCopy( const char* str )
{
    char* n = (char*) malloc( strlen(str) + 1 );
    myAssert( (n != NULL), "Error, malloc failed to allocate memory" );
    strcpy( n, str );
    return n;   
}
#endif


/* returns a string in new memory holding each word ... or NULL if EOF */
char* readLine( FILE* fp  )
{
    int c, i = 0; /* c to hold each char, i for index in string ... */
    int bufLen = LINECHUNK;
    void* tmp;
    /* cast for C++ compilers */
    char* strData = (char*) malloc( bufLen );
    myAssert( (strData != NULL), "Error: malloc failed ... (1)" );

    while( (c = fgetc(fp)) != EOF  &&  c != '\n' )
    {
        if( i == bufLen-1 ) /* skip while i <= bufLen-2 */
        {
            bufLen += bufLen; /* double memory */
            if( (tmp = realloc(strData, bufLen)) == NULL )
            {
                free(strData);
                myAssert( 0, "Error: realloc failed ... (2)" );
            }
            /* else ... */
            strData  = (char*) tmp; /* good realloc above, so update pointer */
        }   
        strData[i++] = c;
    }
    strData[i] = 0; /* assure '\0' termination */

    if( c == EOF  && strData[0] == 0 )
        { free( strData); return NULL; }
       
    /* else ... since didn't return NULL above, adjust string to right-size */
    if( (tmp = realloc(strData, i+1)) == NULL )
    {
        free(strData);
        myAssert( 0, "Error: realloc failed ... (3)" );
    }
    return (char*) tmp; /* return the right-sized string ... */
}

#endif


[David]

Code: [Select]

/* "myNode.h" */  /* 2011-03-27 */
/*
    myNode.h also includes readLine.h that includes ...
        stdio.h, stdlib.h, string.h and has
        myAssert( .. ) and newCopy( .. )
    myNode.h also includes myClist.h
    myNode.h also has msort, isortClist, insert_sortedClist
*/
#ifndef dwMYNODE_H
#define dwMYNODE_H

#ifndef sort_offset
#define sort_offset 0
#endif


#include "readLine.h" /* that includes ...
                            stdio.h, stdlib.h, string.h and
                            myAssert( .. ) and newCopy( .. ) */
                       
typedef struct myNode
{
    char*  str;             /* 'str' holds the address of a new C string */
    struct myNode* next;    /* points to the next C string ... */
} Node;

void clearNode( Node* n )
{
    free( n->str );
}

/* now can include ... */
#include "myClist.h"

/* and also define/add these ... */

/* insert into 'list' in 'ABC...abc...' sorted order the Node */
void insert_sortedClist( Clist*, Node* );
void isortClist( Clist* );
void showClist( Clist* );

/* and these ...*/
void msort( Clist* );
void mergesort( Clist* );
Node* merge( Clist*, Clist* );
void update_end( Clist* );



/* pass in the address of the Clist and the new Node to insert ... */
void insert_sortedClist( Clist* list, Node* n )
{
    Node* head;     
    if( !list->isSorted ) msort( list );
    head = list->front;
   
    /* firstly, we handle most common case where 'n' is NOT the first Node */
    if( head != NULL && strcmp( n->str, head->str ) >= 0 ) /* NEED >= */
    {
        /* so search the linked list for the right location */
        Node* cur = head;
        while( cur->next != NULL && strcmp( cur->next->str, n->str ) <= 0 )
        {
            cur = cur->next;
        }
        if( cur == list->back ) list->back = n;
        n->next = cur->next;
        cur->next = n;
        /* list->front = head; // unchanged */
        ++ list->size;
    }
    else /* if we reach here, this IS the first node ... */
    {
        n->next = head;     /* so set this node in first position */
        list->front = n;
        ++ list->size;
        if( list->size == 1 ) list->back = n;
    }
}

void isortClist( Clist* list )
{
    Node* cur,
        * nextNode;
    Clist nClist;
    initClist( &nClist );
    for( cur = list->front; cur != NULL; cur = nextNode )
    {
        nextNode = cur->next; /* get copy here before next is changed below ...*/
        insert_sortedClist( &nClist, cur ); /* 'cur' already is a Node pointer */
    }
     
    /* now ... update old list with new front and back ... */
    list->front = nClist.front;
    list->back = nClist.back;
    list->isSorted = 1;
    /* size hasn't changed ... */   
}

void showClist( Clist* list ) /* Note: 'head' is a 'local copy' of the pointer */
{
    if( list->size )
    {
        Node* head = list->front;
        int i;
        for( i = 0; head != NULL; head = head->next, ++i )
            printf( "list (%d): %s\n", i+1, head->str ); /* note added '\n' at str end */
        printf( "size = %d\n", list->size );
    }
    else puts( "'Your list is empty'" );
}

/* a recursive mergesort ... */
void mergesort(Clist* list)
{
    Node* cur = list->front;
    Clist a, b;

    /* base case is a Clist of length 0 or 1 ... */
    if ((cur == NULL) || (cur->next == NULL))  return;

    /* split Clist into 'a' and 'b' sublists ... */
    a.front = cur;
    b.front = cur->next;
    while((b.front != NULL) && (b.front->next != NULL))
    {
        cur = cur->next;
        b.front = b.front->next->next;
    }
    b.front = cur->next;
    cur->next = NULL; /* Clist divided into 2 roughly equal parts now ... */

    /* recursively sort the sublists ... */
    mergesort(&a);
    mergesort(&b);

    /* merge the two sorted Clists together ... */
    list->front = merge(&a, &b);
}


/* merge two sorted Clists with heads 'a' and 'b' ... in sorted order */
Node* merge(Clist* a, Clist* b )
{
    Node* sorted,
        * new_merged_head;

    if( a->front == NULL ) return b->front;
    if( b->front == NULL ) return a->front;

    if( strcmp(a->front->str + sort_offset, b->front->str + sort_offset) <= 0 )
    {
        sorted = a->front;
        a->front = a->front->next;
    }
    else
    {
        sorted = b->front;
        b->front = b->front->next;
    }
    new_merged_head = sorted;

    /* now ... */
    while( a->front != NULL && b->front != NULL )
    {
        if( strcmp(a->front->str + sort_offset, b->front->str + sort_offset) <= 0 )
        {
            sorted->next = a->front;
            sorted = a->front;
            a->front = a->front->next;
        }
        else
        {
            sorted->next = b->front;
            sorted = b->front;
            b->front = b->front->next;
        }
    }

    /* and finally ... */
    if( a->front != NULL )
        sorted->next = a->front;
    else if( b->front != NULL )
        sorted->next = b->front;

    return new_merged_head;
}

void update_end( Clist* list ) /* after sort */
{
    if( list->size > 1 )
    {
        Node* cur;
        for( cur = list->front; cur->next != NULL; cur = cur->next ) ;
        list->back = cur;
        list->back->next = NULL;
    }
}

void msort( Clist* clst )
{
    mergesort( clst );
    update_end( clst );
    clst->isSorted = 1;
    /*
    puts( "\nshowing in msort done ..." );
    showClist( clst );
    puts( "" );
    */
}

#endif


[David]

Code: [Select]

/* myClist.h */ /* 2011-03-27 */

/* must define Node before loading this ... */

#ifndef dwMYLIST_H
#define dwMYLIST_H

Node* newNode()
{
    Node* n = (Node*) malloc( sizeof( Node ));
    myAssert( ( n != NULL ), "ERROR! malloc failed in 'newNode()'" );
    return n;
}

typedef struct myClist       /* to hold (data for) a Clist ... */
{
    Node* front;
    Node* back;
    int size;
    int isSorted;
} Clist;


void initClist( Clist* );
void push_frontClist( Clist*, Node* );
void push_backClist( Clist*, Node* );
void clearClist( Clist* ); /* erase/free up all memory in list */


void initClist( Clist* list )
{
    list->front = list->back = NULL;
    list->size = 0;
    list->isSorted = 1;
}

void push_frontClist( Clist* list, Node* n )
{
    n->next = list->front;  /* make old front 2nd positon in list, old=NULL is ok */
    list->front = n;        /* update front ...*/
   
    ++ list->size;
    if( list->size == 1 ) list->back = n;
    if( list->size > 1 ) list->isSorted = 0;
}

void push_backClist( Clist* list, Node* n )
{
    n->next = NULL; /* to signal that the end of the list is reached */
   
    if( list->size > 0 )list->back->next = n; /* place at end */
    else list->front = n;
    list->back = n; /* update back ...*/
   
    ++ list->size;
    if( list->size > 1 ) list->isSorted = 0;
}

   
void clearClist( Clist* list )
{
    Node* head = list->front;
    while( head != NULL )
    {
        Node* nextNode = head->next;
        clearNode( head ); /* free( head->str ); */
        free( head );
        head = nextNode;
    }
    list->size = 0;
    list->isSorted = 1;
    list->front = list->back = NULL ;
}

#endif