PK W4

Programowanie komputerów

Liniowe struktury danych

Tablice i napisy s

przykładami tzw. liniowych struktur danych

emy wyró

nast

puj

ce liniowe struktury danych:

napisy,

tablice sekwencyjne,

kolejki,

stosy,

listy dynamiczne,

tablice rzadkie,

tablice rozproszone.

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?

Programowanie komputerów

Tablice sekwencyjne

W j

zykach programowania przez tablic

rozumie si

g warto

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

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,

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

znakami ASCII lub własnymi typami wyliczeniowymi,

W j

zyku C domy

lnym indeksem tablicy s

liczby naturalne z

zerem

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

ęś

deklaracyjnej programu czy podprogramów

Indeks tablic w j

zyku C jest liczony od zera (0) do warto

(rozmiar-1)

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

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

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:

tab[0]

tab[1]

tab[2]

tab[3]

tab[4]

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[

] =

\n”,

moja_tab[j]

);

/* wypisanie

elementu z opisem i now

lini

}

return 0;

}

Programowanie komputerów

Inicjowanie wartości elementów tablic

Tablic

na zainicjowa

przy pomocy p

tli, np.: for

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’}

znaki[0]

znaki[1]

znaki[2]

znaki[3]

znaki[4]

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]

Po wykonaniu zerowania:

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

Programowanie komputerów

Wykorzystywanie tablic „otwartych”

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

tablica, to

emy u

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};

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*/

Programowanie komputerów

Przykład wykorzystania tablicy jednowymiarowej

Wyliczenie warto

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

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;

}

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ą

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

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.2

1.23

2.12

1.12

3.45

7.23

3.2

5.0

8.7

12.5

1.0

4.78

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

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)

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

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)

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;

}

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;

}

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”,
””

}

Programowanie komputerów

Wypisanie listy napisów

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”);

}

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”,

””,””

}

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

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

Programowanie komputerów

Kolejki FIFO

Dyscyplina First In First Out:

Programowanie komputerów

Stos (kolejka LIFO)

Dyscyplina Last In First Out:

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

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

)

Klucze

pocz

tkowe

Programowanie komputerów

Sortowanie przez wstawianie

Klucze

pocz

tkowe

i = 2

i = 3

i = 5

i = 6

i = 4

i = 7

i = 8

K
r
o
k
i

a
l
g
o
r
y
t
m
u

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;

}

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;

}

Programowanie komputerów

Sortowanie przez wybieranie

Klucze

pocz

tkowe

i = 2

i = 3

i = 5

i = 6

i = 4

K
r
o
k
i

a
l
g
o
r
y
t
m
u

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];

}

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;

}

???

Programowanie komputerów

Sortowanie przez zamianę (bąbelkowe)

Klucze

pocz

tkowe

i = 2

i = 3

i = 5

i = 4

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

i = 6

i = 7

i = 8

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

−−

)

li kolejno

ść

elementów j oraz j-1 jest

niewła

ciwa, zamie

je miejscami;

}

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;

}