C++ Data Structures: Implementation and Testing
Binary Tree Example
#include "example_trees.h"
#include <iostream>
using namespace std;
using namespace main_savitch_11;
int main() {
sips = example();
cout << s << endl;
// searching example
int target = 10;
cout << "search for " << target << " : " << s->Count(target) << endl;
int targets[] = {23, 45, 6, 17, 12, 10, 16, 19, 22, 18, 20, 25};
int targets_size = 12;
for (int i = 0; i < targets_size; ++i) {
cout << "search for " << targets[i] << " : " << s->Count(targets[i]) << endl;
}
int not_there[] = {17, 89, 11, 13, 14, 15, 21, 23, 24, 26};
int not_there_size = 10;
for (int i = 0; i < not_there_size; ++i) {
cout << "search for " << not_there[i] << " : " << s->Count(not_there[i]) << endl;
}
// insert example
set *s2 = new set();
for (int i = 0; i < 5; i++) {
s2->insert(rand());
}
cout << *s2 << endl;
}
#include "example_trees.h"
#include <iostream>
using namespace std;
using namespace main_savitch_11;
sipsingle(int val, sip *lft, sip *right) {
sip *s = new sip();
s->append_data(val);
if (lft != nullptr)
s->append_subset(lft);
if (right != nullptr)
s->append_subset(right);
return s;
}
sip *sipdubble(int val1, int val2, sip *c1, sip *c2, sip *c3) {
sip *s = new sip();
s->append_data(val1);
s->append_data(val2);
if (c1 != nullptr)
s->append_subset(c1);
if (c2 != nullptr)
s->append_subset(c2);
if (c3 != nullptr)
s->append_subset(c3);
return s;
}
sip *example() {
sip *s1 = sipdubble(23, 0, nullptr, nullptr, nullptr);
// cout << *s1 << endl;
sip *s2 = sipsingle(5, nullptr, nullptr);
sip *s3 = sipsingle(10, nullptr, nullptr);
sip *s4 = sipsingle(16, nullptr, nullptr);
sip *s5 = sipsingle(18, nullptr, nullptr);
sip *s6 = sipsingle(20, nullptr, nullptr);
sip *s7 = sipsingle(25, nullptr, nullptr);
sip *s8 = sipsingle(4, s1, s2);
sip *s9 = sipsingle(12, s3, s4);
sip *s10 = sipdubble(19, 22, s5, s6, s7);
sip *s11 = sipdubble(6, 17, s8, s9, s10);
return s11;
}
Table Class Test
#include <iostream> //provides std::cout and std::cin
#include <cctype> //provides toupper
#include <cstdlib> //provides EXIT_SUCCESS & size_t
#include "table1.h" //provides dtable class
using namespace std;
using namespace main_savitch_12a;
//struct definition for test_record_type which has a key & a double.
struct test_record_type
{
int key;
double data;
};
int main()
{
table<test_record_type> test; // a table that we'll perform tests on
char choice; // a command character entered by the user
bool found; // value returned by find function
test_record_type result; // value returned by find function
cout << "I have initialized an empty table. Each record in the" << endl;
cout << "table has an integer key and a real number as data." << endl;
do
{
print_menu();
choice = toupper(get_user_command());
switch (choice)
{
case 'S': cout << "The table size is " << test.size() << endl;
break;
case 'I': test.insert(get_record());
cout << "The record has been inserted." << endl;
break;
case 'R': test.remove(get_key());
cout << "Remove has been called with that key." << endl;
break;
case '?': if (test.is_present(get_key()))
cout << "That key is present." << endl;
else
cout << "That key is not present." << endl;
break;
case 'F': if (test.find(get_key(), found, result))
{
cout << "The key's data is: " << result.data << endl;
}
else
cout << "That key is not present." << endl;
break;
case 'Q': cout << "Ridicule is the best test of truth." << endl;
break;
default: cout << choice << " is invalid. Sorry." << endl;
}
}
while ((choice != 'Q'));
return EXIT_SUCCESS;
}
void print_menu()
// library facilities used: iostream.h
{
cout << endl; // print blank line before the
cout << "The following choices are available: " << endl;
cout << " S Print the result from the size( ) function" << endl;
cout << " I Insert a new record with the insert(...) function" << endl;
cout << " R Remove a record with the remove(...) function" << endl;
cout << " ? Check whether a particular key is present" << endl;
cout << " F Find the data associated with a specified key" << endl;
cout << " Q Quit this test program" << endl;
}
char get_user_command()
// library facilities used: iostream.h
{
char command;
cout << "Enter choice: ";
cin >> command; // input of characters skips blanks & newline character
return command;
}
test_record_type get_record()
// library facilities used: iostream.h
{
test_record_type result;
cout << "Please enter a real number for a record's data: ";
cin >> result.data;
cout << result.data << " has been read." << endl;
result.key = get_key();
return result;
}
int get_key()
// library facilities used: iostream.h
{
int key;
do
{
cout << "Please enter a non-negative integer for a key: ";
cin >> key;
}
while (key < 0);
cout << key << " has been read." << endl;
return key;
}
Heap Class Test
#include "heap.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
srand(time(nullptr));
heap<int> hi;
while (!hi.is_full()) {
int x = rand() % 100;
cout << "insert " << x << endl;
hi.insert(x);
}
hi.check_heap();
cout << "time: " << time(nullptr) << endl;
heap<int> hp;
hp.insert(1);
hp.insert(2);
hp.insert(3);
hp.insert(4);
hp.insert(5);
hp.check_heap();
int x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
cout << "empty? " << hp.is_empty() << endl;
}
Selection Sort Test
#include <algorithm> //provides std::swap
#include <cstdlib> //provides EXIT_SUCCESS, size_t
#include <iostream> //provides std::cout & std::cin
using namespace std;
// prototype of the function used in this test program:
void selectionsort(int data[], size_t n);
// precondition: data is an array with at least n components.
// postcondition: the elements are rearranged so that
// data[0] <= data[1] <= ... <= data[n-1].
int main()
{
const char blank = ' ';
const size_t array_size = 10; // # of elements in the array to be sorted
int data[array_size]; // array of integers to be sorted
int user_input; // # typed by the user
size_t number_of_elements; // how much of the array is used
size_t i; // array index
// provide some instructions.
cout << "Please type up to " << array_size << " positive integers." << endl;
cout << "Indicate the list's end with a zero." << endl;
// read input numbers.
number_of_elements = 0;
cin >> user_input;
while ((user_input != 0) && (number_of_elements < array_size))
{
data[number_of_elements] = user_input;
number_of_elements++;
cin >> user_input;
}
// sort the numbers, & print the result with 2 blanks after each #.
selectionsort(data, number_of_elements);
cout << "In sorted order, your numbers are: " << endl;
for (i = 0; i < number_of_elements; i++)
cout << data[i] << blank << " ";
cout << endl;
return EXIT_SUCCESS;
}
void selectionsort(int data[], size_t n)
// library facilities used: algorithm, cstdlib
{
size_t i, j, index_of_largest;
int largest;
if (n == 0)
return; // no work for an empty array.
for (i = n - 1; i > 0; --i)
{
largest = data[0];
index_of_largest = 0;
for (j = 1; j <= i; j++)
{
if (data[j] > largest)
{
largest = data[j];
index_of_largest = j;
}
}
swap(data[i], data[index_of_largest]);
}
}
Priority Queue Implementation
#ifndef priority_queue_simple_h
#define priority_queue_simple_h
/**
* this class implements a priority queue using a very simple strategy:
* store the values in an array.
* add new values at the end.
* when asked to remove a value, search for the largest (linear search)
*
*/
template<class T>
class priority_queue_simple {
public:
static const int capacity = 30;
priority_queue_simple() {
size = 0;
}
bool is_empty() const {
return size == 0;
}
bool is_full() const {
return size == capacity;
}
/**
* remove the largest value from this priority queue & return it.
*
* precondition: priority queue is not empty.
*/
T remove();
/**
* inserts the 'value' into the priority queue.
*
* precondition: priority queue is not full
*/
void insert(const T& value);
private:
T data[capacity];
int size;
};
#include "priority_queue_simple.template"
#endif // priority_queue_simple_h
Selection Sort Implementation
// FILE: select.cxx
// An interactive test program for the selectionsort function
#include <algorithm> // Provides swap
#include <cstdlib> // Provides EXIT_SUCCESS, size_t
#include <iostream> // Provides cout and cin
using namespace std;
// PROTOTYPE of the function used in this test program:
void selectionsort(int data[], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements are rearranged so that
// data[0] <= data[1] <= ... <= data[n-1].
int main()
{
const char BLANK = ' ';
const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted
int data[ARRAY_SIZE]; // Array of integers to be sorted
int user_input; // Number typed by the user
size_t number_of_elements; // How much of the array is used
size_t i; // Array index
// Provide some instructions.
cout << "Please type up to " << ARRAY_SIZE << " positive integers. " << endl;
cout << "Indicate the list's end with a zero." << endl;
// Read the input numbers.
number_of_elements = 0;
cin >> user_input;
while ((user_input != 0) && (number_of_elements < ARRAY_SIZE))
{
data[number_of_elements] = user_input;
number_of_elements++;
cin >> user_input;
}
// Sort the numbers, and print the result with two blanks after each number.
selectionsort(data, number_of_elements);
cout << "In sorted order, your numbers are: " << endl;
for (i = 0; i < number_of_elements; i++)
cout << data[i] << BLANK << " ";
cout << endl;
return EXIT_SUCCESS;
}
void selectionsort(int data[], size_t n)
// Library facilities used: algorithm, cstdlib
{
size_t i, j, index_of_largest;
int largest;
if (n == 0)
return; // No work for an empty array.
for (i = n - 1; i > 0; --i)
{
largest = data[0];
index_of_largest = 0;
for (j = 1; j <= i; j++)
{
if (data[j] > largest)
{
largest = data[j];
index_of_largest = j;
}
}
swap(data[i], data[index_of_largest]);
}
}