Programming Solution

ADT implementation

noreply@blogger.com (geteamon) — Mon, 28 Dec 2009 01:16:00 +0200

The specification of an ADT (Abstract Data Type) defines abstract data values and abstract operations for the user. Of course, the ADT must implemented in program code.

To implement an ADT, the programmer must do two things:

choose an concrete data representation of the abstract data, using data type that already exist

implement each of the allowabel operations in terms of program instructions

Our choice may be based on:

time efficiency (the speed at which the algorithms execute)

space efficiency (the economical use of memory space)

simplicity and readability of the algorithms

Categories of ADT operations

The basic operations that are performed on an abstract data type fall into different categories. Such as:

Constructor: An operation that creates a new instance (variable) of an ADT. For example: creating a new instance of a list

Transformer: An operation that builds a new value of the ADT, given one or more previous values of the type. For example: inserting an item in a list or deleting an item from a list.

Observer: An operation that allows us to observe the state of an instance of an ADT without changing it. For example: checking if a list is empty or searching a list for a target.

Iterator: This is less common operation, it allows us to process all components in an instance of an ADT. For example: printing the items of a list.

Mutators (setters): Changing the value of an attribute

Accessors (getters): getting the value of an attribute

Reference: wikipedia, acm, answers

Abstract Data Types

noreply@blogger.com (geteamon) — Sat, 19 Sep 2009 02:05:00 +0300

Data abstraction is important because:

It allows uns to create data types not otherwise available in a programming language

It allows us to produce off-the-shelf-software, pieces of software that can be used over and over again in different programs by any programmer

The primary tool for practicing data abstraction is the abstract data type(ADT), a new data type that is not built into the programming language, concentrating only on its logical properties and deferring the details of its implementation.

An abstract data type has both a specification (the what) and an implementation (the how)

Properties of abstract data types

Attributes

Java: fields

C++: data members or member variables

Oprations

Java: methods

C++: member functions

Interaction with (usage of) an abstract data type is made through its interface or public interface

Public attributes

Public operations

TIP: public interface should be built around public operations.

Example of informal specification

TYPE
    IntList
DOMAIN
    Each IntList value is a collection of up to 100 separate integer numbers
OPERATIONS
    Insert an item into the list
    Delete an item from the list
    Return the current length of the list
    Print the list

Notice the complete absense of implementation details

Reference: wikipedia, google books, thefreedictionary

Abstraction

noreply@blogger.com (geteamon) — Fri, 18 Sep 2009 00:02:00 +0300

To cope with complexity, the human mind engages in abstraction, the act of separating the essential qualities of an idea or object from the details of how it works or is composed. With abstraction, we focus on the what, not the how. Abstraction can be performed from different viewpoints.

Examples:

Words of a spoken language

Metaphysical abstractions

Objects in a classroom

Mathematical abstractions

Abstraction in programming

Fig: Abstraction in real life

Abstraction in Programming

Data types: An int-type represents an integer, a float-type represents a floating point number

Functions: absoluteValue

double absoluteValue(double d)
{
    if(d<0)
    {
        return -d;
    }
    else
    {
        return d;
    }
}

#include<cmath>
double absoluteValue(double d)
{
    return abs(d);
}

Both of the given example functions do the same thing. We don't need to know how they are doing. So we are focusing on what, not how.

Types of Abstraction

There are two important abstraction techniques:

control abstraction

data abstraction

Control abstraction is the separation of the logical properties of an action from its implementation.

Data abstraction is the separation of a data type's logical properties from its implementation.

Reference: wikipedia, artima, microsoft

Array vs vector

noreply@blogger.com (geteamon) — Sun, 6 Sep 2009 14:05:00 +0300

Vectors are intended to replace the C-style arrays, i.e. the static arrays:

Safe to pass as a parameter or assign to
Size increases when necessary means no memory management problem
Comparisons (==, < etc.) works "as it should"

vector has its own dangers, though:

No forced boundary limit checks in indexing
Easy to write code that may be inefficient in parameter passing
Passing arrays to libraries that use C arrays is difficult

Comparisons between C arrays and vector:

operation	array	vector
Creation	int t[10]	vector<int> t(10); or vector<int> t; (empty)
Assignment	in a loop	t1 = t2
Indexing	t[i]	t[i] or t.at(i)
Inserting to the end	not possible	t.push_back(item)
Combining	not possible	t1.insert(t1.end(), t2.begin(), t2.end())
Size	programmer must know	t.size()
Emptying	not possible	t.clear()
Comparison	in a loop	t1 == t2 (likewise <>
Insertion to the middle	not possible	t.insert(iterator, item)
Searching	in a loop	find(t.begin(), t.end(), item)
Exchange of values	in a loop	t1.swap(t2)

vector< type > var;An empty vector
vector< type > var(vector< type >); Initialization with another vector
vector< type > var(int);A vector of the size int with elements of the type
vector< type > var(int, element);A vector with int elements initialized to element

Operations:
vector[int] // Indexing the vector at int.
vector1 = vector2 // Assignment
vector1 == vector2 // Comparison
vector1 != vector2vector1 < vector2vector1 <= vector2vector1 > vector2 vector1 >= vector2

Functions:
swap(vector1, vector2) // swaps the contents

Own functions:

type at( int )	Indexing the vector at int
type front()	The first element
type back()	Last element
vector<type>::size_type size()	number of elements
bool empty()	true if vector is empty
void push_back(element)	Element is added to the end of vector
void pop_back()	Last element is removed, size gets smaller by one
void clear()	Empty the vector completely
iterator being()	An iterator to the beginning
iterator end()	An iterator to the end

#include <algorithm>

Functions:

void sort( array, array+size );
void sort( vector.begin(), vector.end() );
// Sorting the vector or array into an ascending order
bool compare(const item&, const item&);
void sort( array, array+size, compare );
void sort( vector.begin(), vector.end(), compare );
// Sort can be given a comparison function as a third parameter
// Function returns true if the first parameter is smaller than the second.
void operations(const item&);
void for_each( array, array+size, operations );
void for_each( vector.begin(), vector.end(), operation );
// Calls the function operation for each element in the array or vector at a time.

Reference: cplusplus, velocityreviews, devx

Vector

noreply@blogger.com (geteamon) — Sun, 6 Sep 2009 00:15:00 +0300

The C++ standard library offers the programmer plenty of generic data structures and algorithms that are ready for use. The programmer can concentrate on the essential and does not need to invent the wheel all over again. Just like string is dynamic and easier to use than static character strings, there is a dynamic data structure corresponding to static arrays. That is vector. vector is a part of the C++ standard library. The problems with arrays in C++:

They are static, i.e. the amount of elements cannot be changed without compiling the program again
An array cannot be copied into another away with the = operator
An array cannot be initialized with an another array
There is no way of knowing the current amount of actual elements without keeping constant score of the situation

vector makes all of the above possible and has a lot of other useful features. In practice, vector is generic, dynamic array.

In order to be able to use vector the library vector must be taken into use.

Any type of data can be put into a vector. All elements must be of the same type (just like with static arrays). vector is defined with <> notation:

vector< element_type > variable_name;

for example:

vector< int > numbers;
vector< string > names;

The vector is empty at initialization if no initial values are given:

vector< double > temperatures1( 5, 20.1 );
vector< double > temperatures2( 3 );
vector< double > temperatures3( temperatures2 );

now there are five elements in the vector temperatures1 with the value 20.1, all three elements in the vector temperatures2 have been initialized to 0.0 and the temperatures3 has the same contents as temperatures2.

Just like string, vector has its own functions.

vector <int> numbers(2,3);
//The elements in numbers are (3 3)
numbers.clear();
//numbers now empty
numbers.push_back(4);
numbers.push_back(10);
//Now the elements are (4 10)
numbers.push_back( numbers[1] );
//(4 10 10)
numbers.push_back( numbers.at( 0 ) );
//(4 10 10 4)
numbers.pop_back();
//(4 10 10)

// printing the contents
if( !numbers.empty() )
{
    unsigned int i;
    for( i = 0; i < numbers.size(); ++i )
    {
        cout << "numbers are: " << numbers[ i ] << " ";
    }
    cout << endl;
}

A vector can be assigned another vector of the same type with the = operator. Two vectors of the same type can be compared with ==, !=, <, >, <= and >= operators.

vector can be passed both as a value and a reference parameter like any ordinary variable:

vector<type> valueparam
vector<type>& referenceparam

In practice vector should always be passed as a reference parameter due to efficiency issues.

Reference: cplusplus, codesource, cppreference

Using several code files

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 22:10:00 +0300

Sometimes it is very handy to use several code files for a particular program. For example, if the program is very big and difficult to handle then its necessary to split the whole program into several files and combine together to make the program work properly. Sometimes function can be moved into a separate file. Let's take an example on how to move the functions into a separate file from the main function.

In the file plus.hh the function is declared:

#ifndef PLUS_HH
#define PLUS_HH

int plus( int a, int b );

#endif // PLUS_HH

In the file plus.cc the function is defined:

int plus( int a, int b )
{
return a + b;
}

In the file main.cc the main function is defined:

#include <iostream>
#include <cstdlib>
#include "plus.hh"

int main( void )
{
cout << "3+4 = " << plus( 3, 4 ) << endl;
return EXIT_SUCCESS;
}

The files work together in that sense that the .hh files (header files) have the declarations of those functions the .cc files (source files) define. The actual code, e.g. the function bodies, is in the .cc files. The .hh files must be added to the program with the #include directive if the functions need to be used in that file.

The command <file> is used when the included file is in some of the systems default directories. The compiler automatically also links these files. "file.hh" means that the header file is in the same directory as the source file. The function definitions need to be included also into the compilation stage to get an executable program. This is done by linking the files together. The compiler also links:

> g++ o plus plus.cc main.cc
>./plus
3+4 = 7

If the different stages of compiling and linking ned to be separated, the source files (.cc) can first be compiled into object files (.o) which then are linked into an executable program. For example:

>g++ c plus.cc
>g++ c main.cc
>g++ o plus plus.o main.o
>./plus
3+4 = 7

It makes sense to separate the compiling and linking stages when compiling large programs. It is easy to locate which stage the errors are coming from.

Some important matters:

Always include only header files
Write the actual code into the source files
Since include adds the file as a part of the compiled file, it is possible that some file is included more than once. Overlapping definitions can prevent compilation
The directives #ifndef, #define and #endif tell the preprocessor to add the file only once into the compiled file no matter how many times it has been included
The readability of a small program can be increased by moving the main to the beginning of the file and adding the definitions of functions after that. The functions must be declared before the main

Reference: fredosaurus, gamedev, learncpp

typedef

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 13:15:00 +0300

Sometimes there is a need to have types that cannot operate together in the program. For instance, money and weight should not be added even though both can be saved into variables of the type double. In these cases the situation can be made clearer by giving an existing type a new name with the typedef definition. For example:

typedef doube Currency;

typedef does not create a new type. For instance the types double and Currency would be interchangeable.

Type definitions make the code easier to read. They can also be used to writing more portable code. The type int is on some machines only 16 bits long, for instance. If the program when moved to this machine needed to operate with large sums, only the typedefinition needs to be changed. All the gazillion points in the code using the alias would remain intact.

Reference: cprogramming, wikipedia, mmbase

switch statement

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 12:45:00 +0300

The switch statement can be used to implement a multi-alternative selection statement when:

The tested value can be interpreted as an integer (int, char or enum)
The alternatives the value is tested are constants that can be interpreted as integers

Note: The switch statement is not as general as the if statement. However, switch is more efficient in some situations.

The general form of the switch statement is:

switch ( tested_expression )
{
    case alternative1:
        statementlist1;
        break;
    .
    .
    .
    case alternativeN:
        statementlistN;
        break;
    default:
        statementlist def;
        break;
}

When the switch statement is executed, the tested expression is evaluated. It is compared to the alternatives one by one. If one of the alternatives matches the tested expression the execution begins in the corresponding statementlist i. The execution continues through the statementlist i until one of the following is reached:

A break statement
A return statement
The end of the switch statement

If the tested expression doesn't match any of the alternatives the statementlist def is executed.

The default clause can be omitted. If the value of the tested expression is not in the alternatives execution "falls through" the switch.

If one of the statementlist i's missing a break the execution continues from the next tested expression, otherwise continues from the statement following the switch.

This can be used in situations where several alternatives have same functionality:

switch( answer )
{
    case 'n':
    case 'N':
        //the actions performed when
        //the user answers n or N
        break;
    ...
}

The break can also be omitted if the entire statement (or actually the function) is exited with return:

switch( month )
{
    case 1:
        return "January";
    case 2:
        return "February";
    etc...
    case 12:
        return "December";
    default:
        return "Error";
}

Reference: msdn, intap, awitness

Enumeration

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 01:33:00 +0300

An enumeration is a datatype with all the valid values defined by the programmer. In C++ an enumeration is declared.

enum TypeName { List_of_values };

that defines a new data type named TypeName whose values are the identifiers in the List of values. Each identifier is associated with an integer constant, i.e. the C++ compiler automatically preforms a identifier-to-integer mapping associating the integer 0 with the first identifier the integer 1 with the second etc.

C++ also allows the programmer to specify explicitly the values given to the identifiers:

enum NumberBase { BINARY = 2, OCTAL = 8, DECIMAL = 10, HEX = 16, HEXADECIMAL = 16 };

The integer associated with an identifier is, by default, one more than the integer associated with the preceding identifier. The integers can be declared:

enum Color { RED = 1, BLUE, GREEN, YELLOW, VIOLET };

Two ro more identifiers can have the same integer value associated with them. The enumerators (the identifiers in the enumeration) can be used wherever int or char values can be used. The enumerator is interpreted as the integer it is associated with. Enumeration and integer data can operate together as they were of the same type.

An integer value cannot be used instead of an enumerator in assignments or as a function parameter without explicit type conversion:

enum Season { SUMMER, FALL, WINTER, SPRING };
void print( Season quarter );

int figure = SUMMER; // figure <--- 0
// equivalent <--- SUMMER
Season equivalent = static_cast (figure);
// print( SUMMER )
print( static_cast (figure) );

Reference: ucalgary, anyexample, codeproject

Streams as parameters

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 01:05:00 +0300

The most important thing to remember when passing a stream to a function as a parameter: the formal parameter needs to be a reference parameter

It makes sense to require that since the function operates with the stream. The state of the stream changes and the change must be passed back to the actual parameter. As a rule the actual parameter needs to be of the same type as the formal parameter of the function, except when:

the type of the formal parameter is	the actual parameter can also be
sitram&	ifstream or istringstream
ostream&	ofstream or ostringstream

In practice that makes writing more general functions possible: the same function can operate with different types of streams.

A small example function:

int readNumber( istrea& stream )
{
    int number;
    stream >> number;
    if( !stream )
    {
        return ERROR;
    }
    else
    {
        return number;
    }
}

Now the same function can be used for reading input from the keyboard:

int number;
number = readNumber( cin );

of from a file:

ifstrea database( "input.txt" );
int number;
number = readNumber( database );

or from a string:

istrinigstream numberstring("12345 67890 101112");
int number;
number = readNumber( numberstring );

Reference: daniweb, bytes, cplusplus

Problems with streams

noreply@blogger.com (geteamon) — Sat, 5 Sep 2009 00:30:00 +0300

The following problem situations can occur when using streams:

An attempt to write data into a outputstream fails (e.g. the disk is full)
An attempt to read data from an inputstream even though everything has already been read (e.g. the read operation is at the end of file)
Data of the wrong type is attempted to read from an inputstream (e.g. an integer is expected but the user types characters)

Noticing the problematic situations is easy with the following details:

All previously introduced stream operations evaluate the stream the operations is directed to ( peek() and get() without parameters are exceptions)
A stream used as a condition evaluates true only if the operation was successful (initialization included)

The following useful examples can be done based on these:

Connecting an inputstream to a file and reading it a line at a time:

ifstream file( "products.dat" );
if( !file )
{
    cerr << "open failed!" << endl;
    return ERROR; // depends on the situation
}
string line;
while( getline( file, line ) )
{
    ...
    // here work with the read data
    ...
}

noticing input of the incorrect type:

cout << "give number: ";
int number;
while( !(cin >> number) )
{
    cerr << "Invalid input, try again!" << endl;
    cin.clear();
    cin.ignore( 1000, '\n' );
}

The cin's own function clear() has been used to deal with the error situation above. The stream malfunctions every time an error occurs when handling data with it. Not even legal operations work any longer. Sometimes the situation can be fixed with the clear() function. Execution can (sometimes) go on normally afterward. Some errors cannot be fixed with clear() (e.g. the end of file has been met)

How to see the difference between the end of stream error and some other error situation:

while( getline( stream, line ) )
{
    ...
}
if( !stream.eof() )
{
    // Read failed for some other reason than
    // the end of the stream
}

The stream's own function eof() returns true only if an attempt has been made to read from the stream after it has already ended. Also peeking the next character in the stream with the peek() function is sometimes an useful way to deduct whether the input has been read entirely or not.

Last, an example on how to read the following input stream:

tel.number1 name1
tel.number2 name2
...

with the code:

int number;
string name;

while( stream >> number && getline( stream, name ) )
{
    // do stuff with the name and number
}
if( !stream.eof() )
{
    // invalid line in input
}

Reference: daniweb, dreamincode, cplusplus

Operations with inputstreams

noreply@blogger.com (geteamon) — Wed, 2 Sep 2009 01:15:00 +0300

cin >> variable

Reads the next word from the stream, interprets it as the same type as the variable and saves the value into the variable. The variable can be of any basic type or string.

cin.get()

Reads and returns the next character in the stream. At the end of input EOF is returned.

cin.get( chr )

Reads the next character into the parameter that must be of the type char.

getline( cin, str )

Reads a line of input from the stream and saves it into a parameter of the type string.

getline( cin, str, chr )

Like above but reads only until meets the first character matching chr.

cin.ignore( how_many, chr )

Reads at most how_many characters from the stream or until meets the first chr. The read characters are "thrown away". How_many is of the type int and chr char.

cin.peek()

Returns the next character in the stream. The character is not read from the stream but the next read operations return it also Returns EOF at the end of input.

Reference: cplusplus, augustcouncil, elcel

Streams in C++

noreply@blogger.com (geteamon) — Tue, 1 Sep 2009 20:10:00 +0300

In C++ streams are represented with datatypes implemented in a number of libraries:

#inlcude <iostream>

istream	Inputstreams usually already associated with the keyboard (cin).
ostream	Outputstreams usually already associated with the monitor (cout or cerr)

#inlcude <fstream>

ifstream	Inputstreams the user must associated with a file on the computer disk
ofstream	Outputstreams the user must associated with a file on the computer disk

#inlcude <sstream>

istringstream	inputstreams the user can use to read from a string using the formatting facilities provided by streams
ostringstream	Outputstreams the user can use to write to a string using the formatting facilities provided by streams

A programmer does not need to worry about associating cout, cin and cerr. They can always be used straight after #include<iostream>. Using streams usually consist of three phases (cin, cerr and cout exceptions):

Initializing (connecting, associating)
Operating with the stream (read, write etc...)
Closing

Before handling data with the streams found in fstream and sstream libraries they must be initialized:

ifstream: A variable of the type ifstream is declared and the name of the file to be read is given:

ifstream stream_name( file_name );

ofstream: A variable of the type ofstream is declared and the name of the file to be written into is given:

ofstream stream_name( file_name );

istringstream: A variable of the type istringstream is declared and the string from which the input is read is given:

istringstream stream_name( s_name );

ostringstream: A varible of the type ostringstream is declared.

ostringstream stream_name;

The file_name is not of the type string. It is of an older character string type adopted from the C language. The programmer must give the name of the correct type:

string file_name;
cin >> file_name;
ifstream file( file_name.c_str() );

the c_str() function returns a character string of the c-style string type matching the original string-typed string. The file_name can also be a character string literal:

ifstream file( "inputs.txt" );

After being initialized, different operations can be done with the stream depending on its type and whether it is an input or an output stream (phase 2).

Working with streams can be confusing because of different alternative ways to do things:

operations: cout << "Hello!";
functions: getline( cin, cstring );
own function: cout.put( 'a' );

Operations that can be used with all kinds of outputstreams (e.g. cout):

cout << value << endl;

Prints the value into the stream: the value can be of any basic datatype or string.

cout.put( c );

Prints one character c(char) into the stream

There are no more essential printing operations. Almost everything can be done with << operator.

The stream must be closed when it is not needed any longer (phase 3). If it isn't properly closed it will needlessly keep on using the system's resources. There are two ways to close a stream:

If the stream is a local variable, C++ automatically closes it when the code block the stream was defined in is exited.
The stream can also be "manually" closed if needed with the stream's own function close():

ifstream database( "phonenumbers.dat" ); // using the stream
...
database.close();

The stream cannot be used after closing unless it is initialized again.

cin, cout and cerr

cin is used for reading from the keyboard and cout for printing on the screen. cerr has the same functionality as cout but it is meant for printing the error messages of the program. All other output is printed into cout.

Reference: cplusplus, exforsys, msdn

Streams

noreply@blogger.com (geteamon) — Tue, 1 Sep 2009 01:05:00 +0300

Most programs have some kind of I/O operations:

Reading data from a file on the computer's disk into the program
Saving the results of the program into a file on the disk for future use

There must be a way in a programming language to represent the real world disk files in such a way that a program can understand them. Usually a special data type that offers operations for reading and writing data is used. In C++ a data type called a stream is used for this purpose. In fact, besides file I/O, all input and output operations in C++ are done with streams.

The stream can be thought of as a line of characters following in a specific order in one direction without ever changing their order.

Only the first character of the stream can be read from the stream ( with the operation get() )
Writing can only be done after the last character in the stream( with the operation put() )

All other stream operations can be implemented with get and put. Not changing the order of characters in a stream is essential:

If the user types "abcdef" on a keyboard undoubtedly the program gets the same characters in the same order from the input stream(cin)
If the program writes characters into a stream connected to a file it is desirable that the characters are saved in the same order they were written into the stream

Streams are sequential in nature: data can only be managed in the same order it is in the stream. A stream is simply a sequence of bytes, that means, if a program is interested in the fifth character in the user's input, the preceding four characters must be read first. The same applies to a stream connected to a file: the file must be read from beginning to end. In reality, disk files can be read and written in an arbitrary order.

A stream is usually connected to a file, the screen or the keyboard. However, streams can also be used to connect two programs to each other. The interesting thing is that streams can always be handled in the same way, regardless of what they happen to be connected to.

Reference: cplusplus, msdn, exforsys

sizeof

noreply@blogger.com (geteamon) — Tue, 1 Sep 2009 00:30:00 +0300

The sizeof operator returns the number of bytes required to store a variable or a data (1 byte = 8 bits). The operator can be applied to any type of variable:

sizeof( variable name );
sizeof( data_type_name );

sizeof is a handy tool in finding out the amount of elements in an array:

const int SIZE = sizeof( array ) / sizeof( element_type );
or
const int SIZE = sizeof( array ) / sizeof( array[ 0 ] );

When the value of size is always equal to the actual amount of elements in the array even if the size of the array is changed between complications.

Note that sizeof does not produce a correct answer if they array is a formal parameter of a function.

Reference: cppreference, space, msdn

Searching data

noreply@blogger.com (geteamon) — Mon, 31 Aug 2009 19:58:00 +0300

Searching is the other problem that often occurs when handling data. The search can be done with some part of the actual data called a key. The easiest way to search is the linear search: successive elements are examined until either the item is found or the end of the list is reached. This is however an extremely inefficient way to search because in average about n/2 elements must be searched and in the worst case the element is not found but all n elements have been searched any way. A more efficient way to search is to first sort the elements. Searching is then faster because it is known that the item is missing when the correct place in the array is passed.

A rather simple but efficient searching algorithm is called binary search. The elements must be in ascending or descending order.

Algorithm: Binary search
    left <--- 0
    right <--- element_amount - 1
    WHILE left <= right
        middle <--- ( left + right )/2
        IF elements[ middle ].key == searched_key THEN
           item found at location middle
        ELSE IF elements[ middle ].key < searched_key THEN
           left <--- middle + 1
        ELSE
           right <--- middle - 1
    item not in the array

How does the binary search work with an integer key:
The search key is 4, there are 10 elements with the key 0-10 in the array

Fig: Binary search mechanism

Note that Binary Search can be used to work with other types than string by changing some points in the code to match the type. string must be changed to match the type of the searched data. The comparisons in the algorithms need to compare the wanted type.

Reference: allexperts, onesmartclick, informit

Sorting in C++

noreply@blogger.com (geteamon) — Mon, 31 Aug 2009 01:35:00 +0300

in C++ the library algorithm provides many easy to use algorithms. The sorting algorithm available is called sort. The contents of an array are sorted with

sort( array_name, array_name+array_size );

Sorting an integer array with sort:

#include <iostream>
#include <algorithm>

using namespace std;

void printArray( int array[], int size );

int main( void )
{
    const int SIZE = 8;
    int array[ SIZE ] = { 4, 6, 5, 7, 8, 1, 2, 3 };

    printArray( array, SIZE );
    sort( array, array+SIZE );
    printArray( array, SIZE );
}

void printArray( int array[], int size )
{
    int i = 0;

    while( i < size )
    {
        cout << array[ i ] << " ";
        ++i;
    }
    cout << endl;
}

The algorithm requires that the smaller than relation, <, has been defined for the elements of the array. To sort an array of structure, the < operator needs to be defined manually to the sorting function:

struct Student
{
    string name;
    int st_number;
};

bool compare( const Student& s1, const Student& s2 );
const int SIZE = 20;

int main()
{
    Student array[SIZE];
    // ...
    sort( array, array+SIZE, compare );
    // ...
}

bool compare( const Student& s1, const Student& s2 )
{
    if( s1.st_number < s2.st_number )
    {
    return true;
    }
    return false;
}

Reference: wikipedia, mathbits, daniweb

Sorting

noreply@blogger.com (geteamon) — Mon, 31 Aug 2009 00:59:00 +0300

Arranging the elements of any array (or some key fields in them) into an ascending or descending order is called sorting. Since sorting is a field of coputer science that has been studied a lot, there are dozens of sorting algorithms available. Different algorithms and their efficiency is usually covered on the course Utilization of Data Structures. Pseudocode for these algorithms can be found in the literature. Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms for instance. An efficient function for sorting data can often be found in one of the libraries.

Reference: wikipedia, sorting-algorithm, smith

Modifiers: unsigned, short and long

noreply@blogger.com (geteamon) — Sun, 30 Aug 2009 18:10:00 +0300

Integers (and in some cases characters) can be adjusted with the modifiers: unsigned, short and long. These can be used to either restrict or widen the used data type:

unsigned int	An integer value represented with as many bits as int. range: 0 and all positives
short int	An integer value represented with at most as many bits as int. range: negatives and positives
long int	An integer value represented with at least as many bits as int. range: negatives and positives
unsigned short int	like short int range: 0 and positives
unsigned long int	like long int range: 0 and positives

it depends on the processor used with how many bits are used to represent each type.

Reference: bilmuh, msdn, faqts

Structures

noreply@blogger.com (geteamon) — Sun, 30 Aug 2009 13:30:00 +0300

Arrays can be used to handle several elements of the same type together. However, sometimes it would be useful to handle several data elements of different types as a unit. In C++ structures are used for this purposes.

Structures (like arrays) are called structured data types, i.e. they have a structure defined by the programmer. A structure is declared:

struct type_name
{
    data_type member_name1;
    ...
    data_type member_nameN;
};

This defines a new type called type_name which can be used as any other type in C++. Note the semicolon (;) at the end. It is a mandatory while declaring a structure.

The individual members in the structure act like any other variable with the type data_type. The members can be accessed using . (dot) operator:

struct Student
{
    string name;
    int student_number;
};
...
Student st; // Declare a new variable of type Student
...
st.name = "Harry Potter";
cin >> st.student_number;

The members of a structure can also be initialized with literals of the same type as the members:

Student harry=
{
    "Harry Potter", 12345
};

The members are initialized in the order they appeared at the declaration. A new value can be assigned to a structure with =, but comparison ( == and != ) is not possible.

The members can be of any type, including arrays:

struct Grade
{
    string name,
    int problem_points[4];
};
...
Grade grade1;
...
grade1.problem_points[2] = 5;

On the other hand, the elements of any array can be of any type, too, including structures:

Student students[200];
...
students[0].name = "Ron Weasley";
cin >> students[54].student_number;

A struct is an aggregate of elements of (nearly) arbitrary types. Structures allow the programmer to define a new data type and group related components together. When structure is passed as a parameter of a function, by default it is passed by value but it can be passed by reference as well.

Reference: fredosaurus, wikipedia, msdn

Arrays as parameters

noreply@blogger.com (geteamon) — Sat, 29 Aug 2009 21:18:00 +0300

Even though call-by-value is the default parameter-passing mechanism in C++, arrays as parameters have some special features. Placing a pair of brackets ( [] ) after the name of a parameter indicates that the parameter is an array:

double arraySum( double array[ ], int array_size )
{
    double sum = 0.0;

    int i = 0;
    while( i < array_size )
    {
        sum = array[ i ] + sum;
    }
    return sum;
}

It is not necessary to specify the capacity of the array. There is no restriction on the capacity of the array passed to the function. It is necessary to use another parameter or a constant to pass the size of the array to the function.

Arrays are automatically passed by reference, i.e. specifying a parameter as an array makes it a reference parameter without the ampersand ( & ). If the function modifies the array, the corresponding argument will also be modified. This can be avoided by declaring the array as a constant reference parameter.

Let's take a larger example:

#include <cstdlib>
#include <iostream>

using namespace std;

const int MAX_NUMBER = 1000;
const int ERROR = -1;
const double END_NUMBER = -1.0;

int readNumbers( double numbers[ ] );
double calculateMean( const double numbers[ ], int how_many );

int main( void )
{
    double numbers[ MAX_NUMBERS ];
    int how_many_read = 0;

    how_many_read = readNumbers( numbers );

    if( how_many_read == ERROR )
    {
        return EXIT_FAILURE;
    }

    cout << "Mean value is: "
         << calculateMean( numbers, how_many_read )
         << endl;

    return EXIT_SUCCESS;
}

int readNumbers( double numbers[ ] )
{
    int how_many = 0;

    //we know that there is room for MAX_NUMBERS
    //amount of space in teh array
    while( how_many < MAX_NUMBERS )
    {
        cout << "Give "
             << how_many + 1
             << ". number: ";

        //The number is read from the input into
        //the array the change modifies the
        //coresponding argument
        cin >> numbers[ how_many ];

        if( numbers[ how_many ] == END_NUMBER )
        {
            return how_many;
        }
        ++how_many;
    }
    //if how_many got too large, and error has occured
    return ERROR;
}

double calculateMean( const double numbers[ ], int how_many )
{
    double sum = 0.0;
    int i = 0;

    if( how_many == 0 )
    {
        return sum;
    }

    //in this function the actual size of
    //the array doesn't matter. It is important
    //to know fo how many numbers the mean is
    //supposed to be calculated from
    while( i < how_many )
    {
        sum = sum + numbers[ i ];
        ++i;
    }
    return sum / how_many;
}

The other alternative woule have been:

int readNumbers( const double numbers[ ], int size )
{
    int how_many = 0;
    //now the size of the array is given as parameter
    while( how_many < size )
    {
        cout << "Give "
             << how_many + 1
             << ". number: ";
        //The number is read from the input
        //into the array the change modifies
        //the corresponding argument
        cin >> numbers[ how_many ];

        if( numbers[ how_many ] == END_NUMBER )
        {
            return how_many;
        }
        ++how_many;
    }
    //if how_many got too large, an error has occured
    return ERROR;
}

It would have been called in main:

how_many_read = readNumbers( numbers, MAX_NUMBERS );

The latter is recommended since the result can be used more widely.

Reference: cplusplus, macs, msdn

Functions: Parameter-passing mechanisms

noreply@blogger.com (geteamon) — Sat, 29 Aug 2009 14:30:00 +0300

The simplest parameter-passing mechanism in C++ occurs by default. It is called call-by-value. Value passed using this method are called value parameters. Any modification of a value parameter within the function body has no effect on the value of its corresponding argument:

void divideByTwo( int parameter )
{
    parameter = parameter / 2;
}

int main( void )
{
    int figure = 42;

    divideByTwo( figure );
    cout << figure << endl;

    return EXIT_SUCCESS;
}

prints 42 as a result.

It would be often useful to be able to change the value of the corresponding argument. For example, if the function needs to return more than one value, data could be returned by changing the value of the parameters. There is also call-by-reference mechanism in C++. These parameters are called reference parameters. Reference parameters are aliases of their corresponding arguments, i.e. any change to the value of a reference parameter within the function body changes the value of its corresponding argument. When using call-by-reference, the values are passed by adding an ampersand (&) between the type and the name of the parameter.

The example mentioned before:

void divideByTwo( int& parameter )
{
    parameter = parameter / 2;
}

int main( void )
{
    int figure = 42;

    divideByTwo( figure );
    cout << figure << endl;

    return EXIT_SUCCESS;
}

prints now 21, i.e. function divideByTwo was able to change the actual value of the parameter.

Reference: msdn, comp, brpreiss

Functions to deal with character

noreply@blogger.com (geteamon) — Fri, 28 Aug 2009 01:17:00 +0300

A lot of useful functions for dealing with characters can be found in the library cctype:

Funstion	Funcionality
isalpha(c);	Returns true if c is a letter (a-z, A-Z)
isupper(c);	Returns true if c is an upper-case letter
islower(c);	Returns true if c is a lower-case letter
isdigit(c);	Returns trud if c is a number(0-9)
isspace(c);	Returns true if c is a white space character
ispunct(c);	Returns true if c is a punctuation mark
toupper(c);	If c is a lower-case letter a upper-case letter is returned, otherwise c is returned
tolower(c);	If c is a upper-case letter a lower-case letter is returned, otherwise c is returned

These can be used by adding #include <cctype> to the includes.

However, the return type and the type of the parameter of these functions is int. This can cause problems in some systems. A safe way to use the functions is always explicitly cast the parameter to int with static_cast<int>( c ); The same can be done to the return type of the toupper and tolower to make sure the character value is correct.

Character string type string

noreply@blogger.com (geteamon) — Thu, 27 Aug 2009 22:22:00 +0300

Since words consist of sequences or strings of characters, there is naturally also the problem of storing and processing strings in C++. One of the solutions to the problem in C++ is the string type. string is part of the C++ standard library. When it is used #include <string> must be added at the beginning of the code file. After that string behaves in the same way as a basic data type:

Defining variables
Parameters and return types of functions
Assignment and initialization from another string variable or literal with =
Printing with cout and reading input with cin
Comparison with ==, !=, <=, >=, <>

In addition, string has other useful properties. Let's take a closer look at the string type.

A string variable is defined:

string variable_name = "init_value";

Any text inside the quotes can be assigned to a string variable. string is a special type that does not necessarily need the "init_value" but it is usually initialized for consistency.

Reading a string:

int main( void )
{
string name = "";
cout << "What's your name?" << endl;
cin >> name;
cout << "Hello" << name << endl;
}

The output of the program:

What's your name?
Harry Potter
Hello Harry

So cin stops reading the input when it encounters the first white space character. The entire line can be read by using the function getline():

int main( void )
{
string name = "";
cout << "What's your name?" << endl;
getline( cin, name );
cout << "Hello" << name << endl;
}

Now the output will be:

What's your name?
Harry Potter
Hello Harry Potter

getline always reads the entire line (including white spaces). It has two arguments, first the input stream (cin) and second which string you wish to write to.

A string variable can contain as many characters as needed. string has a lot of functions of its own that can be used to get information about the string. The size of the string can be obtained with the length() function. The function returns the amount of characters in the string.

cout << name.length();

would print 12 after the getline. The individual characters in a string can be accessed either with the at() function or with [].

name.at( 1 ) = name[ 10 ];

There are several functions for finding substrings:

name.find( "ot" );
name.find( "ot", 3 );

find() functions return the position of the substring "ot" in the string name. If the substring is not found, the function returns a special value string::npos

A part of a stirng can be accessed with the substr() function. On the other hand replace() function lets you to write to a substring.

name.substr( 0, 5 ); //equal Harry
name.replace( 0, 5, "Ron" ); //equals Ron Potter

A part of a string can be removed with erase()

name.erase( 0, 4); // leaves just potter

append() adds a substring to the end of the string:

name.append( " the wizard" );

The length of the string changes if needed. The size can also be changed explicitly with the resize() function:

name.resize( 6 ); //leaves again just potter

Reference: cplusplus, anaturb, cppreference

Array

noreply@blogger.com (geteamon) — Wed, 26 Aug 2009 18:47:00 +0300

A variable of the type int or double can contain one value at a time. It would often be useful of the able to handle an aggregate of elements of the same type. An array is a structured datatype that:

has a specified size
consists of data elements of the same type
the elements are identified by their position in the array

In C++ array variables are declared:

type array_name[ capacity ];

The result is an array type variable named array_name in which data elements of the type type can be stored. The number of elements the array can contain is determined by capacity. type can be any defined type (predefined or programmer-defined). capacity needs to be a constant or a literal. For example, an integer array with nine elements:

int numbers[ 9 ];

An array can be seen as a row of numbered boxes, whose contents can be checked and changed. Every box fits one data element of the type type. In C++ arrays are indexed from zero through size-1.

int numbers[ 9 ] looks like this:

numbers:


0	1	2	3	4	5	6	7	8

the index of the last element is one smaller than the size of the array.

An element at index i can be accessed using [ ]:

numbers[8] = 2*numbers[0];

would give the last element the value of the first element times two. Any expression of the type integer can be used as an operand for the brackets.

For example,

const int SIZE = 10;

int maxValue( )
{
    int array[ SIZE ];
    int i = 0;
    int max = 0;
    while( i <>
    {
        cin >> array[ i ];
        if( array[ i ] > max )
        {
            max = array[ i ];
        }
        ++i;
    }
    return max;
}

No checking is done ot ensure that the indices stay within the range determined by the declaration of the array:

int index = 1000;
numbers[ index ] = 10; // logical error!

A compiler compiles the code above just fine. It is still incorrect because it refers to a non-existent element.

Like all variables, an array needs to be initialized with some sensible values before it can be used. An array can be initialized at declaration:

int numbers[ 9 ] = {1, 2, 3, 4, 5, 6, 7};

results in an array:

numbers:

1	2	3	4	5	6	7	0	0
0	1	2	3	4	5	6	7	8

If there are less elements at initialization than the size of the array can contain, the rest of the elements are initialized to zero.

It is not necessary to tell the size of the array when initialized. It is automatically determined from the number of elements.

int numbers[ ] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

This is true only at initialization and cannot be used as a general method of handling array data. An array cannot be assigned another with =. Moreover, arrays cannot be compared with != and == operators. In array everything must be done one element at a time.

Arrays are static data structures. Their capacity cannot change during program execution. The capacity must always be fixed when the program is compiled:

int capacity = 0;
cin >> capacity;
int array[ capacity ]; // Error

results in a compilation error.

Reference: cplusplus, codesource, fredosaurus