” 辅导CMPUT 201编程、 写作C/C++CMPUT 201 – Winter 2021Assignment 3Dynamic memory allocationLinked ListsProgram organizationHeader files and MakefilesAdhering to provided code stubsProgram testingAssertsIF YOU HAVE NOT EXPLICITLY TOLD US YOU WANT TO WORK IN A PAIR, THENYOU ARE WORKING INDIVIDUALLY FOR THIS ASSIGNMENT. You will still have a teamname assigned to you But this team will only have 1 member: you.Before clicking on the github classroom link below, please check your assigned team nameon eClass first. The process for joining a team is as before (if you are the first one to join,you will create the team on GitHub classroom; if you are working with a partner and theyalready joined, you will simply find the team name on the list and click on it).The github classroom assignment invitation link is httpss://classroom.github.com/g/UJKMgYrf. READ BELOW BEFORE CLICKING ON THISLINKAt thte end, you will have a repository with the following name: httpss://gihub.com/cmput201-w21/assignment3-asgmt3_teamNN .Please update the LICENSE.md file with only your name (if working individually) or bothpartner names (if working in a pair) where it says student nameYour GitHub starter repo is a bit different this time: you will already find the two foldersConcepts CoveredGitHub Instructionsfor Part 1 and Part 2 of the assignment. In each part, you will find the header file you needto adhere to and a sample C client file. Additionally, you will find a script calledcheck.sh in the main directory. Simply run ./check.sh to run the script againstyour code. Documentation on what the script checks for can be found at the top of thescript. Note that your program should not fail any of the assert checks we have in the clientcode. Please read the RepoStructure.md to understand the files provided in therepo and how to find and interpret the Github Actions build statusMake sure to continuously commit and to your repository as you are developing yourassignment and not simply when you are done. This serves two purposes: (1) you alwayshave a backup of your code and can navigate through history to see your changes or revertback to an old version of the code that worked better and (2) showing your progressthrough the assignment allows us to see each partners contribution. Additionally, thesecommits are a great way to show your changes and contributions if you are suspected ofplagiarism. To avoid overloading GitHub actions, you can commit locally as much as youwant but push only once every Hour or at the end of your current working session (or whenyou want to communicate your changes to your partner). We strongly recommend that youwatch the git tutorials on YouTube to avoid running into merge conflicts while working withyour partner on the assignment.This assignment consists of two parts. For both parts of the assignment, we will bechecking for memory leaks; if you remove an element or nuke a list, or anything likethat, dont forget to clean up and free any allocated memory as necessary. Thegeneral rule is if you dynamically allocate any memory yourself, you need to free it yourselftoo. You can use valgrind to check for memory leaks.You must use dynamic memory allocation in this assignment. If you do not, you willget a 0, even if your program behaves correctlyYour program must compile using -std=c99 -Wall without any warnings or errors. Ifwe cannot compile your program or if it compiles with a warning, you will receive a 0for the assignment.Any missing files will result in a 0 in the assignment. Please check the list of files your needto submit for each part. If you forget the README, Makefile, etc., you will get a 0. Pleasemake use of the script we already provide you in your repo to check the format ofyour submission.You need only 1 ReadMe file in the Root folder of your repository. Please see httpss://www.makeareadme.com/ for information about how to create a good ReadMe file,especially in markdown notation. Your README file should also have a references sectionImportant Informationthat lists your references (e.g., any online resources you used) and the contributions of bothpartners (if working in a team).You must adhere to the provided function prototypes. You are free to add extra helperfunctions, but you must implement the given functions without changing their signature.Credits: This assignment has been adapted from one of Mike Godfreys assignments.Were going to implement a data structure called Squeue , because its a bit like both a Stackand a Queue, that allows new elements to be added / removed / peeked at both ends of the list.A Squeue supports the following operations (details to follow): initSqueue ,isEmpty , addFront , leaveFront , mergeFront , peekFront , addBack ,leaveBack , peekBack , mergeBack , print , and nuke . initSqueue andisEmpty do the obvious things.The four operations addFront , leaveFront , mergeFront and peekFrontoperate on the front of the list.The four operations addBack , leaveBack , peekBack and mergeBack operateon the back of the list.It is essential that you use the EXACT function prototypes provided. Otherwise, we willnot be able to compile and test your code and you will get a 0.Were going to implement our Squeue by using Nodes that have links in both directions(forwards and backwards), plus we are Going to keep two special pointers: one to the firstelement and one to the last element. The following shows the structs we expect.struct Node{char* val;struct Node* next;struct Node* prev;};typdef struct{struct Node* first;struct Node* last;} Squeue;You must implement the Squeue using the exact structs above. We have provided you with aPart I (50 marks)header file that contains all the signatures of all functions you need to implement. You will findthis header file in a folder called Part1 in your GitHub repo. Here is the list again anyways(detailed description of the functions follows):void initSqueue (Squeue **squeue);bool isEmpty (const Squeue *squeue);void addFront (Squeue *squeue, char *val);void addBack (Squeue *squeue, char *val);void leaveFront (Squeue *squeue);char* peekBack (const Squeue *squeue);void leaveBack (Squeue *squeue);char* peekFront (const Squeue * squeue);void print (const Squeue * squeue, char direction);void nuke (Squeue * squeue);void mergeFront(Squeue* squeue, char direction);void mergeBack(Squeue* squeue, char direction);void reverse(Squeue* squeue);void destroySqueue(Squeue **squeue);The following is an example of a Main program that shows what is expected from each function.int main1 () {Squeue *s1 = NULL;initSqueue (s1);addFront (s1, alpha);addFront (s1, beta);addFront (s1, gamma);addBack (s1, delta);printf(This prints \gamma beta alpha delta\ across four lines with a tab before each element, and preceded by \squeue is:\ on its own line:\n);print (s1, f);printf(This prints \delta alpha beta gamma\ across four lines with a tab before each element, and preceded by \stack is:\ on its own line:\n);print (s1, r);mergeFront(s1, f);printf(This prints \gammabeta alpha delta\ across three lines with a tab before each element, and preceded by \squeue is:\ on its own line:\n);print(s1, f);mergeBack(s1, r);printf(This prints \gammabeta deltaalpha\ across two lines with a tab before each element, and preceded by \squeue is:\ on its own line:\n);print(s1, f);leaveFront (s1);printf(This prints \deltaalpha\ in one line with a tab before each element, and preceded by \squeue is:\ on its own line:e\n);print(s1, f);addFront(s1, zeta);addFront(s1, eta);leaveBack (s1);void initSqueue (struct Squeue ** squeue);initSqueue initializes the given squeue to an empty squeue. After calling initSqueueon a given squeue , we should be able to add elements to that squeue by callingaddFront or addBack .bool isEmpty (const struct Squeue * squeue);isEmpty checks if the given Squeue is empty. Returns true if it is empty and false ifnot.void addFront (struct Squeue * squeue, char* val);addFront adds the given string (i.e., val ) to the front of the given squeue. Make sure youadjust all pointers of the squeue appropriately. You need to dynamically allocate memoryfor the new string. You cannot assume any maximum size for the string.printf(This prints \eta zeta\ across two lines with a tab before each element, and preceded by \squeue is:\ on its own line:\n);print(s1, f);printf(This prints \eta zeta\ in one line \n);printf(%s %s\n, peekFront(s1), peekBack(s1));printf(This nuke has no output, but is good form to call when done\n);nuke (s1);printf(This assertion should succeed\n);assert (isEmpty (s1));printf(Illegal direction should cause error message\n);print (s1, k);addBack (s1, alpha);addBack (s1, beta);addBack (s1, gamma);reverse(s1);printf(This prints \gamma beta alpha\ across two lines with a tab before each element, and preceded by \squeue is:\ on its own line:\n);print(s1, f);destroySqueue(s1); //we will always call this for any squeue we test with so make sure it is implemented correctly to free any allocated memoryreturn 0;}Detailed function descriptionsvoid addBack (struct Squeue * squeue, char* val);addBack adds the given string (i.e., val) to the back of the given squeue. Make sure youadjust all pointers of the squeue appropriately. You need to dynamically allocate memoryfor the new string. You cannot assume any maximum size for the string.void leaveFront (struct Squeue * squeue);leaveFront deletes the first element from the front of the given squeue. Make sure youadjust all pointers of the squeue appropriately and delete any unneeded struct instances.The first line of the function should be: assert (!isEmpty(s)); to ensure that you donttry accessing elements from an empty squeue.void leaveBack (struct Squeue *squeue);leaveBack deletes the last element at the back of the given squeue. Make sure you adjustall pointers appropriately and Delete any unneeded struct instances. The first line of the functionshould be: assert (!isEmpty(s)); to ensure that you dont try accessing elements froman empty squeue.char* peekFront (const struct Squeue * squeue);peekFront returns the value of the first element from the front of the squeue withoutchanging the squeue. The first line of the function should be: assert (!isEmpty(s)); toensure that you dont try accessing elements from an empty squeue.char* peekBack (const struct Squeue *squeue);peekBack returns the value of the last element from the back of the squeue withoutchanging the squeue. The first line of the function should be: assert (!isEmpty(s)); toensure that you dont try accessing elements from an empty squeue.void print (const struct Squeue * squeue, char direction);print takes a Squeue and a single char that represents the direction, f for forwardand r for reverse, and then prints the squeue in the desired direction. If the direction passedin is not f or r, then print the following message to stderr:Error, illegal direction entered direction . Note thatentered direction must be replaced by the direction passed in as an arugment. Forexample, if the function was called with direction b , the message printed to stderr will beError, illegal direction b . If an illegal direction is detected, just print thatmessage; do not try to print the contents of squeue , and do not exit the program ormake an assertion that could cause the program to abort. To output elements of the stack,the function prints squeue is: on a line, followed by each element on its own line. Eachelement is preceded with a tab. See example code.void nuke (struct Squeue * squeue);nuke takes a Squeue , deletes all of the internal Nodes, and sets the first and last pointersof the Squeue instance to NULL .void mergeFront(struct Squeue* squeue, char direction);mergeFront takes a Squeue and a single char that represents the direction, f forforward and r for reverse. It concatenates the two strings contained in the first two nodes ofthe squeue in the desired direction, stores the concatenated string in the first node, and thendeletes the second node. See the Provided main function example above to understand whatmergeFront does. Note that it is an error if you call mergeFront on a squeue withless than 2 nodes. You should have an assert to check for this. If the direction passed in isnot f or r, then print the following message to stderr:Error, illegal direction entered direction . Note thatentered direction must be replaced by the direction passed in as an arugment. Forexample, if the function was called with direction b , the message printed to stderr will beError, illegal direction b . If an illegal direction is detected, just print thatmessage; do not try to do the merge, and do not exit the program or make an assertionthat could cause the program to abort.void mergeBack(struct Squeue* squeue, char direction);mergeBack takes a Squeue and a single char that represents the direction, f forforward and r for reverse. It concatenates the two strings contained in the last two nodes ofthe squeue in the desired direction, stores the concatenated string in the node before last, andthen deletes the last node. See the provided main function example above to understand whatmergeBack does. Note that it is an error if you call mergeBack on a squeue with lessthan 2 nodes. You should have an assert to check for this. If the direction passed in is not for r, then print the following message to stderr:Error, illegal direction entered direction . Note thatentered direction must be replaced by the direction passed in as an arugment. Forexample, if the function was called with direction b , the message printed to stderr will beError, illegal direction b . If an illegal direction is detected, just print thatmessage; do not try to do the merge, and do not exit the program or make an assertionthat could cause the program to abort.void reverse(Squeue* squeue);reverses the elements in the given squeue. If the squeue was a-b-c-d , where firstpoints to a and last points to d , calling reverse would change the squeue contents tod-c-b-a , and make first point to d and last point to a .void destroySqueue(Squeue **squeue);destroySqueue safely deletes all members of the given squeue as well as any memoryallocated for squeue. After calling destroySqueue on a given squeue , that squeuewould point to NULL .In the Part1 folder on GitHub, you must submit the following files:squeue.h — already there. Do not change the prototypes we provide; you mayadd prototypes for your helper functions though.squeue.c . This file contains the Definitions of all the functions declared insqueue.h . This is the file that contains all your implementation code.squeue_client.c . This file must contain ONLY the main function and#include stdio.h , #include assert.h ,#include stdlib.h , and #include squeue.h . We have provided youa sample file in your repository for testing purposes. When we mark your program, wewill be creating our own main function to test your program. Therefore, we will replaceyour squeue_client.c so if you have anything other than main in there, we willno longer have access to that functionality. NOTE: the local test scripts and GitHubActions check the output of the code we provided in squeue_client.c . Donot change this file, or otherwise the expected output will not match theprograms output and the tests will fail. To create your own tests, you can addyour own C file with your own main function (e.g. bucketstack_test.c and createa separate test target in your Makefile). You can watch this YouTube video tounderstand how to do that.Makefile that correctly compiles and links the code in the above three files into anexecutable called squeue . Your Makefile must have the clean target.If your Makefile does not compile the above files into an executable called squeueDeliverables of Part IGrading of Part Iwith no errors or warnings, you will get a 0 for this part1 mark: clean target works correctly.40 marks: Correct functionality of all expected functions.9 marks: no memory leaks. You will not get these 9 marks if you got 0 for the correctfunctionality part since, obviously, if you implement nothing, you will have nomemory leaks :-)If global variables are used, 10 marks will be taken off your total gradeLinked lists have many advantages over, say, statically allocated approaches. For example, if wewere limited to only statically allocated storage, then one way to implement a stack would be byusing an array to hold the elements, and keeping track of the top element by keeping an integerindex to the top element, as Depicted in Figure 1. The obvious disadvantage of this approach isthat there is an upper bound on how many elements the stack can hold at the same time (here,the bound is 100). Additionally, you must allocate the whole array at once; if you were using onlya small percentage of the available elements most of the time, then you could be wasting a lot ofspace depending on how big the array was. Another problem is that you will need to know themaximum of a string. The advantages of this approach over a linked list are simplicity andspeed: linked lists are easy to get wrong, and with an array you have direct access to allelements (thats not much of an advantage for a stack, but it would be if the Abstract Data Type(ADT) required immediate access to any given element).Compare this to using a linked list approach shown in class. Each element is stored in its ownnode, so there is a storage overhead of one pointer (typically, about four bytes) per element.Also, while creating and deleting new nodes are constant time operations in principle, if real-timePart II (50 marks)performance is a big concern, they can be relatively expensive operations compared to justaccessing an array element.In this assignment, you will investigate a hybrid approach, which we are going to call a BucketStack. An example is shown in Figure 2.Basically, we are going to use a linked list approach, but instead of just one element, each nodewill contain an array of bucketSize elements, for some constant bucketSize . Thismeans that the stack will be unbounded, but that there will be a storage overhead of only onepointer per bucketSize elements (instead of one per element). Of course, this might meansome wasted space, but that will amount to at most bucketSize – 1 elements at any givenmoment. The second diagram shows an example of a Bucket Stack with seven elements and abucketSize of 5. The order of insertion was: alpha , beta , gamma , delta ,epsilon , zeta , eta . Note how topElt in this representation stores the index of thecurrent element at the top of the stack. For simplicity, the diagram shows each string as a directelement in the array. Technically, each element of the array is a char * and the memory forthe string will be dynamically Allocated so we can store any size string we want.Note that because we want to be flexible about the bucket size, you will have to use adynamically allocated array as discussed in class. You will also use two different kinds of structs,one called Stack for the stack itself (the green box) and one called NodeBucket for thevarious nodes (the yellow boxes) that store the elements (or more precisely, store pointers to thedynamic arrays that store the elements).To implement this, you will use the following struct definitions. They are also provided in theheader file you will find in the Part2 folder in your GitHub repo.struct NodeBucket {char** val;struct NodeBucket* next;};typedef struct {struct NodeBucket* firstBucket;int topElt;int bucketSize;} Stack;The prototypes for the functions you must implement are given below; thes are included in theprovided header file.void initStack (int bucketSize, Stack **stack);bool isEmpty (const Stack *stack);void push (char* val, Stack *stack);void pop(Stack *stack);int size (const Stack *stack);char* top (const Stack *stack);void swap (Stack *stack);void print (const Stack *stack);void clear(Stack *stack);void destroyStack(Stack **stack);Any given stack has a fixed bucketSize (a positive integer), which is set when you initializeit via initStack ; that is, any NodeBucket belonging to this stack will have the samenumber of elements, bucketSize , for a given stack. However, you should note that twodifferent stacks can have different bucketSizes .Here is an example of a main function that uses the above bucketstack:int main (int argc, char* argv[]) {Stack *s = NULL;initStack (3, s);push(alpha, s);printf(This prints \alpha\:\n);printf(%s\n, top(s));push(beta, s);printf(This prints \beta\:\n);printf(%s\n, top(s));push (gamma, s);printf(This prints \gamma\:\n);printf(%s\n, top(s));push (delta, s);printf(This prints \delta\:\n);printf(%s\n, top(s));printf(This will print the whole stack with a tab before each element:\delta gamma beta alpha\ across 4 lines, preceded by \stack is:\ on a line on its own\n);print(s);clear(s);printf(This will print an empty stack so just \stack is:\\n);print(s);void initStack (int bucketSize, struct Stack **stack);initStack creates an empty stack with the given bucketSize. Remember that thefirstBucket of an empty BucketStack is NULL .bool isEmpty (const struct Stack *stack);isEmpty returns true if the stack is empty, and false otherwise.push (alice, s);printf(This will print a stack that only contains \alice\\n);print(s);pop (s);printf(This will print an empty stack so just \stack is:\\n);print(s);push (bob, s);push (bob, s);printf(This will print the whole stack with a tab before each element:\bob bob\ across 2 lines, preceded by \stack is:\ on a line on its own\n);;print(s);push(mike, s);printf(This will print the whole stack with a tab before each element:\mike bob bob\ across 3 lines, preceded by \stack is:\ on a line on its own\n);;print(s);swap(s);printf(This will print the whole stack after swapping first two with a tab before each element:\bob mike bob\ across 3 lines, preceded by \stack is:\ on a line on its own\n);;print(s);clear(s);printf(This will print an empty stack so just \stack is:\\n);print(s);destroyStack(s); //we will always call this for any stack we test with so make sure it is implemented correctly to free any allocated memoryreturn 0}Detailed Function Descriptionsvoid push (char* val, struct Stack *stack);push pushes the provided string on to the given stack. You need to dynamically allocatememory for the new string. You cannot assume any maximum size for the string. Note thatpush needs to check if the current firstNodeBucket is full; if so, anotherNodeBucket needs to be allocated and linked in place.void pop(struct Stack *stack);pop pops the top element from the given stack. Note that the value of the popped string is notreturned. Also, note that pop needs to check if the element being removed is the last one inthe current first NodeBucket ; if so, that NodeBucket should be deleted (and so should itsdynamic array), and the appropriate links should be adjusted. At the beginning of the popfunction, assert that the stack is not empty.int size (const struct Stack *stack);size returns the current number of elements in the Stack; it would return 7 for the example inthe diagram.char* top (const struct Stack *stack);top returns the top string on the stack WITHOUT removing it from the stack. At the beginningof the top function, assert that the stack is not empty.void swap (struct Stack *stack);swap swaps the top two elements. In the example shown in the diagram, zeta and etawould change positions. Hint: there is one tricky case you have to consider. Note that its anerror if swap is called when there are fewer than two elements; you should use assert tocheck this.void print (const struct Stack *stack);print prints stack is: on one line followed by the contents of the stack from top tobottom, where each string is displayed on a line preceded by a tab character. In the exampleabove, invoking print on the current stack would display:stack is:etazetaepsilondeltagammabetaalphavoid clear(struct Stack *stack);clear deletes all contents of the stack and adjusts firstBucket , bucketSize , andtopElt accordingly.void destroyStack(Stack **stack);destroyStack completely destroys the stack. This means it deletes all contents of thestack, as well as the memory allocated for the Stack struct. Calling destroyStack on anystack (whether it has elements or not) should always clean up any memory. After caling thedestroyStack function, the stack that was passed in would point to NULL .General Hint: When you test your program on your own, try different values of bucketSize .Two good corner case examples are 1 (effectively giving you a linked list stack) and, say, 100(effectively giving you an array stack). Try some other values too. Also, test different cases:when you have exactly bucketSize elements, when you have one less thanbucketSize elements, when you have one more than bucketSize elements (to see ifyou correctly create a new NodeBucket ). The idea is to make sure your program workscorrectly at boundary values where programming mistakes typically happen. Also, think oftesting corner cases or error-handling behavior. For example, reversing popping an emptystack or reversing a stack with 0 or 1 elements.In the Part2 folder on GitHub, you must submit the following files:bucketstack.h — already there. Do not change the prototypes we provide;you may add helper functions though.bucketstack.c . This file contains the definitions of all the functions declared inbucketstack.h . This file contains all your implementation for this part.bucketstack_client.c . This file must contain ONLY a main function and#include stdio.h , #include assert.h ,Deliverables of Part II#include stdlib.h , and #include bucketstack.h . We haveprovided you a sample file in your repository for testing purposes. When we mark yourprogram, we will be creating our own main function to test your program. Therefore,we will replace your bucketstack_client.c file so if you have anything otherthan main in there, we will no longer have access to that functionality. NOTE: the localtest scripts and GitHub actions check the output of the code we provided. Donot change this file, or otherwise the expected output will not match theprograms output and the tests will fail. To create your own tests, you can addyour own C file with your own main function (e.g. bucketstack_test.c andcreate a separate test target test in your Makefile. See this YouTube video foran explanation of how you can do that).Makefile that correctly compiles and links all the code in the above 3 files into anexecutable called bucketstack . Your Makefile must have the clean target.If your Makefile does does not compile the above files into an executable calledbucketstack with no errors or warnings, you will get a 0 for this part1 mark: make clean works as expected40 marks: Correct functionality of all expected functions.9 marks: no memory leaks. You will not get these 9 marks if you got 0 for the correctfunctionality part since, obviou”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
