Department of Engineering

University of Cambridge >  Engineering Department >  computing help

Exercises 2

To answer these exercises you'll need to be able to get keyboard input from the user. For the moment, use the following fragment to get a string from the user. str needs to point to the start of an existing character array.

char * get_string(char str[])
{
   printf("Input a string\n");
   return gets(str);
}

Sample answers are on page unless otherwise stated.

1. Write your own strcpy routine. Use a for loop with arrays first, then see if you can use a while loop and pointers.

2. The following code fragment uses many of the contractions mentioned earlier. It comes from ghostscript. Re-write it to make it more legible.

   int ccase = (skew >= 0 ? copy_right :
                            ((bptr += chunk_bytes), copy_left))
                            + function;
   

3. Write a program that invites the user to type in a string and prints the string out backwards (The answer's in section 17).
4. Write your own version of strchr (see the manual page for a description).

5. Write a program which reads in a string like ``20C'' or ``15F'' and outputs the temperature to the nearest degree using the other scale. The easiest way to parse the input string is to use sscanf to scan the input string for a number and a character. It will return the number of items successfully read in.

   ...
   int degrees;
   char scale;
   int return_value;
   ...
      return_value = sscanf(str,"%d%c",&degrees, &scale);
   ...
   

6. The following program will be developed later in the handout. Suppose you have a situation where you need to process a stream of things (they might be scanned character images, chess positions or as in this example, strings), some of which might be duplicates. The processing might be CPU-intensive, so you'd rather use the previously calculated values than re-process duplicate entries. What's needed is a look-up table.

   Each entry in the look-up table needs to have a record of the original string and the result of the processing. A structure of type Entry

   typedef struct {
      char str[64]; 
      int value;
   } Entry;
   

   will do for now. For our purposes it doesn't matter much what the processing routine is. Let's use the following, multiplying all the characters' values together.

   int process(char *str){
     int val = 1;
     while (*str){
        val = val * (*str);
        str++;
     }
     return val;
   }
   

   To get strings into the program you can use the get_string function. Now write a program that reads strings from the keyboard. If the string is new, then it's processed, otherwise its value is looked up in a table. The program should stop when `end' is typed. Here's a skeleton program to get you started.

   /* hash1.c */
   /* TODO include standard include files */ 
   
   /* The following 2 lines use the preprocessor to create aliases.
      Note that these lines DON'T end with a `;'
    */ 
   #define TABLE_SIZE 50
   #define MAX_STR_LEN 64
   
   typedef struct {
      char str[MAX_STR_LEN]; 
      int value;
   } Entry;
   
   char str[MAX_STR_LEN];
   
   /* TODO Create an array of TABLE_SIZE elements of type Entry */
   
   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);
   }
   
   main(){
          int num_of_entries = 0;
   /* TODO Use get_string repeatedly. For each string:-
              If the string says `end', then exit.
              If the str is already in the table,
                 print the associated value
              else
                 calculate the value, add a new 
                 entry to the table, then print the value.
    */
   }
   

7. The method used above can be improved upon. Firstly, it will go wrong if there are too many strings. By choosing an arbitrarily large value for TABLE_SIZE you could overcome this problem, but the method of searching the table to see whether an entry is new becomes very inefficient as the table grows.

   A technique called hashing copes with the speed problem. First we need a hash function which given a string produces a number in the range 0..TABLE_SIZE. The following function just adds up the value of the characters in the string and gets the remainder after dividing by TABLE_SIZE.

    
   int hashfn(char *str){
     int total = 0;
     int i;
     while (i = *str++)
         total += i;
     return total % TABLE_SIZE;
   }
   

   Now, whenever a string is to be processed, its hash value is calculated and that is used as an index into the table, which is much quicker than searching. If that entry is empty then the string is new and has to be processed. If the entry is occupied, then the associated value can be accessed. This method is flawed, but we'll deal with that problem later.

   /* hash2.c */
   /* TODO include standard include files */ 
   #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];
   
   /* TODO Create an array of TABLE_SIZE elements of type Entry */
   
   int process(char *str){  /* Same as hash1.c */
     int val = 1;
     while (*str){
        val = val * (*str);
        str++;
     }
     return val;
   }
   
   char * get_string(char str[])  /* Same as hash1.c */
   {
      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){
   /* TODO set all the value entries in the table to EMPTY
          (We'll assume that the process() routine doesn't
           produce -1)
   */
   }
   
   int find_entry(char *str, int bucket){
   /* TODO
      if the entry in postion 'bucket' is EMPTY then fill 
      the entry's fields in and return the string's 
      processed value, else return the value of the entry.
   */
   }
   
   main(){
   int bucket; 
   int val;
          set_table_values();
   /* TODO Use get_a_string repeatedly. For each string:-
             use the hash function to find the string's entry
             in the table, then do the following
   */
          bucket = hashfn(str)
          val = find_entry(str,bucket);
          printf("Value of <%s> is %d\n",str, val);
   
   
   }
   

8. The problem with this method is that the hash function may produce the same value for different strings (for example, `act' and `cat' will both map into the same entry). A simple way of coping with such `collisions' is the following:- If a table entry is occupied, check the string there to see if it's the one being searched for. If it is, then return the associated value. If it isn't the right string, then look at subsequent entries until either
   • an entry for the string is found.
   • an empty entry is found.
   • It's been shown that all entries are full up.

   You'll have to add just a few lines to the find_entry routine of the previous exercise. Remember to cycle round when the bottom of the table is reached.

   A more robust method (and the answer to the exercise here) is in the next set of exercises (see section 17).