WYKA
AD 10
Zmienne o złożonej budowie
Statyczne i dynamiczne struktury danych:
lista, kolejka, stos, drzewo
Programy: c5_1.c, c5_2, c5_3, c5_4, c5_5
Tomasz Zieliński
ZMIENNE O ZA
OŻONEJ BUDOWIE (1)
Zmienne typu prostego:
char, short, int, long, float, double
(unsigned) char, short, int, long
Przykład:
char c, s[10];
int i, j, k, l, m[3][3], n[5][5][5];
float x, y, z
c = getchar();
strcpy(s,  Kowalski );
i = 10; j = 20;
k = i+j; l = i*j;
m[0][1] = 1;
n[0][1][2] = m[1][2] + 128;
ZMIENNE O ZA
OŻONEJ BUDOWIE (2)
Zmienne typu złożonego (struktury)
Przykład:
struct osoba { <--------------- typ zmiennych osoba
char nazwisko[20];
char imie[10];
int wiek;
int wzrost;
} student; <--------------- delaracja zmiennej student typu osoba
strcpy( student.nazwisko,  Kowalski ); // inicjalizacja zmiennej
strcpy( student.imię,  Jan ); //
student.wiek = 23; //
student.wzrost = 187; //
struct osoba pacjent, student = { Kowalski ,  Jan , 23, 187};
ZMIENNE O ZA
OŻONEJ BUDOWIE (3)
Przykład:
struct osoba { <---------- typ zmiennych osoba
char nazwisko[20];
char imie[10];
int wiek;
int wzrost;
} *pstudent; <--------- delaracja wskaz
nika do zmiennej student
ZASADA ZAPISU: *xxx.yyy = xxx->yyy
strcpy( pstudent->nazwisko,  Kowalski ); // inicjalizacja zmiennej
strcpy( pstudent->imię,  Jan ); // inicjalizacja zmiennej
pstudent->wiek = 23;
pstudent->wzrost = 187;
struct osoba *ppacjent, *pstudent = { Kowalski ,  Jan , 23, 187};
STRUKTURY DANYCH (1) - statyczne i dynamiczne
Lista: użytkowników komputera, uczestników wycieczki,
studentów, pacjentów, ...
Kolejka: dokumentów czekających na wydrukowanie przez
drukarkę sieciową
Stos: danych o przerwanych (zawieszonych) programach,
czekających na wykonanie przez procesor
Drzewo: katalogów zbiorów na dysku komputera
Statycznie: tablica, składająca się z wielu elementów jednego
typu, często nie w pełni wypełniona, czasami
przepełniona
Dynamicznie: łańcuch węzłów (bloków komórek w pamięci), które na
siebie pokazują
STRUKTURY DANYCH (2) - statyczne i dynamiczne
Kolejka statycznie Kolejka dynamicznie
wezeł nr 1 wezeł nr 2 wezeł nr 3
komórki komórki komórki
A B C D E
pamięci pamięci pamięci
początek koniec
A adr B adr C adr
I J K L G H
F
koniec
początek
koniec początek adres pierwszego adres ostatniego
węzła węzła
| struct kolejka {
struct kolejka { | int początek;
int początek; | int koniec;
int koniec; | }
struct osoba tablica[ MAX ]; | struct węzeł {
} | struct osoba student;
| struct węzeł *następny;
| }
DYNAMICZNE STRUKTURY DANYCH (1)
Węzły
=====================================================
struct węzeł1 { struct węzeł2 {
struct element info; struct element info;
struct węzeł1 *następny; struct węzeł2 *poprzedni;
}; struct węzeł2 *następny;
};
=====================================================
Przykład:
struct element { // w każdym węz
le jest umieszczona
int liczba; // jedna liczba, np. 220
char litera; // i jedna litera, np. V (voltów)
};
Dynamiczna alokacja pamięci dla węzła i jej zwalnianie:
pwęzeł = (struct węzeł *) malloc( sizeof( struct węzeł ) );
free( pwęzeł );
DYNAMICZNE STRUKTURY DANYCH (2)
Lista jednostronna
info A adr info B adr info X adr info Y
początek
info A adr info B adr info X adr info Y
DODAWANIE
info C adr
początek
info A adr info B adr info X adr info Y
USUWANIE
początek
DYNAMICZNE STRUKTURY DANYCH (3)
Lista dwustronna
info A adr adr info X adr adr info Y
adr info B adr
wskaz
nik
adr info A adr adr info X adr adr info Y adr
adr info B adr
wskaz
nik
info B adr adr info X adr
info A adr
adr info B adr adr info X adr
adr info C adr
DODAWANIE USUWANIE
DYNAMICZNE STRUKTURY DANYCH (4)
Kolejka FIFO (First In First Out) w statycznym buforze kołowym
A B C D E
początek koniec
A B C D E F
początek
koniec
A B C D E F
początek koniec
I J K L G H
F
koniec początek
DYNAMICZNE STRUKTURY DANYCH (5)
Kolejka FIFO (First In First Out) dynamicznie
A adr B adr C adr
początek koniec
A adr B adr C adr D adr
początek koniec
A adr B adr C adr D adr
początek koniec
DYNAMICZNE STRUKTURY DANYCH (6)
STOS statycznie i dynamicznie
Statyczna tablica Dynamiczna struktura
C adr B adr A adr
A B C D E
ostatni
ostatni
D adr C adr B adr A adr
A B C D E F
ostatni
ostatni
A B C D
D adr C adr B adr A adr
ostatni
ostatni
DYNAMICZNE STRUKTURY DANYCH (7) - drzewo binarne
A 14
adr L adr P
B 9 C 21
adr L adr L adr P
E 16
D 5 F 30
adr L adr P
adr P
G 6 H 15 I 20
WYPISYWANIE ELEMENTÓW: 5, 6, 9, 14, 15, 16, 20, 21, 30
IN-ORDER lewo, wypisz, prawo D, G, B, A, H, E, I, C, F
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PRE-ORDER wypisz, lewo, prawo A, B, D, G, C, E, H, I, F
POST-ORDER lewo, prawo, wypisz G, D, B, H, I, E, F, C, A
DYNAMICZNE STRUKTURY DANYCH (8) - drzewo binarne
Poprzednia strona:
struct węzeł { struct element {
struct element info; np. ------> char litera;
struct węzeł *lewy; int liczba;
struct węzeł *prawy; }
};
Przykład:
+
A + (B - C) * (D + E)
A *
- +
B C D E
/* Przyklad 5.5 - DRZEWO BINARNE - jako struktura dynamiczna */
/* wprowadzaj liczby naturalne z klawiatury */
/* znajdz szybko pierwsze powtorzenie */
/* wydrukuj od najmniejszej do najwiekszej */
#include
#include
#include
struct wezel { /* struktura wezla */
int info;
struct wezel *lewy;
struct wezel *prawy;
};
typedef struct wezel *ADRwezel; /* deklaracja adresu do wezla */
ADRwezel PobierzWezel( void ); /* pobranie wolnego wezla */
ADRwezel NowaGałąz
( int x ); /* wygeneruj kolejna galaz */
void PoLewej( ADRwezel p, int x); /* wstaw liczbe x do lewej galezi */
void PoPrawej( ADRwezel p, int x); /* wstaw liczbe x do prawej galezi */
void Preorder( ADRwezel p ); /* kolejnosc 1 */
void Inorder( ADRwezel p ); /* kolejnosc 2 */
void Postorder( ADRwezel p ); /* kolejnosc 3 */
/* program glowny ---------------------------------------------------------------------- */
void main()
{
int liczba;
ADRwezel pdrzewo;
ADRwezel p, q;
printf( "\n Podawaj liczby naturalne. Koniec = jakas litera ! \n\n ");
scanf( "%d", &liczba ); /* podaj pierwsza liczbe */
pdrzewo = NowaGałąz
( liczba ); /* bedzie ona korzeniem drzewa */
while ( scanf("%d", &liczba ) != NULL ) // wczytuj kolejne liczby
{
p = q = pdrzewo;
while( liczba != p->info && q != NULL ) // powtarzaj kiedy rozne
{ // 1. rozne liczby
p = q; // 2. drzewo jest nizej
if ( liczba < p->info )
q = p->lewy; // jesli mniejsze, to w lewo
else
q = p->prawy; // jesli wieksze, to w prawo
}
if ( liczba == p->info ) // znaleziono podana liczbe/
printf(" Liczba %d zostala juz wczytana !\n", liczba );
else if ( liczba < p->info ) // koniec galezi drzewa
PoLewej( p, liczba ); // wstaw liczbe do lewej odnogi
else
PoPrawej( p, liczba); // wstaw liczbe do prawej odnogi
}
printf("\n Inorder :\n"); // Rozne sposowy wyszukiwania
Inorder( pdrzewo ); // elementow w drzwie binarnym
printf("\n Preorder :\n");
Preorder( pdrzewo );
printf("\n Postorder :\n");
Postorder( pdrzewo );
printf("\n");
}
/* Funkcje pomocnicze----------------------------------------------------------------- */
ADRwezel PobierzWezel( void ) /* zwraca adres nowego wezla */
{
ADRwezel p;
p = (ADRwezel) malloc( sizeof( struct wezel ) ) ;
return( p );
}
/*------------------------------------------------------------------------------------------------*/
ADRwezel NowaGałąz
( int x ) /* wygeneruj kolejna galaz */
{ ADRwezel p;
p = PobierzWezel();
p->info = x;
p->lewy = NULL; p->prawy = NULL;
return( p );
}
/*------------------------------------------------------------------------------------------------*/
void PoLewej( ADRwezel p, int x ) /* wstaw liczbe x do lewej galezi */
{
if ( p == NULL )
printf( "Brak pamieci !\n" );
else if ( p->lewy != NULL )
printf( "Lewy zajety !\n" );
else
p->lewy = NowaGałąz
( x );
}
/*------------------------------------------------------------------------------------------------*/
void PoPrawej( ADRwezel p, int x) /* wstaw liczbe x do prawej galezi */
{
if ( p == NULL )
printf( "Brak pamieci !\n");
else if ( p->prawy != NULL )
printf( "Prawy zajety !\n");
else
p->prawy = NowaGałąz
( x );
}
/*------------------------------------------------------------------------------------------------*/
void Preorder( ADRwezel p ) /* kolejnosc 1 */
{ if ( p != NULL )
{
printf(" %5d ", p->info); /* info */
Preorder( p->lewy ); /* idz w lewo */
Preorder( p->prawy ); /* idz w prawo */
}
}
/*------------------------------------------------------------------------------------------------*/
void Inorder( ADRwezel p ) /* kolejnosc 2 */
{
if ( p != NULL )
{
Inorder( p->lewy ); /* idz w lewo */
printf(" %5d ", p->info); /* info */
Inorder( p->prawy ); /* idz w prawo */
}
}
/*------------------------------------------------------------------------------------------------*/
void Postorder( ADRwezel p ) /* kolejnosc 3 */
{
if ( p != NULL )
{
Postorder( p->lewy ); /* idz w lewo */
Postorder( p->prawy ); /* idz w prawo */
printf(" %5d ", p->info); /* info */
}
}