CMSC 15200 - Summer 2016

Homework #7: Due: Saturday August 20th, 2016 @ 11:59pm

In this homework assignment, your task is to implement a string linked list.

You will create your string linked list in its own header and source files called sll.h and sll.c.

Your main function will appear in a file called hw7.c that will test the functions that you wrote in your string linked list library. Make sure to include a Makefile for this program.

It will probably be helpful for you to use the checkit_string function to check strings in the list.

---

String Linked List

We define the string linked list data structure as follows:

struct string_linked_list {
  char* s;
  struct string_linked_list* next;
};

typedef struct string_linked_list SLL;
                      

This is very similiar to the integer linked list you saw in class, but with strings instead. Athough not formally encoded in this data structure definition, we assume that NULL is used to represent the empty list.

---

String Linked List Functions

Implement the following operations. For the most part, the intended behavior of each should be clear from a brief description, but see the notes below for greater detail. Some functions can make heavy use of others - avoid unnecessary code duplication!

/* Build a new list from s and list */
/* For the head of the list, copy the string to the heap (use strdup) */
SLL* SLL_cons(const char* s, SLL* list);

/* Insert a string s into the list before element t */
/* If there is no entry for t, append s to the end of the list */
SLL* SLL_insert(const char* s, const char* t, SLL* list);

/* Compute the length of the given list */
unsigned int SLL_length(const SLL* list);

/* Return boolean, indicating whether list is empty */
_Bool SLL_is_empty(const SLL* list);

/* Return the number of times string s appears in the list */
unsigned int SLL_count(const char* s, const SLL* list);

/* Return boolean, indicating whether the list contains string s */
_Bool SLL_contains(const char* s, const SLL* list);

/* Return boolean, indicating whether the list contains all strings in s_arr */
/* The order of strings in s_arr doesn't matter */
_Bool SLL_contains_all(char** s_arr, unsigned int len, const SLL* list);

/* Remove the matching string entry from the list (if it exists). */
/* Don't forget to free any heap data that is no longer needed. */
SLL* SLL_remove(const char* s, SLL* list);

/* Free the entire string list and all the strings it points to as well */
void SLL_free(SLL* list);

/* Returns the total number of occurrences of the character ch in each string in list */ 
unsigned int SLL_count_char(const SLL* list, char ch) 

/* Test whether the two lists are logically identical */
/* (they may or may not be physically identical) */
_Bool SLL_equals(const SLL* list1, const SLL* list2);

/* Reverse the list */
SLL* SLL_reverse(SLL* list);

Notes:

• An example of SLL_count_char is the following:

  Let's say SLL* L1 = ("Bob") -> ("Jane") -> ("Brad") -> ("Sam") -> NULL

  checkit_int(SLL_count_char(L1, 'a'), 3) PASSES

  checkit_int(SLL_count_char(L1, 'b') ,1) PASSES

• SLL_equals should test whether the two given lists contain the same strings in the same order. By same strings, we mean strings that contain the same sequence of characters; they may be distinct memory objects and still be the same in this sense.
• A NULL string is not allowed in the list (although there's no particular reason it couldn't be).

In your implementation, be mindful of allocations, and guard against memory leaks. Make sure if computation allocates temporary heap objects not needed in the final result, you free them when you no longer need them.

Your test cases should test enough cases to convince a moderate skeptic that your code does, in fact, work. It is fine to test the functions out of order. You do not need to test SLL_free; we will just read it carefully.

---

Style

At the top of your C file, write a comment with your name, etc., in the following form:

              /* Jane Doe, jdoe */
              /* CS152, Summer 2016 */
              /* Homework 7 */
              

This information is not strictly necessary, since your files are already identified by their names and the repository they reside in. Nevertheless, the redundancy is a helpful convenience for us when we are browsing and/or grading your work.

Comments, where they occur, should be helpful and precise. Omit superfluous comments:

              int a = b + c; /* I'm adding b and c and naming it a! */
              

Yes, we can see that.

Your code should be no more than 80 columns wide.

Do not write more than one statement on a line.

Do not submit code that does not compile. If a function is broken, and makes compilation impossible, comment out that function and submit the rest. Non-compiling code will receive little to no credit.

---

Submitting Your Work

Save and commit all your files stated above . Recall that you will need to add your work before you commit it. (Also, notice that in the -m message you include at commit time, -m is simply a command-line option.)

Commit your work early and often. We do not grade intermediate commits, only the work as it stands at the deadline. If you have any issues with subversion, not only your instructors but your classmates can help you. Most of the students in this class have at least one full quarter of experience running subversion.

If, for any reason, perhaps due to a late add, you do not have a CS repository, save your work somewhere you can easily get it and send mail to the lecturer. We'll get you set up with a repository in time to make the deadline.