| | | 5.30 Linked lists |
/* Louis Taber April 15, 2001 */
/* */
/* Linked list program #1 */
#include <stdio.h>
#define TRUE 1
struct token
{
struct token *next; /* link to next item */
char *value; /* link to storage for string */
int usecount; /* number of times encountered */
};
struct token * insert(char * string);
int link_count = 0; /* count of links used */
int item_count = 0; /* count of items */
main()
{
int i; /* loop counter */
char string[200]; /* max string size */
struct token *current;
struct token *start;
struct token *working;
start = NULL;
while( TRUE ) /* Until EOF */
{ /* get a string */
if( fscanf( stdin, "%s", string ) == EOF ) break;
if( start == NULL )
{
start = insert( string );
continue;
}
current = start;
while( TRUE )
{
if( strcmp( string, current->value ) == 0 )
{ /* found existing item */
current->usecount++;
break;
}
if( current->next == NULL ) /* if end of list */
{
current->next = insert( string );
break;
}
else
{ /* get next item on list */
current = current->next;
link_count++;
}
}
}
current = start; /* print out items */
while( TRUE )
{
if( current == NULL ) break;
item_count ++;
if( current->usecount > 3 )
printf("use:%4d -- %s\n",
current->usecount, current->value);
current = current->next;
}
printf("\nItem count: %4d Link count: %4d\n",
item_count, link_count);
}
/* routine to insert string at end of linked list. */
struct token * insert(char * string)
{
int str_length;
struct token * token_ptr;
/* allocate space for structure */
token_ptr = (struct token*) malloc( sizeof( struct token ));
if( token_ptr == NULL )
{
printf("malloc 1 failed\n");
exit();
}
/* get string length and allocate space */
str_length = strlen( string ) + 1;
/* set initial use count */
token_ptr->usecount = 1;
/* clear next pointer */
token_ptr->next = NULL;
/* copy string to heap */
token_ptr->value = (char *) malloc( str_length );
if( token_ptr->value == NULL )
{
printf("malloc 2 failed\n");
exit();
}
strcpy( token_ptr->value, string );
/* return pointer to new structure */
return token_ptr;
}
And the edited output:
use: 13 -- things use: 674 -- will use:1825 -- a use:2588 -- to use: 7 -- Visual use: 7 -- Cybervision Item count: 12191 Link count: 156262111
This program is a modification of the prior
program that uses multiple linked lists and
a hashing algorithm to reduce search time.
The source is available at:
ftp://lt.tucson.az.us/pub/c/link-hash.c
/* Louis Taber April 16, 2001 */
/* */
/* Linked list program #2 */
#include <stdio.h>
#define TRUE 1
/* Number of linked lists */
#define MASKBITS 8
#define HASHMAX ( 1 << MASKBITS )
#define MAXMASK ( HASHMAX - 1 )
/* When run on a text file with 565839 bytes */
/* ( ../linux/Documentation/Configure.help) */
/* with different values of MASKBITS */
/* This was done with an AMD K6-2 500Mhz with */
/* 128 Mbytes running Linux */
/* MASKBITS HASHMAX U Time Link Count */
/* 0 1 23.42 156262111 */
/* 1 2 14.78 78120792 */
/* 4 16 2.26 9750485 */
/* 5 32 1.35 4865690 */
/* 8 256 .42 602588 */
/* 12 4096 .33 32669 */
struct token
{
struct token *next; /* link to next item */
char *value; /* link to storage for string */
int usecount; /* number of times encountered */
};
struct token * insert(char * string);
int link_count = 0; /* count of links used */
int item_count = 0; /* count of items */
/* Routine to determine which linked list */
/* This should be fast and "random". */
int hash(char *st)
{
int rtn=0;
char c;
while( (c = *st++) != '\0' )
{
rtn = ( ( rtn ^ 0x5A5A ) << 2 ) ^ c;
rtn = (rtn & 0xFFFF) ^ (rtn >> 12);
}
return rtn & MAXMASK;
}
main()
{
int i; /* loop counter */
int hash_count[HASHMAX];
int start_point; /* index in to linked list array */
char string[200]; /* max string size */
struct token *current;
struct token *start[HASHMAX];
struct token *working;
/* Print hash algorithm constants */
printf("MASKBITS %d\nHASHMAX %d\nMAXMASK %08x\n",
MASKBITS, HASHMAX, MAXMASK);
for( i=0; i<HASHMAX; i++) start[i] = NULL;
while( TRUE ) /* Until EOF */
{ /* get a string */
if( fscanf( stdin, "%s", string ) == EOF ) break;
/* figure out which list */
start_point = hash( string );
if( start[start_point] == NULL )
{ /* place initial string */
start[start_point] = insert( string );
continue;
}
current = start[start_point];
while( TRUE )
{ /* look for existing item */
if( strcmp( string, current->value ) == 0 )
{ /* found existing item */
current->usecount++;
break;
}
if( current->next == NULL ) /* if end of list */
{ /* place item at end of list */
current->next = insert( string );
break;
}
else
{ /* get next item on list */
current = current->next;
link_count++;
}
}
}
for( i=0; i<HASHMAX; i++ )
{
hash_count[i] = 0;
current = start[i]; /* print out items */
while( start[i] != NULL )
{
if( current == NULL ) break;
item_count++;
hash_count[i]++;
if( current->usecount > 5 )
printf("use:%4d -- %s\n",
current->usecount, current->value);
current = current->next;
}
}
for( i=0; i<HASHMAX; i++ )
printf("%8d",hash_count[i]);
printf("\nItem count: %4d Link count: %4d\n",
item_count, link_count);
}
/* routine to insert string at */
/* end of linked list. */
struct token * insert(char * string)
{
int str_length;
struct token * token_ptr;
/* allocate space for structure */
token_ptr = (struct token*)
malloc( sizeof( struct token ));
if( token_ptr == NULL )
{
printf("malloc 1 failed\n");
exit();
}
/* get string length and allocate space */
/* strlen does not include '\0' */
str_length = strlen( string ) + 1;
/* set initial use count */
token_ptr->usecount = 1;
/* clear next pointer */
token_ptr->next = NULL;
/* copy string to heap */
token_ptr->value = (char *) malloc( str_length );
if( token_ptr->value == NULL )
{
printf("malloc 2 failed\n");
exit();
}
strcpy( token_ptr->value, string );
/* return pointer to new structure */
return token_ptr;
}
And the edited output:
MASKBITS 8 HASHMAX 256 MAXMASK 000000ff use: 13 -- things use: 674 -- will use:1825 -- a use:2588 -- to use: 7 -- Visual use: 7 -- Cybervision 61 46 55 47 51 55 ... Item count: 12191 Link count: 602588
| | | 5.30 Linked lists |