Microsoft Word - Project-3.docx CS 2413 – Data Structures – Spring 2020 – Project Two Due: 11:59 PM, March 23, 2020 Description: In this project, you will implement a generalized list data structure...

The project 3 description is project 2 that says due march 23. Has to be done in accordance with the description of the project and in the most basic way possible. I will send both previous projects so that you can understand the formatting he uses. Will have to output from the input file


Microsoft Word - Project-3.docx CS 2413 – Data Structures – Spring 2020 – Project Two Due: 11:59 PM, March 23, 2020 Description: In this project, you will implement a generalized list data structure using an array. A generalized list can be used to represent a tree data structure. Consider the following tree and the corresponding generalized list. The array representation of the above generalized list structure is given below: _Info _Next _Down 0 999 12 -1 1 75 9 -1 2 90 -1 4 3 30 13 -1 4 80 1 6 5 85 -1 -1 6 55 7 -1 7 45 -1 -1 8 999 0 -1 9 15 -1 10 10 35 5 11 11 25 3 -1 12 999 -1 -1 13 10 -1 -1 90 80 75 15 55 45 35 85 25 30 10 990 980 975 915 955 945 935 985 925 930 910 firstElement = 2; firstFree = 8; Where firstElement is the first location in the array that contains the first element. In this case it is the root of the tree that has a value 90. The free locations in the array are linked by the index positions in the array as a linked list. Follow the linked list starting at index position starting at location 8 and using the _Next index position. For ease I have put the value 999 in the _Info position where the index position is empty. You will implement the following classes along with the methods mentioned each of the classes – You can add other helper methods as you deem useful: template class GLRow; //class prototype template ostream& operator <(ostream& s,="">

& oneGLRow); class GLRow { friend ostream& operator

(ostream& s, GLRow

& oneGLRow); Protected: DT* _Info; int _Next; int _Down; Public: GLRow (); GLRow (DT& newInfo); GLRow (GLRow

& anotherOne); GLRow

& operator= (GLRow

& anotherOne); //Make sure you do //a deep copy int getNext(); int getDown(); DT& getInfo(); int setNext(int n); int setDown(int d); int setInfo (DT& x); ~GLRow(); //destructor }; template class ArrayGLL; //class prototype template ostream& operator <(ostream& s,="">

& oneGLL); class ArrayGLL { friend ostream& operator

(ostream& s, ArrayGLL

& OneGLL); Protected: GLRow

* myGLL; int maxSize; //Maximum size of the array of GLRows int firstElement; int firstFree; Public: ArrayGLL (); ArrayGLL (int size); ArrayGLL (ArrayGLL

& anotherOne); ArrayGLL

& operator= (ArrayGLL

& anotherOne); void display (); //display in parenthesis format 10% BONUS int find (DT& key); //return the index position where you find //the element key; -1 if not found; use recursive search void findDisplayPath (DT& Key); // as you travel through the tree //print the values of nodes encountered. If the element is //you will print the all the values int noFree (); //return the number of free locations; you need //to follow the _Next and get the free locations int size (); //return the number of elements stored int parentPos(DT& Key); // provide the location of the parent of //the element Key in the array 10% BONUS GLRow

& operator [] (int pos); //return the GLRow that is in //in the position pos in the array int getFirstFree(); int getFirstElement(); void setFirstFree (int pos); void setFirstElement (int pos); ~ArrayGLL (); //destructor }; Your main program will have the following structure (changes may be required). #include using namespace std; //define all your classes here (as given above) //write the methods after the class definition (not inside the class //definition); You will have this main program to start. Your program must be //able to work on other main programs as well. I HAVE NOT SYNTAX CHECKED THIS //CODE AND IT IS YOUR REPOSIBILITY. int main () { ArrayGLL firstGLL (20); int noElements, value, next, down, parentPos; int pos = -1; int keyValue; int tempValue = 0; GLRow oneRow (0); //note that this statically defined //make sure you define all the variables //first line of input contains the number of segments cin >> noElements; for (int i=0; i < noelements;="" i++)="" {="" cin="">> value >> next >> down; oneRow.setInfo(value); oneRow.setNext(next); oneRow.setDown(down); firstGLL[i] = oneRow; } firstGLL.setFirstFree (noElements); firstGLL.setFirstElement (0); cout < firstgll="">< endl;="" firstgll.display();="">* secondGLL = new ArrayGLL(firstGLL); (*secondGLL)[1].setInfo(600); (*secondGLL)[2].setInfo(700); cout < *secondgll="">< endl;="" (*secondgll).display();="" keyvalue="700;" pos="(*secondGLL).find(keyValue);" if="" (position="" !="-1)" {="" cout="">< (*secondgll)[pos]="">< endl;="" (*secondgll).finddisplaypath="" (keyvalue);="" }="" parentpos="(*secondGLL).parentPos(keyValue);" if="" (parentpos="" !="-1)" {="" cout="">< (*secondgll)[parentpos]="">< endl;="" }="" cout="">< (*secondgll).size="" ();="" cout="">< (*secondgll).nofree="" ();="" delete="" secondgll="" return="" 0;="" }="" redirected="" input:="" redirected="" input="" provides="" you="" a="" way="" to="" send="" a="" file="" to="" the="" standard="" input="" of="" a="" program="" without="" typing="" it="" using="" the="" keyboard.="" to="" use="" redirected="" input="" in="" visual="" studio="" environment,="" follow="" these="" steps:="" after="" you="" have="" opened="" or="" created="" a="" new="" project,="" on="" the="" menu="" go="" to="" project,="" project="" properties,="" expand="" configuration="" properties="" until="" you="" see="" debugging,="" on="" the="" right="" you="" will="" see="" a="" set="" of="" options,="" and="" in="" the="" command="" arguments="" type="">< input="" filename”.="" the="">< sign="" is="" for="" redirected="" input="" and="" the="" input="" filename="" is="" the="" name="" of="" the="" input="" file="" (including="" the="" path="" if="" not="" in="" the="" working="" directory).="" a="" simple="" program="" that="" reads="" a="" matrix="" can="" be="" found="" below.="" #include=""> using namespace std; int main () { int r,c,cv,nsv; int val; cin >> r >> c >> cv >> nsv; for (int i=0; i < r;="" i++)="" {="" for="" (int="" j="0;" j="">< c;="" j++)="" {="" cin="">> value; cout < value="">< “="" “;="" }="" endl;="" }="" return="" 0;="" }="" constraints="" 1.="" in="" this="" project,="" the="" only="" header="" you="" will="" use="" is="" #include=""> and using namespace std. 2. None of the projects is a group project. Consulting with other members of this class our seeking coding solutions from other sources including the web on programming projects is strictly not allowed and plagiarism charges will be imposed on students who do not follow this. Rules for Gradescope ( Project 3 ): 1. Students have to access GradeScope through Canvas using the GradeScope tab on the left, or by clicking on the Project 3 assignment submission button. 2. Students should upload their program as a single cpp file and cannot have any header files. If, there are header files(for classes) you need to combine them to a single cpp file and upload to GradeScope. 3. Students have to name their single cpp file as ‘project3.cpp’. All lower case. The autograder will grade this only if your program is saved as this name. 4. Sample input files and output files are given. Your output should EXACTLY match the sample output file given. Please check the spaces and new lines before you email us telling that the ‘output exactly matches but not passing the test cases’. Suggest using some type of text comparison to check your output with the expected. 5. Students need to have only one header file(iostream) while uploading to GradeScope. You cannot have ‘pch.h’ or ’stdafx.h’. 6. Students cannot have 'system pause' at the very end of the cpp file. 7. A few test cases will be released during the course of the project and the remaining test cases will be released after all the students have submitted that will add up to the allocated autograder points on GradeScope. 8. Manual grading involves implementation points and documentation points that will be graded after every student submits. 14 999 12 -1 75 9 -1 90 -1 4 30 13 -1 80 1 6 85 -1 -1 55 7 -1 45 -1 -1 999 0 -1 15 -1 10 35 5 11 25 3 -1 999 -1 -1 10 -1 -1