Who Gets the Cake $($Part $2)$

Learning Goals

Insert and delete nodes in a linked list

Changes from HW$01$ Cake

In HW$01$ Cake, an array is used to keep track who is still in the game. In this assignment, a linked list is used. The output of your program should match the output of HW$01$ Cake. In addition, the linked list is printed every time one number is removed.

The files in expected directory have $-$DDEBUG in Makefile to turn on the code printing the lists starting from the nodes to be eliminated. If Makefile does not have $-$DDEBUG, the outputs should be the same as the files in HW$01$ Cake.

Initialize Pointers

You should always initialize pointers to NULL. Uninitialized pointers can make your programs' behavior unpredictable.

Printing ListNode

You should call printListNode each time BEFORE you delete any node and print the node value. In the expected files, printListNode is not called for the last value in the list. Follow the expected files format. You can turn on the DEBUG flag in your Makefile for printing.

Helpful Notes

For this assignment, it will be beneficial to first complete createList and deleteNode functions before trying to complete eliminate, as these are important building blocks for the eliminate function, which is the most complicated piece of this assignment. While working on createList and deleteNode, you are encouraged to write your own test cases to ensure your code is working as expected.

Code template:

$//***$

$//***$ You MUST modify this file

$//***$

#include

#include

#include

#include

#include $"$hw$10.$h$"$

$//$ DO NOT MODIFY this function $--->>>$

void printListNode$($ListNode$*$ head$)$

$\{$

ListNode$*$ p $=$ head;

printf$("$printListNode: $")$;

while $($p $!=$ NULL$)$

$\{$

printf$("\%7$d $",$ p $->$ value$)$;

p $=$ p $->$ next;

$\}$

printf$("$

$")$;

$\}$

$//<<<---$ until here

$//$ create a linked list storing values $0,1,2,...$ valn $-1$

$//$ The first node $($head$)$ stores $0,$ the next node stores $1,$

$//...,$ the last node stores valn $-1$

$//$ return the head of the linked list

ListNode$*$ createList$($int valn$)$

$\{$

return NULL;

$\}$

$//$ eliminate the nodes in the linked list

$//$ starting from the head, move one node at a time and count to valk.

$//$ eliminate that node, keep counting

$//$

$//$ when reaching the end of the list, continue from the beginning of

$//$ the list

$//$

$//$ print the values of the nodes to be deleted

void eliminate$($ListNode$*$ head, int valk$)$

$\{$

#ifdef DEBUG

$//$ this #ifdef $...$ #endif should be inside the condition $*$BEFORE$*$ a

$//$ node' value is printed and it is deleted

ListNode $*$ todelete $=$ p;

printListNode $($todelete$)$;

#endif

$\}$

$//$ head points to the first node in the linked list

$//$ todelete points to the node to be deleted

$//$

$//$ delete the node and return the head of the linked list

$//$ release the memory of the deleted node

$//$

$//$ should check several conditions:

$//1.$ If head is NULL, the list is empty and this function returns

$//$ NULL

$//2.$ If todelete is NULL, nothing can be deleted, return head

$//3.$ If todelete is not in the list, keep the list unchanged and

$//$ return head

$//$ It is possible that todelete is the first node in the list $($i$.$e$.,$

$//$ the head$).$ If this occurs, return the second node of the list.

ListNode$*$ deleteNode$($ListNode$*$ head, ListNode$*$ todelete$)$

$\{$

return NULL;

$\}$

main file:

$//***$

$//***$ You may modify this file but don't submit it$.$

$//***$

#include

#include

#include

#include $"$hw$10.$h$"$

int main$($int argc, char$**$ argv$)$

$\{$

if $($argc $!=3)$

$\{$

fprintf$($stderr$,$ "need two numbers

$")$;

return EXIT$\_$FAILURE;

$\}$

int valn $=($int$)$ strtol$($argv$[1],$ NULL, $10)$;

int valk $=($int$)$ strtol$($argv$[2],$ NULL, $10)$;

if $(($valn $<=1)||($valk $<=1))$

$\{$

return EXIT$\_$FAILURE;

$\}$

ListNode $*$ head $=$ NULL;

head $=$ createList$($valn$)$;

eliminate$($head$,$ valk$)$;

return EXIT$\_$SUCCESS;

$\}$

make file:

# $***$

# $***$ You may modify this file but don't submit it$.$

# $***$

WARNING $=-$Wall $-$Wshadow $--$pedantic

ERROR $=-$Wvla $-$Werror

GCC $=$ gcc $-$std$=$c$11-$g $$($WARNING$)$ $$($ERROR$)$

TESTFLAGS $=-$DDEBUG

SRCS $=$ main.c hw$10.$c

OBJS $=$ $$($SRCS:$\%.$c$=\%.$o$)$

hw$10$: $$($OBJS$)$

$$($GCC$)$ $$($TESTFLAGS$)$ $$($OBJS$)-$o hw$10$

$.$c$.$o:

$$($GCC$)$ $$($TESTFLAGS$)-$c $$*.$c

testall: test$1$ test$2$ test$3$

test$1$: hw$10$

$./$hw$1063>$ output$1$

diff output$1$ expected$/$expected$1$

test$2$: hw$10$

$./$hw$1064>$ output$2$

diff output$2$ expected$/$expected$2$

test$3$: hw$10$

$./$hw$10257>$ output$3$

diff output$3$ expected$/$expected$3$

memory: hw$10$

# You may consider using other flags for valgrind, such as $--$leak$-$check$=$full, to ensure that your program has absolutely no memory errors

valgrind $./$hw$10125$

clean: # remove all machine generated files

rm $-$f hw$10*.$o output? $*$~