Informatyka materialy

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ROGRAM W

C++

/* ************************************************
Program computes the volume of a spherical ball

************************************************ */

#include <iostream.h> // input-output library
#include <cmath.h> // 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”;

}

RZYKŁADOWY PROGRAM

#include <iostream.h> // 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”;

}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

Ę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”;

Ę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”;

Ę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”;

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

NSTRUKCJE 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 ...

ITO

RASTOTENESA

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 << ” ”;

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ABLICE

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’};

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

UNKCJE

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);
}

ROSTE PRZYKŁ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

IĘCEJ O ARGUMENTACH

void Separator (char * string){
static char separator = ‘ ’;
cout << separator << string;

separator = ‘,’;
} // different action the first time

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ZORCE

(

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 <class Type>
void Swap (Type &first, Type &second)

{
Type temporary = first;

first = second;
second = temporary;
}

EKURENCJA

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);
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

LGORYTM

UKLIDESA

int nwd (int x, int y)
{

if (y =

= 0)return x;

return nwd (y, x % y);

}

IEŻE

ANOI

–

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);
}

}

OSZUKIWANIE 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;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ODSTAWOWE 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];

}

STAWIANIE 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;
}

SUWANIE 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;
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

UNKCJA 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;
}

ETODA 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();
}

}

ORTOWANIE 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);

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

CALANIE

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++];

}
}

ZYBKIE 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++];
}

ORTOWANIE 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);
}

YSZUKIWANIE 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”;

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

YSZUKIWANIE 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”;

UNKCJA MIESZAJĄCA DLA DŁ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

SUWANIE 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;
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ILNIA I SYMBOL

EWTONA

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

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);

}

ERMUTACJE

–

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++;

}
}

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

RANSPOZYCJE

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;

}

ODZBIORY 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;
}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

OSOWE 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”;

ETODA 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;
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ETODA

EWTONA

–

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;

}

ZUKANIE MINIMUM FUNKCJI

–

ZŁOTY PODZIAŁ

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);

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ETODA 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);

ETODA ELIMINACJI

AUSSA

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; }

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];

}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

LASY

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;
};

RZYKŁ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

ONSTRUKTOR I DESTRUKTOR

Address :: Address(int actual_number) :

House_number(actual_number) // initialization list
{...}

Address my_address(12);

Address :: ~Address(){...} //clean_up_here

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

UNKCJE ZAPRZYJAŹ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
};

RZEŁADOWANIE OPERATORÓW

return_type operator∆ (parameter_declaration_list)

{
local_declarations;
statement_list;

return expression;
}

ICZBY 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);
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ONSTRUKTOR 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

ZIEDZICZENIE 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;

ZORCE KLAS

template <class Item>

class object {
Item left_node;

Item right_node;
public:

object(Item, Item);
};
template <class Item> object <Item> ::

object(Item L, Item R) :
left_node(L), right_node(R) { };

object <int> Integer_Pair(3,5);

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

YNAMICZNA 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];

ODOWÓ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”);

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ODOWÓ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));

OLIMORFIZM

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();

RZYKŁ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];
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

OJEMNIK SEKWENCYJNY TYPU WEKTOR

template <class T> 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);
};

OJEMNIK WEKTOR

–

KONSTRUKTOR

template <class T> vector <T> ::

vector(unsigned int NoElements) : size(NoElements) {
data = new T[size]; // possible default initialization !

assert(data != NULL); // usually done automatically
}

template <class T> vector <T> ::
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;

}

ONSTRUKTOR KOPIUJĄCY

template <class T>
vector <T> :: vector(const vector<T> & source)

: size(source.size) {
data = new T[size];

for (int i = 0; i < size; i++) // copy from
data[i] = source.data[i]; // old vector
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

// destructor

template <class T>
vector <T> :: ~vector() {
delete [] data;

data = NULL; // prevents errors if twice deleted
size = 0;

}

ODSTAWOWE OPERACJE

template <class T>
unsigned int vector <T> :: length() const {
return size;

}

template <class T>
T & vector <T> :: operator [] (unsigned int index) const

{
assert(index >= 0 && index < size);

return data[index];
}

MIANA ROZMIARU

template <class T>
unsigned int vector <T> ::

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;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

OWY POJEMNIK

template <class T>
class boundedVector : public vector <T> {

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

};

ONSTRUKTOR

template <class T> boundedVector <T> ::
boundedVector(int lowIndex, int highIndex)

: lowbound(lowIndex), // the only way to initialize
vector<T>(highIndex – lowIndex + 1)

{
assert(lowIndex <= highIndex);

}

template <class T> boundedVector <T> ::
boundedVector(int lowIndex, int highIndex, T & initial)

: lowbound(lowIndex),
vector<T>(highIndex – lowIndex + 1, initial)

{
assert(lowIndex <= highIndex);

}

PERATOR INDEKSU

template <class T>
T & boundedVector <T> :: operator [] (int index) const

{
return vector<T> :: operator [] (index – lowbound);
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

OZOSTAŁE FUNKCJE

template <class T>
int boundedVector <T> :: lowerBound() const

{
return lowBound;

}

template <class T>
int boundedVector <T> :: upperBound() const

{
return lowBound + length() - 1;

}

UDOWA HISTOGRAMU

void histogram (){
boundedVector <int> 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’;
}

UNKCJA ZLICZAJĄCA

void countLetters (boundedVector<int> & 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]++;
}

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

TRUKTURY DANYCH

–

LISTY LINIOWE

template <class T>
class list {

protected:
link <T> *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 <T>;

};

ISTA JEDNOKIERUNKOWA

template <class T>
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 <T>;
friend class Iterator <T>;

};

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

KŁADNIKI KLAS LINK I LIST

template <class T> link <T> * link <T> :: insert(T value)
{

new link <T>(value, Next);
assert(Next != NULL);

return Next;
}

template <class T> void list <T> :: add(T value)
{

First = new link <T>(value, First);
assert(First != NULL);

}

KŁADNIKI KLASY LIST

template <class T> T list <T> :: first_element() const
{

assert(First != NULL);
return First->Value;

}

template <class T> bool list <T> :: is_empty() const

{
return First =

= NULL;

}

template <class T> bool list <T> :: includes(T value) const
{
for (link <T> *p = First; p; p = p->Next)

if (value =

= p->Value)return true;

return false;

}

template <class T> void list <T> :: remove_first() {
assert(First != NULL);

link <T> *ptr = First; // save pointer to the first item
First = ptr->Next; // reassign the First node
delete ptr;

}

template <class T> void list <T> :: delete_all() {
link <T> *next;

for (link <T> *p = First; p; p = next){
next = p->Next;
delete p;

}
First = NULL;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ŁOŻONE OPERACJE NA LIŚCIE

template <class T> class Iterator {
public:

Iterator(list <T> &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 <T> &my_list; // data fields

link <T> *previous;
link <T> *current;

};

KŁADNIKI KLASY

TERATOR

template <class T> Iterator <T> ::
Iterator(list <T> &aList) : my_list(aList){

init();
}

template <class T> bool Iterator <T> :: init(){
previous = NULL;
current = my_list.First;

return current != NULL;
}

template <class T> T Iterator <T> :: operator()(){
assert(current != NULL);

return current->Value;
}
template <class T> void Iterator <T> :: operator=(T val){

assert(current != NULL);
current->Value = val;

}

ALSZE SKŁADNIKI KLASY

TERATOR

template <class T> void Iterator <T> :: remove_current()
{

assert(current != NULL);
if (previous =

= NULL)

my_list.First = current->Next;
else

previous->Next = current->Next;
delete current;
current = NULL;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

PERATORY

ORAZ

template <class T> bool Iterator <T> :: 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 <class T> bool Iterator <T> :: operator !(){
if (current =

= NULL && previous != NULL)

current = previous->Next;
return current != NULL;

}

STAWIANIE NA LISTĘ PRZED CURRENT

template <class T> void Iterator <T> :: add_before(T val)
{
if (previous)

previous = previous->insert(val);
else {

my_list.list<T>::add(val); // to avoid subclass
previous = my_list.First;

current = previous->Next; //if current is NULL
}
}

STAWIANIE NA LISTĘ ZA CURRENT

template <class T> void Iterator <T> :: add_after(T val)

{
if (current)current->insert(val); // not shown

else if (previous)
current = previous->insert(val);
else

my_list.list<T>::add(val);
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ISTY UPORZĄDKOWANE

template <class T> class ordered_list : public list<T> {
public:

virtual void add (T value);
};

template <class T> void ordered_list <T> :: add (T value){
Iterator <T> itr(*this);
for (itr.init(); ! itr; itr++)

if (value < itr()) {
itr.add_before(value);

return;
}

itr.add_before(value);
}

ORTOWANIE PRZEZ WSTAWIANIE

template <class T> void insert_sort (vector<T> &v){

ordered_list <T> sorter;
// copy the entire vector into the ordered list

vector_Iterator <T> vitr(v);
for (vitr.init(); ! vitr; vitr++)
sorter.add(vitr());

// copy the values back into the array
int i = 0;

Iterator <T> itr(sorter);
for (itr.init(); ! itr; itr++)

v[i++] = itr();
}

RZYKŁAD

–

WSKAŹNIKI NA KONIEC

template <class T> class double_ended : public list<T> {

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 <T> * Last;
};

template <class T> void double_ended <T> :: add (T value){
if (is_empty()) {

list <T> :: add(value);
Last = First; // only need to handle empty list

} else
list <T> :: add(value);

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

template <class T>

void double_ended <T> :: add_to_end (T value){
if (Last != NULL)
Last = Last->insert(value);

else
add(value);

}

template <class T> void list <T> :: delete_all() {

list <T> :: delete_all();
Last = NULL;
}

template <class T> void list <T> :: remove_first() {
list <T> :: remove_first();

if (is_empty()) Last = NULL;
}

OLEJKA

FIFO

template <class T> T Ring <T> :: dequeue(){
// delete from a queue

assert(! is_empty());
Last_free = Last_free->Next;

return Last_free->value;
}

template <class T> void Ring <T> :: 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;
}

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

OLEJKA

FIFO

–

KONSTRUKTOR

template <class T> Ring <T> :: Ring(int max){
T initial_value;

// create the first link
Last_free = new link <T>(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);

}

RYTMETYKA 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
};

PERACJE NA POJEDYNCZYCH SKŁ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));

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

LASA 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 <term> terms; // data field
friend polynomial operator * (const polynomial &,

const polynomial &);
friend polynomial operator + (const polynomial &,
const polynomial &);

};

PERACJA DODAWANIA I PRZYPISANIA

void polynomial :: operator + =(const polynomial & right){
Iterator <term> itrL(terms);

Iterator <term> 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++;

}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ODAWANIE PEŁ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;
}

NOŻENIE PEŁNE

polynomial operator * (const polynomial & left,

const polynomial & right)
{
// start with empty polynomial

polynomial result;
Iterator <term> itr (right.terms);

for (itr.init(); !itr; itr++)
result += left * itr();

return result;
}

NOŻENIE PRZEZ POJEDYNCZY SKŁADNIK

// first define multiplication and assignment operator
void polynomial :: operator *= (const term & right)

{
Iterator <term> 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;
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

RZEWA BINARNE

template <class T>
class node {

public:
T value;

.
.
.

protected:
node <T> *left_ptr;

node <T> *right_ptr;
};

UNKCJE REKURENCYJNE

void tree <T> :: preorder(node <T> *ptr){

if (ptr){examine (ptr);
preorder (ptr->left_ptr); preorder (ptr->right_ptr);

}
}

void tree <T> :: postorder(node <T> *ptr){
if (ptr){
postorder (ptr->left_ptr); postorder (ptr->right_ptr);

examine (ptr);
}

}
void tree <T> :: inorder(node <T> *ptr){

if (ptr){inorder (ptr->left_ptr); examine (ptr);
inorder (ptr->right_ptr);
}

}

EST PRZYNALEŻNOŚCI

bool tree <T> :: member(T val) const
{

node <T> *current = root;
while (current){

if (current->value =

= val)

return true;

current =
(current->value < val) ?

current->right():
current->left();

}
return false;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

STAWIANIE DO DRZEWA

void tree <T> :: insert(T val) {
if (root){

node <T> *current = root, *child;
while (current){

if (current->value < val){
child = current->right();
if (! child){

current->
right(new node<T>(val));

return;
}

}
else {

...
}
current = child;

}
}

else root = new node <T>(val);
}

BRÓT W LEWO

–

KOD

avlNode <T> * avlNode <T> :: rotate_left(){
avlNode <T> *nodeA = this;

avlNode <T> *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;
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

BRÓT W PRAWO

–

KOD

avlNode <T> * avlNode <T> :: rotate_right(){
avlNode <T> *nodeA = this;

avlNode <T> *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;
}

ÓWNOWAŻENIE

–

KOD

avlNode <T> * avlNode <T> :: 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();

}
}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

STAWIANIE NOWEGO ELEMENTU

avlNode <T> * avlNode <T> :: 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 <T>(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 <T>(val));

bal_fac++;
}

}

void avlTree<T> :: add(T val){
if(root)root = root->add(val);

else root = new avlNode <T>(val);
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

RAFY

–

ALGORYTM PRZESZUKIWANIA WGŁĄ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);

ROGRAM 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”;

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

ROGA

ULERA

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”;

ROGRAM

–

ŚCIEŻKA

AMILTONA

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;

}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

LGORYTM 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;
}

}

EALIZACJA ALGORYTMU

RIMA

void prim_spanning_tree (node Graph[], int root) {
heap <vkey> 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;

}
}
}

Materiały pomocnicze do wykładu Informatyka dla kierunku Elektronika i Telekomunikacja

LGORYTM

IJKSTRY

–

PROGRAM

void dijkstra (node Graph[], int start) {
heap <arc> 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;

}
}
}

}

Wyszukiwarka

Podobne podstrony:
PRZYSZLOSC KOMPUTEROW, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arteterapią i socjoterap
2008-probny-praktyka-teleinformatyk-wlasny, Technik Informatyk, materialy egzamin teoretyczny
Polecenia linuxa i unixa, Technik Informatyk - materiały, SO I SK
23. Znaki informacyjne, Materiały dla Instruktorów nauki jazdy, instruktor, konspekty
ZASTOSOWANIA KOMPOW, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arteterapią i socjoterapią
2008-probny-praktyka-teleinformatyk-wlasny-klucz, Technik Informatyk, materialy egzamin teoretyczny
Nauka o informacji - materiał do egzaminu, Bibliotekoznawstwo, Bibliotekoznawstwo 2, Informacja nauk
ako pytania zadania cz2 2010, Studia - informatyka, materialy, Architektura komputerów
porownanie, Studia - informatyka, materialy, Assembler
Linki, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arteterapią i socjoterapią ^V^, ^v^ Info
OPROGRAMOWANIE, ^v^ UCZELNIA ^v^, ^v^ Pedagogika, promocja zdrowia z arteterapią i socjoterapią ^V^,
cw4a, Uczelniane, Semestr 1, Modelowanie i analiza systemów informatycznych, Materiały - Uniwersytet

więcej podobnych podstron