CMSC 15200 - Summer 2013

Homework #5 (Long): Due: Wednesday August 21th, 2013 @ 1:30pm

In this homework, your task is to build a string linked list toolkit. Your submission must contain the implementation of the string linked list operations described in this document.

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 hw5.c that will test the functions that you wrote in your string linked list library.

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;
                      

We also assume, although it is not formally encoded in this data structure definition, 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.

/* return a quasi-boolean, indicating whether list is empty */
int SLL_is_empty(SLL *list);

/* 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(char *s, SLL *list);

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

/* compute the length of the given list */
int SLL_length(SLL *list);

/* returns the total number of occurrences of the character ch in each string in list */ 
int SLL_totalChars(SLL * list, char ch) 

/* returns a new list of that nodes are replicated the number of times specified by parameter count */ 
SLL * SLL_replicate(SLL * list,int count)

/* Create a new list that is an ordered union of the the two list. */ 
/* Use strcmp to determine which string is less/greater than the other string */ 
SLL * SLL_mergeAndOrder(SLL * list1, SLL * list2); 

/* test whether the two lists are logically identical */
/* (they may or may not be physically identical) */
int SLL_same(SLL *list1, SLL *list2);

Notes:

• An example of SLL_totalchars is the following

  Lets say SLL * L1 = ("Bob") -> ("Jane") -> ("Brad") -> ("Sam") -> NULL

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

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

• An example of SLL_replicate is the following

  Lets say SLL * L1 = ("Bob") -> ("Jane") -> ("Brad") -> NULL

  SLL * L2 = SLL_replicate(L1,2) = ("Bob") -> ("Bob") -> ("Bob") -> ("Jane") -> ("Jane") -> ("Jane") -> ("Brad") -> ("Brad") -> ("Brad") -> NULL

• An example of SLL_mergeAndOrder is the following

  Lets say SLL * L1 = ("a") -> ("d") -> ("z") -> NULL

  Lets say SLL * L2 = ("c") -> ("b") -> NULL

  SLL * L3 = SLL_mergeAndOrder(L1,L2) = ("a")->("b")->("c")->("d")->("z") -> NULL

• SLL_same 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.

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 hw4.c file, write a comment with your name, etc., in the following form:

              /* Jane Doe, jdoe */
              /* CS152, Summer 2013 */
              /* Homework 5 */
              

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 your files in YOUR-REPOSITORY/hw5. 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 Adam. We'll get you set up with a repository in time to make the deadline.