Assignment 9 Solution

Mac users, bad news! Since I don’t want you to be overwhelmed by the unnecessary complexity of the valgrind tool on MacOS, for this assignment, you are asked to work in a UNIX/Linux box such as Google Cloud, the gargamel server, or your personal computer running Linux.




Introduction to Circularly Linked List


A circularly linked list contains a list of nodes, each of which has a next pointer pointing to the next node in the list and a reference to an element. Unlike a singly linked list whose last node’s next pointer is null, in a circularly linked list, it points back to the first node. Thus, there is actually neither first nor last node. If we traverse the nodes of a circularly linked list from any node by following next pointers, we will cycle through the nodes. Even though a circularly linked list has no beginning or end, we nevertheless need some node to be marked as a special node, which we call the cursor. It allows us to have a place to start from and know where we currently are if we ever need to traverse a circularly linked list. And if we remember this starting point, then we can also know when we are done – we are done with a traversal of a circularly linked list when we return to the node that was the cursor node when we started. We can define some methods for a circularly linked list:




void *insert(void *cursor, void *name);
Creates a new node by calling malloc(). For the Josephus program as described below, the name of the soldier comes in as the second argument.

Inserts the new node immediately after the cursor; if the list is empty, then this new node becomes the cursor and its next pointer points to itself.

Returns the pointer pointing the new node as the new cursor.


void *release(void *cursor);
Removes the node immediately after the cursor.

Returns the current cursor. If the list becomes empty, return null.




void *advance(void *cursor);
Advances the cursor to the next node in the list and returns it.




void print(void *cursor);
Prints the node pointed by cursor.




For the Josephus program as described below, the name of the soldier is printed.







The Josephus Problem




In this project, you will use a circularly linked list to simulate the Josephus problem.




Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction (AD 70).  During the Jewish-Roman war he was trapped in a cave with a group of 39 soldiers surrounded by Romans.  The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding clockwise around it, to kill every seventh person until only one was left, who must then commit suicide.  Josephus, an accomplished mathematician, quickly found the safe spot in the circle (24th) to be the last to go.  But when the time came, instead of killing himself he joined the Roman side.  The problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand.




Program Details




Although it is totally up to you how you design your program, it needs to satisfy the following rules:




It consists of at least 2 source files (.c files) and at least 2 header files (.h files). One of the header files is provided to you as cl.h. It contains 4 functions as described in the first section above. Your program for the Circular Linked List must implement these 4 functions, no more, no less.
It takes the names of the soldiers and the elimination order from the user.
It is organized in the following way:

bin_files/ : a subfolder that holds executable file(s)
obj_files/ : a subfolder that holds object file(s)
inc_files/ : a subfolder that holds header file(s)
src_files/ : a subfolder that holds source file(s)
It comes with a workable makefile.
Very importantly, when testing your program, use valgrind to check memory leaks. There should be none.



Please find a sample output below.

User it verify the correctness of your program.










What to submit?



Create a tar ball by the name of cs3335_a9_yourlastname.tar that contains your entire program folder.




Submit the tar ball file through BlazeVIEW by the due time.