Typy danych

• Liczby całkowite (integer), przechowywane najczęściej w notacji uzupełnieniowe do dwóch, realizuje się tradycyjne operacje arytmetyczne oraz porównania.

• Liczby rzeczywiste (real) , przechowuje się w postaci zmienno przecinkowej, realizuje się operacje arytmetyczne,

• Dane znakowe (character) przechowuje symbole znakowe, zapisywane w kodzie ASCII lub Unicode. Realizuje się operacje porównania łańcuchów , łączenia łańcuchów poprzez doklejenie jednego z nich na koniec drugiego (operacja konkatenacji),

• Wartości logiczne (boolean), dane mogą przyjmować dwie wartości 0 (false), 1 (true)

Przykładowe typy danych w języku C i C⁺⁺

• Dane znakowe

Danymi znakowymi - char- są pojedyncze litery, cyfry lub inne znaki z klawiatury (cyfra zadeklarowana jako znak nie może być zastosowana w operacjach matematycznych). Każdy znak zapisywany jest w pojedynczej komórce pamięci.

Łańcuch jest to ciąg znaków, np. słowo, wyrażenie, zdanie, może mieć dowolną kombinację liter cyfr ,znaków interpunkcyjnych

• Liczby całkowite

- short int Zajmuje jedną komórkę pamięci, liczba

całkowita (0 do 255).

- int Zajmuje dwie komórki pamięci , liczba

całkowita (-32 768 do 32 767)

- long int Zajmuje cztery komórki, liczba całkowita

między (-2 147 483 648 do 2 147 483 648)

- unsignet long Zajmuje cztery komórki (0 do 4 294 967 295)

• Liczby dziesiętne (zmiennopozycyjne), zapisywane w postaci wykładniczej. (x=m^c, m-mantysa, c-cecha)

-float Zajmuje 4 komórki pamięci. Liczba (3.4*10^-38 do

3.4*10³⁸). W zapisie 5 lub 6 miejsc znaczących.

-double Zajmuje 8 komórek pamięci. Liczba (1.7*10^-308 do

1.7*10³⁰⁸. W zapisie 7 do 13 miejsc znaczących.

-long double Zajmuje 10 komórek pamięci .

Liczba (3.4*10^-4932 do 1.1*10⁴⁹³²)

Struktury danych.

• Pamięć komputera jest zorganizowana w postaci pojedynczych komórek pamięci adresowanych za pomocą kolejnych liczb.

• Korzystniejszym jest w wielu przypadkach korzystać z bardziej naturalnego układu danych, np. tablicy prostokątnej (lista grupy studenckiej - wiersze opatrzone nazwiskami kolumny ocenami).

Konieczne jest zatem umożliwienie użytkownikowi myślenia w kategoriach ich abstrakcyjnej organizacji.

Tablice

Tablica jest zbiorem danych odpowiednio uporządkowanych z punktu widzenia użytkownika.

Tablica jest jednorodna kiedy wszystkie elementy są takiego samego typu.

Powiedzmy, że algorytm operuje na ciągu złożonym z 24 cogodzinnych odczytów prędkości wiatru zgromadzonych w jednowymiarowej tabeli odczyty. Odniesienie do adresów komórek w pamięci jest natychmiastowe. Dane pamiętane są w 24 kolejnych komórkach pamięci

Jeśli zatem pierwsza dana znajduje się w komórce o adresie x to n-ta dana znajduje się w komórce x+(n-1).

Jeżeli dane przechowywane są w postaci nie macierzy prostokątnej a oddzielnych komórkach o kolejnych adresach, to prostokątną strukturę należy zasymulować. Jeżeli danymi są oceny uzyskiwane przez grupę 30 studentów w ciągu 15 tygodni zajęć to można obliczyć pojemność wymaganego bloku pamięci i zarezerwować blok kolejnych komórek pamięci (ciągły blok pamięci).

W tak uzyskanej tablicy dane zapisujemy wiersz po wierszu, czyli zapisujemy wierszami w odróżnieniu kiedy wartości zapisuje się kolumnami.

Jeżeli zatem:

• x jest adresem komórki pamięci zawierającej element z pierwszego wiersza i pierwszej kolumny,

• c jest liczbą kolumn w tablicy,

• to adres elementu i-tego wiersza i j-tej kolumny określa zależność zwana wielomianem adresowym

x+(c (i-1))+(j-1)

Listy

Ustalony rozmiar i kształt tablic umożliwia łatwy dostęp do elementu poprzez zastosowanie wielomianu adresowego. Trudniej jest z dostępem w strukturach dynamicznych, których zarówno rozmiary jak i kształt mogą ulegać zmianom.

n.p. lista członków PKZP, rośnie na skutek zapisywania się nowych i maleje na skutek odchodzenia starych.

Struktura dynamiczna nazywana jest listą

Podstawowym narzędziem stosowanym w implementacji struktur dynamicznych jest wskaźnik.

Po zapamiętaniu danych w pewnej komórce pamięci można także zapamiętać adres tych danych w innej komórce pamięci i użyć później zawartości tej komórki do odnajdywania poszukiwanych danych.

Komórki pamięci zawierające adresy wskazujące na inną komórkę pamięci nazywamy wskaźnikami (pointers).

Charakter wskaźników mają również adresy URL (Uniform Resource Locator) wiążące lokacje hypertekstowe w internecie.

Współczesne języki programowania umożliwiają deklarowanie, alokację i manipulowanie wskaźnikami.

Programista może zatem w pamięci komputera tworzyć złożone sieci danych.

Przykładem są katalogi zbiorów bibliotecznych porządkujące zwykle alfabetycznie pozycje według tytułów. Aby znajdować pozycje według autora( rozrzuco-ne po całej liście) wystarczy zatem w bloku dotyczącym każdej książki umieścić komórkę pamięci typu wskaźnikowego a w każdej z tych komórek umieścić adres kolejnego bloku reprezentującego danego autora.

Listy zwarte

W pamięci komputera przechowywana jest cała lista nazw

w jednym bloku następujących po sobie komórek pamięci.

• Cały blok danych podzielony jest na podbloki o długości n (np. n= 8) komórek pamięci.

• W każdej komórce zapisywana jest nazwa, jeżeli nazwa zawiera mniej niż n znaków pozostałe pola wypełniane są np. spacjami.

Zalety i wady listy zwartej:

• wygodna z powodu prostoty,

• w przypadku usuwania elementów powstają dziury wymagające przesunięcia wszystkich następujących, po usuwanym, elementów aby zapełnić dziurę,

• problemy z dodawaniem nowych nazw do listy, kończące się dość często potrzebą przeniesienia rozszerzonej listy w inne wolne miejsce pamięci.

Listy z dowiązaniami.

Uprzednio sygnalizowanych problemów można uniknąć korzystając ze wskaźników, tworząc listy z dowiązaniami (linked list).

• Każdą nazwę można zapamiętać w bloku n+1 komórek pamięci ( n - komórek zajmuje nazwa, jedną komórkę zajmuje wskaźnik do następnej nazwy na liście).

• Informację o położeniu pierwszego elementu z listy zapamiętuje się zwykle w dodatkowej komórce pamięci nazywanej nagłówkiem.

• Koniec listy z dowiązaniami oznacza się za pomocą wskaźnika NIL, który jest specjalnym ciągiem binarnym,

umieszczonym w ostatnim elemencie listy, w komórce pamięci przeznaczonej na wskaźnik do kolejnego elementu (NIL - słowo kluczowe, wskaźnik który nie wskazuje na żadną wartość)

• Usunięcie nazwy z listy wymaga zmiany tylko wskaźnika, który wskazywał usuwany element i zastąpienie go wskaźnikiem do elementu występującego po elemencie usuwanym.

• W celu wstawienia nowego elementu do listy należy znaleźć blok złożony z n+1 komórek pamięci w pierwszych n - komórkach zapamiętać nazwę a w ostatniej wskaźnik do następnego elementu na liście.

Zmiany wymaga również wskaźnik związany z nazwą, która ma poprzedzać nowy element tak aby został wskazany

Stos

Stos jest to lista, w której wszystkie operacje wstawiania i usuwania wykonuje się na tym samym końcu struktury zwanym wierzcholkiem.

Element wstawiony jako pierwszy do struktury jest z niej jako pierwszy usuwany (struktura LIFO „last-in, first-out”.

• Wkładanie (push) i zdejmowanie (pop) elementów odbywa się tylko na koniec stosu nazywany wierzchołkiem (top) stosu .

Korzystanie ze stosu jest szczególnie istotne w sytuacjach w których przerywana jest realizacja programu głównego i realizowana jest obsługa innej procedury/procedur, po zakończeniu której/ych konieczny jest powrót do lokacji początkowej. Często zdarzają się zagnieżdżone procedury przerwaniowe, które wymagają realizacji ścieżki powrotów do programu głównego.

Implementacja stosu.

• Efektywne wykorzystanie pamięci wymaga określenia rozmiaru ciągłego bloku komórek pamięci, wystarczająco dużego aby zmieścił się w nim cały stos w miarę jego wzrastania i kurczenia się.

• W miarę wkładania i zdejmowania elementów konieczna jest znajomość położenia wierzchołka stosu zapewnia to adres wierzchołka pamiętany w dodatkowej komórce pamięci zwanej wskaźnikiem stosu.

Jeżeli nie da się zarezerwować bloku pamięci tak, aby zapewnić, że stos zawsze się w nim zmieści, to rozwiązaniem jest zastosowanie omawianej poprzednio struktury z dowiązaniami.

Kolejka

Kolejka (queue) jest listą do której dane wstawia się na jednym zakończeniu zwanym „ końcem” lub „ogonem” kolejki natomiast usuwa się dane z „glowy” lub „ początku” kolejki. (FIFO first-in, first-out)

• Kolejka występuje w pamięci komputera jako zwarty blok komórek pamięci.

• Konieczność wykonywania operacji na początku i końcu kolejki wymaga zarezerwowania dwóch dodatkowych komórek pamięci do zapamiętania położenia początku kolejki wskaźnik początku (head pointer) oraz położenia końca kolejki wskaźnik końca (tail pointer)

• Ponieważ poddawana obsłudze programowej jest część kolejki zawarta jest w komórkach określonych wskaźnikami początku i końca, pozostała część kolejki jest niewykorzystywana, a dopisywane kolejne elementy i ich obsługa skutkują zwiększaniem obszaru martwego

Można tego uniknąć wprowadzając kolejkę cykliczną.

Blok pamięci w której znajduje się kolejka przypomina pętlę; ostatnia i pierwsza komórka tej pętli sąsiadują z sobą. A operacje na poszczególnych komórkach pamięci dotyczą obszaru pomiędzy wskaźnikami początku i końca.

Oprócz zbioru komórek pamięci wykorzystywanych do pamiętania elementów kolejki, implementacja kolejki powinna zawierać:

• zestaw procedur za pomocą których realizuje się wstawianie elementów do kolejki,

• zestaw procedur za pomocą których realizuje się usuwanie elementów z kolejki,

• zestaw procedur sprawdzających zapełnienie.

Drzewa

Jest to struktura hierarchiczna odzwierciedlająca strukturę organizacyjną dowolnej firmy.

• węzeł drzewa - element w którym schodzą się gałęzie,

• węzeł w wierzchołku to korzeń drzewa,

• węzły znajdujące się po przeciwnych końcach gałęzi to liście,

• węzeł razem z węzłami znajdującymi się pod nim tworzą poddrzewa,

• bezpośredni potomkowie węzła to jego dzieci,

• bezpośredni przodek węzła to rodzic,

• węzły o tym samym ojcu to rodzeństwo,

• głębokość drzewa to liczba węzłów na najdłuższej ścieżce od korzenia do liścia.

Drzewa binarne

Drzewa binarne to takie drzewa w których każdy węzeł posiada co najwyżej dwójkę dzieci

1.Drzewa binarne można przechowywać w pamięci w postaci struktury z dowiązaniami.

Każdy węzeł drzewa binarnego ma trzy składowe:

• dane,

• wskaźnik do pierwszego dziecka węzła (wskaźnik lewego dziecka),

• wskaźnik do drugiego dziecka węzła (wskaźnik prawego dziecka)

Zapamiętanie drzewa wymaga znalezienia wolnych bloków komórek pamięci, w których:

• należy zarezerwować miejsce na wskaźnik korzenia,

• można zapamiętać węzły i powiązania węzłów za pomocą wskaźników,

• wskaźnik musi wskazywać lewe dziecko lub prawe dziecko, lub mieć przypisaną wartość NIL, jeżeli w drzewie nie ma już węzłów.

• liście są zatem węzłami, których oba wskaźniki są równe NIL,

2.Drzewa binarne można również przechowywać w pamięci w postaci ciągłego bloku komórek pamięci.

• W pierwszej komórce bloku zapamiętujemy wskaźnik do korzenia,

• Lewe dzieci węzła pamiętanego w komórce n znajdują się w komórkach 2n,

• Prawe dzieci węzła n znajdują się w komórkach 2n+1,

• Komórki, które reprezentują lokacje niewykorzystane przez bieżącą strukturę drzewa markuje się za pomocą ciągu bitów oznaczającego brak danych,

Pozwala to w łatwy sposób znajdować poszukiwane dane.

• Lokację rodzica danego węzła uzyskuje się dzieląc położenie tego węzła przez dwa bez reszty (rodzicem węzła E jest węzeł B)

• Lokację rodzeństwa danego węzła można określić dodając 1 jeśli numer jest parzysty lub odejmując 1 jeśli numer jest nieparzysty (rodzeństwem dla węzła B jest węzeł C)

W przypadku drzew z dowiązaniami proces wyszukiwania lokacji wymaga wstawienia dodatkowych wskaźników.

Wyszukiwanie lokacji bez wykorzystywania wskaźników jest efektywne jeżeli drzewa danych są w miarę zrównoważone (pod korzeniem oba poddrzewa mają tę samą głębokość) metoda staje się nieefektywna w przypadku drzew niezrównoważonych.

Pakiet implementujący drzewa binarne

Procedury oraz obszar pamięci zarezerwowany do pamiętania drzewa tworzą pakiet z którego korzysta się później jak z narzędzia abstrakcyjnego.

Rozpatrzmy problem przechowywania listy nazw w porządku alfabetycznym.

Załóżmy , że potrzebne nam są następujące operacje na listach:

• wyszukiwanie (search) wskazanego elementu,

• wstawienie (insert) nowego elementu,

• wypisanie (print) listy alfabetycznie.

Jednym z możliwych algorytmów jest algorytm poszukiwania binarnego (Patrz 2-gi wykład) opierający się na zasadzie odnajdywania środkowego elementu coraz mniejszych fragmentów listy. Najłatwiej zrobić to na liście zwartej ale do takiej listy bardzo trudno wstawiać nowe elementy (patrz listy zwarte). Korzystniej jest pamiętać listy w strukturze z dowiązaniami.

• Środkowy element listy umieszczamy w korzeniu,

• Środkowy element lewej połowy umieszczamy w lewym dziecku korzenia,

• Środkowy element drugie polowy w prawym dziecku korzenia,

• Środkowe elementy wszystkich pozostałych ćwiartek listy stają się dziećmi korzenia itd.

• Proces sprawdzania wartości i przechodzenia do dziecka powtarza się aż do znalezienia poszukiwanej wartości (sukces) lub dojścia do ostatniego liścia drzewa bez sukcesu.

Wypisywanie alfabetyczne listy dla przypadku kiedy elementy lewego poddrzewa są mniejsze od korzenia a prawego większe od korzenia sprowadza się do alfabetycznego uporządkowania;

• lewego poddrzewa,

• wypisania korzenia,

• uporządkowania alfabetycznego prawego poddrzewa.

Wstawianie nowego elementu

Aby wstawić nowy element do drzewa porusza się analogiczną ścieżką jak podczas jego wyszukiwania, ponieważ element jest nieobecny w drzewie wyszukiwanie doprowadzi na sam dół drzewa do miejsca lokacji nowego węzła

Wyspecjalizowane typy danych,

Podstawowe typy danych liczby całkowite, rzeczywiste, znaki, wartości logiczne są dość ubogie w praktycznych zastosowaniach.

Typy definiowane przez użytkownika

Współczesne języki umożliwiają definiowanie własnych typów danych typów definiowanych przez użytkownika

Np. dane personalne zawarte w zmiennej osoba o niejednorodnej strukturze można zdefiniować w postaci typu zdefiniowanego przez użytkownika.

W języku C⁺⁺ wymaga to napisania

typedef struct

{ char Nazwisko [10];

char Imię [10];

char Pesel [11];

char sex [1];

int wiek ;

float umiejętności:

} Tosoba;

Do programu można zatem wprowadzić zmienne dotyczące czterech osób,

Tosoba adas, stas, zosia, lusia;

Mówimy że skonstruowano cztery instancje tego typu o nazwach adas, stas, zosia, lusia.

Abstrakcyjne typy danych

Abstrakcyjny typ danych określa:

• sposób reprezentacji, pamiętania danych.

• Procedury, definiujące operacje, które można wykonywać na instancjach tego typu.

Przykład abstrakcyjnego typu danych o nazwie StosLiczbCałkowitych przedstawiony jako moduł programu w języku ADA. Moduł ten (zwany w ADZIE pakietem) o nazwie PakietStosowy zawiera opis nowego typu o nazwie

StosLiczbCałkowitych oraz określa dwie procedury: włóż zdejmij. Typ zdefiniowano jako tablicę ElementyStosu złożoną z 25 liczb całkowitych oraz liczby wskaźnik stosu wykorzystywany do zapamiętania wierzchołka stosu.

Szczegóły procedur włóż i zdejmij trzeba zaprogramować w innym module, zwanym treścią pakietu.

Powyższy pakiet to wzorzec stosów. Deklaracja 2 przykładowych instancji wygląda następująco:

StosPierwszy: StosLiczbCałkowitych;

StosDrugi: StosLiczbCałkowitych;

Element z wierzchołka można zdjąć za pomocą:

zdejmij (StaraWartość, StosPierwszy)

a włożyć liczbę 257 na stos drugi

włóż (257, StosDrugi)

Kapsułkowanie danych

Pakiet programowy zawierający struktury danych i zestaw procedur do obsługi tych struktur. Profesjonalna obsługa takich elementów jak stos kolejka, lista, drzewo wymaga korzystania z załączonych procedur. Zawsze istnieje jednak pokusa dotarcia przez mało profesjonalnego programistę na skróty do określonych danych, wpisania na skróty określonych danych. Taka praktyka jest naganna z punktu widzenia Inżynierii Oprogramowania, ponieważ prowadzi do kłopotów w późniejszych fazach „życia” i pielęgnacji oprogramowania.

Integralność danych jest chroniona przed źle wykonywanymi modyfikacjami poprzez kapsułkowanie danych.

Kapsułkowanie danych, polega na takiej konstrukcji pakietu, że dostęp do jego wewnętrznej struktury jest możliwy jedynie za pomocą ustalonych procedur pakietu

W przedstawionym pakiecie kapsulkowanie polega na przeniesieniu wszystkich szczegółów dotyczących struktury stosu do części prywatnej (private) pakietu. Informacje w części prywatnej są dostępne tylko lokalnie dla pakietu.

Z zewnątrz pakietu widoczna jest informacja z części publicznej, widać że na zewnątrz istnieją tylko:

• Typ StosLiczbCałkowitych,

• Procedury włóż i zdejmij,

Fakt że stos zaimplementowano jako tablicę ElementyStosu ukryty jest w pakiecie instrukcji

Klasy.

Zarówno pakiety jak i klasy wykorzystują łączenie struktur danych z procedurami manipulującymi na tych procedurach w pakiety. Można je wykorzystywać jako narzędzia abstrakcyjne w różnych miejscach programu.

Główna różnica tkwi w elastyczności klasy, która może zawierać również:

• tylko procedury,

• tylko struktury danych,

• oba te elementy,

• żaden z nich,

• języki obiektowe oferują definiowanie klas za pomocą innych klas stosując dziedziczenie.

Paradygmat obiektowy może pewnego dnia stać się metodą, dzięki której będzie można konstruować duże oprogramowanie ze wstępnie przygotowanych elementów, którymi są klasy.

Inżynieria oprogramowania

Zajmuje się wszelkimi aspektami produkcji oprogramowania: od analizy i określenia wymagań, przez projektowanie i wdrożenie, aż do ewolucji gotowego oprogramowania. Podczas gdy informatyka zajmuje się teoretycznymi aspektami produkcji oprogramowania, inżynieria oprogramowania koncentruje się na stronie praktycznej.

1

---