Data Structure and Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/* Search an array for a key using Binary Search (BinarySearch.cpp) */
#include <iostream>
using namespace std;
 
int binarySearch(const int a[], int size, int key);
int binarySearch(const int a[], int iLeft, int iRight, int key);
void print(const int a[], int iLeft, int iRight);
 
int main() {
   const int SIZE = 10;
   int a1[SIZE] = {1, 4, 5, 8, 12, 19, 24, 31, 43, 55}; // sorted
 
   cout << binarySearch(a1, SIZE, 8) << endl;
   cout << binarySearch(a1, SIZE, 12) << endl;
   cout << binarySearch(a1, SIZE, 24) << endl;
   cout << binarySearch(a1, SIZE, 21) << endl;
}
 
// Search the array for the given key
// If found, return array index; otherwise, return -1
int binarySearch(const int a[], int size, int key) {
   // Call recursive helper function
   return binarySearch(a, 0, size-1, key);
}
 
// Recursive helper function for binarySearch
int binarySearch(const int a[], int iLeft, int iRight, int key) {
   // For tracing the algorithm
   print(a, iLeft, iRight);
 
   // Test for empty list
   if (iLeft > iRight) return -1;
 
   // Compare with middle element
   int mid = (iRight + iLeft) / 2;  // truncate
   if (key == a[mid]) {
      return mid;
   } else if (key < a[mid]) {
      // Recursively search the lower half
      binarySearch(a, iLeft, mid - 1, key);
   } else {
      // Recursively search the upper half
      binarySearch(a, mid + 1, iRight, key);
   }
}
 
// Print the contents of the given array from iLeft to iRight (inclusive)
void print(const int a[], int iLeft, int iRight) {
   cout << "{";
   for (int i = iLeft; i <= iRight; ++i) {
      cout << a[i];
      if (i < iRight) cout << ",";
   }
   cout << "}" << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

/* Sorting an array using Merge Sort (MergeSort.cpp) */
#include <iostream>
using namespace std;
 
void mergeSort(int a[], int size);
void mergeSort(int a[], int iLeft, int iRight, int work[]);
void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,
           int iRightHalfLeft, int iRightHalfRight, int work[]);
void print(const int a[], int iLeft, int iRight);
 
int main() {
   // Test 1
   const int SIZE_1 = 8;
   int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1};
 
   print(a1, 0, SIZE_1 - 1);
   cout << endl;
   mergeSort(a1, SIZE_1);
   print(a1, 0, SIZE_1 - 1);
   cout << endl << endl;
 
   // Test 2
   const int SIZE_2 = 13;
   int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5};
 
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
   mergeSort(a2, SIZE_2);
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
}
 
// Sort the given array of size
void mergeSort(int a[], int size) {
   int work[size];  // work space
   mergeSort(a, 0, size - 1, work);
}
 
// Sort the given array in [iLeft, iRight]
void mergeSort(int a[], int iLeft, int iRight, int work[]) {
   if ((iRight - iLeft) >= 1) {   // more than 1 elements, divide and sort
      // Divide into left and right half
      int iLeftHalfLeft = iLeft;
      int iLeftHalfRight = (iRight + iLeft) / 2;   // truncate
      int iRightHalfLeft = iLeftHalfRight + 1;
      int iRightHalfRight = iRight;
 
      // Recursively sort each half
      mergeSort(a, iLeftHalfLeft, iLeftHalfRight, work);
      mergeSort(a, iRightHalfLeft, iRightHalfRight, work);
 
      // Merge two halves
      merge(a, iLeftHalfLeft, iLeftHalfRight, iRightHalfLeft, iRightHalfRight, work);
   }
}
 
// Merge two halves in [iLeftHalfLeft, iLeftHalfRight] and [iRightHalfLeft, iRightHalfRight]
// Assume that iLeftHalfRight + 1 = iRightHalfLeft
void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,
           int iRightHalfLeft, int iRightHalfRight, int work[]) {
   int size = iRightHalfRight - iLeftHalfLeft + 1;
   int iResult = 0;
   int iLeft = iLeftHalfLeft;
   int iRight = iRightHalfLeft;
   while (iLeft <= iLeftHalfRight && iRight <= iRightHalfRight) {
      if (a[iLeft] <= a[iRight]) {
         work[iResult++] = a[iLeft++];
      } else {
         work[iResult++] = a[iRight++];
      }
   }
   // Copy the remaining left or right into work
   while (iLeft <= iLeftHalfRight) work[iResult++] = a[iLeft++];
   while (iRight <= iRightHalfRight) work[iResult++] = a[iRight++];
 
   // for tracing
   print(a, iLeftHalfLeft, iLeftHalfRight);
   print(a, iRightHalfLeft, iRightHalfRight);
   cout << "=> ";
   print(work, 0, size - 1);
   cout << endl;
 
   // Copy the work back to the original array
   for (iResult = 0, iLeft = iLeftHalfLeft; iResult < size; ++iResult, ++iLeft) {
      a[iLeft] = work[iResult];
   }
}
 
// Print the contents of the given array from iLeft to iRight (inclusive)
void print(const int a[], int iLeft, int iRight) {
   cout << "{";
   for (int i = iLeft; i <= iRight; ++i) {
      cout << a[i];
      if (i < iRight) cout << ",";
   }
   cout << "} ";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

/* Sorting an array using Merge Sort with bottom-up interactive algorithm
   (MergeSortInteractive.cpp) */
#include <iostream>
using namespace std;
 
void mergeSort(int a[], int size);
void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,
           int iRightHalfLeft, int iRightHalfRight, int work[]);
void print(const int a[], int iLeft, int iRight);
 
int main() {
   // Test 1
   const int SIZE_1 = 8;
   int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1};
 
   print(a1, 0, SIZE_1 - 1);
   cout << endl;
   mergeSort(a1, SIZE_1);
   print(a1, 0, SIZE_1 - 1);
   cout << endl << endl;
 
   // Test 2
   const int SIZE_2 = 13;
   int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5};
 
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
   mergeSort(a2, SIZE_2);
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
}
 
// Sort the given array of size
void mergeSort(int a[], int size) {
   int work[size];  // work space
   int width = 1;   // width of sublists to merge
 
   while (width < size) {
      // Merge 2 sublists of width
      for (int i = 0; i < size - width; i += 2*width) {
         // Get the bounds of left and right sublists
         int iLeftHalfLeft = i;
         int iLeftHalfRight = i + width - 1;
         int iRightHalfLeft = i + width;
         int iRightHalfRight = i + 2*width - 1;
         if (iRightHalfRight >= size - 1) iRightHalfRight = size - 1;
 
         // Merge left and right sublists
         merge(a, iLeftHalfLeft, iLeftHalfRight, iRightHalfLeft, iRightHalfRight, work);
      }
      width *= 2;
   }
}
 
// Merge two halves in [iLeftHalfLeft, iLeftHalfRight] and [iRightHalfLeft, iRightHalfRight]
// Assume that iLeftHalfRight + 1 = iRightHalfLeft
void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,
           int iRightHalfLeft, int iRightHalfRight, int work[]) {
   int size = iRightHalfRight - iLeftHalfLeft + 1;
   int iResult = 0;
   int iLeft = iLeftHalfLeft;
   int iRight = iRightHalfLeft;
   while (iLeft <= iLeftHalfRight && iRight <= iRightHalfRight) {
      if (a[iLeft] <= a[iRight]) {
         work[iResult++] = a[iLeft++];
      } else {
         work[iResult++] = a[iRight++];
      }
   }
   // Copy the remaining left or right into work
   while (iLeft <= iLeftHalfRight) work[iResult++] = a[iLeft++];
   while (iRight <= iRightHalfRight) work[iResult++] = a[iRight++];
 
   // for tracing
   print(a, iLeftHalfLeft, iLeftHalfRight);
   print(a, iRightHalfLeft, iRightHalfRight);
   cout << "=> ";
   print(work, 0, size - 1);
   cout << endl;
 
   // Copy the work back to the original array
   for (iResult = 0, iLeft = iLeftHalfLeft; iResult < size; ++iResult, ++iLeft) {
      a[iLeft] = work[iResult];
   }
}
 
// Print the contents of the given array from iLeft to iRight (inclusive)
void print(const int a[], int iLeft, int iRight) {
   cout << "{";
   for (int i = iLeft; i <= iRight; ++i) {
      cout << a[i];
      if (i < iRight) cout << ",";
   }
   cout << "} ";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

/* Sorting an array using Quick Sort (QuickSort.cpp) */
#include <iostream>
using namespace std;
 
void quickSort(int a[], int size);
void quickSort(int a[], int left, int right);
void choosePivot(int a[], int left, int right);
int partition(int a[], int left, int right);
void print(const int a[], int left, int right);
 
int main() {
   // Test 1
   const int SIZE_1 = 8;
   int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1};
 
   print(a1, 0, SIZE_1 - 1);
   cout << endl;
   quickSort(a1, SIZE_1);
   print(a1, 0, SIZE_1 - 1);
   cout << endl << endl;
 
   // Test 2
   const int SIZE_2 = 13;
   int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5};
 
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
   quickSort(a2, SIZE_2);
   print(a2, 0, SIZE_2 - 1);
   cout << endl;
}
 
// Sort the given array of size
void quickSort(int a[], int size) {
   quickSort(a, 0, size - 1);
}
 
// Sort the given array in [left, right]
void quickSort(int a[], int left, int right) {
   if ((right - left) >= 1) {   // more than 1 elements, need to sort
      choosePivot(a, left, right);
      int pivotIndex = partition(a, left, right);
      quickSort(a, left, pivotIndex -  1);
      quickSort(a, pivotIndex + 1, right);
   }
}
 
// Choose a pivot element and swap with the right
void choosePivot(int a[], int left, int right) {
   int pivotIndex = (right + left) / 2;
   int temp;
   temp = a[pivotIndex];
   a[pivotIndex] = a[right];
   a[right] = temp;
}
 
// Partition the array [left, right] with pivot initially on the right.
// Return the index of the pivot after partition, all elements to the
// left of pivot are smaller; while to the right are larger.
int partition(int a[], int left, int right) {
   int pivot = a[right];
   int temp;  // for swapping
   int storeIndex = left;
      // Start the storeIndex from left, swap elements smaller than
      //  pivot into storeIndex and increase the storeIndex.
      // At the end of the pass, all elements up to storeIndex are
      //  smaller than pivot.
   for (int i = left; i < right; ++i) {  // exclude pivot
      if (a[i] < pivot) {
         // for tracing
         print(a, left, right);
 
         if (i != storeIndex) {
            temp = a[i];
            a[i] = a[storeIndex];
            a[storeIndex] = temp;
         }
         ++storeIndex;
 
         // for tracing
         cout << "=> ";
         print(a, left, right);
         cout << endl;
      }
   }
   // Swap pivot and storeIndex
   a[right] = a[storeIndex];
   a[storeIndex] = pivot;
 
   // for tracing
   print(a, left, storeIndex - 1);
   cout << "{" << a[storeIndex] << "} ";
   print(a, storeIndex + 1, right);
   cout << endl;
 
   return storeIndex;
}
 
// Print the contents of the given array from left to right (inclusive)
void print(const int a[], int left, int right) {
   cout << "{";
   for (int i = left; i <= right; ++i) {
      cout << a[i];
      if (i < right) cout << ",";
   }
   cout << "} ";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

/* Bucket Sort (Radix Sort)  (BucketSort.cpp) */
#include <iostream>
#include <vector>
using namespace std;
 
void bucketSort(int a[], int size);
void bucketSort(vector<int> & list, int radix);
void printBuckets(const vector<int> buckets[], int size);
void print(const vector<int> list);
 
const int NUM_BUCKETS = 10;
 
int main() {
   const int SIZE = 13;
   int a[] = {28, 104, 25, 593, 22, 129, 4, 11, 129, 4, 111, 20, 9};
   bucketSort(a, SIZE);
}
 
void bucketSort(int a[], int size) {
   // find maximum to decide on the number of significant digits
   int max = a[0];
   for (int i = 1; i < size; ++i) {
      if (a[i] > max) max = a[i];
   }
 
   // Decide on the max radix (1000, 100, 10, 1, etc)
   int radix = 1;
   while (max > 10) {
      radix *= 10;
      max /= 10;
   }
 
   // copy the array into a vector
   vector<int> list(size);
   for (int i = 0; i < size; ++i) {
      list[i] = a[i];
   }
   bucketSort(list, radix);
}
 
// Sort the given array of size on the particular radix (1, 10, 100, etc)
// Assume elements are non-negative integers
// radix shall be more than 0
void bucketSort(vector<int> & list, int radix) {
   if (list.size() > 1 && radix > 0) {  // Sort if more than 1 elements
      // For tracing
      cout << "To sort: ";
      print(list);
 
      vector<int> buckets[NUM_BUCKETS];  // 10 buckets
 
      // Distribute elements into buckets
      for (int i = 0; i < list.size(); ++i) {
         int bucketIndex = list[i] / radix % 10;
         buckets[bucketIndex].push_back(list[i]);
      }
 
      // For tracing
      cout << "radix=" << radix << ": ";
      printBuckets(buckets, NUM_BUCKETS);
 
      // Recursively sort the non-empty bucket
      for (int bi = 0; bi < NUM_BUCKETS; ++bi) {
         if (buckets[bi].size() > 0) {
            bucketSort(buckets[bi], radix / 10);
         }
      }
 
      // Gather all the buckets into list and return
      list.resize(0);  // remove all elements
      for (int bi = 0; bi < NUM_BUCKETS; ++bi) {
         for (int j = 0; j < buckets[bi].size(); ++j) {
            list.push_back((buckets[bi])[j]);
         }
      }
 
      // For tracing
      cout << "Sorted: ";
      print(list);
   }
}
 
// Print the contents of all buckets
void printBuckets(const vector<int> buckets[], int size) {
   for (int i = 0; i < size; ++i) {
      // print each bucket
      cout << "{";
      for (int bi = 0; bi < buckets[i].size(); ++bi) {
         cout << (buckets[i])[bi];
         if (bi < buckets[i].size() - 1) cout << ",";
      }
      cout << "} ";
   }
   cout << endl;
}
 
// Print the contents of vector<int>
void print(const vector<int> list) {
   cout << "{";
   for (int i = 0; i < list.size(); ++i) {
      cout << list[i];
      if (i < list.size() - 1) cout << ",";
   }
   cout << "}" << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#ifndef NODE_H
#define NODE_H
 
template <typename T> class List;  // Forward reference
 
template <typename T>
class Node {
private:
   T data;
   Node * nextPtr;
public:
   Node (T d) : data(d), nextPtr(0) { }; // Constructor
   T getData() const { return data; };   // Public getter for data
   Node * getNextPtr() const { return nextPtr; } // Public getter for nextPtr
 
friend class List<T>;  // Make List class a friend to access private data
};
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#ifndef LIST_H
#define LIST_H
 
#include <iostream>
#include "Node.h"
 
// Forward Reference
template <typename T>
std::ostream & operator<<(std::ostream & os, const List<T> & lst);
 
template <typename T>
class List {
private:
   Node<T> * frontPtr;  // First node
   Node<T> * backPtr;   // Last node
public:
   List();   // Constructor
   ~List();  // Destructor
   void pushFront(const T & value);
   void pushBack(const T & value);
   bool popFront(T & value);
   bool popBack(T & value);
   bool isEmpty() const;
 
friend std::ostream & operator<< <>(std::ostream & os, const List<T> & lst);
      // Overload the stream insertion operator to print the list
};
 
// Constructor - Create an empty list without any node
template <typename T>
List<T>::List() : frontPtr(0), backPtr(0) { }
 
// Destructor - Remove all the dynamically allocated nodes
template <typename T>
List<T>::~List() {
   while (frontPtr) {
      Node<T> * tempPtr = frontPtr;
      frontPtr = frontPtr->nextPtr;
      delete tempPtr;
   }
   // std::cout << "Destructor completed..." << std::endl;
}
 
// Is list empty? Check if frontPtr is null
template <typename T>
bool List<T>::isEmpty() const { return frontPtr == 0; }
 
// Push the data in front by dynamically allocate a new node
template <typename T>
void List<T>::pushFront(const T & value) {
   Node<T> * newNodePtr = new Node<T>(value);
   if (isEmpty()) {
      frontPtr = backPtr = newNodePtr;
   } else {
      newNodePtr->nextPtr = frontPtr;
      frontPtr = newNodePtr;
   }
}
 
// Push the data at the end by dynamically allocate a new node
template <typename T>
void List<T>::pushBack(const T & value) {
   Node<T> * newNodePtr = new Node<T>(value);
   if (isEmpty()) {
      frontPtr = backPtr = newNodePtr;
   } else {
      backPtr->nextPtr = newNodePtr;
      backPtr = newNodePtr;
   }
}
 
// Pop and the data in front to value and remove the node
template <typename T>
bool List<T>::popFront(T & value) {
   if (isEmpty()) {
      return false;
   } else if (frontPtr == backPtr) {  // only one node
      value = frontPtr->data;
      delete frontPtr;         // remove node
      frontPtr = backPtr = 0;  // empty
   } else {
      value = frontPtr->data;
      Node<T> * tempPtr = frontPtr;
      frontPtr = frontPtr->nextPtr;
      delete tempPtr;
   }
   return true;
}
 
// Pop and the data at the end to value and remove the node
template <typename T>
bool List<T>::popBack(T & value) {
   if (isEmpty()) {
      return false;
   } else if (frontPtr == backPtr) {  // only one node
      value = backPtr->data;
      delete backPtr;          // remove node
      frontPtr = backPtr = 0;  // empty
   } else {
      // Locate second to last node
      Node<T> * currentPtr = frontPtr;
      while (currentPtr->nextPtr != backPtr) {
         currentPtr = currentPtr->nextPtr;
      }
      value = backPtr->data;
      delete backPtr;          // remove last node
      backPtr = currentPtr;
      currentPtr->nextPtr = 0;
   }
   return true;
}
 
// Overload the stream insertion operator to print the list
template <typename T>
std::ostream & operator<< (std::ostream & os, const List<T> & lst) {
   os << '{';
   if (!lst.isEmpty()) {
      Node<T> * currentPtr = lst.frontPtr;
      while (currentPtr) {
         os << currentPtr->getData();
         if (currentPtr != lst.backPtr) os << ',';
         currentPtr = currentPtr->getNextPtr();
      }
   }
   os << '}';
}
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/* Test Driver for List class (TestList.cpp) */
#include <iostream>
#include "List.h"
using namespace std;
 
int main() {
 
   List<int> lst1;
   cout << lst1 << endl;
   lst1.pushFront(8);
   lst1.pushBack(88);
   lst1.pushFront(9);
   lst1.pushBack(99);
   cout << lst1 << endl;
 
   int result;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popFront(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popFront(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* DoubleLinkedNode template class for double linked list (DoubleLinkedNode.h) */
#ifndef DOUBLE_LINKED_NODE_H
#define DOUBLE_LINKED_NODE_H
 
template <typename T> class DoubleLinkedList; // Forward reference
 
template <typename T>
class DoubleLinkedNode {
private:
   T data;
   DoubleLinkedNode * nextPtr;
   DoubleLinkedNode * prevPtr;
public:
   DoubleLinkedNode (T d) : data(d), nextPtr(0), prevPtr(0) { };
   T getData() const { return data; };
   DoubleLinkedNode * getNextPtr() const { return nextPtr; }
   DoubleLinkedNode * getPrevPtr() const { return prevPtr; }
 
friend class DoubleLinkedList<T>;
   // Make DoubleLinkedList class a friend to access private data
};
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

/* DoubleLinkedList template class for double linked list
   (DoubleLinkedList.h) */
#ifndef DOUBLE_LINKED_LIST_H
#define DOUBLE_LINKED_LIST_H
 
#include <iostream>
#include "DoubleLinkedNode.h"
 
// Forward Reference
template <typename T>
std::ostream & operator<<(std::ostream & os,
      const DoubleLinkedList<T> & lst);
 
template <typename T>
class DoubleLinkedList {
private:
   DoubleLinkedNode<T> * frontPtr;
   DoubleLinkedNode<T> * backPtr;
public:
   DoubleLinkedList();   // Constructor
   ~DoubleLinkedList();  // Destructor
   void pushFront(const T & value);
   void pushBack(const T & value);
   bool popFront(T & value);
   bool popBack(T & value);
   bool isEmpty() const;
 
friend std::ostream & operator<< <>(std::ostream & os,
      const DoubleLinkedList<T> & lst);
      // Overload the stream insertion operator to print the list
};
 
// Constructor - Create an empty list with no node
template <typename T>
DoubleLinkedList<T>::DoubleLinkedList() : frontPtr(0), backPtr(0) { }
 
// Destructor - Remove all the dynamically allocated nodes
template <typename T>
DoubleLinkedList<T>::~DoubleLinkedList() {
   while (frontPtr) {
      DoubleLinkedNode<T> * tempPtr = frontPtr;
      frontPtr = frontPtr->nextPtr;
      delete tempPtr;
   }
   // std::cout << "Destructor completed..." << std::endl;
}
 
// Is list empty? Check if frontPtr is null
template <typename T>
bool DoubleLinkedList<T>::isEmpty() const { return frontPtr == 0; }
 
// Push the data in front by dynamically allocate a new node
template <typename T>
void DoubleLinkedList<T>::pushFront(const T & value) {
   DoubleLinkedNode<T> * newPtr = new DoubleLinkedNode<T>(value);
   if (isEmpty()) {
      frontPtr = backPtr = newPtr;
   } else {
      frontPtr->prevPtr = newPtr;
      newPtr->nextPtr = frontPtr;
      frontPtr = newPtr;
   }
}
 
// Push the data at the end by dynamically allocate a new node
template <typename T>
void DoubleLinkedList<T>::pushBack(const T & value) {
   DoubleLinkedNode<T> * newPtr = new DoubleLinkedNode<T>(value);
   if (isEmpty()) {
      frontPtr = backPtr = newPtr;
   } else {
      backPtr->nextPtr = newPtr;
      newPtr->prevPtr = backPtr;
      backPtr = newPtr;
   }
}
 
// Pop and the data in front to value and remove the node
template <typename T>
bool DoubleLinkedList<T>::popFront(T & value) {
   if (isEmpty()) {
      return false;
   } else if (frontPtr == backPtr) {  // only one node
      value = frontPtr->data;
      delete frontPtr;         // remove node
      frontPtr = backPtr = 0;  // empty
   } else {
      value = frontPtr->data;
      DoubleLinkedNode<T> * tempPtr = frontPtr;
      frontPtr = frontPtr->nextPtr;
      frontPtr->prevPtr = 0;
      delete tempPtr;
   }
   return true;
}
 
// Pop and the data at the end to value and remove the node
template <typename T>
bool DoubleLinkedList<T>::popBack(T & value) {
   if (isEmpty()) {
      return false;
   } else if (frontPtr == backPtr) {  // only one node
      value = backPtr->data;
      delete backPtr;          // remove node
      frontPtr = backPtr = 0;  // empty
   } else {
      value = backPtr->data;
      DoubleLinkedNode<T> * tempPtr = backPtr;
      backPtr = backPtr->prevPtr;  // 2nd last node
      backPtr->nextPtr = 0;
      delete tempPtr;
   }
   return true;
}
 
// Overload the stream insertion operator to print the list
template <typename T>
std::ostream & operator<< (std::ostream & os, const DoubleLinkedList<T> & lst) {
   os << '{';
   if (!lst.isEmpty()) {
      DoubleLinkedNode<T> * currentPtr = lst.frontPtr;
      while (currentPtr) {
         os << currentPtr->getData();
         if (currentPtr != lst.backPtr) os << ',';
         currentPtr = currentPtr->getNextPtr();
      }
   }
   os << '}';
}
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/* Test Driver for List class (TestList.cpp) */
#include <iostream>
#include "DoubleLinkedList.h"
using namespace std;
 
int main() {
 
   DoubleLinkedList<int> lst1;
   cout << lst1 << endl;
   lst1.pushFront(8);
   lst1.pushBack(88);
   lst1.pushFront(9);
   lst1.pushBack(99);
   cout << lst1 << endl;
 
   int result;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popFront(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popFront(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
   lst1.popBack(result)
      ? cout << "value is " << result << ", list is " << lst1 << endl
      : cout << "empty list" << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#ifndef STACK_H
#define STACK_H
 
#include <iostream>
 
// Forward Reference
template <typename T>
class Stack;
template <typename T>
std::ostream & operator<<(std::ostream & os, const Stack<T> & s);
 
template <typename T>
class Stack {
private:
   T * data;      // Array
   int tos;       // Top of stack, start at index -1
   int capacity;  // capacity of the array
   int increment; // each subsequent increment size
public:
   explicit Stack(int capacity = 10, int increment = 10);
   ~Stack();  // Destructor
   void push(const T & value);
   bool pop(T & value);
   bool isEmpty() const;
 
friend std::ostream & operator<< <>(std::ostream & os, const Stack<T> & s);
      // Overload the stream insertion operator to print the list
};
 
// Constructor - Create an empty list without any node
template <typename T>
Stack<T>::Stack(int cap, int inc) : capacity(cap), increment(inc) {
   data = new T[capacity];
   tos = -1;
}
 
// Destructor - Remove all the dynamically allocated nodes
template <typename T>
Stack<T>::~Stack() {
   delete[] data;  // remove the dynamically allocate storage
   // std::cout << "Destructor completed..." << std::endl;
}
 
// Is list empty? Check if frontPtr is null
template <typename T>
bool Stack<T>::isEmpty() const { return tos < 0; }
 
// Push the data on top of the stack
template <typename T>
void Stack<T>::push(const T & value) {
   if (tos < capacity - 1) {
      // Have space, simply add in the value
      data[++tos] = value;
   } else {
      // No more space. Allocate a bigger array
      T * newDataPtr = new T[capacity + increment];
      for (int i = 0; i <= tos; ++i) {
         newDataPtr[i] = data[i];   // copy over
      }
      delete[] data;
      data = newDataPtr;
   }
}
 
// Pop the data from the TOS
template <typename T>
bool Stack<T>::pop(T & value) {
   if (isEmpty()) {
      return false;
   } else {
      value = data[tos--];
   }
   return true;
}
 
// Overload the stream insertion operator to print the list
template <typename T>
std::ostream & operator<< (std::ostream & os, const Stack<T> & stack) {
   os << '{';
   for (int i = stack.tos; i >= 0; --i) {
      os << stack.data[i];
      if (i > 0) os << ',';
   }
   os << '}';
}
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/* Test Driver for Stack class (TestStack.cpp) */
#include <iostream>
#include "Stack.h"
using namespace std;
 
int main() {
 
   Stack<int> s1;
   cout << s1 << endl;
   s1.push(8);
   s1.push(88);
   cout << s1 << endl;
 
   int result;
   s1.pop(result)
      ? cout << "value is " << result << ", stack is " << s1 << endl
      : cout << "empty stack" << endl;
 
   s1.push(9);
   s1.push(99);
   cout << s1 << endl;
 
   s1.pop(result)
      ? cout << "value is " << result << ", stack is " << s1 << endl
      : cout << "empty stack" << endl;
 
   s1.pop(result)
      ? cout << "value is " << result << ", stack is " << s1 << endl
      : cout << "empty stack" << endl;
   s1.pop(result)
      ? cout << "value is " << result << ", stack is " << s1 << endl
      : cout << "empty stack" << endl;
   s1.pop(result)
      ? cout << "value is " << result << ", stack is " << s1 << endl
      : cout << "empty stack" << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* Node template class for binary tree (Node.h) */
#ifndef NODE_H
#define NODE_H
 
template <typename T> class BinaryTree; // Forward reference
 
template <typename T>
class Node {
private:
   T data;
   Node * rightPtr;
   Node * leftPtr;
public:
   Node (T d) : data(d), rightPtr(0), leftPtr(0) { };
   T getData() const { return data; };
   Node * getRightPtr() const { return rightPtr; }
   Node * getLeftPtr() const  { return leftPtr;  }
 
friend class BinaryTree<T>;
   // Make BinaryTree class a friend to access private data
};
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

/* BinaryTree template class for binary tree (BinaryTree.h) */
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
 
#include <iostream>
#include <queue>
#include "Node.h"
 
// Forward Reference
template <typename T>
std::ostream & operator<<(std::ostream & os, const BinaryTree<T> & lst);
 
template <typename T>
class BinaryTree {
private:
   Node<T> * rootPtr;
 
   // private helper functions
   void insertNode(Node<T> * & ptr, const T & value);
   void preOrderSubTree(const Node<T> * ptr, std::ostream & os = std::cout) const;
   void inOrderSubTree(const Node<T> * ptr, std::ostream & os = std::cout) const;
   void postOrderSubTree(const Node<T> * ptr, std::ostream & os = std::cout) const;
   void removeSubTree(Node<T> * & ptr);
public:
   BinaryTree();   // Constructor
   ~BinaryTree();  // Destructor
   void insert(const T & value);
   bool isEmpty() const;
   void preOrderTraversal(std::ostream & os = std::cout) const;
   void inOrderTraversal(std::ostream & os = std::cout) const;
   void postOrderTraversal(std::ostream & os = std::cout) const;
   void breadthFirstTraversal(std::ostream & os = std::cout) const;
 
friend std::ostream & operator<< <>(std::ostream & os, const BinaryTree<T> & lst);
      // Overload the stream insertion operator to print the list
};
 
// Constructor - Create an empty list with no node
template <typename T>
BinaryTree<T>::BinaryTree() : rootPtr(0) { }
 
// Destructor - Remove all the dynamically allocated nodes
template <typename T>
BinaryTree<T>::~BinaryTree() {
   removeSubTree(rootPtr);
   // std::cout << "Destructor completed..." << std::endl;
}
 
template <typename T>
void BinaryTree<T>::removeSubTree(Node<T> * & ptr) {
   if (ptr) {
      removeSubTree(ptr->leftPtr);   // remove left subtree
      removeSubTree(ptr->rightPtr);  // remove right subtree
      delete ptr;
   }
}
 
// Is list empty? Check if rootPtr is null
template <typename T>
bool BinaryTree<T>::isEmpty() const { return rootPtr == 0; }
 
// Push the data in front by dynamically allocate a new node
template <typename T>
void BinaryTree<T>::insert(const T & value) {
   insertNode(rootPtr, value);
}
 
// Need to pass the pointer by reference so as to modify the caller's copy
template <typename T>
void BinaryTree<T>::insertNode(Node<T> * & ptr, const T & value) {
   if (ptr == 0) {
      ptr = new Node<T>(value);
   } else {
      if (value < ptr->data)
         insertNode(ptr->leftPtr, value);
      else if (value > ptr->data)
         insertNode(ptr->rightPtr, value);
      else
         std::cout << "duplicate value" << std::endl;
   }
}
 
template <typename T>
void BinaryTree<T>::preOrderTraversal(std::ostream & os) const {
   os << "{ ";
   preOrderSubTree(rootPtr);
   os << '}' << std::endl;
}
 
template <typename T>
void BinaryTree<T>::preOrderSubTree(const Node<T> * ptr, std::ostream & os) const {
   if (ptr) {
      os << ptr->data << ' ';
      preOrderSubTree(ptr->leftPtr);
      preOrderSubTree(ptr->rightPtr);
   }
}
 
template <typename T>
void BinaryTree<T>::inOrderTraversal(std::ostream & os) const {
   os << "{ ";
   inOrderSubTree(rootPtr);
   os << '}' << std::endl;
}
 
template <typename T>
void BinaryTree<T>::inOrderSubTree(const Node<T> * ptr, std::ostream & os) const {
   if (ptr) {
      inOrderSubTree(ptr->leftPtr);
      os << ptr->data << ' ';
      inOrderSubTree(ptr->rightPtr);
   }
}
 
template <typename T>
void BinaryTree<T>::postOrderTraversal(std::ostream & os) const {
   os << "{ ";
   postOrderSubTree(rootPtr);
   os << '}' << std::endl;
}
 
template <typename T>
void BinaryTree<T>::postOrderSubTree(const Node<T> * ptr, std::ostream & os) const {
   if (ptr) {
      postOrderSubTree(ptr->leftPtr);
      postOrderSubTree(ptr->rightPtr);
      os << ptr->data << ' ';
   }
}
 
// Breadth First Search (BFS)
template <typename T>
void BinaryTree<T>::breadthFirstTraversal(std::ostream & os) const {
   std::queue<Node<T> * > q;
   if (!isEmpty()) q.push(rootPtr);
 
   os << "{ ";
   Node<T> * currentPtr;
   while (currentPtr = q.front()) {
      std::cout << currentPtr->data << ' ';
      if (currentPtr->leftPtr) q.push(currentPtr->leftPtr);
      if (currentPtr->rightPtr) q.push(currentPtr->rightPtr);
      q.pop();  // remove this node
   }
   os << '}' << std::endl;
}
 
// Overload the stream insertion operator to print the list in in-order traversal
template <typename T>
std::ostream & operator<< (std::ostream & os, const BinaryTree<T> & lst) {
   lst.inOrderTraversal(os);
   return os;
}
 
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* Test Driver for BinaryTree class (TestBinaryTree.cpp) */
#include <iostream>
#include "BinaryTree.h"
using namespace std;
 
int main() {
   BinaryTree<int> t1;
   t1.insert(6);
   t1.insert(10);
   t1.insert(5);
   t1.insert(15);
   t1.insert(7);
   t1.insert(4);
   t1.insert(9);
 
   t1.preOrderTraversal();
   t1.inOrderTraversal();
   t1.postOrderTraversal();
   cout << t1;
   t1.breadthFirstTraversal();
}