Exercises 3
- 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).
- Put 10 integers in a file, one per line.
Write a program that reads the numbers then prints their sum and
and average.
- Write a program that counts the characters, words and lines
in a file.
- Read the 1st 10 uids from /etc/passwd, save them in an array of
strings and sort them using qsort.
- Take a simple program (the malloc example online 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.
- 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.
- 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.
- 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.
- At the moment, if a string is long enough it will be too big for
the array. Change the Entry definition to:-