” CSCI 2122 写作、c++程序调试Lab 6: Queues, Stacks, and Binary TreesCSCI 2122 – Winter 20211 IntroductionThis lab is designed to introduce you to queues, stacks, and binary trees. By the end of this lab, you will be expectedto 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 its important that youdo 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 theLab Technical Document for more information on using git. You will notice that your repository has a file in theLab6 directory named delete this file. Due to the limitations of GitLab, we are not able to push completely emptydirectories. Before you push your Work to your repository (which should be in the Lab6 directory anyway), makesure 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!12 QueuesA queue is a common data structure which performs operations in a first in, first out order. This is often abbreviatedas FIFO. A common analogy is to imagine that you are in line at the bank. The first person in line will be the firstperson served at one of the tellers. In this case, its a first come, first served situation where the first thing addedto 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 onesyou have written before in this class. The goal is that your queue should be able to hold any reasonable number ofitems 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, youll 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 noelements in it to start. Similar to previous labs, your queue will hold typeless data in the form of void pointers sothat you dont have to worry about creating hard-typed queues.2.1 enqueueWhenever a user wants to add an item to a queue, they will need to call the enqueue function. The enqueue functionshould accept a pointer to a Queue and a pointer to an element, then add that element to one end of its list. Thiscan be at the start of the list or the end of the list, as long as you are consistent every time. Every time an elementis added, the size of your queue should increase.2.2 dequeueWhenever a user wants to retrieve an item from a queue, they will need to call the dequeue function. The dequeuefunction should accept a pointer to a Queue, then remove and return the item which has been in the queue the longestin the form of a void pointer. Every time an element is removed, the size of your queue should decrease. The itemremoved should be from the opposite end of the list compared to where you add (enqueue) them.2.3 peekA user is allowed to look at whatever the Current oldest item is in your queue using the peek function. The peekfunction should accept a pointer to a Queue, then return a void pointer representing the item at the front of thequeue, which should be the oldest item. Since the item is not removed, the size of the queue should not change.2.4 sizeThe size function should return the number of items remaining in a Queue. It will accept a pointer to a Queue andreturn an integer representing the number of items currently in that queue.2.5 containsThe contains function will accept a pointer to a Queue and a void pointer to an element, then return true if theelement is currently in the queue. If the element is not in the queue, this should return false instead.23 StacksStacks are similar to queues in that they are also arrays/lists which contain some number of items, but instead ofbeing first in, first out (FIFO), they are set up to be last in, first out (LIFO). You are likely to hear about stacksoften throughout your university career in Computer Science, so now is a great time to get accustomed to how theywork! These instructions are largely similar to queues and will function the same, except in a few areas. We will onlytalk about the differences below: assume anything we dont 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 youhave written before in this class. The goal is that your stack should be able to hold any reasonable number of itemssuch that we are able to minimally perform the three basic stack operations: push, pop, and peek. In addition tothe three basic stack operations, youll 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 (seethe Stack contract for more information). It should start as an array or list (your choice) and should have no elementsin it to start. Similar to previous labs, your stack will hold typeless data in the form of void pointers so that youdont have to worry about creating hard-typed queues.3.1 pushThis 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 youre consistent.3.2 popThis function is similar to dequeue, except that it retrieves an item from the same end of the list at which the elementsare added. This means that whatever item was most recently pushed to the stack is the next item which will bepopped, not the oldest.3.3 peekThe peek function is similar to the queues Peek function, except it returns a pointer to the last element pushed tothe stack, not the oldest.34 Binary TreesBinary trees are a data structure which allows you to create a hierarchy of data by setting some condition on howthe data is stored. In computer science, binary trees are a very important data type as they allow you to store andsearch for data quickly by following a relatively short series of steps in order to determine if the data youre lookingfor is present in your collection.A binary tree can be represented in a number of ways, but in this lab were going to use a struct to define theimportant components of a binary tree. In later labs we will be expanding on our binary trees to solve more complexproblems (such as priority queues and tree-search methods), but for now we will work with a very basic binary treeand 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 leadsfrom one node to another node as theyre joined together. Each node in a binary is allowed to have two such edgesleaving it, thus giving it the binary name. These edges point to other nodes, and the nodes they connect to are knownas the children of the node. A node which is pointing to such a child node is referred to as a parent node. Everybinary tree starts with a single node at the top, referred to as a root node, and traditionally builds downward,although theres no reason why you cant flip it upside down and say it grows upward instead. A tree is technically aspecific type of graph, and you will learn more about graphs in your third year courses, such as Design and Analysisof 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 anode is added, it does not necessarily know who its parent is. There is also a condition such that a binary tree is notallowed to have a cycle in it. A cycle is a series of edges/nodes such that if you start at some node V and followsome series of edges, you will arrive back at V . A binary tree is not allowed to do this, and thus you never have toworry about your nodes circling back around to places youve already been when youre searching.In the above image, you can see the basic anatomy of an integer-based binary tree. The node at the top (21) is theroot note, as it has no parent nodes. As integers are inserted into the binary tree, they follow a specific pattern fordetermining where they should be placed in the tree. When an integer is added, we compare it to the value of theroot node. If it is less than the root nodes stored value, then we should add it on the left side of our tree. If it isequal to, or greater than, the root nodes value, we should add it to the right side of our tree. For example, if wewanted 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 its greater, we want to add it to9s 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 canimagine are null pointers). If we ever get to a point where were 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 ourabove example, 13 would be placed inside a node with two null edges and the left edge of 16s node would point tothe new 13 node.If you use some simple logic, you should notice that the integer binary tree actually sorts the values into ranges. Forexample, 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 isobviously true. This extends to all values in the binary tree. For example, if a node is to the right of 24 and the leftof 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, andthus the observation holds. This is an example of the sorting power of a binary tree.While its possible to represent binary trees with just an array, we will be using a struct with pointers to enable usto practice recursive algorithms. It turns out that from the point of view of a function working on a single node, anyposition in the tree can be traversed to similar to the way you iterate through a linked list: by continuously updating4a function with the next node so you can perform the same action repeatedly until you arrive at the location youdesire. This is done via recursion and is a powerful tool for operating on tree structures.4.1 Initializing a Binary TreeIn this lab, binary trees come with two structures: the tree itself and the individual nodes. A tree node consists ofthree fields: the data (a void pointer), and a left and right pointer to another tree node. By default, the left andright pointers of any node are set to null. As a tree grows, these are updated to reflect new nodes being added to theleft and right subtrees of each node. A Tree consists of the things youve seen before, such as the name of the datatype it holds and the size of that data type. Similar to a linked list, it also holds a starting node so you always haveaccess to your root node.In addition to those fields a binary tree will also contain two other variables: a function pointer to a comparefunction, and a function pointer to a print function. These will be provided by the user during initialization and willbe used in your code to ensure your binary tree is built properly.4.2 Inserting Values into a Binary TreeIn this lab, we will focus very simply on creating a binary tree of integers. As such, inserting values should berelatively simple. First, if your binary tree does not yet have a root node, if you insert a value it can become yourfirst node. As mentioned above, this means creating a node, adding the data value to it, setting its child (left andright) 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 insertyour value. Start at the root node and compare your inserted value to the root nodes value. If the inserted value isless than the root nodes value, your node should be placed in the left subtree. Otherwise it should be placed in theright 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 nodes correct child pointer point to it. If the subtree is notnull, you can recursively call your insertion function on the node in the designated subtree. Once a node has beeninserted, you can end your function with an appropriate return.4.3 Searching a Binary TreeTo 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 were searching for, we return true. However, ifwe 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 TreeOne 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 withthe numbers printed in smallest-to-largest order. This particular order is referred to as an in-order traversal of thebinary 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-followingin 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 rootnode, then print the right subtree of the Root node. If your recursive function is set up properly, you will traverseand print the tree in the following way:5Since the algorithm we have defined only prints each nodes value after the left subtree has been printed, we will get thevalues 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 wejust discussed):1. In-Order: Prints the state of the tree from left-to-right. Can be performed by recursively printing the leftsubtree of a node, printing the nodes 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 recursivelyprinting 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 resurivelyprinting 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 FunctionsYou may remember that your binary tree stores two function pointers. Because your binary tree relies on the typing ofyour tree in order to make comparisons and to print values in traversals, the user initializing the binary tree is requiredto 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 relevantvalues, 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 appropriatevalue based on the binary trees type and print that value to the screen, followed by a single space.Here, you can see the compare and Print functions provided to your binary trees initialize function:1 int compareInt ( void * a , void * b)2 {3 return *(( int *) b) – *(( int *) a);4 }56 void printInt ( void * a)7 {8 printf (%d , *(( int *) a ));9 }4.6 Recursion on Binary TreesWe have explained recursion in previous labs, but can provide some extra tips here for how to handle recursion withbinary trees.1. Remember that every node in your binary tree is the same as all of the others. This means it should be easy totreat each node independently and make recursive calls on the children of the current node to continue movingthrough the tree. If a function asks for a BinaryTreeNode as a pointer, odds are good we expect you to callthat 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. Thissaves a recursive step and should make your code easier to follow. Whenever possible, only make a recursivecall 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 acompare function for integers is very simple, as youre simply returning the difference between integer 2 andinteger 1.4. Remember to use a return statement in front of your recursive calls when you expect them to be returning avalue. It makes your programs faster if you can make a guarantee to C that the return statement the last thinga function does.65 Lab 6 Function ContractsIn this lab you will be responsible for fulfilling three lab contracts: the Queue contract, the Stack contract, and theBinary Tree contract. Each contract is designed to test you on some of the things youve learned throughout theinstruction portion of this lab.All contracts must be completed exactly as the requirements are laid out. Be very careful to thoroughly read thecontract instructions before proceeding. This does not, however, preclude you from writing more functions than youare 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 mainfunction in order to test your code yourself. It may be more convenient for you to write a C source file with a mainfunction by itself and take advantage of the compilers ability to link files together by accepting multiple source filesas inputs. When you push your code to Gitlab, you dont 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, favourconsistency in style, not dedication to a style that doesnt work.The contracts in this document are worth the following points values, for a total of 10.Contract PointsQueue 3Stack 3Binary Tree 4Total 1075.1 Queue5.1.1 ProblemYou must create a structure and set of functions for managing a queue.5.1.2 PreconditionsYou are required to write a program for handling queues. This consists of queue.c, which should contain all of yourfunction implementations, and queue.h, which should contain your structure definition, any necessary typedefs, andall of your forward function declarations. When you compile, you will need to include the source file in your commandin order to ensure the functions exist during the linking process. You may include any additional helper functions asyou see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are notnull. 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,youre free to design your struct however youd like.The details of the queue functionality Are described in the Queue section of this document. The bool type referencedin this contract is found in stdbool.h. You are expected to do basic error checking (such as checking fornull pointers and correct index boundaries).Your queue program must include the following struct (typedef-ed appropriately):Structure Name Fields FunctionalityQueue (typedef Queue) Any youd like. Whatever you deem necessary.Your queue program must include the following functions:Requirement ConditionsFunction Queue* queue initialize(int, char*)Input Parameters An integer for setting the data type size and a string representing the name of the datatype being stored.Return Value A pointer to an initialized Queue.Notes None.Requirement ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 PostconditionsYour program should be capable of producing and destroying Queue ( queue) structures. All of the functions shouldbe capable of executing without crashing. Failure states should be handled by return values. If a function with avoid return type fails, it does not need to be reported.5.1.4 RestrictionsNone.85.1.5 File RequirementsThis contract requires you to provide a C source file named queue.c and a C header file named queue.h. Yourheader 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 anymain 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 willbe compiled by executing make. Your Makefile should produce both an queue.o file and an queue executable fileby 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 TestingTo 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 toprovide your own. Using a Makefile for compiling these files together can save you a lot of time.5.1.7 Sample Inputs and OutputsWe provide a complete output file, but do not use it for comparison in the pipeline. The main object file for thisprogram will test your various functions on a Queue. Your code should minimally be able to complete the test mainfunction in the object file, but you may find it more convenient to test your functions with your own main functionfirst. Writing your own main function for testing purposes can be extremely helpful.95.2 Stack5.2.1 ProblemYou must create a structure and set of functions for managing a stack.5.2.2 PreconditionsYou are required to write a program for handling stacks. This consists of stack.c, which should contain all of yourfunction implementations, and stack.h, which should contain your structure definition, any necessary typedefs, andall of your forward function declarations. When you compile, you will need to include the source file in your commandin order to ensure the functions exist During the linking process. You may include any additional helper functions asyou see fit. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are notnull. 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. Thesize 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 referencedin this contract is found in stdbool.h. You are expected to do basic error checking (such as checking for nullpointers and correct index boundaries).Your stack program must include the following struct (typedef-ed appropriately):Structure Name Fields FunctionalityStack (typedef Stack) Any youd like. Whatever you deem necessary.Your stack program must include the following functions:Requirement ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 ConditionsFunction 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 PostconditionsYour program should be capable of producing and destroying Stack ( Stack) structures. All of the functions shouldbe capable of executing without crashing. Failure states should be handled by return values. If a function with avoid return type fails, it does not need to be reported.5.2.4 RestrictionsNone.105.2.5 File RequirementsThis contract requires you to provide a C source file named stack.c and a C header file named stack.h. Yourheader 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 anymain functions, or your program will fail during marking.In addition to the C files, you will also be required to make a Makefile f”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
