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:

huffman.h: Header file.
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

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✶ `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. `new_object` stores the address of the generic type. `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. 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`.) 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(…)`). ⚠`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. You are effectively splitting a linked list into two lists. `pq` is the head (first node) of a valid linked list. If the list is empty, return `NULL` (since there is nothing to dequeue). Upon return, `pq` must be a valid linked list. Reminder: `NULL` is a valid linked list of size 0. Thus: `pq` might be NULL. Upon removing the last node, you should set `pq` to `NULL`. You must set the `next` field of the removed `Node` to `NULL`. The caller is responsible for freeing the detached node, and any memory it refers to. ⚠ This function should not call `free(…)`, directly or indirectly.
		`stack push(Node✶✶ stack, const void✶ new object)` → return type: Node✶ `stack` stores the address of the first `Node` in the linked list. `new_object` stores the address of the generic type. If `new_object` is `NULL`, the list should remain intact, and you should return `NULL`. 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`. The `ptr` field of the newly allocated `Node` should store `new_object`. 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✶ `list` stores the address of the first `Node` in the linked list. 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. You should make the removed `Node` into a single-node linked list. You return the address of the removed `Node`. 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 `list` stores the address of the first `Node` in the list. `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`. 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(…)`. The `destroy_node(…)` function should free all memory associated with list. 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`. 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

⚠ 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.
⚠ Do not modify huffman.h.
⚠ Do not include a main(…) in huffman.c. (→ zero credit, since we won't be able to compile.)
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.

In general, to submit any assignment for this course, you will use the following command:

264submit ASSIGNMENT FILES…

Submit often and early, even well before you are finished. Doing so creates a backup that you can retrieve in case of a problem (e.g., accidentally deleted your files).

To retrieve your most recent submission, type 264get --restore ASSIGNMENT (e.g., 264get --restore hw12).

To retrieve an earlier submission, first type 264get --list ASSIGNMENT to view your past submissions and find the timestamp of the one you want to retrieve. Then, type 264get --restore -t TIMESTAMP ASSIGNMENT.

Scores will be posted to the Scores page after the deadline for each assignment.

Pre-tester ●

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

Using the pretester

The pretester is a tool for checking your work after you believe you are done, and before we have scored it. It is not a substitute for your own checking, but it may help you avoid big surprises by letting you know if your checking was not adequate. To use the pre-tester, first submit your code. Then, type the following command. (Do this only after you have submitted, and only after you believe your submission is perfect.)

264test hw12

Do not ask TAs or instructors which tests you failed.

Keep in mind:

Pre-testing is intended only for those who believe they are done and believe their submission is perfect.
The pre-tester is not part of the requirements of this or any other assignment.
You are responsible for reading the assignment carefully, and ensuring that your code meets all requirements.
Feedback is limited, to ensure that everyone learns to test their own code.
If your code is failing some tests, review your tests and make sure they are comprehensive enough to catch any bugs (deviations from requirements). Follow the tips given by the pre-tester.
Code quality issues are not reported by the pre-tester; writing clean code is something you must learn to do from the start, not a clean-up step to do at the end.

Logistics:

If we discover that we have not checked some significant part of the assignment requirements, we may add additional tests at any time up to the point when scores are released.
The pre-tester will only be enabled after much of the class has submitted the assignment, and at least a few people have submitted perfect submissions. This is to allow us to test the pre-tester.
The pre-tester checks your most recent submission. You must submit first.
You may be limited to running the pre-tester ≤24 times in a 24-hour period. (This is not implemented yet but will be added.)

Q&A

Updates

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

Advanced C Programming

Fall 2017 :: ECE 264 :: Purdue University

Huffman #1 (E)

Getting Started

Overview

Structure defined

Requirements

Examples of `cmp_fn(…)` and `print_fn(…)`

Submit

Pre-tester ●

Q&A

Updates

Advanced C Programming

Fall 2017 :: ECE 264 :: Purdue University

Huffman #1 (E)

Getting Started

Overview

Structure defined

Requirements

Examples of cmp_fn(…) and print_fn(…)

Submit

Pre-tester ●

Q&A

Updates

Examples of `cmp_fn(…)` and `print_fn(…)`