Algorytmy i struktury

danych

WYKŁAD 6, cz.1

 

3 7 7 9 3 8 4

 

2 5 0 1 2 5

2

Algorytmy i struktury, wykład 6, cz.1

Wykład 6: Sortowanie plików



obsługa plików binarnych – c.d.



sortowanie plików metodą łączenia prostego i
łączenia naturalnego

3

Algorytmy i struktury, wykład 6, cz.1

Zmiana bieżącego położenia w pliku



Zmiana tzw. bieżącej pozycji wstawiania lub czytania w pliku
dokonywana jest automatycznie podczas wykonywania operacji
zapisu lub odczytu albo poprzez wywołanie funkcji:

int fseek (FILE*

file

, long

offset

, int

whence

);

W wypadku powodzenia wynikiem wykonania funkcji jest
przesunięcie pozycji w pliku o wartość

offset

(może być dodatnia lub

ujemna) względem pozycji określonej przez parametr

whence

:



SEEK_SET – (0) – względem początku pliku



SEEK_CUR – (1) – względem aktualnej pozycji



SEEK_END – (2) – względem końca pliku

W przypadku powodzenia operacji przesunięcia funkcja zwraca 0, w
przeciwnym wypadku – wartość <> 0

4

Algorytmy i struktury, wykład 6, cz.1

Zmiana bieżącego położenia w pliku



Zmiana pozycji w pliku możliwa jest również poprzez
wywołanie funkcji:

int fgetpos (FILE*

file

, fpos_t*

pos

) – zwraca bieżącą pozycję w pliku

wpisując ją do
zmiennej

pos

;

int fsetpos (FILE*

file

, const fpos_t*

pos

) – ustawia bieżącą pozycję

w pliku zgodnie z wartością zmiennej

pos

;

Obydwie funkcje w razie bezbłędnego wykonania zwracają wartość
0, lub !=0 w przypadku wystąpienia błędu

long ftell (FILE*

file

) – zwraca pozycję w pliku (w bajtach)

void rewind (FILE*

file

) – ustawia pozycję na początek pliku; jej

użycie jest równoznaczne z wywołaniem fseek(file, 0, SEEK_SET)

5

Algorytmy i struktury, wykład 6, cz.1

Reagowanie na znak końca pliku



Podczas czytania zawartości plików fakt dotarcia do końca pliku
można sprawdzić przy pomocy funkcji:

int feof (FILE*

file

);

Zwraca ona:

wartość różną od 0 - jeżeli podczas czytania danych z pliku
natrafiono na jego koniec (EOF – End Of File)
0 – jeżeli nie natrafiono na koniec pliku



Czytając plik binarny lub plik znakowy o nieznanej długości należy
realizować to w pętli, której zakończenie jest uwarunkowane
napotkaniem znaku końca pliku, czy właśnie EOF

6

Algorytmy i struktury, wykład 6, cz.1

Wyjście danych do pliku binarnego – zapis

blokowy

Posługując się plikiem binarnym, do zapisu można posłużyć się
funkcją:

size_t fwrite(const void *

ptr

, size_t

size

, size_t

n

, FILE*

stream

);



ptr – wskaźnik na dowolny obiekt, adres początkowy
zapisywanych danych



size – wielkość każdego zapisywanego elementu



n – liczba zapisywanych elementów



stream – uchwyt pliku do którego następuje zapis

Łączna liczba zapisanych bajtów jest równa (n * size)
W przypadku poprawnego wykonania funkcji zwraca ona w wyniku liczbę
poprawnie zapisanych elementów (nie bajtów) równą n, w przypadku
wystąpienia błędu – liczbę mniejszą od n

7

Algorytmy i struktury, wykład 6, cz.1

Binarny zapis – przykład wyjścia danych z

rekordu

#include <stdio.h>

struct teststruct
{ int i;
char ch; };

void main(void)
{
FILE *stream;
struct teststruct s;

if ((stream = fopen("TEST.DAT", "wb")) == NULL)
fprintf(stderr, "Nie mozna otworzyc pliku\n");

s.i = 0;
s.ch = 'A';

fwrite(&s, sizeof(s), 1, stream);

fclose(stream);
}

Blokowe

wyjście

rekordu do

pliku

zewnętrznego

skojarzonego

ze zmienną

„stream”

8

Algorytmy i struktury, wykład 6, cz.1

Binarne wejście – czyli jak odczytywać na

przykład rekordy?

Posługując się plikiem binarnym, do odczytu danych można posłużyć
się funkcją:

size_t fread ( void *

ptr

, size_t

size

, size_t

n

, FILE*

stream

);



ptr – wskaźnik na strukturę w pamięci w której umieszczone
mają być odczytane dane



size – wielkość odczytywanych elementów



n – liczba odczytywanych elementów



stream – uchwyt pliku z którego następuje odczyt

Łączna liczba odczytanych bajtów jest równa (n * size)
W przypadku poprawnego wykonania funkcji zwraca ona w wyniku liczbę
poprawnie odczytanych elementów (nie bajtów) równą n, w przypadku
wystąpienia błędu – liczbę mniejszą od n

9

Algorytmy i struktury, wykład 6, cz.1

Binarny odczyt – przykład odczytu danych

do rekordu

#include <stdio.h>

struct teststruct
{ int i;
char ch; };

void main(void)
{
FILE *moj_plik;
struct teststruct s;

if ((moj_plik = fopen("TEST.DAT", "rb")) == NULL)
fprintf(stderr, "Nie mozna otworzyc pliku\n");

fread(&s, sizeof(s), 1, moj_plik);

fclose(moj_plik);
}

Blokowe wejście

danych z pliku

zewnętrznego

skojarzonego ze

zmienną

„mój_plik” do

rekordu s

10

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Zdefiniujmy typ strukturowy przechowujące dane
osobowe:

Struct osoba {

Char imie[25];
Char nazwisko[35];
Char PESEL[11];
Unsigned int wiek;
Unsigned int wzrost;
Char plec;

};

Zdefiniowana

struktura będzie

podstawą dla

konstruowanej

kartoteki

Polami struktury
mogą być tablice

Albo zmienne typu

prostego

11

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Załóżmy, że chcemy dodatkowo przechowywać dane
adresowe dla każdej osoby. Definicja struktury dla
adresu może być następująca:

Struct dane_adresowe {

Char ulica[40];
Char dom[4], lokal[4];
Char kod_p[6];
Char miejscowość[30];

};



Aby dołączyć dane adresowe do definicji struktury dla
danych osobowych, trzeba zastosować struktury
zagnieżdżone

12

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Po prostu jako jedno z pól struktury należy zdefiniować
pole zdefiniowane jako dane_adresowe:

Struct osoba {

Char imie[25];
Char nazwisko[35];
Char PESEL[11];
Unsigned int wiek;
Unsigned int wzrost;
Char plec;

Struct dane_adresowe adres;

};

Pole strukturowe,

zagnieżdżone

wewnątrz struktury

Struktura

dane_adresowe

została

zdefiniowana

wcześniej

13

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Zbudujmy zatem kartotekę danych osobowych, którą
zorganizujemy w postaci tablicy, której elementem jest
struktura:

Struct osoba kartoteka[30];

[0]

[1]

[2]

[29]

zagnieżdż

one dane

adresowe

14

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Aby wstawić lub odczytać wartość pola w tablicy
struktur, należy wykorzystać zarówno indeksowanie i
kropkę charakterystyczną dla referencji do struktur, np.
polecenie:

kartoteka[1].imie=„Anna”;

Powoduje wstawienie na pozycji o indeksie ==1 w jej

pole „imie” wartości „Anna”.



Podobnie działamy przy zagnieżdżonych strukturach
będących elementami tablic:

kartoteka[23].adres.ulica=„Świeradowska”;

15

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych



Do obsługi (wczytywania, wypisywania) danych w
skojarzeniu z klawiaturą i monitorem,
przechowywanych w kartotece można wykorzystać
pętlę for. Robimy to na takich zasadach, o których
mówiliśmy już przy okazji tablic, np..:

for(i=0; i<30; i++) {

gets(kartoteka[i].imie);
………
scanf(„%u”, &kartoteka[i].wiek);
………
gets(kartoteka[i].adres.miejscowość);
………

}

16

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych, wczytanie danych z

pliku do kartoteki

#include <stdio.h>

FILE *moj_plik;
struct osoba kartoteka[30];
int erob, poz;

main()
{ if ((moj_plik = fopen("TEST.DAT", "rb")) == NULL)
fprintf(stderr, "Nie mozna otworzyc pliku\n");

erob = feof(moj_plik);

poz = 0;

while (erob =

= 0) {

fread(&kartoteka[poz], sizeof(kartoteka[poz]), 1, moj_plik);
poz++;
erob = feof(moj_plik);
}

fclose(moj_plik);
}

Blokowe wczytywanie

rekordów do kartoteki

Detekcja końca pliku, z

którego następuje

wczytywanie danych

17

Algorytmy i struktury, wykład 6, cz.1

Przykład – kartoteka danych

osobowych, zapis danych z

kartoteki do pliku

#include <stdio.h>

FILE *moj_plik;
struct osoba kartoteka[30];
int poz;

main()
{ if ((moj_plik = fopen("TEST.DAT", „wb")) == NULL)
fprintf(stderr, "Nie mozna otworzyc pliku\n");

for (poz=0; kartoteka[poz]; poz++) {
fwrite(&kartoteka[poz], sizeof(kartoteka[poz]), 1, moj_plik);
}

fclose(moj_plik);
}

Blokowy zapis

kolejnych rekordów do

pliku zewnętrznego

18

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych



Podobnie, jak sortowaliśmy tablice sekwencyjne, tak
również możemy sortować dane, które są
przechowywane w plikach sekwencyjnych,



Oczywiście inne są metody sortowania danych, które
są zgromadzone w plikach zewnętrznych,



Wynika to przede wszystkim z innej organizacji
dostępu do danych, które są przechowywane w plikach
zewnętrznych. gdzie ogranicza nas przed wszystkim
ich sekwencyjność. Takiego ograniczenia nie mieliśmy
w przypadku sortowania tablic



Poznamy dwie metody sortowania danych w plikach
zewnętrznych (wg N.Wirtha), tj.:



METODĘ ŁĄCZENIA PROSTEGO



METODĘ ŁĄCZENIA NATURALNEGO

19

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych METODĄ ŁĄCZENIA

PROSTEGO



Metoda łączenia prostego polega na sukcesywnym

dzieleniu danych w pliku na podciągi o ustalonej długości

maksymalnej i łączeniu tych podciągów wraz z

równoczesnych porządkowaniem zawartych w nich

elementów w uporządkowane podciągi danych. Porządek

ten może być dowolny, np. rosnący lub malejący



Zapis logiki algorytmu sortowania metodą łączenia

prostego może być następujący:

co_ile = 1;

do {

dalej=0;

rozdzielanie;
if rozdzielono{

łączenie;

dalej = 1;
}

co_ile = 2 * co_ile;
}while (dalej=1);

20

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych METODĄ ŁĄCZENIA

PROSTEGO - niemalejące



Zawartość sortowanego pliku:

 

3 7 2 5 7 9 1 0 8 3 2 5 4



co_ile == 1

- ROZDZIELANIE SERII

:

 

3 2 7 1 8 2 4

 

7 5 9 0 3 5



co_ile == 1

- ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

3 7 2 5 7 9 0 1 3 8 2 5 4

13 wygenerowanych

serii liczb, które

potem będą łączone

w ustalonym

porządku sortowania

21

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE PROSTE – niemalejące,

krok 2



Zawartość sortowanego pliku:



co_ile == 2

- ROZDZIELANIE SERII

:

 

3 7 7 9 3 8 4

 

2 5 0 1 2 5



co_ile == 2

- ŁĄCZENIE SERII

– w ustalonym porządku sortowania

:

 

2 3 5 7 0 1 7 9 2 3 5 8 4

 

3 7 2 5 7 9 0 1 3 8 2 5 4

7 wygenerowanych

serii liczb, które

potem będą łączone

w ustalonym

porządku sortowania

22

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE PROSTE – niemalejące,

krok 3



Zawartość sortowanego pliku:



co_ile == 4

- ROZDZIELANIE SERII

:

 

2 3 5 7 2 3 5 8

 

0 1 7 9 4



co_ile == 4

- ŁĄCZENIE SERII

– w ustalonym porządku sortowania

:

 

0 1 2 3 5 7 7 9 2 3 4 5 8

 

2 3 5 7 0 1 7 9 2 3 5 8 4

4 wygenerowane

serie liczb, które

potem będą łączone

w ustalonym

porządku sortowania

23

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE PROSTE – niemalejące,

krok 4



Zawartość sortowanego pliku:



co_ile == 8

- ROZDZIELANIE SERII

:

 

0 1 2 3 5 7 7 9

 

2 3 4 5 8



co_ile == 8

- ŁĄCZENIE SERII

– w ustalonym porządku sortowania

:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

 

0 1 2 3 5 7 7 9 2 3 4 5 8

2 wygenerowane

serie liczb, które

potem będą łączone

w ustalonym

porządku sortowania

24

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE PROSTE – niemalejące,

krok 5



Zawartość sortowanego pliku:



co_ile == 16

- ROZDZIELANIE SERII

:



NIE ROZDZIELONO SERII – KONIEC ALGORYTMU SORTOWANIA PLIKU METODĄ ŁĄCZENIA PROSTEGO



PLIK POSORTOWANY WYGLĄDA NASTĘPUJĄCO:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

 

0 1 2 2 3 3 4 5 5 7 7 8 9

 

0 1 2 2 3 3 4 5 5 7 7 8 9

25

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych METODĄ ŁĄCZENIA

NATURALNEGO



Metoda łączenia naturalnego polega na sukcesywnym

dzieleniu danych w pliku na podciągi i łączeniu tych

podciągów wraz z równoczesnych porządkowaniem

zawartych w nich elementów. Nie ustala się długości

tych podciągów – zależy to wyłącznie od ułożenia

wartości sortowanych elementów



Zapis logiki algorytmu sortowania metodą łączenia

naturalnego może być następujący:

do {

dalej=0;

rozdzielanie;
if rozdzielono{

łączenie;

dalej = 1;
}

}while (dalej=1);

26

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych METODĄ ŁĄCZENIA

NATURALNEGO-1 - niemalejące



Zawartość sortowanego pliku:

 

3 7 2 5 7 9 1 0 8 3 2 5 4



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

3 7 1 3 4

 

2 5 7 9 0 8 2 5



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

2 3 5 7 7 9 0 1 8 2 3 5 4

7 serii, które

ułożyły się w

porządku

niemalejącym

27

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-1 –

niemalejące, krok 2



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

2 3 5 7 7 9 2 3 5

 

0 1 8 4



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

0 1 2 3 5 7 7 8 9 2 3 4 5

4 serie, które

ułożyły się w

porządku

niemalejącym

 

2 3 5 7 7 9 0 1 8 2 3 5 4

28

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-1 –

niemalejące, krok 3



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

0 1 2 3 5 7 7 8 9

 

2 3 4 5



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

2 serie, które

ułożyły się w

porządku

niemalejącym

 

0 1 2 3 5 7 7 8 9 2 3 4 5

29

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-1 –

niemalejące, krok 4



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

 

0 1 2 2 3 3 4 5 5 7 7 8 9



NIE ROZDZIELONO SERII – KONIEC ALGORYTMU SORTOWANIA PLIKU METODĄ ŁĄCZENIA NATURALNEGO-1



PLIK POSORTOWANY WYGLĄDA NASTĘPUJĄCO:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

30

Algorytmy i struktury, wykład 6, cz.1

Sortowanie danych w plikach

zewnętrznych METODĄ ŁĄCZENIA

NATURALNEGO-2 - niemalejące



Zawartość sortowanego pliku:

 

3 7 2 5 7 9 1 0 8 3 2 5 4



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

3 7 1 3 4

 

2 5 7 9 0 8 2 5



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

2 3 5 7 7 9 0 1 3 4 8 2 5

Połączenie

podciągów w

jeden ciąg

niemalejący

różnica

pomiędzy

łączeniem

naturalnym w

wersji 1 i 2

31

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-2 –

niemalejące, krok 2



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

2 3 5 7 7 9 2 5

 

0 1 3 4 8



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

0 1 2 3 3 4 5 7 7 8 9 2 5

 

2 3 5 7 7 9 0 1 3 4 8 2 5

3 serie, które

ułożyły się w

porządku

niemalejącym

32

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-2 –

niemalejące, krok 3



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

0 1 2 3 3 4 5 7 7 8 9

 

2 5



ŁĄCZENIE SERII –

w ustalonym porządku sortowania

:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

2 serie, które

ułożyły się w

porządku

niemalejącym

 

0 1 2 3 3 4 5 7 7 8 9 2 5

33

Algorytmy i struktury, wykład 6, cz.1

ŁĄCZENIE NATURALNE-2 –

niemalejące, krok 4



Zawartość sortowanego pliku:



ROZDZIELANIE SERII – podciągi o wartościach niemalejących

:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

 

0 1 2 2 3 3 4 5 5 7 7 8 9



NIE ROZDZIELONO SERII – KONIEC ALGORYTMU SORTOWANIA PLIKU METODĄ ŁĄCZENIA NATURALNEGO-2



PLIK POSORTOWANY WYGLĄDA NASTĘPUJĄCO:

 

0 1 2 2 3 3 4 5 5 7 7 8 9

34

Algorytmy i struktury, wykład 6, cz.1

Podsumowanie



Poznaliśmy kolejne istotne elementy dotyczące obsługi

plików binarnych,



Nauczyliśmy się zapisywać i odczytywać dane na styku

pliku i rozbudowanej tablicy struktur. Jest to dobry

wstęp do obsługi kartotek w języku C



Poznaliśmy wybrane zagadnienia dotyczące sortowania

plików (czy potrafisz napisać odpowiedni program

sortujący pliki?)



Przestudiuj samodzielnie metodę polifazowego

sortowania plików – to też może być przydatne



To już wszystkie wiadomości na wykładzie z AiSD.

Teraz należy przygotować się do rozliczenia z

przedmiotu.

Dziękuję za uwagę