Homework 3

Fri. Oct. 24, 12:20

1.

Reading: Kernigan and Ritchie: 5.5 - 5.9, 6.1 - 6.4

2.

Consider the following program fragment:

1 : int a = 0, b = 1, *p1, *p2;

2 : a = 3;

3 : if (a = b) {p1 = &a; p2 = &b;} else {p2 = &a; p1 = &b;}

4 : b = a++;

5 : *p1 += 10; a = ++(*p1);

6 : a = *p1 / 2;

Fill in the following table where each row is a line in the program and each column is a variable. In each slot in the table, place the value of the variable after the the corresponding line has been executed. For instance, in line 2, for variable a, place 3 because after executing line 2, a's value is 3. If the value of a variable is unknown(ie: it hasn't been initialized), place a question mark(?) in the slot. For pointers(p1, p2), place the variable that the pointer points to in the slot.

Line # a b p1 p2 *p1 *p2 1 2 ...

3.

This problem involves writing a series of functions which implement a lookup table. More specifically, the lookup table will map one char to another char. A lookup table is an array of pairs of characters:

For example, the following table maps 'a' to 'b', 'b' to 'c', and 'c' to 'a':

key val

'a' 'b'

'b' 'c'

'c' 'a'

In general, we want to have lookup tables of any size, not just some fixed constant SIZE. In order to do this, we will need to use dynamic allocation (malloc). Instead of using an array, we will use a pointer and allocate the amount of space that we need for a table when we create it. When we are finished with the table, we need to deallocate it using free. The definition of the table type should look like the following:

  struct pair *t; /* pointer to the series of pairs */

  int current_sz; /* number of elements currently in the table */

  int max_sz; /* maximum number of elements that can be put in table */ }

The functions that you need to write are as follows:

/* allocate space for a table of maximum size sz, containing no elements */
struct table t_create(int sz);

/* deallocate space for table t.  the table can no longer be used */
void t_destroy(struct table t);

/* insert pair p into table t.  
   return 1 if insertion was successful 
     - ie: if there was room in t and t does not already contain a pair with 
           a key the same as the key of p(there are no
           duplicate keys allowed in a table)
   return 0 if insertion was not successful. 
*/
int t_insert(struct table *t, struct pair p);

/* lookup key k in the table.
   return the corresponding val of the pair.
   if no pair with key k appears in the table, return the
   null character('\0')
*/
char t_lookup(struct table t, char a)

/* print out all of the elements of the table */
void print_table(struct table t);

4.

Once you have written the lookup table functions use them in an encryption program as follows:

• Prompt the user for two strings(s1 and s2) of the same length.
• Based on these strings, create an encryption table. Your encryption table should map the first character in s1 to the first character in s2. The 2nd character in s1 to the second character in s2. For example, if the user types in: ``abc'' and ``bca''. Create the encryption table:

  key val

  'a' 'b'

  'b' 'c'

  'c' 'a'

• Now, to create an encrypted string e from an unencrypted string s, check each character in s against the encryption table, if the character appears as a key in the encryption table, replace that character by the corresponding val character in the encrypted string e. If the character you are checking does not appear in the table, copy that character as is into the encrypted string e. Write a function encrypt and use it here:

  char *encrypt(char *s);

  Remember, encrypt should create a new string(ie: use malloc) rather than just modifying the string s which you pass it.

• Prompt the user to type in a secret message (a secret message is a series of words terminated by a final word ``.'') and using encrypt, encrypt the message.
• To test your functions, also create a decryption table which does the reverse mapping (given ``abc'' and ``bca'', map 'b' to 'a', 'c' to 'b', and 'a' to 'c'). Encrypt your messages and then decrypt your messages. Print out both versions. Make sure that the decryption of your encryption is the same as the original string. Hand in some sample output to show that your encryption and decryption works properly.

5.

Extra Credit: Instead of mapping characters to characters, map strings to strings.