Wykład II
Typ danych, proste typy
danych
Algorytmy i struktury danych
Wyższa Szkoła Biznesu
Semestr III Informatyka
stosowana
2
Abstrakcyjny model
Maszynę cyfrową wynaleziono w celu ułatwienia i
przyspieszenia obliczeń.
W większości je obecnych zastosowań większe
znaczenie ma możliwość przechowywania i dostępu
do dużych partii informacji, natomiast sama
pierwotnie uzyskana zdolność wykonywania obliczeń
wydaje się nieistotna.
We wszystkich tych przypadkach duże partie
informacji,
które
mają
być
przetwarzane,
reprezentują – w pewnym sensie – abstrakcyjny
model części świata rzeczywistego.
3
Model - uproszczenie
zbioru faktów
Informacja dostępna komputerowi stanowi pewien
wybrany zbiór danych o świecie rzeczywistym,
mianowicie zbiór danych uznanych za istotne dla
rozważanego problemu, tj. taki, co do którego ma
się przekonanie, że za jego pomocą można uzyskać
pożądane wyniki.
Dane te reprezentują model abstrakcyjny w tym
sensie,
że
pewne
właściwości
obiektów
rzeczywistych są ignorowane, ponieważ nie są
związane z badanym problemem.
Stosowany
model
jest
zatem
pewnym
uproszczeniem zbioru faktów.
4
Przykład - kartoteka
pracowników
Każdy
pracownik
jest
(abstrakcyjnie)
reprezentowany w kartotece przez zbiór danych
potrzebnych bądź to pracodawcy, bądź do
prowadzenia jego rozliczeń podatkowych.
Zbiór ten może zawierać pewne informacje
identyfikujące zatrudnionego np.. jego nazwisko
i imię czy też wysokość uposażenia.
Jednakże nie będzie on zwykle zawierał
nieistotnych tu informacji takich jak kolor
włosów, wzrost, czy waga.
5
Wybór modelu
abstrakcyjnego
Przy
rozwiązywaniu
rzeczywistych
problemów (przy pomocy komputera, bądź
bez niego) trzeba dokonywać wyboru
abstrakcyjnego modelu rzeczywistości,
czyli zdefiniować zbiór danych mających
reprezentować rzeczywistą sytuację.
Wybór ten powinien być podporządkowany
problemowi, który ma być rozwiązany.
6
Wybór reprezentacji
informacji
Potem (po wyborze modelu abstrakcyjnego)
następuje wybór reprezentacji tych informacji.
Ten wybór jest z kolei podyktowany narzędziem,
które służy do rozwiązania problemu, czyli
możliwościami komputera.
Trzeba również brać pod uwagę operacje, które
mają być wykonywane na danych. (np. z punktu
widzenia dodawania małych licz mogła by być
wygodna inna reprezentacja niż w wypadku
mnożenia czy dodawania dużych liczb).
7
Przykład – decyzje
podejmowane dla wyboru
sposobu reprezentowania
pozycji obiektu
Pierwsza decyzja może dotyczyć wyboru jako reprezentacji
pary liczb stanowiących współrzędne kartezjańskie, bądź
biegunowe.
Druga decyzja może prowadzić do reprezentacji
zmiennopozycyjnej, gdzie każda liczba rzeczywista x
(współrzędna) składa się z pary liczb całkowitych
oznaczających ułamek f i wykładnik e przy pewnej
podstawie (np. x=f·2
e
).
Kolejna decyzja – wynikająca ze świadomości, że dane
trzeba przechowywać w pamięci maszyny cyfrowej – może
prowadzić do dwójkowej, pozycyjnej reprezentacji liczb.
Ostatnią decyzją może być sposób realizacji reprezentacji
(np. zapis za pomocą strumienia magnetycznego).
8
Nie musimy sami
podejmować wszystkich
decyzji
Pierwsza z decyzji zależy od problemu, natomiast
następne zależą coraz bardziej od stosowanego
narzędzia i jego technologii.
Nie można żądać od programisty (na szczęście) by
podejmował decyzje o sposobie reprezentowania liczb
czy
wręcz
o
charakterystyce
urządzenia
przechowującego informacje.
Takie decyzje na „niskim szczeblu” zostawia się
projektantom komputerów, którzy mają najwięcej
potrzebnych
informacji
na
temat
stosowanych
technologii i mogą podjąć najbardziej sensowne decyzje
odpowiednie dla wszystkich (bądź prawie wszystkich)
zastosowań, w których odgrywa rolę pojęcie liczby.
9
Język programowania –
maszyna abstrakcyjna
Na tym tle widać wyraźnie znaczenie języków
programowania. Język programowania reprezentuje
bowiem pewną abstrakcyjną maszynę, która rozumie
występujące w nim terminy, stanowiące pewien
wyższy poziom abstrakcji w stosunku do obiektów
używanych przez rzeczywisty komputer.
Programista używając takiego języka „wyższego
poziomu” jest więc uwolniony od problemów
reprezentacji liczb (choć w pewnym sensie zostaje też
stosowaną
reprezentacją
skrępowany),
jeśli
oczywiście liczba należy do elementarnych obiektów
danego języka.
10
Pod spodem jednak masa
bitów,
ale nas to zwykle nie
interesuje
Znaczenie używania języka oferującego odpowiedni zbiór
podstawowych
pojęć
abstrakcyjnych
wspólnych
dla
większości problemów przetwarzania danych polega głównie
na niezawodności programów wynikowych.
Łatwiej napisać program przy użyciu znanych pojęć liczb,
zbiorów, ciągów, czy powtórzeń (iteracji) zamiast bitów,
słów czy skoków.
Oczywiście komputer będzie reprezentował wszystkie dane
– zarówno liczby, zbiory, jak i ciągi – jako wielką masę bitów.
Fakt ten jest jednak dotąd nieistotny dla programisty, jak
długo nie musi się on interesować problemem reprezentacji
wybranych przez siebie pojęć i dopóki może być pewien, że
odpowiednie reprezentacje w komputerze (czy translatorze)
są wystarczając do jego celów.
11
Abstrakcyjne pojęcia
winny być jednak „bliskie”
komputerowi
Dokonanie przez inżyniera (czy twórcę translatora)
odpowiedniego wyboru jest tym łatwiejsze, im
bliższe
danemu
komputerowi
są
pojęcia
abstrakcyjne.
Zwiększa
się
wówczas
również
prawdopodobieństwo, że pojedynczy wybór będzie
odpowiedni dla prawie wszystkich zastosowań.
Fakty te ograniczają w pewien sposób możliwe
oddalenie poziomu abstrakcji używanych pojęć od
danego komputera.
12
Wszystkie dane mają
swoje typy
W matematyce zmienne klasyfikuje się zgodnie z ich pewnymi
istotnymi właściwościami.
Rozróżnia się zmienne rzeczywiste, zespolone i logiczne lub
też zmienne reprezentujące pojedyncze wartości, zbiory
wartości, zbiory zbiorów, a także funkcje, funkcjonały, zbiory
funkcji, itd.
W przetwarzaniu danych klasyfikacja zmiennych jest pojęciem
równie ważnym (jeśli nie ważniejszym).
Każda stała, zmienna, wyrażenie, czy funkcja jest
pewnego typu.
Typ ten dokładnie charakteryzuje zbiór wartości, do którego
może należeć stała, bądź jakie może przyjmować zmienna czy
wyrażenie, bądź jakie mogą być generowane przez funkcję.
13
Deklaracja typu
W tekstach matematycznych można zazwyczaj określić
typ zmiennej na podstawie kroju czcionki, jaką ją
oznaczamy.
W programach komputerowych nie jest to możliwe
ponieważ stosujemy jeden ogólnie dostępny krój
czcionek.
Szeroko przyjęto zatem stosowanie zasady, że typ danej
podaj się explicite w deklaracji stałej, zmiennej czy
funkcji oraz że deklaracja ta poprzedza w tekście
programu użycie owej stałej, zmiennej czy funkcji.
Zasada ta jest szczególnie istotna, jeśli się zwróci uwagę
na fakt, że kompilator musi dokonać wyboru
reprezentacji obiektów wewnątrz pamięci maszyny.
14
Od zakresu wartości
zależy wielkość
potrzebnego obszaru
pamięci
Oczywiście wielkość obszaru pamięci
przydzielonego zmiennej należy wybrać
odpowiednio do zakresu wartości, które ta
zmienna może przyjmować.
Jeśli informacje o zakresie wartości są
znane kompilatorowi można uniknąć, tzw.
dynamicznej alokacji pamięci, co jest
kluczem
do
efektywnej
realizacji
algorytmu.
15
Cechy charakterystyczne
pojęcia typu
Typ danych określa zbiór wartości, do którego należy stała
bądź które może przyjmować zmienna lub wyrażenie albo
które mogą być generowane przez operator lub funkcję.
Typ wartości oznaczonej przez stałą, zmienną lub wyrażenie
można określić na podstawie ich postaci bądź deklaracji ,
bez konieczności wykonywania procesu obliczeniowego.
Każdy operator lub funkcja ma argumenty ustalonego typu,
jak również daje wynik ustalonego typu. Jeśli operator
dopuszcza argumenty wielu typów (np. „+” oznacza
dodawanie zarówno liczb całkowitych jak i rzeczywistych), to
typ uzyskiwanego wyniku jest określany za pomocą
specyficznych dla danego języka reguł.
16
Typy nadają monotonnym
bitom interpretację
W konsekwencji kompilator może korzystać z informacji o
typach w celu sprawdzenia poprawności wielu konstrukcji.
Na przykład przypisanie wartości logicznej (prawda-fałsz) do
zmiennej arytmetycznej (liczba) może zostać wykryte bez
potrzeby wykonywania programu, na etapie jego kompilacji.
Ten rodzaj redundancji w tekście programu jest niezwykle
pomocny przy tworzeniu programów i należy go uznać za
podstawową zaletę dobrych języków programowania wysokiego
poziomu (w stosunku do kodu maszynowego czy też kodu
adresów symbolicznych).
Ostatecznie dane w pamięci będą stanowiły jednolitą masę
bitów bez jakiejkolwiek struktury. Jednakże to właśnie ta
struktura abstrakcyjna umożliwia programistom rozpoznawać
znaczenie danych w monotonnym krajobrazie pamięci maszyny.
17
Wartości i typy składowe,
typ podstawowy
Nowe typy w większości języków programowania
definiuje
się
za
pomocą
typów
danych
zdefiniowanych wcześniej.
Wartości
takiego
nowego
typu
są
zwykle
konglomeratami
wartości
składowych
(component values) o pierwotnie zdefiniowanych
typach składowych (constituent types) i mówi się,
że są one ustrukturowane.
Jeśli występuje tylko jeden typ składowy, tzn.
wszystkie składowe są tego samego typu to ów typ
nazywa się typem podstawowym (base type).
18
Moc typu
Liczbę różnych wartości należących
do typu T nazywa się mocą
(cardinality) T.
Moc typu pozwala określić wielkość
pamięci
potrzebnej
do
reprezentowania zmiennej x typu T.
19
Typy wyliczeniowe
Ponieważ typy składowe również mogą być
ustrukturyzowane itd. tworzy się więc w rezultacie
całe hierarchie struktur; niemniej oczywiście
elementarne składowe muszą być atomowe.
Potrzebna jest więc pewna notacja służąca do
określenia
takich
typów
prostych
nieustrukturyzowanych.
Narzuca
się
metoda
polegająca na wyliczeniu wartości tworzących typ.
Np. w programie dotyczącym figur geometrycznych
można określić typ prosty o nazwie kształt, którego
wartości mogą być oznaczone identyfikatorami
prostokąt, kwadrat, elipsa, okrąg.
20
Typy standardowe
Oprócz takich typów definiowanych
przez programistę muszą istnieć
pewne typy standardowe (standard
types),
które
są
zdefiniowane
wcześniej
(przez
producenta
kompilatora).
Na ogół typy standardowe zawierają
liczby i wartości logiczne.
21
Typy uporządkowane i
skalarne
Jeśli wartości typu są uporządkowane,
to
typ
będziemy
nazywali
uporządkowanym
(porządkowym,
ordered) lub skalarnym (scalar).
W przypadku typu wyliczeniowego
przyjmuje
się,
że
wartości
są
uporządkowane zgodnie z kolejnością
ich wyliczenia.
22
Strukturalizacja typów
Przyjmując powyższe zasady, możemy definiować typy
proste, następnie zaś budować konglomeraty – typy
złożone, o dowolnym stopniu zagnieżdżenia.
W rzeczywistości nie wystarczy dysponować tylko jedną
ogólną metodą tworzenia typów złożonych. W związku z
różnymi praktycznymi problemami reprezentacji i
zastosowań
język
programowania
ogólnego
przeznaczenia
powinien
oferować
wiele
metod
strukturalizacji typów danych.
W sensie matematycznym wszystkie te metody mogą
być równoważne; różnice polegają na wyborze
operatorów stosowanych do konstruowania wartości i
wybierania składowych tych wartości.
23
Podstawowe statyczne
struktury danych
Podstawowymi strukturami danych
złożonych są:
tablica,
rekord,
zbiór,
i ciąg (plik).
24
Struktury dynamiczne
Bardziej wyrafinowane struktury nie są zwykle
definiowane jako typy „statyczne”, lecz są
„dynamiczne” generowane podczas wykonania
programu i mogą w tym procesie zmieniać swój
kształt i rozmiary.
Będziemy na dalszych wykładach omawiać te
struktury. Są to
– listy,
– pierścienie,
– drzewa,
– i ogólne grafy skończone.
25
Operatory i ich składanie
Zmienne i ich typy wprowadza się do programu w celu
użycia ich w obliczeniach. W związku z tym musi istnieć
pewien podzbiór operatorów.
Dla
standardowych
typów
danych
w
językach
programowania proponuje się pewną liczbę prostych,
standardowych (atomowych) operacji wraz z pewną liczbą
metod ich składania (tworzenia operacji złożonych) za
pomocą proponowanych operatorów prostych.
Problem składania operacji uważa się często za esencję
sztuki programowania. Jednakże w trakcie wykładów
okaże się, że właściwe, trafne składanie danych jest
problemem równie podstawowym, jak i ważnym.
26
Operatory proste
Porównanie i przypisanie
Najważniejszymi
operatorami
prostymi
są
porównanie i przypisanie, tzn. test na równość (i
uporządkowanie w wypadku typów skalarnych)
oraz instrukcja narzucająca równość.
Istnieje fundamentalna różnica między tymi
operatorami stąd większość języków programowania
stosuje dwa różne oznaczenia.
Te dwie podstawowe operacje definiuje się dla
większości typów danych, ale należy zaznaczyć, że
ich wykonanie może się wiązać, ze znaczną stratą
czasu wykonania, jeśli dane są duże i/lub mają
złożoną strukturę.
27
Konwersje typów
Oprócz testu na równość (czy na uporządkowanie) i
przypisania wprowadza się klasę fundamentalnych operacji
zwanych operacjami konwersji typów.
Są one odwzorowaniami typów danych na inne typy (są
szczególnie istotne w przypadku typów złożonych).
Wartości
złożone
generuje
się
za
pomocą
tzw.
konstruktorów, a wartości składowe wybiera się za pomocą
tzw. selektorów.
Konstruktory i selektory stanowią więc operacje konwersji
typów będące funkcjami typów składowych na typy złożone i
vice versa.
Każda metoda strukturalizacji będzie się wiązała z określoną
parą złożoną z konstruktora i selektora, o wyraźnie odrębnych
oznaczeniach.
28
Typy wyliczeniowe
(enumerated)
W wielu programach stosuje się liczby
całkowite
wtedy,
gdy
właściwości
numeryczne nie są potrzebne, a liczba
całkowita reprezentuje wybór spośród pewnej
małej liczby wartości.
W tych wypadkach dobrze jest wprowadzić
nowy prosty typ danych T, wyliczając zbiór
wszystkich możliwych wartości c
1
, c
2
, ..., c
n
.
T=(c
1
, c
2
, ..., c
n
)
Mocą typu T jest wartość funkcji moc(T)=n .
29
Przykłady typów
wyliczeniowych
kształt=(prostokąt, kwadrat, elipsa, okrąg)
kolor=(czerwony, żółty zielony)
płeć=(mężczyzna, kobieta)
Boolean=(false, true)
dzieńtygodnia=(poniedziałek, wtorek, środa, czwartek, piątek,
sobota, niedziela)
waluta=(euro, funt, dolar, korona, rubel, jen)
przeznaczenie=(piekło, czyściec, niebo)
środeklokomocji=(pociąg, autobus, samochód, statek, samolot)
ranga=(szeregowiec,
kapral,
sierżant,
porucznik,
major,
pułkownik, generał)
obiekt=(stała, typ, zmienna, procedura, funkcja)
struktura=(plik, tablica, rekord, zbiór)
30
Typy wyliczeniowe
są bardziej obrazowe
Definicja typu wyliczeniowego wprowadza nie tylko nowy
identyfikator typu, ale jednocześnie zbiór identyfikatorów
oznaczających poszczególne wartości definiowanego typu.
Identyfikatorów tych można używać w programie jako
stałych, a ich wystąpienia czynią program bardziej
zrozumiałym.
Wprowadźmy na przykład zmienne r: ranga czy p: płeć.
Możliwe
wówczas
są
przypisania
p:=mężczyzna;
r:=major.
Są one bardziej obrazowe niż ich numeryczne odpowiedniki
p:=0; r:=4 oparte na założeniu, że do oznaczeń używamy
liczb naturalnych według kolejności ich wyliczania.
31
Uporządkowanie w typach
wyliczeniowych
Ponadto translator może dzięki temu
wykrywać „nierozważne” stosowanie
operatorów do typów nienumerycznych
np. p:=p+1;
Wprowadza się jednak operatory funkcji
generujących
następnik
bądź
poprzednik argumentu.
Uporządkowanie
wartości
typu
te
określa następująca reguła (c
i
<c
j
)
(i<j)
32
Standardowe typy proste
Standardowe typy proste są to takie
typy, które na większości maszyn
cyfrowych występują jako „możliwości
wbudowane”.
Należą do nich
– zbiór liczb całkowitych,
– zbiór wartości logicznych,
– zbiór znaków alfanumerycznych,
– zbiór liczb rzeczywistych.
33
Typ całkowity
Typ Integer stanowi podzbiór wszystkich liczb
całkowitych, którego zakres zależy od możliwości
danej maszyny.
Jednakże zakłada się, że wszystkie operacje na
danych tego typu są dokładne i odpowiadają
podstawowym
prawom
arytmetyki
oraz,
że
wykonanie programu zostanie przerwane jeśli wynik
znajdzie się poza reprezentowanym podzbiorem.
Standardowe operatory dostarczają tu czterech
podstawowych
operacji:
dodawania
(+),
odejmowania (-), mnożenia (*) i dzielenia (div)
34
Typ rzeczywisty
Oznacza pewien podzbiór liczb rzeczywistych. Podczas
gdy zakłada się, że arytmetyka liczb całkowitych daje
wyniki dokładne, to dla arytmetyki liczb rzeczywistych
dopuszcza się wyniki niedokładne w ramach pewnych
błędów zaokrąglenia spowodowanych wykonywaniem
obliczeń na skończonej licznie cyfr.
Jest to zasadniczy powód dla którego w większości
języków programowania wyraźnie odróżnia się typy
całkowite i rzeczywiste.
Oferowany zestaw działań jest tożsamy z zestawem
zdefiniowanym dla liczb całkowitych, z tym że dzielenie
oznacza się symbolem / oznaczającym dzielenie
zwracające wartość rzeczywistą
.
35
Typ logiczny
Dwie wartości standardowego typu logicznego są
najczęściej oznaczane identyfikatorami false i
true.
Do operatorów logicznych zaliczamy koniunkcję
(, and, iloczyn logiczny), alternatywę (, or,
sumę logiczną) i negację (~, not).
p
q
pq
pq
~p
true
true
true
true
false
true
false
true
false
false
false
true
true
false
true
false
false
false
false
true
36
Porównania dają wyniki typu
logicznego
Zauważmy,
że
zastosowanie
operatora
porównania daje wynik typu logicznego.
W związku z tym wynik porównania może być
przypisany do zmiennej logicznej bądź użyty
jako argument operatora logicznego.
Np. dla zmiennych p i q typu logicznego i
zmiennych całkowitych x=5, y=8, z=10 dwie
instrukcje przypisania: p:=x=y i p:=(x<y)
(yz) dają w rezultacie p=false i q=true.
37
Typ znakowy
Obejmuje zbiór znaków alfanumerycznych.
Niestety jak mówiliśmy na poprzednim wykładzie
nie istnieje ogólnie przyjęty standardowy zbiór
znaków stosowany we wszystkich systemach
komputerowych.
Typ znakowy najczęściej reprezentuje obecnie dane
z kodu ASCII (bądź jednego z jego narodowych
wariantów). Nie należy jednak tego uznawać za
niezmiennik i sposób kodowania zależy od
konkretnego komputera i zainstalowanego na nim
systemu operacyjnego, a nawet od stosowanego
oprogramowania.
38
Założenia dotyczące
zbioru znaków
Aby konstruować niezależne od komputera algorytmy, w
których korzysta się ze znaków musimy przyjąć pewne
założenia dotyczące typu znakowego:
Zawiera znaki łacińskie, cyfry arabskie i pewną liczbę innych
znaków graficznych, jak np. znaki przystankowe.
Podzbiory liter i cyfr są uporządkowane i spójne, tzn.
– (‘A’x) (x‘Z’)x jest literą
– (‘0’x) (x‘9’)x jest cyfrą
Zawiera znak pusty (spację), którego można używać jako
separatora.
W większości języków wprowadza się wzajemnie odwrotne
funkcje pozwalające dokonywać konwersji typu znakowego
na całkowity i odwrotnie.
39
Typy okrojone
Często się zdarza, że zmienna przyjmuje
wartości jedynie z pewnego przedziału wartości
określonego typu.
Wyraża się to definiując typ okrojony, zgodnie
z formatem T=min..max, gdzie min i max
stanowią granice przedziału.
Przykłady
– rok=1900..2099
– litera=‘A’..’Z’
– cyfra=‘0’..’9’
– oficer=porucznik..generał
40
(nie) Dozwolone użycie
typu okrojonego
Dla zmiennych y: rok i L: Litera
– dozwolone są przypisania y:=1973 i
L:=‘W’
– natomiast niedozwolone y:=1291 i
L:=‘9’.
Dopuszczalność przypisań y:=i czy L:=c,
gdzie i jest liczbą całkowitą, a c wartością
znakową można sprawdzić dopiero podczas
wykonania programu.