Informa cz4 v6 id 213362 Nieznany

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PODSTAWY

PROGRAMOWANIA

kurs I - część 4

PROWADZĄCY: dr inż. Marcin Głowacki

E-Mail:

Marcin.Glowacki@pwr.wroc.pl

Pok.907 C-5

Wrocław 2011

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

ABLICE

EKSTOWE

Teksty przechowuje się w tablicach typu

char

Zapis:
- pojedyncze znaki w pojedynczych apostrofach:

‘

’

- wyrazy/zdania/teksty w cudzysłowie:

”

Tekst lub wyraz albo zdanie.

”

Definicja tablicy z wyrazem

char

Imie [] = ”MARCIN”; // ”MARCIN”

ale

char

Imie[] ={ ’M’,’A’,’R’,’C’,’I’,’N’,’\0’ };

spowoduje utworzenie w pamięci tablicy (łańcucha) znaków:

6 - znaków
7 - elementów

INDEKS

[0]

[1]

[2]

[3]

[4]

[5]

[6]

WARTOŚĆ

Zero: ‘\0’ – znak specjalny oznaczający koniec tekstu w tablicy

Gdy zadajemy rozmiar to zawsze trzeba pamiętać o definiowaniu jednego znaku
więcej na zero.

char Imie[12];

//imię może mieć do 11 znaków – CZY MA KTOS DLUZSZE IMIE niż 11 znaków ?

cout<< ”Podaj imie: ”;
cin>>Imie;

Drukowanie na ekranie:

cout<<endl<<”Podales imie: ”<<Imie;

lub przy użyciu wskaźników:

int i=0;
while(*(Imie+i)) {

//dopóki nie napotka 0

cout<<*(Imie+i)<<endl;

//pamietamy – przesuwa się wskaznik o jeden

i++;

//(na kolejny element)

}
Efekt: M

// Znak ‘0’ nie jest już wyświetlany, ponieważ następuje opuszczenie cyklu while()

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

EKSTACH

- podejście klasyczne wywodzące się z języka C

Można skorzystać z gotowych funkcji przetwarzania tekstów z bibliotek

string.h

oraz

ctype.h

Biblioteka

string.h

#include <

string.h

Przede wszystkim:

size_t

strlen

(char *str)

– oblicza długość tekstu i zwraca (unsigned)

oraz

int

sizeof

()

- można skorzystać z uniwersalnego liczydła rozmiaru

int

strcmp

(

char *str1, char *str2

)

– porównuje dwa teksty

int

strncmp

(

char *str1, char *str2, int n

)

- dla n = liczba znakow

<0 gdy str1 jest przed str2

Wynik:

=0 gdy str1=str2
>0 gdy str1 jest po str2

char

strcpy

(

char *przeznaczenie, char *zrodlo

)

- kopiowanie dwóch tekstów

char

strncpy

(

char *przeznaczenie, char *zrodlo, int n

)

- dla n = liczba znakow

char

strcat

(

char *przeznaczenie, char *zrodlo

)

– kopiowanie przez dopisanie tekstu źródła na

koniec tekstu przeznaczenia

char

strncat

(

char *przeznaczenie, char *zrodlo, int n

)

- dla n = liczba znaków

Biblioteka

ctype.h

#include <

ctype.h

int

toupper

(

char c

) –

mała litera na dużą (duza bez zmian)

int

tolower

(

char c

) –

duża litera na małą (mala bez zmian)

Konwersje liczbowo <=> tekstowe:

int

atoi

(

char *tekst

)

– ASCII do integer

long

atol

(

char *tekst

)

– ASCII do long

double

atof

(

char *tekst

)

– ASCII do double

Poza standardem ANSI (nie wszędzie dostępne):

char *

itoa

(

int N, char *buf, int podstawa

)

– zamienia N na tekst o podstawie i umieszcza w buf

char *

ltoa

(

long N, char *buf, int podstawa

)

char *

ultoa

(

unsigned long N, char *buf, int podstawa

)

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

EKSTACH

#include <iostream>
#include <string.h>
#include <ctype.h>
using namespace std;
char

zdanie

[81];

int

wyrazy

[40];

//////////////////// FUNKCJE /////////////////////////////////
int

fnPodziel

(

char zdan[], int wyr[]

){ //zwraca liczbe wyrazow

int liczba=0; //liczba znalezionych wyrazow
if (

zdan

[0]=='\0')

return (liczba); //kontrola czy zdanie puste

int fl_pocz=0; //fl_pocz (0-szuka pocz.) (1-szuka konca)
int dlg=strlen(

zdan

);

for(int i=0;i<dlg;i++)

if ((

zdan

[i]!='\t')&&(

zdan

[i]!=' ')) {

if (fl_pocz==0) {
fl_pocz=1;

wyr

[liczba++]=i;

}
} else {

zdan

[i]='\0';

fl_pocz=0;
}
return (liczba);
}
int main(){
cout<<"Wprowadz swoje zdanie:";
cin.getline(

zdanie

,sizeof(

zdanie

));

cout<<"To jest twoje zdanie: "<<zdanie<<endl;
int liczba=

fnPodziel

(

zdanie,wyrazy

);

for (int i=0;i<liczba;i++)
cout<<"Wyraz "<<i+1<<" na pozycji "<<

wyrazy

[i]

<<" to "<<&(

zdanie

[wyrazy[i]])<<endl;

return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

EKSTACH

TABLICE WSKAŹNIKÓW –

w tablicach można przechowywać

wskaźniki na tablice, a w nich kolejne wskaźniki na tablice, a w nich ...

//Program wyświetla dni tygodnia
//na podstawie pierwszych trzech znaków z klawiatury
#include <

iostream

#include <

string.h

#include <

ctype.h

using namespace std;
char

Dzi

[4];

char

*Dzien

[]={

"poniedzialek","wtorek","sroda","czwartek",

"piatek","sobota","niedziela"};

int

fnPodaj

(){

while(1){
cout<<"Podaj pierwsze trzy znaki nazwy dnia tygodnia:(k-koniec) ";

cin.getline(

Dzi

,4);

for(int i=0;i<3;i++) {

Dzi

[i]=

tolower

(

Dzi

[i]);

//zmiana na male litery

if (

Dzi

[i]=='k') return (0); //sprawdz czy koniec

}

if(

strlen

(

Dzi

)==3) return (1);

//sprawdza czy dlugosc rowna 3 znaki

cout<<"Wyraz powinien mieć 3 znaki. Wpisales wyraz o dlugosci

"<<

strlen

(

Dzi

)<<endl;

//bledna dlugosc

}}
int

main

(){

int i;
while(

fnPodaj

()){

for (i=0;i<7;i++) //porownaj poszczegolne dni

if(!strncmp(

Dzi

Dzien

[i],3)) {

cout<<"Dzien zaczynajacy sie na "<<

Dzi

<<" to "<<

Dzien

[i]<<endl;

break; //znaleziony dzien

}

if(i==7) //gdy sam konczy for to i=7, gdy break to i<7
cout<<"Nie znalazlem dnia zaczynajacego sie od:" <<

Dzi

<<endl;

}
return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

10.

TRUKTURY

ANYCH

Dane mogą być grupowane w usystematyzowane formy nazywane

STRUKTURAMI

struct

nazwa

{

//struktura posiada swoją nazwę

typ zmienna1

;

//składnik

typ zmienna2

;

//składnik

typ zmienna3;

//składnik

};

STRUKTURA

jest nowym typem zdefiniowanym przez programistę, jednak

należy pamiętać, że bezpośrednio lub pośrednio składa się z typów
wbudowanych.

Podobnie do definicji

KLASY

, ale z pełnym dostępem do składników i bez

definicji metod, czyli funkcji do przetwarzania zmiennych klasy:

class

nazwa

{

//klasa posiada nazwę

public:

//dostęp do składników bez ograniczeń

typ zmienna1

;

//składnik

typ zmienna2

;

//składnik

typ zmienna3;

//składnik

};

W dostępie do zmiennych składowych struktury

używa się operatora ‘.’

(kropka) oraz ”->” jeśli mamy do czynienia ze wskaźnikiem na strukturę.

nazwa

wej

bufor, *wsk_nazwa;

bufor

zmienna1++

;

wsk_nazwa

bufor

;

wsk_nazwa

->zmienna1;

//dostęp do struktury przez wskaźnik

Przykład: struktura zawierająca liczby zespolone

struct

zespol

{

;

składowa rzeczywista

i urojona

int

;

//nie można nadawać wartości domniemanych

};

zespol

={2,4},

;

.a=

.a+5;

.b=

.b+5;

Rezultat: y=7+9i

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

TRUKTURY

ANYCH

Przykład: Program liczy sumę liczb zespolonych

#include <iostream>
#include <cstdlib>
#include <iomanip>

using namespace std;

struct

zespol

{

int

; //a+bi; składowa rzeczywista a i urojona b

};
void fnWyswietl(

zespol

){

cout<<"("<<

z.a

setiosflags(ios::showpos)<<

z.b

<<"i)"

<<resetiosflags(ios::showpos);

};

zespol

fnDodaj(

zespol

int fl_wysw

) {

zespol

suma;

suma.a=

z1.a

z2.a

;

suma.b=

z1.b

z2.b

;

if(fl_wysw) {

fnWyswietl(

);cout<<" + ";fnWyswietl(

);

cout<<" = ";fnWyswietl(suma);cout<<endl;

}
return suma;
}
int

main

(){

zespol

={2,3},

={4,5},

wynik

;

wynik=fnDodaj(

x,y

,1);

zespol

={4,3};

wynik

=fnDodaj(

wynik

,1);

return 0;
};

Efekt:
(2+3i) + (4+5i) = (6+8i)
(6+8i) + (4+3i) = (10+11i)
Aby kontynuować, naciśnij dowolny klawisz . . .

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

NIA

Dane o zadeklarowanych typach mogą być przetwarzane pojedynczo we wspólnej

przestrzeni pamięci nazywanej:

UNIA

union

nazwa

{

//struktura posiada swoją nazwę

typ zmienna1

;

//składnik

typ zmienna2

;

//składnik

typ zmienna3;

//składnik

...
};

Rezerwowana jest przestrzeń pamięci operacyjnej dla największego rozmiaru
zmiennej składowej.

UWAGA

Tylko jeden składnik może być użyty

w tym samym czasie.

Trzeba pamiętać typ danej zapisanej ostatnio do unii i zgodnie z tym typem używać
unię.

Przykład:

union

schowek

{

char

;

//nie można nadawać wartości domniemanych

int

float

};

schowek S1;
S1.c=’A’;
cout<<

S1.c

<<endl;

S1.f=2.72;
cout<<

S1.f

<<endl;

LE: cout<<S1.c<<endl;

//teraz już trzeba używać

S1.f

typu

float

Zastosowanie praktyczne unii jest ... mało praktyczne.

char

int

float

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

RZECIĄśANIE

PERATORÓW

Operatory, które mogą być przeciążane:

>>=

<<=

->*

new

delete

Nie mogą być przeciążane:

.* :: ?:

Niektóre operatory mogą być jedno- lub
dwuargumentowe

& * - +

Operatory są zdefiniowane i przeciążone dla typów wbudowanych, np.

dla int, long, float, double. Kompilator wykrywa typ zmiennych stojących po
obydwu stronach operatora i dobiera odpowiednią funkcję, która wykona
właściwe operacje. Muszą być zdefiniowane różne funkcje dla różnego typu
liczb i kodowania.

Definicja jako funkcja globalna:

arg1

arg2

// gdzie

operator

typ

operator@

(typ

arg1

, typ

arg2

);

Istotna jest kolejność argumentów

arg1

arg2

Po lewej stronie operatora

będzie

pierwszy argument

wywołania funkcji,

po prawej stronie drugi argument

. Ma to znaczenie w procesie wykrywania

typów danych biorących udział w operacji. Nie ma konieczności, żeby typy
argumentów były takie same.

Dzięki wykorzystaniu konwersji można stosować wiele typów danych jako

argumentów, które będą konwertowane do właściwych typów. Należy zadbać
o jednoznaczność kierunku konwersji, tak aby kompilator wiedział który z
argumentów ma konwertować.

Można operatory przeciążyć dla dowolnych typów pisząc odpowiednie
funkcje operatorowe, które mogą być

funkcjami globalnymi

albo funkcjami

składowymi klasy.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

OPERATORY DWUARGUMENTOWE

Przykład: Operator dodawania ”+” zdefiniowany jest jako funkcja globalna:

typ

operator

(

typ

arg1

typ

arg2

){

typ

wynik

;

...
//operacje zmierzające do wykonania operacji dodawania
// i zwrócenia wyniku zgodnego z typem deklarowanym
...

return

wynik

;

};

Przykład:

struct

zespol

{

int

; //a+bi; składowa rzeczywista a i urojona b

};

zespol

operator+

(

zespol

) {

zespol

suma={0,0};

suma.a=

z1.a

z2.a

;

suma.b=

z1.b

z2.b

;

return suma;
}

zespol

operator+=

(

zespol

) {

z1.a=

z1.a

z2.a

;

z1.b=

z1.b

z2.b

;

return z1;
}

Wywołanie:
zespol x={2,3},y={4,5},wynik;
wynik=x+y;

//użycie operatora przeciążonego +

zespol k={4,3};
wynik+=k;

//użycie operatora przeciążonego +=

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

UWAGA

: Dla większej liczby jednoczesnych operacji

zachowana

jest kolejność działań

, np. mnożenie i dzielenie wykonywane jest

przed dodawaniem i odejmowaniem.

A + B * C to samo co A + (B * C )

A = B = C = D to samo co A = ( B = ( C =D))

OPERATORY JEDNOARGUMENTOWE

Występują jako przedrostek lub przyrostek z różnicą w działaniu.

Jednoargumentowe funkcje operatorowe zwykle nic nie zwracają tylko
wykonują operacje na argumentach:

Definicja jako funkcja globalna:

arg

lub

arg

// gdzie

operator

typ

operator@

(typ

arg

){

typ

wynik

;

...
//operacje zmierzające do wykonania funkcji operatorowej
// i zwrócenia wyniku zgodnego z typem deklarowanym
...

return

wynik

;

};

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przykład. Program z przeciążonymi operatorami: + += - -=

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

struct

zespol

{

int a,b; //a+bi; składowa rzeczywista a i urojona b
};
void fnWyswietl(

zespol

z){

cout<<"("<<z.a<<setiosflags(ios::showpos)<<z.b<<"i)"
<<resetiosflags(ios::showpos);
};
void fnWyswietl(

zespol

z1,

zespol

z2,

zespol

wynik, char operat[4]){

fnWyswietl(z1);cout<<" "<<operat<<" ";fnWyswietl(z2);
cout<<" = ";fnWyswietl(wynik);cout<<endl;
}

zespol

operator-

(

zespol

z1) {

//jednoargumentowy '-'

zespol

wynik={0,0};

wynik.a=-1*z1.a;
wynik.b=-1*z1.b;
return wynik;
}

zespol

operator+

(

zespol

z1) {

//jednoargumentowy '+'

zespol

wynik={0,0};

wynik.a=z1.a;
wynik.b=z1.b;
return wynik;
}

zespol

operator+

(

zespol

z1,

zespol

z2) {

//dwuargumentowy '+'

zespol

suma={0,0};

suma.a=z1.a+z2.a;
suma.b=z1.b+z2.b;
return suma;
}

zespol

operator+

(

zespol

z1,int rzeczyw) {

//dwuargumentowy '+'

zespol

suma={0,0};

suma.a=z1.a+rzeczyw;
suma.b=z1.b;
return suma;
}

zespol

operator+

(int rzeczyw,

zespol

z1) {

//dwuargumentowy '+'

zespol

suma={0,0};

suma.a= rzeczyw+z1.a;
suma.b=z1.b;
return suma;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

zespol

operator-

(

zespol

z1,

zespol

z2) {

//dwuargumentowy '-'

zespol

suma={0,0};

suma.a=z1.a-z2.a;
suma.b=z1.b-z2.b;
return suma;
}

zespol

operator-

(

zespol

z1,int rzeczyw) {

//dwuargumentowy '+'

zespol

suma={0,0};

suma.a=z1.a-rzeczyw;
suma.b=z1.b;
return suma;
}

zespol

operator-

(int rzeczyw,

zespol

z1) {

//dwuargumentowy '+'

zespol

suma={0,0};

suma.a=rzeczyw-z1.a;
suma.b=-1*z1.b;
return suma;
}

zespol

operator+=

(

zespol

) {

z1.a=

z1.a

z2.a

;

z1.b=

z1.b

z2.b

;

return z1;
}

zespol

operator+=

(

zespol

&z1,int rzeczyw) {

//dwuargumentowy "+="

suma=z1+rzeczyw;
return z1;
}

zespol

operator+=

(int rzeczyw,

zespol

z1) {

//dwuargumentowy "+="

zespol

suma={0,0};

suma= rzeczyw+z1;
return suma;
}

zespol

operator-=

(

zespol

z1,

zespol

z2) {

//dwuargumentowy "-="

zespol

suma={0,0};

suma=z1-z2;
return suma;
}

zespol

operator-=

(

zespol

z1,int rzeczyw) {

//dwuargumentowy "-="

zespol

suma={0,0};

suma=z1-rzeczyw;
return suma;
}

zespol

operator-=

( int rzeczyw,

zespol

z1) {

//dwuargumentowy "-="

zespol

suma={0,0};

suma= rzeczyw-z1;
return suma; }
///////////////////////////////////////////// MAIN /////////////////////////////////////////////////

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

int

main

(){

zespol

x={2,3},y={4,5},wynik;

wynik=x+y

;

//dwuargumentowy '+'

fnWyswietl(x,y,wynik,"+");

zespol

k={4,3};

fnWyswietl

(+wynik

,k,

wynik+=k

,"+");

//jednoargumentowy '+'

//i dwuargumentowy "+="

fnWyswietl(

k=-wynik

);

//jednoargumentowy '-'

cout<<endl;
wynik=x-y;
fnWyswietl(x,y,wynik,"-");
fnWyswietl(wynik,k,

wynik-=k

,"-");

//dwuargumentowy "-="

fnWyswietl(x);cout<<" + 5 = ";fnWyswietl(

wynik=x+5

);cout<<endl;

//dodawanie rzeczywistej po prawej

cout<<"5 + ";fnWyswietl(x);cout<<" = ";fnWyswietl(

wynik=5+x

);cout<<endl;

//dodawanie rzeczywistej po lewej

fnWyswietl(x);cout<<" - 5 = ";fnWyswietl(

wynik=x-5

);cout<<endl;

//odejmowanie rzeczywistej po prawej

cout<<"5 - ";fnWyswietl(x);cout<<" = ";fnWyswietl(

wynik=5-x

);cout<<endl;

//odejmowanie rzeczywistej po lewej

system("PAUSE");
return 0;
}

Rezultat:

(2+3i) + (4+5i) = (6+8i)
(6+8i) + (4+3i) = (10+11i)
(-6-8i)
(2+3i) - (4+5i) = (-2-2i)
(-2-2i) - (-6-8i) = (4+6i)
(2+3i) + 5 = (7+3i)
5 + (2+3i) = (7+3i)
(2+3i) - 5 = (-3+3i)
5 - (2+3i) = (3-3i)
Aby kontynuować, naciśnij dowolny klawisz . . .

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

OPERATOR STRUMIENIA WYJŚCIA

‘

’

Ktoś skonstruował klasy

ostream

oraz

istream

a także przeciążył operator

dla typów wbudowanych, np. dla int:

cout.operator<<(int ...)

Można przeciążyć ten operator dla własnych typów, ponieważ funkcja
operatorowa może być funkcją globalną i nie musi ingerować w definicję klasy

ostream

Przykład:

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

struct

zespol

{

int

; //a+bi; składowa rzeczywista a i urojona b

};

ostream

operator<<

(

ostream

& ekran,

zespol

) {

ekran <<

"("

z.a

<<setiosflags(ios::showpos)<<

z.b

"i)"

<<resetiosflags(ios::showpos);

return ekran;

};
////////////////////////////// MAIN ////////////////////////////////////
int

main

(){

zespol

={2,3},

={4,5},wynik;

cout<<"Liczba zespolona x = "<<

<<endl;

cout<<"Liczba zespolona y = "<<

<<endl;

system("PAUSE");
return 0;
}

Referencja użyta w argumencie dla wyświetlanych danych

zespol

nie jest

konieczna, bo operator nie ma zamiaru jej modyfikować, ale oszczędza
miejsce w pamięci, ponieważ nie jest tworzona dodatkowa kopia wartości
zespol z na stosie

Rezultat:

Liczba zespolona x = (2+3i)
Liczba zespolona y = (4+5i)
Aby kontynuować, naciśnij dowolny klawisz . . .

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

11.

MIENNE

YNAMICZNE

Operatory:

new

- dynamicznie tworzy zmienną w trakcie działania programu

- rezerwuje miejsce w pamięci, zmienna nie ma nazwy

delete

- kasuje zmienną utworzoną uprzednio przez

new

- zwalnia miejsce w pamięci

new

typ

zwraca

WSKAŹNIK

na nowo utworzoną zmienną danego

typu

int *wd;
wd =

new

int

; //deklaracja zmiennej dynamicznej typu int

lub

int

*wd =

new

int

;

*wd = 10;
*wd+=5;
x = (*wd)++;
........

delete

wd;

//usuniecie zmiennej dynamicznej

Nie zawsze się uda utworzyć zmienną dynamiczną (brak pamięci – inne problemy),

zatem zawsze warto testować wynik operacji.

double

*wz =

new

double

;

if (wz == 0) //wskaźnik równy zero – nic nie wskazuje

//zmienna dynamiczna nie utworzona

Dynamicznie tworzymy

TABLICE

– ale

musimy zadać rozmiar

PRZYKŁAD:

#include <iostream>
using namespace std;
const int MAXTAB=10;
int main(){

int

*iTab =

new

int

[MAXTAB];

//tworzy tablicę iTab – trzeba podać

rozmiar

if (iTab)

//prawda to iTab różne od zera <=> poprawnie utworzone

for (int i = 0; i<MAXTAB; i++){

iTab[i]=i*i;

cout <<i<<" "<<iTab[i]<<endl;

}

else

{ cerr<< "Zalozenie tablicy niemozliwe"; return 1; } //błąd założenia tablicy

//.............tutaj inne operacje przetwarzania

delete

[] iTab;

//kasuje tablice iTab

return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

YNAMICZNE

TRUKTURY

ANYCH

Do dynamicznych struktur danych zalicza się:

- stosy (sterty),
- kolejki,
- listy,
- drzewa binarne (w tym stogi),

YNAMICZNE

TRUKTURY

ANYCH

STOS

jest strukturą, która posiada swoje dno i wierzchołek. Dane ułożone są

w sekwencji począwszy od dna do wierzchołka. Możliwa jest realizacja stosu
przy użyciu listy jednokierunkowej.

dno stosu

nastepny

dane

NULL

wezel 1

wezel 2

nastepny

dane

nastepny

dane

nastepny

dane

wezel 3

wezel n

wierzcholek

Nowe dane mogą być składowane na szczycie stosu, ponad wierzchołkiem. Do
wskaźnika na następny element wpisywana jest poprzedni adres wierzchołka,
a wtedy wierzchołek się przesuwa wskazując na nową daną na szczycie stosu.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

dno stosu

nastepny

dane

NULL

wezel 1

wezel 2

nastepny

dane

nastepny

dane

wezel 3

wierzcholek

dno stosu

nastepny

dane

NULL

wezel 1

wezel 2

nastepny

dane

nastepny

dane

wezel 3

wierzcholek

nastepny

dane

wezel 4

wierzcholek

Odłożenie nowej danej na szczycie stosu

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

YNAMICZNE

TRUKTURY

ANYCH

Pobieranie danych

ze stosu odbywa się w odwrotnej kolejności niż dodawanie

danych, podobnie jak w buforach LIFO – Last In First Out.
Po pobraniu danej ze stosu adres ze wskaźnika na następny węzeł wpisywany
jest do wierzchołka, który zniża się do następnego elementu ze stosu.
Odczytywanie powoduje ściąganie danych ze stosu. Nie ma przeszkód, żeby
mieć swobodny dostęp do informacji przechowywanych na stosie

dno stosu

nastepny

dane

NULL

wezel 1

wezel 2

nastepny

dane

nastepny

dane

wezel 3

wierzcholek

dno stosu

nastepny

dane

NULL

wezel 1

wezel 2

nastepny

dane

nastepny

dane

wezel 3

wierzcholek

nastepny

dane

wezel 4

wierzcholek

Ściągnięcie danej ze stosu

KOLEJKA

jest strukturą, która posiada swój początek i koniec. Dane ułożone

są w sekwencji począwszy do końca. Możliwa jest realizacja kolejki przy
użyciu listy jednokierunkowej.
Dane do kolejki są dodawane na końcu, a pobierane na początku. Pobieranie
danych ze stosu odbywa się w tej samej kolejności co dodawanie danych,
podobnie jak w buforach FIFO – First In First Out.

poczatek

nastepny

dane

nastepny

dane

nastepny

dane

NULL

wezel 1

wezel 2

wezel n

.........

koniec

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

YNAMICZNE

TRUKTURY

ANYCH

poczatek

nastepny

dane

nastepny

dane

nastepny

dane

NULL

wezel 1

wezel 2

wezel 3

koniec

poczatek

nastepny

dane

nastepny

dane

nastepny

dane

wezel 1

wezel 2

wezel 3

koniec

nastepny

dane

wezel 4

koniec

NULL

Dodanie danej na końcu kolejki

poczatek

nastepny

dane

nastepny

dane

nastepny

dane

wezel 1

wezel 2

wezel 3

nastepny

dane

wezel 4

koniec

NULL

poczatek

nastepny

dane

nastepny

dane

wezel 1

wezel 2

nastepny

dane

wezel 3

koniec

NULL

poczatek

Pobranie danej z początku kolejki

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

ISTY

Lista

to ciąg zmiennych dynamicznych powiązanych wskazaniami. Jedna

zmienna wskazuje na inne zmienne tego samego typu dzięki polu
wskaźnikowemu będącemu składnikiem zmiennej. Listę mogą tworzyć
struktury lub obiekty.

Lista

stanowi sekwencyjne powiązanie ze sobą

kolejnych elementów listy, nazywanych węzłami. Powiązania (wskazania)
mogą być jednokierunkowe lub dwukierunkowe.

Lista jednokierunkowa:

pierwszy

nastepny

dane

nastepny

dane

nastepny

dane

NULL

wezel 1

wezel 2

wezel n

.........

Lista dwukierunkowa:

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wezel n

.........

dane

poprzedni

...

NULL

ostatni

Lista dwukierunkowa ze wskazaniem na dane:

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wezel n

.........

wsk_dane

poprzedni

ostatni

...

NULL

dane

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Elementarne operacje na liście:

- wczytanie danych do nowego elementu listy i umieszczenie ich na liście

w określonej kolejności,

- wydruk elementów listy,
- wyszukanie żądanego elementu,
- usunięcie żądanego elementu,
- zapisanie wszystkich elementów listy do pliku,
- odczytanie wszystkich elementów listy z pliku.

Przykład realizacji listy dwukierunkowej.

Określenie struktury danych:

struct

dane

{

char

nazwisko

[MAX],

imie

[MAX];

int

album

;

}

struct

wezel

{

wezel *

nastepny

, *

poprzedni

;

dane *

wsk_dane

;

};

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wezel n

.........

wsk_dane

poprzedni

ostatni

...

NULL

dane

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

DODAWANIE WĘZŁA DO LISTY

pierwszy

NULL

ostatni

NULL

pierwszy

nastepny

poprzedni

NULL

wezel 1

wsk_dane

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wsk_dane

poprzedni

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wezel 3

wsk_dane

poprzedni

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 2

wezel 1

wsk_dane

poprzedni

ostatni

NULL

dane

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

USUWANIE WĘZŁA Z LISTY

pierwszy

NULL

ostatni

NULL

pierwszy

nastepny

poprzedni

NULL

wezel 1

wsk_dane

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wsk_dane

poprzedni

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wezel 3

wsk_dane

poprzedni

ostatni

NULL

dane

pierwszy

nastepny

poprzedni

nastepny

NULL

wezel 1

wezel 2

wsk_dane

poprzedni

ostatni

NULL

dane

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przykład: Lista dwukierunkowa studentów

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
using namespace std;
const int MAX = 100;
const int SZER = 20;
struct

dane

{

char

nazwisko

[MAX],

imie

[MAX];

int

album

;

};
struct

wezel

{

wezel *

nastepny

, *

poprzedni

;

dane *

wsk_dane

;

};

void

Dodaj

(

wezel *&pierwszy, wezel *&ostatni

) {

//referencja do wskaźnika

dane

*nowe_dane

;

//wczytanie nowych danych

nowe_dane

new

dane;

if (

nowe_dane

==NULL) { cerr<<"

Brak pamieci na nowe dane

"; return; }

cout<<"

Podaj nazwisko

: ";

cin.getline

(

nowe_dane->nazwisko

,MAX);

cout<<"

Podaj imie

: ";

cin.getline

(

nowe_dane->imie

,MAX);

int i, dlg=

strlen

(

nowe_dane->nazwisko

);

nowe_dane->nazwisko

[0]=

toupper

(

nowe_dane->nazwisko

[0]);

//pierwsza duża

for (i=1;i<dlg;i++)

nowe_dane->nazwisko

[i]=

tolower

(

nowe_dane->nazwisko

[i]);

dlg=

strlen

(

nowe_dane->imie

);

nowe_dane->imie

[0]=

toupper

(

nowe_dane->imie

[0]);

for (i=1;i<dlg;i++)

nowe_dane->imie

[i]=

tolower

(

nowe_dane->imie

[i]);

cout<<"

Podaj album:

";cin>>

nowe_dane->album

;

wezel

*nowy

;

//tworzenie nowego wezla dla danych

nowy=

new

wezel;

if (

nowy

==NULL) { cerr<<"

Brak pamieci na nowy wezel

"; return; }

nowy->wsk_dane=nowe_dane;

//wskazanie na dane dla wezla

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

//Wybor miejsca na wczepienie nowego wezla do listy

if(pierwszy==NULL) {

//gdy lista pusta

pierwszy=

nowy

; ostatni=

nowy

;

nowy->poprzedni

=NULL;

nowy->nastepny

=NULL;}

else

{

//czy nowy jest równy lub przed pierwszym

(

strcmp

(

nowy->wsk_dane->nazwisko

pierwszy->wsk_dane->nazwisko

)<=0) {

pierwszy->poprzedni=

nowy

;

nowy->nastepny

=pierwszy;

pierwszy=

nowy

;

pierwszy->poprzedni=NULL;
}

else

{

//czy nowy jest równy ostatniemu lub za ostatnim

(

strcmp

(

nowy->wsk_dane->nazwisko

ostatni->wsk_dane->nazwisko

)>=0) {

ostatni->nastepny=

nowy

;

nowy->nastepny

=NULL;

nowy->poprzedni=ostatni;
ostatni=

nowy

;

}

else

{

//nowy powinien być gdzieś w środku

wezel *buf=pierwszy->nastepny;

while

(

strcmp

(

buf->wsk_dane->nazwisko

nowy->wsk_dane->nazwisko

)<0)

buf=buf->nastepny;

//jak wyjdzie z while to znalazl nastepny

nowy->nastepny

=buf;

nowy->poprzedni

=buf->poprzedni;

buf->poprzedni=

nowy

;

nowy->poprzedni->nastepny

nowy

;

}
}
}
}
void

Znajdz

(

wezel *&pierwszy, wezel *&ostatni

) {

wezel *buf=pierwszy;
if(buf==NULL) { cerr<<"

LISTA JEST PUSTA !

"<<endl; return; }

char

szukaj

[MAX],

bufor

[MAX];

cout<<"

Podaj szukane nazwisko:

cin.getline

(

szukaj

,MAX);

int i, dlg=

strlen

(

szukaj

);

szukaj

[0]=

toupper

(

szukaj

[0]);

for (i=1;i<dlg;i++)

szukaj

[i]=

tolower

(

szukaj

[i]);

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

cout<<setw(SZER)<<"Nazwisko"<<setw(SZER)<<"Imie"<<setw(SZER)

<<"Album"<<endl;

while (buf!=NULL) {
if (

strncmp

(

buf->wsk_dane->nazwisko

szukaj

,dlg)==0)

cout<<setw(SZER)<<buf->

wsk_dane->nazwisko

<<setw(SZER)

<<buf->

wsk_dane->imie

<<setw(SZER)<<

buf->wsk_dane->album

<<endl;

buf=buf->nastepny;
}
}
void

Usun

(

wezel *&pierwszy, wezel *&ostatni

) {

wezel *buf=pierwszy;
if(buf==NULL) { cerr<<"

LISTA JEST PUSTA !

"<<endl; return; }

char

szukaj

[MAX],bufor[MAX];

cout<<"

Podaj nazwisko do usuniecia:

cin.getline

(

szukaj

,MAX);

int i, dlg=

strlen

(

szukaj

);

szukaj

[0]=

toupper

(

szukaj

[0]);

for (i=1;i<dlg;i++)

szukaj

[i]=

tolower

(

szukaj

[i]);

cout<<setw(SZER)<<"Nazwisko"<<setw(SZER)<<"Imie"<<setw(SZER)<<"
Album"<<endl;

while

(buf!=NULL) {

if (

strcmp

(buf->

wsk_dane->nazwisko

szukaj

)==0) {

cout<<setw(SZER)<<

buf->wsk_dane->nazwisko

<<setw(SZER)

buf->wsk_dane->imie

<<setw(SZER)<<buf->wsk_dane->album<<endl;

(buf->poprzedni!=NULL)

buf->poprzedni->nastepny=buf->nastepny;

else

pierwszy=buf->nastepny;

(buf->nastepny!=NULL)

buf->nastepny->poprzedni=buf->poprzedni;

else

ostatni=buf->poprzedni;

delete

buf->wsk_dane;

delete

buf;

}
buf=buf->nastepny;
}
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

void

Drukuj

(

wezel *&pierwszy, wezel *&ostatni

) {

wezel *buf=pierwszy;
if(buf==NULL) { cerr<<"

LISTA JEST PUSTA !

"<<endl; return; }

cout<<setw(SZER)<<"Nazwisko"<<setw(SZER)<<"Imie"<<setw(SZER)
<<"Album"<<endl;
while (buf!=NULL) {
cout<<setw(SZER)<<buf->wsk_dane->nazwisko<<setw(SZER)
<<buf->wsk_dane->imie
<<setw(SZER)<<buf->wsk_dane->album<<endl;
buf=buf->nastepny;
}
cout<<"******************* KONIEC LISTY
********************"<<endl; return;
}

int

main

() {

char

znak

;

wezel *pierwszy=NULL, *ostatni=NULL, *nowy;
while(

){

cout<<endl<<"

MENU

:"<<endl;

cout<<"

1 - Dodaj dane

"<<endl<<"

2 - Znajdz

"<<endl

<<"

3 - Drukuj

"<<endl<<"

4 - Usun

"<<endl

<<"

Q - Wyjscie

"<<endl;

cout<<"

Wybierz opcje:

cin

>>znak;

cin.ignore

(255,'\n');

switch(

znak

){

case '

Dodaj

(

pierwszy

ostatni

); break;

case '

Znajdz

(

pierwszy

ostatni

); break;

case '

Drukuj

(

pierwszy

ostatni

); break;

case '

Usun

(

pierwszy

ostatni

); break;

case '

': return 0;

default: cerr<<"

\t\t\tBledna opcja:

"<<

znak

;break;

}
}
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Efekt:
MENU :
1 - Dodaj dane
2 - Znajdz
3 - Drukuj
4 - Usun
Q - Wyjscie
Wybierz opcje: 1
Podaj nazwisko: Kowalski
Podaj imie: Jan
Podaj album: 123456

MENU :
1 - Dodaj dane
2 - Znajdz
3 - Drukuj
4 - Usun
Q - Wyjscie
Wybierz opcje: 1
Podaj nazwisko: Malinowski
Podaj imie: Tomasz
Podaj album: 567891

MENU :
1 - Dodaj dane
2 - Znajdz
3 - Drukuj
4 - Usun
Q - Wyjscie
Wybierz opcje: 1
Podaj nazwisko: Lemanski
Podaj imie: Krzysztof
Podaj album: 3456

MENU :
1 - Dodaj dane
2 - Znajdz
3 - Drukuj
4 - Usun
Q - Wyjscie
Wybierz opcje: 3
Nazwisko Imie Album
Kowalski Jan 123456
Lemanski Krzysztof 3456
Malinowski Tomasz 567891
***************** KONIEC LISTY **************

MENU :
1 - Dodaj dane
2 - Znajdz
3 - Drukuj
4 - Usun
Q - Wyjscie

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

12.

PERACJE NA

LIKACH

CZYM JEST PLIK ?

Nagłówek

END

PLIK

identyfikowany jest w każdym systemie operacyjnym w postaci

nazwy

PLIK

jest

sekwencyjny

w kierunku od początku do końca pliku. Przy zapisie i

przy odczycie – operacje te odbywają się na aktualnej pozycji pliku. Odczyt i
zapis danych przesuwa automatycznie pozycję w pliku do przodu.

PLIK

przechowuje dane o określonych typach:

•

pliki

tekstowe

, zawierające znaki char, - podczas dostępu następuje

konwersja znaków specjalnych na odpowiednie dla systemu operacyjnego,
np. w MSDOS znaki New Line konwertuje na <CR><LF>; inny znak końca
pliku.

•

pliki

binarne

, z treścią binarną – brak jakichkolwiek konwersji.

W bibliotece:

fstream

mamy obiekty związane z plikami:

#include <

fstream

•

domyślnie do odczytu:

ifstream

•

domyślnie do zapisu:

ofstream

UWAGA:

TAK naprawdę to ma jedynie znaczenie tylko jeśli nie są

zdefiniowane flagi. Wtedy działają domyślne ustawienia dla

ifstream

–

odczyt i

ofstream

– zapis.

FAZA I:

Otwarcie

pliku do odczytu lub zapisu

Sprawdzenie

poprawności operacji

Definiujemy odpowiednie obiekty i używamy je jako

strumienie

Zawsze należy sprawdzić, czy plik został poprawnie otwarty.

FAZA II:

Zapis

lub

odczyt

(przesunięcia)

Do zapisu w pliku i odczytu używamy operatorów:

(jak przy

strumieniach

FAZA III:

Zamknięcie

pliku

kierunek

aktualna

pozycja

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

Użycie:
//Otwarcie do odczytu

ifstream

plik_in

(“

filename

”); //strumień

plik_in

do odczytu

ifstream

plik_in

(“

filename

”,

flagi

); //strumień

plik_in

do odczytu

//Otwarcie do zapisu

ofstream

plik_out

(“

filename

”); //strumień

plik_out

do zapisu

ofstream

plik_out

(“

filename

”,

flagi

); //strumień

plik_out

do zapisu

UWAGA:

Obowiązkowo sprawdzenie czy plik poprawnie otwarty:

if (

plik

) {

cerr<<”Blad otwarcia pliku !”;
...
}

FLAGI

trybu otwierania pliku:

Flaga

Znaczenie

Otwarcie do czytania (domyślne dla

ifstream

)

out

Otwarcie do zapisu (domyślne dla

ofstream

)

app

Zawsze dopisuj na końcu pliku

ate

Ustaw pozycje na koniec pliku ("at end")

trunc

Usuń poprzednią zawartość pliku

binary

Nie konwertuj znaków specjalnych

Kombinacje FLAG

i ich znaczenie:

Flagi

Znaczenie

CMode

Czyta (plik też musi istnieć)

"r"

out

Czyści zawartość i zapisuje (tworzy jeśli trzeba)

"w"

out | trunc

Czyści zawartość i zapisuje (tworzy jeśli trzeba)

"w"

out | app

Dołącza na końcu (tworzy jeśli trzeba)

"a"

in | out

Czyta i zapisuje; pozycja na początku pliku (plik musi istnieć)

"r+"

in | out | trunc

Czyści, czyta i zapisuje (tworzy jeśli trzeba)

"w+"

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

Przykład:

ifstream

plik_in

(“

filename

”,

binary

); //otwarcie w trybie binarnym

ofstream

plik_in

(“

filename

”,

out

binary

app

);

Co się dzieje podczas otwierania pliku ?

ofstream

plikWsk

new

ofstream

(”

Nazwa_pliku

");

// przetwarzanie danych i wysyłanie do pliku

delete

plikWsk

;

//zamykanie pliku

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

PRZYKŁAD:

Program zapisuje dane do pliku, a następnie czyta te dane z //pliku

#include <

iostream

#include <fstream>
#include <string>
using namespace std;

void

fnZapisz

(

ofstream

&Plik

){

char x[]="abc",y[]="xyz";

int a=100;

cout<<"Zapisuje do pliku:\n";

Plik

<<x<<' '<<a<<' '<<y<<endl;

//zapis do pliku

cout<<x<<' '<<a<<' '<<y<<endl; //kontrolnie na ekran

}
void

fnOdczyt

(

ifstream

&Plik

){

char x[4],y[4];

int a;

cout<<"Odczytuje z pliku:\n";

Plik

>>x>>a>>y

; //odczyt z pliku

cout<<x<<' '<<a<<' '<<y<<endl; //kontrolnie na ekran

}
int main(){
char

Nazwa

[257];

cout<<"Podaj nazwe pliku do zapisu i odczytu: ";
cin.getline(

Nazwa

,sizeof(

Nazwa

));

ofstream

plik_zap

(

Nazwa

); //otwarcie pliku do zapisu

if (

plik_zap

) { //może być też: if(

plik_zap

fail()

)

cerr <<"Pliku nie udało się otworzyć !"<<endl;

return 1;

} else {

fnZapisz

(

plik_zap

);

plik_zap

close

();

}

ifstream

plik_dane

(

Nazwa

); //otwarcie pliku do odczytu

if (

plik_dane

) {

cerr <<"Pliku nie udało się otworzyć !"<<endl;

return 1;

} else {

fnOdczyt

(

plik_dane

);

plik_dane

close()

;

}
return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

PRZYKŁAD:

Program zapisuje dane do pliku, a następnie czyta te dane z pliku przy użyciu

funkcji fscanf()

#include <stdio.h>
using namespace std;

void fnZapisz(FILE *Plik){

char x[]="abc",y[]="xyz";

int a=100;

printf("Zapisuje do pliku:\n");

fprintf (Plik, "%s %d %s", x, a,y); //zapis do pliku

printf ("%s %d %s\n", x, a,y); //kontrolnie na ekran

}
void fnOdczyt(FILE *Plik){

char x[4],y[4];

int a;

printf("Odczytuje z pliku:\n");

fscanf (Plik, "%s",x); //odczyt z pliku

fscanf (Plik, "%d",&a);

fscanf (Plik, "%s",y);

printf ("%s %d %s\n", x, a,y); //kontrolnie na ekran

}
int main(){
char Nazwa[257];
printf("Podaj nazwe pliku do zapisu i odczytu: ");
scanf("%s",Nazwa);
FILE * plik_zap = fopen (Nazwa,"w+");
//ofstream plik_zap(Nazwa); //otwarcie pliku do zapisu
if (!plik_zap) { //może być też: if(plik_zap.fail())

printf("Pliku nie udało się otworzyć !\n");

return 1;

} else {

fnZapisz(plik_zap);

fclose(plik_zap);

}
FILE *plik_dane= fopen (Nazwa,"r+");; //otwarcie pliku do odczytu
if (!plik_dane) {

printf("Pliku nie udało się otworzyć !\n");

return 1;

} else {

fnOdczyt(plik_dane);

fclose(plik_dane);

}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

return 0;
}

PERACJE NA

LIKACH

INNA METODA DOSTĘPU DO PLIKU:

Jeśli zadeklarowany jest strumień, ale nie jest inicjalizowany („pusty”):

ifstream

plik;

lub

ofstream

plik;

//bez znaczenia, który do jakich celów

to można otwierać pliki przy pomocy funkcji składowych klasy

basic_ios

Funkcje składowe

Znaczenie

Plik

.open

(

nazwa

)

Otwiera plik jako strumień i używa domyślnego trybu

plik

.open

(

nazwa, flagi

)

Otwiera plik jako strumień i używa flag do określenia trybu

plik

.close

()

Zamyka plik

plik

.is_open

()

Zwraca wynik czy plik jest otwarty

plik.

clear

()

Czyści znaczniki końca pliku EOF i FAIL (powinno się wykonywać
przed zamknięciem pliku)

Przykład: - program wyświetla wszystkie teksty z plików o nazwach podanych
w linii komend

#include <cstdlib>
#include <

fstream

#include <iostream>
using namespace std;

int main (int argc, char* argv[]){

ifstream

plik

;

for (int i=1; i<argc; i++) {

//dla wszystkich plików z linii komend

plik

open

(

argv[i]

);

// otwiera

plik

char

;

while (

plik

get

(

)) {

cout.put(c);

// zapisuje zawartość

plik

na cout – znak po znaku

}

plik

clear

();

// czyści bity eof i fail

plik

close

();

// zamyka

plik

}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

OPERACJE NA ZMIENNYCH POZYCJACH W PLIKU:

Klasa

Funkcje składowe

Znaczenie

basic_istream<>

plik

.tellg

()

plik

.seekg

(

pos

)

plik

.seekg

(

offset, rpos

)

Zwraca pozycję aktualną do odczytu
Ustawia na zadanej pozycji licząc od początku
Ustawia na zadanej pozycji

offset

licząc od

rpos

basic_ostream<>

plik

.tellp

()

plik

.seekp

(

pos

)

plik

.seekp

(

offset, rpos

)

Zwraca pozycję aktualną do zapisu
Ustawia na zadanej pozycji licząc od początku
Ustawia na zadanej pozycji

offset

licząc od

rpos

Możliwe jest przesuwanie aktualnej pozycji na dowolną, na której następnie

dokonana będzie operacja zapisu lub odczytu.

Przesuwanie może odbywać się poprzez wskazanie bezwzględnej pozycji w

odniesieniu do początku pliku lub według dodatkowego parametru określającego
zadane miejsce. Pozycja w pliku jest typem:

pos_type

. Istnieją zadeklarowane stałe

dla typowych pozycji:

Stała

Meaning

beg

Pozycja jest podana w odniesieniu do początku pliku ("beginning")

cur

Pozycja jest podana w odniesieniu do aktualnej pozycji ("current")

end

Pozycja jest podana w odniesieniu do końca pliku ("end")

Przykłady:

// zachowaj aktualną pozycję
std::ios::

pos_type

pos

plik

tellg()

;

...

//przetwarzanie

// przesuń się do pozycji zapisanej w

pos

/////////////////////////////////////////////////////////////////

plik

seekg

(

pos

);

// przesuń pozycję na początek pliku

plik

seekg

(0, std::ios::

beg

);

...
// seek 20 character forward

plik

seekg

(20, std::ios::

cur

);

...
// seek 10 characters before the end

plik

seekg

(-10, std::ios::

end

);

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PERACJE NA

LIKACH

FAZIE ODCZYTU

można też wysłać całą zawartość pliku (bufor z

przygotowanymi do odczytu danymi) na strumień wyjścia standardowego
cout.

// wysłanie zawartości całego bufora na cout
std::cout <<

plik

rdbuf()

;

Przykład:

#include <iostream>
#include <fstream>

void DrukujDwa (const char*

nazwa

)

{
std::

ifstream

plik

(

nazwa

);

// otwarcie pliku

std::cout <<

plik

rdbuf

();

// wyświetl zawartość pliku po raz

pierwszy

plik

clear

();

// wyczyść bity eof i fail

plik

seekg

(

);

// przesunięcie na początek

std::cout <<

plik

rdbuf

();

// wyświetl zawartość pliku po raz

drugi

}
int main (int argc, char* argv[])
{

// wyświetla dwukrotnie zawartość plików zadanych w linii komend

for (int i=1; i<argc; ++i) {
DrukujDwa (argv[i]);
}
return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Odczyt danych przy użyciu:

getline

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////
void error(const char * blad, const char * podmiot = ””){
cerr<<blad<<” “<<podmiot<<endl;
exit(1);
}
int main (int argc, char *argv[]) {
if (argc!=2) error (“zla liczba argumentów”);

ifstream

zrodlo

(argv[1]);

//otwarcie pliku zrodla

if(!

zrodlo

) error (”Nie moge otworzyc pliku:”, argv[1]);

char bufor[100];
while(

zrodlo

getline

(

bufor

sizeof(bufor)

)) {

cout<<bufor<<endl;
}

zrodlo

clear

();

zrodlo

close

();

return 0;
}

Program ograniczony jest do wczytania wierszy o długości 100 znaków i dla
wierszy dłuższych zwraca błąd przerywając while.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Inny przykład z użyciem zmiennej typu

string

w całości obiektowy nie ma

takich ograniczeń

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////
void error(const char * blad, const char * podmiot = ""){
cerr<<blad<<" "<<podmiot<<endl;
exit(1);
}
int main (int argc, char *argv[]) {
if (argc!=2) error ("zla liczba argumentow");

ifstream

zrodlo

(argv[1]);

//otwarcie pliku zrodla

if(!

zrodlo

) error (”Nie moge otworzyc pliku:”, argv[1]);

string

bufor

;

while(

getline

(

zrodlo

bufor

)) {

cout<<bufor<<endl;
}

zrodlo

clear

();

zrodlo

close

();

return 0;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

SKAŹNIKI DO

UNKCJI

Wskaźniki zawierają adresy, zatem mogą również wskazywać na miejsce w
pamięci, gdzie rozpoczynają się kody maszynowe instrukcji danej funkcji.

Definicja:

typ

(

*wskaznik

)

(

arg1, arg2,...

);

UWAGA

: Muszą być nawiasy w deklaracji

(

*wsk_fun

)

. Pominięcie nawiasów,

czyli

int *wsk_fun(

arg1, arg2,...

)

; powoduje, że będzie to deklaracja funkcji

wsk_fun

, która zwraca

wskaźnik na

int

Przykład:

int

(

*wsk_fun

)

(

char, int

);

//deklaracja pustego wskaźnika

Funkcja, na którą będzie wskazywał wskaźnik

wsk_fun

powinna zwracać

wartość

int

oraz posiadać argumenty

char, int

int Wyswietl(

char, int

);

//jest taka funkcja

wsk_fun

Wyswietl

;

//teraz

wsk_fun

wskazuje na funkcję

Wyswietl

Nazwa funkcji jest wskaźnikiem na początek kodu funkcji Podobnie jak przy
tablicach.

Wywołanie:

char

znak

=’\n’;

int

liczba

=5;

Wyswietl(

znak, liczba

);

//normalnie

wsk_fun(

znak, liczba

);

//przez wskaźnik do funkcji

Zastosowanie:

- przy przekazywaniu argumentów do innej funkcji;
- do tworzenia tablic wskaźników funkcji; tablice takie stanowią jakby

listę działań – funkcje są ponumerowane.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

SKAŹNIKI DO

UNKCJI

Możliwe jest utworzenie tablicy wskaźników do funkcji.

Definicja:

typ

(

*tab_fun

[

ROZM

])(

arg1, arg2, ...

);

UWAGA

: muszą to być funkcje, które zwracają to samo lub nic nie zwracają

oraz posiadają te same zestawy argumentów wywołania. Tablica musi
posiadać rozmiar.

Przykład – użycie w menu

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void

Pobierz

() {

cout<<" \t\t\tPobieram dane !"; }
void

Oblicz

() {

cout<<" \t\t\tObliczam i obliczam !"; }
void

Drukuj

() {

cout<<" \t\t\tDrukuje !"; }
int main() {
void (

*Tab_Fun

[

])()={

Pobierz

Oblicz

Drukuj

};

char

znak

;

while(1){
cout<<endl<<" MENU :"<<endl;
cout<<" 1 - Pobierz dane"<<endl<<" 2 - Oblicz"<<endl
<<" 3 - Drukuj"<<endl<<" Q - Wyjscie "<<endl;
cout<<" Wybierz opcje: "; cin>>znak;
switch(

znak

){

case '1':
case '2':
case '3':

(

*Tab_Fun

[atoi(&

znak

)-1]

)

(); break;

case 'Q':
case 'q': return 0;
default: cerr<<"\t\t\tBledna opcja: "<<znak;break;
}
}
}

Efekt:
MENU :
1 - Pobierz dane
2 - Oblicz
3 - Drukuj
Q - Wyjscie
Wybierz opcje: 1
Pobieram dane !
MENU :
1 - Pobierz dane
2 - Oblicz
3 - Drukuj
Q - Wyjscie
Wybierz opcje: 2
Obliczam i obliczam
!
MENU :
1 - Pobierz dane
2 - Oblicz
3 - Drukuj
Q - Wyjscie
Wybierz opcje: 3
Drukuje !
MENU :
1 - Pobierz dane
2 - Oblicz
3 - Drukuj
Q - Wyjscie
Wybierz opcje: 4
Bledna opcja: 4

MENU :

1 - Pobierz dane
2 - Oblicz
3 - Drukuj
Q - Wyjscie
Wybierz opcje:

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

13.

RZEWA

Drzewo jest bardziej skomplikowaną strukturą niż poprzednie,
przypominającą graf. Składa się z węzłów oraz połączeń pomiędzy węzłami
nazywanymi krawędziami. Jeden z węzłów drzewa nazywany jest korzeniem.
Korzeń jest jedynym węzłem drzewa, który nie posiada węzłów poprzednich.
Dla każdego innego węzła określony jest dokładnie jeden węzeł poprzedni, z
którym łączy się jedną krawędzią. Węzły ostatnie, nie posiadające węzłów
następnych, nazywane są liśćmi. Dla każdego innego węzła istnieją węzły
następne. Węzeł poprzedni względem danego nazywany jest przodkiem, a
dowiązane węzły następne nazywane są potomkiem.

Dla każdego drzewa można określić:

•

ścieżka z u do v - zbiór węzłów, przez które należy przejść z węzła u do v

•

droga - ścieżka skierowana

•

głębokość węzła u to długość drogi u - liczba węzłów, przez które należy
przejść od korzenia do węzła u liczona z korzeniem włącznie

•

korzeń ma głębokość 1

•

wysokość węzła u - maksymalna liczba węzłów na drodze począwszy od
u do najbardziej odległego liścia w jego poddrzewie z węzłem u włącznie
= maksymalna liczba krawędzi na drodze + 1

•

wysokość drzewa = głębokość najdalszego liścia= wysokość korzenia

•

stopień węzła - liczba jego bezpośrednich następników

•

stopień drzewa - maksymalny stopień węzłów drzewa

Drzewo może być drzewem pustym lub węzłem ze skończoną liczbą
dowiązanych struktur drzewiastym określanych jako poddrzewa.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przykład drzewa stopnia 3

głębokość/wysokość

1/5

2/2

2/5

3/1

3/3

4/1

4/2

5/1

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

DRZEWO BINARNE

Jeżeli liczba następnych elementów wynosi dokładnie 2 (jest stopnia 2) to

drzewo nazywamy

DRZEWEM BINARNYM

W drzewie binarnym każdy z węzłów zawiera dwa wskazania na dwa inne
węzły: lewy i prawy. Każdy z kolejnych elementów posiada wskazanie na dwa
kolejne elementy. W konsekwencji każdy z elementów drzewa zawiera
wskazania na dwa inne elementy.

Struktura drzewa umożliwia bardzo szybkie dotarcie do poszukiwanej
informacji.

Przykład kompletnego drzewa binarnego:

korze

zeł

ść

KOPIEC

Kopiec inaczej zwany stogiem jest szczególnym przypadkiem kompletnego
uporządkowanego drzewa binarnego, które spełnia tzw. warunek kopca, tzn.

każdy następnik jest niewiększy od swego poprzednika.

Z warunku tego

wynikają szczególne własności kopca:

•

w korzeniu kopca znajduje się największy element

•

na ścieżkach (połączeniach między węzłami), od korzenia do liścia,
elementy są posortowane nierosnąco (max-heap) lub niemalejąco (min-
heap)

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

•

drzewo jest kompletne - wypełniane od strony lewej do prawej i
kompletne na wszystkich poziomach, za wyjątkiem najniższego
poziomu, który może być napełniony od lewej strony, ale niedopełniony
od prawej strony,

•

tablica posortowana w porządku

nierosnącym

jest kopcem max-heap.

Przykładowy kopiec (max-heap):

korze

zeł

ść

Tablica[] = {16,12,8,8,10,4}

Szczególne własności kopców zostały wykorzystane do stworzenia algorytmu
sortowania zwanego HeapSort.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

BINARNE DRZEWO POSZUKIWAŃ – BST (Binary Search Tree)

Binarne drzewo poszukiwań jest drzewem, w którym elementy są
uporządkowane według określonego klucza, stanowiącego składnik danych
elementów drzewa. W binarnym drzewie poszukiwań wszystkie węzły lewego
poddrzewa są z wartością klucza mniejszą od danego węzła, a wszystkie węzły
prawego poddrzewa są z wartością klucza większą lub równą.

Wstawianie elementów do drzewa BST polega na odnalezieniu właściwej
pozycji dla nowego liścia. Począwszy o korzenia zmierzając w głąb drzewa, w
każdym kolejnym węźle podejmowana jest decyzja, w którą stronę należy się
kierować, w lewo lub prawo, aby znaleźć właściwą pozycję na dopięcie

nowego

liścia

w drzewie. Jeśli wartość klucza jest mniejsza od danego węzła obierany

jest kierunek na lewo, w przeciwnym razie kierunek na prawo. Operacja jest
powtarzana aż do osiągnięcia maksymalnej głębokości dla drogi pokonywanej
na podstawie kolejnych wyborów.

Kształt drzewa zależy od kolejności dodawania nowych elementów. Drzewo
może być zdegenerowane – jeśli będą dodawane dane posortowane, czyli w
określonym porządku względem uporządkowania drzewa to będą zawsze
dodawane tylko po lewej lub tylko po prawej stronie. Zmierza do konstrukcji
listy.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przykład procesu tworzenia drzewa BST:

Dołączanie: 3,2,5,4,6,1

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Podobnie odbywa się poszukiwanie węzła o określonej wartości klucza węzła w
drzewie.

Typowe są trzy metody przeszukiwania drzewa:

- pre-order (wzdłużne): korzeń, lewe poddrzewo, prawe poddrzewo,

- in-order (poprzeczne): lewe poddrzewo, korzeń, prawe poddrzewo,

- post-order (wsteczne): lewe poddrzewo, prawe poddrzewo, korzeń

Przeglądanie poziomami wymaga dodatkowych struktur danych, np. kolejki
Przedrostki pre-, in- oraz post- oznaczają kolejność przeglądania węzła
środkowego – korzenia, odpowiednio przed-, między- oraz po-.

Przeglądanie drzewa BST metodą in-order daje w rezultacie dane

posortowane

Inna metoda przeglądania:
- poziomami: pierwszy poziom (korzeń), drugi poziom, trzeci poziom itd.

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

przeglądanie: pre-order

przeglądanie: in-order

przeglądanie: post-order

przeglądanie: poziomami

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Elementarne operacje na drzewie:
- dodawanie nowych elementów do drzewa zgodnie z ustalonym porządkiem
- przeszukiwanie drzewa z celu odnalezienia węzłów zgodnych ze wzorcem
- określanie parametrów drzewa, np. liczba węzłów, liczba liści, wysokość
- zmiana wartości węzłów
- usuwanie wybranych węzłów
- kasowanie drzewa
- zapis i odczyt drzewa z pliku – metodą pre-order

Drzewo jako struktura dynamiczna musi posiadać węzły ze wskaźnikami na
swoich następników: lewy i prawy węzeł.

Przykład dynamicznego drzewa binarnego:

dane=

wskaźnik

dane=

NULL

wskaźnik

wskaźnik
na korzeń

NULL

NULL NULL

NULL

korzeń

wskaźnik

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przykład programu do obsługi drzewa BST:

(źródło: Krystyna Koleśnik, „Podstawy programowania strukturalnego w języku C++”)

Definicja węzła dynamicznego

typedef int TDaneW;
struct TWezel { //struktura wezla
int numer;
TDaneW danew; //dane w wezle
TWezel* lewy;
TWezel* prawy;
};

Dołączanie węzła dynamicznego do drzewa:
- szukana jest pozycja dla nowego liścia

typedef TWezel* wW; //wskaznik na wezel
void

Dolacz

(wW &wb,TDaneW dane, int (*

Relacja

)(TDaneW*,TDaneW*)) {

if(wb==NULL) { //znaleziona pozycja –

dołącz do wb

wb=new TWezel;

//nowy węzeł dynamiczny

wb->lewy=NULL;

//dla liścia

wb->prawy=NULL; //dla liścia
wb->danew=dane;

//zapis danych

lw++;

//bieżący licznik węzłów

cout<<"Dolaczony: "<<dane<<endl;
} else if (

Relacja

(&dane, &wb->danew)<0) {

cout<<wb->danew<<endl<<" /"<<endl<<"/"<<endl;

Dolacz

(wb->lewy,dane,

Relacja

); //

przejdź w lewo

}
else {
cout<<wb->danew<<endl<<"\\"<<endl<<" \\"<<endl;

Dolacz

(wb->prawy,dane,

Relacja

); //

przejdź w prawo

}
}
int

Warunek

(TDaneW* potomek, TDaneW* rodzic) { //warunek

//uporządkowania drzewa

if (*potomek < *rodzic) return (-1);
if (*potomek == *rodzic) return (0);
if (*potomek > *rodzic) return (1);
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Użycie

main(){
int i,j;
TDaneW klucz;
wW korzen=NULL
...
cin>>i;

Dolacz

(korzen,i,

Warunek

);

...

Dołączanie węzła dynamicznego do drzewa:

wW

Szukaj

(wW wb,TDaneW danep, int (*

Relacja

)(TDaneW*,TDaneW*)) {

int wynik; //wynik relacji
if(wb) {

//wb musi być różne od NULL

wynik=

Relacja

(&danep, &wb->danew);

if(wynik<0) //gdy wartość poszukiwana jest mniejsza od bieżącej
return

Szukaj

(wb->lewy,danep,

Relacja

);

//idź w lewo

else if (wynik>0) //gdy wartość poszukiwana jest większa od bieżącej
return

Szukaj

(wb->prawy,danep,

Relacja

); //idź w prawo

}
return wb; //gdy wb=NULL lub wartość poszukiwana jest równa bieżącej
}

Użycie

main(){
int i,j;
TDaneW klucz;
wW korzen=NULL

cout<<"Podaj poszukiwana liczbe calkowita: ";
cin>>klucz;
if(p=

Szukaj

(korzen,klucz,

Warunek

))

cout<<"Znaleziona wartosc klucza: "<<p->danew<<endl;
else cout<<"Nie znaleziono zadanej wartosci klucza: "<<endl;

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Przeglądanie drzewa różnymi metodami:

void Wyswietl(wW wezel) {
cout<<" klucz wezla numer "<<lw<<" wynosi: "<<wezel->danew<<endl;
}
void

PreOrder

(wW wb, //wskaznik biezacego wezla

int &poziom, //numer poziomu
void(*

Operacja

)(wW)){ //operacja wykonywana na wezle

if(wb) {
poziom++;
cout << "PreOrder - poziom wezla: "<<poziom;
lw=lw+1;
cout <<" numer wezla: "<<lw;

Operacja

(wb);

PreOrder

(wb->lewy,poziom,

Operacja

);

PreOrder

(wb->prawy,poziom,

Operacja

);

poziom--;
}
}
void

InOrder

(wW wb, //wskaznik biezacego wezla

int &poziom, //numer poziomu
void(*

Operacja

)(wW)){ //operacja wykonywana na wezle

if(wb) {
poziom++;

InOrder

(wb->lewy,poziom,

Operacja

);

cout << "InOrder - poziom wezla: "<<poziom;
lw=lw+1;
cout <<" numer wezla: "<<lw;

Operacja

(wb);

InOrder

(wb->prawy,poziom,

Operacja

);

poziom--;
}
}
void

PostOrder

(wW wb, //wskaznik biezacego wezla

int &poziom, //numer poziomu
void(*

Operacja

)(wW)){ //operacja wykonywana na wezle

if(wb) {
poziom++;

PostOrder

(wb->lewy,poziom,

Operacja

);

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

PostOrder

(wb->prawy,poziom,

Operacja

);

cout << "PostOrder - poziom wezla: "<<poziom;
lw=lw+1;
cout <<" numer wezla: "<<lw;

Operacja

(wb);

poziom--;
}
}

Użycie
int lw=0;

//zmienna globalna

main(){
int i,j;
TDaneW klucz;
wW korzen=NULL

lw=0;
int poziom=0;

PreOrder

(korzen,poziom,

Wyswietl

);

lw=0;
poziom=0;

InOrder

(korzen,poziom,

Wyswietl

);

lw=0;
poziom=0;

PostOrder

(korzen,poziom,

Wyswietl

);

Przeglądanie poziomami:

# include "kolejka.h"
void Inicjuj(wKolejka Kolejka)
{ Kolejka->Pocz=NULL;
Kolejka->Kon=NULL;
Kolejka->dl=0;
}

void NaPoczatku(wKolejka Kol, wEl Element)
{ Kol->dl++;
Element->nast=Kol->Pocz;
if (Kol->Pocz==NULL)
Kol->Kon=Element;

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

Kol->Pocz=Element;
}

void NaKoncu(wKolejka Kol, wEl Element)
{ Kol->dl++;
Element->nast=NULL;
if (Kol->Pocz==NULL)
Kol->Pocz=Element;
else
Kol->Kon->nast=Element;
Kol->Kon=Element;
}

wEl PobierzPierwszy(wKolejka Kol)
{ wEl E;
E=Kol->Pocz;
if (E!=NULL)
if (Kol->Pocz==Kol->Kon)
{ Kol->Pocz=NULL;
Kol->Kon=NULL;
}
else
Kol->Pocz=Kol->Pocz->nast;
Kol->dl--;
return E;
}

int Dlugosc(wKolejka Kol)
{ return Kol->dl;}

void DoKolejki(wKolejka Kolejka, void* wb)
{ wEl Element;
Element=new TElement;
Element->dane=wb;
NaKoncu(Kolejka,Element);
}

void* ZKolejki(wKolejka Kolejka)
{ wEl Element;
void* dane;
Element=PobierzPierwszy(Kolejka);
dane= Element->dane;
delete Element;
return dane;
}

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

void

Poziomami

(wW wb,

int &poziom,
void (*Operacja)(wW)) //
{ wKolejka Kolejka= new Naglowek;
Inicjuj(Kolejka);
if (wb){

DoKolejki

(Kolejka,wb);

while (Dlugosc(Kolejka)){
wb=(wW)

ZKolejki

(Kolejka);

lw++; //zlicza wezly
cout <<"Poziomami - numer kolejny wezla: "<<lw;

Operacja

(wb);

if (wb->lewy)

DoKolejki

(Kolejka,wb->lewy);

if (wb->prawy)

DoKolejki

(Kolejka,wb->prawy);

}

}
}

Użycie
int lw=0;

//zmienna globalna

main(){
int i,j;
TDaneW klucz;
wW korzen=NULL

lw=0;

Poziomami

(korzen,poziom,

Wyswietl

);

Zliczanie liści, węzłów i wysokości

int

LiczLiscie

(wW wb){ //tak jak post-order

if(wb)
if (wb->lewy==NULL && wb->prawy==NULL)
return 1;

WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1

(dr.inż Marcin Głowacki)

else
return

LiczLiscie

(wb->lewy) +

LiczLiscie

(wb->prawy);

else
return 0;
}
int

LiczWezly

(wW wb){ //tak jak post-order

if(wb)
return

LiczWezly

(wb->lewy) +

LiczWezly

(wb->prawy)+

;

else
return 0;
}
int

Wysokosc

(wW wb){

int wl,wp;
if(!wb) return 0;
wl =

Wysokosc

(wb->lewy);

wp =

Wysokosc

(wb->prawy);

if (wl>wp) return wl+1;
return wp+1;
}

Kasowanie drzewa

void

KasujDrzewo

(wW &wb) { //tak jak post-order - najpierw kasuje

potomków
//a potem rodzica.
if (wb) {

KasujDrzewo

(wb->lewy);

KasujDrzewo

(wb->prawy);

lw=lw+1;
delete (wb);
}
wb=NULL;
}

Wyszukiwarka

Podobne podstrony:
Informa cz4 v9 id 213363 Nieznany
Informa cz4 v3 id 213361 Nieznany
Informacje dla inwestora id 213 Nieznany
Informa wyklad petle id 716506 Nieznany
inform r1 rozw id 288565 Nieznany
Informa cz2 v3 id 213358 Nieznany
Informacja pod ochrona id 21351 Nieznany
informatyka model PP id 214055 Nieznany
informatyka pp arkusz1 id 21382 Nieznany
Informa cz2 v5 id 213359 Nieznany
Informa cz1 v5 id 213357 Nieznany
Informa cz3 v5 id 213360 Nieznany
Informacje dla inwestora id 213 Nieznany
INFORM EXCEL2007 2 id 716490 Nieznany
informacje uzupelniajace id 482 Nieznany

więcej podobnych podstron