|
|
Insertion Sort
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed
1 #include <iostream>
2 #include <string.h>
3
4 template <typename T>
5 class InsertionSort
6 {
7 public:
8 InsertionSort();
9 ~InsertionSort();
10
11 void sort(T arr[], int size);
12 private:
13 void compareExchange(T arr[], int l, int r);
14 bool greater(T left, T right);
15 };
16
17
18 template <typename T>
19 InsertionSort<T>::InsertionSort(){}
20
21
22 template <typename T>
23 InsertionSort<T>::~InsertionSort(){}
24
25 template <typename T>
26 void InsertionSort<T>::sort(T arr[], int size)
27 {
28 for(int i = 1; i < size; ++i)
29 {
30 for(int j = i; j > 0; --j)
31 {
32 compareExchange(arr, j-1, j);
33 }
34 }
35 }
36
37 template <typename T>
38 void InsertionSort<T>::compareExchange(T arr[], int l, int r)
39 {
40 if(greater(arr[l], arr[r]))
41 {
42 T temp = arr[l];
43 arr[l] = arr[r];
44 arr[r] = temp;
45 }
46 }
47
48 template <typename T>
49 bool InsertionSort<T>::greater(T left, T right)
50 {
51 return left > right;
52 }
53
54 template <>
55 bool InsertionSort<const char*>::greater(const char *left, const char *right)
56 {
57 return strcmp(left, right) > 0;
58 }
59
60 template <typename T>
61 void print(T arr[], int size)
62 {
63 for(int i = 0; i < size; ++i)
64 std::cout << arr[i] << " ";
65 std::cout << std::endl;
66 }
67
68 template <>
69 void print(std::string arr[], int size)
70 {
71 for(int i = 0; i < size; ++i)
72 std::cout << arr[i].c_str() << " ";
73 std::cout << std::endl;
74 }
75
76 template <>
77 void print(const char *ptrArray, int size)
78 {
79 for(int i = 0; i < size; ++i)
80 std::cout << ptrArray[i] << " ";
81 std::cout << std::endl;
82 }
83
84 int main()
85 {
86 int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
87 InsertionSort<int> isInt;
88 isInt.sort(arr, 9);
89 print(arr, 9);
90
91 std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
92 InsertionSort<std::string> isString;
93 isString.sort(strArr, 8);
94 print(strArr, 8);
95
96 const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
97 InsertionSort<const char*> isPtr;
98 isPtr.sort(ptrArray, 9);
99 print(ptrArray, 9);
100
101 return 0;
102 }
Read more ...
Selection Sort
An elementary sorting technique which finds the smallest element in the array and then exchanges it with the element in the first position 1 #include <iostream>
2
3 class SelectionSort
4 {
5 public:
6 SelectionSort();
7 ~SelectionSort();
8
9 void sort(int arr[], int size);
10
11 private:
12 void exchange(int &x, int &y);
13 };
14
15
16 SelectionSort::SelectionSort() {}
17
18
19 SelectionSort::~SelectionSort() {}
20
21 void SelectionSort::sort(int arr[], int size)
22 {
23 for(int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx)
24 {
25 int min = outerLoopIdx;
26 for(int innerLoopIdx = outerLoopIdx + 1; innerLoopIdx < size; ++innerLoopIdx)
27 {
28 if(arr[min] > arr[innerLoopIdx])
29 {
30 min = innerLoopIdx;
31 }
32 }
33 exchange(arr[outerLoopIdx], arr[min]);
34 }
35 }
36
37 void SelectionSort::exchange(int &x, int &y)
38 {
39 int t = x;
40 x = y;
41 y = t;
42 }
43
44 void print(int arr[], int size)
45 {
46 for(int i = 0; i < size; ++i)
47 std::cout << arr[i] << " ";
48 }
49
50 int main()
51 {
52 int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
53 SelectionSort ss;
54 ss.sort(arr, 9);
55 print(arr, 9);
56 }
Output:
Read more ...
Bubble Sort
This sort gets its name from the way smaller/larger elements gets to the top of the list using bubble comparison
1 #include <iostream>
2
3 class BubbleSort
4 {
5 public:
6 BubbleSort(){}
7 ~BubbleSort(){}
8 void sort(int arr[], int size);
9 };
10
11 void BubbleSort::sort(int arr[], int size)
12 {
13
14 for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
15 {
16 for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
17 {
18
19
20 if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
21 {
22 int temp = arr[innerLoopIdx];
23 arr[innerLoopIdx] = arr[innerLoopIdx + 1];
24 arr[innerLoopIdx + 1] = temp;
25 }
26 }
27 }
28 }
29
30 void print(int arr[], int size)
31 {
32 for(int i = 0; i < size; ++i)
33 std::cout << arr[i] << " ";
34 std::cout << std::endl;
35 }
36
37 int main()
38 {
39 int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
40 BubbleSort bs;
41 bs.sort(arr, 9);
42 print(arr, 9);
43 return 0;
44 }
Output
References:
Bubble Sort Animation
Read more ...
The Problem
Given an array A[n] of n numbers. You have to modify A[n] such that A[i] will be equal to multiplication of all the elements of A[n] except A[i] e.g.
A[0] = A[1] * A[2] * ... * A[n-1] and
A[1] = A[0] * A[2] * ... * A[n-1] You have to solve the problem without using the division operator and in O(n). You cannot make use of another array
Read more ...
The Problem
Given an array A[n] of n numbers. You have to compose an array O[N] such that O[i] will be equal to multiplication of all the elements of A[n] except A[i] e.g.
O[0] = A[1] * A[2] * ... * A[n-1] and
O[1] = A[0] * A[2] * ... * A[n-1]
You have to solve the problem without using the division operator and in O(n).
C++ Program #include <iostream>
#define MAX 5
int main()
{
int arr[MAX] = { 4, 3, 5, 1, 2 };
int product;
int product_of_elems_before[MAX] = {0};
product = 1;
for(int i = 0; i < MAX; ++i)
{
product_of_elems_before[i] = product;
product *= arr[i];
}
int product_of_elems_after[MAX] = {0};
product = 1;
for(int i = MAX - 1; i >= 0; --i)
{
product_of_elems_after[i] = product;
product *= arr[i];
}
for(int i = 0; i < MAX; ++i)
{
arr[i] = product_of_elems_before[i] * product_of_elems_after[i];
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
Java Program public class ArrayMultiplication
{
public static void main(String args[])
{
int[] arr = new int[]{ 3, 2, 1, 4, 5 };
int product;
int productOfElemsBefore[] = new int[arr.length];
product = 1;
for(int i = 0; i < arr.length; ++i)
{
productOfElemsBefore[i] = product;
product *= arr[i];
}
int productOfElemsAfter[] = new int[arr.length];
product = 1;
for(int i = arr.length - 1; i >= 0; --i)
{
productOfElemsAfter[i] = product;
product *= arr[i];
}
for(int i = 0; i < arr.length; ++i)
{
arr[i] = productOfElemsBefore[i] * productOfElemsAfter[i];
System.out.print(arr[i] + " ");
}
}
}
Read more ...
The Problem
There are 3 pegs source ,auxillary and target. n disks of different sizes are given which can slide onto any peg . In the beginning all of the disks are in the source peg in the order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from source peg to target peg such that in the end the target peg will have all the disks in the same order of size.
Rules:
1. Only one disk can be moved from one peg to another peg at a time
2. A larger disk cannot be placed on top of the smaller disk C++ Program #include <iostream>
#include <cstdlib>
static int moveCounter = 0;
void towerOfHanoi(int ndisk, char source, char auxillary, char target)
{
if(ndisk == 1)
{
std::cout << "Move [" << ndisk << "] [" << source << "] to [" <<
target << "]" << std::endl;
++moveCounter;
return;
}
//place ndisk - 1 disks from source to auxillary peg
towerOfHanoi(ndisk - 1, source, target, auxillary);
//place ndisk to target peg
std::cout << "Move [" << ndisk << "] [" << source << "] to [" <<
target << "]" << std::endl;
++moveCounter;
//place ndisk - 1 disks from auxillary to target peg
towerOfHanoi(ndisk - 1, auxillary, source, target);
}
int main(int args, char *argv[])
{
if(argv[1] == NULL)
{
std::cout << "ERROR: Insufficient Arguments\n";
std::cout << "Usage: ./a.out number_of_disks\n";
exit(-1);
}
int disks = atoi(argv[1]);
char peg1 = 'A', peg2 = 'B', peg3 = 'C';
towerOfHanoi(disks, peg1, peg2, peg3);
std::cout << "Total Moves = " << moveCounter << std::endl;
}
Read more ...
The following code checks if the given singly linked list is a palindrome using recursion.
Time Complexity: O(n)
Space Complexity: O(n) C++ Program bool isPalindrome() const
{
Node* node = isPalindrome(head, head);
if(node)
return true;
return false;
}
Node* isPalindrome(Node *left, Node *right) const
{
if(right == NULL)
{
return left;
}
left = isPalindrome(left, right->link);
if(left)
{
bool palindrome = left->ch == right->ch ? true : false;
if(palindrome)
{
left = left->link ? left->link : left;
return left;
}
}
return NULL;
}
Java Program public boolean isPalindrome()
{
Node node = isPalindrome(head, head);
if(node == null)
return false;
return true;
}
private Node isPalindrome(Node left, Node right)
{
if(right == null)
{
return left;
}
left = isPalindrome(left, right.link);
if(left != null)
{
boolean palindrome = left.data == right.data ? true : false;
if(palindrome)
{
left = (left.link != null) ? left.link : left;
return left;
}
}
return null;
}
Read more ...
One of the frequently asked question in the interviews is to reverse a singly-linked list using iterative and recursive approach.
Iterative Approach void ireverse()
{
Node *current = head;
Node *prev = NULL;
Node *next = current->link;
while(next != NULL)
{
current->link = prev;
prev = current;
current = next;
next = next->link;
}
current->link = prev;
head = current;
}
Recursive Approach void reverse(Node *current, Node *prev, Node *next)
{
if(next == NULL)
{
current->link = prev;
head = current;
return;
}
current->link = prev;
reverse(next, current, next->link);
}
1. The complete C++ program can be viewed here
2. Java programmers can find the Java version of the above problem here
Read more ...
Given a string My name is Antonio Gonsalves. You have to reverse all the letters of the words in the string so that the resultant string looks like yM eman si oinotnA sevlasnoG
int main()
{
char str[] = "My name is Antonio Gonsalves",
*startPtr = str,
*endPtr = str,
*spacePtr;
while(*spacePtr != '\0')
{
while(*endPtr != ' ' && *endPtr != '\0')
++endPtr;
spacePtr = endPtr;
endPtr = spacePtr - 1;
char temp;
while(startPtr < endPtr)
{
temp = *endPtr;
*endPtr-- = *startPtr;
*startPtr++ = temp;
}
startPtr = spacePtr + 1;
endPtr = spacePtr + 1;
}
printf("%s\n", str);
return 0;
}
$ ./a.out
yM eman si oinotnA sevlasnoG
Read more ...
There is an important difference between the following two definitions:
char amessage[] = "Hello World";
char *pmessage = "Hello World";
1. amessage is just an array, big enough to hold the sequence of characters and '\0'
2. amessage refers to the same memory location and cannot be changed
3. Individual characters within amessage can be changed
#include <stdio.h>
int main()
{
char amessage[] = "Hello World from the C Program";
amessage[0] = 'P';
printf("%s\n", amessage);
return 0;
}
1. pmessage is a pointer pointing to a string constant
2. The string constant "Hello World" is stored in a read only memory location and cannot be modified
3. pmessage can be changed to point to some other memory location
#include <stdio.h>
int main()
{
char *pmessage = "Hello World from the C Program";
pmessage[0] = 'P'; //throws segmentation fault
printf("%s\n", pmessage);
return 0;
}
Read more ...
The binary tree above can be represented as the following to calculate the vertical sum of the nodes
Read more ...
C++
A node can be removed from a Binary Search Tree using two approaches.
1. Double Pointer Approach
2. Single Pointer Approach
Read more ...
C++
A node can be inserted in a binary search tree using two approaches Double pointer approach
void insert(BinaryTreeNode **node, int data)
{
if(*node == NULL)
{
*node = getNewNode(data);
}
if(data == (*node)->data)
{
//do nothing
}
else if(data < (*node)->data)
{
insert(&(*node)->left, data);
}
else
{
insert(&(*node)->right, data);
}
}
Single pointer approach
BinaryTreeNode* insert(BinaryTreeNode *node, int data)
{
if(node == NULL)
{
node = getNewNode(data);
return node;
}
if(data == node->data)
{
//do nothing
}
else if(data < node->data)
{
node->left = insert(node->left, data);
}
else
{
node->right = insert(node->right, data);
}
return node;
}
Read more ...
Write a C/C++ Program to reverse a stack in place?
You can only use the following ADT functions on the stack:
1. empty()
2. push()
3. pop()
4. top()
Solution:
1. Whenever in place conversion is required, use recursion which will make use of function stack to store the variables
2. Pop out all the elements from the given stack recursively and store them in a variable.
3. As the stack unwinding happens, push the variable obtained at each unwinding step to the bottom of the stack. Refer method push_to_bottom below
void stack_reverse(std::stack<int> &s)
{
if(s.empty())
{
return;
}
int elem = s.top(); s.pop();
stack_reverse(s);
push_to_bottom(s, elem);
}
void push_to_bottom(std::stack<int> &s, int elem)
{
if(s.empty())
{
s.push(elem);
return;
}
int top = s.top(); s.pop();
push_to_bottom(s, elem);
s.push(top);
}
Read more ...
There are basically two ways of traversing a binary tree
1. Depth First Traversals
2. Breadth First Traversal
Depth First Traversal
A binary tree can be traversed in three ways using the depth first approach namely
1. Inorder Traversal
template <typename T>
void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
{
if(node)
{
inOrder(node->left, out);
out.push_back(node->key);
inOrder(node->right, out);
}
}
2. Preorder Traversal
template <typename T>
void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
{
if(node)
{
out.push_back(node->key);
preOrder(node->left, out);
preOrder(node->right, out);
}
}
3. Postorder Traversal
template <typename T>
void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
{
if(node)
{
postOrder(node->left, out);
postOrder(node->right, out);
out.push_back(node->key);
}
}
Breadth First Traversal
There is only one kind of Breadth first traversal viz. Level Order traversal. This traversal does not move along the branches of the tree but makes use of a FIFO queue. In the sample code, I have used std::deque as the helper queue for achieving the same.
template <typename T>
void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
{
std::deque<BSTNode<T>*> hQ;
hQ.push_back(bstree->m_root);
levelOrder(hQ, out);
}
template <typename T>
void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
{
while(hQ.empty() == false)
{
BSTNode<T> *current = hQ.front();
if(current != NULL)
{
hQ.pop_front();
out.push_back(current->key);
addChildren(current, hQ);
}
}
}
The BTTraveller class takes care of returning Binary Tree node elements in the order you are traversing the tree.
1 #ifndef _BTTraveller_H_
2 #define _BTTraveller_H_
3 #include "BSTNode.h"
4 #include <deque>
5
6
7 namespace algorithms
8 {
9 template <typename T>
10 class BTTraveller
11 {
12 public:
13 static void inOrder(BST<T> *bstree, std::deque<T> &elems);
14 static void preOrder(BST<T> *bstree, std::deque<T> &elems);
15 static void postOrder(BST<T> *bstree, std::deque<T> &elems);
16 static void levelOrder(BST<T> *bstree, std::deque<T> &elems);
17
18 private:
19 static void inOrder(BSTNode<T> *node, std::deque<T> &elems);
20 static void preOrder(BSTNode<T> *node, std::deque<T> &elems);
21 static void postOrder(BSTNode<T> *node, std::deque<T> &elems);
22 static void levelOrder(std::deque<BSTNode<T>*> &helperQ, std::deque<T> &elems);
23 static void addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &helperQ);
24
25 BTTraveller();
26 BTTraveller(const BTTraveller&);
27 const BTTraveller& operator=(const BTTraveller&);
28 };
29 };
30
31 #include "BTTraveller.hpp"
32 #endif
1
2 namespace algorithms
3 {
4 template <typename T>
5 void BTTraveller<T>::inOrder(BST<T> *bstree, std::deque<T> &out)
6 {
7 inOrder(bstree->m_root, out);
8 }
9
10 template <typename T>
11 void BTTraveller<T>::preOrder(BST<T> *bstree, std::deque<T> &out)
12 {
13 preOrder(bstree->m_root, out);
14 }
15
16 template <typename T>
17 void BTTraveller<T>::postOrder(BST<T> *bstree, std::deque<T> &out)
18 {
19 postOrder(bstree->m_root, out);
20 }
21
22 template <typename T>
23 void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
24 {
25 std::deque<BSTNode<T>*> hQ;
26 hQ.push_back(bstree->m_root);
27 levelOrder(hQ, out);
28 }
29
30 template <typename T>
31 void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
32 {
33 if(node)
34 {
35 inOrder(node->left, out);
36 out.push_back(node->key);
37 inOrder(node->right, out);
38 }
39 }
40
41 template <typename T>
42 void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
43 {
44 if(node)
45 {
46 out.push_back(node->key);
47 preOrder(node->left, out);
48 preOrder(node->right, out);
49 }
50 }
51
52 template <typename T>
53 void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
54 {
55 if(node)
56 {
57 postOrder(node->left, out);
58 postOrder(node->right, out);
59 out.push_back(node->key);
60 }
61 }
62
63 template <typename T>
64 void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
65 {
66 while(hQ.empty() == false)
67 {
68 BSTNode<T> *current = hQ.front();
69 if(current != NULL)
70 {
71 hQ.pop_front();
72 out.push_back(current->key);
73 addChildren(current, hQ);
74 }
75 }
76 }
77
78 template <typename T>
79 void BTTraveller<T>::addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &hQ)
80 {
81 if(node->left != NULL)
82 {
83 hQ.push_back(node->left);
84 }
85 if(node->right != NULL)
86 {
87 hQ.push_back(node->right);
88 }
89 }
90 }
You need to include BTTraveller class as a friend class in both the BSTNode as well as BST class declarations. This ensures that the BTTraveller class has access to private data members of these two classes
The BSTNode class
1 #ifndef _BSTNode_H_
2 #define _BSTNode_H_
3 #include <iostream>
4
5
6 namespace algorithms
7 {
8 template <typename T>
9 class BST;
10
11 template <typename T>
12 class BTTraveller;
13
14 template <typename T>
15 class BSTNode
16 {
17 public:
18 BSTNode(T key);
19 ~BSTNode();
20
21 friend class BST<T>;
22 friend class BTTraveller<T>;
23
24 private:
25 BSTNode<T> *left;
26 BSTNode<T> *right;
27 T key;
28 };
29 };
30
31 #include "BSTNode.hpp"
32 #endif
The BST class
1 #ifndef _BinarySearchTree_H_
2 #define _BinarySearchTree_H_
3 #include "BSTNode.h"
4
5
6 namespace algorithms
7 {
8 template <typename T>
9 class BTTraveller;
10
11 template <typename T>
12 class BST
13 {
14 public:
15 BST();
16 ~BST();
17
18
19 void insert(T key);
20 void remove(T key);
21 void clear();
22
23
24 bool find(T key);
25 bool isEmpty() const;
26
27 friend class BTTraveller<T>;
28
29 private:
30 void remove(BSTNode<T> **node);
31 void clear(BSTNode<T> *node);
32 BSTNode<T>** find(BSTNode<T> **node, const T key);
33 BSTNode<T>** getSuccessor(BSTNode<T> **node);
34 BSTNode<T>* getNewNode(T key);
35
36
37 BSTNode<T> *m_root;
38 };
39 };
40
41 #include "BST.hpp"
42 #endif
The BSTNode.hpp and BST.hpp files remains the same as in the post
The Client Program
1 #include "BST.h"
2 #include "BTTraveller.h"
3 #define MAX 20
4 using namespace algorithms;
5
6
7
8 template <typename T>
9 void DumpDeque(std::deque<T> &q)
10 {
11 std::cout << std::endl;
12 std::deque<T>::const_iterator itr;
13 for(itr = q.cbegin(); itr != q.cend(); ++itr)
14 {
15 std::cout << *itr << " ";
16 }
17 std::cout << std::endl;
18 q.clear();
19 }
20
21 int main(int argc, char *argv[])
22 {
23 int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120, 111 };
24 BST<int> bstInt;
25 for(int i = 0; i < MAX; ++i)
26 {
27 bstInt.insert(nodes[i]);
28 }
29
30 std::deque<int> elems;
31 BTTraveller<int>::inOrder(&bstInt, elems);
32 DumpDeque(elems);
33 BTTraveller<int>::preOrder(&bstInt, elems);
34 DumpDeque(elems);
35 BTTraveller<int>::postOrder(&bstInt, elems);
36 DumpDeque(elems);
37 BTTraveller<int>::levelOrder(&bstInt, elems);
38 DumpDeque(elems);
39
40 return 0;
41 }
Output
$ ./BinarySearchTree.exe
1 5 10 15 20 30 35 40 50 60 65 70 75 80 90 100 110 111 120 130
50 40 20 10 5 1 15 30 35 60 70 65 80 75 90 100 110 130 120 111
1 5 15 10 35 30 20 40 65 75 111 120 130 110 100 90 80 70 60 50
50 40 60 20 70 10 30 65 80 5 15 35 75 90 1 100 110 130 120 111
Read more ...
A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree.
The programs below describes the three basic operations in a binary search tree viz. search, insert and remove
1. Searching a node
template <typename T>
BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
{
if(*node == NULL || (*node)->key == key)
{
return node;
}
else if((*node)->key > key)
{
return find(&(*node)->left, key);
}
else
{
return find(&(*node)->right, key);
}
}
2. Inserting a node
template <typename T>
void BST<T>::insert(T key)
{
BSTNode<T> **node = find(&m_root, key);
if(*node == NULL)
{
*node = getNewNode(key);
}
}
3. Removing a node
Removing a node from binary search tree is the trickiest of all the operations. There are three cases to be considered when removing a node from a binary search tree:
Case 1. If both left and right child are null, the node can simply be deleted.
Case 2. If only one of the right child or left child is null, the address of the node is set to point to the left child or the right child which ever is not null and the current node is deleted.
Case 3. The complex of the three cases, if both left and right child are present. This requires finding the successor of the current node which is to be removed.
template <typename T>
void BST<T>::remove(BSTNode<T> **node)
{
BSTNode<T> *old = *node;
if((*node)->left == NULL)
{
*node = (*node)->right;
delete old;
}
else if((*node)->right == NULL)
{
*node = (*node)->left;
delete old;
}
else
{
BSTNode<T> **successor = getSuccessor(node);
(*node)->key = (*successor)->key;
remove(successor);
}
}
Following is the complete example showing the implementation details of the search, find and remove operations in a binary search tree.
The BST Node Class
1 #ifndef _BSTNode_H_
2 #define _BSTNode_H_
3 #include <iostream>
4
5
6 namespace algorithms
7 {
8 template <typename T>
9 class BST;
10
11 template <typename T>
12 class BSTNode
13 {
14 public:
15 BSTNode(T key);
16 ~BSTNode();
17
18 friend class BST<T>;
19
20 private:
21 BSTNode<T> *left;
22 BSTNode<T> *right;
23 T key;
24 };
25 };
26
27 #include "BSTNode.hpp"
28 #endif
1
2 namespace algorithms
3 {
4 template <typename T>
5 BSTNode<T>::BSTNode(T key) : left(0), right(0)
6 {
7 this->key = key;
8 }
9
10 template <typename T>
11 BSTNode<T>::~BSTNode()
12 {
13 }
14 }
15
The Binary Search Tree Class
1 #ifndef _BinarySearchTree_H_
2 #define _BinarySearchTree_H_
3 #include "BSTNode.h"
4
5
6 namespace algorithms
7 {
8 template <typename T>
9 class BST
10 {
11 public:
12 BST();
13 ~BST();
14
15
16 void insert(T key);
17 void remove(T key);
18 void clear();
19
20
21 bool find(T key);
22 bool isEmpty() const;
23
24 private:
25 void remove(BSTNode<T> **node);
26 void clear(BSTNode<T> *node);
27 BSTNode<T>** find(BSTNode<T> **node, const T key);
28 BSTNode<T>** getSuccessor(BSTNode<T> **node);
29 BSTNode<T>* getNewNode(T key);
30
31
32 BSTNode<T> *m_root;
33 };
34 };
35
36 #include "BST.hpp"
37 #endif
1
2 namespace algorithms
3 {
4 template <typename T>
5 BST<T>::BST()
6 {
7 m_root = 0;
8 }
9
10 template <typename T>
11 BST<T>::~BST()
12 {
13 clear();
14 }
15
16 template <typename T>
17 void BST<T>::clear()
18 {
19 clear(m_root);
20 }
21
22 template <typename T>
23 void BST<T>::clear(BSTNode<T> *node)
24 {
25 if(node != NULL)
26 {
27 clear(node->left);
28 clear(node->right);
29 delete node;
30 }
31 }
32
33 template <typename T>
34 void BST<T>::insert(T key)
35 {
36 BSTNode<T> **node = find(&m_root, key);
37 if(*node == NULL)
38 {
39 *node = getNewNode(key);
40 }
41 }
42
43 template <typename T>
44 void BST<T>::remove(T key)
45 {
46 BSTNode<T> **node = find(&m_root, key);
47 remove(node);
48 }
49
50 template <typename T>
51 void BST<T>::remove(BSTNode<T> **node)
52 {
53 BSTNode<T> *old = *node;
54 if((*node)->left == NULL)
55 {
56 *node = (*node)->right;
57 delete old;
58 }
59 else if((*node)->right == NULL)
60 {
61 *node = (*node)->left;
62 delete old;
63 }
64 else
65 {
66 BSTNode<T> **successor = getSuccessor(node);
67 (*node)->key = (*successor)->key;
68 remove(successor);
69 }
70 }
71
72 template <typename T>
73 BSTNode<T>** BST<T>::getSuccessor(BSTNode<T> **node)
74 {
75 BSTNode<T> **tmp = &(*node)->left;
76 while((*tmp)->right != NULL)
77 {
78 tmp = &(*tmp)->right;
79 }
80 return tmp;
81 }
82
83 template <typename T>
84 bool BST<T>::find(const T key)
85 {
86 BSTNode<T> **pos = find(&m_root, key);
87 return *pos != NULL;
88 }
89
90 template <typename T>
91 bool BST<T>::isEmpty() const
92 {
93 return m_root == 0;
94 }
95
96 template <typename T>
97 BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
98 {
99 if(*node == NULL || (*node)->key == key)
100 {
101 return node;
102 }
103 else if((*node)->key > key)
104 {
105 return find(&(*node)->left, key);
106 }
107 else
108 {
109 return find(&(*node)->right, key);
110 }
111 }
112
113 template <typename T>
114 BSTNode<T>* BST<T>::getNewNode(T key)
115 {
116 BSTNode<T> *node = new BSTNode<T>(key);
117 if(node == NULL)
118 {
119 std::cerr << "ERROR: Insufficient Memory";
120 std::cerr << std::endl;
121 }
122 return node;
123 }
124 }
The Client Program for testing the BST code above
1 #include "BST.h"
2 #define MAX 20
3 using namespace algorithms;
4
5
6 int main(int argc, char *argv[])
7 {
8 int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120 };
9 BST<int> bstInt;
10 for(int i = 0; i < MAX; ++i)
11 {
12 bstInt.insert(nodes[i]);
13 }
14
15 std::cout << (bstInt.find(130) ? "true" : "false");
16 bstInt.remove(50);
17 std::cout << (bstInt.find(50) ? "true" : "false");
18
19 return 0;
20 }
Output of the run
$ ./BinarySearchTree.exe
truefalse
Read more ...
Static library is a group of object files bundled together in an archive by the archiver program. The static libraries have a .a extension.
Advantages
1. The executable is not dependent on any library as the library code is included in the binary
2. In some cases performance improvement Command for creating a static library
ar rcs -o libmylibrary.a file1.o file2.o file3.o
Steps for generating the static library libemployee.a for the Employee Program written in the previous post
1. Compiling source files to object files
g++ -Wall -c -fPIC -O -I. -o Employee.o Employee.cpp 2. Command for building the archive file libemployee.a
ar -rcs -o libemployee.a Employee.o
Read more ...
A shared library is a library required by an executable to run properly. Such executables are called incomplete executables as they call routines present in the shared library code. The executables generated from the shared library are smaller in size than the ones generated from a static library
When an executable built with shared library is run, the dynamic loader identifies the list of dependent libraries to be loaded and searches for them in the standard default locations and the locations pointed to by the environment variable LD_LIBRARY_PATH (Linux), SHLIB_PATH (HP-UX), LIBPATH (AIX)
Shown below is the Employee class which we will use to generate the shared library libemployee.so
1 #ifndef _Employee_H_
2 #define _Employee_H_
3
4
5
6 #include <iostream>
7
8 class Employee
9 {
10 public:
11 Employee();
12 Employee(const std::string name, int age);
13 virtual ~Employee();
14
15
16 void setName(const std::string name);
17 void setAge(int age);
18
19
20 const char* getName() const;
21 int getAge() const;
22
23 private:
24 std::string m_name;
25 int m_age;
26 };
27
28 #endif
1 #include "Employee.h"
2
3
4 Employee::Employee()
5 {
6 }
7
8 Employee::Employee(const std::string name, int age)
9 {
10 m_name = name;
11 m_age = age;
12 }
13
14 Employee::~Employee()
15 {
16 }
17
18 void Employee::setName(const std::string name)
19 {
20 m_name = name;
21 }
22
23 void Employee::setAge(int age)
24 {
25 m_age = age;
26 }
27
28 const char* Employee::getName() const
29 {
30 return m_name.c_str();
31 }
32
33 int Employee::getAge() const
34 {
35 return m_age;
36 }
Compiling the Employee source files to object files g++ -Wall -c -fPIC -O -I. -o Employee.o Employee.cpp
Linking the object files to generate the shared library libemployee.so gcc -o libemployee.so Employee.o -shared -fPIC -Wl,-rpath,. -L. -lstdc++
Read more ...
A process is a program in execution. A process may have one or more threads executing different sections of the program. Every thread in the process maintains it's own separate stack, registers and program counter.
Key Points
A stack is a collection of stack frames where each stack frame refers to a function call
Stack Frame
When a function call is made, a block of memory is set aside which stores information about the following:
1. Arguments passed to the function
2. Return address of the caller function
3. Local variables used by the function and
4. Other temporary variables needed by the compiler
This block of memory is called a stack frame. When the function returns, the stack frame is turned invalid and reclaimed.
Registers used in a Stack Frame
1. ESP (Extended Stack Pointer) : 32 bit register that points to the top of the stack. All the addresses lower than the stack pointer are considered unused or garbage and all the higher addresses are considered valid
2. EBP (Extended Base Pointer) : Also known as Frame Pointer, this 32 bit register is used to reference all the function parameters and the local variables in the current stack frame
ebp + 4 + 4 * n points to the address at which the nth argument of the function is stored
ebp + 4 points to the address at which return address of the caller function is stored
ebp is the frame pointer of the callee function
ebp - 4n refers to the address where the nth local variable is stored
3. EIP (Extended Instruction Pointer) : This register holds the address of the next instruction to be executed. It is saved on to the stack as part of the CALL instruction. Also known as Program Counter
4. EAX, EBX, ECX, EDX : General purpose registers for storing intermediate results
Following figure shows how stack frames are laid out in memory during execution
Read more ...
Continuing our series on makefile tutorial, below is a simple makefile which compiles the Hello World program Main.cpp into an object file Main.o and generates the binary executable Main.exe
PROJECT := Main
SRCEXT := .h .cpp
OBJEXT := .o
EXEEXT := .exe
CC := gcc
CXX := g++
CFLAGS := -o
CXXFLAGS := -o
LDFLAGS := -o
.SUFFIXES:
.SUFFIXES: $(SRCEXT) $(OBJEXT) $(EXEEXT)
SRC := \
Main.cpp
OBJ := \
$(SRC:.cpp=.o)
EXE := \
$(PROJECT)$(EXEEXT)
.PHONY: all clean compile link
all : compile link
clean :
@echo
@echo "Cleaning Temporary Files..."
$(RM) $(OBJ) $(EXE)
compile : $(OBJ)
link : $(EXE)
$(OBJ) :
@echo
@echo "Compiling Source Files..."
$(CXX) $(CXXFLAGS) $(OBJ) $(SRC)
$(EXE) :
@echo
@echo "Linking..."
$(LD) $(OBJ) $(LDFLAGS) $(EXE)
run :
@echo
@$(EXE)
The Hello World program
#include <iostream>
int main()
{
printf("Hello World");
return 0;
}
Output
Read more ...
|
|
