CS301 – Data Structures

Sample Output
A1 Sample Output.mp4

@zaasmi said in CS301 GDB 1 Solution and Discussion:

From Stack and Queue data structures which data structure you will suggest using for entry to exit path finding module? Select a data structure and give comments in favour to justify your selection. Also mention why you are not selecting the other data structure?

I Would suggest Stack data structure over Queue. This is because in solving a maze problem, we need to explore all possible paths. Along with that, we also need to track the paths visited.
If we were to use Queue, then after finding an unsuccessful path, we’ll have to start again from the entry point as queue only supports deletion from the front (FIFO property). This would not be useful in our case, as we need to trace back the unsuccessful path until we find another way.
Using Stack, what we can do is, while moving into the maze, we can push the index of the last visited cell and when reached the end of the maze(not exit-point), just keep popping elements from the stack until the cell at stack Top has another way to move.
Using this approach (particularly stack), you can find the correct path in the shortest possible time.

@zareen
100% Solution Code

#include <iostream> using namespace std; /* The Student class */ class Student { private: string firstname, lastname, VUID; int marks; Student *nextStudent; public: // constructor of Student class to initialize data members of class Student(){ VUID = ""; marks = 0; firstname = ""; lastname = ""; nextStudent = NULL; } // Student class method to set VU ID of Student void setVUID(string val){ VUID = val; }; //Student class method to get VU ID of Student string getVUID(){ return VUID; }; // Student class method to set first name of Student void setFirstName(string val){ firstname = val; }; //Student class method to get first name of Student string getFirstName(){ return firstname; }; // Student class method to set last name of Student void setLastName(string val){ lastname = val; }; //Student class method to get last name of Student string getLastName(){ return lastname; }; //Student class method to set the Marks of Student void setMarks(int val) { marks = val; }; // Student class method to get the Marks of Student int getMarks() { return marks; } //Student class method to point current Student to next Student void setNext(Student *nextStudent) { this->nextStudent = nextStudent; } // Student class method to get memory address where pointer is pointing Student *getNext() { return nextStudent; } }; /* The List class */ class List { private: Student * head; Student * current; public: // constructor of list class to initialize data members of class List() { head = new Student(); head->setNext(NULL); current = NULL; } // list class method to add Students into list void add() { Student *newStudent = new Student(); int loc_marks = 0; string loc_vuid = "", loc_fname = "", loc_lname = ""; cout<<"\nEnter VU ID: "; cin>>loc_vuid; newStudent->setVUID(loc_vuid); cout<<"Enter Marks: "; cin>>loc_marks; newStudent->setMarks(loc_marks); cout<<"Enter First Name: "; cin>>loc_fname; newStudent->setFirstName(loc_fname); cout<<"Enter Last Name: "; cin>>loc_lname; newStudent->setLastName(loc_lname); if(head->getNext() == NULL){ newStudent->setNext(NULL); head->setNext(newStudent); current = newStudent; } else{ Student *temp = head; while(temp->getNext() != NULL && temp->getNext()->getMarks() >= loc_marks){ temp = temp->getNext(); } current = temp; newStudent->setNext(current->getNext()); current->setNext( newStudent ); current = newStudent; } }; // list class method to get the information of Student void getInfo() { if (current != NULL){ cout<<"VU ID: "<<current->getVUID()<<endl; cout<<"Marks: "<<current->getMarks()<<endl; cout<<"First Name: "<<current->getFirstName()<<endl; cout<<"Last Name: "<<current->getLastName()<<endl<<endl; } }; // list class method to move current to next Student bool next() { if (current == NULL){ return false; } current = current->getNext(); }; // frient function to list class to show all students in the list friend void showStudents(List list){ Student* savedCurrent = list.current; list.current = list.head; for(int i = 1; list.next(); i++){ list.getInfo(); } list.current = savedCurrent; }; }; main() { int input = 0; List lst; while(input != -1) { cout<<"1. To Add New Student in Ranking"<<endl; cout<<"2. To Display Ranking"<<endl; cout<<"3. To Close"<<endl<<endl; cout<<"Enter Your Choice: (1, 2 or 3) "; cin>> input; if(input == 1) { lst.add(); cout<<"Student's information saved successfully.\n"; } else if(input == 2) { cout<<"\nRanking Chart"<<endl; showStudents(lst); return 0; } else { return 0; } } }

CS301-assignment-no3-Solution.docx

#include<iostream> using namespace std; class TNode{ private: node* root; public: TNode(); int isEmpty(); void buildTree(int item); void insert(int item,node *,node *); void minNode(node*); void maxNode(node*); int countNodes(node*); int treeHeight(node*); void displayBinTree(); }; TNode::TNode(){ root = NULL; } int TNode::isEmpty() { return (root == NULL); } void TNode::buildTree(int item){ node *p = new node; node *parent; cout <<"Insert node in BST :" << item <<endl; insert(item,p,parent); } void TNode::insert(int item,node * p,node * parent){ p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isEmpty()){ root = p; } else{ node *ptr; ptr = root; while(ptr != NULL){ parent = ptr; if(item > ptr->data){ ptr = ptr->right; } else{ ptr = ptr->left; } } if(item < parent->data){ parent->left = p; } else{ parent->right = p; } } } void TNode::minNode(node* p){ while (p->left != NULL){ p = p->left; } cout << "Minimum value : " << p->data <<endl; } void TNode::maxNode(node* p){ while (p->right != NULL){ p = p->right; } cout << "Maximum value : " << p->data <<endl; } int TNode::countNodes(node* p){ int node = 1; //Node itself should be counted if (p == NULL){ return 0; } else{ node += countNodes(p->left); node += countNodes(p->right); return node; } } int TNode::treeHeight(node* p){ if (p == NULL) { return 0; } else { int left_side = treeHeight(p->left); int right_side = treeHeight(p->right); if (left_side > right_side) { return(left_side + 1); } else { return(right_side + 1); } } } void TNode::displayBinTree(){ cout <<endl<<endl; minNode(root); maxNode(root); cout <<"Height of BST : "<<treeHeight(root); cout <<"\nTotal nodes : "<<countNodes(root); } int main(){ TNode b; int data[] = {7,2,9,1,5,14}; cout <<"Constructing Binary Search Tree by Inserting Nodes One by One "<<endl; cout <<"------------------------------------------------------------- "<<endl; int arrSize = sizeof(data)/sizeof(data[0]); for(int i = 0; i < arrSize; i++) { b.buildTree(data[i]); } }

100% Solved:

#include <iostream> #include <string.h> using namespace std; const int arrLength = 10; struct Student{ string userVUID; string userDetails; }std1={"NULL","NULL"}; class ArrQueue{ private: //Data Members Student arr[arrLength]; int front; int rear; public: //Constructor ArrQueue(){ for(int i=0; i<arrLength; i++) arr[i] = std1; front = -1; rear = -1; } //Member Functions void enQue(Student std){ if(isEmpty()){ arr[0] = std; front++; rear++; } else if(isFull()){ cout << " Queue is full."; } else{ arr[rear+1] = std; rear++; } } void deQue(){ if(isEmpty()){ cout<< " No Student In the Queue.\n"; } else if(rear == 0){ arr[front] = std1; front = -1; rear = -1; } else{ int tempfront = front; arr[front] = std1; for(int i=1; i<=rear; i++ ){ arr[front] = arr[i]; front++; } rear--; front = tempfront; } } int queLength(){ return rear+1; } bool isEmpty(){ if(front==-1 || rear==-1) return true; else return false; } bool isFull(){ if(rear == arrLength-1) return true; else return false; } void showQue(){ cout << "\n |Sr. VU ID Details |"; cout << "\n --- -------------------------------\n"; for(int i=front; i<=rear; i++){ cout<<" "<< i+1<< ". "<< arr[i].userVUID << " " << arr[i].userDetails <<"\n"; } } }; int main(){ /*Code For Even Id's Student std[] = {{"BC12345684","Bilal (BSCS)"}, {"BC12345685","Bilal (BSCS)"},{"BC12345686","Bilal (BSCS)"},{"BC12345687","Bilal (BSCS)"}, {"BC12345688","Bilal (BSCS)"}};*/ /*Code For Odd Id's */ Student std[] = {{"BC12345683","Bilal (BSCS)"}, {"BC12345684","Bilal (BSCS)"},{"BC12345685","Bilal (BSCS)"},{"BC12345686","Bilal (BSCS)"}, {"BC12345687","Bilal (BSCS)"}}; ArrQueue arrQue; cout << "\n -----------------------------------"; cout << "\n | Queue (After Adding Students) |"; cout << "\n -----------------------------------"; for(int i=0; i<=4; i++){ arrQue.enQue(std[i]); } arrQue.showQue(); cout << "\n -----------------------------------"; cout << "\n | Queue (After Removing Students) |"; cout << "\n -----------------------------------"; /* Code For Even Id's for(int i=0; i<=1; i++){ arrQue.deQue(); }*/ /*Code For Odd Id's*/ for(int i=0; i<1; i++){ arrQue.deQue(); } arrQue.showQue(); }

Solution Idea!

#include <bits/stdc++.h> using namespace std; class HeapNode_Min { // Tree node of Huffman public: //Add data members here. char d; unsigned f; HeapNode_Min *l, *r; HeapNode_Min(char d, unsigned f = -1) { //Complete the body of HeapNode_Min function this->d = d; this->f = f ; this->l = NULL; this->r = NULL; } }; class Analyze { // two heap nodes comparison public: bool operator()(HeapNode_Min* l, HeapNode_Min* r) { //add return before statement and statement is completed. return (l->f > r->f); //Complete this statement } }; void display_Codes(HeapNode_Min* root, string s) // To print codes of huffman tree from the root. { if (!root) return; if (root->d != '$') cout root->d "\t: " s "\n"; display_Codes(root->l, s + "0"); display_Codes(root->r, s + "1"); //Complete this statement by passing arguments } void HCodes(char data[], int freq[], int s) // builds a Huffman Tree { HeapNode_Min *t,*r, *l ; // top, right, left priority_queue<HeapNode_Min*, vector<HeapNode_Min*>, Analyze> H_min; int a=0; while (a<s){H_min.push(new HeapNode_Min(data[a], freq[a])); ++a;} while (H_min.size() != 1) { l = H_min.top(); H_min.pop(); r = H_min.top(); H_min.pop(); t = new HeapNode_Min('$', r->f + l->f); t->r = r; t->l = l; H_min.push(t); } display_Codes(H_min.top(), ""); } int main() { int frequency[] = { 3, 6, 11, 14, 18, 25 }; char alphabet[] = { 'A', 'L', 'O', 'R', 'T', 'Y' }; //Complete this statement by passing data type to both sizeof operators int size_of = sizeof(alphabet) / sizeof(*alphabet); cout"Alphabet"":""Huffman Code\n"; cout"--------------------------------\n"; //Call Huffman_Codes function. HCodes(alphabet, frequency, size_of); return 0; }

.CPP File Code

using namespace std; #include <stdlib.h> #include <iostream> struct StudentDetail{ string name; string vuid; }; //class Node* head; class Node{ struct StudentDetail newStd; class Node* next; class Node* prev; void Set(string name,string vuid) { newStd.name=name; newStd.vuid=vuid; } Node Get() { } void setNext(string name,string vuid){ if(next==NULL) { } else { class Node* newNode= new Node(); newStd.name=name; newStd.vuid=vuid; newNode->next= newNode; } } string getNext() { next; } void setPrev(string name,string vuid){ if(next==NULL) { } else { class Node* newNode= new Node(); newStd.name=name; newStd.vuid=vuid; newNode->next= newNode; } } string getPrev() { prev; } }; class DoublyLinkedList{ public: struct StudentDetail newStd; class DoublyLinkedList* headPtr; class DoublyLinkedList* curPtr; class DoublyLinkedList* nextPtr; int size; //dfdf class DoublyLinkedList* headDlinkList=NULL; void addAtBegining(string vuid, string name) { class DoublyLinkedList* dNode= new DoublyLinkedList(); dNode->newStd.vuid=vuid; dNode->newStd.name=name; dNode->nextPtr=headDlinkList; headDlinkList= dNode; dNode->curPtr=dNode; } void addAtEnd(string vuid, string name) { class DoublyLinkedList* dNode= new DoublyLinkedList(); dNode->newStd.vuid=vuid; dNode->newStd.name=name; dNode->nextPtr=headDlinkList; headDlinkList= dNode; dNode->curPtr=dNode; } void delNode() { class DoublyLinkedList* temp1=curPtr; class DoublyLinkedList* temp2= temp1; temp1->nextPtr= temp2->nextPtr; free(temp2); } void print() { class DoublyLinkedList* temp= headDlinkList; while(temp!=NULL) { cout<<temp->newStd.vuid<<" "<<temp->newStd.name<<endl; temp= temp->nextPtr; } } }; int main() { string vuid,name; cout<<"Add your vuID and Name at First Position "<<endl; cout<<"_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _"<<endl; DoublyLinkedList dlist1; cin>>vuid; cin>>name; dlist1.addAtBegining(vuid,name); dlist1.print(); cout<<"Insertion At Beginning in doubly Link List "<<endl; cout<<"_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _"<<endl; cin>>vuid; cin>>name; dlist1.addAtBegining(vuid,name); dlist1.print(); cout<<"Insertion At End in doubly Link List "<<endl; cout<<"_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _"<<endl; cin>>vuid; cin>>name; dlist1.addAtEnd(vuid,name); dlist1.print(); cout<<"Deletion of Current Node (Last Node) "<<endl; cout<<"_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ __ _ _"<<endl; dlist1.delNode(); dlist1.print(); }

Download .cpp File