Advanced C Programming

Fall 2017 :: ECE 264 :: Purdue University

Due 11/10

Huffman #1 (E)

This exercise will familiarize you with linked lists, which you will need for a subsequent programming assignment.

Getting Started

Start by getting the files. Type 264get hw12 and then cd hw12 from bash.

You will get the following files:

  1. huffman.h: Header file.
  2. huffman.c: Functions you have to write in this homework.

Overview

In this exercise, you will use a linked list to implement a priority queue or a stack.

A priority queue is implemented as a linked list where the objects stored in the list are actually ordered. For example, if we want to store a linked list of numbers 5, 10, 4, 3, 1, and the linked list is used to implement a priority queue, the linked list should appear as follows:

1→3→4→5→10→NULL

Here, we assume that "→" is the "pointer." We also assume that a smaller number has a higher priority, and it is therefore listed first. If we now want to get number 7 to join the priority queue, we should have the list updated to:

1→3→4→5→7→10→NULL

We call this the enqueue operation. To remove an item from a priority queue, we always remove the item with the highest priority. This is call the dequeue operation. In this case, a dequeue operation will remove 1 from the list:

3→4→5→7→10→NULL

When a stack is implemented as a linked list, the object that is pushed onto the stack always appears as the first item on the list. Therefore, if we push the list of numbers 5, 10, 4, 3, 1 onto a stack successively, we have the following linked list:

1→3→4→10→5→NULL

If we pop from the stack, we have

3→4→10→5→NULL
If we now push 7 onto the stack, we have
7→3→4→10→5→NULL
In both priority queue and stack, we always remove an item from the beginning of the list because that is the most convenient place to remove an item from a list.

To help you understand the complexity involved in the removal of an item not at the beginning of a list, you will also write a function to remove the last item from a list. For the following list:

7→3→4→10→5→NULL
The removal of the last item in the list gives you
7→3→4→10→NULL
You will also write a function to destroy a linked list and free all memory associated with that linked list.

Structure defined

The following structure will be used for HW12.

typedef struct _Node {
   void* ptr;
   struct _Node* next;
} Node;
ptr stores an address that points to a generic type. The generic type can be a simple data type, a multi-dimensional array, or even a user-defined structure. Essentially, you will be implementing a linked lists of addresses stored in ptr. We shall assume that within a linked list, these addresses in ptr will all be pointing to objects of the same type. next stores an address that points to an object of type Node (or struct _Node), thereby allowing you to maintain a linked list.

Requirements

  1. Your submission must contain each of the following files, as specified:
    file contents
    huffman.c functions
    pq enqueue(Node✶✶ pq, const void✶ new object, int(✶cmp fn)(const void✶ , const void✶ )))
    return type: Node✶
    1. *pq stores the address of the first Node in the linked list. If *pq is NULL, the list is currently empty. You may assume that if *pq is not NULL, the list is valid.
    2. new_object stores the address of the generic type.
    3. cmp_fn stores the address of the comparison function for comparing the two objects of the same type. The addresses of the two objects, treated as addresses pointing to generic type, are passed into the function.
    4. If new_object is NULL, the list should remain intact, and you should return NULL. (Note that this is what we choose to do for this exercise. In some applications, you may want to allow NULL as new_object.)
    5. If you could not allocate a new Node to store new_object in the ptr field, the list should remain intact, and you should return NULL. Otherwise, the newly allocated Node should be inserted into the linked list such that all Node's before the new Node in the list contain objects that are smaller (or equal) to the new Node (according to cmp_fn(…)), and all Node's after the new Node in the list contain objects that are bigger (or equal) to the new Node (according to cmp_fn(…)).
    6. *pq should be updated if the new Node becomes the first item in the list. The function should return the address of the new Node.
    pq dequeue(Node✶✶ pq)
    return type: Node✶
    Detach the head of the linked list and return as a single-node linked list.
    1. You are effectively splitting a linked list into two lists.
    2. *pq is the head (first node) of a valid linked list.
    3. If the list is empty, return NULL (since there is nothing to dequeue).
    4. Upon return, *pq must be a valid linked list.
    5. Reminder: NULL is a valid linked list of size 0. Thus:
      1. *pq might be NULL.
      2. Upon removing the last node, you should set *pq to NULL.
    6. You must set the next field of the removed Node to NULL.
    7. The caller is responsible for freeing the detached node, and any memory it refers to.
      1. This function should not call free(…), directly or indirectly.
    stack push(Node✶✶ stack, const void✶ new object)
    return type: Node✶
    1. *stack stores the address of the first Node in the linked list.
    2. new_object stores the address of the generic type.
    3. If new_object is NULL, the list should remain intact, and you should return NULL.
    4. If you could not allocate a new Node to store new_object in the ptr field, the list should remain intact, and you should return NULL.
    5. The ptr field of the newly allocated Node should store new_object.
    6. The newly allocated Node should become the first Node of the list, and *stack should be updated. The function returns the address of the new Node.
    stack pop(Node✶✶ stack))
    return type: Node✶
    In a sense, this is the same as pq_dequeue(…)
    remove last node(Node✶✶ list)
    return type: Node✶
    1. *list stores the address of the first Node in the linked list.
    2. If the list is empty, there is nothing to remove. You should return NULL. Otherwise, you should remove the last Node from the linked list and if necessary, update *list accordingly.
    3. You should make the removed Node into a single-node linked list. You return the address of the removed Node.
    4. Again, as in the dequeue and pop operations, this function does not deallocate memory associated with the original linked list. The caller function is responsible for freeing the memory associated with the removed Node (including the memory associated with the ptr in the removed Node).
    destroy node(Node✶ list, void (✶destroy fn)(void✶))
    return type: void
    1. list stores the address of the first Node in the list.
    2. destroy_fn stores the address of the function to deallocate the memory associated with the address of the generic type stored in the ptr field of an Node.
    3. If the generic type is a simple data type, the free(…)function in stdlib.h is an appropriate function for destroy_fn. If the generic type is a user-defined type such as the Maze structure in HW10, an appropriate function for destroy_fn is free_maze(…).
    4. The destroy_node(…) function should free all memory associated with list.
    5. For each Node in the list, it has to use destroy_fn to deallocate memory associated with the address of the generic type stored in the ptr field and free to deallocate memory allocated for the Node.
    6. You may want to take a look at the print_node(…) function provided in huffman.c as an example on how to call a function whose address has been passed in as a parameter.
    test_huffman.c functions
    main(int argc, char✶ argv[])
    return type: int
    Test all of the required functions in your huffman.c.
    • Running your main(…) should cover all of your code in huffman.c, except for the parts that deal with allocation failures. (Testing error handling code is a standard practice, but takes more setup than we expect from you at this point.)
    • We should be able to compile and run your test_huffman.c with someone else's huffman.c.
    • Your test should return EXIT_SUCCESS and produce the output in expected.txt if and only if the implementation code (huffman.c) is correct.
    • If the huffman.c is incorrect, this should return EXIT_FAILURE and/or print output different from your expected.txt.
    expected.txt output Expected output from running your test_huffman.c.
    • When your runs, the output (on stdout) should be identical to the contents of this file, if and only if the huffman.c it was compiled with is correct.
    • This can be anything you like, as long as it distinguishes a working implementation (huffman.c) from a flawed one.
    • You will write this file by hand. (This is not created by your code.)
    • To check if your output matches, run:
      gcc huffman.c test_huffman.c -o huffman diff <(./huffman) expected.txt
  2. Do not print error messages or anything else on stdout (i.e., with printf(…)), except as directed by the instructions. Your main(…) can (and should) print some output to stdout.
  3. Do not modify huffman.h.
  4. Do not include a main(…) in huffman.c. (→ zero credit, since we won't be able to compile.)
  5. Submissions must meet the code quality standards and the course policies on homework and academic integrity.

Examples of cmp_fn(…) and print_fn(…)

We have provided examples of destroy_fn(…) functions. Here are some examples of cmp_fn(…) (for the pq_enqueue(…) function) and print_fn(…) (for the print_node(…) function, which has been defined for you in huffman.c). If we store the addresses of int (i.e., int*) as the addresses of the generic type (void*) in ptr, we can use the following comparison function:

static int int_cmp(const void* p1, const void* p2) {
   return *(const int*)p1 - *(const int*)p2;
}
Here, the addresses p1 and p2 have been typecast to const int*, and dereferenced to obtain const int for comparison (with the difference being the result). If we store the addresses of char (i.e., char*) as the addresses of the generic type (void*) in ptr, and each address of char is actually the address of the first character of string, we can use the following comparison function:
static int string_cmp(const void* p1, const void* p2) {
   return strcmp((const char*)p1, (const char*)p2);
}
We can use the following print functions for the two generic types for the print_fn(…) parameter in the print_node(…) function.
static void int_print(const void* ptr) {
   printf("%d", *(const int*)ptr);
}
static void string_print(const void* ptr) {
   printf("%s", (const char*)ptr);
}
These functions will be useful for your test functions (to be written in test_huffman.c, for example). These comparsion functions and print functions should not appear in huffman.c

Submit

To submit HW12, type 264submit HW12 huffman.c test_huffman.c expected.txt from inside your hw12 directory.

Pre-tester

The pre-tester for HW12 has been released and is ready to use.

Q&A

Updates

10/30/2017 Preview posted
11/5/2017 Fixed typo in submit instructions. They now include all 3 files.