New thread especially for students of C and C++

[David]

Now ... the enhanced and simplified version using typedef ...

Code: [Select]

/* list_stuff2.c */

/* this version 2010=05-08 */

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

/*
    Notes:
    1. for circular lists the tail points back to the head, instead of NULL
    2. for circular lists the tail is tracked/passed ... thus: head = tail->next
*/


typedef struct Node
{
    int data;
    struct Node* next;
} Node;

typedef Node* pNode;

pNode createNewNode( int val )
{
    pNode newNode = (pNode) malloc( sizeof(Node) );
    if( newNode == NULL)
    {
        fputs( "Error: malloc failed to allocate memory. "
                "Press 'Enter' to exit ... ", stderr );
        getchar();
        exit(1);
    }
    newNode->data = val;
    newNode->next = NULL;
    return newNode;
}

/* head pointer is passed in to p, a local copy */
void show( pNode p )
{
    for( ; p != NULL; p = p->next )
        printf( "%d ", p->data );
    putchar( '\n' );
}

/* returns '1' if the list is cyclic or '0' if NULL terminated ... */
int isCyclic( pNode head )
{
    pNode start = head;
    for( ;; )
    {
        if( start==NULL || start->next==NULL ) return 0;
        else if( start->next == head ) return 1;
        else start = start->next;
    }
}

/* show list: (1) tail points to NULL ... or (2) tail points back to head */
void showCyclic( pNode p )
{
    pNode cur = p;
    if( cur && isCyclic( p ) ) p = cur = cur->next;
    int count = 0;
    if( cur != NULL )
    {
        printf( "%d ", cur->data ); /* handle first node as a special case */
        cur = cur->next;
        ++count;

        for( ; cur && cur != p; cur = cur->next )
            printf( "%d ", cur->data ), ++count;
        printf( "\nThe list above is %scyclic and has length %d \n",
                (cur ? "" : "NOT "), count );
    }
    else puts( "... empty" );
}


/* reverses direction of pointers to next ... handles cyclic lists only */
void revCyclic(pNode* headRef)
{
    pNode start = *headRef;
    if( start != NULL && start != start->next ) /* if more than one element */
    {
        pNode cur, nxtTmp, newHead = NULL;
        start = start->next; /* recall: start = tail->next ... for cyclic ... */
        cur = start; /* A */

        /* ok ... switch directions of first pointer ... as special case */
        /* A->B->C  becomes  C->B->A */
        nxtTmp = cur->next;     /* address of B stored in Tmp */
        cur->next = newHead;    /* A-> N */
        newHead = cur;          /* N := A  ... A-> A */
        cur = nxtTmp;           /* A := B  ... so now ... B-> A */

        while( cur != start )   /* now can handle cur != start in a loop ... */
        {
            nxtTmp = cur->next; /* address of C stored in Tmp ... */
            cur->next = newHead;/* B-> N */
            newHead = cur;      /* N := B ... B-> B */
            cur = nxtTmp;       /* B := C ... so now ... C-> B */
        }
        /*  recall ( cur == start )  here ... */
        start->next = newHead; /* close loop: join old head (now tail) to newHead */
        *headRef = cur; /* i.e return the tail ... since a circular list */
    }
}

void eraseAllCyclic( pNode* headRef ) /* handles NULL terminated also */
{
    if( *headRef != NULL )
    {
        pNode cur = *headRef, start = *headRef, t;
        cur = start->next;
        free( start ); /* free the first node as a special case ... */

        for( t = cur; t &&  t!=start; t = cur ) /* handle the rest ...*/
        {
            cur = cur->next;
            free( t );
        }
        *headRef = NULL;
    }
}

void eraseAll( pNode* headRef )
{
    pNode n = *headRef;
    for( ; n != NULL; *headRef = n )
    {
        n = n->next;
        free( *headRef );
    }
}


void pushNodeFront( pNode* headRef, pNode n )
{
    n->next = *headRef;
    *headRef = n;
}

void insertNodeSorted( pNode* ref, pNode n )
{
    while( *ref  &&  n->data > (*ref)->data ) /* find place to insert ... */
        ref = &( (*ref)->next ); /* move ref to point to the next field of the node */
    pushNodeFront( ref, n ); /* pk ... now insert here ... */
}

void push_front( pNode* headRef, int newData )
{
    pNode newNode = createNewNode( newData );
    newNode->next = *headRef;
    *headRef = newNode;
}

void insertValSorted( pNode* ref, const int val )
{
    while( *ref  &&  val > (*ref)->data )
        ref = &( (*ref)->next ); /* move ref to point to the next field of the node */
    push_front( ref, val );
}

/*
    Probably the hardest part is seeing that reverse( &rest )
    does in fact reverse the rest ... Also ... seeing the trick to
    getting the one front node all the way to the end of the list.
    Drawing a sketch might assist seeing how this works ...
*/
void reverse(pNode* headRef) /* a recursive reverse method demo'd here ... */
{
    pNode first = *headRef;
    if( first != NULL ) /* suppose first = a, b, c... */
    {
        pNode rest = first->next; /* rest = b, c... */
        if( rest == NULL) return;   /* since one element only in the list */

        /* recursive call ... */
        reverse( &rest ); /* reverse the smaller  b, c... case */

        /* now unwinding stack ... */
        *headRef = rest; /* fix the head pointer */

        /* ... consider old 'first' 'a' and old 'first->next' 'b' */
        first->next->next = first; /* put the first 'a' after 'b' ... */
        first->next = NULL; /* set this 'new end' .... to be the 'end' ... */
        /*
        puts( "Unwinding stack ..." );
        show( rest );
        */
    }
}

/* head pointer is passed in to p, a local copy */
int len( pNode p )
{
    int count = 0;
    for( ; p != NULL; ++ count, p = p->next ) ;
    return count;
}

/* create and return the new list 1, 2, 3, 4... */
pNode createNewListRange( int r ) /* r is a local copy */
{
    pNode head = NULL; /* start with the empty list */
    while( r ) push_front( &head, --r );
    return head;
}

pNode createNewListLocalRefRange( int r )
{
    pNode head = NULL;
    pNode* lastPtrRef= &head; /* begins pointing to the head pointer */
    int i;
    for( i = 0; i < r; ++i )
    {
        push_front( lastPtrRef, i ); /* add at the last pointer in the list */
        lastPtrRef = &( (*lastPtrRef)->next ); /* advance to point to the
                                                  new last pointer */
    }
    return head;
}

pNode insertSort( pNode cur )
{
    pNode n, nhead = NULL;
    while( cur != NULL )
    {
        n = cur;
        cur = cur->next;
        insertNodeSorted( &nhead, n );
    }
    return nhead;
}



int main( void )
{
    int i, test[] = { 1, 11, 10, 9, 8, 7, 6, 3, 4, 5, 2, 0 };
    const int size = sizeof test / sizeof test[0];
    pNode tail, list = createNewListRange( 7 );
    printf( "The length of the createNewListRange( 7 ) is %d and the list is:\n",
            len( list ) );
    show( list );
    
    tail = list;
    reverse( &list );
    printf( "The length of the reverse( &list ) is %d and the list is:\n",
            len( list ) );
    show( list );
    
    push_front( &(tail->next), 99);
    tail = tail->next;
    push_front( &(tail->next), 101);

    printf( "The length AFTER THE 2ND push_front( &(tail->next), 101)"
            " is %d and the list is:\n",
            len( list ) );
    show( list );
    
    eraseAll( &list );
    printf( "After eraseAll( &list ) ... length is %d and the list is:\n",
            len( list ) );
    show( list );
    
    fputs( "Press 'Enter' to continue ... ", stdout );
    getchar();

/* ************************************************************************** */
    
    list = createNewListLocalRefRange( 11 );
    printf( "The length of the createNewListLocalRefRange( 11 )"
            " is %d and the list is:\n",
            len( list ) );
    show( list );
    
    eraseAll( &list );
    for( i =0; i < size; ++ i)
        insertValSorted( &list, test[i] );
    printf( "The length of the NEW (insertValSorted) list"
            " is %d and the list is:\n",
            len( list ) );
    show( list );
    
    eraseAllCyclic( &list ); /* test out on a NON-cyclic list ... */
    printf( "After eraseAllCyclic( &list ) ... "
            "the length is %d and the list is:\n", len( list ) );
    show( list );
    
    for( i =0; i < 17; ++ i)
        push_front( &list, i );
    printf( "The length of the NEW (push_front) list is %d and the list is:\n",
            len( list ) );
    show( list );
    
    list = insertSort( list );
    printf( "The length of the NEW (insertSort'ed) list is %d and the list is:\n",
            len( list ) );
    show( list );
    
    tail = list; /* get a copy of head pointer ... before reversing ... */
    reverse( &list );
    printf( "The length of the reversed( &list ) is %d and the list is:\n",
            len( list ) );
    showCyclic( list ); /* test out on NON-cyclic list ... */

    tail->next = list; /* make into a cyclic list ... */
    printf( "The next list is %scyclic ... \n",
            (isCyclic( tail ) ? "" : "NOT ") );
    showCyclic( tail );

    revCyclic( &tail );
    printf( "After ... revCyclic( &tail ) ... the list is %scyclic ... \n",
            (isCyclic( tail ) ? "" : "NOT ") );
    showCyclic( tail );
    eraseAllCyclic( &tail );

    printf( "After ... 'eraseAllCyclic( &tail ); showCyclic( tail );' list is " );
    showCyclic( tail );
    
    fputs( "Press 'Enter' to continue ... ", stdout );
    getchar();
    return 0;
}



And ... merging two unsorted files into one new file (in sorted order) ...
via insert_sort and one linked list in RAM ... (and using a struct to hold the data)

Code: [Select]

/* mergeTwoFiles_struct.c */ /* this version 2010-05-25 */

/*
    C demo of merging two files into a new sorted file ... using a linked-
    list ... by inserting struct, in sorted order, into the (growing) list.
    
    Note: using fscanf( fp, "%s", buffer ) to read each WORD on the file line...
    EXCEPT FOR the last chunk on the line ... That is obtained by ...
    pS->first = getString( fp ); // reads the WHOLE rest of the line ... //
    
    http://developers-heaven.net/forum/index.php/topic,46.0.html
*/

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

#define fName1 "info1.txt"
#define fName2 "info2.txt"
#define fName3 "merge.txt"
#define WORD_CHUNK 32 /* adjust to your data's size to minimize realloc calls */

/*
info1.txt

09876 year1 Smith Catee Rose
08765 year2 Clinton Hilary Claire
07654 year3 Barrack Richard Kenneth

info2.txt

08967 year1 Edison Bill
06789 year2 Bell Robert Ed

merge.txt

07654 year3 Barrack Richard Kenneth
06789 year2 Bell Robert Ed
08765 year2 Clinton Hilary Claire
08967 year1 Edison Bell
09876 year1 Smith Catee Rose
*/

typedef struct myStudent
{
    char* id;
    char* year;
    char* last;
    char* first;
    struct myStudent* next;
} Student;

typedef Student* pStudent;

/* these 2 global var's used to simplify function calls ... */
pStudent pHead = NULL; /* Note: need a NULL value to start inserts ... */
int numStudents = 0;

void insert( pStudent pS );
int readFile( char* name );
int writeFile( char* name );
int studentCmp( pStudent pS1, pStudent pS2 );
char* newCopy( char* str );
char* getString( FILE* fp );
void view( pStudent pS );
void showAll();
void delAll();
void flushStdin();
void myAssert( int condition, char message[] );


int main() /* ********************* start of main *************************** */
{
    int num = readFile( fName1 );
    if( num )
        numStudents += num;

    num = readFile( fName2 );
    if( num )
    numStudents += num;

    //showAll();

    num = writeFile( fName3 );
    if( num == numStudents )
        printf
        (
            "All %d students were successfully sorted and merged in file %s.",
            num, fName3
        );
    else
        printf
        (
            "Error: writing to file %s  Note: wrote %d vs. numStudents of %d",
            fName3, num, numStudents
        );

    delAll();
    printf("\n\nPress 'Enter' to continue ... ");
    flushStdin();

    /* if using Windows OS ... */
    system( "notepad merge.txt" );
    return 0;
    
} /* ******************************* end of main **************************** */



void flushStdin()
{
    while( getchar()!='\n' ) ;
}

char* newCopy( char* str )
{
    char* nCopy = (char*) malloc( strlen(str) + 1 );
    myAssert( (nCopy != NULL), "Error: malloc failed (0) " );
    strcpy( nCopy, str );
    return nCopy;
}

char* getString( FILE* fp )
{
    int c, i= 0, chunk = WORD_CHUNK;
    char* tmp;
    char* buffer = (char*) calloc( chunk, 1 );
    myAssert( (buffer != NULL), "Error: calloc failed (1) " );
    while( (c=fgetc(fp))!=EOF && c!='\n' ) /*eats up WHOLE line including '\n'*/
    {
        if( i == chunk - 2 )
        {
            chunk += WORD_CHUNK;
            tmp = (char*) realloc( buffer, chunk );
            if( tmp == NULL )
            {
                free( buffer );
                myAssert( 0, "Error: realloc failed (2) " );
            }
            /* else ...  update buffer address ... */
            buffer = tmp;
        }
        buffer[i++] = c;
    }
    buffer[i] = 0;
    tmp = (char*) realloc( buffer, i+1  );
    if( tmp == NULL )
    {
        free( buffer );
        myAssert( 0, "Error: realloc failed (3) " );
    }
    return tmp;
}

/* insert in list with last & first names in proper order */
void insert( pStudent pS )
{
    pStudent q = pHead; /* Get a working copy of pHead in q */
    
    /* Firstly, we handle the case where 'this' should be the first element. */
    if(pHead == NULL || studentCmp(pS, pHead) < 0)
    {
        /* So ... it now becomes the first element ... */
        pS->next = pHead; /* old pHead becomes 2nd in list ... */
        pHead = pS; /* and ... this pS ... becomes the head of the list */
    }
    else /* If here ... search the linked list for the right location ... */
    {
        /* Start comparing with element AFTER 'q' ... i.e. the 'next in' ... */
        while(q->next != NULL && studentCmp(q->next, pS) <= 0)
        {
            q = q->next; /* Traverse the list ... */
        }
        /*
            Ok, insert after 'q' by relinking the pointers (similar to above)
            ( Includes inserting at end position ... where q->next == NULL )
        */
        pS->next = q->next; /* Inserted 'pS' is linked to 'upstream element' */
        q->next = pS;  /* Now 'q' is updated to link to the new 'pS' element */
    }
}

void view( pStudent pS )
{
    printf
    (
        "ID: %s  "
        "Year: %s  "
        "Name: %s,%s", /* Note: 2nd string already contains a leading space */
        pS->id, pS->year, pS->last, pS->first
    );
}

void showAll()
{
    pStudent p = pHead;     /* int c; */
    if( pHead == NULL )
    {
        puts("\nNo records in memory at present.") ;
        return;
    }

    /* If reach here ... */
    while( p != NULL )
    {
        view( p );
        putchar( '\n' );
        p = p->next;
    }
    fflush( stdout );
}

int writeFile(char *name)
{
    FILE* fp;
    int count = 0; /* to track the records actually written to the file */
    pStudent p = pHead;
    if( p == NULL )
    {
        puts("\nNo records available ... so NO records written to file.") ;
        return 0;
    }
    
    fp = fopen( name, "w" );
    if( fp == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", name);
        flushStdin();
        return 0;
    }

    while( p != NULL )
    {
        fprintf
        (
            fp,
            "%s "
            "%s "
            "%s" /*no space here ... since a leading space is in next string*/
            "%s\n",
            p->id, p->year, p->last, p->first
        );

        ++count;
        p = p->next;
    }
    fclose( fp );
    return count; /* Number of records written. */
}

int readFile( char* name )
{
    int count = 0;
    pStudent pS;
    char buffer[WORD_CHUNK+1];
    FILE* fp = fopen( name, "r" );
    if( fp  == NULL )
    {
        printf
        (
            "\nError opening file %s.\n"
            "Perhaps it hasn't been created yet?\n"
            "Press 'Enter' to continue ... ",
            name
        );
        flushStdin();
        return 0;
    }

    /* If the program reaches here ... */
    while(  fscanf(fp, "%s", buffer) != EOF  )
    {
        pS = (pStudent) malloc( sizeof(Student) );
        myAssert( (pS != NULL), "Error: malloc failed (4) " );
        
        pS->id = newCopy( buffer );

        fscanf( fp, "%s", buffer );
        pS->year = newCopy( buffer );

        fscanf( fp, "%s", buffer );
        pS->last = newCopy( buffer );

        pS->first = getString( fp ); /* reads the WHOLE rest of the line ... */

        insert( pS );
        ++count;
    }
    fclose( fp );

    printf("%d records were read into memory from the file %s.\n", count, name);

    return count; /* Total number of student records found in the file. */
}

/* A function to compare two student records to permit sorting ... */
int studentCmp( pStudent pS1, pStudent pS2 )
{
    int compare = strcmp(pS1->last, pS2->last); /* compare last_names */
    if ( compare == 0 ) /* if last_names same ... use first_names */
        return strcmp(pS1->first, pS2->first);
    return compare; /* use last_names after all since different */
}

void delAll()
{
    pStudent p = pHead; /* set p to this initial value to start loop */
    pStudent pNext;     /* to hold the pointer to the next record */

    while( p != NULL )
    {
        pNext = p->next; /* get pointer to the next record */

        free( p->first );
        free( p->last );
        free( p->year );
        free( p->id );
        
        free( p );

        p = pNext; /* update p ... */
    }

    /* update globals ...  */
    pHead = NULL;
    numStudents = 0;
}

void myAssert( int condition, char message[] )
{
    if( !condition )
    {
        fputs( message, stderr );
        getchar();
        exit(1);
    }
}


Here are some more merge/sorts of 2 files (that wouldn't fit here) ...

and a way to sort a file too big for memory ...
(by breaking it up into 2 parts and sorting each part, then merging the 2 sorted files)

http://developers-heaven.net/forum/index.php/topic,106.msg611.html#msg611

[David]

Check back soon ... for a mail merge demo in C, using a list of a list of lines of C strings, for a 'keyed' dictionary ...

(Also ... featuring a circular linked list to speed up push_back ... and searches for data that is mostly ordered.)

(Actually ... please contact me, if you are interested in this useful program for professional contractors ... who manage many job sites in a single project ... each job site tasks, pulled from a master-dictionary-of-keyed-tasks to be done there.)

[David]

Here is a step on the way there ... to a mail merge program ...  

Take a look at this split_demo.c that shows how to split a line ( a CString ) ...
and to return a Clist of words/tokens ...

Note: You will need all three files that follow, in the same folder, to compile/run this split_demo.c ...
(First the demo file ... then the three helper files ...)

Code: [Select]

/* split_demo.c */ /* this version 2010-07-13 */

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

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

#define DELIMITS "* .?!,;:\t-" /* if don't define ... becomes "\t " */

#include "split.h"  /*
                        includes ClistOfString.h ... that includes ...
                        stdio.h, stdlib.h, string.h ... and adds ...
                        readLine, myAssert
                    */

int main() /* ********************** BEGIN MAIN ***************************** */
{
    char s[] ="*** See! *** Sample words, split-up?  ";
    char* s2 = "This, ... sample string, into tokens ... ";
    Clist myCList;
    List ml;
    init( &myCList ); /* Note: MUST initial list for it to work properly ... */

    printf( "For delimits '%s', \n", DELIMITS );
    printf( "splitting string '%s' \n", s );
    split( &myCList, s );
    showAll( &myCList );

    msort( &myCList );
    puts( "\nAfter msort ... " );
    showAll( &myCList );
    printf( "... and after msort ... the original string is still: \n"
          "'%s'\n", s );

    fputs( "\nPress 'Enter' to continue ... ", stdout );
    getchar();

    split( &myCList, s );

    ml.line = newCopy( "At_the_end_at_first ..." );
    push_back( &myCList, &ml );

    ml.line = newCopy( "z_But_at_the_beginning_at_first ..." );
    push_front( &myCList, &ml );

    msort( &myCList );
    puts( "\nAfter ... (another) split( &myCList, s ); (then) msort( &myCList ); ... " );
    showAll( &myCList );
    printf( "Note ... the original string is now: \n"
          "'%s'\n", s );

    fputs( "Press 'Enter' to continue ... ", stdout );
    getchar();
   
    freeAll( &myCList );
    showAll( &myCList );
   
    split( &myCList, s );
    split( &myCList, s2 );
    split( &myCList, s );
    puts( "\nAfter ... split( &myCList, s ); split( &myCList, s2 ); "
          "split( &myCList, s ); ... " );
    showAll( &myCList );
    printf( "Note ... the 1st original string is now: \n"
          "'%s'\n", s );
    printf( "Note ... the 2nd original string is now: \n"
          "'%s'\n", s2 );

    fputs( "Press 'Enter' to continue ... ", stdout );
    getchar();

    msort( &myCList );
    puts( "\nAfter msort ... " );
    showAll( &myCList );
    printf( "Note ... the 1st original string is now: \n"
          "'%s'\n", s );
    printf( "Note ... the 2nd original string is now: \n"
          "'%s'\n", s2 );

    freeAll( &myCList );
    showAll( &myCList );
    fputs( "Press 'Enter' to continue ... ", stdout );
    getchar();

    return 0;
} /* ******************************** END MAIN ****************************** */



And a slightly different form of split, that preserves any empty field, if delimiters are adjacent ...
(Note: this 2nd demo uses split2.h)

Code: [Select]

/* split_demo_2.c */ /* this version 2010-07-13 */

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

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

#define DELIMITS ", -" /* if don't define ... becomes "\t " */

#include "split2.h"  /*
                        includes ClistOfString.h ... that includes ...
                        stdio.h, stdlib.h, string.h ... and adds ...
                        readLine, myAssert
                    */

#define TESTFILE "test.txt" /* 9 lines (with 3 blank) */
/*

2, ,,Hi-there,,my,dearest
3, Mary

5, What,can,I,do,for,you?,

7, Dearest,
8, You,can,go,,,to,the,store,for,me.,,,
9, my dear

*/


int main() /* ********************** BEGIN MAIN ***************************** */
{
    FILE* fp = fopen( TESTFILE, "r" );
    char* s; /* (pointer to) C string ... to hold a line of 'words' ... */
    Clist myCL;
    init( &myCL ); /* Note: MUST initial list for it to work properly ... */

    myAssert( (fp != NULL), "Error: file " TESTFILE " failed to open." );
    while( (s = readLine(fp)) )
    {
        printf( "For delimits ... '%s', ", DELIMITS );
        printf( "splitting string ... \n'%s' \n", s );
        split( &myCL, s );
       
        //showAll( &myCL );
        {
            int i = 0;
            pList p = myCL.start;
            for( ; p != NULL; p = p->next )
                printf( "<%02d> '%s'\n", ++i, p->line );
            printf( "myCL.size = %d\n", myCL.size );
            putchar('\n');
        }

        free( s );
        freeAll( &myCL );
    }
    fclose( fp );
   
    /* Note: used a new block here ... just to add this code here ... */
   
    {   /* Note: '\0' char at index 7 AND at index 9 ... so split stops at 7 */
        char ary[] = { '0', ';', '2', '3', ' ', '5', ';', '\0', '8', '\0' };
        int i = 0, len = sizeof ary;
        printf( "ary len = %d, ary = '", len );
        for( ; i < len; ++i ) putchar( ary[i] );
        puts("'");
        split( &myCL, ary );
        showAll( &myCL );
        freeAll( &myCL );
    }

    printf( "Press 'Enter' to exit ... " ); fflush( stdin );
    getchar();
    return 0;
} /* ******************************** END MAIN ****************************** */


[David]

Here are the three helper files needed for the above program(s) to compile/run ...

Code: [Select]

/* split.h */ /* this version: 2010-07-13 */

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

#ifndef dwSPLIT_H
#define dwSPLIT_H

#ifndef DELIMITS
#define DELIMITS  " \t"
#endif

#define NUM_DLMTS  sizeof(DELIMITS) -1

#include "ClistOfString.h" /* adds stdio, stdlib, string, readLine, myAssert */


char* createNewString( int len )
{
char* n;
    if( len < 0 ) len = 0;
    n = (char*) malloc(len+1);
    myAssert( (n!=NULL), "Error: malloc failed to allocate memory." );
    n[0] = 0;
    return n;
}

char* newCopy( const char* s )
{
    int slen = strlen(s);
    char* ncopy = createNewString(slen);
    strcpy(ncopy, s);
    return ncopy;
}

char* substr( const char* start, const char* end )
{
    int len = end-start+1;
    char* newCpy = createNewString(len);
    strncpy( newCpy, start, len );
    newCpy[len] = 0;
    return newCpy;
}

/* returns POSITION 1..len if in string ... otherwise, returns 0 */

int chrInString( const char* s, char c )
{
    int i;
    for( i =0; s[i] != 0; ++i )
        if( c ==  s[i] )
            return i+1;
    return 0;
}

void split( Clist* lst, char* s )
{
    char *p1 = s, *p2;
    List ml;
    for( ; ; ) /* loop forever ... until break */
    {
        while( *p1 != 0 && strchr(DELIMITS, *p1) ) ++p1;
        if( *p1 == 0 )
break; /* i.e. if empty or all delimits */

        p2 = p1+1;
        while( *p2 != 0 && !strchr(DELIMITS, *p2) ) ++p2;
        ml.line = substr( p1, p2-1 ); /* new copy in new memory in ml.line */
        push_back( lst, &ml );
        p1 = p2;
    }
}


#endif

Also see ...
http://developers-heaven.net/forum/index.php/topic,2584.0.html

And the 2nd version, for the 2nd demo above ...

Code: [Select]

/* split2.h */ /* this version: 2010-07-13 */

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

#ifndef dwSPLIT2_H
#define dwSPLIT2_H

#ifndef DELIMITS
#define DELIMITS  " \t"
#endif

#define NUM_DLMTS  sizeof(DELIMITS) -1

#include "ClistOfString.h" /* adds stdio, stdlib, string, readLine, myAssert */


char* createNewString( int len )
{
char* n;
    if( len < 0 ) len = 0;
    n = (char*) malloc(len+1);
    myAssert( (n!=NULL), "Error: malloc failed to allocate memory." );
    n[0] = 0;
    return n;
}

char* newCopy( const char* s )
{
    int slen = strlen(s);
    char* ncopy = createNewString(slen);
    strcpy(ncopy, s);
    return ncopy;
}

char* substrLen( const char* start, int len )
{
    char* newCpy = createNewString(len);
    strncpy( newCpy, start, len );
    newCpy[len] = 0;
    return newCpy;
}

/* returns POSITION 1..len if in string ... otherwise, returns 0 */

int chrInString( const char* s, char c )
{
    int i;
    for( i =0; s[i] != 0; ++i )
        if( c ==  s[i] )
            return i+1;
    return 0;
}

void split( Clist* lst, char* s )
{
    List ml;
    char* t = s + strlen(s); /* t is address of one past last char in line */
    while( s < t ) /* loop while s is still IN the line ... */
    {
        /* search for delimiters ... including ALSO '\0' at end of line ... */
        size_t len = strcspn(s, DELIMITS);
        ml.line = substrLen( s, len ); /* copy is in new memory in ml.line */
        push_back( lst, &ml );
        /* advance pointer to just beyond 'delimiter' at end of this 'word' */
        s += len+1;
    }
}

#endif


Code: [Select]

/* ClistOfString.h */ /* this version: 2010-07-13 */

#ifndef dwClistOfString_H
#define dwClistOfString_H

#ifndef sort_offset
#define sort_offset 0
#endif

/* using readLine here ... instead of gets and fgets */
#include "readLine.h" /* includes stdio.h, stdlib.h  ... also myAssert( ... ) */

/* Note: stdio.h, stdlib.h and myAssert were included in "readLine.h" above */
#ifndef dwSTRING_H
#define dwSTRING_H
#include <string.h> /* re. memcpy */
#endif

typedef struct ClistOfString
{
    char* line;     /* since CStrings are '\0' terminated ... can get strlen */
    struct ClistOfString* next;
} List ;

typedef List* pList;

typedef struct myClist
{
    pList start;
    pList end;
    int size;
    int isSorted;
} Clist;

/* with these, an address is passed, so NO copy made and/or original updated */
void init( Clist* ); /* sets start to NULL, size to 0. isSorted to 1 */
void push_front( Clist*, List* );
void push_back( Clist*, List* );
void freeAll( Clist* );
void show( pList );
void showAll( Clist* );

void msort( Clist* );
void mergesort( Clist* );
pList merge( Clist*, Clist* );
void update_end( Clist* );


void init( Clist* list )
{
    list->start = list->end = NULL;
    list->size = 0;
    list->isSorted = 1;
}

void push_front( Clist* list, List* d )
{
    pList p = (pList) malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/
    p->next = list->start;
    list->start = p;

    ++ list->size;
    if( list->size > 1 ) list->isSorted = 0;
    else list->end = list->start;
}

void push_back( Clist* list, List* d )
{
    pList p = (pList) malloc( sizeof(List) );
    if( p == NULL )
    {
        freeAll( list );
        myAssert( 0, "Error: malloc failed to allocate memory." );
    }

    /* now add in ALL new dat ... (assuming next pointer is last of dat) */
    memcpy( p, d, sizeof(List)-sizeof(pList) ); /* -sizeof(any_pointer) is ok */
    /* and set pointers to next ... and start ...*/

    p->next = NULL;
    ++ list->size;
    if( list->size > 1 )
    {
        list->end->next = p;
        list->end = p;
        list->isSorted = 0;
    }
    else
        list->start = list->end = p;
}

void freeAll( Clist* list )
{
    //printf( "\nFreeing list->size  of %d ... \n", list->size );
    if( list->size > 0 )
    {
        pList cur = list->start;
        for( ; cur != NULL; cur = list->start  )
        {
            list->start = cur->next;
            free( cur->line );
            free( cur );
        }
        init( list );
    }
}

void show( pList pd )
{
    printf( "%s\n", pd->line );
}
void showAll( Clist* list )
{
    if( list->size )
    {
pList p = list->start;
for( ; p != NULL; p = p->next )
show( p );
printf( "List size = %d\n", list->size );
    }
    else puts( "The list is empty ... " );
}


/* a recursive mergesort ... */
void mergesort(Clist* list)
{
    pList cur = list->start;
    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.start = cur;
    b.start = cur->next;
    while((b.start != NULL) && (b.start->next != NULL))
    {
        cur = cur->next;
        b.start = b.start->next->next;
    }
    b.start = 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->start = merge(&a, &b);
    list->isSorted = 0;
}


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

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

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

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

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

    return new_merged_head;
}

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

void msort( Clist* clst )
{
    mergesort( clst );
    update_end( clst );
}

#endif /* end of ifndef dwSTRING_H ... */


And you can find readLine.h here ...

http://developers-heaven.net/forum/index.php/topic,106.msg564.html#msg564


For an other version of split.h, ClistOfString.h with Clist.h separated out ... Cvec ... and demo programs that use these ... see ...

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

[David]

Merging ... using a linked-list, insertsort and fgets to read each line (no struct) ...
(and to sort lines using an offset into that line)
(placed here, since wouldn't fit above, with other files merging/sorting examples.)

Code: [Select]

/* mergeTwoFiles_fgets.c */ /* this version 2010-05-25 */

/*
    C demo of merging two files into a new sorted file ... using a linked-
    list ... by inserting lines, in sorted order, into the (growing) list.
    
    Note: using while( fgets(buffer, MAXLEN+1, fp) ) to read each file line,
    so ... max line length is limited to the define value of MAXLEN
    
    Pick MAXLEN so '\n' char is always included at the end of each line read in
    
    http://developers-heaven.net/forum/index.php/topic,46.0.html
*/

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

#define fName1 "info1.txt"
#define fName2 "info2.txt"
#define fName3 "merge.txt"
#define MAXLEN 132

#define sort_offset 12 /* so files will be sorted by names ... */

/*
info1.txt

09876 year1 Smith Catee Rose
08765 year2 Clinton Hilary Claire
07654 year3 Barrack Richard Kenneth

info2.txt

08967 year1 Edison Bill
06789 year2 Bell Robert Ed

merge.txt

07654 year3 Barrack Richard Kenneth
06789 year2 Bell Robert Ed
08765 year2 Clinton Hilary Claire
08967 year1 Edison Bell
09876 year1 Smith Catee Rose
*/

typedef struct myStudent
{
    char* dataLine;
    struct myStudent* next;
} Student ;

typedef Student *pStudent;

/* using these two global variable to ease function calls ... */
pStudent pHead = NULL; /* Note: needs a NULL value to start inserts ... */
int numStudents = 0;

void insert( pStudent pS );
int readFile( char* name );
int writeFile( char* name );
int studentCmp( pStudent pS1, pStudent pS2 );
char* newCopy( char* str );
void view( pStudent pS );
void showAll();
void delAll();
void flushStdin();
void myAssert( int condition, char nessage[] );



int main() /* ********************* start of main *************************** */
{
    int num = readFile( fName1 );
    if( num )
        numStudents += num;

    num = readFile( fName2 );
    if( num )
        numStudents += num;

    //showAll();

    num = writeFile( fName3 );
    
    if( num == numStudents )
        printf
        (
            "All %d students were successfully sorted and merged in file %s.",
            num, fName3
        );
    else
        printf
        (
            "Error: writing to file %s  Note: wrote %d vs. numStudents of %d",
            fName3, num, numStudents
        );

    delAll();
    printf("\n\nPress 'Enter' to continue ... ");
    flushStdin();

    system( "notepad merge.txt" );
    return 0;
    
} /* ******************************* end of main **************************** */



void flushStdin()
{
    while( getchar()!='\n' ) ;
}

char* newCopy( char* str )
{
    char* nCopy = (char*) malloc( strlen(str) + 1 );
    myAssert( (nCopy != NULL), "Error: malloc failed (1)" );
    strcpy( nCopy, str );
    return nCopy;
}

/* insert in list with last & first names in proper order */
void insert( pStudent pS )
{
    pStudent q = pHead; /* Get a working copy of pHead in q */
    
    /* Firstly, we handle the case where 'this' should be the first element. */
    if(pHead == NULL || studentCmp(pS, pHead) < 0)
    {
        /* So ... it now becomes the first element ... */
        pS->next = pHead; /* old pHead becomes 2nd in list ... */
        pHead = pS; /* and ... this pS ... becomes the head of the list */
    }
    else /* If here ... search the linked list for the right location ... */
    {
        /* Start comparing with element AFTER 'q' ... i.e. the 'next in' ... */
        while(q->next != NULL && studentCmp(q->next, pS) <= 0)
        {
            q = q->next; /* Traverse the list ... */
        }
        /*
            Ok, insert after 'q' by relinking the pointers (similar to above)
            ( Includes inserting at end position ... where q->next == NULL )
        */
        pS->next = q->next; /* Inserted 'pS' is linked to 'upstream element' */
        q->next = pS;  /* Now 'q' is updated to link to the new 'pS' element */
    }

}

void view( pStudent pS )
{
    printf( pS->dataLine ); /* string already has '\n' at end ... */
    fflush( stdout );
}

void showAll()
{
    pStudent p = pHead;     /* int c; */
    if( pHead == NULL )
    {
        puts("\nNo records in memory at present.") ;
        return;
    }

    /* If reach here ... */
    while( p != NULL )
    {
        view( p );
        p = p->next;
    }
}

int writeFile(char *name)
{
    FILE* fp;
    int count = 0; /* to track the records actually written to the file */
    pStudent p = pHead;
    if( p == NULL )
    {
        puts("\nNo records available ... so NO records written to file.") ;
        return 0;
    }
    
    fp = fopen( name, "w" );
    if( fp == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", name);
        flushStdin();
        return 0;
    }

    for( ; p != NULL; p = p->next )
    {
        fprintf( fp, "%s", p->dataLine ); /* Note: 'line' already has '\n' at end */
        ++count;
    }
    fclose( fp );
    return count; /* Number of records written. */
}

int readFile( char* name )
{
    int count = 0;
    pStudent pS;
    char buffer[MAXLEN+1];
    FILE* fp = fopen( name, "r" );
    if( fp  == NULL )
    {
        printf
        (
            "\nError opening file %s.\n"
            "Perhaps it hasn't been created yet?\n"
            "Press 'Enter' to continue ... ",
            name
        );
        flushStdin();
        return 0;
    }

    /* If the program reaches here ... */
    while(  fgets( buffer, MAXLEN+1, fp )  )
    {
        pS = (pStudent) malloc( sizeof(Student) );
        myAssert( (pS != NULL), "Error: malloc failed (2)" );
        pS->dataLine = newCopy( buffer );
        insert( pS );
        ++count;
    }
    fclose( fp );
    printf("%d records were read into memory from the file %s.\n", count, name);
    return count; /* Total number of student records found in the file. */
}

/* A function to compare two student records to permit sorting ... */
int studentCmp( pStudent pS1, pStudent pS2 )
{
    return strcmp( pS1->dataLine+sort_offset, pS2->dataLine+sort_offset );
}

void delAll()
{
    pStudent p = pHead; /* set p to this initial value to start loop */
    pStudent pNext;     /* to hold the pointer to the next record */
    for( ; p != NULL; p = pNext  )
    {
        pNext = p->next; /* get pointer to the next record */
        free( p->dataLine );
        free( p );
    }
    /* update globals ...  */
    pHead = NULL;
    numStudents = 0;
}

void myAssert( int condition, char message[] )
{
    if( !condition )
    {
        fputs( message, stderr );
        getchar();
        exit(1);
    }
}



As above, but using readLine instead of fgets ... so ... NO max line length (except as set by available memory)

Code: [Select]

/* mergeTwoFiles_readLine.c */ /* this version 2010-05-25 */

/*
    C demo of merging two files into a new sorted file ... using a linked-
    list ... by inserting lines, in sorted order, into the (growing) list.
    
    Note: using while( (line = readLine(fp)) ) to read each file line,
    so ... NO max line length ... (except as limited by available memory)
    
    http://developers-heaven.net/forum/index.php/topic,46.0.html
*/

#include "readLine.h" /* includes stdio.h, stdlib.h and myAssert */

#include <string.h> /* re. strcmp */

#define fName1 "info1.txt"
#define fName2 "info2.txt"
#define fName3 "merge.txt"

#define sort_offset 12 /* so files will be sorted by names ... */

/*
info1.txt

09876 year1 Smith Catee Rose
08765 year2 Clinton Hilary Claire
07654 year3 Barrack Richard Kenneth

info2.txt

08967 year1 Edison Bill
06789 year2 Bell Robert Ed

merge.txt

07654 year3 Barrack Richard Kenneth
06789 year2 Bell Robert Ed
08765 year2 Clinton Hilary Claire
08967 year1 Edison Bell
09876 year1 Smith Catee Rose
*/

typedef struct myStudent
{
    char* dataLine;
    struct myStudent* next;
} Student ;

typedef Student *pStudent;

/* using these two global variable to ease function calls ... */
pStudent pHead = NULL; /* Note: needs a NULL value to start inserts ... */
int numStudents = 0;

void insert( pStudent pS );
int readFile( char* fName );
int writeFile( char* fName );
int studentCmp( pStudent pS1, pStudent pS2 );
void view( pStudent pS );
void showAll();
void delAll();
void flushStdin();


int main() /* ********************* start of main *************************** */
{
    int num = readFile( fName1 );
    if( num )
        numStudents += num;

    num = readFile( fName2 );
    if( num )
        numStudents += num;

    //showAll();

    num = writeFile( fName3 );
    
    if( num == numStudents )
        printf
        (
            "All %d students were successfully sorted and merged in file %s.",
            num, fName3
        );
    else
        printf
        (
            "Error: writing to file %s  Note: wrote %d vs. numStudents of %d",
            fName3, num, numStudents
        );

    delAll();
    printf("\n\nPress 'Enter' to continue ... ");
    flushStdin();

    system( "notepad merge.txt" );
    return 0;
    
} /* ******************************* end of main **************************** */



void flushStdin()
{
    while( getchar()!='\n' ) ;
}


/* insert in list with last & first names in proper order */
void insert( pStudent pS )
{
    pStudent q = pHead; /* Get a working copy of pHead in q */
    
    /* Firstly, we handle the case where 'this' should be the first element. */
    if(pHead == NULL || studentCmp(pS, pHead) < 0)
    {
        /* So ... it now becomes the first element ... */
        pS->next = pHead; /* old pHead becomes 2nd in list ... */
        pHead = pS; /* and ... this pS ... becomes the head of the list */
    }
    else /* If here ... search the linked list for the right location ... */
    {
        /* Start comparing with element AFTER 'q' ... i.e. the 'next in' ... */
        while(q->next != NULL && studentCmp(q->next, pS) <= 0)
        {
            q = q->next; /* Traverse the list ... */
        }
        /*
            Ok, insert after 'q' by relinking the pointers (similar to above)
            ( Includes inserting at end position ... where q->next == NULL )
        */
        pS->next = q->next; /* Inserted 'pS' is linked to 'upstream element' */
        q->next = pS;  /* Now 'q' is updated to link to the new 'pS' element */
    }

}

void view( pStudent pS )
{
    puts( pS->dataLine );
    fflush( stdout );
}

void showAll()
{
    pStudent p = pHead;     /* int c; */
    if( pHead == NULL )
    {
        puts("\nNo records in memory at present.") ;
        return;
    }

    /* If reach here ... */
    while( p != NULL )
    {
        view( p );
        p = p->next;
    }
}

int writeFile(char *fName)
{
    FILE* fp;
    int count = 0; /* to track the records actually written to the file */
    pStudent p = pHead;
    if( p == NULL )
    {
        puts("\nNo records available ... so NO records written to file.") ;
        return 0;
    }
    
    fp = fopen( fName, "w" );
    if( fp == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", fName);
        flushStdin();
        return 0;
    }

    for( ; p != NULL; p = p->next )
    {
        fprintf( fp, "%s\n", p->dataLine );
        ++count;
    }
    fclose( fp );
    return count; /* Number of records written. */
}

int readFile( char* fName )
{
    int count = 0;
    pStudent pS;
    char* line;
    FILE* fp = fopen( fName, "r" );
    if( fp  == NULL )
    {
        printf
        (
            "\nError opening file %s.\n"
            "Perhaps it hasn't been created yet?\n"
            "Press 'Enter' to continue ... ",
            fName
        );
        flushStdin();
        return 0;
    }

    /* If the program reaches here ... */
    while(  (line = readLine(fp)) )
    {
        pS = (pStudent) malloc( sizeof(Student) );
        myAssert( (pS != NULL), "Error: malloc failed (2)" );
        pS->dataLine = line;
        insert( pS );
        ++count;
    }
    fclose( fp );
    printf("%d records were read into memory from the file %s.\n", count, fName);
    return count; /* Total number of student records found in the file. */
}

/* A function to compare two student records to permit sorting ... */
int studentCmp( pStudent pS1, pStudent pS2 )
{
    return strcmp( pS1->dataLine+sort_offset, pS2->dataLine+sort_offset );
}

void delAll()
{
    pStudent p = pHead; /* set p to this initial value to start loop */
    pStudent pNext;     /* to hold the pointer to the next record */
    for( ; p != NULL; p = pNext  )
    {
        pNext = p->next; /* get pointer to the next record */
        free( p->dataLine );
        free( p );
    }
    /* update globals ...  */
    pHead = NULL;
    numStudents = 0;
}



And here is a way to sort a file too large for memory ....
break it into 2 parts and sort each file using a merge sort and then merge the 2 sorted files

Code: [Select]

/* mergeTwoFiles_msortAndMerge.c */ /* this version 2010-05-25 */

/*
    C demo of merging two files into a new sorted file ...
    1st, read each file into a linked-list,
    2nd, then msort and write file back sorted to a new sorted file
    3rd, then merge the 2 sorted files, line by line, into a merge.txt file
    
    Note 1: using my ClistOfString.h and my readLine.h ... included below
    
    Note 2: using while( (line = readLine(fp)) ) to read each file line,
    so ... NO max line length ... (except as limited by available memory)
    
    http://developers-heaven.net/forum/index.php/topic,46.0.html
*/

/* set sort_offset to 12 here, so file lines will be sorted by name ... */
#define sort_offset 12 /* if sort_offset not defined here, default is 0 */

#include "ClistOfString.h" /* includes <string.h>, "readLine.h" that includes */
                           /* stdio.h, stdlib.h and myAssert */

#define fName1 "info1.txt"
#define fName2 "info2.txt"
#define fName3 "merge.txt"

/*
info1.txt

09876 year1 Smith Catee Rose
08765 year2 Clinton Hilary Claire
07654 year3 Barrack Richard Kenneth

info2.txt

08967 year1 Edison Bill
06789 year2 Bell Robert Ed

merge.txt

07654 year3 Barrack Richard Kenneth
06789 year2 Bell Robert Ed
08765 year2 Clinton Hilary Claire
08967 year1 Edison Bell
09876 year1 Smith Catee Rose
*/


void readFile( char*, Clist* );
int writeFile( char*, Clist* );
int mergeFiles( char*, char*, char* );


int main() /* ********************* start of main *************************** */
{
    int count1, count2, count3;
    Clist cl;
    init( &cl );

    readFile( fName1, &cl );
    //showAll( &cl );
    msort( &cl );
    count1 = writeFile( "sorted" fName1, &cl );
    if( count1 != cl.size )
        printf( "\nError: only %d of %d lines filed\n", count1, cl.size );
    freeAll( &cl );
    //system( "notepad sorted" fName1 );
    
    readFile( fName2, &cl );
    //showAll( &cl );
    msort( &cl );
    count2 = writeFile( "sorted" fName2, &cl );
    if( count2 != cl.size )
        printf( "\nError: only %d of %d lines filed\n", count2, cl.size );
    freeAll( &cl );
    //system( "notepad sorted" fName2 );
    
    count3 = mergeFiles( "sorted" fName1, "sorted" fName2, fName3 );
    if( count3 != count1+count2 )
        printf( "\nError: only %d of %d lines filed\n", count3, count1+count2);
    system( "notepad " fName3 );
    
    return 0;
    
} /* ******************************* end of main **************************** */


void readFile( char* fName, Clist* cl )
{
    List lst;
    FILE* fp = fopen( fName, "r" );
    if( fp  == NULL )
    {
        printf
        (
            "\nError opening file %s.\n"
            "Perhaps it hasn't been created yet?\n"
            "Press 'Enter' to continue ... ",
            fName
        );
        getchar();
        return;
    }

    /* If the program reaches here ... */
    while( (lst.line = readLine(fp)) )
    {
        push_back( cl, &lst );
    }
    fclose( fp );
    printf("%d records were read into memory from the file %s.\n", cl->size, fName);
}

int writeFile( char *fName, Clist* cl )
{
    FILE* fp;
    int count = 0; /* to track the records actually written to the file */
    pList pL;
    if( !cl->size )
    {
        puts("\nNo records available ... so NO records written to file.") ;
        return 0;
    }

    fp = fopen( fName, "w" );
    if( fp == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", fName);
        getchar();
        return 0;
    }

    for( pL = cl->start; pL != NULL; pL = pL->next )
    {
        fprintf( fp, "%s\n", pL->line );
        ++count;
    }
    fclose( fp );
    return count; /* Number of records written. */
}

int mergeFiles( char* a, char* b, char* c )
{
    FILE* f1, * f2, * f3;
    char* line1, * line2;
    int count = 0;

    f1 = fopen( a, "r" );
    if( f1 == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", a);
        getchar();
        return 0;
    }

    f2 = fopen( b, "r" );
    if( f2 == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", b);
        getchar();
        return 0;
    }
    
    f3 = fopen( c, "w" );
    if( f3 == NULL )
    {
        printf("\nError opening file %s.  Press 'Enter' to continue ... ", c);
        getchar();
        return 0;
    }
    
    line1 = readLine(f1);
    line2 = readLine(f2);
    while( line1 && line2 )
    {
        if( strcmp(line1+sort_offset, line2+sort_offset) <= 0 )
        {
            fprintf( f3, "%s\n", line1 );
            ++count;
            free( line1 );
            line1 = readLine(f1);
        }
        else
        {
            fprintf( f3, "%s\n", line2 );
            ++count;
            free( line2 );
            line2 = readLine(f2);
        }
    }
    
    /* test end conditions ... */
    if( line1 )
    {
        fprintf( f3, "%s\n", line1 );
        ++count;
        free( line1 );
        while( (line1 = readLine(f1)) )
        {
            fprintf( f3, "%s\n", line1 );
            ++count;
            free( line1 );
        }
    }
    else if( line2 )
    {
        fprintf( f3, "%s\n", line2 );
        ++count;
        free( line2 );
        while( (line2 = readLine(f2)) )
        {
            fprintf( f3, "%s\n", line2 );
            ++count;
            free( line2 );
        }
    }
    fclose(f3); fclose(f2); fclose(f1);
    return count;
}


The above program uses these next 2 files also:

ClistOfString.h and readLine.h  ... (that were suppled above, just before this program.)

[David]

Addendum:

Added here ... linked_list_ex5.cpp upgraded ... now as a C++ class

Code: [Select]

// linked_list_ex6.cpp // class MyStudentList //

// linked_list_ex5.cpp upgraded ... now as a C++ class

// this version  2010-07-26 //

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

class MyStudentList
{
public:
    // a friend function is used here for this overloaded operator <<
    friend ostream& operator<< ( ostream& fout, MyStudentList& obj )
    {
        if( obj.head == 0 )
            return fout << "The list is empty.\n";
        // else ...
        int i = 0;
        Node* pNext = obj.head;
        while( pNext )
        {
            fout << "Node[" << ++i << "] is holding "
                 << "id[" << pNext->id << "] and name "
                 << pNext->name << endl;
            pNext = pNext->next;
        }
        return fout;
    }

    // Default constructor ...
    MyStudentList()
    {
        head = tail = 0;
        size = 0;
    }
   
    // Destructor ...
    ~MyStudentList()
    {
        clear();
    }

    int get_size() { return size; }
   
    // methods ...
    void push_back( int new_id, string new_name )
    {
        Node* pNew = new Node;
        pNew->id = new_id;
        pNew->name = new_name;
        pNew->next = NULL;

        if( head != 0 )
        {
            tail->next = pNew;
            tail = pNew;
        }
        else
            head = tail = pNew;
        ++ size;
    }
   
    void push_front( int new_id, string new_name )
    {
        Node* pNew = new Node;
        pNew->id = new_id;
        pNew->name = new_name;
       
        pNew->next = head;
        head = pNew;

        if( tail == 0 )
            tail = pNew;
        ++ size;
    }

    void show()
    {
        if( head == 0 )
        {
            cout << "The list is empty.\n";
            return;
        }

        int i = 0;
        Node* pNext = head;
        while( pNext )
        {
            cout << "Node[" << ++i << "] is holding "
                 << "ID[" << pNext->id << "] "
                 << pNext->name << endl;
            pNext = pNext->next;
        }
    }

    void clear()
    {
        Node* pNext = head;
        while( pNext )
        {
            Node* copy  = pNext;
            pNext = pNext->next;
            delete( copy );
        }
        head = tail = 0;
        size = 0;
    }

private:
    struct Node
    {
        int id;
        string name;
        Node *next;
    };
    Node* head;
    Node* tail;
    int size;
};



int main()
{
    // get some 'name' data ...
    const string names[] = { "Susan", "Sarah", "Joe" };
    const int num_names = sizeof names / sizeof names[0] ;
   
    // construct an empty list ...
    MyStudentList myList;
   
    int id ;
    cout << "After push_back loop ... \n";
    for( id = 0; id < num_names; ++id )
        myList.push_back( id+1, names[id] );

    myList.show();
    cout << "The list size is " << myList.get_size() << endl;


    cout << "\nAfter push_back of visitor ... \n";
    // note id has value num_names now ... at end of above loop
    myList.push_back( ++id, "Guest visitor" );
    // using OVERLOADED <<
    cout << myList;
    cout << "The list size is " << myList.get_size() << endl;

    cout << "\nAfter myList.clear() ... \n";
    myList.clear();
    cout << myList;
    cout << "The list size is " << myList.get_size() << endl;

    cout << "\nAfter push_front loop ... and push_front visitor ...\n";

    for( id = 0; id < num_names; ++id )
        myList.push_front( id+1, names[id] );
    myList.push_front( ++id, "Guest visitor" );
    cout << myList; // using overloaded <<
    cout << "The list size is " << myList.get_size() << endl;
   
   
    cout << "\nPress 'Enter' to continue ... " << flush;
    cin.get();
}


[David]

And ...a vector like container class ... bottom up ... (Note: you may like to move the struct into the class as a private data member ... to better 'hide' all the raw data from a user of this class ... or to make the struct into a class with protected data members, public functions/methods and let classBook inherit class Contact)

Code: [Select]

// aryPointersToStruct.cpp

// class Book ...
// a vector like dynamic array of pointers to
// struct Contacts

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cctype> // re. tolower ...
#include <cstdlib> // re. qsort array ...
using namespace std;

const char FILE_NAME[] = "Contacts2010.txt";
const int ARY_SIZE = 2; // starting array capacity ...

struct Contacts
{
   string name;
   int area;
   int phone;
};
// to print a contact...
ostream& operator<< ( ostream& os, const Contacts& c )
{
    return os << setw(20) << left << c.name+"," << right
              << " (" << c.area << ") "
              << c.phone/10000 << "-"
              << c.phone%10000;
}

int compareContactsNameIgnoreCase( const void*, const void* );
int compareContacts ( const void*, const void* );

string toCaps( const string& s )
{
    string new_s = s;
    for( int i = s.size()-1; i>= 0; --i )
        new_s[i] = toupper(new_s[i]);
    return new_s;
}


class Book
{
public:
    friend ostream& operator<< ( ostream& os, const Book& b );
    // default constructor ...
    Book() : size(0), capacity(ARY_SIZE)
    {
        ary = new Contacts[capacity];
    }
    // destructor ...
    ~Book()
    {
        delete [] ary;
        size = capacity = 0;
    }
    void enlarge();
    void reserve( int n_cap );
    void takeIn();
    void read();
    void write();
    void edit();
    void del( int index );
    void sortBook();
    void find();
    int get_size() { return size;}
    int get_capacity() { return capacity;}
private:
    Contacts* ary; // ary of pointers to struct Contacts
    int size;
    int capacity;
};

ostream& operator<< ( ostream& os, const Book& b )
{
    for( int i = 0; i < b.size; ++ i )
        os << setw(3)<< i+1 << ": "<< b.ary[i] << endl;
    os << "ary size = " << b.size
       << " and capacity = " << b.capacity << endl;

    return os;
}

void Book::enlarge()
{
    capacity += capacity;
    Contacts* n_ary = new Contacts[capacity];
    for( int i = 0; i < size; ++i )
    {
         n_ary[i].name = ary[i].name;
         n_ary[i].area = ary[i].area;
         n_ary[i].phone = ary[i].phone;
    }
    delete [] ary;
    ary = n_ary;
}

void Book::reserve( int n_cap )
{
     if( n_cap > capacity)
     {
         capacity = (n_cap+1)/2;
         enlarge();
     }
}

void Book::takeIn()
{
    cout << "Enter a blank line to exit ...\n";
    string line, prompt = "Enter name, area phone : ";
    while( cout<<prompt<<flush && getline( cin, line ) && line.size() )
    {
        if( line.find(',') == string::npos )
        {
            cout << "You forgot the 'comma' after the name field ...\n";
            continue;
        }
       
        if( size == capacity )
            enlarge();

        istringstream iss( line );
        getline( iss, ary[size].name, ',' );
        iss >> ary[size].area >> ary[size].phone;
        cout << "You entered " << ary[size].name << " ("
             << ary[size].area << ") "
             << ary[size].phone/10000 << "-"
             << ary[size].phone%10000
             << " Ok (y/n) ? " << flush;
        string reply(1,' ');
getline( cin, reply );
        if( reply[0] == 'y' || reply[0] == 'Y' )
            ++ size;
        else cout << "Try entry again ...\n";
    }
}

void Book::read()
{
     if( size > 0 )
     {
         for( ;; )
         {
             cout << "Exit or Add or Overwrite " << size
                  << " contacts already in memory (e/a/o) ? "
                  << flush;
             string reply( 1, ' ' );
             getline( cin, reply );
             if( reply[0] == 'e' || reply[0] == 'E' ) return;
             if( reply[0] == 'a' || reply[0] == 'A' ) break;
             if( reply[0] == 'o' || reply[0] == 'O' ) { size = 0; break; }
             // else ...
             cout << "Try entry again ...\n";
         }
     }
     
     ifstream fin( FILE_NAME );
     string line;
     while( getline( fin, line ) )
     {
         if( size == capacity ) enlarge();
         istringstream iss( line );
         getline( iss, ary[size].name, ',' );
         iss >> ary[size].area >> ary[size++].phone;
     }
     fin.close();
     cout << size << " contacts were read from file ...\n";
}

void Book::write()
{
    ofstream fout( FILE_NAME );
    if( ! fout )
    {
        cout << "Error: opening file "
             << FILE_NAME << " to write.\n";
        return;
    }
    cout << "File '" << FILE_NAME << "' already exists ...\n"
         << "Are sure you want to overwite this file (y/n) ? "
         << flush;
    string reply( 1, ' ' );
    getline( cin, reply );
    if( reply[0] != 'y' && reply[0] != 'Y' )
    {
        cout << "Overwrite aborted ...\n";
        fout.close();
        return;
    }

    int i;
    for( i = 0; i < size; ++i )
    {
        fout << ary[i].name << ", "
             << ary[i].area << " "
             << ary[i].phone << endl;
    }
    fout.close();
    cout << i << " contacts were written to file.\n";
}

void Book::edit()
{
    int i; // index to edit ...
    for( ;; )
    {
        cout << "Contact number to edit (0 to exit): " << flush;
        string line;
        getline( cin, line );
        istringstream iss( line );
        iss >> i;
        if( i == 0 ) return;
        if( --i >= 0 && i < size )
        {
            cout << ary[i] << endl;
            cout << "Abort, Delete or Edit (a/d/e) ? " << flush;
            string reply( 1, ' ' );
            getline( cin, reply );
            if( reply[0] == 'a' || reply[0] == 'A' ) return;
            if( reply[0] == 'd' || reply[0] == 'D' ) { del( i ); return; }
            if( reply[0] == 'e' || reply[0] == 'E' ) break;
            else cout << "Invalid entry.  Enter one of (a/d/e) ...\n";
        }
        else if( size > 0 )
             cout << "Outside valid range 1.."
                  << size << endl;
        else cout << "No contacts in memory to edit or erase ...\n";
    }
    // ok so can edit now ...
    string line, prompt = "Enter name, area phone : ";
    while( cout << prompt && getline( cin, line ) && line.size() )
    {
        if( line.find(',') == string::npos )
        {
            cout << "You forgot the 'comma' after the name field ...\n";
            continue;
        }
       
        string n_name;
        int n_area, n_phone;
        istringstream iss( line );
        getline( iss, n_name, ',' );
        iss >> n_area >> n_phone;
        cout << "You entered " << n_name << " ("
             << n_area << ") "
             << n_phone/10000 << "-"
             << n_phone%10000
             << " Ok (a/y/n) ? " << flush;
        string reply(1,' ');
        getline( cin, reply );
        if( reply[0] == 'y' || reply[0] == 'Y' )
        {
            ary[i].name = n_name;
            ary[i].area = n_area;
            ary[i].phone = n_phone;
            return;
        }
        else if( reply[0] == 'a' || reply[0] == 'A' )
        {
             cout << "Edit aborted ...\n";
             return;
        }
        else cout << "Try entry again ...\n";
    }
}

void Book::del( int index )
{

    for( int i = index; i < size-1; ++ i )
    {
        ary[i].name = ary[i+1].name;
        ary[i].area = ary[i+1].area;
        ary[i].phone = ary[i+1].phone;
    }
    -- size;
}

void Book::sortBook()
{
    cout << "Ignore case (y/n ) ? " << flush;
    string reply( 1, ' ' );
    getline( cin, reply );
    if( reply[0] == 'y' || reply[0] == 'Y' )
    {
        qsort(ary, size, sizeof(Contacts), compareContactsNameIgnoreCase);
        cout << "Sorted with case ignored ...\n";
    }
    else
    {
        qsort(ary, size, sizeof(Contacts), compareContacts);
        cout << "Sorted with case considered ...\n";
    }
}

void Book::find()
{
    int i; // index to edit ...
    for( ;; )
    {
        startAgain:
        cout << "Contact name to find (empty line to exit): " << flush;
        string line;
        getline( cin, line );
        if( !line.size() ) break;
        for( int j = 0; j < size; ++ j )
        {
            if( ary[j].name == line )
            {
                cout << "Found at position "
                     << j+1 << ": "<< ary[j] << endl;
                goto startAgain;
            }
        }
        // else ...
        cout << "Not found ...\n";
        for( int j = 0; j < size; ++ j )
        {
            if( toCaps(ary[j].name).find(toCaps(line)) != string::npos )
            {
                cout << "but found in .. "
                     << j+1 << ": "<< ary[j] << endl;
            }
        }
    }
}


const string MENU = "1. (T)ake in new contacts from keyboard\n"
                    "2. show (A)ll contacts in array memory\n"
                    "3. (R)ead in all contacts in file\n"
                    "4. (W)rite all contacts to file\n"
                    "5. (E)dit/(E)rase a contact\n"
                    "6. (S)ort contacts\n"
                    "7. (F)ind contact\n"
                    "8. e(X)it\n"
                    "Enter your choice (1..8) : ";

int main()/////////////////////////////////////////////////
{
    Book myBlackBook;

    // testing size and capacity ...
    cout << "ary size = " << myBlackBook.get_size()
         << " and capacity = " << myBlackBook.get_capacity()
         << endl;
/*
    myBlackBook.reserve( 200 );
    cout << "size = " << myBlackBook.get_size()
         << " capacity = " << myBlackBook.get_capacity()
         << endl;
*/
    myBlackBook.read();

    int choice;
    do
    {
        cout << myBlackBook << endl;
        cout << MENU << flush;
        choice = cin.get();
        cin.sync();
        switch( choice )
        {
            case '1': case 't': case 'T' : myBlackBook.takeIn(); break;
            case '2': case 'a': case 'A' : /*cout << myBlackBook;*/ break;
            case '3': case 'r': case 'R' : myBlackBook.read(); break;
            case '4': case 'w': case 'W' : myBlackBook.write(); break;
            case '5': case 'e': case 'E' : myBlackBook.edit(); break;
            case '6': case 's': case 'S' : myBlackBook.sortBook(); break;
            case '7': case 'f': case 'F' : myBlackBook.find(); break;
            case '8': case 'x': case 'X' : choice = '8'; break;
            default  : cout << "Not implemented yet ...\n";
        }
    }
    while( choice != '8' );
}//////////////////////////////////////////////////////////


int compareContactsNameIgnoreCase( const void* s1, const void* s2 )
{
    Contacts* c1 = (Contacts*) s1;
    Contacts* c2 = (Contacts*) s2;
    int i = 0;
    while( i != c1->name.size() && i != c2->name.size()  )
    {
        if( tolower(c1->name[i]) != tolower(c2->name[i]) )
            break;
        ++i;
    }
    /* now test end conditions .... */
    if( i == c1->name.size() && i == c2->name.size() )
    {
        if( c1->area == c2->area ) return c1->phone - c2->phone;
        else return c1->area - c2->area;
    }
    else if( i < c1->name.size() && i < c2->name.size() )
         return tolower(c1->name[i]) - tolower(c2->name[i]);
    else if( i < c2->name.size() ) return -1;
    else return 1;
}

int compareContacts ( const void* s1, const void* s2 )
{
     Contacts* c1 = (Contacts*) s1;
     Contacts* c2 = (Contacts*) s2;
     if( c1->name == c2->name )
     {
         if( c1->area == c2->area )
         {
             return c1->phone - c2->phone;
         }
         else return c1->area - c2->area;;

     }
     else if (c1->name < c2->name) return -1;
     else return 1;
}


[David]

A start of a Money class ... with change ...

Code: [Select]

// classMoney.cpp // this revision 2010-09-12 //

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

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class Money
{
public:
    friend ostream& operator << ( ostream&, const Money& );
    friend Money operator + ( const Money&, const Money& );
    friend Money operator %( double, const Money & ); // get percent ...
    Money() : cents(0) {} // default constructor ...
    Money( int cnts ) : cents( cnts ) {}
    Money (double dols ) : cents( int( (dols+.005)*100 )) {}
    int get_cents() { return cents; }
    void show_change();
private:
    int cents; // input in main restricts to 9 digits for cents (7 for dollars)
    // Note: you could upgrade here to a long long for (total) cents ...
    // if 7 digits is not enough for dollars ...
};

ostream& operator << ( ostream& out, const Money& m )
{   // convert to string ...
    ostringstream oss;
    oss << m.cents;
    string sm = oss.str();
    // and format ...
    if( sm.size() > 2 ) sm.insert( sm.size()-2, "." );
    else if( sm.size() == 2 ) sm = "0." + sm;
    else sm = "0.0" + sm;
    return out << sm;
}

Money operator + ( const Money& a, const Money& b )
{
    Money c;
    c.cents = a.cents + b.cents;
    return c;
}

Money operator %( double pc, const Money& m) // get percent ...
{
    Money c;
    c.cents =  int(( m.cents)* pc/100.0 + 0.5 );
    return c;
}

void Money::show_change()
{
    int cents_remaining = cents;

    int dols = cents_remaining / 100;
    cents_remaining -= dols*100;

    int qrts = cents_remaining / 25;
    cents_remaining -= qrts*25;

    int dimes = cents_remaining / 10;
    cents_remaining -= dimes*10;

    int nickles = cents_remaining / 5;
    cents_remaining -= nickles*5;

    cout << "change is ..."
         << "\ndollars  : " << dols
         << "\nquarters : " << qrts
         << "\ndimes    : " << dimes
         << "\nnickles  : " << nickles
         << "\npennies  : " << cents_remaining << endl;
}


// used by main ...

bool more();/* defaults to 'true'/'yes' ... unless 'n' or 'N' entered ... */
bool isValidInt( const string& s );
bool getInput( const string& prompt, int& cents );



int main() /////////////////////////////////////////////////////////////////////
{
    cout << "Money(1.235)  +  Money(99.7249)  = "
         << Money(1.235) << " + " <<  Money(99.72) << " = "
         << Money(1.235) + Money(99.72) << endl << endl;
         
    cout << "13 % Money(20.255) = "
         << .13 << " * " <<  Money(20.255) << " = "
         << 13 % Money(20.255) << endl << endl;

    do
    {
        vector< Money > mv;
        do
        {
            int cents;
            if( !getInput( "Enter amount: ", cents )) continue;
            mv.push_back( Money( cents ));
        }
        while( more() );

        Money sum;
        cout << "The sum of\n";
        for( int i = mv.size()-1; i >= 0; --i )
        {
            cout << setw(10) << mv[i] << endl;
            sum = sum + mv[i];
        }
        cout << "==========\n"
             << setw(10) << sum << endl;
           

        cout << "Or " << sum.get_cents() << " all in cents.\n";
       
        Money HST = 13.0 % sum;
        cout << "The new Ontario HST is " << setw(10) << HST << endl
             << "and the new total is   " << setw(10) << sum + HST << endl
             << "or in ";
        (HST+sum).show_change();
       
        /* make sure cin stream is 'empty' before calling 'more()' ... */
    }
    while( more() );
} //////////////////////////////////////////////////////////////////////////////



bool more()/* defaults to 'true'/'yes' ... unless 'n' or 'N' entered ... */
{
    cout << "More (y/n) ? " << flush;
    int reply = cin.get();
    cin.sync(); /* 'flush' cin stream  ...  */
    if( reply == 'n' || reply == 'N' ) return false;
    /* else ... */
    return true;
}

bool isValidInt( const string& s )
{
    for( int i = s.size()-1; i >= 0; --i )
        if( s[i] < '0' || s[i] > '9' ) return false;
    return true;
}

bool getInput( const string& prompt, int& cents )
{
    cout << prompt << flush;
    string testStr;
    getline( cin, testStr );

    // see if test string entered above has a decimal point ...
    size_t i;
    if( (i = testStr.find('.')) != string::npos ) // it has a decimal point
    {
        string cnts = testStr.substr( i+1 );
        if( !isValidInt( cnts ) ) // validate cents part ...
        {
            cout << cnts << " is not an integer cents amount...\n";
            return false;
        }
        // else ...
        if( cnts.size() < 2 ) cnts += "0";

        istringstream iss_c( cnts.substr( 0, 2) );
        iss_c >> cents;
        if( cnts.size() > 2 && cnts[2] >= '5' ) ++ cents;

        // now handle any dollars ... but validate first ...

        testStr.erase( i ); // only dollars  remain now ... if any ?
        if( testStr == "" ) testStr = "0";
        // limit is here set to total of 9 digits for cents ...
        if( !isValidInt( testStr ) || testStr.size() > 7 )
        {
            cout << testStr << " is not a valid dollar amount here ...\n";
            return false;
        }
        // else ...
        istringstream iss_d( testStr );
        int dlrs;
        if( iss_d >> dlrs )  cents += dlrs * 100;
        else { cout << iss_d << " invalid dollar amount ...\n"; return false; }
    }
    else // NO decimal point in test string entered ... so ... validate if int
    {   // limit is here set to total of 9 digits for cents ...
        if( !isValidInt( testStr ) || testStr.size() > 7 )
        {
            cout << testStr << " is not a valid dollar amount here ...\n";
            return false;
        }
        // else ...
        istringstream iss_d( testStr );
        int dlrs;
        if( iss_d >> dlrs )  cents = dlrs * 100;
        else { cout << testStr << " invalid dollar amount ...\n"; return false; }
    }
    return true;
}