Atsiskaityti privalote iki paskutinės praktinės paskaitos.

Assignment: Užduotis

• Privalote įgyvendinti 4 skirtingas duomenų struktūras ir jų pagrindines funkcijas:
  • Binary Tree: Dvejetainis medis: create(), insertLeft(), insertRight(), getRoot(), setRoot(), getLeftChild(), getRigthChild(), destroy().
  • Stack: Stekas: create(), push(), pop(), isEmpty(), isFull(), destroy(), ect.
  • 2 laisvai pasirinktas duomeų struktūras.
• Sukurtoms duomenų struktūroms privalote sugalvoti algoritmą, kuriame pademonstruotumėte jų veikimą pvz:
  • Stekas -> sukurti algoritmą, kuris skaičiuoja aritmetines išraiškas 9(((5+8)+(87))+3).
  • Dvejetainis medis -> įgyvendinti Parse Tree algoritmą plačiau rasite čia.
  • Laisvai pasirinkta duomenų struktūra 1 -> Bet koks algoritmas.
  • Laisvai pasirinkta duomenų struktūra 2 -> Bet koks algoritmas.
• Privalote išvesti tarpinius algoritmo žingsnius pvz. iterptas elementas, pašalintas elementas, atliktas palyginimas, sunaikinta duomenų struktūra ir pan.

Example of Stack ADT

/* 
 * File:   main.cpp
 * Author: Marius
 *
 * Created on January 27, 2019, 12:02 AM
 */

#include <cstdlib>
#include <iostream>
#define MAX_SIZE 10 // Max size of Stack container

using namespace std;

int container[MAX_SIZE]; // Container to store Stack ADT elements

class Stack{
    public: 
        int top;
        
        Stack(){ top = -1;}
        
        bool isFull(){
            if(MAX_SIZE - top == 1){
                return true;
            }else{
                return false;
            }
        }
        bool isEmpty(){
            if(top == -1){
                return true;
            }else{
                return false;
            }
        }
        void push(int x){
            if(!isFull()){
                top++;
                container[top] = x;
            }else{
               cout<< "\nStack is full\n";
            }
        }
        int pop(){
            int x;
            if(!isEmpty()){
                x = container[top];
                top--;
                return x;
            }else{
                return -1;
            }
        }
        void print(){
            cout << "------------------------------------"<< endl;
            for(int i=0; i <= top; i++){
                if(top == i){
                    cout << container[i] << ".";
                }else{
                    cout << container[i] << ",";
                } 
            }
            cout << "\n------------------------------------"<< endl;
        }
        
};

int main(int argc, char** argv) {
    Stack stack;
   
    for(int i=0; i < MAX_SIZE; i++){
        stack.push(i);
    }
    
    // Every step displaying Stack data structure container 
    stack.print();
    stack.pop();
    stack.print();
    stack.push(99);
    stack.print();

}

Example of LinkedList ADT

#include <cstdlib>
#include <iostream>

using namespace std;

class Node{
  public:
    Node *next;
    int data;
};

class LinkedList{
  public:
    int length;
    Node *head;

    LinkedList(){
      this->length = 0;
      this->head = nullptr;
    }
    ~LinkedList(){
      cout << "LIST DELETED" << endl;
    }
    void add(int data){
      Node *node = new Node();
      node->data = data;
      node->next = this->head;
      this->head = node;
      this->length++;
    }
    void remove(int position){
      Node *temp1 = head;
      if(position == 1){
        head = temp1->next;
        delete temp1;
      }
      for(int i=0; i < position - 2; i++){
        temp1 = temp1->next;
      }
      Node *temp2 = temp1->next;
      temp1->next = temp2->next;
      delete temp2;
    }
    void display(){
      Node *head = this->head;
      int i = 1;
      while(head){
        cout << i<<": "<< head->data << endl;
        head = head->next;
        i++;
      }

    }
};

Example of Queue ADT

#include <string>
#include <iostream>
using namespace std;

class Queue {
private:
  int data[10]={};
  int size;
  int front;
  int rear;
  int numberOfItems = 0;
public:

  Queue(){
    front = rear = -1;
    size = sizeof(data) / sizeof(data[0]);
    for(int i=0; i < size; i++){
      data[i] = -1;
    }
  }

  void insert(int input){
    if(numberOfItems + 1 <= size){
      data[rear] = input;
      rear++;
      numberOfItems++;
      cout << "INSERT " << input << " was added to Queue!" <<endl;
      displayQueue();
    }else{
      cout << "Sorry but the Queue is Full!"<< endl;
    }
  }
  void remove(){
    if(numberOfItems > 0){
      cout << "REMOVE " << data[front] << " was removed from Queue!" <<endl;
      data[front] = -1;
      front++;
      numberOfItems--;
    }else{
      cout << "Sorry but the Queue is Empty!"<< endl;
    }
  }
  void peek(){
    if(data[front] != -1)
      cout << "The First Element is " << data[front] <<endl;
  }
  void displayQueue(){
    cout << "------------------------------" <<endl;
    cout<< "|" << data[front];
    for(int i=0; i < size; i++){
      if(data[i] != -1) {
        cout << "|" << data[i] << "|";
      } else{
        cout << "|" << " " << "|";
      }
    }
    cout << "\n------------------------------" <<endl;
  }

};