Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
PROGRAM W C++
/* ************************************************
Program computes the volume of a spherical ball
************************************************ */
#include // input-output library
#include // math functions library
void main()
{
const double PI = 3.14159;
cout <<  Enter the radius:  ;
double radius;
cin >> radius;
double power = 1.0;
for (int k = 1; k <= 3; k++) power *= radius;
double volume = 4 * PI * power / 3;
cout <<  \nThe volume of the spherical ball is 
<< volume <<  cubic meters.\n ;
}
PRZYKA
ADOWY PROGRAM
#include // input-output library
void main()
{
cout <<  Enter the number of chosen month:  ;
int month; cin >> month;
switch (month)
{
case 1: cout <<  January\n ; break;
case 2: cout <<  February\n ; break;
.
.
.
case 11: cout <<  November\n ; break;
case 12: cout <<  December\n ; break;
default: cout <<  Code error\n ;
}
}
� Jerzy Tyszer 2004 1
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
P
TLA WYLICZENIOWA
for (init_exp; bool_exp; step_exp)
statement;
// oblicz wartość n silnia (n!)
cin >> number;
int product = 1;
for (int k = 2; k <= number; k++)
product * = k;
cout << number <<  ! =  ;
cout << product <<  \n ;
P
TLA UPRZEDZAJ
CA
while (bool_exp) statement;
char c;
int value = 0, sign = 1;
// skip space
while ((c = getchar()) = =   );
// determine sign
if (c = =  + || c = =  - )
sign = (c = =  + ) ? 1 : -1;
else value = c -  0 ;
// calculate value of the number
while ((c = getchar()) >=  0 && c <=  9 )
value = 10 * value + c -  0 ;
cout << sign * value <<  \n ;
P
TLA POTWIERDZAJ
CA
do
statement;
while (bool_exp);
cin >> value; int temp = value;
int numDigits = 0;
do
{
numDigits++;
value /= 10;
}
while (value != 0);
cout << temp <<  contains 
<< numDigits <<  digit(s)\n ;
� Jerzy Tyszer 2004 2
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
INSTRUKCJE CONTINUE ORAZ GOTO
for (int i = 1; i < limit_a; i++)
for (int j = 1; j < limit_b; j++)
for (int k = 1; k < limit_c; k++)
{
statements_1;
if (condition_1) continue;
statements_2;
if (condition_2) goto e1;
}
e1: further statements ...
SITO ERASTOTENESA
cin >> n;
int prime = 2;
unsigned int sieve = 0xFFFFFFFC; // set 1 & 111111100
while (prime * prime <= n){
for (int mult = 2*prime; mult <= n; mult += prime)
sieve &= ~(1 << mult); // reset on mult
do // find next non-zero number
prime++;
while (!(sieve & (1 << prime)));
}
for (int i = 2; i <= n; i++)
if (sieve & (1 << i))cout << i <<   ;
� Jerzy Tyszer 2004 3
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
TABLICE
const int NUM_ELEMENTS = 25;
int count[NUM_ELEMENTS]; // array of 25 int elements
char text[NUM_ELEMENTS]; // array of 25 char elements
int Primes[10] = {2,3,5,7,11,13,17,19,23,29};
double Table[6] = {3.1,2.5}; // � {3.1,2.5,0,0,0,0}
int histogram[4] = {0}; // � {0,0,0,0}
int Vector[] = {7,1,4}; // array of 3 int elements
double sum = 0.0; // compute the average
for (int index = 0; index < numValues; index++)
sum += Data[index];
double average = sum / numValues;
int ABC[4][3] = {1,2,3,4,5,6,7,8,9,10,11,12};
ABC[0][0] = 1; ABC[0][1] = 2; ABC[0][2] = 3;
ABC[1][0] = 4; ABC[1][1] = 5; ABC[1][2] = 6;
ABC[2][0] = 7; ABC[2][1] = 8; ABC[2][2] = 9;
ABC[3][0] = 10; ABC[3][1] = 11; ABC[3][2] = 12;
char Text[80] = {  computer };
char Text[80] = { c , o , m , p , u , t , e , r };
char Text[] = {  computer };
char Text[] = { c , o , m , p , u , t , e , r };
� Jerzy Tyszer 2004 4
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
FUNKCJE
double volume (double);
double volume (double radius)
{
const double PI = 3.14159;
double power = 1.0;
for (int i = 1; i <= 3; i++)power * = radius;
return (4.0 * PI * power / 3.0);
}
PROSTE PRZYKA
ADY
// przez wartość
int Round (double number)
{
return (number + 0.5);
}
// przez referencję
void Swap (char &first, char &second){
char temporary = first;
first = second;
second = temporary;
} // no return instruction
WI
CEJ O ARGUMENTACH
void Separator (char * string){
static char separator =   ;
cout << separator << string;
separator =  , ;
} // different action the first time
� Jerzy Tyszer 2004 5
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
WZORCE (SZABLONY) FUNKCJI
void Swap (char &first, char &second)
{ char temporary = first;
first = second; second = temporary;}
void Swap (bool &first, bool &second)
{ bool temporary = first;
first = second; second = temporary;}
void Swap (int &first, int &second)
{ int temporary = first;
first = second; second = temporary;}
void Swap (double &first, double &second)
{ double temporary = first;
first = second; second = temporary;}
void Swap (short &first, short &second)
{ short temporary = first;
first = second; second = temporary;}
void Swap (long &first, long &second)
{ long temporary = first;
first = second; second = temporary;}
template
void Swap (Type &first, Type &second)
{
Type temporary = first;
first = second;
second = temporary;
}
REKURENCJA
int Factorial (int n)
{
if (n = = 0)return 1;
return n * Factorial(n-1);
}
int Factorial (int n) // silnia raz jeszcze
{
int product = 1;
for (int k = 2; k <= n; k++)product * = k;
return product;
}
double Power (double x, int n)
{
if (n = = 0)return 1.0;
if (n % 2 = = 0)return Power(x * x, n / 2);
else return x * Power(x * x, n / 2);
}
� Jerzy Tyszer 2004 6
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
ALGORYTM EUKLIDESA
int nwd (int x, int y)
{
if (y = = 0)return x;
return nwd (y, x % y);
}
WIEŻE HANOI  FUNKCJA REKURENCYJNA
void Move(int n, char F, char T, char S){
if (n = = 1) cout <<  Move the top disk
from  << F <<  to << T <<  \n ;
else
{
Move(n-1, F, S, T);
Move(1, F, T, S);
Move(n-1, S, T, F);
}
}
POSZUKIWANIE REKURENCYJNE
bool Move (int step, int x, int y){
int k = -1, u, v; bool OK = false;
do
{
k++; // next candidate jump
u = x + Jump[k][0]; v = y + Jump[k][1];
if(u >= 0 && u < size && v >= 0 && v < size
&& Board[u][v] = = 0) // if allowed
{
Board[u][v] = step; // record the jump
if(step < size*size && ! Move(step + 1,u,v))
Board[u][v] = 0;
else OK = true;
}
} while (!OK && k < 7);
return OK;
}
� Jerzy Tyszer 2004 7
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
PODSTAWOWE DANE I FUNKCJE
const int HEAP_MAX = 1000;
void insert(double value); // insert a new item
double min() const; // get the root
void remove_min(); // remove the root
int min_child(int parent); // auxiliary function
double heap[HEAP_MAX + 1]; // actual heap array
int heap_size = 0; // the current heap size
double min() const
{
return heap[1];
}
WSTAWIANIE DO KOPCA
void insert(double value) {
int child = ++heap_size;
int parent = child/2;
while (parent && heap[parent] > value){
heap[child] = heap[parent];
child = parent;
parent /= 2;
}
heap[child] = value;
}
USUWANIE Z KOPCA PIERWSZEGO ELEMENTU
void remove_min() {
double last = heap[heap_size--];
int x = 1; int c = min_child(1);
while (c && heap[c] < last){
heap[x] = heap[c];
x = c;
c = min_child(c); // returns 0
} // if no children
heap[x] = last;
}
� Jerzy Tyszer 2004 8
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
FUNKCJA POMOCNICZA
int min_child(int parent)
{
int left = 2*parent;
int right = left + 1;
if (left > heap_size)return 0;
if (right > heap_size || heap[left] < heap[right])
return left;
return right;
}
METODA HEAPSORT  PROGRAM
void heapsort(double vector[], int size)
{
if (size > HEAP_MAX) return;
for (int i = 0; i < size; i++)
insert(vector[i]);
for (i = 0; i < size; i++){
vector[i] = min();
remove_min();
}
}
SORTOWANIE SZYBKIE  FUNKCJA
void Qsort(double data[], int first, int last) {
if(first >= last)return;
double pivot = data[first];
int left = first, right = last + 1;
while (1){
do left++; while (left <= last && data[left] < pivot);
do right--; while (data[right] > pivot);
if (left > right)break;
swap(data[left], data[right]);
}
swap(data[first], data[right]);
Qsort(data, first, right - 1);
Qsort(data, right + 1, last);
}
� Jerzy Tyszer 2004 9
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
SCALANIE
void mergeAB(int C[], int A[], int N, int B[], int M)
{
for (int i = 0, j = 0, k = 0; k < N + M; k++)
{
if (i = = N){ C[k] = B[j++]; continue;}
if (j = = M){ C[k] = A[i++]; continue;}
C[k] = (A[i] < B[j]) ? A[i++] : B[j++];
}
}
SZYBKIE SCALANIE
void merge(int A[], int h, int m, int r)
{
int i, j, k, Aux[maxN];
for (i = m + 1; i > h; i--) Aux[i-1] = A[i-1];
for (j = m; j < r; j++) Aux[r+m-j] = A[j+1];
for (k = h; k <= r; k++)
if (Aux[j] < Aux[i]) A[k] = Aux[j--];
else A[k] = Aux[i++];
}
SORTOWANIE PRZEZ SCALANIE
void mergesort(int A[], int h, int r)
{
if (r <= h) return;
int m = (h + r)/2;
mergesort (A, h, m);
mergesort (A, m+1, r);
merge (A, h, m, r);
}
WYSZUKIWANIE SEKWENCYJNE
const int SIZE = 100;
int A[SIZE], int left, right, key;
bool found = false;
for (int k = left; k <= right; k++)
if (key = = A[k]) {found = true; break;}
if (found) cout << k; else cout <<  Failure ;
� Jerzy Tyszer 2004 10
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
WYSZUKIWANIE BINARNE
const int SIZE = 100;
int A[SIZE], int left, right, key;
bool found = false;
while (right >= left){
int m = (left + right) / 2;
if (key = = A[m]){found = true; break;}
if (key < A[m]) right = m - 1; else left = m + 1;
}
if (found) cout << m; else cout <<  Failure ;
FUNKCJA MIESZAJ
CA DLA DA
UGICH KLUCZY
char vector[80]; int Modulo = PRIME;
int h = 0; int base = 127; // instead of 128 !!!
for (int k = 0; vector[k]; k++)
h = (base * h + vector[k]) % Modulo;
// h is now a key
USUWANIE Z TABLICY
int Hash[PRIME]; int i; // delete i-th element
Hash[i] = EMPTY;
int j;
for (j = i + 1; Hash[j] != EMPTY; j = (j + 1) % PRIME) {
int item = Hash[j];
Hash[j] = EMPTY;
// re-insert element item
int index = H(item);
while (Hash[index] != EMPTY)
index = (index + 1) % PRIME;
Hash[index] = item;
}
� Jerzy Tyszer 2004 11
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
SILNIA I SYMBOL NEWTONA
double binomial(int n, int k){ // returns (n choose k)
return floor(0.5 + exp(factln(n) - factln(k) - factln(n-k)));
}
double factln(int n){ // returns ln(n!)
static double a[101];
if(n == 1)return 0.0;
if(n <= 100)return a[n] ? a[n] : (a[n] = gammln(n+1.0));
else return gammln(n+1.0);
}
double gammln(double xx){ //returns the value of ln(Gamma(xx)) for xx>0
double x, y, tmp, ser;
static double cof[6]={76.18009172947146, -86.50532032941677,
24.01409824083091, -1.231739572450155, 0.1208650973866179e-2,
-0.5395239384953e-5};
int j;
y = x = xx;
tmp = x + 5.5;
tmp -= (x + 0.5)*log(tmp);
ser = 1.000000000190015;
for(j = 0; j <= 5; j++)ser += cof[j]/++y;
return -tmp + log(2.5066282746310005*ser/x);
}
PERMUTACJE  PORZ
DEK LEKSYKOGRAFICZNY
void permutation(int n, int P[]){
for (int j = 0; j <= n; j++)P[j] = j;
int i = 1;
while (i != 0){
for (int k = 1; k <= n; k++)cout << P[k] <<  ,  ;
cout <<  \n ; // print the next permutation
i = n - 1;
while (P[i] > P[i+1])i--;
j = n;
while (P[i] > P[j])j--;
swap (P[i], P[j]);
int r = n; int s = i + 1;
while (r > s) {
swap (P[r], P[s]); r--; s++;
}
}
}
� Jerzy Tyszer 2004 12
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
TRANSPOZYCJE
int P[10], Q[10], Dir[10]; // the main program
for (int i = 1; i <= n; i++){
P[i] = Q[i] = i; Dir[i] = -1; // -1: left, 1: right
}
SJT (1,n);
void SJT (int k, int n){ // Steinhaus-Johnson-Trotter
if (k > n){ /* print permutation in array P */ }
else {
SJT (k+1, n);
for (int i = 1; i <= k-1; i++){
Move (k, Dir[k]); // swap k with its neighbor
SJT (k+1, n);
}
Dir[k] = -Dir[k];
}
}
// swap number j with its neighbor indicated by d
void Move (int j, int d){
int z = P[Q[j] + d]; // neighbor of j
P[Q[j]] = z; // swap j and its neighbor
P[Q[j] + d] = j;
Q[z] = Q[j]; // change accordingly locations
Q[j] = Q[j] + d;
}
PODZBIORY K-ELEMENTOWE
void sub_sets (int n, int k){
int C[max]; // max is equal to k + 1
C[0] = -1;
for (int i = 1; i <= k; i++)C[i] = i;
int j = 1;
while (j){
for (int z = 1; z <= k; z++)cout << C[z] <<  ,  ;
cout <<  \n ; // print the next combination
j = k;
while (C[j] = = n - k + j)j--;
C[j]++;
for (i = j+1; i <= k; i++)C[i] = C[i-1] + 1;
}
}
� Jerzy Tyszer 2004 13
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
LOSOWE PODZBIORY K-ELEMENTOWE
for (int i = 0; i < n; i++) P[i] = i;
for (i = 0; i < k; i++){
int j = random(i, n-1);
int item = P[j];
cout << item <<  ,  ;
P[j] = P[i];
P[i] = item;
}
cout <<  \n ;
METODA BISEKCJI  PROGRAM W C++
double fun (double x){
return (x + 1)*(x*x - 3);}
double Bisection (double a, double b)
{
const double ACCURACY = 1.0E-6;
const double NEAR_ZERO = 1.0E-9;
double ya = fun(a);
double yb = fun(b);
while (fabs(b - a) > ACCURACY)
{
double x = (a + b) / 2.0;
double y = fun(x);
if (fabs(y) < NEAR_ZERO)return x;
if (ya * y > 0){ a = x; ya = y;}
else { b = x; yb = y;}
}
return a;
}
� Jerzy Tyszer 2004 14
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
METODA NEWTONA  PROGRAM
double Newton (void (*fun)(double, double &, double &), double a, double b)
{
const double ACCURACY = 1.0E-6; const int MAX = 100;
double f, df, dx, root;
root = (a + b) / 2.0; // initial guess
for (int i = 0; i < MAX; i++)
{
fun(root, f, df);
dx = f / df;
root -= dx;
if ((a - root)*(root  b) < 0.0){
cout <<  jump out of brackets\n ; return 0.0;}
if (fabs(dx) < ACCURACY) return root;
}
cout <<  maximum iterations exceeded\n ;
return 0.0;
}
SZUKANIE MINIMUM FUNKCJI  ZA
OTY PODZIAA

const double R = 0.38197;
if (f(b1) > f(b2)){
a = b1;
b1 = b2;
b2 = c  R*(c-a);
}
else {
c = b2;
b2 = b1;
b1 = a + R*(c-a);
}
� Jerzy Tyszer 2004 15
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
METODA TRAPEZÓW  PROGRAM
double f1(double), f2(double), double f3(double);
double TrapezoidalArea
(double a, double b, int n, double (*fun)(double))
{
double xValue = a;
double deltaX = (b - a) / double(n);
double sum = fun(xValue) / 2.0;
for (int i = 1; i <= n-1; i++)
{
xValue + = deltaX;
sum + = fun(xValue);
}
sum + = fun(xValue + deltaX) / 2.0;
return deltaX * sum;
}
// calling function TrapezoidalArea
double result = TrapezoidalArea(A,B,100,f2);
double result_bis = TrapezoidalArea(C,D,500,f1);
METODA ELIMINACJI GAUSSA
bool Reduce (int n, double M[][n]){
const double EPSILON = 1.0E-6; int i, j, k, pivot_row;
double quotient, absolute_pivot;
for (i = 0; i < n; i++){
absolute_pivot = Abs(M[i][i]); pivot_row = i;
for (k = i + 1; k < n; k++)
if (Abs(M[k][i]) > absolute_pivot){
absolute_pivot = Abs(M[k][i]); pivot_row = k;
}
if (absolute_pivot < EPSILON)return false;
if (i != pivot_row)
for (j = 0; j <= n; j++)
swap(M[i][j], M[pivot_row][j]);
for (j = i + 1; j < n; j++){
quotient = -M[j][i] / M[i][i];
for (k = i; k <= n; k++)
M[j][k] += quotient * M[i][k];
}
} return true; }
� Jerzy Tyszer 2004 16
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
void Solve(int n, double M[][n])
{
Solution[n-1] = M[n-1][n] / M[n-1][n-1];
for (int i = n - 2; i >= 0; i--){
Solution[i] = M[i][n+1];
for (int j = i + 1; j <= n; j++)
Solution[i] -= M[i][j] * Solution[j];
Solution[i] /= M[i][i];
}
}
� Jerzy Tyszer 2004 17
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
KLASY
class class_name {
public: // available to other objects
data_members;
function_members;
private: // to prevent the direct access
data_members; // default option
function_members;
protected: // only my family can use it
data_members;
function_members;
};
PRZYKA
AD DEKLARACJI KLASY
class Address {
private:
char Street[80], City[80], Country[80];
int House_number;
int Zip_code[6];
public:
void enter_data(char[],char[],char[],int,int[]);
void display();
int get_number() const { //inline function
return House_number;
}
};
Address my_address, university, my_girl_friend;
int where = my_girl_friend.get_number();
university.display(); // prints the university address
KONSTRUKTOR I DESTRUKTOR
Address :: Address(int actual_number) :
House_number(actual_number) // initialization list
{...}
Address my_address(12);
Address :: ~Address(){...} //clean_up_here
� Jerzy Tyszer 2004 18
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
FUNKCJE ZAPRZYJAy
NIONE
class B; // pre-declaration
class A {
public:
int fun (B &object);
};
class B { // fun gets access to B objects
friend int A::fun(B &object); //friend class A
};
PRZEA
ADOWANIE OPERATORÓW
return_type operator" (parameter_declaration_list)
{
local_declarations;
statement_list;
return expression;
}
LICZBY ZESPOLONE
class complex {
double re, im;
public: // default arguments
complex (double r = 0.0, double i = 0.0) :
re(r), im(i){} // initialization list
friend complex operator+ (complex,complex);
friend complex operator* (complex,complex);
// they are not members of class complex !!!
};
complex operator+ (complex a1, complex a2){
complex sum; // temporary variable
sum.re = a1.re + a2.re;
sum.im = a1.im + a2.im;
return sum;
}
complex operator* (complex a1, complex a2){ // casting
return complex (a1.re * a2.re - a1.im * a2.im,
a1.re * a2.im + a1.im * a2.re);
}
� Jerzy Tyszer 2004 19
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
KONSTRUKTOR JAKO KONWERTER
complex operator+ (complex);
complex complex :: operator+ (complex a1){
return complex (a1.re + re, a1.im + im);
}
complex result = second + argument;
complex result = second.operator+ (argument); //WRONG
DZIEDZICZENIE I HIERARCHIA KLAS
class Vehicle {
public: void start(){cout <<  Starting a vehicle.\n ;}
double capacity(); void loading();
private: double weight; int wheels;
};
class Car : public Vehicle {
public: void display_name( );
int seats;
};
class Motorcycle : public Vehicle,
public Bike { ... };
Motorcycle Valkiria, Gold_wing;
WZORCE KLAS
template
class object {
Item left_node;
Item right_node;
public:
object(Item, Item);
};
template object ::
object(Item L, Item R) :
left_node(L), right_node(R) { };
object Integer_Pair(3,5);
� Jerzy Tyszer 2004 20
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
DYNAMICZNA ALOKACJA TABLICY
Tablica jednowymiarowa
cin >> size;
double *Vector = new double[size];
Vector [5] = 33;
*(Vector + 5) = 33;
Vector[0] = 15;
*Vector = 15;
delete [] Vector;
Tablica dwuwymiarowa
double **Vector;
cin >> size_1; cin >> size_2;
Vector = new double *[size_1];
for (int i = 0; i < size_1; i++)
Vector[i] = new double[size_2];
RODOWÓD
class person {
char name[80];
person *father, *mother;
public:
person(char *text){
strcpy(name,text);
father = mother = NULL;
}
};
person *root = new person( Jan Kowalski );
(*root).father = new person( Roch Kowalski );
(*root).mother = new person( Anna z Potockich );
(*(*root).father).father = new person( Lech Kowalski );
� Jerzy Tyszer 2004 21
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
RODOWÓD JEST STRUKTUR
REKURENCYJN

class person {
char name[80];
person *father, *mother;
public:
person(char *text, person *f, person *m):
father(f), mother(m){
strcpy(name,text);
}
};
person *root =
new person( Jan Kowalski ,
new person( Roch Kowalski ,
new person( Lech Kowalski ,NULL,NULL),NULL),
new person( Anna z Potockich ,NULL,NULL));
POLIMORFIZM
Vehicle Bus;
Bus.start();
class Car : public Vehicle {
public: void start(){cout <<  Starting a car.\n ;
};
Vehicle *p;
p = new Car;
p -> start();
class Vehicle {
public:
virtual void start(){cout <<  Starting a vehicle.\n ;}
};
p -> start();
PRZYKA
AD KONSTRUKTORA KOPIUJ
CEGO
Vector :: Vector (const Vector &original)
{
size = original.size;
Ptr = new double[size];
for (int i = 0; i < size; i++)
Ptr[i] = original.Ptr[i];
}
� Jerzy Tyszer 2004 22
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
POJEMNIK SEKWENCYJNY TYPU WEKTOR
template class vector {
protected:
T *data; // data area
unsigned int size;
public:
vector(unsigned int NoElements); // constructor
vector(unsigned int NoElements, T & initial);
vector(const vector & source); // copy constructor
virtual ~vector(); // destructor
T & operator [](unsigned int index) const; // access
unsigned int length() const; // length of vector
// dynamically change size
unsigned int setSize(unsigned int NoElements);
unsigned int setSize(unsigned int NoElements,
T & initial);
};
POJEMNIK WEKTOR  KONSTRUKTOR
template vector ::
vector(unsigned int NoElements) : size(NoElements) {
data = new T[size]; // possible default initialization !
assert(data != NULL); // usually done automatically
}
template vector ::
vector(unsigned int NoElements, T & initial)
: size(NoElements) {
data = new T[size];
for (int i = 0; i < size; i++) // set to initial value
data[i] = initial;
}
KONSTRUKTOR KOPIUJ
CY
template
vector :: vector(const vector & source)
: size(source.size) {
data = new T[size];
for (int i = 0; i < size; i++) // copy from
data[i] = source.data[i]; // old vector
}
� Jerzy Tyszer 2004 23
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
// destructor
template
vector :: ~vector() {
delete [] data;
data = NULL; // prevents errors if twice deleted
size = 0;
}
PODSTAWOWE OPERACJE
template
unsigned int vector :: length() const {
return size;
}
template
T & vector :: operator [] (unsigned int index) const
{
assert(index >= 0 && index < size);
return data[index];
}
ZMIANA ROZMIARU
template
unsigned int vector ::
setSize(unsigned int NoElements, T & initial){
T *newData = new T[NoElements]; int i;
if (NoElements <= size){
for (i = 0; i < NoElements; i++)
newData[i] = data[i];
}
else {
for (i = 0; i < size; i++)newData[i] = data[i];
for (i = size; i < NoElements; i++)
newData[i] = initial;
}
delete [] data;
size = NoElements; data = newData;
return size;
}
� Jerzy Tyszer 2004 24
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
NOWY POJEMNIK
template
class boundedVector : public vector {
protected:
const int lowbound;
public:
boundedVector(int lowIndex, int highIndex);
boundedVector(int lowIndex, int highIndex,
T & initial);
boundedVector(const boundedVector & source);
T & operator [](int index) const; // access
int lowerBound() const;
int upperBound() const;
// destructor provided by class vector
};
KONSTRUKTOR
template boundedVector ::
boundedVector(int lowIndex, int highIndex)
: lowbound(lowIndex), // the only way to initialize
vector(highIndex  lowIndex + 1)
{
assert(lowIndex <= highIndex);
}
template boundedVector ::
boundedVector(int lowIndex, int highIndex, T & initial)
: lowbound(lowIndex),
vector(highIndex  lowIndex + 1, initial)
{
assert(lowIndex <= highIndex);
}
OPERATOR INDEKSU
template
T & boundedVector :: operator [] (int index) const
{
return vector :: operator [] (index  lowbound);
}
� Jerzy Tyszer 2004 25
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
POZOSTAA
E FUNKCJE
template
int boundedVector :: lowerBound() const
{
return lowBound;
}
template
int boundedVector :: upperBound() const
{
return lowBound + length() - 1;
}
BUDOWA HISTOGRAMU
void histogram (){
boundedVector counts( a ,  z , 0);
string word;
while (cin >> word)
countLetters (counts, word);
for (char c =  a ; c <=  z ; c++)
cout <<  letter << c <<  :
<< counts[c] <<  \n ;
}
FUNKCJA ZLICZAJ
CA
void countLetters (boundedVector & counts,
const string & text)
{
for (int i = 0; text[i] !=  \0 ; i++){
char c = text[i];
if (isupper(c)) c = tolower(c);
if (islower(c)) count[c]++;
}
}
� Jerzy Tyszer 2004 26
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
STRUKTURY DANYCH  LISTY LINIOWE
template
class list {
protected:
link *First; // data field
public:
list() : First(NULL) {} // default constructor
list(const list &source); // copy constructor
virtual ~list(); // destructor
virtual void add(T value); // insert a new item
virtual void delete_all();
T first_element() const; // access the first item
virtual bool includes(T value) const; // inclusion test
bool is_empty() const;
virtual void remove_first();
friend class Iterator ;
};
LISTA JEDNOKIERUNKOWA
template
class link {
public:
link * insert(T value); // after current link
private:
link(T val, link *ptr) : Value(val), Next(ptr) { }
link *Next;
T Value;
friend class list ;
friend class Iterator ;
};
� Jerzy Tyszer 2004 27
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
SKA
ADNIKI KLAS LINK I LIST
template link * link :: insert(T value)
{
new link (value, Next);
assert(Next != NULL);
return Next;
}
template void list :: add(T value)
{
First = new link (value, First);
assert(First != NULL);
}
SKA
ADNIKI KLASY LIST
template T list :: first_element() const
{
assert(First != NULL);
return First->Value;
}
template bool list :: is_empty() const
{
return First = = NULL;
}
template bool list :: includes(T value) const
{
for (link *p = First; p; p = p->Next)
if (value = = p->Value)return true;
return false;
}
template void list :: remove_first() {
assert(First != NULL);
link *ptr = First; // save pointer to the first item
First = ptr->Next; // reassign the First node
delete ptr;
}
template void list :: delete_all() {
link *next;
for (link *p = First; p; p = next){
next = p->Next;
delete p;
}
First = NULL;
}
� Jerzy Tyszer 2004 28
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
ZA
OŻONE OPERACJE NA LIŚCIE
template class Iterator {
public:
Iterator(list &aList);
virtual bool init(); virtual T operator()();
virtual bool operator !(); virtual bool operator++();
virtual void operator=(T value); void remove_current();
void add_before(T new_value); void add_after(T new_value);
protected:
list &my_list; // data fields
link *previous;
link *current;
};
SKA
ADNIKI KLASY ITERATOR
template Iterator ::
Iterator(list &aList) : my_list(aList){
init();
}
template bool Iterator :: init(){
previous = NULL;
current = my_list.First;
return current != NULL;
}
template T Iterator :: operator()(){
assert(current != NULL);
return current->Value;
}
template void Iterator :: operator=(T val){
assert(current != NULL);
current->Value = val;
}
DALSZE SKA
ADNIKI KLASY ITERATOR
template void Iterator :: remove_current()
{
assert(current != NULL);
if (previous = = NULL)
my_list.First = current->Next;
else
previous->Next = current->Next;
delete current;
current = NULL;
}
� Jerzy Tyszer 2004 29
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
OPERATORY ++ ORAZ !
template bool Iterator :: operator++(){
if (current = = NULL){ // move current pointer
if (previous = = NULL) // to next element
current = my_list.First;
else
current = previous->Next;
}
else {
previous = current;
current = current->Next;
}
return current != NULL;
}
template bool Iterator :: operator !(){
if (current = = NULL && previous != NULL)
current = previous->Next;
return current != NULL;
}
WSTAWIANIE NA LIST
PRZED CURRENT
template void Iterator :: add_before(T val)
{
if (previous)
previous = previous->insert(val);
else {
my_list.list::add(val); // to avoid subclass
previous = my_list.First;
current = previous->Next; //if current is NULL
}
}
WSTAWIANIE NA LIST
ZA CURRENT
template void Iterator :: add_after(T val)
{
if (current)current->insert(val); // not shown
else if (previous)
current = previous->insert(val);
else
my_list.list::add(val);
}
� Jerzy Tyszer 2004 30
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
LISTY UPORZ
DKOWANE
template class ordered_list : public list {
public:
virtual void add (T value);
};
template void ordered_list :: add (T value){
Iterator itr(*this);
for (itr.init(); ! itr; itr++)
if (value < itr()) {
itr.add_before(value);
return;
}
itr.add_before(value);
}
SORTOWANIE PRZEZ WSTAWIANIE
template void insert_sort (vector &v){
ordered_list sorter;
// copy the entire vector into the ordered list
vector_Iterator vitr(v);
for (vitr.init(); ! vitr; vitr++)
sorter.add(vitr());
// copy the values back into the array
int i = 0;
Iterator itr(sorter);
for (itr.init(); ! itr; itr++)
v[i++] = itr();
}
PRZYKA
AD  WSKAy
NIKI NA KONIEC
template class double_ended : public list {
public:
double_ended() : Last(NULL) {}
virtual void add(T value); //override 3 functions
virtual void delete_all();
virtual void remove_first();
void add_to_end (T value); // new function
protected:
link * Last;
};
template void double_ended :: add (T value){
if (is_empty()) {
list :: add(value);
Last = First; // only need to handle empty list
} else
list :: add(value);
}
� Jerzy Tyszer 2004 31
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
template
void double_ended :: add_to_end (T value){
if (Last != NULL)
Last = Last->insert(value);
else
add(value);
}
template void list :: delete_all() {
list :: delete_all();
Last = NULL;
}
template void list :: remove_first() {
list :: remove_first();
if (is_empty()) Last = NULL;
}
KOLEJKA FIFO
template T Ring :: dequeue(){
// delete from a queue
assert(! is_empty());
Last_free = Last_free->Next;
return Last_free->value;
}
template void Ring :: enqueue(T value){
// insert a new object into a queue
if (Last_filled->Next = = Last_free)
// create a new link object
Last_filled = Last_filled->insert(value);
else {
//re-use old link objects
Last_filled = Last_filled->Next;
Last_filled->Value = value;
}
}
� Jerzy Tyszer 2004 32
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
KOLEJKA FIFO  KONSTRUKTOR
template Ring :: Ring(int max){
T initial_value;
// create the first link
Last_free = new link (initial_value,0);
assert (Last_free != NULL);
Last_filled = Last_free;
// create a loop by pointing to itself
Last_filled->Next = Last_filled;
// now add the remaining elements
while (max-- > 0)
Last_filled->insert(initial_value);
}
ARYTMETYKA WIELOMIANÓW  SPOSÓB REPREZENTACJI
class term {
public:
term (int coef, int pow); // constructor
int coefficient; // data fields
const int exponent; // once created never changes
};
OPERACJE NA POJEDYNCZYCH SKA
ADNIKACH
term operator *(const term & left, const term & right){
term result (left.coefficient * right.coefficient,
left.exponent + right.exponent);
return result;
}
term operator +(const term & left, const term & right){
assert(left.exponent = = right.exponent);
term result (left.coefficient + right.coefficient,
left.exponent);
return result;
}
bool operator = = (const term & left, const term & right){
return ((left.coefficient = = right.coefficient)
&& (left.exponent = = right.exponent));
}
� Jerzy Tyszer 2004 33
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
KLASA WIELOMIANÓW
class polynomial {
public:
polynomial ();
polynomial (const polynomial & p); // copy constructor
polynomial (term & t);
polynomial (int zero);
polynomial (int one, int zero);
void operator = (const polynomial & right);
void operator + = (const polynomial & right);
void operator * = (const term &);
private:
list terms; // data field
friend polynomial operator * (const polynomial &,
const polynomial &);
friend polynomial operator + (const polynomial &,
const polynomial &);
};
OPERACJA DODAWANIA I PRZYPISANIA
void polynomial :: operator + =(const polynomial & right){
Iterator itrL(terms);
Iterator itrR(right.terms);
for (itrL.init(),itrR.init(); !itrL && !itrR; itrL++){
while (!itrR && itrL().exponent < itrR().exponent){
itrL.add_before(itrR());
itrR++;
}
if (!itrR && itrR().exponent = = itrL().exponent){
itrL = itrL() + itrR();
itrR++;
}
}
while (!itrR){
itrL.add_before(itrR()); itrR++;
}
}
� Jerzy Tyszer 2004 34
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
DODAWANIE PEA
NE
polynomial operator + (const polynomial & left,
const polynomial & right){
// duplicate left using the copy constructor
polynomial result(left);
// use already defined operator +=
result += right;
return result;
}
MNOŻENIE PEA
NE
polynomial operator * (const polynomial & left,
const polynomial & right)
{
// start with empty polynomial
polynomial result;
Iterator itr (right.terms);
for (itr.init(); !itr; itr++)
result += left * itr();
return result;
}
MNOŻENIE PRZEZ POJEDYNCZY SKA
ADNIK
// first define multiplication and assignment operator
void polynomial :: operator *= (const term & right)
{
Iterator itr (terms);
for (itr.init(); !itr; itr++)
itr += itr() * right;
}
// and then actual multiplication
polynomial operator * (const polynomial & left,
const term & right)
{
// duplicate left using the copy constructor
polynomial result(left);
result *= right;
return result;
}
� Jerzy Tyszer 2004 35
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
DRZEWA BINARNE
template
class node {
public:
T value;
.
.
.
protected:
node *left_ptr;
node *right_ptr;
};
FUNKCJE REKURENCYJNE
void tree :: preorder(node *ptr){
if (ptr){examine (ptr);
preorder (ptr->left_ptr); preorder (ptr->right_ptr);
}
}
void tree :: postorder(node *ptr){
if (ptr){
postorder (ptr->left_ptr); postorder (ptr->right_ptr);
examine (ptr);
}
}
void tree :: inorder(node *ptr){
if (ptr){inorder (ptr->left_ptr); examine (ptr);
inorder (ptr->right_ptr);
}
}
TEST PRZYNALEŻNOŚCI
bool tree :: member(T val) const
{
node *current = root;
while (current){
if (current->value = = val)
return true;
current =
(current->value < val) ?
current->right():
current->left();
}
return false;
}
� Jerzy Tyszer 2004 36
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
WSTAWIANIE DO DRZEWA
void tree :: insert(T val) {
if (root){
node *current = root, *child;
while (current){
if (current->value < val){
child = current->right();
if (! child){
current->
right(new node(val));
return;
}
}
else {
...
}
current = child;
}
}
else root = new node (val);
}
OBRÓT W LEWO  KOD
avlNode * avlNode :: rotate_left(){
avlNode *nodeA = this;
avlNode *nodeB = nodeA->right();
// make reconnections
nodeA->right(nodeB->left());
nodeB->left(nodeA);
// update balance factors
int Abf = nodeA->bal_fac, Bbf = nodeB->bal_fac;
if (Bbf <= 0){
if (Abf >= 1)nodeB->bal_fac = Bbf - 1;
else nodeB->bal_fac = Abf + Bbf  2;
nodeA->bal_fac = Abf  1;
}
else {
if (Abf <= Bbf)nodeB->bal_fac = Abf - 2;
else nodeB->bal_fac = Bbf  1;
nodeA->bal_fac = Abf  Bbf  1;
}
return nodeB;
}
� Jerzy Tyszer 2004 37
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
OBRÓT W PRAWO  KOD
avlNode * avlNode :: rotate_right(){
avlNode *nodeA = this;
avlNode *nodeB = nodeA->left();
// make reconnections
nodeA->left(nodeB->right());
nodeB->right(nodeA);
// update balance factors
int Abf = nodeA->bal_fac, Bbf = nodeB->bal_fac;
if (Bbf <= 0){
if (Bbf > Abf)nodeB->bal_fac = Bbf + 1;
else nodeB->bal_fac = Abf + 2;
nodeA->bal_fac = Abf  Bbf + 1;
}
else {
if (Abf <= -1)nodeB->bal_fac = Bbf + 1;
else nodeB->bal_fac = Abf + Bbf + 2;
nodeA->bal_fac = Abf + 1;
}
return nodeB;
}
RÓWNOWAŻENIE  KOD
avlNode * avlNode :: balance(){
if (bal_fac < 0){
if (left()->bal_fac <= 0)
return rotate_right();
else { // double rotation
left(left()->rotate_left());
return rotate_right();
}
}
else {
if (right()->bal_fac >= 0)
return rotate_left();
else { // double rotation
right(right()->rotate_right());
return rotate_left();
}
}
}
� Jerzy Tyszer 2004 38
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
WSTAWIANIE NOWEGO ELEMENTU
avlNode * avlNode :: add(T val){
if (val < value){ // insert into left subtree
if (left()){
int old_bf = left()-> bal_fac;
left(left()->add(val));
if((left()->bal_fac != old_bf) &&
left()->bal_fac)bal_fac--;
}
else {
left(new avlNode (val));
bal_fac--;
}
}
else { // insert into right subtree  next slide !
}
if((bal_fac < -1) || (bal_fac > 1))
return balance();
return this;
}
if (right()){ // insert into right subtree
int old_bf = right()-> bal_fac;
right(right()->add(val));
if((right()->bal_fac != old_bf) &&
right()->bal_fac)bal_fac++;
}
else {
right(new avlNode (val));
bal_fac++;
}
}
void avlTree :: add(T val){
if(root)root = root->add(val);
else root = new avlNode (val);
}
� Jerzy Tyszer 2004 39
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
GRAFY  ALGORYTM PRZESZUKIWANIA WGA

B
void depth_first (node Graph[], int current) {
Graph[current].color = green; // it assumes all nodes
Graph[current].discovered = ++time; // are initialized
vertex *ptr = Graph[current].ptr;
while (ptr){
if (Graph[ptr->id].color = = bronze){
Graph[ptr->id].pred = current;
depth_first(Graph, ptr->id);
}
ptr = ptr->next;
}
Graph[current].color = red;
Graph[current].finished = ++time;
}
time = 0;
for (int v = 0; v < Nodes; v++)
if (my_graph[v].color = = bronze)depth_first(my_graph,v);
PROGRAM ZNAJDYWANIA ŚCIEŻKI
bool search (node Graph[], int v, int w) {
if (v = = w)return true;
Graph[v].visited = true;
vertex *ptr = Graph[v].ptr;
while (ptr){
if (! Graph[ptr->id].visited){
if(search(Graph, ptr->id, w)){
cout << ptr->id << v;
return true;
}
}
ptr = ptr->next;
}
return false;
}
if(search(my_graph, v, w))cout <<  path found ;
� Jerzy Tyszer 2004 40
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
DROGA EULERA
int tour (node Graph[], int v) {
while (true){ // program destroys graph
vertex *ptr = Graph[v].ptr;
if (ptr = = NULL)return v;
int w = ptr->id;
Stack.push(w);
remove_edge(v, w); // delete two Graph objects
remove_edge(w, v);
v = w;
}
}
// print Euler path
while (tour(my_graph, v) = = v && !Stack.empty()){
v = Stack.pop(); cout <<  - << v;
}
cout <<  \n ;
PROGRAM  ŚCIEŻKA HAMILTONA
bool searchH (node Graph[], int v, int w, int d) {
// only for tiny graphs ! First call with d = V
if (v = = w)return (d = = 0); // new !
Graph[v].visited = true;
vertex *ptr = Graph[v].ptr;
while (ptr){
if (! Graph[ptr->id].visited){
if(searchH(Graph, ptr->id, w, d - 1)){
cout << ptr->id << v;
return true;
}
}
ptr = ptr->next;
}
Graph[v].visited = false; // new !
return false;
}
� Jerzy Tyszer 2004 41
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
ALGORYTM PRZESZUKIWANIA WSZERZ
void breadth_first (node Graph[], int start) {
Graph[start].color = green; // it assumes all nodes
Graph[start].distance = 0; // are properly initialized
enqueue(Q,start);
while (! empty(Q)){
int v = dequeue(Q); vertex *ptr = Graph[v].ptr;
while (ptr){
if (Graph[ptr->id].color = = bronze){
Graph[ptr->id].color = green;
Graph[ptr->id].distance = Graph[v].distance + 1;
Graph[ptr->id].pred = v;
enqueue(Q,ptr->id);
}
ptr = ptr->next;
}
Graph[v].color = red;
}
}
REALIZACJA ALGORYTMU PRIMA
void prim_spanning_tree (node Graph[], int root) {
heap Queue(Nodes);
for (int i = 0; i < Nodes; i++){
Graph[i].tree = false; // no member of tree
Queue.insert(vkey(i, i = = root ? 0 : INF));
}
while (! Queue.empty()){
vkey u = Queue.extract_min(); Graph[u.id].tree = true;
vertex *ptr = Graph[u.id].ptr;
while (ptr){
int v = ptr->id;
if (!Graph[v].tree && ptr->weight < key(v)){
Graph[v].pred = u.id;
Queue.update_key(v, ptr->weight);
}
ptr = ptr->next;
}
}
}
� Jerzy Tyszer 2004 42
Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja
ALGORYTM DIJKSTRY  PROGRAM
void dijkstra (node Graph[], int start) {
heap Queue(Edges);
Queue.insert(arc(start,0.0));
while (! Queue.empty()){
arc u = Queue.extract_min();
if (! tree.member(u.id)){
double dist = u.length;
tree.insert(u.id);
vertex *ptr = Graph[u.id].ptr;
while (ptr){
int v = ptr->id;
Queue.insert(arc(v, dist + ptr->weight));
ptr = ptr->next;
}
}
}
}
� Jerzy Tyszer 2004 43