Desktop Programming > C/C++ & Visual C++
ClistOfInt.h, ClistOfString.h, Clist.h, Clist_func's.h (with FUNCTION POINTERS)
David:
Update:
you can contact me via this link ...
https://sites.google.com/site/andeveryeyeshallseehim/
(my/editor gmail link is on the 2nd page)
These next few pages are an attempt to create a mini-library of helper files to add to C ... Clist and Cvec ... C emulations of the C++ STL list and vector containers ...
This 'library' for Clist, NOW has Clist_func's.h, that uses function pointers, to facilitate reuse. Just pass in your own compare functions for sorts, searches, etc. ... of any struct you desire ...
You will also find there ... example programs ... similar to the Cvec programs below, that demonstrate using these new Clist files ... some that use function pointers (and some that don't) ...
Note: Clist is the C list container that parallels the Cvec container ... so you will want to see these parallel Cvec examples for instructions that will help you to use these Clist files ...
The Cvec library is available here ... (also example programs)
http://developers-heaven.net/forum/index.php/topic,2580.0.html
A link to a program that uses split.h ... (Note: split.h uses ListOfString.h that includes readLine.h and List.h)
http://developers-heaven.net/forum/index.php/topic,466.msg676.html#msg676
Note: when you have exhausted these following pages, you may like to see the latest versions of Cvec and Clist in files Cvec2.h and Clist2.h at the following link:
http://developers-heaven.net/forum/index.php?topic=2598.0
David:
Here is the core file, Clist.h.
Before you load this file, you will need to ....
typedef a struct ... List
for example:
typedef struct myListOfStr
{
char* str;
struct myListOfStr* next;
} Node ;
and ...
typedef Node* pNode;
and define a function ...
void clearNode( pNode p ) { /* your code to free any dynamic memory goes here */ ; }
for example:
void clearNode( pNode p )
{
free( p->str );
}
Also, you will need the function myAssert that is available in readLine.h or readWord.h
Also, you will need stdio.h, stdlib.h and string.h ... which are all included by including either readLine.h or readWord.h
(For readLine.h and readWord.h, see next link) ...
http://developers-heaven.net/forum/index.php/topic,2580.msg2864.html#msg2864
--- Code: ---/* Clist.h */ /* 2016-10-07 */
/*
BEFORE loading ... you MUST FIRST typedef (struct) Node and pNode
i.e. typedef a struct/node/element/record as Node and typedef Node* pNode;
... and ... define clearNode( pNode p ); ... see example at end
*/
#ifndef dwClist_H
#define dwClist_H
/* #include <stdlib.h> // re. realloc */
/* #include <string.h> // re. memcopy */
typedef struct myClist
{
pNode start;
pNode end;
int size;
int isSorted;
} Clist;
/* with these, an address is passed, so NO copy made and/or
original updated */
void initClist( Clist* ); /* set start&end to NULL, size to 0, isSorted to 1 */
void push_frontClist( Clist*, pNode );
void push_backClist( Clist*, pNode );
void clearClist( Clist* );
/* void showClist( Clist* ); */
void initClist( Clist* list )
{
list->start = list->end = NULL;
list->size = 0;
list->isSorted = 1;
}
void push_frontClist( Clist* list, pNode d )
{
pNode p = (pNode) malloc( sizeof(Node) );
if( p == NULL )
{
clearClist( list );
myAssert( 0, "Error: malloc failed ...." );
}
/* now add in ALL new dat ... (assuming 'next pointer' is last in struct) */
memcpy( p, d, sizeof(Node)-sizeof(pNode) ); /* -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_backClist( Clist* list, pNode d )
{
pNode p = (pNode) malloc( sizeof(Node) );
if( p == NULL )
{
clearClist( list );
myAssert( 0, "Error: malloc failed ..." );
}
/* now add in ALL new dat ... (assuming next pointer is last of dat) */
memcpy( p, d, sizeof(Node)-sizeof(pNode) ); /* -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 clearClist( Clist* list )
{
/* printf( "\nFreeing list->size of %d ... \n", list->size ); */
if( list->size > 0 )
{
pNode cur = list->start;
for( ; cur != NULL; cur = list->start )
{
list->start = cur->next;
clearNode( cur );
free( cur );
}
initClist( list );
}
}
/*
void showClist( Clist* list )
{
if( list->size )
{
pNode p = list->start;
for( ; p != NULL; p = p->next )
showNode( p );
printf( "Node size = %d\n", list->size );
}
else puts( "The list is empty ... " );
}
*/
#endif
#if 0 /* *************************************************************** */
/* before we can include the Clist.h file below, we first need these ... */
#include <stdlib.h> /* re. alloc, exit */
#include <string.h> /* re. memcpy */
typedef struct ClistOfInt
{
int val;
struct ClistOfInt* next;
} Node ; /* i.e. ... a node/element/record in the list ... */
typedef Node* pNode;
void clearNode( pNode p )
{
/* no dynamic Cstrings, etc... to free here ... */
}
/*
void showNode( pNode p )
{
printf( "%d ", p->val );
}
*/
#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
/* Ok ... NOW can include ... */
#include "Clist.h"
/* needs stdlib.h, string.h and myAssert & all included above */
#endif /* ************************************************************* */
--- End code ---
David:
These next two files, ClistOfInt.h and ClistOfString.h, will each also load in the file Clist.h above ...
Note that ClistOfString.h also loads in readLine.h and Clist.h
(Each of ClistOfInt.h and ClistOfString.h, will also include: stdio.h, stdlib.h, string.h, myAssert ...
Note that ClistOfString.h first includes readLine.h which now also defines the function newCopy, to makes a new copy of a C string in new dynamic memory.)
Firstly, ClistOfInt.h
--- Code: ---/* ClistOfInt.h */ /* this version: 2016-10-07 */
/*
this version with added isortClist and insert_sortedClist (still has msort)
also added isSorted, unique, isUnique, sumClist, findClist, eraseClist
*/
#ifndef dwClistOfInt_H
#define dwClistOfInt_H
/* before we can include the Clist.h file below, we first need these ... */
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* re. memcpy */
#ifndef myType
#define myType int
#endif
typedef struct ClistOfInt
{
myType val;
struct ClistOfInt* next;
} Node ; /* i.e. ... a node/element/record in the list ... */
typedef Node* pNode;
void clearNode( pNode p )
{
/* no dynamic Cstrings, etc... to free here ... */
p = p; /* to keer warning message surpressed */
}
/*
void showNode( pNode p )
{
printf( "%d ", p->val );
}
*/
#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
/* Ok ... NOW can include ... */
#include "Clist.h"
/* needs stdio.h, stdlib.h, string.h and myAssert & all included above */
/* and now can add these functions to ClistOfInt...*/
void msortClist( Clist* );
void mergesort( Clist* );
pNode mergeClist( Clist*, Clist* );
void update_end( Clist* );
void insert_sortedClist( Clist*, pNode );
void isortClist( Clist* );
int isSortedClist( Clist* );
void uniqueClist( Clist* );
int isUniqueClist( Clist* );
myType sumClist( Clist* );
pNode findClist( Clist*, myType ); /* returns pointer to list with int value, or NULL */
void eraseClist( Clist* cl, pNode p );
/* a recursive mergesort ... */
void mergesort(Clist* list)
{
pNode 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 = mergeClist(&a, &b);
}
/* merge two sorted Clists with heads 'a' and 'b' ... in sorted order */
pNode mergeClist(Clist* a, Clist* b )
{
pNode sorted, new_merged_head;
if( a->start == NULL ) return b->start;
if( b->start == NULL ) return a->start;
if( a->start->val - b->start->val <= 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( a->start->val - b->start->val <= 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 )
{
pNode cur;
for( cur = list->start; cur->next != NULL; cur = cur->next ) ;
list->end = cur;
list->end->next = NULL;
}
}
void msortClist( Clist* c )
{
mergesort( c );
update_end( c );
c->isSorted = 1;
}
int isSortedClist( Clist* c )
{
pNode p = c->start;
for( ; p != NULL && p->next != NULL; p = p->next )
if( p->next->val < p->val ) return 0;
return 1;
}
void uniqueClist( Clist* c )
{
pNode p;
if( !c->isSorted ) msortClist( c );
p = c->start;
while( p->next != NULL )
{
if( p->val == p->next->val )
{
pNode tmp = p->next;
p->next = p->next->next;
free( tmp );
-- c->size;
}
else p = p->next;
}
update_end( c ) ; /* update end ... */
}
int isUniqueClist( Clist* cl )
{
pNode p = cl->start;
if( cl->size < 2 ) return 1;
if( !cl->isSorted ) msortClist( cl );
for( ; p->next != NULL; p = p->next )
{
if( p->val == p->next->val ) return 0;
}
/* else */
return 1;
}
myType sumClist( Clist* cl )
{
myType sum = 0;
pNode p;
for( p = cl->start; p != NULL; p = p->next ) sum += p->val;
return sum;
}
pNode findClist( Clist* cl, myType value )
{
pNode p;
for( p = cl->start; p != NULL; p = p->next )
if( p->val == value ) return p;
/* else if reach here ... */
return NULL;
}
void eraseClist( Clist* cl, pNode p )
{
if( cl->size )
{
pNode cur = cl->start;
pNode prev = NULL;
for( ; cur!= NULL && cur != p; cur = cur->next ) /* advance to p or end */
prev = cur;
if( cur == NULL ) { puts( "ERROR! pNode NOT found in Clist." ); return; }
/* else ... */
if( prev != NULL ) prev->next = cur->next;
if( cur == cl->start ) cl->start = cur->next;
if( cur == cl->end ) cl->end = prev;
free( cur );
-- cl->size; /* ...and update size */
}
else puts( "Clist is empty ..." );
}
/* pass in the address of the Clist and the new Node to insert ... */
void insert_sortedClist( Clist* list, pNode n )
{
pNode head;
if( !list->isSorted ) msortClist( list );
head = list->start;
/* firstly, we handle most common case where 'n' is NOT the first Node */
if( head != NULL && n->val >= head->val ) /* NEED >= */
{
/* so search the linked list for the right location */
pNode cur = head;
while( cur->next != NULL && cur->next->val <= n->val )
{
cur = cur->next;
}
if( cur == list->end ) list->end = n;
n->next = cur->next;
cur->next = n;
/* list->start = 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->start = n;
++ list->size;
if( list->size == 1 ) list->end = n;
}
}
void isortClist( Clist* list )
{
pNode cur,
nextNode;
Clist nClist;
initClist( &nClist );
for( cur = list->start; 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->start = nClist.start;
list->end = nClist.end;
list->isSorted = 1;
/* size hasn't changed ... */
}
#endif
--- End code ---
David:
Here is a link to readLine.h which is needed by the following ClistOfString.h ...
http://developers-heaven.net/forum/index.php/topic,2580.msg2864.html#msg2864
Note: readWord.h is also available at the above link.
David:
Now ... ClistOfString.h ... to supply most all you need to easily handle lists of dynamic C strings
--- Code: ---/* ClistOfString.h */ /* 2016-10-07 */
/* version @ 2015-12-17 has added: char* pop_frontClist( Clist* cl ); */
/*
this version with added isortClist and insert_sortedClist (still has msort)
isSorted, unique, isUnique, joinClist, showClist, findClist, eraseClist
*/
#ifndef dwClistOfString_H
#define dwClistOfString_H
/* using readLine here instead of gets and fgets ... readLine.h also includes */
#include "readLine.h" /* ... stdio.h, stdlib.h, string.h, myAssert, newCopy */
#ifndef sort_offset
#define sort_offset 0
#endif
typedef struct ClistOfString
{
char* str; /* since CStrings are '\0' terminated ... can get strlen */
struct ClistOfString* next;
} Node ; /* i.e. ... a node/element/record in the list ... */
typedef Node* pNode;
void clearNode( pNode p )
{
free( p->str );
}
/* Ok ... NOW can include ... */
#include "Clist.h"
/* needs stdlib.h, string.h and myAssert & all included above */
void showNode( pNode p )
{
printf( "%s ", p->str );
}
/* and these ...*/
void msortClist( Clist* );
void mergesortClist( Clist* );
pNode mergeClist( Clist*, Clist* );
void update_end( Clist* );
void insert_sortedClist( Clist*, pNode );
void isortClist( Clist* );
int isSortedClist( Clist* );
void uniqueClist( Clist* );
int isUniqueClist( Clist* );
char* joinClist( Clist*, const char* );
void showClist( const Clist* );
pNode findClist( Clist*, const char* findStr );
void eraseClist( Clist*, pNode );
char* pop_frontClist( Clist* cl );
/* a recursive mergesortClist ... */
void mergesortClist(Clist* list)
{
pNode 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 ... */
mergesortClist(&a);
mergesortClist(&b);
/* mergeClist the two sorted Clists together ... */
list->start = mergeClist(&a, &b);
}
/* mergeClist two sorted Clists with heads 'a' and 'b' ... in sorted order */
pNode mergeClist(Clist* a, Clist* b )
{
pNode sorted, new_merged_head;
if( a->start == NULL ) return b->start;
if( b->start == NULL ) return a->start;
if( strcmp(a->start->str + sort_offset, b->start->str + 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->str + sort_offset, b->start->str + 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 )
{
pNode cur;
for( cur = list->start; cur->next != NULL; cur = cur->next ) ;
list->end = cur;
list->end->next = NULL;
}
}
void msortClist( Clist* clst )
{
mergesortClist( clst );
update_end( clst );
clst->isSorted = 1;
}
int isSortedClist( Clist* c )
{
pNode p = c->start;
for( ; p != NULL && p->next != NULL; p = p->next )
if( strcmp(p->next->str, p->str) < 0 ) return 0;
return 1;
}
void uniqueClist( Clist* c )
{
pNode p;
int oldSize = c->size;
if( !c->isSorted ) msortClist( c );
p = c->start;
while( p->next != NULL )
{
if( strcmp(p->str + sort_offset, p->next->str + sort_offset) == 0 )
{
pNode tmp = p->next;
p->next = p->next->next;
clearNode( tmp ); /* needed here for types like dynamic Cstrings, etc */
free( tmp );
-- c->size;
}
else p = p->next;
}
if( c->size < oldSize ) update_end( c ) ; /* update end ... */
}
int isUniqueClist( Clist* cl )
{
pNode p = cl->start;
if( cl->size < 2 ) return 1;
if( !cl->isSorted ) msortClist( cl );
for( ; p->next != NULL; p = p->next )
{
if( strcmp( p->str, p->next->str ) == 0 ) return 0;
}
/* else */
return 1;
}
char* joinClist( Clist* cl, const char* s )
{
char* concatStr;
int sumsize = 0;
int add = strlen( s );
pNode p;
for( p = cl->start; p != NULL; p = p->next ) sumsize += strlen(p->str) + add;
concatStr = (char*) malloc( sumsize-add+1 );
myAssert( (concatStr != NULL), "Error, malloc failed to allocate memory for concatStr" );
concatStr[0] = 0;
for( p = cl->start; p != NULL; p = p->next )
{
strcat( concatStr, p->str );
if( p->next != NULL ) strcat( concatStr, s );
}
return concatStr;
}
void showClist( const Clist* cl )
{
pNode p = cl->start;
for( ; p != NULL; p = p->next ) showNode( p ); /*printf( "%s ", p->str ); */
}
/* returns pointer if present, else returns NULL */
pNode findClist( Clist* cl, const char* findStr )
{
pNode p;
for( p = cl->start; p != NULL; p = p->next )
if( strcmp(p->str, findStr) == 0 ) return p;
/* else if reach here ... */
return NULL;
}
void eraseClist( Clist* cl, pNode p ) /* if p valid, erase element there */
{
pNode prev = NULL, cur = cl->start;
for( ; cur != NULL && cur != p; cur = cur->next ) prev = cur;
if( cur == NULL )
{ puts( "\neraseClist ERROR! Pointer NOT found ..."); return; }
if( prev != NULL ) prev->next = cur->next; /* case of NOT FIRST element*/
else cl->start = cl->start->next; /* case of IS FIRST element*/
if( cur == cl->end ) cl->end = prev; /* case of IS LAST element*/
clearNode( cur ); /* needed here for types like dynamic C strings, etc */
free( cur ); /* free memory for dynamic Node ... */
/* now update size and return (by reference, since address passed in) */
-- cl->size;
}
char* pop_frontClist( Clist* cl )
{
if( cl->size )
{
pNode cur = cl->start;
char* str = cur->str ;
cl->start = cur->next;
/* free( cur->str ); */
free( cur ); /* free memory for dynamic Node ... */
-- cl->size; /* now update size ... */
if( !cl->size ) cl->end = NULL; /* update end if Clist is empty */
return str; /* and return (by reference, since address passed in) */
}
return newCopy( "" );
}
/* pass in the address of the Clist and the new Node to insert ... */
void insert_sortedClist( Clist* list, pNode n )
{
pNode head;
if( !list->isSorted ) msortClist( list );
head = list->start;
/* 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 */
pNode cur = head;
while( cur->next != NULL && strcmp( cur->next->str, n->str ) <= 0 )
{
cur = cur->next;
}
if( cur == list->end ) list->end = n;
n->next = cur->next;
cur->next = n;
/* list->start = 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->start = n;
++ list->size;
if( list->size == 1 ) list->end = n;
}
}
void isortClist( Clist* list )
{
pNode cur,
nextNode;
Clist nClist;
initClist( &nClist );
for( cur = list->start; 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->start = nClist.start;
list->end = nClist.end;
list->isSorted = 1;
/* size hasn't changed ... */
}
#endif /* end of #ifndef dwClistOfString_H */
--- End code ---
And a little test program that demo's using a ClistOfString as a stack ...
--- Code: ---/* push_pop_words.c */ /* 2016-1o-13 */
/* a demo of using a ClistOfString as a 'stack' ... */
#include "ClistOfString.h" /* includes files: "readLine.h" and "Clist.h" */
#define pushClist push_frontClist
#define popClist pop_frontClist
int isEmptyClist( const Clist* cl )
{
return cl->size == 0;
}
/* print from front to back ... */
void printClist( const Clist* cl )
{
pNode cur = cl->start;
for( ; cur != NULL; cur = cur->next )
printf( "%s ", cur->str );
}
int main()
{
/* Get some test data to work with ... */
char* words[] = { "a", "big", "fat", "cat", "was",
"black", "with", "white", "patches", "all", "over" };
const int size = sizeof words / sizeof *words;
int i;
Clist stk, stk2;
Node lst;
initClist( &stk ); /* MUST inital to work OK ... */
initClist( &stk2 );
puts( "Printing the array ... " );
for( i = 0; i < size; ++ i )
{
/* lst.str = newCopy(words[i]);
if you use a new copy in dynamic memory ...
then free that memory when done with it here. */
lst.str = words[i];
pushClist( &stk, &lst );
printf( "%s ", words[i] );
}
puts( "\n\nPrinting the Clist after array was 'pushed' onto it... " );
printClist( &stk );
puts( "\n\nPrinting the stack while popping elements ... " );
while( !isEmptyClist( &stk ) )
{
/* below we pass the pointer to the (perhaps dynamic) C string in the Node ...
BUT we ...
free the memory that held each dynamic Node. */
char* str = popClist( &stk );
printf( "%s ", str );
/* free( str ); free if dynamic Cstring & if done with it */
lst.str = str;
pushClist( &stk2, &lst ); /* push_front onto a 2nd list */
}
puts( "\n\nPrinting the 2nd stack while popping elements ... " );
while( stk2.size ) /* OK ... here we see the recersed order ... */
{
char* str = popClist( &stk2 );
printf( "%s ", str );
}
puts( "\n" );
do
{
printf( "Enter a 'word' to 'push' (onto the 'stack'): " );
fflush( stdout );
lst.str = readLine( stdin );
pushClist( &stk, &lst );
}
while( more() );
while( !isEmptyClist( &stk ) )
{
lst.str = popClist( &stk );
printf( "%s ", lst.str );
pushClist( &stk2, &lst );
}
putchar( '\n' );
while( !isEmptyClist( &stk2 ) )
{
char* str = popClist( &stk2 );
printf( "%s ", str );
free( str ); /* free each dynamic Cstring when done with it */
}
fputs( "\nPress 'Enter' to continue/exit ... ", stdout );
fflush ( stdout );
getchar();
return 0;
}
--- End code ---
Navigation
[0] Message Index
[#] Next page
Go to full version