Homework 3

The goal of this homework is to give you practice with stacks, queues, and linked lists. All of the problems are from labs 9 and 10, so if you completed those labs you should be able to just copy/paste your solutions into the provided hw3.c file.

Starter Files

You should put your code for this homework into a file named hw3.c, that should compile against our hw3.h. If you wish, you may start from our boilerplate files:

The boilerplate archives include a main.c and a testsuite.c (for testing your other functions). You will only need to submit hw3.c.

For the palindrome problem you will use two dynamic arrays, one as a stack and one as a queue. These are already implemented for you in the dynarray_t type:

Here is a quick reference to the functions we provided for dealing with dynamic arrays:

typedef dynarray_t;                                     // dynamic array struct

/* Basic/common operations */

void   dynarray_init    (dynarray_t *a);                // initialize struct
void   dynarray_free    (dynarray_t *a);                // free struct
size_t dynarray_size    (dynarray_t *a);                // return element count
size_t dynarray_is_empty(dynarray_t *a);                // return true if empty

/* Stack operations */

void   dynarray_push(dynarray_t *a, data_t item);       // add to back
data_t dynarray_pop (dynarray_t *a);                    // remove from back
data_t dynarray_top (dynarray_t *a);                    // return back

/* Queue operations */

void   dynarray_enqueue(dynarray_t *a, data_t item);    // add to back
data_t dynarray_dequeue(dynarray_t *a);                 // remove from front
data_t dynarray_front  (dynarray_t *a);                 // return front

In addition, you may find the following function from ctype.h useful:

  • int tolower(int c)

    Converts c to its lowercase equivalent. If no conversion is possible, the value returned is unchanged. NOTE: For the purposes of this lab, you may use this function as if it accepts and returns a char.

Palindromes

Use a stack and queue (using the dynarray_t structure) to implement a more powerful version of the is_palindrome() function from an earlier lab. As a reminder, this function implements simple palindome verification. Here is the signature and documentation for the function which is declared in hw3.c:

  • bool is_palindrome(char *text)

    Return true if text is a palindrome, false otherwise. A palindrome is a string that is identical to itself when reversed. For example, "madam", "dad", and "abba" are palindromes. Note: the empty string is a palindrome, as is every string of length one.

For this homework, you should make the function more flexible than the version you wrote for the earlier lab. Your new solution should ignore whitespace and punctuation, and all comparisons should be case-insensitive. Include some tests in your main function. Examples of valid palindromes:

  • ""
  • "a"
  • "aa"
  • "aaa"
  • "aba"
  • "abba"
  • "Taco cat"
  • "Madam, I'm Adam"
  • "A man, a plan, a canal: Panama"
  • "Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

Singly-Linked List Exercises

For the remaining exercises you will implement the following singly-linked list functions which use the sllist_t and slnode_t types defined in hw3.h:

  • Implement the sllist_count function, which should return a count of the number of times that the given item is found in the list.

  • Implement the sllist_find method. This will be very similar to the included contains method, except that it needs to return the index of the first occurrence of the given element if it is found, rather than a simple boolean. Thus, you will need to track the current index as you traverse the linked list. This method should return -1 if the item is not found.

  • Implement the sllist_free method. This should clean up the list by deallocating all of the nodes in the list and clearing the list members (head and size).

  • Implement the sllist_addlast method, which should add a new element onto the tail of the list. You must also remember to handle the special case when the list is empty. Don't forget to update the size tracker! IMPORTANT: Given the current implementation, there is no O(1) way to add an element to the tail of the list. You have two options to implement this function:

    • Iterate to the end of the list, finding the last node and adding the new node after that node. This will be O(n) but that is ok for the purposes of this lab.

    • Add a tail reference to the sllist_t struct and use it to add a new item in O(1) time. This is a better solution, but will require you to change several other functions to properly maintain the tail pointer.

  • Implement the sllist_is_equal function. Equality should be defined as follows: both lists have the same number of elements, and each pair of corresponding elements in the list are also equal (as defined by the == operator).

  • Implement the sllist_insert function. This function should insert an item at an arbitrary index in the linked list. This operation will be inherently inefficient because index-based accesses are not O(1) as they are in arrays. One way of organizing this method is to work through the following steps:

    1. Check to make sure the index is in bounds.

    2. Create a new node to contain the item being inserted.

    3. Check to see if insertion should occur at the head; if so, handle that as a special case.

    4. If the item is not being inserted at the head, use a loop to step through the correct number of nodes, keeping track of a prev node and a cur node. Insert the new node at the appropriate location.

    5. Increment the size of the list.

  • Implement the sllist_remove function. This function should remove the given item from the list if it is present. If there are multiple occurences of the given item, it should only remove the first one. You will need to traverse the list looking for the item to remove, keeping track of the predecessor node so that you can reconnect the two separate parts of the list after removal. If the item is not found in the list, the function should make no changes.