CS113: Homework 4

Turn in a PRINTOUT of your program (no sample data necessary) with your full name and netID, in class; AND, e-mail the source code to oneill+assign4@cs.cornell.edu.

Please email the file "lists.c" after you have added the necessary functions to it.

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

Problem: Implementing a Linked List

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 50. 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[50]; /* 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.
• void clean_list(string_list *l);
  • Deletes all the nodes in the list. (Make sure you free all the dynamically-obtained memory!)

Problem: Encrypting a Linked List

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
Cardivascular!
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.