WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
1
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)
1
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)
2
9.
T
ABLICE
T
EKSTOWE
Teksty przechowuje się w tablicach typu
char
Zapis:
- pojedyncze znaki w pojedynczych apostrofach:
‘
Z
’
- 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ŚĆ
M
A
R
C
I
N
\0
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
A
R
C
I
N
// 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)
3
O
PERACJE NA
T
EKSTACH
1.
- 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)
4
O
PERACJE NA
T
EKSTACH
2.
#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)
5
O
PERACJE NA
T
EKSTACH
3.
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)
6
10.
S
TRUKTURY
D
ANYCH
1
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
{
//
a
+
b
i
;
składowa rzeczywista
a
i urojona
b
int
a
,
b
;
//nie moŜna nadawać wartości domniemanych
};
zespol
x
={2,4},
y
;
y
.a=
x
.a+5;
y
.b=
x
.b+5;
Rezultat: y=7+9i
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
7
S
TRUKTURY
D
ANYCH
2
Przykład: Program liczy sumę liczb zespolonych
#include <iostream>
#include <cstdlib>
#include <iomanip>
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);
};
zespol
fnDodaj(
zespol
z1
,
zespol
z2
,
int fl_wysw
=
0
) {
zespol
suma;
suma.a=
z1.a
+
z2.a
;
suma.b=
z1.b
+
z2.b
;
if(fl_wysw) {
fnWyswietl(
z1
);cout<<" + ";fnWyswietl(
z2
);
cout<<" = ";fnWyswietl(suma);cout<<endl;
}
return suma;
}
int
main
(){
zespol
x
={2,3},
y
={4,5},
wynik
;
wynik=fnDodaj(
x,y
,1);
zespol
k
={4,3};
wynik
=fnDodaj(
wynik
,
k
,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)
8
U
NIA
1
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
c
;
//nie moŜna nadawać wartości domniemanych
int
i;
float
f;
};
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)
9
P
RZECIĄśANIE
O
PERATORÓW
1
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
@
to
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,
a
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)
10
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
,
b
; //a+bi; składowa rzeczywista a i urojona b
};
zespol
operator+
(
zespol
z1
,
zespol
z2
) {
zespol
suma={0,0};
suma.a=
z1.a
+
z2.a
;
suma.b=
z1.b
+
z2.b
;
return suma;
}
zespol
operator+=
(
zespol
&
z1
,
zespol
z2
) {
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)
11
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
@
to
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)
12
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)
13
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
,
zespol
z2
) {
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)
14
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)
15
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
,
b
; //a+bi; składowa rzeczywista a i urojona b
};
ostream
&
operator<<
(
ostream
& ekran,
zespol
&
z
) {
ekran <<
"("
<<
z.a
<<setiosflags(ios::showpos)<<
z.b
<<
"i)"
<<resetiosflags(ios::showpos);
return ekran;
};
////////////////////////////// MAIN ////////////////////////////////////
int
main
(){
zespol
x
={2,3},
y
={4,5},wynik;
cout<<"Liczba zespolona x = "<<
x
<<endl;
cout<<"Liczba zespolona y = "<<
y
<<endl;
system("PAUSE");
return 0;
}
Referencja uŜyta w argumencie dla wyświetlanych danych
zespol
&
z
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)
16
11.
Z
MIENNE
D
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)
17
D
YNAMICZNE
S
TRUKTURY
D
ANYCH
1
Do dynamicznych struktur danych zalicza się:
- stosy (sterty),
- kolejki,
- listy,
- drzewa binarne (w tym stogi),
D
YNAMICZNE
S
TRUKTURY
D
ANYCH
2
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)
18
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)
19
D
YNAMICZNE
S
TRUKTURY
D
ANYCH
3
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)
20
D
YNAMICZNE
S
TRUKTURY
D
ANYCH
4
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)
21
L
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
nastepny
NULL
wezel 1
wezel 2
wezel n
.........
dane
dane
dane
poprzedni
poprzedni
...
...
...
NULL
ostatni
Lista dwukierunkowa ze wskazaniem na dane:
pierwszy
nastepny
poprzedni
nastepny
nastepny
NULL
wezel 1
wezel 2
wezel n
.........
wsk_dane
wsk_dane
wsk_dane
poprzedni
poprzedni
ostatni
...
...
...
NULL
dane
dane
dane
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
22
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
nastepny
NULL
wezel 1
wezel 2
wezel n
.........
wsk_dane
wsk_dane
wsk_dane
poprzedni
poprzedni
ostatni
...
...
...
NULL
dane
dane
dane
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
23
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
wsk_dane
poprzedni
ostatni
NULL
dane
dane
pierwszy
nastepny
poprzedni
nastepny
nastepny
NULL
wezel 1
wezel 2
wezel 3
wsk_dane
wsk_dane
wsk_dane
poprzedni
poprzedni
ostatni
NULL
dane
dane
dane
pierwszy
nastepny
poprzedni
nastepny
NULL
wezel 2
wezel 1
wsk_dane
wsk_dane
poprzedni
ostatni
NULL
dane
dane
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
24
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
wsk_dane
poprzedni
ostatni
NULL
dane
dane
pierwszy
nastepny
poprzedni
nastepny
nastepny
NULL
wezel 1
wezel 2
wezel 3
wsk_dane
wsk_dane
wsk_dane
poprzedni
poprzedni
ostatni
NULL
dane
dane
dane
pierwszy
nastepny
poprzedni
nastepny
NULL
wezel 1
wezel 2
wsk_dane
wsk_dane
poprzedni
ostatni
NULL
dane
dane
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
25
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)
26
//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
if
(
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
if
(
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)
27
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;
if
(buf->poprzedni!=NULL)
buf->poprzedni->nastepny=buf->nastepny;
else
pierwszy=buf->nastepny;
if
(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)
28
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(
1
){
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 '
1
':
Dodaj
(
pierwszy
,
ostatni
); break;
case '
2
':
Znajdz
(
pierwszy
,
ostatni
); break;
case '
3
':
Drukuj
(
pierwszy
,
ostatni
); break;
case '
4
':
Usun
(
pierwszy
,
ostatni
); break;
case '
Q
':
case '
q
': 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)
29
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)
30
12.
O
PERACJE NA
P
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)
31
O
PERACJE NA
P
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
in
in
in
in
Otwarcie do czytania (domyślne dla
ifstream
)
out
out
out
out
Otwarcie do zapisu (domyślne dla
ofstream
)
app
app
app
app
Zawsze dopisuj na końcu pliku
ate
ate
ate
ate
Ustaw pozycje na koniec pliku ("at end")
trunc
trunc
trunc
trunc
Usuń poprzednią zawartość pliku
binary
binary
binary
binary
Nie konwertuj znaków specjalnych
Kombinacje FLAG
i ich znaczenie:
Flagi
Znaczenie
CMode
in
in
in
in
Czyta (plik teŜ musi istnieć)
"r"
out
out
out
out
Czyści zawartość i zapisuje (tworzy jeśli trzeba)
"w"
out | trunc
out | trunc
out | trunc
out | trunc
Czyści zawartość i zapisuje (tworzy jeśli trzeba)
"w"
out | app
out | app
out | app
out | app
Dołącza na końcu (tworzy jeśli trzeba)
"a"
in | out
in | out
in | out
in | out
Czyta i zapisuje; pozycja na początku pliku (plik musi istnieć)
"r+"
in | out | trunc
in | out | trunc
in | out | trunc
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)
32
O
PERACJE NA
P
LIKACH
Przykład:
ifstream
plik_in
(“
filename
”,
in
|
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)
33
O
PERACJE NA
P
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)
34
O
PERACJE NA
P
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)
35
return 0;
}
O
PERACJE NA
P
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
Plik
Plik
Plik
.open
.open
.open
.open
(
nazwa
)
Otwiera plik jako strumień i uŜywa domyślnego trybu
plik
plik
plik
plik
.open
.open
.open
.open
(
nazwa, flagi
)
Otwiera plik jako strumień i uŜywa flag do określenia trybu
plik
plik
plik
plik
.close
.close
.close
.close
()
Zamyka plik
plik
plik
plik
plik
.is_open
.is_open
.is_open
.is_open
()
Zwraca wynik czy plik jest otwarty
plik.
plik.
plik.
plik.
clear
clear
clear
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
c
;
while (
plik
.
get
(
c
)) {
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)
36
return 0;
}
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
37
O
PERACJE NA
P
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
beg
beg
beg
Pozycja jest podana w odniesieniu do początku pliku ("beginning")
cur
cur
cur
cur
Pozycja jest podana w odniesieniu do aktualnej pozycji ("current")
end
end
end
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)
38
O
PERACJE NA
P
LIKACH
W
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
(
0
);
// 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)
39
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)
40
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)
41
W
SKAŹNIKI DO
F
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)
42
W
SKAŹNIKI DO
F
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
[
3
])()={
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)
43
13.
D
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)
44
Przykład drzewa stopnia 3
głębokość/wysokość
1/5
2/2
2/5
3/1
3/1
3/1
3/3
4/1
4/2
5/1
5/1
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
45
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:
15
20
17
24
10
3
8
korze
ń
w
ę
zeł
w
ę
zeł
li
ść
li
ść
li
ść
li
ść
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)
46
•
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):
16
8
4
10
8
12
korze
ń
w
ę
zeł
w
ę
zeł
li
ść
li
ść
li
ść
Tablica[] = {16,12,8,8,10,4}
1.
2.
3.
4.
5.
6.
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)
47
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)
48
Przykład procesu tworzenia drzewa BST:
3
3
2
3
2
5
3
2
5
4
3
2
5
4
6
3
2
5
1
4
6
Dołączanie: 3,2,5,4,6,1
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
49
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)
50
3
2
5
1
4
6
3
2
5
1
4
6
3
2
5
1
4
6
3
2
5
1
4
6
przeglądanie: pre-order
przeglądanie: in-order
przeglądanie: post-order
przeglądanie: poziomami
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
5
4
6
1
2
3
4
5
6
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
51
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=
L
P
3
dane=
L
P
2
dane=
L
P
1
dane=
L
P
5
wskaźnik
wskaźnik
dane=
L
P
4
dane=
L
P
6
NULL
wskaźnik
wskaźnik
wskaźnik
wskaźnik
wskaźnik
na korzeń
NULL
NULL NULL
NULL NULL
NULL
korzeń
wskaźnik
wskaźnik
wskaźnik
wskaźnik
wskaźnik
WYKŁADY cz.4 v.6 (2011) Podstawy programowania 1
(dr.inŜ Marcin Głowacki)
52
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)
53
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)
54
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)
55
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)
56
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)
57
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)
58
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)+
1
;
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;
}