Book Suggestions for Computer Languages

Hello Everyone!

This is just a short post to hand out some suggestions about books. If you are studying a programmatic language, you may find a lot of books in the market which cover all the details of the language and from basic to complex all of the concepts.

However, I personally recommend HeadFirst books which are great if you are a beginner at language and complex books with lots of boring theories and background history are tiresome for  you. You will find books on C++, C#, Java, JavaScript, Html, SQL and many other languages.
There are also books on Design Patterns and Algorithms. The content and concept is explained in easy to understand and interesting way for you to have a great learning time. There are exercises and practices in the book too. The books cover all the basic and common concepts about the languages but if you want more details and advanced knowledge, you can refer to those complex books after acquiring basic concepts. :P

" The more you know, the more you grow. :) "

Read More

Search Algorithms in C++ || Binary Search Tree || Part 3

This is part 3 for Binary Search Tree, previous posts are Part 1 and Part 2. In this post, I'll attach the complete code also explain how Remove function for BST can be implemented.

There are a few situations possible while removing a node from the BST. There node may have no children, both children, etc. Let's have a quick view of them.

Key is element to be deleted.

• BST is empty -- then do nothing.
• Key is not found -- do nothing.
• Key is found at a node which is:

                 (a) A leaf node -- delete that node (let's call it current node), Update its Parent's appropriate child to Null (e.g. if it was Left child that got deleted, set lChild pointer in Parent to null.), point Previous (Previous is the Parent node of the Current node) pointer to null. (if the current was leaf as well as root, then set root pointer to null)

                (b) Not a leaf node and has:

                       (i) One child N -- Previous adapts N, Remove Current

                       (ii) Two children -- find the Predecessor¹ P of the current node, Swap P and current node, if P is leaf then apply A else apply B(a)

Figure A

Figure B

 ¹To find a Predecessor, go to left child and then keep going right till the leaf element is reached. Predecessor is the element which is smaller to the Current node but larger than all it's left side children.

In this figure A, you can see even if replace predecessor with current node i.e. 12 with 9, the order of the tree remains intact. See figure B. 

Now let's look at the code.

void remove(const T & key)

{

if (s == 0)

{

cout << "\n Empty! \n";

return;

}

else

{

if (search(key) == false)

{

cout << "\n Key not found! \n";

return;

}

//SEARCHING

Node* curr = root;

Node* prev = nullptr;   //parent

while (curr != nullptr && curr->data != key)

{

prev = curr;

if (curr->data > key)

curr = curr->lchild;   //key is smaller

else

curr = curr->rchild;   //key is greater

}    

if (curr->lchild == nullptr && curr->rchild == nullptr) //if leaf

{

delete curr;

if (curr == root)

root = nullptr;

//is it left or right child?

else if (prev->data > key)   

prev->lchild = nullptr;

else if (prev->data < key)

prev->rchild = nullptr;

}

else     //not leaf

{

//single child

if ((curr->lchild != nullptr && curr->rchild == nullptr) || (curr->lchild == nullptr && curr->rchild != nullptr))

{

if (prev->lchild = curr)    //if curr was left child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->lchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->lchild = curr->rchild;   //prev adopts right child

}

}

else if (prev->rchild = curr)    //if curr was right child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->rchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->rchild = curr->rchild;   //prev adopts right child

}

}

delete curr;

}

//if curr has 2 children

else if (curr->lchild != nullptr && curr->rchild != nullptr)

{

//find the predecessor

Node* curr2 = curr->lchild;  //go to left of the curr

Node* prev2 = curr;

Node* prev3 = nullptr;

while (curr2 != nullptr)

{

prev3 = prev2;

prev2 = curr2;

curr2 = curr2->rchild;

}

swap(curr->data, prev2->data);   //swapped

//if prev2 is a leaf

if (prev2->lchild == nullptr && prev2->rchild == nullptr) 

{

if (prev2 == root)

root = nullptr;

else if (prev3->lchild == prev2)

prev3->lchild = nullptr;

else if (prev3->rchild == prev2)

prev3->rchild = nullptr;

delete prev2;

}

//if prev2 has one child

else if ((prev2->lchild != nullptr && prev2->rchild == nullptr) || (prev2->lchild == nullptr && prev2->rchild != nullptr))

{

if (prev3->lchild = prev2)    //if prev2 was left child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->lchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if curr has right child

{

prev3->lchild = prev2->rchild;   //prev adopts right child

}

}

else if (prev3->rchild = prev2)    //if prev2 was right child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->rchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if prev2 has right child

{

prev3->rchild = prev2->rchild;   //prev adopts right child

}

}

delete curr;

}

}

}

s--;   //reducing size

}

}

This is all so far about BST. 

To download code, Click Here!

In my code, I have other utility functions too as per my requirement which I have not discussed here. Keep them or remove them, your choice! :P

Thanks for reading. If any question, Comment below! :)

        

Read More

Search Algorithms in C++ || Binary Search Tree || Part 2

This is the second post in continuation of the last post on Binary Search Trees in C++.

Just like we did for vectors, linked strings; we will have a struct for Node to represent nodes of the tree. The node will contain a  data element, a pointer to the left child and a pointer to the right child.

template <class T>
struct node{
             T data;
             node * lChild, rChild;
}

And then a class for BST (Binary Search Tree). In the private members, we will have a node* root element that will serve as the beginning of tree traversal. We will have some basic functions like insert, search and remove in the class. I have made an iterator for the traversal in my class. Given below is the code:

template <class T>
class bst {
private:
struct Node {
T data;
Node* lchild;
Node* rchild;

};   //I've made the struct inside the class so that user cannot access it

Node* root;   //private members
int s;

Node* createNode(const T & obj )  //a utility function
{
Node* temp = new Node;
temp->data = obj;
temp->lchild = temp->rchild = nullptr;
return temp;

}

int height(Node* n )  //to get tree height at a specific node

{

if (n == nullptr)

{

return 0;

}

else

{

int ln = height(n->lchild);     //used recursion to get tree height using

                                                                    originating branches from the child

int rn = height(n->rchild);

return (max(rn, ln) + 1);

}

}

bst()  //default constructor

{

s = 0;

root = nullptr;

}

Strategy used in Insert:  We have two nodes to help in our traversal, Previous and Current. In the parameter we take 'key', which is the data to be inserted, we compare that data with the current node and go to its left if the data in the current node is greater than the key (as the left child is smaller than its parent) and go to its right if the data in the current node is smaller than the key (as the right child is greater than its parent).

  >> Note: The data here is template T type which can be an int, string or any custom datatype. The comparison is done using < and > operators which may be type specific. E.g. different for integer comparison and different for string comparsion. 

Also, in every traversal we update Previous pointer with the Current pointer to move to the next and update Current with left or right child's pointer using comparison. The while loop traversal keeps going till we reach the leaf position where we can insert our new node. After the while loop ends, the Previous pointer is pointing to the node of which we will make a new child, either left or right, after comparison of the data.

If the previous pointer is simply empty, it means no node has been created so far and the tree is empty, so we create a new node at the Root. 

void insert(const T & key)

{

                

Node* curr = root;  //current element in the traversal, in the beginning it is root

Node* prev = nullptr;    //previous element, i.e. parent of the current node

while (curr != nullptr)    //if the tree is not empty, start traversal

{

prev = curr;

if (curr->data > key)   //if key < current then go to left

{

curr = curr->lchild;  

}

else if (curr->data < key)    //if key > current then go to right

{

curr = curr->rchild;

}

else

return;    //no repetition allowed

}

if (prev == nullptr)

{

root = createNode(key);    //if empty

s++;

}

else        //tree size >= 1

{

if (prev->data < key)     //key is bigger

{

prev->rchild = createNode(key);

s++;

}

else if (prev->data > key)    //key is smaller

{

prev->lchild = createNode(key);

s++;

}

}

}

bool search(const T & key)  //returns the true if the key found in the tree, else false
{
Node* curr = root;
while (curr != nullptr && curr->data != key )
{
if (curr->data > key)
curr = curr->lchild;   //key is smaller
else
curr = curr->rchild;   //key is greater
}

if (curr != nullptr)
return true;

return false;

}

int size()
{
return s;
}

int height()
{
return height(root);
}

Here is the code for the Iterator of this class, it will be in the public section of the BST class

//************* ITERATOR **************//

class iterator {
private:
vector <Node*> nodes;
int index;

public:
iterator(int i, vector <Node*> & v)
{
nodes = v;    //automatically does deep copy in vector class
index = i;
}

iterator(const iterator & obj)
{
nodes = obj.nodes;
index = obj.index;
}

bool operator != (const iterator & obj)
{
if (index != obj.index)
return true;

return false;
}

void  operator ++ ()
{
index++;

}

void operator ++ (int ind)
{
index = index + ind;
}

T operator * ()
{
return nodes[index]->data;
}
};


/****************** End of Iterator Class *********************/

We will also require some utility functions in the BST class to help initialise the iterator.

==> To see what are iterators and how they work, Click Here!

void getNodes_inOrder(Node* n, vector  <Node*> & v )
{
if (n != nullptr)
{
getNodes_inOrder(n->lchild, v);
v.push_back(n);
getNodes_inOrder(n->rchild, v);
}
}

iterator begin()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(0, v);     //starting index is 0
return itr;
}

iterator end()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(v.size(), v);     //ending index is vector's size
return itr;
}

The Remove function of this class is a bit tricky and long in code length. So I will explain that in the next post. Complete code will be posted in the next post.

Thank you for reading and comment below if you have any questions! :)

Read More

Dynamic Array || Create a Class in C++ || C plus plus

Hi! In this post, I'll be creating a class called Dynamic Array with a number of utility functions.

What is a Dynamic Array?

A dynamic array is an array which is dynamically allocated. I'll be making int type array here. You can also make a char, double or float type class. It will have utility functions which double the size when we run out of storage plus functions like add element, remove element, etc. The advantage of this class is that while using it we wouldn't have to worry about resizing it or anything, we'll just make and object of class type and work with it.

If you have used String object before then you probably know already that how a class works. String is also a class with char data type.

Code for the Class

The private section of the class will contain 3 members:

class DynamicArray
{
 private:
          int* arr;  //our array
         int size;  //how many elements are there
         int cap;  //capacity i.e. how many elements can fit in the array

public:

       //utility functions here

}

Let's make the constructors first (write constructors in the public section). The default constructors, as mentioned previously, will have no parameters and it also has no return type.

DynamicArray()
{
     arr = nullptr; //since nothing in it at the time it is constructed hence point it to the null
     size = 0;          //nothing stored yet
     cap = 0;          //0 capacity
}

The parameterized constructor will have only one parameter i.e. the capacity in the beginning.

DynamicArray( int c )
{
    cap = c;
    size = 0;
    arr = new int[cap];  //making a dynamic array of capacity cap
}

What other functions do we require? Insert or Add Element, of course. The utility functions that are to be used by the user/public are to be made in public section. They are just like ordinary functions i.e. they have a return type.

PS: A point to remember is that while you are inside any function or constructor of the class, you can access its private members or private functions. Like I did in the constructors. But as soon as you go outside the class, you have access only to the public stuff.

Let's write code for the insert here. But there is a small point to consider, what if run out of capacity? In that case, we shall have to double the capacity. We can make a function for that as well which will double the capacity and since that function is only required by the insert function of this class (not required to the public), we shall make it private. So first, let's make a utility function called DoubleCap (double the capacity first)

void DoubleCap()
{
     int new_cap;
     if (cap == 0)
         new_cap = 1;

    else
   {
       new_cap = cap*2;   //doubling the capacity
       int* temp = new int[new_cap];    //made a temporary array since we need to shift data
       // if you don't know why make another temporary, please refer to  (Intro to Dynamic Allocation.)

        for (int i = 0; i < cap; i++)
                temp[i]  = arr [i];     //copying

         delete [] arr;
         arr = temp;
         cap = new_cap;
    }
    
}


void Insert(int d)   //d is that data that is to be inserted
{
    //there are two cases for insertion
   // first : when we have not overflowed the array i.e. capacity is available for insertion
  //second : when we have run out of capacity which requires doubling the capacity

      if (size < cap)
    {
        arr[size] = d;   //added the element at the next index e.g. when size was 0 (first insertion)
                               // we inserted at arr[0]
        size++;         // then increase the size by one
    }

   else                  //when size has surpassed the capacity
    {
        //calling the utility function
        DoubleCap();
        arr[size] = d;
        size++;
    }

}   //end of function

Now let's write the opposite of Insert i.e. Erase or Remove Element. I'll use another private utility function for it which will Half the Capacity when the size has dropped below half of the current capacity. It also will be a private function.

void HalfCap()
{
            int new_cap = cap/2;
            int* temp = new int[new_cap];
            
           for (int i = 0; i < size; i++)
                    temp[i] = arr[i];

         arr = temp;
         cap = new_cap;
}

void Erase()
{
     if (size < cap/2)
           HalfCap();
      
     size--;     //simply reduce the size, we don't delete it. 
     //by reducing size, we make it available for being over-written
}

We can make a number of other utility functions like Get Size which returns the size of the array in public.

int getSize()
{
     return size;
}

Or the Get Element which receives an index in parameter and returns whatever is stored at the index since the array arr is not accessible to the outside world and they can't access elements as arr[i]. 

int getElement( int i )
{
    return arr[i];
}

You can also try making the functions like Print Array.

In the end, we make the destructors. Destructors are made when the memory is being dynamically allocated in a class i.e. it has a dynamic element.

The prototype of the the destructor is just like that of the class. Except for ~ before the name which distinguishes it from the constructors. Plus, it has no parameters.

~DynamicArray()
{
    delete [ ] arr;
}

How to use the class?

First, you need to include it. Please refer to (Intro to Class.)

Using class and its utility functions is easy.

Make an object of class type.

How destructors and constructors are called?

The constructors are called automatically i.e. when you create the element. 

For instance,

   

DynamicArray obj1;    //the default constructors is called

int capacity = 20;

DynamicArray obj2(capacity);    //the parameterized constructor is called

DynamicArray obj3(25);            //parameterized constructor

I hope it has cleared the difference between calls for parameterized and default constructor. For parameterzed, you pass the parameters right when you create it. Writing as:

DynamicArray obj;

obj(25);                     //won't work!!

The destructor is called automatically when the program ends. Don't forget to make destructors for the class with dynamic allocation it can leads to the overflow in the Heap memory. Whatever you allocate on Dynamic Memory heap, must de-allocate it.

How to use utility functions?

Easy. Use the dot operator (.)

For example,

DynamicArray obj(10);

obj.Insert(55);

obj.Insert(44);

obj.PrintArray();

int size = obj.getSize(); 

Thank you for reading. Feel free to comment below. :)

Read More

Find and Replace words in a paragraph || C++ function || Char array practice

Limitations :

• Hard coded paragraph
• The word to be found and to be replaced with must be of the same lengths.
• For those who have no idea of pointers, simple char array is used hence hard coded the size as well.

Code:

   

#include <iostream>

#include <conio.h>

using namespace std;

void mySearch(char para1[], int size, char find[], int fsize, int &index, int x)  //Search function

{

index = -1;

int i = 0;

if (find[i] == para1[x])   //para1 is the array that contains paragraph

{ 

                  //find contains the word to be found

int j = x, flag = 0;

for (i = i + 1; i < size && find[i] != '\0' && flag == 0; i++)

{

x++;

if (find[i] == para1[x])

{

;

}

else

flag = 1;  //if the complete word is not found ... breaks the loop

}

if (flag == 0)

{

index = i;  //if the complete word is found

}

}

}

char toReplace(char replace[], int size, char para[], int rsize, int index, int x1) //this function replaces

{

int i = index;

para[i] = replace[x1];  

return para[i];

}

int main()

{

char para[400] = "Cheating is the getting of a reward for ability by dishonest means or finding an easy way out of an unpleasant situation. It is generally used in situations to gain unfair advantage in a competitive situation. This broad definition will necessarily include acts of bribery, cronyism, sleaze, nepotism and any situation where individuals are given preference using inappropriate criteria.";  //hard coded para

cout << para << endl;  //displaying paragraph (optional)

char find[10], replace[10];

cout << "Find : ";

cin >> find;

cout << endl << "Enter the word to replace with : ";

cin >> replace;

cout << endl;

int index = 0, j = 0;

char w;

for (int i = 0; para[i] != '\0'; i++)

{

mySearch(para, 400, find, 10, index, i);

if (index != -1)

{

for (j; replace[j] != '\0'; j++)

{

w = toReplace(replace, 10, para, 400, index, j);

cout << w;

index++;

i++;

}

i--;

j = 0;

}

else

cout << para[i]; //displaying paragraph

}

system("pause");

return 0;

}

Thank you for reading! ^^

Read More

Simple Calculator (With C++)

In order to make a calculator, you must have idea about if/else statements and loop in case you want the calculator to print the menu after every calculation.

Here, I have used 'do while'

do 

{

    //the thing that is to be repeated.

}

while (//condition)

The operations performed by this calculator are :

Sum

Subtract

Multiply

Divide

Magnitude

Power

ASCII of a character

Source Code:

#include <iostream>

#include  <stdlib.h>

using namespace std;

int main()

{

char redo;

do

{

cout << " *** Welcome to The Ultimate Calculator *** " << endl << endl;

cout << " If you want to ADD press 0 " << endl << " If you want to DIVIDE press 1 " << endl << " If you want to take MAGNITUDE press 2 " << endl << " If you want to take POWER press 3 " << endl << " If you want to find ASCII press 4 " << endl << " If you want to EXIT press 5 " << endl;

int x;

cin >> x;

if (x == 0)

{

cout << " You have selected ADDITION function. " << endl << endl;

cout << " Enter the Numbers you want to Add " << endl;

int a, b;

cout << " Enter the first number : ";

cin >> a;

cout << " Enter the second number : ";

cin >> b;

int sum = a + b;

cout << " The Result is " << sum << endl;

}

else if (x == 1)

{

cout << " You have selected DIVISION function. " << endl << endl;

cout << " Enter the Numerator : ";

int a,b;

cin >> a;

cout << " Enter the Denominator : ";

cin >> b;

float div = (a * 1.0) / b;

cout << " The Result is " << div << endl;

}

else if (x == 2)

{

cout << " You have selected MAGNITUDE function. " << endl << endl;

cout << " Enter the Number you want to take Magnitude of : ";

int a;

cin >> a;

if (a > 0)

cout << endl << " The Magnitude is " << a << endl;

else

{

int m = a * (-1);

cout << " The Magnitude is " << m << endl;

}

}

else if (x == 3)

{

cout << " You have selected POWER function. " << endl << endl;

cout << " Enter the Base : ";

int a;

cin >> a;

cout << " Enter the Exponent : ";

int b;

cin >> b;

int i = 1;

int prod = 1;

while (i <= b)

{

prod = a * prod;

i++;

if (i > b)

cout << " The Result is " << prod << endl;

}

}

else if (x == 4)

{

cout << " You have selected ASCII Teller. " << endl << endl;

cout << " Enter the character " << endl;

char a;

cin >> a;

cout << " It's ASCII value is " << (int)a << endl;

}

else if (x == 5)

exit(EXIT_SUCCESS);

else

{

cout << " The input you have entered is invalid! " << endl;

exit(EXIT_FAILURE);

}

cout << " Do you want to perform another Calculation? ( Y or N) : ";

cin >> redo;

cout << endl << endl;

}

while ((redo == 'y') || (redo == 'Y'));

system("pause");

return 0;

}

Hope you find it useful. :) Thank you! ^^

Read More