Assignment 4 Specification
COMP 2401BD Fall 2022 − "Introduction to Systems Programming"
Assignment 4 Specification | Due Nov. 16th at 11:59PM
COMP 2401 B/D (Updated: Nov. 4th)
Assignment #4: Tracking the Hunt
Collections and Pointers
Goals:
For this assignment, you will write a program in C, in the Ubuntu Linux environment of the course VM, that allows the use
to manage their estimated likelihood of various “ghosts” and the rooms they might be in by storing them in different data
structures.
Learning Outcomes:
If you are keeping up with the lectures, completing tutorials, and read the course notes as needed, then by the end of this
assignment you will have demonstrated that you can:
● Write a program that manipulates collections using encapsulated functionality
● Implement different kinds of collections, including an a
ay of pointers and a singly linked list with a tail
● Practice writing code that manages multiple pointers to the same data
Assignment Context (Optional Read):
Excellent stuff with that evidence database! Now that our team is able to track evidence in real time, they’re able to make
some better guesses about the kinds of spooky ghosts (or neighbourhood bullies, I guess) that are wandering the
uildings.
This week, you’ll be building another data manager that will help us track the estimated likelihood of which kinds of spirits
(or otherwise) are in each room. You’ll need to track a list of rooms, and each room has a list of ghosts that we think might
e in it. Each ghost has a type, and a likelihood of it being in that room based on the evidence we collected using you
previous work. We’ll also give a unique ID to each one, to make sure our likelihoods aren’t getting all confused. Long term,
we want to be able to track lots of different ghost types and information, so our Building data should track both a list of
ooms and a list of all the suspected ghosts.
This program is just a proof-of-concept, though, so we won’t be checking against our full database of ghost types just yet.
We’ll keep it simple for our junior hunters - we’ve expanded our club to include a once-weekly after school program fo
local children looking for some fun scares, but they have to be home before 8:00PM. One of them was inspired by you
decryption algorithm and even started working with Arduino coding!
Oh, and we’ll be keeping an eye out for any rooms we think were set up by the local bullies. Real or not, I don’t think they
get this is all for fun.
1
COMP 2401BD Fall 2022 − "Introduction to Systems Programming"
Assignment 4 Specification | Due Nov. 16th at 11:59PM
Overview:
For this assignment, you must make sure that you are following the good code practices that we’ve been following for the
previous assignments. This assignment is quite similarly structured to the previous assignment, but you’ll be working with
data that’s pointed to in multiple locations. Be extra careful to have no memory leaks, and to avoid accessing freed data.
You must read and understand the code that has been provided to you. In this assignment, you will be compiling
programs with multiple files. We have not yet talked about the “good” way to compile and link using Makefiles, so we will
e using a somewhat “bad” way of compiling. For example, if your program contains three source files file1.c, file2.c, and
file3.c, then you can use the following command to create an executable called a4: gcc -o a4 file1.c file2.c
file3.c
(You may use Makefiles if you wrote each line of the Makefile yourself and you provide reproducible instructions for the TA
in your README)
For this assignment, you will be writing the code to manage a Ghost database. There are Buildings, and each Building
maintains a collection of all Ghosts in the building and all Rooms. Each Room maintains a collection of Ghosts in that
oom. Each Ghost tracks the Room it is in and uses an enumerated type to track what type of ghost it is, and the
likelihood that the ghost is actually present (a floating point value between 0.0 and 100.0, but you do not need to validate
this).
The implementation details are important to follow - while some of the approaches to data structures and operations
may not be “optimal”, they are here to provide you with practice with pointers and freeing memory in more complex
scenarios.
Provided Code:
Your submission must separate the program’s functions into the following source files, with structures, forward
declarations, and constant definitions in the defs.h file:
● main.c : main(), printMenu()
● building.c : initBuilding(), loadBuildingData(), cleanupBuilding()
● ghost.c : initGhostList(), initGhost(), addGhost(), addGhostByLikelihood(),
printGhosts(), printByLikelihood(), printGhost(), cleanupGhostData(),
cleanupGhostList()
● room.c : initRoomA
ay(), initRoom(), addRoom(), printRooms(), cleanupRoomA
ay()
You will need to create function prototypes, forward declarations, and structs as defined in the instructions below.
Deductions Reminder: All of the standard penalties and requirements continue to apply. You may add additional helpe
functions if they help you to better organize and otherwise write cleaner code, but otherwise you should not modify the
code or structure of code unless specified.
Print Formatting: There is no specified way of printing. The print formatting may be assessed, but it is up to you to
make sure that it is printed in a nice and legible way. Group like data together, make sure to print all data of the structures,
make sure that data is in a consistent “shape” (eg. fixed-size columns) and make sure that each element of a list is visibly
separated. It does not need to be perfect, but it should be easy to read and understand at a glance.
2
COMP 2401BD Fall 2022 − "Introduction to Systems Programming"
Assignment 4 Specification | Due Nov. 16th at 11:59PM
Instructions:
Data Structures
While there is some inference required for the exact definitions of these data structures, make sure that all of the data
structures follow the notes below. You must define the following data types:
1. RoomA
ayType: A static a
ay containing many ghosts. The RoomA
ayType contains an elements field, which
must be declared as a statically allocated a
ay of GhostType pointers. You will set the maximum capacity to an existing,
predefined constant, and the structure must contain a size field to track the cu
ent number of ghosts in the elements
a
ay.
2. GhostListType: A singly linked list meant to hold NodeType elements which point to GhostTypes. It must have both a
head and a tail.
3. NodeType: The NodeType works with the GhostListType structure to implement a singly linked list of GhostType
data.
4. BuildingType: This is a kind of “Overall Data” collection, which represents a building in our data, and holds all of the
data at a higher level for us to reference. It contains two statically allocated fields: A linked list of ghosts, stored as a
GhostListType, and a static a
ay of rooms, stored as an instance of the RoomA
ayType.
Generally, you can think of the structures as:
● A room contains many ghosts
● A ghost is in one room
● The building contains a list of every ghost and an a
ay every room, like a big database
● We are only storing one copy of each room and ghost in memory, outside of temporary variables
1. Implement the ghost management functions
1.1. Implement the void initGhostList(GhostListType *list) function that initializes both fields of the given
list parameter to default values. Since collections always begin as empty, the head and tail of the list should be
set to NULL.
1.2. Implement the void initGhost(int id, GhostEnumType gt, RoomType *r, float like, GhostType
**ghost) function that dynamically allocates memory for a GhostType structure, initializes its fields to the
given parameters, and “returns” this new structure using the ghost parameter.
1.3. Implement the void addGhost(GhostListType *list, GhostType *ghost) function that adds the ghost
directly at the back (i.e. the end) of the given list. The linked list must be implemented as we saw in class,
specifically with no dummy nodes.
1.4. Implement the void addGhostByLikelihood(GhostListType *list, GhostType *ghost) function that
adds the ghost to the given list, directly in its co
ect place, in descending order by likelihood. You must
implement this by finding the co
ect insertion point in the list, as we saw in class, and inserting the new ghost.
Do not add to the end of the list and then sort. Do not use any sorting function or algorithm.
1.5. Implement the void cleanupGhostData(GhostListType *list) function that traverses the given list and
deallocates its data only.
1.6. Implement the void cleanupGhostList(GhostListType *list) function that traverses the given list and
deallocates its nodes only.
3
COMP 2401BD Fall 2022 − "Introduction to Systems Programming"
Assignment 4 Specification | Due Nov. 16th at 11:59PM
1.7. Implement the void printGhost(GhostType *ghost) function that prints to the screen every field of the given
ghost. The ghost type must be printed as a descriptive string (e.g. “Poltergeist”, “Wraith”, “Phantom”, “Bullies”,
“Other”, or “Unknown"). The name of the ghost’s room must be printed out as well, or the string “Unknown” if
the ghost has no room specified.
1.8. Implement the void printGhosts(GhostListType *list, int ends) function that prints every ghost in
the given list to the screen, using an existing function. If the ends parameter is set to C_TRUE, then the two
ghosts at the head and tail of the linked list must be printed out a second time, after all the ghosts have been
output. If the ends parameter is set to C_FALSE, then the head and tail are not printed a second time at the
end.
1.9. Implement the void printByLikelihood(GhostListType *origList, int ends) function that prints
every ghost in the given list to the screen, in decreasing order by likelihood. The function must be implemented
as follows:
(a) declare a temporary list as a local variable, and initialize it as empty
(b) traverse the given list origList, and add each of its data elements to the temporary list, in descending
order by ghost likelihood; do not make copies of the data! The temporary list is a separate list with its
own unique nodes, but with pointers to the same data as the original list
(c) print out the ghosts in the temporary list, using the given ends parameter as described in 1.8
(d) clean up the memory for the temporary list, without deallocating the data because the same data is still
used in the original list
NOTE: You must reuse existing functions everywhere possible.
2. Implement the room management functions
2.1. Implement the void initRoomA
ay(RoomA
ayType *a
) function that initializes the fields of the given
RoomA
ayType structure that require initialization. In this case, the size of the