Next: More information Up: ANSI C for Programmers Previous: Find the bug

# 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 6#3
• 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;
}

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)){
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.

Next: More information Up: ANSI C for Programmers Previous: Find the bug
Tim Love
1999-10-06