Notatki
Podstawy Programowania 1
Typy wyliczeniowe i jednowymiarowe tablice
Arkadiusz Chrobot
Zakład Informatyki
2 listopada 2015
1/ 42
Plan
Notatki
Abstrakcja danych
Typy wyliczeniowe
Słowo kluczowe typedef
Tablice jednowymiarowe
Inicjacja tablicy
Operacje na tablicach jednowymiarowych
2/ 42
Abstrakcja danych
Notatki
Abstrakcja może dotyczyć nie tylko operacji (instrukcji) wykonywanych
w programach, ale również danych. Język C pozwala na tworzenie progra-
miście własnych typów danych, które są dostosowane do problemu przez
niego rozwiązywanego. Przykładem takiego typu danych są typy wylicze-
niowe.
3/ 42
Typy wyliczeniowe
Notatki
Typ wyliczeniowy pozwala nadawać nazwy liczbom należącym do określo-
nego podzbioru liczb całkowitych. Innymi słowy, możemy myśleć o typie
wyliczeniowym jako o zbiorze stałych. Ogólny wzorzec definicji typy wyli-
czeniowego można zapisać następująco:
enum nazwa_typu {element_1=wartość, & , element_n};
Jak można zauważyć, nazwy (identyfikatory) poszczególnych elementów
typu wyliczeniowego są pisane wielkimi literami, tak jak stałe. Jest to jed-
nak kwestia wyłącznie konwencji, można zastosować każdą pisownię zgod-
ną z regułami dotyczącymi tworzenia identyfikatorów w języku C. Każ-
demu z elementów wolno nam przypisać dowolną liczbę całkowitą typu
int. Jeśli opuścimy wszystkie przypisania wartości, to pierwszy element
automatycznie otrzyma wartość 0, a kolejne o jeden większą od swojego
poprzednika. Język C pozwala również na przypisanie tej samej liczby do
więcej niż jednego elementu typu wyliczeniowego oraz na zmianę wartości
wybranych elementów lub wybranej grupy elementów w takim typie. Typy
wyliczeniowe mogą być definiowane globalnie lub lokalnie.
4/ 42
Typy wyliczeniowe
Notatki
Przykłady
enum names_of_days {MONDAY=0, TUESDAY=1, WEDNESDAY=2, THURSDAY=3,
FRIDAY=4, SATURDAY=5, SUNDAY=6};
Typ ten nadaje wartości poszczególnym dniom tygodnia, począwszy do
zera. To samo można zapisać nieco krócej w ten sposób:
enum names_of_days {MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY,
SATURDAY, SUNDAY};
Jeśli chcemy, aby wartości dni tygodnia zaczynały się od 1, a nie od 0, to
możemy to zapisać tak:
enum names_of_days {MONDAY=1, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY,
SATURDAY, SUNDAY};
Każdy kolejny dzień za poniedziałkiem otrzyma wartość większą od jego
poprzednika, czyli TUESDAY=2, WEDNESDAY=3, itd.
5/ 42
Typy wyliczeniowe
Notatki
Przykłady
Jeśli chcielibyśmy wyróżnić dni weekendu innymi wartościami, np. 9 i 10,
to możemy zapisać to tak:
enum names_of_days {MONDAY=1, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY,
SATURDAY=9, SUNDAY};
Możemy także uszeregować wartości typu wyliczeniowego w kolejności ma-
lejącej:
enum directions {NORTH=3, WEST=2, EAST=1, SOUTH=0};
6/ 42
Zmienne typu wyliczeniowego
Notatki
Zmienna typu wyliczeniowego może być zadeklarowana jako lokalna (w tym
parametr) lub globalna. Wzorzec jej deklaracji jest następujący:
enum nazwa_typu_wyliczeniowego nazwa_zmiennej;
Tak zadeklarowanej zmiennej możemy przypisać dowolny element jej typu
wyliczeniowego. Zmienne typu wyliczeniowego mogą pełnić rolę liczników
w pętlach for, zmiennych sterujących (selektorów) w instrukcjach switch
oraz mogą być użyte w warunkach w instrukcjach warunkowych oraz po-
zostałych pętlach. Niestety, sposób implementacji typów wyliczeniowych
w języku C nie jest zbyt wyrafinowany. Stanowią one jedynie ułatwienie
dla programisty, którego poprawności kompilator nie weryfikuje, traktując
zmienne typu wyliczeniowego jako zmienne typu int, zatem zmiennej te-
go typu można przypisać dowolną liczbę całkowitą. Może to być przyczyną
wielu błędów w programach. Język C umożliwia także tworzenie stałych
typu wyliczeniowego z użyciem słowa kluczowego const.
7/ 42
Typy wyliczeniowe
Notatki
Przykłady
#include
enum names_of_days {MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY};
void print_message(enum names_of_days day)
{
switch(day) {
case MONDAY:
case TUESDAY:
case WEDNESDAY:
case THURSDAY:
case FRIDAY:
puts("Do pracy!");
break;
default:
puts("Wolne!");
}
}
int main(void)
{
enum names_of_days day;
for(day=MONDAY;day<=SUNDAY;day++)
print_message(day);
return 0;
}
8/ 42
Typy wyliczeniowe
Notatki
Komentarz do przykładu
W przykładowym programie zadeklarowano zmienną lokalną typu wylicze-
niowego w funkcji main() (zmienna day) oraz parametr tego samego typu
w funkcji print_message() (również o nazwie day). Ponadto program
pokazuje jak takie zmienne mogą być użyte jako licznik pętli for oraz ja-
ko selektor w instrukcji switch. Na uwagę zasługuje również konstrukcja
tej ostatniej instrukcji. Okazuje się, że pozostawienie przypadku pustego,
nawet bez instrukcji break może być użyteczne. W wypadku opisywanego
programu skróciło jego zapis. Funkcja print_message() po otrzymaniu
wartości odpowiadającej dowolnemu przypadkowi, poza przypadkiem do-
myślnym, wykona instrukcję związaną z piątkiem. Instrukcje dla soboty
i niedzieli wykonywane są jako przypadek domyślny. Niestety nie istnieje
prosty sposób na wypisanie na ekranie nazw elementów zbioru za pomocą
funkcji printf(). Możliwe jest jednak wypisanie ich wartości za pomocą
ciągu formatującego "%d".
9/ 42
Typy wyliczeniowe
Notatki
Przykłady
#include
enum names_of_days {MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY=9, SUNDAY};
void print_message(enum names_of_days day)
{
switch(day) {
case MONDAY:
case TUESDAY:
case WEDNESDAY:
case THURSDAY:
case FRIDAY:
puts("Do pracy!");
break;
default:
puts("Wolne!");
}
}
int main(void)
{
enum names_of_days day;
for(day=MONDAY;day<=SUNDAY;day++)
print_message(day);
return 0;
}
10/ 42
Typy wyliczeniowe
Notatki
Komentarz do przykładu
Niewielka zmiana w programie (nadanie elementowisaturdaywartości 9)
ujawnia niedoskonałości typów wyliczeniowych. Po uruchomieniu przeko-
namy się, że tydzień teraz ma aż 11 dni, z czego większość jest wolna.
Problemem jest zastosowanie zmiennej day jako licznika pętli for. Kie-
dy licznik ten osiągnie wartość 4 odpowiadającą elementowifriday, to
w następnej iteracji zostanie zwiększony o jeden. Wartości 5 nie odpowia-
da żaden element typu wyliczeniowego, ale jest ona nadal poprawna, bo
program traktuje zmienną day tak, jakby miała wartość typu int. Należy
pamiętać o takich niuansach używając typów wyliczeniowych. Typ wylicze-
niowy jest w język C po prostu  pojemnikiem na stałe.
11/ 42
Słowo kluczowe typedef
Notatki
Pisanie słowa kluczowego enum przed każdą deklaracją zmiennej typu wy-
liczeniowego może być nużące i łatwo jest o nim zapomnieć. Celem zniwe-
lowania tej niedogodności można użyć słowa kluczowego typedef, które
pozwala nadać całej definicji typu krótszą nazwę np.:
typedef enum names_of_days {MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY=9, SUNDAY} days;
Teraz zmienną tego typu można zadeklarować jako np.:
days day = MONDAY;
Słowo kluczowe typedef pozwala nadać nazwy także innym typom da-
nych, nawet będącym częściom standardu języka. Należy więc go stosować
z rozsądkiem. Wiele osób programujących w języku C zaleca w ogóle rezy-
gnację z jego używania, bo, w ich opinii, degraduje ono czytelność kodu,
ukrywając prawdziwy typ zmiennej.
12/ 42
Tablice jednowymiarowe
Notatki
Jednowymiarowe tablice są przykładem struktur danych, czyli zmiennych,
które potrafią przechowywać więcej niż jedną wartość w określonym po-
rządku. W przypadku tablic są to dane tego samego typu. Ilustracja za-
mieszczona poniżej obrazuje tablicę jednowymiarową, która pozwala prze-
chowywać do 8 liczb całkowitych.
0 1 2 3 4 5 6 7
-7 7 10 -3 0 7 15 0
Liczby u góry tablicy, napisane mniejszym fontem, to indeksy tablicy, któ-
re pozwalają jednoznacznie określić położenie wybranego elementu tablicy.
W języku C indeksy są zawsze liczbami naturalnymi, a pierwszy indeks ta-
blicy ma zawsze wartość 0. Element to pojedyncze miejsce w tablicy, które
służy do przechowywania pojedynczej danej. O ile indeksy są niepowta-
rzalne i uszeregowane rosnąco, to wartości mogą być nieuporządkowane
i wielokrotnie się powtarzać. Tablica nazywana jest niekiedy, niezbyt po-
prawnie, wektorem.
13/ 42
Tablice jednowymiarowe
Notatki
Deklaracja
Tak jak inne zmienne, tablica musi zostać zadeklarowana przed jej uży-
ciem. Tablice mogą być zarówno zmiennymi lokalnymi, jak i globalnymi.
W pierwszym przypadku wartości ich elementów wynoszą domyślnie ze-
ro, w drugim są nieokreślone. Ogólny schemat deklaracji tablicy można
przedstawić następująco:
typ_danych nazwa_tablicy[liczba_elementów];
Elementy tablicy mogą mieć dowolny z typów, które do tej pory zosta-
ły przedstawione na wykładzie. Tablice elementów typu char mają spe-
cjalne znaczenie i będą omawiane na odrębnym wykładzie. Nazwa tablicy
jest identyfikatorem budowanym zgodnie z regułami języka C. Liczba ele-
mentów określa ile elementów będzie liczyła tablica. Najczęściej jest ona
podawana wprost jako liczba, lub jest stałą zdefiniowaną z pomocą instruk-
cji #define. Zgodnie ze standardem ISO C99 liczba elementów musi być
większa od zera. Zakres indeksów dla tablicy jednowymiarowej jest zawsze
od 0 doliczba_elementów-1.
14/ 42
Tablice jednowymiarowe
Notatki
Dostęp do elementów
Warto zauważyć, że tablica została skonstruowana przez analogię do budo-
wy pamięci operacyjnej, o czym można się przekonać porównując uprosz-
czony model pamięci przedstawiony na poprzednim wykładzie z ilustracją
z poprzedniego slajdu. Aby zapisać lub odczytać wartość z komórki pamięci
procesor musi podać jej adres. Podobnie programista, który chce uzyskać
dostęp do elementu tablicy musi podać jego indeks. Schemat takiego od-
wołania można przedstawić następująco: nazwa_tablicy[indeks]
W języku C nazwa tablicy jest równoznaczna (w większości przypadków)
wskaz
nikowi. Zatem to samo odwołanie może być wykonane na trzy spo-
soby:
*(nazwa_tablicy+indeks)
*(indeks+nazwa_tablicy)
indeks[nazwa_tablicy]
Dwa pierwsze oparte są na tzw. arytmetyce wskaz
ników. Z czterech przed-
stawionych tu sposobów najczęściej stosowany jest pierwszy, czasem moż-
na spotkać drugi. Ostatnie dwa są stosowane rzadko z uwagi na ich małą
czytelność.
15/ 42
Tablice jednowymiarowe
Notatki
Rozmiar tablicy i liczba elementów
Rozmiar tablicy, czyli liczbę bajtów, które ona zajmuje w pamięci operacyj-
nej, można określić stosując operator sizeof. Liczbę jej elementów można
określić stosując wyrażenie:
sizeof(nazwa_tablicy)/sizeof(nazwa_tablicy[0])
Stosują arytmetykę wskaz
ników, zaprezentowaną na poprzednim slajdzie
można to wyrażenie zapisać także w następującej postaci:
sizeof(nazwa_tablicy)/sizeof(*nazwa_tablicy)
Niestety, te wyrażenia, ani operator sizeof nie działają, jeśli tablica jest
parametrem funkcji.
16/ 42
Tablice jednowymiarowe
Notatki
Przekazywanie do funkcji
Tablice można i należy przekazywać do funkcji. Parametr przekazujący
tablicę do funkcji może mieć taką samą postać jak jej deklaracja, z do-
kładnością do nazwy. Liczba elementów jest ignorowana przez kompilator,
co oznacza, że pod parametr tablicowy, który deklaruje, że ma np. 10
elementów można podstawić tablicę o dowolnej liczbie elementów i kom-
pilator nie będzie w żaden sposób protestował. Jeśli typy elementów nie
będą się zgadzały, to wystosuje jedynie ostrzeżenie. Najczęściej zatem po-
mija się liczbę elementów, zostawiając jedynie w parametrze puste nawiasy
kwadratowe, co jest drugim sposobem przekazania tablicy przez parametr.
Trzecim sposobem jest zadeklarowanie parametru jako wskaz
nika takiego
samego typu jak typ elementów tablicy lub typu wskaz
nik na void (void
*). Ta ostatnia deklaracja nie oznacza wskaz
nika pustego, ale wskaz
nik,
któremu może być przypisany lub pod który może być podstawiony do-
wolny typ wskaz
nikowy. Przekazanie tablicy działa zawsze jak przekazanie
przez wskaz
nik.
17/ 42
Inicjacja tablicy
Notatki
Tablica zainicjowana
Tablice można zadeklarować jako zainicjowaną. Wystarczy po zamykają-
cym nawiasie kwadratowym dodać instrukcję przypisania i wymienić warto-
ści elementów tablicy w nawisach klamrowych, rozdzielając je przecinkami.
W takim przypadku można pominąć liczbę elementów tablicy, zostawiając
puste nawiasy. Zostanie ona ustalona na podstawie liczby wymienionych
w nawiasach klamrowych wartości. Jeśli jednak zdecydujemy się ją po-
dać, to musimy w nawiasach klamrowych podać tyle wartości, ile ta liczba
określa. Przykład ilustruje taki sposób deklaracji tablicy:
int main(void)
{
double fractions[] = {0.1, 0.2, 0.3};
double fractions_2[3] = {0.1, 0.2, 0.3};
return 0;
}
18/ 42
Inicjacja tablicy
Notatki
Inicjacja przez użytkownika
Wartości elementów tablicy możne podać również użytkownik za pomo-
cą klawiatury. Tak określone dane należy wprowadzić w pętli do każdego
elementu z osobna, używając funkcji scanf(). Ponieważ element jest po-
jedynczą zmienną, to przekazując go jako argument wywołania scanf()
powinniśmy go poprzedzić operatorem wyłuskania adresu. Ilustruje to przy-
kład:
int main(void)
{
int array[5];
unsigned int i;
for(i=0;i<5;i++)
scanf("%d",&array[i]);
return 0;
}
19/ 42
Inicjacja tablicy
Notatki
Inicjacja z wykorzystaniem indeksów
W przypadku dużych tablic trudno byłoby stworzyć zainicjowaną tablicę
lub prosić użytkownika o jej wypełnienie. Jeśli elementy tej tablicy są typu
int lub kompatybilnego, to można wykorzystać zmienną indeksującą do
ich zainicjowania:
int main(void)
{
int array[1000];
unsigned int i;
for(i=0;i<1000;i++)
array[i] = i;
return 0;
}
W ten sposób elementy uzyskają wartości swoich indeksów. Choć sposób
ten jest prosty w realizacji, to wstępne uszeregowanie wartości elementów
tablicy nie zawsze musi być pożądane.
20/ 42
Generator liczb pseudolosowych
Notatki
Tablice można zainicjować za pomocą generatora liczb pseudolosowych.
Ten mechanizm za pomocą określonej wartości początkowej i pewnych
wzorów matematycznych wylicza wartości, które wydają się być losowe.
Niestety, badania statystyczne wykazują, że tak nie jest, stąd generator
ten określany jest mianem pseudolosowego. Dla potrzeb tego wykładu lo-
sowość, jaką daje ten mechanizm jest całkowicie wystarczająca, nie nadaje
się ona jednak do poważniejszych zastosowań, takich jak kryptografia.
21/ 42
Generator liczb pseudolosowych
Notatki
Korzystanie z generatora w języku C
W języku C dostępne są cztery pary funkcji zadeklarowanych w pliku
nagłówkowym stdlib.h, umożliwiających korzystanie z generatora liczb
pseudolosowych. Pierwsza para to funkcje srand() i rand(). Pierwsza
przyjmuje jeden argument wywołania typu unsigned int i ustawia go
jako pierwszą wartość ciągu liczb pseudolosowych (tzw. ziarno). Druga nie
przyjmuje żadnych argumentów, ale zwraca liczbę pseudolosową typu int
z zakresu od 0 dorand_max. Dwie kolejne funkcje to srandom(), która
działa tak jak srand() i random(), która podobna jest w działaniu do
rand(), ale zwraca wartości z zakresu typu long int. Zarówno srand(),
jaki i srandom() muszą być wywoływane poza wszelkimi pętlami.
Zazwyczaj jako argument przekazuje się do nich wartość zwróconą przez
funkcję time() zadeklarowaną w pliku nagłówkowym time.h. Zwraca ona
bieżący czas w postaci liczb całkowitej. Jako jej argument wywołania prze-
kazuje się 0 lubnull.
22/ 42
Generator liczb pseudolosowych
Notatki
Sposób użycia
Generator liczb pseudolosowych generuje liczby naturalne. Jeśli chcieliby-
śmy, aby została wylosowana liczba z zakresu od 0 do 9, to możemy użyć
następującego wyrażenia:
int x = random()%10;
Aby zmienić zakres na od 1 do 10 należy zastosować takie wyrażenie:
int x = 1+random()%10;
Jeśli interesuje nas zakres na od -10 do 10, to wyrażenie musi mieć po-
stać:
int x = -10+random()%21;
Jeśli chcemy, aby poprzedni zakres zmienić na przedział (-11,11), to mu-
simy dodać część ułamkową:
double x = -10+random()%21+(double)random()/RAND_MAX;
23/ 42
Generator liczb pseudolosowych
Notatki
Sposób użycia
Aby wylosować małą literę spośród 26 innych należ zastosować takie wy-
rażenie:
char x = 'a'+random()%26;
Te wszystkie przykłady będą również działać, jeśli zamiast random() za-
stosujemy rand().
24/ 42
Inicjacja tablicy
Notatki
Inicjacja tablicy z użyciem liczb pseudolosowych
Poniższa funkcja wypełnia tablice o number_of_elements elementach
liczbami pseudolosowymi z zakresu od 0 do 199:
void fill_array_with_random_numbers(int array[])
{
srand(time(0));
int i;
for(i=0; iarray[i]=rand()%200;
}
Należy zauważyć, że tak losowane wartości mogą się powtarzać.
25/ 42
Inicjacja tablicy
Notatki
Przestawianie
Korzystając z indeksu możemy uzyskać tablicę, której wartości elemen-
tów są uporządkowane rosnąco i nie powtarzają się. Możemy ją zamienić
w tablicę, której wartości elementów się nie powtarzają, ale tworzą nieupo-
rządkowany ciąg stosując algorytm przestawiania (ang. shuffle). Polega on
na przeglądaniu kolejnych elementów takiej tablicy i zamianie ich wartości
z losowo wybranymi elementami, spośród tych, które nie zostały jeszcze
odwiedzone (włączając bieżąco badany). Algorytm ten został zaimplemen-
towany za pomocą kilku funkcji, które będą przedstawione na kolejnych
slajdach.
26/ 42
Inicjacja tablicy
Notatki
Przestawianie - zamiana wartości elementów
Poniższa funkcja zamienia miejscami wartość dwóch zmiennych, które zo-
staną przekazane jako jej argumenty wywołania:
void swap(int *first, int *second)
{
int tmp;
tmp = *first;
*first = *second;
*second = tmp;
}
27/ 42
Inicjacja tablicy
Notatki
Przestawianie - losowanie elementu
Poniższa funkcja losuje indeks elementu tablicy począwszy od bieżącego
(from), a skończywszy na ostatnim (array_length-1):
int choose(int from)
{
return from+rand()%(ARRAY_LENGTH-from);
}
28/ 42
Inicjacja tablicy
Notatki
Przestawienie - implementacja
Poniższa funkcja dokonuje właściwego przestawienia elementów. Proszę
zwrócić uwagę, że wybór drugiego z elementów tablicy, z którym należy
wymienić wartość bieżącego elementu dokonywany jest za pomocą funkcji
choose():
void shuffle(int array[])
{
srand(time(0));
unsigned int i;
for(i=0;iswap(&array[i],&array[choose(i)]);
}
29/ 42
Kopiowanie tablic
Notatki
Dwie tablice o takich samych typach elementów można skopiować przy po-
mocy dowolnej instrukcji iteracyjnej. Jednakże bardziej efektywnym sposo-
bem wykonania tej operacji jest użycie funkcji memcpy() zadeklarowanej
w pliku nagłówkowym string.h. Ta funkcja przyjmuje trzy argumenty
wywołania. Jako pierwszy przekazywana jest nazwa tablicy, do której ko-
piowane będą wartości, jako drugi nazwa tablicy z której będą kopiowane
wartości, a jako trzeci rozmiar kopiowanej tablicy. Należy zadbać, aby ta-
blica kopiowana była równa lub mniejsza rozmiarem od tablicy, do której
następuje kopiowanie. Wartość zwracana przez funkcję memcpy() jest naj-
częściej ignorowana. Z tego samego pliku nagłówkowego, co memcpy()
pochodzi również funkcja memset(). Przyjmuje ona trzy argumenty. Po-
zwala ona skopiować wielokrotnie ustaloną wartość do tablicy. Może ona
być wykorzystana do inicjowania lub zerowania tablic. Ta funkcja przyj-
muje trzy argumenty: nazwę tablicy, na której ma być wykonana operacja,
liczbę typu int, która ma być do niej wpisana i rozmiar tablicy. Wartość
zwracana przez funkcję jest zazwyczaj również ignorowana.
30/ 42
Wypisanie wartości elementów tablicy na ekranie
Notatki
Do indeksowanie poszczególnych elementów tablicy można użyć dowol-
nej instrukcji iteracyjnej, np. pętli for. Zaprezentowana poniżej funkcja
wypisuje na ekran zawartość tablicy o 100 elementach typu int:
void print_array(int array[])
{
unsigned int i;
for(i=0; i<100; i++)
printf("array[%u]: %d ",i,array[i]);
}
Sposób wypisania można też uprościć:
void print_array(int array[])
{
unsigned int i;
for(i=0; i<100; i++)
printf(" %d ",array[i]);
}
31/ 42
Wyszukiwanie wartości minimalnej
Notatki
Algorytm
W niektórych zagadnieniach należy znalez
ć wartość minimalną w nieupo-
rządkowanej tablicy. Algorytm jej wyszukiwania jest stosunkowo prosty:
1. Zapamiętaj w osobnej zmiennej wartość pierwszego elementu tablicy,
jako wartość minimalną.
2. Przeglądaj kolejne elementy tablicy; jeśli któryś z nich ma wartość
mniejszą od tej w zmiennej, to ją w niej umieść; teraz to będzie
wartość najmniejsza.
3. Jeśli odwiedzone zostały wszystkie elementy w tablicy, to wartość
najmniejsza znajduje się w zmiennej.
32/ 42
Wyszukiwanie wartości minimalnej
Notatki
Implementacja
Poniższa funkcja implementuje ten algorytm dla tablicy o liczbie elementów
określonej wartością stałejnumber_of_elements:
int find_min(int *array)
{
int min;
unsigned int i;
min=array[0];
for(i=1; iif(min>array[i])
min=array[i];
return min;
}
33/ 42
Wyszukiwanie wartości maksymalnej
Notatki
Implementacja
Algorytm wyszukiwania wartości maksymalnej w tablicy jest bardzo po-
dobny do wyszukiwania wartości minimalnej - wystarczy zastąpić słowa
 wartość minimalna słowami  wartość maksymalna . Kod funkcji go im-
plementującej różni się od kodu funkcji szukającej wartości minimalnej na-
zwą funkcji, zmiennej oraz znakiem w warunku instrukcji warunkowej:
int find_max(int *array)
{
int max;
unsigned int i;
max=array[0];
for(i=1; iif(maxmax=array[i];
return max;
}
34/ 42
Wyszukiwanie ekstremów
Notatki
A
atwo zauważyć, że w przypadku, gdy potrzebujemy zarówno wartości mi-
nimalnej, jak i maksymalnej, a nie tylko jednej z nich, to korzystniej będzie
będzie szukać ich obu przeglądając tablicę tylko raz, a oba wyniki zwracając
przez parametry funkcji:
void find_exterme_values(int array[], int *min, int *max)
{
unsigned int i;
*max = *min = array[0];
for(i=1; iif(*min>array[i])
*min=array[i];
if(*max*max=array[i];
}
}
35/ 42
Wyszukiwanie określonej wartości w tablicy
Notatki
nieuporządkowanej
Algorytm
Często spotykanym problemem jest lokalizacja wartości w nieuporządko-
wanej tablicy. Jest wiele odmian tego problemu. Nas będzie interesowała
ta, w której należy podać indeks pierwszego elementu od początku tabli-
cy, który zawiera szukaną wartość. Algorytm rozwiązania tego problemu
jest prosty: należy przeglądać kolejne elementy tablicy, aż do napotkania
takiego, który zawiera szukaną wartość. Wówczas należy zwrócić wartość
jego indeksu. Alternatywnie, jeśli żaden element tablicy nie zawiera takiej
wartości, to należy zwrócić określoną wartość, która ten fakt zasygnalizuje
np. -1.
36/ 42
Wyszukiwanie określonej wartość w tablicy
Notatki
nieuporządkowanej
Implementacja
Poniższa funkcja implementuje przedstawiony algorytm:
int find_value_index(int array[], int value)
{
unsigned int i;
for(i=0; iif(array[i]==value)
return i;
}
return -1;
}
37/ 42
Wyszukiwanie wartości w tablicy - druga wersja
Notatki
Algorytm
Jeśli przyjrzymy się poprzedniej funkcji, to zauważymy, że w każdej itera-
cji pętli for sprawdzane są dwa warunki: czy nie został osiągnięty ostatni
element w tablicy oraz czy nie została znaleziona poszukiwana wartość.
Okazuje się, że tę pętlę można uprościć. Choć rozwiązanie jest dosyć za-
skakujące. Należy bowiem umieścić wartości wszystkich sprawdzanych ele-
mentów w tablicy o jeden większej niż wynosi ich liczba, a w nadmiarowym,
ostatnim elemencie tablicy należy umieścić & szukaną wartość! Takie roz-
wiązanie pozwala sprawdzać w pętli jedynie to, czy już nie znaleziono szu-
kanej wartości. Nie ma konieczności sprawdzania, czy nie osiągnięto końca
tablicy. Po zakończeniu pętli wystarczy zbadać, czy wartość zmiennej in-
deksującej jest równa indeksowi ostatniego elementu. Jeśli nie, to znaczy że
szukana wartość wystąpiła wcześniej w tablicy, w elemencie, który określa
zmienna indeksująca. Jeśli tak, to wartość nie wystąpiła wcześniej i należy
zasygnalizować jej brak zwracając liczbę -1.
38/ 42
Wyszukiwanie wartości w tablicy - druga wersja
Notatki
Implementacja
Poniższa funkcja implementuje opisany algorytm:
int faster_find_value_index(int *array, int value)
{
//Tylko w ISO C99!
int larger_array[NUMBER_OF_ELEMENTS+1];
memcpy(larger_array,array,sizeof(array[0])*NUMBER_OF_ELEMENTS);
larger_array[NUMBER_OF_ELEMENTS]=value;
unsigned int i = 0;
while(larger_array[i]!=value)
i++;
return (i!=NUMBER_OF_ELEMENTS)?i:-1;
}
Proszę zwrócić uwagę, że tablica oryginalna jest kopiowana przy pomocy
memcpy(), a z uwagi na to, że jest ona przekazywana przez wskaz
nik, to
jej rozmiar jest określany jako iloczyn rozmiaru jej pierwszego elementu
i stałej określającej liczbę jej elementów.
39/ 42
Podziękowania
Notatki
Składam podziękowania dla dra inż. Grzegorza A
ukawskiego i mgra inż.
Leszka Ciopińskiego za udostępnienie materiałów, których fragmenty zo-
stały wykorzystane w tym wykładzie.
40/ 42
Pytania
Notatki
?
41/ 42
koniec
Notatki
Dziękuję Państwu za uwagę.
42/ 42
Notatki
Notatki


Wyszukiwarka

Podobne podstrony:
PP1 handout 9
PP1 handout 3
AGH Sed 4 sed transport & deposition EN ver2 HANDOUT
PP1 lecture 4
HANDOUT 1
HANDOUT Chronology of polities?c to J ?nning
AGH Sed2 erosion weather etc HANDOUT
PP1 laboratorium 7
DG ćw handout 10 verb complementation
handout booklet
handout4
Zagadnienie2 PrognozaWstep handout
Back vowels handout
Wyklad04 2008 handout
PP1 wyklad
Zajęcia 1 handout
PP1 wyklad 8
Wyklad4 handout

więcej podobnych podstron