6 Notes6.29 Structures6.30 Linked lists

6.30 Linked lists

This program inputs "tokens" from the standard input and places them on a linked list keeping track of usage The source is available at:
ftp://lt.tucson.az.us/pub/c/link.c

/* 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

Instructor: Louis Taber, louis.taber.at.pima at gmail dot com (520) 206-6850
My web site in Cleveland, OH
The Pima Community College web site

6 Notes6.29 Structures6.30 Linked lists