Struktury
" tablica  przykład obiektu grupującego wiele
obiektów składowych pod jedną nazwą;
ograniczenie  wszystkie składowe tego samego
typu
" potrzeba struktury danych grupującej zmienne
ró\
nego typu (np. dane opisujące pracownika)
" struktura  obiekt zło\
ony z jednej lub kilku
zmiennych (dopuszczalnie ró\
nych typów)
zgromadzonych razem i występujących pod
wspólną nazwą
" formy definicji struktur
o struct {
char imie[24];
char nazwisko[32];
int rok;
} o1,o2;
- definiuje dwa  egzemplarze struktury. Gdy chcemy
zdefiniować trzeci  musimy powtórzyć całą definicję
o struct osoba {
char imie[24];
char nazwisko[32];
int rok;
} o1,o2;
- zawiera nazwę struktury (etykietę)  pozwala to na
definicję dodatkowych  egzemplarzy
struct osoba o3, o4;
o typedef struct osoba {
char imie[24];
char nazwisko[32];
int rok;
} OSOBA;
OSOBA o1,o2,o3,o4;
przez typedef definiujemy typ OSOBA, który potem
wykorzystujemy do definicji kolejnych  wcieleń struktury
" inicjalizacja struktury  mo\
liwa w trakcie definicji
OSOBA o1={ James , Bond ,1965);
" odwołanie do poszczególnych składowych (pól)
struktury  u\
ycie operatora  . składowej struktury
o1.imie /* odwołanie do pola imie */
o1.nazwisko /* odwołanie do pola nazwisko */
o1.rok /* odwołanie do pola rok */
nazwa pola jest nazwą lokalną widoczną tylko wewnątrz
struktury
" dozwolone operacje na strukturach
o przypisanie jej innej struktury jako całości
o kopiowanie jej w całości na inną strukturę (w tym 
przesyłanie argumentów funkcjom i zwracanie przez
funkcje wartości)
o inicjalizacja w trakcie definicji
o pobieranie adresu struktury przez operator &
o odwołanie się do składowych struktury
" niedozwolone jest porównywanie struktur
Przykład  ilustracja u\
ycia struktur:
#include
#include
#include
using namespace std;
typedef struct {
char imie[24];
char nazwisko[32];
int rok;
} OSOBA;
OSOBA utworz(char *imie, char *nazwisko, int rok)
{
OSOBA temp;
strcpy(temp.imie,imie);
strcpy(temp.nazwisko,nazwisko);
temp.rok=rok;
return temp;
}
void wypisz(OSOBA kto)
{
cout << "Imie : " << kto.imie << endl;
cout << "Nazwisko : " << kto.nazwisko << endl;
cout << "Rok urodz.: " << kto.rok << endl;
}
main()
{
OSOBA o1={"Jan","Nowak",1983}; /* inicjalizacja */
OSOBA o2;
wypisz(o1);
o2=o1; /* przypisanie struktury */
/* porownanie struktur - nielegalne
if (o1==o2) cout << "Struktury identyczne\n");
*/
wypisz(o2);
wypisz(utworz("John","Lennon",1940));
}
Imie : Jan
Nazwisko : Nowak
Rok urodz.: 1983
Imie : John
Nazwisko : Lennon
Rok urodz.: 1940
" zagnie\
d\
anie struktur  wcześniej zdefiniowane struktury
mogą być u\
yte do definicji nowych
struct punkt {
int x;
int y;
}
struct prosto {
struct punkt p1;
struct punkt p2;
}
struct punkt d,g;
struct prosto ekran;
odwołanie do pól takiej struktury:
ekran.p1 /* dolny lewy punkt ekranu */
ekran.p1.x /* współrzędna x dolnego lewego punktu
ekranu */
" struktury jako argumenty funkcji
o struktury mogą być argumentami funkcji oraz mogą być
zwracane przez funkcje
o są przekazywane do funkcji poprzez wartość (jak
wszystkie inne zmienne)  na stosie tworzona jest kopia
struktury, którą funkcja manipuluje bez zmiany oryginału
#include
using namespace std;
struct punkt {
int x;
int y;
};
struct prosto {
struct punkt p1;
struct punkt p2;
};
struct punkt rob_punkt(int x, int y)
{
struct punkt temp;
temp.x=x;
temp.y=y;
return temp;
};
struct prosto rob_prosto(struct punkt p1, struct punkt p2)
{
struct prosto temp;
temp.p1=p1;
temp.p2=p2;
return temp;
};
void wypisz_rozmiar(struct prosto pp)
{
cout << "Ekran ma rozmiary: " << pp.p2.x-pp.p1.x <<  na 
<< pp.p2.y-pp.p1.y << pikseli.\n",
}
struct punkt dodaj_punkty(struct punkt p1, struct punkt p2)
{
p1.x += p2.x;
p1.y += p2.y;
return p1;
}
main()
{
struct punkt d, m, g;
struct prosto ekran;
d=rob_punkt(10,10);
m=rob_punkt(320,200);
g=dodaj_punkty(d,m);
printf("Punkt d: (%3d, %3d)\n",d.x,d.y);
printf("Punkt m: (%3d, %3d)\n",m.x,m.y);
printf("Punkt g: (%3d, %3d)\n",g.x,g.y);
ekran=rob_prosto(d,g);
wypisz_rozmiar(ekran);
}
Punkt d: ( 10, 10)
Punkt m: (320, 200)
Punkt g: (330, 310)
Ekran ma rozmiary: 320 na 200 pikseli.
Wskaz
niki do struktur
" przekazywanie do funkcji du\
ej struktury nieefektywne 
zamiast tego mo\
emy u\
yć wskaz
nika
" definicja wskaz
nika  analogicznie jak dla innych typów
OSOBA ktos = {  John ,  Lennon , 1940};
OSOBA *po;
po = &ktos;
cout <<  ktos.imie  << ktos.nazwisko << ktos.rok);
%s, urodzony: %d\n , ktos.imie,
ktos.nazwisko,ktos.rok);
cout << (*po).imie %s, (*po).nazwisko urodzony: %d\n ,
(*po).imie, (*po).nazwisko,(*po).rok);
" udostępnienie składowej struktury wskazywanej przez
wskaz
nik  zamiast:
(*wskaz
nik).pole
mo\
emy napisać:
wskaz
nik->pole
printf( %s %s, urodzony: %d\n , po->imie,
po->nazwisko,po->rok);
" operatory  . oraz  ->  najwy\
szy priorytet (równy (), [])
struct {
int len;
char *str;
} *p
++p-> len a" ++(p->len)  zwiększa zmienną len
(++p)->len - zwiększa p przed odwołaniem do len
p++->len a" (p++)->len - zwiększa p po odwołaniu do len
*p->str - udostępnia coś, na co wskazuje str
*p->len - błąd !!! (p->len nie jest wskaz
nikiem)
Tablice struktur
" struktury i wskaz
niki do nich mo\
na gromadzić w tablicach:
OSOBA t[10], *s[10];
t  tablica 10 elementów, z których ka\
dy to struktura typu
OSOBA
t[0] - struktura typu OSOBA o indeksie 0
t[0].rok - składnik rok struktury typu OSOBA o indeksie 0,
zmienna typu int
t[0].imie[0] - pierwszy znak składnika imie struktury OSOBA o
indeksie 0; zmienna typu char
s  tablica wskaz
ników do struktur typu OSOBA
s[0] - zerowy element tablicy typu OSOBA* (adres)
*s[0].rok - błędny zapis (s[0].rok to nie jest wskaz
nik)
(*s[0]).imie[1]  drugi znak składnika imie struktury
wskazywanej przez s[0]
s[0]->imie[1] - inny zapis tego, co wy\
ej
Struktury odwołujące się do samych siebie
" są to struktury, które w swojej definicji zawierają odwołanie
(wskaz
nik) do innej struktury tego samego typu
" przy pomocy takich struktur mo\
na zaimplementować
struktury dynamiczne, takie jak: listy jednokierunkowe, listy
dwukierunkowe, drzewa binarne itp.
" struktury takie są szczególnie u\
yteczne do obsługi ciągu
zmiennej liczby obiektów opisywanych strukturami
Przykład  struktura do tworzenia listy jednokierunkowej:
typedef struct pers {
char *imie;
char *nazwisko;
int rok;
pers *nast;
} OSOBA;
Obsługa plików
" do tej pory korzystaliśmy tylko ze standardowego
wejścia i wyjścia (C++ : cin, cout, operatory <<, >>)
" inna mo\
liwość  korzystanie z plików zewnętrznych
" wymagania:
o konieczność powiązanie pliku (elementu systemu
plików systemu operacyjnego) z obiektem języka
(otwarcie pliku)
o u\
ywanie właściwych funkcji bibliotecznych do
transferu danych
Rozwiązanie w C:
" plik  opisany przez strukturę typu FILE zdefiniowaną
w bibliotece stdio  konieczność włączenie nagłówka
cstdio
" egzemplarz tej struktury zawiera dane potrzebne do
obsługi pliku (bufor wymiany danych, dane adresowe,
informacja o błędach itp.)
" znajomość tej struktury niekonieczna  wystarczy
mieć wskaz
nik do tej struktury i u\
ywać właściwych
funkcji bibliotecznych
" uzyskanie powiązania między plikiem (z systemu
plików OS) a wskaz
nikiem do FILE  otwarcie pliku 
odpowiada za to funkcja fopen
" składnia fopen:
fp = fopen( nazwa_pliku ,  typ_dost );
fp  wskaz
nik do FILE
typ_dost : r  otwiera plik do czytania
w  otwiera plik do pisania; kasuje poprzednią wersję (jeśli
istnieje)
a  otwiera plik do dopisywania
gdy plik binarny  dodatkowo  b , np.:
FILE *fp;
fp=fopen(  aaa , rb ); //otwarcie pliku binarnego aaa do czytania
" zwykle środowisko systemu operacyjnego jest
odpowiedzialne za otwarcie 3 plików standardowych
i udostępnienie programowi ich wskaz
ników; ich
standardowe nazwy to stdin (klawiatura), stdout
i stderr (ekran)
" inne funkcje działające na plikach:
fclose(FILE *fp);
fprintf(FILE *fp, format, ...);
fscanf(FILE *fp, format, ...);
int getc(FILE *fp);
int putc(int c, FILE *fp);
Przykłady:
// Obsługa plików w C  funkcje fopen, fclose, fprintf
#include
#define T_DOL 0
#define T_GORA 150
#define T_KROK 5
int main()
{
FILE *fp;
if ((fp=fopen("zestaw","wb"))==NULL)
{
printf("Nie moge otworzyc pliku zestaw\n");
return 1;
}
fprintf(fp," T[F] T[C]\n");
fprintf(fp,"----------------\n");
for (int fahr=T_DOL; fahr <=T_GORA; fahr=fahr+T_KROK)
fprintf(fp,"%6.1f %6.1f\n",fahr, 5*(fahr-32.0)/9);
fclose(fp);
return 0;
}
// Obsługa plików w C - prosty program kopiujacy pliki
#include
int main(int ac, char * av[ ])
{
FILE *fs, *fd;
int c;
if (ac!=3)
{
printf("uzycie: kopiuj nazwa_orygial nazwa_kopia");
return 1;
}
if ((fs=fopen(av[1],"rb"))==NULL)
{
printf("Nie moge otworzyc pliku %s\n",av[1]);
return 1;
}
if ((fd=fopen(av[2],"wb"))==NULL)
{
printf("Nie moge otworzyc pliku %s\n",av[2]);
return 1;
}
while ((c=getc(fs))!=EOF) putc(c,fd);
fclose(fs);
fclose(fd);
}
" stała EOF  zwracana, gdy osiągnięty jest koniec
pliku
" zmienna c typu int, by móc przenieść normalne znaki
oraz EOF
" limit na liczbę jednocześnie otwartych plików 
konieczność zamykania nieu\
ywanych plików
Rozwiązanie w C++:
" pliki  reprezentowane przez obiekty specjalnego typu
(klasy) zdefiniowanej w bibliotece standardowej
" pełną realizację operacji I/O zapewnia system
powiązanych (przez dziedziczenie) klas 
konieczność włączenia bibliotek iostream, fstream
" w C++ - wpływająca i wypływająca informacja
srumień bajtów; by zrealizować I/O musimy:
o zdefiniować w pamięci  centrum zarządzania
strumieniem (definicja egzemplarza klasy)
o powiązać go z fizycznym plikiem (metoda open()
lub konstruktor)
o u\
yć właściwych funkcji (metod klasy fstream)
o zlikwidować niepotrzebny strumień metoda close()
" stała EOF  zwracana, gdy osiągnięty jest koniec
pliku
" błędy powstałe w czasie pracy strumieni  ustawiają
flagi bitowe w słowie iostate w klasie ios_base;
wykrycie błędu ułatwia operator konwersji na bool
// Obsługa plików w C++  funkcje fopen, fclose, fprintf
/* Pisanie do pliku  funkcje open, close, operator << */
#include
#include
#include
using namespace std;
const int T_DOL=0, T_GORA=150, T_KROK=5;
int main()
{
ofstream fp;
fp.open("zestaw.dat");
if (!fp)
{
printf("Nie moge otworzyc pliku zestaw.dat\n");
return 1;
}
fp<<" T[F] T[C]\n";
fp<<"----------------\n";
for (int fahr=T_DOL; fahr <=T_GORA; fahr=fahr+T_KROK)
fp< << setprecision(1) << 5*(fahr-32.0)/9 << endl;
fp.close();
return 0;
}
" zwykle do reprezentowania plików dyskowych
u\
ywamy obiektów typu ofstream (zapis do pliku) lub
ifstream (czytanie z plików)
" metoda open() mo\
e mieć drugi argument określający
tryb pracy z danym plikiem; wartości domyślne tego
parametru to: ios_base::in dla klasy ifstream,
ios_base::out dla klasy ofstream
// Obsługa plików w C++ - prosty program kopiujacy pliki
#include
#include
#include
using namespace std;
int main(int ac, char * av[ ])
{
if (ac!=3)
{
printf("uzycie: kopiuj nazwa_orygial nazwa_kopia");
return 1;
}
ifstream fs(av[1],ios::in|ios::binary);
if (!fs)
{
printf("Nie moge otworzyc pliku %s\n",av[1]);
return 1;
}
ofstream fd(av[2],ios::out|ios::binary);
if (!fd)
{
printf("Nie moge otworzyc pliku %s\n",av[2]);
return 1;
}
int c;
while ((c=fs.get())!=EOF) fd.put(c);
if (!fs.eof()||!fd)
{
cout << "Jakis dziwny blad !!!\n";
return(1);
}
fs.close(); fd.close();
}
Struktury odwołujące się do samych siebie  przykłady
" najprostszy przykład  lista jednokierunkowa
" realizuje liniowe uporządkowanie
" lista określona poprzez:
o nagłówek listy (wskaz
nik do struktury składowej
listy) i system wskaz
ników pokazujących na kolejny
element
" operacje podstawowe:
o wstawianie elementu do listy
o usuwanie elementu z listy
o przeglądanie listy
#include
#include
#include
using namespace std;
#define MAX_BUFOR 40
typedef struct pers {
char *imie;
char *nazwisko;
int rok;
struct pers *nast;
} OSOBA;
OSOBA *S; //nagłówek listy
void lista1(FILE *fp) //tworzenie listy  dodawanie do początku
{
char b1[MAX_BUFOR],b2[MAX_BUFOR];
unsigned len;
OSOBA *B; //egzemplarz aktualnie dodawany
int rok;
S=(OSOBA*)NULL; //wstępne ustawienie nagłowka listy
while (fscanf(fp,"%s %s %d",b1,b2,&rok)!=EOF)
{
B=new OSOBA;
B->nast=S;
S=B;
len=(unsigned)strlen(b1);
 B->imie=new char[len+1];
strcpy(B->imie,b1);
len=(unsigned)strlen(b2);
B->nazwisko=new char[len+1];
strcpy(B->nazwisko,b2);
B->rok=rok;
}
}
void lista(FILE *fp) //tworzenie listy  dodawanie do konca
{
char b1[MAX_BUFOR],b2[MAX_BUFOR];
unsigned len;
OSOBA *B,*P; //B  aktualnie dodawany, P  dodany poprzednio
int rok;
S=(OSOBA*)NULL;
while (fscanf(fp,"%s %s %d",b1,b2,&rok)!=EOF)
{
B= new OSOBA;
if (S==(OSOBA*)NULL) S=B;
else P->nast=B;
B->nast=(OSOBA*)NULL;
len=(unsigned)strlen(b1);
B->imie= new char[len+1];
strcpy(B->imie,b1);
len=(unsigned)strlen(b2);
B->nazwisko=new char[len+1];
strcpy(B->nazwisko,b2);
B->rok=rok;
P=B;
}
}
void drukuj_lista()
{
OSOBA *B;
B=S;
do
printf("%s %s %d \n",B->nazwisko,B->imie,B->rok);
while (B=B->nast);
}
OSOBA *najstarsza()
{
OSOBA *w, *x;
int min;
min=S->rok;
x=S;
for (w=S; w!=(OSOBA*)NULL; w=w->nast)
if (w->rok {
min=w->rok;
x=w;
}
return x;
}
main()
{
FILE *fp;
OSOBA *stara;
fp=fopen("dane","rb");
lista(fp);
fclose(fp);
drukuj_lista();
stara=najstarsza();
printf("\nNajstarsza: %s %s, %d\n",stara->imie,stara->nazwisko,
stara->rok);
system("PAUSE");
}
Drzewa
" podstawowa dynamiczna struktura danych; opisuje
hierarchiczny układ danych
" elementy struktury drzewa:
o wyró\
niony element  korzeń
o węzły: wewnętrzne, zewnętrzne (liście)
o relacje pomiędzy węzłami: przodek, potomek
" często stosowane drzewa: drzewa binarne (o stopniu 2)
" szczególne przypadki drzew binarnych:
o binarne drzewa poszukiwań (BST): x  węzeł, je\
eli y nale\
y
do lewego poddrzewa x, to klucz[y] d" klucz[x]; gdy y nale\
y do
prawego poddrzewa x, to klucz[x] d" klucz[y]
o kopiec (stóg)  binarne drzewo wypełnione na wszystkich
poziomach ewentualnie z wyjątkiem ostatniego (który jest
wypełniony od lewej do prawej), w ka\
dym węz
le jest
spełniona relacja kopca: klucz[potomka] d" klucz[rodzica]
(stąd: korzeń kopca zawiera element o maksymalnym kluczu)
" realizacja drzew  najczęściej: dynamiczne struktury
wskaz
nikowe; niekiedy: tablice (np. dla kopców)
" przykład u\
yteczności drzew  sortowania drzewiaste
o przekształć listę wejściową w binarne drzewo
poszukiwań
o obejdz
drzewo w kolejności  najpierw w lewo ; wypisz
elementy danych przy ich powtórnym odwiedzeniu
Zło\
oność  O(N2); powód  pewne sekwencje danych
prowadzą do wąskich i długich drzew  ich konstrukcja
to proces o zło\
oności O(N2)
Przykład: sekwencja: 28, 1018, 402, 396, 35, 46, 354, 76,
128,112, 106, 100
procedura obejdz(T)
if T puste then return
else
begin
obejdz(L(T))
wypisz element w korzeniu T
obejdz(P(T))
return
end
Drzewa  przykład: sortowanie drzewiaste
#include
#include
using namespace std;
typedef struct node {
int k;
struct node *lewy;
struct node *prawy;
} NODE;
NODE *Root; //korzen drzewa
void dodaj(int k)
{
NODE *x,*y,*c;
c=new NODE;
c->k=k;
c->lewy=(NODE*) NULL;
c->prawy=(NODE*) NULL;
y=(NODE*) NULL;
x=Root;
while(x)
{
y=x;
if(kk) x=x->lewy;
else x=x->prawy;
}
if(!y)
Root=c;
else
{
if(kk) y->lewy=c;
else y->prawy=c;
}
}
void obejdz(NODE *TREE)
{
if (!TREE) return;
obejdz(TREE->lewy);
cout << TREE->k<< endl;
obejdz(TREE->prawy);
}
main()
{
int nr;
Root=(NODE*) NULL;
for(int i=0; i< 10; i++)
{
cout << "Podaj kolejna liczbe: ";
cin >> nr;
dodaj(nr);
}
obejdz(Root);
system("PAUSE");
}
Unie
" typ zmiennej, która pozwala na wykorzystanie tego
samego miejsca w pamięci (w ró\
nym czasie) do
zapisania wartości ró\
nych typów
o mamy zapisać dwie tablice:
int a[30];
char b[100];
których znajomość nie będzie nigdy potrzebna
jednocześnie
o definiujemy unię:
union tablice {
int a[30];
char b[100];
} x;
o unia x zajmuje w pamięci tyle co dłu\
sza z tablic a i b (czyli
4*30 = 120 bajtów)
o tablice a i b zaczynają się od tego samego adresu (zajmują
ten sam obszar pamięci)
o do x będziemy mogli wstawiać liczby całkowite lub teksty
(ale nie jednocześnie  więc albo jeden albo drugi typ)
o za kontrolę tego, jaki typ znajduje się aktualnie w unii
odpowiada programista
o odwołanie do składowych  jak dla struktur:
union tablice x;
union tablice *p;
x.a[5]; /* nazwa_unii.składowa */
p->a[5]; /* wskaz
nik_unii->składowa */
" unie mogą wystąpić w strukturach i tablicach (i na odwrót)
Przykład:
#define NSYMB 100
struct { /* symbol */
char *nazwa; /* nazwa symbolu */
int flaga; /* znacznik stanu */
int utype; /* typ wartości */
union { /* wartości symbolu */
int ival;
float fval;
char *sval;
} u;
} tab_symb[NSYMB];
" odwołanie do składowej ival k-tego symbolu:
tab_symb[k].u.ival
" odwołanie do pierwszego znaku tekstu wskazywanego przez sval:
*tab_symb[k].sval
lub
tab_symb[k].u.sval[0]
Pole bitowe
" stosowane w sytuacji gdy chcemy zapakować kilka
danych bitowych (typu: tak  nie) w pojedynczym
obiekcie typu całkowitego
Przykład: tablica symboli omawiana wy\
ej, potrzebne
określenie, czy symbol jest
" słowem kluczowym
" obiektem zewnętrznym,
" obiektem statycznym
Mo\
liwe reprezentacje:
" przez maskowania:
#define KEYWORD 01 /* słowo kluczowe */
#define EXTERNAL 02 /* obiekt zewnętrzny */
#define STATIC 04 /* obiekt statyczny */
unsigned int flags;
flags |=EXTERNAL|STATIC; /* ustawia bity EXERNAL i
STATIC */
flags &= ~(EXTERNAL | STATIC); /* kasuje te bity */
" przez pola bitowe
struct {
unsigned int is_keyword : 1;
unsigned int is_extern : 1;
unsigned int is_static : 1;
} flags;
definiuje flags jako zmienną zawierającą trzy jednobitowe pola
(liczba po dwukropku  rozmiar pola)
" ustawienie pól:
flags.is_extern=flags.is_static=1;
" kasowanie pól:
flags.is_extern=flags.is_static=0;
" zale\
ność od implementacji (umieszczenie pól w słowie 
od lewej do prawej czy na odwrót; mo\
liwość
przekraczania słów)
" deklarujemy jako int (signed lub unsigned)
" pola bitowe nie są tablicami, nie mają adresów (nie mo\
na
stosować operatora &), nie na wskaz
ników do pól
bitowych)