Monday, December 28, 2009

ADT implementation

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





Saturday, September 19, 2009

Abstract Data Types

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



 

Friday, September 18, 2009

Abstraction

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



Sunday, September 6, 2009

Array vs vector

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:

operationarrayvector
Creationint t[10]vector<int> t(10); or
vector<int> t; (empty)
Assignmentin a loopt1 = t2
Indexingt[i]t[i] or t.at(i)
Inserting to the endnot possiblet.push_back(item)
Combiningnot possiblet1.insert(t1.end(), t2.begin(), t2.end())
Sizeprogrammer must knowt.size()
Emptyingnot possiblet.clear()
Comparisonin a loopt1 == t2 (likewise <>
Insertion to the middlenot possiblet.insert(iterator, item)
Searchingin a loopfind(t.begin(), t.end(), item)
Exchange of valuesin a loopt1.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

Previous post

Next post


Vector

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

Previous post

Next post


Saturday, September 5, 2009

Using several code files

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

Previous post

Next post


typedef

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

Previous post

Next post


switch statement

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

Previous post

Next post


Enumeration

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

Previous post

Next post


Streams as parameters

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

Previous post

Next post


Problems with streams

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

Previous post

Next post


Wednesday, September 2, 2009

Operations with inputstreams

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

Previous post

Next post


Tuesday, September 1, 2009

Streams in C++

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

Previous post

Next post


Streams

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


Previous post

Next post


sizeof

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


Previous post

Next post


Monday, August 31, 2009

Searching data

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

binary search technique

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

Previous post

Next post


Sorting in C++

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

Previous post

Next post


Sorting

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


Previous post

Next post



Sunday, August 30, 2009

Modifiers: unsigned, short and long

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


Previous post

Next post


Structures

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


Previous post

Next post




Saturday, August 29, 2009

Arrays as parameters

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


Previous post

Next post