Department of Engineering

University of Cambridge >  Engineering Department >  computing help

Exercises 3

1. Improve your primes program so that
   • It stops searching for primes in the range 0 to n once it has marked all the multiples of primes
   • It can take as an argument a number to show the upper bound of the primes to print out (see A.1).

2. Put 10 integers in a file, one per line. Write a program that reads the numbers then prints their sum and and average.

3. Write a program that counts the characters, words and lines in a file.

4. Read the 1st 10 uids from /etc/passwd, save them in an array of strings and sort them using qsort.

5. Take a simple program (the malloc example on page will do) and break it up into 2 or 3 source files. See if you can compile them into an executable. Try adding static to variable and function definitions to see what difference it makes. Write a makefile for it.

6. Write a program that given a filename will produce a new file encrypted using any method you like. Then write another program to decrypt files.

7. Write a program to count the number of ways that 8 queens can be placed on a chess board without any 2 of them being on the same row, column or diagonal.

8. Hashing - First a solution to the last hash exercise.

   #include <stdio.h>
   #include <stdlib.h>
   #define TABLE_SIZE 50
   #define MAX_STR_LEN 64
   #define EMPTY  -1
   
   typedef struct {
      char str[MAX_STR_LEN]; 
      int value;
   } Entry;
   
   char str[MAX_STR_LEN];
   
   /* Create an array of elements of type Entry */
   Entry table[TABLE_SIZE];
   
   int process(char *str){
     int val = 1;
     while (*str){
        val = val * (*str);
        str++;
     }
     return val;
   }
   
   char * get_string(char str[])
   {
      printf("Input a string\n");
      return gets(str);
   }
   
   int hashfn(char *str){
     int total = 0;
     int i;
     while (i = *str++)
         total += i;
     return total % TABLE_SIZE;
   }
   
   
   void set_table_values(void){
   /* set all the value entries in the table to EMPTY
      (here we assume that the process() routine doesn't
       produce -1)
   */
   int i;
     for (i =0;i<TABLE_SIZE;i++)
         table[i].value= EMPTY;
   }
   
   int find_entry(char *str, int bucket){
      if (table[bucket].value == EMPTY){
         strcpy(table[bucket].str,str);
         table[bucket].value = process(str);
      }
      else{
         if (strcmp(table[bucket].str,str)){
            bucket = (bucket +1)% TABLE_SIZE;
            return find_entry(str, bucket);
         }
      }
   
      return table[bucket].value;
   }
   
   
   main(){
   int bucket;
   int val;
          set_table_values();
   
   /* Use get_string repeatedly. For each string:-
          use the hash function to find the string's entry
          in the table.
   */
          while(get_string(str)){
            if (! strcmp(str,"end")){
                printf("Program ended\n");
                exit(0);
            }
   
            bucket = hashfn(str);
            val = find_entry(str,bucket);
            printf("Value of <%s> is %d\n",str,val);
          }
   }
   

   Another approach to collisions is for each entry in the hash table to be the beginning of a linked list of items that produce the same hash function value. First we need to alter the Entry structure so that it includes pointer to another Entry. There's a slight complication here in that we can't define a pointer to something which isn't defined yet, so we introduce a tag name to the structure.

   typedef struct _entry {
    int value;
    struct _entry *next;
    char str[20];
   } Entry;
   

   New entry structures can be generated using the following routine.

   Entry *create_an_entry(void){
   Entry *entry;
     entry = (Entry*) malloc(sizeof (Entry));
     return entry;
   }
   

   find_entry needs to be re-written.

   int find_entry(Entry ** entry, char *str){
    if (*entry == NULL){
       *entry =  create_an_entry();
       set_entry(*entry,str);
       return (*entry)->value;
    }
    else{ 
       if ((*entry) -> value != EMPTY){
          if (!strcmp ((*entry) ->str, str)){
             printf("Valueue for <%s> already calculated\n",str);
             return (*entry) -> value;
          }
          else{
             printf("There's a collision: <%s> and <%s> share\n",
                       (*entry) ->str, str);
             printf("the same hashfn valueue\n");
    
             find_entry(&((*entry)->next),str);
             
          }
       }
       else{
          printf("<%s> is a new string\n",str);
          set_entry((*entry),str);
          return (*entry)->value;
       }    
    }
   }
   

   The initial table can now be

   /* Create an array of elements of type Entry */
   Entry *table[TABLE_SIZE];
   

   These entries need to be initialised to NULL.

   Now write a program with the following main routine to test all this out.

   main(){
   int bucket;
   int value;
          set_table_values();
   
   /* Use get_string repeatedly. For each string:-
          use the hash function to find the string's entry
          in the table.
   */
          while(get_string(str)){
            if (! strcmp(str,"end")){
                printf("Program ended\n");
                exit(0);
            }
   
            bucket = hashfn(str);
            value = find_entry(&(table[bucket]), str);
            printf("Valueue of <%s> is %d\n",str,value);
          }
   }
   

   This program could be further elaborated
   • At the moment, if a string is long enough it will be too big for the array. Change the Entry definition to:-

     typedef struct _entry {
      int val;
      struct _entry *entry;
      char *str;
     } Entry;
     

     and change the code so that correctly sized space for each string is created using malloc.

   • A hash function should be quick to calculate and provide an even spread of values to minimize collisions. Add some diagnostics to the program and improve the hash function.