/* 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 */
}
/* 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'" );
}
/* 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'" );
}
/* 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'" );
}
/* 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 * * * * * * * * * * * * * * * */
/* 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
/* "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
/* 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