辅导CSCI 2122、讲解program编程、c++程序语言辅导 讲解SPSS|讲解SPSS
- 首页 >> Java编程 Lab 6: Queues, Stacks, and Binary Trees
CSCI 2122 - Fall 2020
1 Introduction
This lab is designed to introduce you to queues, stacks, and binary trees. By the end of this lab, you will be expected
to understand those concepts. In the next lab we will be expanding your trees to encompass heaps (priority queues)
and we will be using queues and stacks to perform depth-first and breadth-first searches, so it’s important that you
do your best to understand the concepts laid out below.
In this lab you are expected to perform the basics of cloning your Lab 6 repository from the GitLab course group.
A link to the course group can be found here and your repository can be found in the Lab6 subgroup. See the
Lab Technical Document for more information on using git. You will notice that your repository has a file in the
Lab6 directory named delete this file. Due to the limitations of GitLab, we are not able to push completely empty
directories. Before you push your work to your repository (which should be in the Lab6 directory anyway), make
sure to first use the git rm command to remove the extra file. If you do not, your pipeline could fail.
Be sure to read this entire document before starting!
1
2 Queues
A queue is a common data structure which performs operations in a ”first in, first out” order. This is often abbreviated
as FIFO. A common analogy is to imagine that you are in line at the bank. The first person in line will be the first
person served at one of the tellers. In this case, it’s a first come, first served situation where the first ”thing” added
to the queue is also the first thing we work with when the time comes to do some processing.
In this lab, your task will be to implement a queue using any designs or libraries of your own make, including ones
you have written before in this class. The goal is that your queue should be able to hold any reasonable number of
items such that we are able to minimally perform the three basic queue operations: enqueue, dequeue, and peek.
In addition to the three basic queue operations, you’ll also be expected to provide size and contains function.
Your queue will have an initialization function, which should return a pointer to a typedefed struct called Queue
(see the Queue contract for more information). It should start as an array or list (your choice) and should have no
elements in it to start. Similar to previous labs, your queue will hold typeless data in the form of void pointers so
that you don’t have to worry about creating hard-typed queues.
2.1 enqueue
Whenever a user wants to add an item to a queue, they will need to call the enqueue function. The enqueue function
should accept a pointer to a Queue and a pointer to an element, then add that element to one end of its list. This
can be at the start of the list or the end of the list, as long as you are consistent every time. Every time an element
is added, the size of your queue should increase.
2.2 dequeue
Whenever a user wants to retrieve an item from a queue, they will need to call the dequeue function. The dequeue
function should accept a pointer to a Queue, then remove and return the item which has been in the queue the longest
in the form of a void pointer. Every time an element is removed, the size of your queue should decrease. The item
removed should be from the opposite end of the list compared to where you add (enqueue) them.
2.3 peek
A user is allowed to look at whatever the current oldest item is in your queue using the peek function. The peek
function should accept a pointer to a Queue, then return a void pointer representing the item at the front of the
queue, which should be the oldest item. Since the item is not removed, the size of the queue should not change.
2.4 size
The size function should return the number of items remaining in a Queue. It will accept a pointer to a Queue and
return an integer representing the number of items currently in that queue.
2.5 contains
The contains function will accept a pointer to a Queue and a void pointer to an element, then return true if the
element is currently in the queue. If the element is not in the queue, this should return false instead.
2
3 Stacks
Stacks are similar to queues in that they are also arrays/lists which contain some number of items, but instead of
being ”first in, first out” (FIFO), they are set up to be ”last in, first out” (LIFO). You are likely to hear about stacks
often throughout your university career in Computer Science, so now is a great time to get accustomed to how they
work! These instructions are largely similar to queues and will function the same, except in a few areas. We will only
talk about the differences below: assume anything we don’t mention is the same as the queues implementation.
In this lab, your task will be to implement a stack using any designs or libraries of your own make, including ones you
have written before in this class. The goal is that your stack should be able to hold any reasonable number of items
such that we are able to minimally perform the three basic stack operations: push, pop, and peek. In addition to
the three basic stack operations, you’ll also be expected to provide size and contains function.
Your stack will have an initialization function, which should return a pointer to a typedefed struct called Stack (see
the Stack contract for more information). It should start as an array or list (your choice) and should have no elements
in it to start. Similar to previous labs, your stack will hold typeless data in the form of void pointers so that you
don’t have to worry about creating hard-typed queues.
3.1 push
This function is similar to enqueue, except that we generally refer to items as being pushed to the top of the stack.
This can be either end of the list, similar to the queue, as long as you’re consistent.
3.2 pop
This function is similar to dequeue, except that it retrieves an item from the same end of the list at which the elements
are added. This means that whatever item was most recently pushed to the stack is the next item which will be
popped, not the oldest.
3.3 peek
The peek function is similar to the queue’s peek function, except it returns a pointer to the last element pushed to
the stack, not the oldest.
3
4 Binary Trees
Binary trees are a data structure which allows you to create a hierarchy of data by setting some condition on how
the data is stored. In computer science, binary trees are a very important data type as they allow you to store and
search for data quickly by following a relatively short series of steps in order to determine if the data you’re looking
for is present in your collection.
A binary tree can be represented in a number of ways, but in this lab we’re going to use a struct to define the
important components of a binary tree. In later labs we will be expanding on our binary trees to solve more complex
problems (such as priority queues and tree-search methods), but for now we will work with a very basic binary tree
and do some simple searches and traversals so we have an opportunity to learn exactly how they function.
A binary tree is made up a series of nodes (called tree nodes or vertices) and edges. An edge is a path which leads
from one node to another node as they’re joined together. Each node in a binary is allowed to have two such edges
leaving it, thus giving it the binary name. These edges point to other nodes, and the nodes they connect to are known
as the children of the node. A node which is pointing to such a child node is referred to as a parent node. Every
binary tree starts with a single node at the top, referred to as a root node, and traditionally builds downward,
although there’s no reason why you can’t flip it upside down and say it grows upward instead. A tree is technically a
specific type of graph, and you will learn more about graphs in your third year courses, such as Design and Analysis
of Algorithms I.
Since the tree only grows in one direction, we can make a few simple observations. First, a binary tree is directed,
meaning that the edges leaving a node point at other nodes, but those edges are not bi-directional. Thus, when a
node is added, it does not necessarily know who its parent is. There is also a condition such that a binary tree is not
allowed to have a cycle in it. A cycle is a series of edges/nodes such that if you start at some node V and follow
some series of edges, you will arrive back at V . A binary tree is not allowed to do this, and thus you never have to
worry about your nodes circling back around to places you’ve already been when you’re searching.
In the above image, you can see the basic anatomy of an integer-based binary tree. The node at the top (21) is the
root note, as it has no parent nodes. As integers are inserted into the binary tree, they follow a specific pattern for
determining where they should be placed in the tree. When an integer is added, we compare it to the value of the
root node. If it is less than the root node’s stored value, then we should add it on the left side of our tree. If it is
equal to, or greater than, the root node’s value, we should add it to the right side of our tree. For example, if we
wanted to add 13 to this tree, we would see 13 is less than 21, and thus we would want to add it on the left side,
which is referred to as the left subtree. We then compare 13 to 9, and seeing that it’s greater, we want to add it to
9’s right subtree, and then to the left subtree of 16.
In our diagram, we are designating edges to other nodes (pointers) in blue, and edges without nodes (which we can
imagine are null pointers). If we ever get to a point where we’re trying to add something to a subtree which is null,
we create a new node that holds the value we want to insert and update that edge to refer to the new node. In our
above example, 13 would be placed inside a node with two null edges and the left edge of 16’s node would point to
the new 13 node.
If you use some simple logic, you should notice that the integer binary tree actually sorts the values into ranges. For
example, the fact that the 16 is to the left of 21, and to the right of 9 suggests that it must fall in [9, 21], which is
obviously true. This extends to all values in the binary tree. For example, if a node is to the right of 24 and the left
of 33, so it must at least be in the range [24, 33]. In our example binary tree, we can see that the node is 27, and
thus the observation holds. This is an example of the sorting power of a binary tree.
While it’s possible to represent binary trees with just an array, we will be using a struct with pointers to enable us
to practice recursive algorithms. It turns out that from the point of view of a function working on a single node, any
position in the tree can be traversed to similar to the way you iterate through a linked list: by continuously updating
4
a function with the next node so you can perform the same action repeatedly until you arrive at the location you
desire. This is done via recursion and is a powerful tool for operating on tree structures.
4.1 Initializing a Binary Tree
In this lab, binary trees come with two structures: the tree itself and the individual nodes. A tree node consists of
three fields: the data (a void pointer), and a left and right pointer to another tree node. By default, the left and
right pointers of any node are set to null. As a tree grows, these are updated to reflect new nodes being added to the
left and right subtrees of each node. A tree consists of the things you’ve seen before, such as the name of the data
type it holds and the size of that data type. Similar to a linked list, it also holds a starting node so you always have
access to your root node.
In addition to those fields a binary tree will also contain two other variables: a function pointer to a compare
function, and a function pointer to a print function. These will be provided by the user during initialization and will
be used in your code to ensure your binary tree is built properly.
4.2 Inserting Values into a Binary Tree
In this lab, we will focus very simply on creating a binary tree of integers. As such, inserting values should be
relatively simple. First, if your binary tree does not yet have a root node, if you insert a value it can become your
first node. As mentioned above, this means creating a node, adding the data value to it, setting its child (left and
right) pointers to null, then setting it as the root node in the tree struct.
If there is already a root node, you will need to write a simple recursive function to find the correct place to insert
your value. Start at the root node and compare your inserted value to the root node’s value. If the inserted value is
less than the root node’s value, your node should be placed in the left subtree. Otherwise it should be placed in the
right subtree.
Once you have determined which subtree to place it in, you must first make a check to see if the subtree is null. If so,
make a node with the inserted value and have the root node’s correct child pointer point to it. If the subtree is not
null, you can recursively call your insertion function on the node in the designated subtree. Once a node has been
inserted, you can end your function with an appropriate return.
4.3 Searching a Binary Tree
To search a binary tree, we follow the same style of function as outlined above for inserting, with a few minor changes.
First, rather than creating nodes, we are checking to see if a given searched value matches any nodes along the way.
If we ever reach a node where the data in the node matches the data we’re searching for, we return true. However, if
we are searching and end up attempting to follow a subtree which should contain the value, but that subtree is null,
then the value must not exist in our tree, thus we should return false.
4.4 Printing the Values of a Binary Tree
One great feature of an integer-based binary tree is that it will naturally sort all of your data, and do so very quickly.
If you were to imagine reading the values from left-to-right based on their absolute ordering, you would end up with
the numbers printed in smallest-to-largest order. This particular order is referred to as an in-order traversal of the
binary tree, where a traversal is a way of moving from node-to-node in a tree following a specific pattern.
In order to achieve such a result, you can recursively perform a combination of value printing and pointer-following
in order to reach (and print) every node in the binary tree in a particular pattern. To print an in-order node pattern,
you would start at the root node. Recursively print the left subtree of the root node, then print the value of the root
node, then print the right subtree of the root node. If your recursive function is set up properly, you will traverse
and print the tree in the following way:
5
Since the algorithm we have defined only prints each node’s value after the left subtree has been printed, we will get the
values printed in left-to-right order. For this binary tree, that output would be {3, 9, 16, 21, 24, 27, 33, 42}.
There are several types of basic traversals which can be performed on a binary tree, as follows (including the one we
just discussed):
1. In-Order: Prints the state of the tree from left-to-right. Can be performed by recursively printing the left
subtree of a node, printing the node’s value, then recursively printing the right subtree of a node.
2. Pre-Order: Prints the state of the tree such that you print the value of the node, followed by recursively
printing the left subtree, then the right subtree.
3. Post-Order: Prints the state of the tree such that you recursively print the left subtree, followed by resurively
printing the right subtree, followed by printing the value of the node.
4. Reverse-Order: Prints the state of the tree from right-to-left. Performs the in-order operations in reverse.
4.5 The Compare and Print Functions
You may remember that your binary tree stores two function pointers. Because your binary tree relies on the typing of
your tree in order to make comparisons and to print values in traversals, the user initializing the binary tree is required
to pass in a function for comparing two values in the tree, as well as a function which can print a binary tree node value.
The compare function accepts two void pointers and returns an int. It should cast the two pointers to relevant
values, then compare them. It should output the following values based on the state of the values:
1. If the two values are considered equal, return 0.
2. If the second value is larger than the first value (or should appear later), return a value greater than 0.
3. If the second value is smaller than the first value (or should appear sooner), return a value less than 0.
The print function should accept a single void pointer and return nothing. Convert the pointer to an appropriate
value based on the binary tree’s type and print that value to the screen, followed by a single space.
4.6 Recursion on Binary Trees
We have explained recursion in previous labs, but can provide some extra tips here for how to handle recursion with
binary trees.
1. Remember that every node in your binary tree is the same as all of the others. This means it should be easy to
treat each node independently and make recursive calls on the children of the current node to continue moving
through the tree. If a function asks for a BinaryTreeNode as a pointer, odds are good we expect you to call
that function on a child node at each recursive step!
2. It is more efficient to test for NULL children in the current node and not recurse on a NULL pointer. This
saves a recursive step and should make your code easier to follow. Whenever possible, only make a recursive
call to a node that you know exists.
3. Remember to use the compare function stored in your tree to decide which child node to check. Creating a
compare function for integers is very simple, as you’re simply returning the difference between integer 2 and
integer 1.
4. Remember to use a return statement in front of your recursive calls when you expect them to be returning a
value. It makes your programs faster if you can make a guarantee to C that the return statement the last thing
a function does.
6
5 Lab 6 Function Contracts
In this lab you will be responsible for fulfilling three lab contracts: the Queue contract, the Stack contract, and the
Binary Tree contract. Each contract is designed to test you on some of the things you’ve learned throughout the
instruction portion of this lab.
All contracts must be completed exactly as the requirements are laid out. Be very careful to thoroughly read the
contract instructions before proceeding. This does not, however, preclude you from writing more functions than you
are asked for. You may write as many additional functions as you wish in your C source files.
All contracts are designed to be submitted without a main function, but that does not mean you cannot write a main
function in order to test your code yourself. It may be more convenient for you to write a C source file with a main
function by itself and take advantage of the compiler’s ability to link files together by accepting multiple source files
as inputs. When you push your code to Gitlab, you don’t need to git add any of your extra main function source files.
The programs you write for this lab will not be compiled with any additional libraries, as they should not be required.
For those of you who are concerned, when deciding which naming conventions you want to use in your code, favour
consistency in style, not dedication to a style that doesn’t work.
The contracts in this document are worth the following points values, for a total of 10.
Contract Points
Queue 3
Stack 3
Binary Tree 4
Total 10
7
5.1 Queue
5.1.1 Problem
You must create a structure and set of functions for managing a queue.
5.1.2 Preconditions
You are required to write a program for handling queues. This consists of queue.c, which should contain all of your
function implementations, and queue.h, which should contain your structure definition, any necessary typedefs, and
all of your forward function declarations. When you compile, you will need to include the source file in your command
in order to ensure the functions exist during the linking process. You may include any additional helper functions as
you see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are not
null. Trying to perform operations on null will lead to segmentation faults or other program crashes at run-time.
Your Queue is a typedeffed structure, but as long as the type works with all of the function contracts listed below,
you’re free to design your struct however you’d like.
The details of the queue functionality are described in the Queue section of this document. The bool type referenced
in this contract is found in. You are expected to do basic error checking (such as checking for
null pointers and correct index boundaries).
Your queue program must include the following struct (typedef-ed appropriately):
Structure Name Fields Functionality
Queue (typedef Queue) Any you’d like. Whatever you deem necessary.
Your queue program must include the following functions:
Requirement Conditions
Function Queue* queue initialize(int, char*)
Input Parameters An integer for setting the data type size and a string representing the name of the data
type being stored.
Return Value A pointer to an initialized Queue.
Notes None.
Requirement Conditions
Function bool queue enqueue(Queue*, void*)
Input Parameters A pointer to a Queue, and a void pointer to an element.
Return Value True if the element was successfully added to the queue. Otherwise false.
Notes This function should insert the given element at the end of the queue.
Requirement Conditions
Function void* queue dequeue(Queue*)
Input Parameters A pointer to a Queue.
Return Value A void pointer to the element that was removed.
Notes This function should remove the element at the front of the queue and return a pointer to it.
Requirement Conditions
Function void* queue peek(Queue*)
Input Parameters A pointer to a Queue.
Return Value A void pointer to the element at the front of the queue.
Notes This function should return a pointer to the element at the front of the queue.
Requirement Conditions
Function int queue size(Queue*)
Input Parameters A pointer to a Queue.
Return Value An integer representing the number of elements in the queue.
Notes None.
Requirement Conditions
Function bool queue contains(Queue*, void*)
Input Parameters A pointer to a Queue and a void pointer to an element.
Return Value True if the given item is in the queue. Otherwise false.
Notes None.
Requirement Conditions
Function bool queue destroy(Queue*)
Input Parameters A pointer to a Queue.
Return Value True if the queue is successfully deallocated. Otherwise false.
Notes This function should deallocate any remaining elements and then the queue itself.
5.1.3 Postconditions
Your program should be capable of producing and destroying Queue ( queue) structures. All of the functions should
be capable of executing without crashing. Failure states should be handled by return values. If a function with a
void return type fails, it does not need to be reported.
5.1.4 Restrictions
None.
8
5.1.5 File Requirements
This contract requires you to provide a C source file named queue.c and a C header file named queue.h. Your
header files should contain your forward declarations, struct definitions and typedefs, as well as any library imports
(includes) you may need. Always protect your header with a define guard. Your source files must not contain any
main functions when you submit, or your program will fail during marking.
In addition to the C files, you will also be required to make a Makefile for the queue program. Your program will
be compiled by executing make. Your Makefile should produce both an queue.o file and an queue executable file
by compiling your code with the queueM.o file located in CI/objects/queue.
Your source, header, and make files should be placed in the Lab6/queue/ directory in your GitLab repository.
5.1.6 Testing
To test your code, you can compile your source files with the queueM.o object file found in CI/objects/queue.
Your program can then be executed as normal. The object file contains a main function, so you do not need to
provide your own. Using a Makefile for compiling these files together can save you a lot of time.
5.1.7 Sample Inputs and Outputs
We provide a complete output file, but do not use it for comparison in the pipeline. The main object file for this
program will test your various functions on a Queue. Your code should minimally be able to complete the test main
function in the object file, but you may find it more convenient to test your functions with your own main function
first. Writing your own main function for testing purposes can be extremely helpful.
9
5.2 Stack
5.2.1 Problem
You must create a structure and set of functions for managing a stack.
5.2.2 Preconditions
You are required to write a program for handling stacks. This consists of stack.c, which should contain all of your
function implementations, and stack.h, which should contain your structure definition, any necessary typedefs, and
all of your forward function declarations. When you compile, you will need to include the source file in your command
in order to ensure the functions exist during the linking process. You may include any additional helper functions as
you see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are not
null. Trying to perform operations on null will lead to segmentation faults or other program crashes at run-time.
Your stack will hold a specific data type (and that data type only) as defined by the initialization parameters. The
size of the data type held is provided, as is the name.
The details of the stack functionality are described in the Stacks section of this document. The bool type referenced
in this contract is found in. You are expected to do basic error checking (such as checking for null
pointers and correct index boundaries).
Your stack program must include the following struct (typedef-ed appropriately):
Structure Name Fields Functionality
Stack (typedef Stack) Any you’d like. Whatever you deem necessary.
Your stack program must include the following functions:
Requirement Conditions
Function Stack* stack initialize(int, char*)
Input Parameters An integer for setting the data type size and a string representing the name of the data.
Return Value A pointer to an initialized Stack.
Notes None.
Requirement Conditions
Function bool stack push(Stack*, void*)
Input Parameters A pointer to a Stack, and a void pointer to an element.
Return Value True if the element was successfully pushed to the stack. Otherwise false.
Notes This function should push the given element to the top of the stack.
Requirement Conditions
Function void* stack pop(Stack*)
Input Parameters A pointer to a Stack.
Return Value A void pointer to the element that was popped.
Notes This function should pop an element off the top of the stack and return a pointer to it.
Requirement Conditions
Function void* stack peek(Stack*)
Input Parameters A pointer to a Stack.
Return Value A void pointer to the element on the top of the stack.
Notes This function should return a pointer to the element on the top of the stack.
Requirement Conditions
Function int stack size(Stack*)
Input Parameters A pointer to a Stack.
Return Value An integer representing the number of elements in the stack.
Notes None.
Requirement Conditions
Function bool stack contains(Stack*, void*)
Input Parameters A pointer to a Stack and a void pointer to an element.
Return Value True if the given item is in the stack. Otherwise false.
Notes None.
Requirement Conditions
Function bool stack destroy(Stack*)
Input Parameters A pointer to a Stack.
Return Value True if the stack is successfully deallocated. Otherwise false.
Notes This function should deallocate any remaining elements and then the stack itself.
5.2.3 Postconditions
Your program should be capable of producing and destroying Stack ( Stack) structures. All of the functions should
be capable of executing without crashing. Failure states should be handled by return values. If a function with a
void return type fails, it does not need to be reported.
5.2.4 Restrictions
None.
10
5.2.5 File Requirements
This contract requires you to provide a C source file named stack.c and a C header file named stack.h. Your
header files should contain your forward declarations, struct definitions and typedefs, as well as any library imports
(includes) you may need. Always protect your header with a define guard. Your source files must not contain any
main functions, or your program will fail during marking.
In addition to the C files, you will also be required to make a Makefile for the stack program. Your program will
be compiled by executing make. Your Makefile should produce both a stack.o file and a stack executable file by
compiling your code with the stackM.o file located in CI/objects/stack.
Your source, header, and make files should be placed in the Lab6/stack/ directory in your GitLab repository.
5.2.6 Testing
To test your code, you can compile your source files with the stackM.o object file found in CI/objects/stack. Your
program can then be executed as normal. The object file contains a main function, so you do not need to provide
your own when you submit to GitLab. Using a Makefile for compiling these files together can save you a lot of time.
5.2.7 Sample Inputs and Outputs
A sample output is provided, but is not used in a comparison when executing your pipeline. The main object file
for this program will test your various functions on a stack. Your code should minimally be able to complete the
test main function in the object file, but you may find it more convenient to test your functions with your own main
function first.
11
5.3 Binary Tree
5.3.1 Problem
You must create a structure and set of functions for managing a binary tree.
5.3.2 Preconditions
You are required to write a program for handling binary trees. This consists of bintree.c, which should contain
all of your function implementations, and bintree.h, which should contain your structure definitions, any necessary
typedefs, and all of your forward function declarations. When you compile, you will need to include the source file
in your command in order to ensure the functions exist during the linking process. You may include any additional
helper functions as you see fit. Since you are dealing with pointers, you will need to check all of your pointers to
ensure they are not null. Trying to perform operations on null will lead to segmentation faults or other program
crashes at run-time.
Your binary tree will hold a specific data type (and that data type only) as defined by the initialization parameters.
The size of the data type held is provided, as is the name. Each value stored in the binary tree should be of the given
size in bytes. For example, if your binary is initialized as an int binary tree, then the item size will be 4 and the type
name will be ”int”.
Your binary tree will contain a series of pointers to structs we will call nodes. Nodes contain the data hel
CSCI 2122 - Fall 2020
1 Introduction
This lab is designed to introduce you to queues, stacks, and binary trees. By the end of this lab, you will be expected
to understand those concepts. In the next lab we will be expanding your trees to encompass heaps (priority queues)
and we will be using queues and stacks to perform depth-first and breadth-first searches, so it’s important that you
do your best to understand the concepts laid out below.
In this lab you are expected to perform the basics of cloning your Lab 6 repository from the GitLab course group.
A link to the course group can be found here and your repository can be found in the Lab6 subgroup. See the
Lab Technical Document for more information on using git. You will notice that your repository has a file in the
Lab6 directory named delete this file. Due to the limitations of GitLab, we are not able to push completely empty
directories. Before you push your work to your repository (which should be in the Lab6 directory anyway), make
sure to first use the git rm command to remove the extra file. If you do not, your pipeline could fail.
Be sure to read this entire document before starting!
1
2 Queues
A queue is a common data structure which performs operations in a ”first in, first out” order. This is often abbreviated
as FIFO. A common analogy is to imagine that you are in line at the bank. The first person in line will be the first
person served at one of the tellers. In this case, it’s a first come, first served situation where the first ”thing” added
to the queue is also the first thing we work with when the time comes to do some processing.
In this lab, your task will be to implement a queue using any designs or libraries of your own make, including ones
you have written before in this class. The goal is that your queue should be able to hold any reasonable number of
items such that we are able to minimally perform the three basic queue operations: enqueue, dequeue, and peek.
In addition to the three basic queue operations, you’ll also be expected to provide size and contains function.
Your queue will have an initialization function, which should return a pointer to a typedefed struct called Queue
(see the Queue contract for more information). It should start as an array or list (your choice) and should have no
elements in it to start. Similar to previous labs, your queue will hold typeless data in the form of void pointers so
that you don’t have to worry about creating hard-typed queues.
2.1 enqueue
Whenever a user wants to add an item to a queue, they will need to call the enqueue function. The enqueue function
should accept a pointer to a Queue and a pointer to an element, then add that element to one end of its list. This
can be at the start of the list or the end of the list, as long as you are consistent every time. Every time an element
is added, the size of your queue should increase.
2.2 dequeue
Whenever a user wants to retrieve an item from a queue, they will need to call the dequeue function. The dequeue
function should accept a pointer to a Queue, then remove and return the item which has been in the queue the longest
in the form of a void pointer. Every time an element is removed, the size of your queue should decrease. The item
removed should be from the opposite end of the list compared to where you add (enqueue) them.
2.3 peek
A user is allowed to look at whatever the current oldest item is in your queue using the peek function. The peek
function should accept a pointer to a Queue, then return a void pointer representing the item at the front of the
queue, which should be the oldest item. Since the item is not removed, the size of the queue should not change.
2.4 size
The size function should return the number of items remaining in a Queue. It will accept a pointer to a Queue and
return an integer representing the number of items currently in that queue.
2.5 contains
The contains function will accept a pointer to a Queue and a void pointer to an element, then return true if the
element is currently in the queue. If the element is not in the queue, this should return false instead.
2
3 Stacks
Stacks are similar to queues in that they are also arrays/lists which contain some number of items, but instead of
being ”first in, first out” (FIFO), they are set up to be ”last in, first out” (LIFO). You are likely to hear about stacks
often throughout your university career in Computer Science, so now is a great time to get accustomed to how they
work! These instructions are largely similar to queues and will function the same, except in a few areas. We will only
talk about the differences below: assume anything we don’t mention is the same as the queues implementation.
In this lab, your task will be to implement a stack using any designs or libraries of your own make, including ones you
have written before in this class. The goal is that your stack should be able to hold any reasonable number of items
such that we are able to minimally perform the three basic stack operations: push, pop, and peek. In addition to
the three basic stack operations, you’ll also be expected to provide size and contains function.
Your stack will have an initialization function, which should return a pointer to a typedefed struct called Stack (see
the Stack contract for more information). It should start as an array or list (your choice) and should have no elements
in it to start. Similar to previous labs, your stack will hold typeless data in the form of void pointers so that you
don’t have to worry about creating hard-typed queues.
3.1 push
This function is similar to enqueue, except that we generally refer to items as being pushed to the top of the stack.
This can be either end of the list, similar to the queue, as long as you’re consistent.
3.2 pop
This function is similar to dequeue, except that it retrieves an item from the same end of the list at which the elements
are added. This means that whatever item was most recently pushed to the stack is the next item which will be
popped, not the oldest.
3.3 peek
The peek function is similar to the queue’s peek function, except it returns a pointer to the last element pushed to
the stack, not the oldest.
3
4 Binary Trees
Binary trees are a data structure which allows you to create a hierarchy of data by setting some condition on how
the data is stored. In computer science, binary trees are a very important data type as they allow you to store and
search for data quickly by following a relatively short series of steps in order to determine if the data you’re looking
for is present in your collection.
A binary tree can be represented in a number of ways, but in this lab we’re going to use a struct to define the
important components of a binary tree. In later labs we will be expanding on our binary trees to solve more complex
problems (such as priority queues and tree-search methods), but for now we will work with a very basic binary tree
and do some simple searches and traversals so we have an opportunity to learn exactly how they function.
A binary tree is made up a series of nodes (called tree nodes or vertices) and edges. An edge is a path which leads
from one node to another node as they’re joined together. Each node in a binary is allowed to have two such edges
leaving it, thus giving it the binary name. These edges point to other nodes, and the nodes they connect to are known
as the children of the node. A node which is pointing to such a child node is referred to as a parent node. Every
binary tree starts with a single node at the top, referred to as a root node, and traditionally builds downward,
although there’s no reason why you can’t flip it upside down and say it grows upward instead. A tree is technically a
specific type of graph, and you will learn more about graphs in your third year courses, such as Design and Analysis
of Algorithms I.
Since the tree only grows in one direction, we can make a few simple observations. First, a binary tree is directed,
meaning that the edges leaving a node point at other nodes, but those edges are not bi-directional. Thus, when a
node is added, it does not necessarily know who its parent is. There is also a condition such that a binary tree is not
allowed to have a cycle in it. A cycle is a series of edges/nodes such that if you start at some node V and follow
some series of edges, you will arrive back at V . A binary tree is not allowed to do this, and thus you never have to
worry about your nodes circling back around to places you’ve already been when you’re searching.
In the above image, you can see the basic anatomy of an integer-based binary tree. The node at the top (21) is the
root note, as it has no parent nodes. As integers are inserted into the binary tree, they follow a specific pattern for
determining where they should be placed in the tree. When an integer is added, we compare it to the value of the
root node. If it is less than the root node’s stored value, then we should add it on the left side of our tree. If it is
equal to, or greater than, the root node’s value, we should add it to the right side of our tree. For example, if we
wanted to add 13 to this tree, we would see 13 is less than 21, and thus we would want to add it on the left side,
which is referred to as the left subtree. We then compare 13 to 9, and seeing that it’s greater, we want to add it to
9’s right subtree, and then to the left subtree of 16.
In our diagram, we are designating edges to other nodes (pointers) in blue, and edges without nodes (which we can
imagine are null pointers). If we ever get to a point where we’re trying to add something to a subtree which is null,
we create a new node that holds the value we want to insert and update that edge to refer to the new node. In our
above example, 13 would be placed inside a node with two null edges and the left edge of 16’s node would point to
the new 13 node.
If you use some simple logic, you should notice that the integer binary tree actually sorts the values into ranges. For
example, the fact that the 16 is to the left of 21, and to the right of 9 suggests that it must fall in [9, 21], which is
obviously true. This extends to all values in the binary tree. For example, if a node is to the right of 24 and the left
of 33, so it must at least be in the range [24, 33]. In our example binary tree, we can see that the node is 27, and
thus the observation holds. This is an example of the sorting power of a binary tree.
While it’s possible to represent binary trees with just an array, we will be using a struct with pointers to enable us
to practice recursive algorithms. It turns out that from the point of view of a function working on a single node, any
position in the tree can be traversed to similar to the way you iterate through a linked list: by continuously updating
4
a function with the next node so you can perform the same action repeatedly until you arrive at the location you
desire. This is done via recursion and is a powerful tool for operating on tree structures.
4.1 Initializing a Binary Tree
In this lab, binary trees come with two structures: the tree itself and the individual nodes. A tree node consists of
three fields: the data (a void pointer), and a left and right pointer to another tree node. By default, the left and
right pointers of any node are set to null. As a tree grows, these are updated to reflect new nodes being added to the
left and right subtrees of each node. A tree consists of the things you’ve seen before, such as the name of the data
type it holds and the size of that data type. Similar to a linked list, it also holds a starting node so you always have
access to your root node.
In addition to those fields a binary tree will also contain two other variables: a function pointer to a compare
function, and a function pointer to a print function. These will be provided by the user during initialization and will
be used in your code to ensure your binary tree is built properly.
4.2 Inserting Values into a Binary Tree
In this lab, we will focus very simply on creating a binary tree of integers. As such, inserting values should be
relatively simple. First, if your binary tree does not yet have a root node, if you insert a value it can become your
first node. As mentioned above, this means creating a node, adding the data value to it, setting its child (left and
right) pointers to null, then setting it as the root node in the tree struct.
If there is already a root node, you will need to write a simple recursive function to find the correct place to insert
your value. Start at the root node and compare your inserted value to the root node’s value. If the inserted value is
less than the root node’s value, your node should be placed in the left subtree. Otherwise it should be placed in the
right subtree.
Once you have determined which subtree to place it in, you must first make a check to see if the subtree is null. If so,
make a node with the inserted value and have the root node’s correct child pointer point to it. If the subtree is not
null, you can recursively call your insertion function on the node in the designated subtree. Once a node has been
inserted, you can end your function with an appropriate return.
4.3 Searching a Binary Tree
To search a binary tree, we follow the same style of function as outlined above for inserting, with a few minor changes.
First, rather than creating nodes, we are checking to see if a given searched value matches any nodes along the way.
If we ever reach a node where the data in the node matches the data we’re searching for, we return true. However, if
we are searching and end up attempting to follow a subtree which should contain the value, but that subtree is null,
then the value must not exist in our tree, thus we should return false.
4.4 Printing the Values of a Binary Tree
One great feature of an integer-based binary tree is that it will naturally sort all of your data, and do so very quickly.
If you were to imagine reading the values from left-to-right based on their absolute ordering, you would end up with
the numbers printed in smallest-to-largest order. This particular order is referred to as an in-order traversal of the
binary tree, where a traversal is a way of moving from node-to-node in a tree following a specific pattern.
In order to achieve such a result, you can recursively perform a combination of value printing and pointer-following
in order to reach (and print) every node in the binary tree in a particular pattern. To print an in-order node pattern,
you would start at the root node. Recursively print the left subtree of the root node, then print the value of the root
node, then print the right subtree of the root node. If your recursive function is set up properly, you will traverse
and print the tree in the following way:
5
Since the algorithm we have defined only prints each node’s value after the left subtree has been printed, we will get the
values printed in left-to-right order. For this binary tree, that output would be {3, 9, 16, 21, 24, 27, 33, 42}.
There are several types of basic traversals which can be performed on a binary tree, as follows (including the one we
just discussed):
1. In-Order: Prints the state of the tree from left-to-right. Can be performed by recursively printing the left
subtree of a node, printing the node’s value, then recursively printing the right subtree of a node.
2. Pre-Order: Prints the state of the tree such that you print the value of the node, followed by recursively
printing the left subtree, then the right subtree.
3. Post-Order: Prints the state of the tree such that you recursively print the left subtree, followed by resurively
printing the right subtree, followed by printing the value of the node.
4. Reverse-Order: Prints the state of the tree from right-to-left. Performs the in-order operations in reverse.
4.5 The Compare and Print Functions
You may remember that your binary tree stores two function pointers. Because your binary tree relies on the typing of
your tree in order to make comparisons and to print values in traversals, the user initializing the binary tree is required
to pass in a function for comparing two values in the tree, as well as a function which can print a binary tree node value.
The compare function accepts two void pointers and returns an int. It should cast the two pointers to relevant
values, then compare them. It should output the following values based on the state of the values:
1. If the two values are considered equal, return 0.
2. If the second value is larger than the first value (or should appear later), return a value greater than 0.
3. If the second value is smaller than the first value (or should appear sooner), return a value less than 0.
The print function should accept a single void pointer and return nothing. Convert the pointer to an appropriate
value based on the binary tree’s type and print that value to the screen, followed by a single space.
4.6 Recursion on Binary Trees
We have explained recursion in previous labs, but can provide some extra tips here for how to handle recursion with
binary trees.
1. Remember that every node in your binary tree is the same as all of the others. This means it should be easy to
treat each node independently and make recursive calls on the children of the current node to continue moving
through the tree. If a function asks for a BinaryTreeNode as a pointer, odds are good we expect you to call
that function on a child node at each recursive step!
2. It is more efficient to test for NULL children in the current node and not recurse on a NULL pointer. This
saves a recursive step and should make your code easier to follow. Whenever possible, only make a recursive
call to a node that you know exists.
3. Remember to use the compare function stored in your tree to decide which child node to check. Creating a
compare function for integers is very simple, as you’re simply returning the difference between integer 2 and
integer 1.
4. Remember to use a return statement in front of your recursive calls when you expect them to be returning a
value. It makes your programs faster if you can make a guarantee to C that the return statement the last thing
a function does.
6
5 Lab 6 Function Contracts
In this lab you will be responsible for fulfilling three lab contracts: the Queue contract, the Stack contract, and the
Binary Tree contract. Each contract is designed to test you on some of the things you’ve learned throughout the
instruction portion of this lab.
All contracts must be completed exactly as the requirements are laid out. Be very careful to thoroughly read the
contract instructions before proceeding. This does not, however, preclude you from writing more functions than you
are asked for. You may write as many additional functions as you wish in your C source files.
All contracts are designed to be submitted without a main function, but that does not mean you cannot write a main
function in order to test your code yourself. It may be more convenient for you to write a C source file with a main
function by itself and take advantage of the compiler’s ability to link files together by accepting multiple source files
as inputs. When you push your code to Gitlab, you don’t need to git add any of your extra main function source files.
The programs you write for this lab will not be compiled with any additional libraries, as they should not be required.
For those of you who are concerned, when deciding which naming conventions you want to use in your code, favour
consistency in style, not dedication to a style that doesn’t work.
The contracts in this document are worth the following points values, for a total of 10.
Contract Points
Queue 3
Stack 3
Binary Tree 4
Total 10
7
5.1 Queue
5.1.1 Problem
You must create a structure and set of functions for managing a queue.
5.1.2 Preconditions
You are required to write a program for handling queues. This consists of queue.c, which should contain all of your
function implementations, and queue.h, which should contain your structure definition, any necessary typedefs, and
all of your forward function declarations. When you compile, you will need to include the source file in your command
in order to ensure the functions exist during the linking process. You may include any additional helper functions as
you see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are not
null. Trying to perform operations on null will lead to segmentation faults or other program crashes at run-time.
Your Queue is a typedeffed structure, but as long as the type works with all of the function contracts listed below,
you’re free to design your struct however you’d like.
The details of the queue functionality are described in the Queue section of this document. The bool type referenced
in this contract is found in
null pointers and correct index boundaries).
Your queue program must include the following struct (typedef-ed appropriately):
Structure Name Fields Functionality
Queue (typedef Queue) Any you’d like. Whatever you deem necessary.
Your queue program must include the following functions:
Requirement Conditions
Function Queue* queue initialize(int, char*)
Input Parameters An integer for setting the data type size and a string representing the name of the data
type being stored.
Return Value A pointer to an initialized Queue.
Notes None.
Requirement Conditions
Function bool queue enqueue(Queue*, void*)
Input Parameters A pointer to a Queue, and a void pointer to an element.
Return Value True if the element was successfully added to the queue. Otherwise false.
Notes This function should insert the given element at the end of the queue.
Requirement Conditions
Function void* queue dequeue(Queue*)
Input Parameters A pointer to a Queue.
Return Value A void pointer to the element that was removed.
Notes This function should remove the element at the front of the queue and return a pointer to it.
Requirement Conditions
Function void* queue peek(Queue*)
Input Parameters A pointer to a Queue.
Return Value A void pointer to the element at the front of the queue.
Notes This function should return a pointer to the element at the front of the queue.
Requirement Conditions
Function int queue size(Queue*)
Input Parameters A pointer to a Queue.
Return Value An integer representing the number of elements in the queue.
Notes None.
Requirement Conditions
Function bool queue contains(Queue*, void*)
Input Parameters A pointer to a Queue and a void pointer to an element.
Return Value True if the given item is in the queue. Otherwise false.
Notes None.
Requirement Conditions
Function bool queue destroy(Queue*)
Input Parameters A pointer to a Queue.
Return Value True if the queue is successfully deallocated. Otherwise false.
Notes This function should deallocate any remaining elements and then the queue itself.
5.1.3 Postconditions
Your program should be capable of producing and destroying Queue ( queue) structures. All of the functions should
be capable of executing without crashing. Failure states should be handled by return values. If a function with a
void return type fails, it does not need to be reported.
5.1.4 Restrictions
None.
8
5.1.5 File Requirements
This contract requires you to provide a C source file named queue.c and a C header file named queue.h. Your
header files should contain your forward declarations, struct definitions and typedefs, as well as any library imports
(includes) you may need. Always protect your header with a define guard. Your source files must not contain any
main functions when you submit, or your program will fail during marking.
In addition to the C files, you will also be required to make a Makefile for the queue program. Your program will
be compiled by executing make. Your Makefile should produce both an queue.o file and an queue executable file
by compiling your code with the queueM.o file located in CI/objects/queue.
Your source, header, and make files should be placed in the Lab6/queue/ directory in your GitLab repository.
5.1.6 Testing
To test your code, you can compile your source files with the queueM.o object file found in CI/objects/queue.
Your program can then be executed as normal. The object file contains a main function, so you do not need to
provide your own. Using a Makefile for compiling these files together can save you a lot of time.
5.1.7 Sample Inputs and Outputs
We provide a complete output file, but do not use it for comparison in the pipeline. The main object file for this
program will test your various functions on a Queue. Your code should minimally be able to complete the test main
function in the object file, but you may find it more convenient to test your functions with your own main function
first. Writing your own main function for testing purposes can be extremely helpful.
9
5.2 Stack
5.2.1 Problem
You must create a structure and set of functions for managing a stack.
5.2.2 Preconditions
You are required to write a program for handling stacks. This consists of stack.c, which should contain all of your
function implementations, and stack.h, which should contain your structure definition, any necessary typedefs, and
all of your forward function declarations. When you compile, you will need to include the source file in your command
in order to ensure the functions exist during the linking process. You may include any additional helper functions as
you see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are not
null. Trying to perform operations on null will lead to segmentation faults or other program crashes at run-time.
Your stack will hold a specific data type (and that data type only) as defined by the initialization parameters. The
size of the data type held is provided, as is the name.
The details of the stack functionality are described in the Stacks section of this document. The bool type referenced
in this contract is found in
pointers and correct index boundaries).
Your stack program must include the following struct (typedef-ed appropriately):
Structure Name Fields Functionality
Stack (typedef Stack) Any you’d like. Whatever you deem necessary.
Your stack program must include the following functions:
Requirement Conditions
Function Stack* stack initialize(int, char*)
Input Parameters An integer for setting the data type size and a string representing the name of the data.
Return Value A pointer to an initialized Stack.
Notes None.
Requirement Conditions
Function bool stack push(Stack*, void*)
Input Parameters A pointer to a Stack, and a void pointer to an element.
Return Value True if the element was successfully pushed to the stack. Otherwise false.
Notes This function should push the given element to the top of the stack.
Requirement Conditions
Function void* stack pop(Stack*)
Input Parameters A pointer to a Stack.
Return Value A void pointer to the element that was popped.
Notes This function should pop an element off the top of the stack and return a pointer to it.
Requirement Conditions
Function void* stack peek(Stack*)
Input Parameters A pointer to a Stack.
Return Value A void pointer to the element on the top of the stack.
Notes This function should return a pointer to the element on the top of the stack.
Requirement Conditions
Function int stack size(Stack*)
Input Parameters A pointer to a Stack.
Return Value An integer representing the number of elements in the stack.
Notes None.
Requirement Conditions
Function bool stack contains(Stack*, void*)
Input Parameters A pointer to a Stack and a void pointer to an element.
Return Value True if the given item is in the stack. Otherwise false.
Notes None.
Requirement Conditions
Function bool stack destroy(Stack*)
Input Parameters A pointer to a Stack.
Return Value True if the stack is successfully deallocated. Otherwise false.
Notes This function should deallocate any remaining elements and then the stack itself.
5.2.3 Postconditions
Your program should be capable of producing and destroying Stack ( Stack) structures. All of the functions should
be capable of executing without crashing. Failure states should be handled by return values. If a function with a
void return type fails, it does not need to be reported.
5.2.4 Restrictions
None.
10
5.2.5 File Requirements
This contract requires you to provide a C source file named stack.c and a C header file named stack.h. Your
header files should contain your forward declarations, struct definitions and typedefs, as well as any library imports
(includes) you may need. Always protect your header with a define guard. Your source files must not contain any
main functions, or your program will fail during marking.
In addition to the C files, you will also be required to make a Makefile for the stack program. Your program will
be compiled by executing make. Your Makefile should produce both a stack.o file and a stack executable file by
compiling your code with the stackM.o file located in CI/objects/stack.
Your source, header, and make files should be placed in the Lab6/stack/ directory in your GitLab repository.
5.2.6 Testing
To test your code, you can compile your source files with the stackM.o object file found in CI/objects/stack. Your
program can then be executed as normal. The object file contains a main function, so you do not need to provide
your own when you submit to GitLab. Using a Makefile for compiling these files together can save you a lot of time.
5.2.7 Sample Inputs and Outputs
A sample output is provided, but is not used in a comparison when executing your pipeline. The main object file
for this program will test your various functions on a stack. Your code should minimally be able to complete the
test main function in the object file, but you may find it more convenient to test your functions with your own main
function first.
11
5.3 Binary Tree
5.3.1 Problem
You must create a structure and set of functions for managing a binary tree.
5.3.2 Preconditions
You are required to write a program for handling binary trees. This consists of bintree.c, which should contain
all of your function implementations, and bintree.h, which should contain your structure definitions, any necessary
typedefs, and all of your forward function declarations. When you compile, you will need to include the source file
in your command in order to ensure the functions exist during the linking process. You may include any additional
helper functions as you see fit. Since you are dealing with pointers, you will need to check all of your pointers to
ensure they are not null. Trying to perform operations on null will lead to segmentation faults or other program
crashes at run-time.
Your binary tree will hold a specific data type (and that data type only) as defined by the initialization parameters.
The size of the data type held is provided, as is the name. Each value stored in the binary tree should be of the given
size in bytes. For example, if your binary is initialized as an int binary tree, then the item size will be 4 and the type
name will be ”int”.
Your binary tree will contain a series of pointers to structs we will call nodes. Nodes contain the data hel