C++ Programming Code Examples
C++ > Data Structures and Algorithm Analysis in C++ Code Examples
Header file for top-down splay tree
/* Header file for top-down splay tree */
#ifndef SPLAY_TREE_H_
#define SPLAY_TREE_H_
#include "dsexceptions.h"
#include <iostream.h> // For NULL
// SplayTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// Node and forward declaration because g++ does
// not understand nested classes.
template <class Comparable>
class SplayTree;
template <class Comparable>
class BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( ) : left( NULL ), right( NULL ) { }
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
friend class SplayTree<Comparable>;
};
template <class Comparable>
class SplayTree
{
public:
explicit SplayTree( const Comparable & notFound );
SplayTree( const SplayTree & rhs );
~SplayTree( );
const Comparable & findMin( );
const Comparable & findMax( );
const Comparable & find( const Comparable & x );
bool isEmpty( ) const;
void printTree( ) const;
void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x );
const SplayTree & operator=( const SplayTree & rhs );
private:
BinaryNode<Comparable> *root;
BinaryNode<Comparable> *nullNode;
const Comparable ITEM_NOT_FOUND;
const Comparable & elementAt( BinaryNode<Comparable> *t ) const;
void reclaimMemory( BinaryNode<Comparable> * t ) const;
void printTree( BinaryNode<Comparable> *t ) const;
BinaryNode<Comparable> * clone( BinaryNode<Comparable> *t ) const;
// Tree manipulations
void rotateWithLeftChild( BinaryNode<Comparable> * & k2 ) const;
void rotateWithRightChild( BinaryNode<Comparable> * & k1 ) const;
void splay( const Comparable & x, BinaryNode<Comparable> * & t ) const;
};
#include "SplayTree.cpp"
#endif
Return the smallest. Returns the smallest of a and b. If both are equivalent, a is returned. min() function is a library function of algorithm header, it is used to find the smallest value from given two values, it accepts two values and returns the smallest value and if both the values are the same it returns the first value. The versions for initializer lists (3) return the smallest of all the elements in the list. Returning the first of them if these are more than one. The function uses operator< (or comp, if provided) to compare the values.
The #ifndef directive of the C++ Programming Language helps in allowing the conditional compilation. The C++ Programming Language's preprocessor helps in determining only if the macro provided is not at all existed before including the specific subsequent code in the C++ compilation process. The #ifndef preprocessor only checks If the specific macro is not at all defined with the help of the #define directive. If the condition is TRUE then it will be helpful in executing the code otherwise the else code of the #ifndef will be compiled or executed only if present.
A friend function of a class is defined outside that class' scope but it has the right to access all private and protected members of the class. Even though the prototypes for friend functions appear in the class definition, friends are not member functions. A friend can be a function, function template, or member function, or a class or class template, in which case the entire class and all of its members are friends. If a function is defined as a friend function in C++ programming language, then the protected and private data of a class can be accessed using the function. By using the keyword friend compiler knows the given function is a friend function. For accessing the data, the declaration of a friend function should be done inside the body of a class starting with the keyword friend.
In the C++ Programming Language, the #define directive allows the definition of macros within your source code. These macro definitions allow constant values to be declared for use throughout your code. Macro definitions are not variables and cannot be changed by your program code like variables. You generally use this syntax when creating constants that represent numbers, strings or expressions. The syntax for creating a constant using #define in the C++ is: #define token value
The main purpose of C++ programming is to add object orientation to the C programming language and classes are the central feature of C++ that supports object-oriented programming and are often called user-defined types. A class is used to specify the form of an object and it combines data representation and methods for manipulating that data into one neat package. The data and functions within a class are called members of the class.
A C++ template is a powerful feature added to C++. It allows you to define the generic classes and generic functions and thus provides support for generic programming. Generic programming is a technique where generic types are used as parameters in algorithms so that they can work for a variety of data types. We can define a template for a function. For example, if we have an add() function, we can create versions of the add function for adding the int, float or double type values. Where Ttype: It is a placeholder name for a data type used by the function. It is used within the function definition. It is only a placeholder that the compiler will automatically replace this placeholder with the actual data type. class: A class keyword is used to specify a generic type in a template declaration.
Templates are powerful features of C++ which allows us to write generic programs. Similar to function templates, we can use class templates to create a single class to work with different data types. Class templates come in handy as they can make our code shorter and more manageable. A class template starts with the keyword template followed by template parameter(s) inside <> which is followed by the class declaration. T is the template argument which is a placeholder for the data type used, and class is a keyword. Inside the class body, a member variable var and a member function functionName() are both of type T.
A destructor is a special member function that works just opposite to constructor, unlike constructors that are used for initializing an object, destructors destroy (or delete) the object. Destructors in C++ are members functions in a class that delete an object. They are called when the class object goes out of scope such as when the function ends, the program ends, a delete variable is called etc. Destructors are different from normal member functions as they don't take any argument and don't return anything. Also, destructors have the same name as their class and their name is preceded by a tilde(~).
In C++, constructor is a special method which is invoked automatically at the time of object creation. It is used to initialize the data members of new object generally. The constructor in C++ has the same name as class or structure. Constructors are special class functions which performs initialization of every object. The Compiler calls the Constructor whenever an object is created. Constructors initialize values to object members after storage is allocated to the object. Whereas, Destructor on the other hand is used to destroy the class object. • Default Constructor: A constructor which has no argument is known as default constructor. It is invoked at the time of creating object.
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
(OOP) is a "Programming Paradigm" that is based on the concept of objects. An object is a "Data Structure" that contains data (fields) and functions. And Objects are instances of
Notice that we have not returned any values from the 'cyclicSwap()' function. When these variables are swapped in "Cyclic Order" in the 'cyclicSwap()' function, variables a, b and c in
