CS113: Homework 3

Please create a separate .c file for each problem. Make the subject line of your email "Assignment 3".

DO NOT just e-mail me your source code. YOU MUST turn in a printout of the code to receive credit for the assignment.

In some of these problems, you will be asked to write specific functions. In your programs, you are free to introduce your own additional functions to aid you. (You are encouraged to do so, in fact, as long as you don't go overboard.)

NOTE: The problems below build on each other. Turn in a separate file for each problem, even though much of your code should be recycled in later problems.

Problem 1: Reversing a sentence (reverse.c)

For this problem you must prompt the user for a string corresponding to a sentence, and print the words of the sentence in reverse. For example, if the input string is "My name is Caleb Nichol", the output must be "Nichol Caleb is name My". You should treat a "word" of the sentence as any contiguous block of characters not containing the space character ' '.

You may assume that the input line is of lenth <= 250 characters. For reading strings of text, you should use the function fgets.

It is strongly recommended that you write a function that takes a string and performs the entire manipulation:

void reverse_sentence( char *s );

And here's a big hint: you may find it quite useful to write a helper function:

void reverse_substring( char *s, int start, int end );

that reverses the block of characters in the string s starting at position start and ending at position end-1. For example, calling reverse_substring(s,0,n) for a string of length n would reverse all the characters in the string. (So if the string was "Lisa Bonet ate no basil" the resulting string would be "lisab on eta tenoB asiL".)

Here are some sample interactions with my program:

Please enter a sentence: My name is Caleb Nichol
Backwards: Nichol Caleb is name My


Please enter a sentence: What's your problem?
Backwards: problem? your What's


Please enter a sentence: Lisa Bonet ate no basil
Backwards: basil no ate Bonet Lisa

Please enter a sentence: problem?
Backwards: ?melborp

Problem 2: Implementing a Linked List (lists.c)

If you want to store a variable amount of data, one common data structure to use is the singly-linked list. A linked list is a chain of items in which each item points to the next one in the chain. Such a data structure is rather inefficient if you want to search for individual elements all the time, but it's perfect for something like a variable-length stack, where you want to add elements cheaply and you only need to access the last element you added.

More information on singly-linked lists is available in "Practical C Programming", Chapter 17, and we'll also discuss lists in class.

For this problem, you will use structures and dynamic memory allocation to implement a singly-linked list of strings. You will add your code to a preexisting source file, available below. The strings can be at most of length 250. Each node should point to the next node in the list, and the last node should be NULL. (If the list is empty, the list itself should be NULL.) Graphically, such a list might look like this:

To create your list, you should use the following structure for the nodes, as well as the helpful typedefs for nodes and lists.

typedef struct list_node_struct {
   char node_string[250]; /* string held in this node */
   struct list_node_struct *next; /* pointer to next node */
} list_node;

typedef list_node *string_list;

You should also implement the following functions, none of which should require more than a few simple lines of code.

• string_list create_list();
  • Returns a new list.
• int add_string(string_list *l, char *s);
  • Adds the string s to the list *l by creating a new node to hold s and inserting it into the list. (You must pass a reference to the list, because the first element will change.)
  • Should return 1 if the insertion was successful, and 0 otherwise (for example, if your call to malloc is unsuccessful).
  • Multiple copies of the same string are allowed.
• void print_list(string_list l);
  • Prints all the strings in the order in which they appear in the current list.
  • If the list is empty, prints "(The list is empty!)".
• int search_string(string_list l, char *s);
  • Returns 1 if the string s is in the list, 0 otherwise.
• int delete_string(string_list *l, char *s);
  • Deletes the first node found containing the string s, and frees the space of the node that was used to hold the string.
  • Returns 1 if the deletion was successful, 0 if the string is not in the list.
  • This will be tricky! Make sure you've drawn a picture of how pointers will move around before you start writing code.
• void clean_list(string_list *l);
  • Deletes all the nodes in the list. (Make sure you free all the dynamically-obtained memory!)

Problem 3: Encrypting a Linked List (encrypt.c)

Given a string and a key, which for our purposes is a positive integer, it is possible to "encrypt" the string by shifting every letter of the string "forward" by the number of letters specified by the key. For instance, if the key is 2 and the string is "Hello", the encrypted version of the string is "Jgnnq", since 'j' is two letters in the alphabet after 'h', 'g' is two letters in the alphabet after 'e', etc.

This encryption process should "wrap around" once the end of the alphabet is reached. For instance, if the key is 3, 'z' should be shifted to 'c': shifting 'z' once yields 'a', shifting 'a' yields 'b', and shifting 'b' the third time yields 'c'. As another example, the string "Zany" encrypted with key 4 yields "Derc".

Your function doesn't have to work with negative keys.

Flesh out the following function declarations:

• void encrypt_string(char *s, int k);
  • Accepts a string s and a key k and "shifts" the string by shifting each alphabetic character, depending on the value of the key.
  • The function should preserve the case of alphabetic characters, and non-alphabetic characters should not be changed.
• void encrypt_list(string_list l, int k);
  • Given a string_list, this function should encrypt each string in the list using the key k.

Using Your Functions

The following source code will help you write a program that creates a string_list and accepts the following commands:

• add s: add the string s to the list (using your add_string function, above)
• search s: searches the list for s
• encrypt k: encrypts all the strings in the list using the key k
• print: prints all the strings in the order in which they appear in the list
• clean: deletes the list
• end: deletes the list, ends the program

Enter a command: print
(The list is empty!)

Enter a command: add Abacus
Add successful!

Enter a command: add Cardiovascular!
Add successful!

Enter a command: add Binoculars
Add successful!

Enter a command: search Abacus
The string 'Abacus' is in the list.

Enter a command: print
Binoculars
Cardiovascular!
Abacus

Enter a command: encrypt 1
Encryption successful!

Enter a command: print
Cjopdvmbst
Dbsejpwbtdvmbs!
Bcbdvt

Enter a command: clean
List has been cleaned.

Enter a command: search Abacus
The string 'Abacus' is not in the list.

Enter a command: end
Thanks, it's been fun.

Problem 4: Doing More With Your Linked List (extra.c)

Modify your solution to problem 3 (or problem 2 if you didn't get problem 3 to work) to give it the following additional functionality:

• load s: open the file named s (a string given by the user), which is a text file consisting of strings, one string per line (with a newline character at the end of each line). Read in the contents of the file, inserting each string into the list, then close the file (do not modify the file!). Notify the user that the file was loaded successfully (if it really was), or that the load failed (if no file of that name exists).
• sort: sort the list into alphabetical order (you may use the same ordering as strcmp). You must use the C utility function qsort in order to get full credit for this.
• reverse: for each string in the list, reverse it using functions similar to those you wrote for problem 1. If the string consists of more than 1 word, reverse the order of the words. If the string is a single word, reverse the characters of the word.
• save s: create a text file named s and save the contents of the list to this file, one string per line, with each line terminated by a newline character. You should save the list in its current state, e.g. if it has been encrypted, save the strings in their encrypted form. You may assume that the file you are saving to does not already exist.