Programowanie komputerów

Prowadzący:

dr hab. inż. Kazimierz Worwa, prof. UW MSC

r.a. 2007/2008

UCZELNIA WARSZAWSKA

Kierunek INFORMATYKA I EKONOMETRIA

2

Programowanie komputerów

Lokalizacja plików do wykładów

http://members.lycos.co.uk/pkjw84/kw/

logowanie:

nazwa u

ż

ytkownika

2007/2008

hasło

kw

Programowanie komputerów

Wykład 4

Tablice

Napisy

Algorytmy sotowania

4

Programowanie komputerów

Liniowe struktury danych

Tablice i napisy s

ą

przykładami tzw. liniowych struktur danych

Mo

ż

emy wyró

ż

ni

ć

nast

ę

puj

ą

ce liniowe struktury danych:

napisy,

tablice sekwencyjne,

kolejki,

stosy,

listy dynamiczne,

tablice rzadkie,

tablice rozproszone.

5

Programowanie komputerów

Tablice sekwencyjne

W praktyce programowania najcz

ęś

ciej spotykamy si

ę

z tablicami:

jednowymiarowymi (wektory),

dwuwymiarowymi (macierze)

trójwymiarowymi (prostopadło

ś

ciany lub tzw. kostki)

Bardzo cz

ę

sto u

ż

ywa si

ę

poj

ę

cia tablica dla okre

ś

lenia

implementacji macierzy, czyli tablicy dwuwymiarowej

Liczna grupa metod numerycznych wykorzystuje poj

ę

cie tablicy

(ci

ą

gu, sekwencji liczb)

Jak zatem wygl

ą

da obsługa tablic w j

ę

zykach programowania?

6

Programowanie komputerów

Tablice sekwencyjne

W j

ę

zykach programowania przez tablic

ę

rozumie si

ę

ci

ą

g warto

ś

ci

(np. liczb, znaków, innych typów prawidłowych dla kompilatora),
b

ę

d

ą

cych tego samego typu,

Pojedyncza zmienna w tablicy nazywana jest elementem tablicy,

Do wszystkich zmiennych w tablicy odwołujemy si

ę

poprzez t

ę

sam

ą

nazw

ę

wykorzystuj

ą

c indeks elementu tablicy,

Indeks tablicy budowany jest na podstawie typu wyliczeniowego -
najcz

ęś

ciej s

ą

to liczby naturalne z zerem (0) wł

ą

cznie,

S

ą

j

ę

zyki programowania (np. Pascal), w których indeksy mog

ą

by

ć

znakami ASCII lub własnymi typami wyliczeniowymi,

W j

ę

zyku C domy

ś

lnym indeksem tablicy s

ą

liczby naturalne z

zerem

7

Programowanie komputerów

Deklarowanie tablic jednowymiarowych (wektorów)

W j

ę

zyku C tablice jednowymiarowe deklarujemy według schematu:

typ_elementów nazwa_tablicy [rozmiar]

każdy z elementów tablicy

jest typu „typ_elementów”

dostęp do każdego

z elementów tablicy

jest realizowany

poprzez jej nazwę

rozmiar podawany jest

jako liczba stało-

przecinkowa w otoczeniu
nawiasów kwadratowych

Zmienne i stałe typu tablicowego deklarujemy w cz

ęś

ci

deklaracyjnej programu czy podprogramów

Indeks tablic w j

ę

zyku C jest liczony od zera (0) do warto

ś

ci

(rozmiar-1)

8

Programowanie komputerów

Tablice jednowymiarowe

Przykład: deklaracja pi

ę

ciopozycyjnej tablicy liczb całkowitych:

int tab[5]

Po wykonaniu powy

ż

szej deklaracji powstaje w pami

ę

ci

operacyjnej nast

ę

puj

ą

ca struktura danych:

tab[0]

tab[1]

tab[2]

tab[3]

tab[4]

spójny obszar pamięci operacyjnej

najmłodszy adres

najstarszy adres

9

Programowanie komputerów

Tablice jednowymiarowe

Wypełnienie tablicy z wykorzystanie p

ę

tli for :

int tab[5];

int j;

for (j=0; j<5; j++)

{

tab [ j ] = j; /* podstawienie warto

ś

ci do elementu tablicy */

}

Po wykonaniu powy

ż

szych działa

ń

otrzymujemy:

0

tab[0]

1

tab[1]

2

tab[2]

3

tab[3]

4

tab[4]

10

Programowanie komputerów

Tablice jednowymiarowe

Przykład: Wczytanie elementów do tablicy i wypisanie ich na ekranie:

#include <stdio.h>
int moja_tab[8];
int j;

main( ) {

for (j=0; j<8; j++)
{

scanf(„%d”, &moja_tab[j]);

/*wczytanie elementu do tablicy*/

printf(„moja_tab[

%d

] =

%d

\n”,

j

,

moja_tab[j]

);

/* wypisanie

elementu z opisem i now

ą

lini

ą

*/

}

return 0;

}

11

Programowanie komputerów

Inicjowanie wartości elementów tablic

Tablic

ę

mo

ż

na zainicjowa

ć

przy pomocy p

ę

tli, np.: for

Mo

ż

na równie

ż

wczyta

ć

warto

ś

ci elementów przy pomocy funkcji

scanf

Zainicjowanie warto

ś

ci tablicy w postaci wyliczenia listy warto

ś

ci:

typ_elementów nazwa_tablicy [rozmiar] = {lista_warto

ś

ci}

Przykład:

char znaki[5] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}

A

znaki[0]

B

znaki[1]

C

znaki[2]

D

znaki[3]

E

znaki[4]

12

Programowanie komputerów

Inicjowanie wartości elementów tablic

Nie nale

ż

y polega

ć

na warto

ś

ciach inicjalizacyjnych tablic. Mo

ż

e to by

ć

ró

ż

nie realizowane dla poszczególnych

ś

rodowisk j

ę

zyka C i dla ró

ż

nych

systemów operacyjnych. Dlatego te

ż

w dobrym zwyczaju le

ż

y jawne

wypełnienie tablicy warto

ś

ciami pocz

ą

tkowymi na przykład z

wykorzystaniem p

ę

tli for

:

int tab[100];
int j;
for (j=0; j<100; j++)
{

tab[ j ] = 0;

/* wyzerowanie tablicy */

}

tab[0]

tab[1]

tab[2]

tab[99]

0

0

0

0

Po wykonaniu zerowania:

......................

13

Programowanie komputerów

Wykorzystywanie tablic „otwartych”

Je

ż

eli z góry nie zakładamy ile elementów ma mie

ć

tablica, to

mo

ż

emy u

ż

y

ć

deklaracji tzw. tablicy otwartej:

typ_elementów nazwa_tablicy [ ] = {lista_warto

ś

ci}

Rozmiar tablicy nie jest podawany wprost.

Faktyczny rozmiar tablicy jest wyliczany przez

środowisko języka C na podstawie liczby elementów

zamieszczonych w liście wartości zadawanych do tablicy

Przykłady:

int całkowite[ ] = {1, 4, 6, -8, 3, -56, 19, 27, -13};

float rzeczywiste[ ] = {-12.23, 45.0, 1.4};

unsigned int naturalne[ ] = {0, 2, 8, 9, 23, 90, 100, 234};

14

Programowanie komputerów

Przepisywanie zawartości z tablicy do innej tablicy

Aby przepisa

ć

zawarto

ść

jednej tablicy do innej tablicy musimy

przepisa

ć

kolejno jej poszczególne elementy

DOZWOLONY SPOSÓB PRZEPISYWANIA WARTO

Ś

CI:

int

ź

ródło[5] = {0, 1, 2, 3, 4}

int wynik[5];
int i;

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

wynik[i] =

ź

ródło[i];

/*przepisywanie pojedynczych elementów*/

}

NIEDOZWOLONY SPOSÓB:

wynik =

ź

ródło;

/*nieprawidłowa próba u

ż

ycia nazwy całej tablicy*/

15

Programowanie komputerów

Przykład wykorzystania tablicy jednowymiarowej

Wyliczenie warto

ś

ci

ś

redniej elementów tablicy:

#include <stdio.h>

zakres = 20; /*zadeklarowanie stałej globalnej*/

int tablica[zakres];

int i, suma;

float

ś

rednia;

int main ( )

{

ś

rednia = 0.0; /*zainicjowanie warto

ś

ci zmiennych globalnych*/

suma = 0;

/*wczytanie zawarto

ś

ci tablicy*/

for (i=0; i<zakres; i++)

{

printf(„Podaj: tablica[ %d ]= ”, i);

scanf(„%d”, &tablica[i]);

printf(\n); /*przej

ś

cie do nast

ę

pnego wiersza*/

}

/*obliczenie warto

ś

ci

ś

redniej i wypisanie wyniku*/

for (i=0; i<zakres; i++)

{

suma = suma + tablica[i];

}

ś

rednia = suma / zakres;

/*niejawne uzgodnienie typów do float -

rzutowanie typów w j

ę

zyku C */

printf(„Warto

ść

ś

rednia elementów tablicy wynosi %f\n”,

ś

rednia);

return 0;

}

16

Programowanie komputerów

Przykład wykorzystania tablicy jednowymiarowej

Wykorzystanie niesko

ń

czonej p

ę

tli for :

#include <stdio.h>

unsigned long suma;

unsigned int liczba;

unsigned int tablica[100];

int licznik;

main ( )

{

printf(„Program wczytuje maksymalnie 100 liczb naturalnych do tablicy i oblicza

ich sum

ę

.\n”);

licznik = 0; /*zainicjowanie warto

ś

ci zmiennych*/

suma = 0;

liczba = 0;

for( ; ; )

/* niesko

ń

czona p

ę

tla for. Mo

ż

na j

ą

przerwa

ć

wył

ą

cznie poleceniem:

break */

{

if (((liczba == 1) || (licznik == 100))

{

break;

}

else

{

printf(„Podaj liczb

ę

dodatni

ą

z zakresu: 2 - 65535.”);

printf(„Podaj warto

ść

1, aby wcze

ś

niej zako

ń

czy

ć

działanie programu.\n”);

scanf(„%u”, &liczba); /*wczytanie liczby z klawiatury*/

tablica[licznik] = liczba; licznik++;

suma = suma + liczba;

}

}

printf(„Wczytano %d liczb. Ich suma wynosi: %lu\n”; liczba, suma);

return 0;

}

pętla nieskończona

wyjście z pętli

instrukcje poza pętlą

17

Programowanie komputerów

Tablice wielowymiarowe

W j

ę

zyku C tablice wielowymiarowe deklarujemy według schematu:

typ_elementów nazwa_tablicy [wymiar1]...[wymiarN]

każdy z elementów tablicy

jest typu „typ_elementów”

dostęp do każdego

z elementów tablicy

jest realizowany

poprzez jej nazwę

każdy z wymiarów podawany jest

jako liczba stałoprzecinkowa w otoczeniu

nawiasów kwadratowych

Przykład: deklaracja dwuwymiarowej tablicy (macierzy) liczb

rzeczywistych:

float macierz_R [4][3];

indeks

wiersza

indeks

kolumny

18

Programowanie komputerów

Inicjowanie wartości elementów macierzy

Przy pomocy podwójnej p

ę

tli for :

float macierz_R[4][3]

int i, j;
for(i=0; i<4; i++)
{

for (j=0; j<3; j++)
{

macierz_R[i][j] = 0.0;

}

}

Jawnie ustawiaj

ą

c list

ę

warto

ś

ci:

float macierz_R[4][3]=

{

0.0, 0.0, 0.0,
0.2, 1.23, 2.12,
1.12, 3.45, 7.23,
3.2, 5.0, 8.7

};

Selektywnie wstawianie warto

ś

ci do tablicy:

macierz_R[2][2] = 1.0;

macierz_R[0][2] = 12.5;

macierz_R[3][1] = 4.78;

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0

1

2

0

1

2

3

0.0

0.0

0.0

0.2

1.23

2.12

1.12

3.45

7.23

3.2

5.0

8.7

0

1

2

3

12.5

1.0

4.78

0

1

2

3

19

Programowanie komputerów

Przykład wykorzystania tablicy dwuwymiarowej

W poni

ż

szym przykładzie do macierzy liczb całkowitych wstawiana jest, a nast

ę

pnie

wypisywana warto

ść

iloczynu indeksów wierszy i kolumn poszczególnych elementów

macierzy:

#include <stdio.h>

int macierz[4][5];

main( )
{

for(i=0; i<4; i++)

for(j=0; j<5; j++)

macierz[i][j] = i*j;

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

for(j=0; j<5; j++)

printf(„%d”, macierz[i][j]);

printf(„\n”);

}

return 0;

}

Wynik zadziałania programu:

0 0 0 0 0
0 1 2 3 4
0 2 4 6 8
0 3 6 9 12

20

Programowanie komputerów

Napisy - tablice znaków

Napis (ang. string) jest najcz

ęś

ciej wykorzystywan

ą

jednowymiarow

ą

tablic

ą

w j

ę

zyku C

C nie ma wbudowanego typu napisowego string (tak, jak ma
to wi

ę

kszo

ść

innych j

ę

zyków programowania)

Ka

ż

dy napis w j

ę

zyku C jest jednowymiarow

ą

tablic

ą

znaków,

która automatycznie jest zamykana specjalnym elementem
zerowym (null)

Sposób deklarowania napisu:

char nazwa_napisu[rozmiar_napisu]

każdy z elementów

napisu jest typu

znakowego

ostatni znak napisu jest

zawsze znakiem null

automatycznie dodawanym

przez środowisko języka C

21

Programowanie komputerów

Funkcje operujące na napisach

z biblioteki <stdio.h>:

gets(napis) - wczytanie napisu, Enter zamieniany na null

printf(napis, ...) - wypisanie napisu

z biblioteki <string.h>:

strcpy(wynik,

ź

ródło) - kopiuje

ź

ródło do wyniku

strcat(wynik,

ź

ródło) - doł

ą

cza

ź

ródło do wyniku

strcmp(napis1, napis2) - porównywanie napisów:

== 0 - napisy identyczne,

< 0 - napis1 jest leksykograficznie mniejszy od napis2

> 0 - napis1 jest leksykograficznie wi

ę

kszy od napis2

strlen(napis) - zwraca długo

ść

napisu (liczb

ę

znaków)

22

Programowanie komputerów

Przykłady działania na napisach

Poni

ż

szy program wczytuje napis i wypisuje go pojedynczymi

znakami na ekran:

#include <stdio.h>

char napis[80];

int i;

int main( )

{

printf(„Wprowad

ź

napis nie wi

ę

kszy ni

ż

80 znaków:”);

gets(napis);

for(i=0;

napis[i]

; i++)

printf(„%c”, napis[i]);

return 0;

}

23

Programowanie komputerów

Przykłady działania na napisach

Poni

ż

szy program działa tak, jak poprzedni, ale nie wykorzystuje p

ę

tli

for:

#include <stdio.h>

char napis[80];

int i;

main( )

{

printf(„Wprowad

ź

napis nie wi

ę

kszy ni

ż

80 znaków:”);

gets(napis);

printf(napis);

return 0;

}

24

Programowanie komputerów

Inicjowanie napisów

Napis inicjowany jako otwarta tablica znaków :

char komunikat[ ] = „Naci

ś

nij klawisz”;

char imi

ę

[ ] = „Anna”;

Otwarta lista napisów 40-znakowych:

char lista_przedmiotów[ ][40] = {

„Techniki programowania”,
„Algorytmika”,
„Metody numeryczne”,
„Symulacja komputerowa”,
„Mikroekonomia”,
„Statystyka matematyczna”,
””

}

25

Programowanie komputerów

Wypisanie listy napisów

p

ę

tla wy

ś

wietlaj

ą

ca list

ę

przedmiotów pojedynczymi znakami

int i, j;

for(i=0;

lista_przedmiotów[i][j]

; i++)

{

for(j=0;

lista_przedmiotów[i][j]

; j++)

printf(„%c”, lista_przedmiotów[i][j]);

printf(„\n”);

}

26

Programowanie komputerów

Wielopoziomowa lista napisów

Otwarta lista dwójek napisów 30-znakowych:

char lista_par[ ][2][40] = {

„Techniki programowania”, „rok 1-szy”,

„Algorytmika”, „rok 1-szy”,

„Metody numeryczne”, „rok 4-ty”,

„Symulacja komputerowa”, „rok 3-ci”,

„Mikroekonomia”, „rok 1-szy”,

„Statystyka matematyczna”, „rok 2-gi”,

””,””

}

27

Programowanie komputerów

Przykład tablic - kolejki

Kolejka (queue) jest struktur

ą

danych wykorzystywan

ą

najcz

ęś

ciej jako bufor przechowuj

ą

cy dane okre

ś

lonych typów.

Dyscypliny kolejek:

FIFO (First In First Out) - pierwszy element wchodz

ą

cy

staje si

ę

pierwszym wychodz

ą

cym

Round-Robin - cykliczna kolejka z dyscyplin

ą

czasu

obsługi komunikatu przechowywanego w kolejce (w
systemach operacyjnych, sieciach komputerowych)

LIFO (Last In First Out) - ostatni wchodz

ą

cy staje si

ę

pierwszym wychodz

ą

cym (tak działa stos)

kolejki priorytetowe - dodatkowo w standardowym
mechanizmie kolejki uwzgl

ę

dnia si

ę

warto

ś

ci priorytetów

przechowywanych danych

28

Programowanie komputerów

Kolejki FIFO

Dyscyplina First In First Out:

d

1

We

Wy

d

1

We

Wy

d

2

d

1

We

Wy

d

2

d

3

d

4

d

5

d

6

29

Programowanie komputerów

Stos (kolejka LIFO)

Dyscyplina Last In First Out:

d

1

We

Wy

d

1

d

2

We

Wy

d

1

d

2

d

3

d

4

d

5

d

6

We

Wy

30

Programowanie komputerów

Metody sortowania wewnętrznego

Podstawowe algorytmy sortowania

Sortowanie przez wstawianie (

ang. insertion sort

)

Sortowanie przez wybieranie (selekcj

ę

) (

ang. selection sort

)

Sortowanie przez zamian

ę

(b

ą

belkowe) (

ang. exchange sort, bubble sort

)

Efektywne algorytmy sortowania

Sortowanie przez kopcowanie (

ang. heap sort

)

Sortowanie metod

ą

malej

ą

cych przyrostów (Shella)

Sortowanie szybkie (

ang

.

quicksort

)

Sortowanie przez scalanie (

ang. merge sort

)

44

55

12

42

94

18

06

67

Klucze

pocz

ą

tkowe

31

Programowanie komputerów

Sortowanie przez wstawianie

44

55

12

42

94

18

06

67

Klucze

pocz

ą

tkowe

44

55

12

42

94

18

06

67

i = 2

44

55

12

42

94

18

06

67

i = 3

44

55

12

42

94

18

06

67

i = 5

44

55

12

42

94

18

06

67

i = 6

44

55

12

42

94

18

06

67

i = 4

44

55

12

42

94

18

06

67

i = 7

44

55

12

42

94

18

06

67

i = 8

K
r
o
k
i

a
l
g
o
r
y
t
m
u

32

Programowanie komputerów

Idea algorytmu sortowania przez wstawianie

void InsertionSort (int tab[ ], int n)

{

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

{

przesu

ń

wszystkie elementy tab[j] wi

ę

ksze od tab[i] o jedn

ą

pozycj

ę

;

umie

ść

tab[i] w odpowiednim miejscu;

}

}

33

Programowanie komputerów

Przykładowy algorytm sortowania przez wstawianie

void InsertionSort (int tab[ ], int n)

{

for ( int i=1, j; i<n; i++)

{

int temp=tab[i];

for (j=i; j>0 && temp<tab[j-1]; j

−−

−−

−−

−−

)

tab[j]= tab[j-1];

tab[j]=temp;

}

}

34

Programowanie komputerów

Sortowanie przez wybieranie

44

55

12

42

94

18

06

67

Klucze

pocz

ą

tkowe

44

55

12

42

94

18

06

67

i = 2

i = 3

i = 5

i = 6

i = 4

K
r
o
k
i

a
l
g
o
r
y
t
m
u

44

55

12

42

94

18

06

67

44

55

12

42

94

18

06

67

44

55

12

42

94

18

06

67

44

55

12

42

94

18

06

67

35

Programowanie komputerów

Idea algorytmu sortowania przez wybieranie

void SelectionSort (int tab[ ], int n)

{

for (i=0; i<n-1; i++)

{

wybierz najmniejszy element spo

ś

ród tab[i], ..., tab[n-1];

zamie

ń

wybrany element z tab[i];

}

}

36

Programowanie komputerów

Przykładowy algorytm sortowania przez wybieranie

void SelectionSort (int tab[ ], int n)
{

int i, least, j;
for ( i=0; i<n-1; i++ )
{

for (j=i+1, least=i; j<n; j++)

if (tab[j] < tab[least])

least=j;

// zamiana (tab[least], tab[i]);

int temp= tab[least];
tab[least] = tab[i];
tab[i ]=temp;

}

}

37

Programowanie komputerów

Przykładowy algorytm sortowania przez wybieranie

void SelectionSort (int tab[ ], int n)

{

for (int i=0, least, j; i<n-1; i++)

{

for (j=i+1, least=i; j<n; j++)

if (tab[j] < tab[least])

least=j;

// zamiana (tab[least], tab[i]);

int temp= tab[least];

tab[least] = tab[i];

tab[i ]=temp;

}

}

???

38

Programowanie komputerów

Sortowanie przez zamianę (bąbelkowe)

44

Klucze

pocz

ą

tkowe

55

i = 2

42

i = 3

18

i = 5

06

94

i = 4

67

44

12

42

18

06

94

67

06

06

K r o k i a l g o r y t m u

12

55

55

18

94

42

67

44

44

55

42

18

67

94

12

12

06

44

55

42

18

67

94

12

06

44

55

42

18

67

94

12

i = 6

06

44

55

42

18

67

94

12

i = 7

06

44

55

42

18

67

94

12

i = 8

39

Programowanie komputerów

Idea algorytmu sortowania przez zamianę

void BubbleSort (int tab[ ], int n)

{

for (i=0; i<n-1; i++)

for (j=n

−

1; j>i; j

−−

)

je

ś

li kolejno

ść

elementów j oraz j-1 jest

niewła

ś

ciwa, zamie

ń

je miejscami;

}

40

Programowanie komputerów

Przykładowy algorytm sortowania przez zamianę

void BubbleSort (int tab[ ], int n)

{

for (int i=0; i<n-1; i++)

for (int j=n

−−−−

1; j>i; j

−−

−−

−−

−−

)

if (tab[j]<tab[j

−−−−

1])

{

// zamiana (tab[j

−−−−

1] , tab[j ])

int temp= tab[j

−−−−

1];

tab[j

−−−−

1] = tab[j ];

tab[j ]=temp;

}

}

41

Programowanie komputerów