DYNAMICZNE STRUKTÓRY DANYCH W WYBRANYCH JĘZYKACH PROGRAMOWANIA
PRACA DYPLOMOWA
SPIS TREŚCI
1. Wstęp
2. Wiadomości ogólne
3. Słowa kluczowe i struktura programu
4. Zmienne, Typy danych
4.1. typy proste
4.2. zmienne wskazujące ( wskaźniki)
4.3. typy strukturalne
4.3.1 struktury występujące w języku C
4.3.2 rekordy występujące w języku Pascal
5. tablice
5.1. tablice i wskaźniki
5.2. tablice wielowymiarowe
6.
7. struktury dynamiczne
7.1. listy
7.1.1. listy jednokierunkowe
7.1.2. listy dwukierunkowe
7.1.3. listy cykliczne
7.2. drzewa
7.3. Grafy
7.4. Stosy
7.5. kolejki
8. przykładowe funkcje i procedury (C, Pascal)
8.1. język programowania C
8.1.1. wstawianie elementu na początek listy jednokierunkowej
8.1.2. wstawianie elementu na koniec listy jednokierunkowej
8.1.3. ?
8.1.4. ?
8.2. język programowania Pascal
8.2.1. procedura tworzenia i dołączania do niego składnika
8.2.2. ?
8.2.3. ?
8. zakończenie .
Rozwiązanie dowolnego zadanie posługując się komputerem, należy skonstruować odpowiedni algorytm, tj. podać zbiór reguł rozwiązania zadania w skończonej liczbie kroków. Każdy algorytm składa się z dwóch zasadniczych części : opisu danych, na których działa, oraz czynności, które są wykonywane na tych danych. Algorytm napisany w języku programowania nazywa się programem, w którym czynności wykonywane na danych są opisane za pomocą odpowiednich instrukcji języka. Zagadnienia te przybliżye w dalszej części pracy.
Od wyboru właściwej w danym momencie struktury danych może zależeć wszystko : szybkość działania programu, możliwość jego łatwej modyfikacji, czytelności zapisu algorytmów i ... dobre samopoczucie programisty.
Każdy kto poznał jakikolwiek język programowania, został niejako zmuszony do opanowania zasad posługiwania się twz. typami podstawowymi. Przykładowo w C mamy do dyspozycji typy :int, long, float, char ,typy wskaźnikowe etc. Mogą one posłużyć jako elementy bazowe rekordów, tablic ,unii, które już zasługują na miano struktur danych. Prawdziwa przygoda rozpoczyna się dopiero, gdy dostajemy do ręki twz. listy, drzewa binarne, grafy... . wraz z nimi rozszerza się znacznie możliwości rozwiązania programowego wielu ciekawych zagadnień; zwiększa się wachlarz potencjalnych zastosowań informatyki. Ogólną nazywają się one dynamiczne struktury danych, i właśnie o tym traktuje ta praca.
Zanim jednak przejdę do szczegółowej charakterystyki dynamicznych struktur, chciałbym wspomnieć o językach programowania za pomocą, których będziemy je tworzyć. W poniższej pracy poruszę również problem struktur statycznych (tablic, rekordów itp.), które będziemy wykorzystywać w dynamicznych strukturach danych.
Turbo Pascal , C są to języki programowania za pomocą których postara się przedstawić i wyjaśnić działanie dynamicznych struktur danych.
Język C jest wysoce modularny, każdy program można zdekompilować na oddzielnie kompilowane moduły z publicznym interfejsem i ukrytą implementacj. I odwrotnie : do każdego programu można dołączyć wcześniej opracowane moduły, przechowywane na dysku. W rezultacie każdy większy program składa się z dwóch rodzajów plików : - plików nagłówkowych, - pliki źródłowych. Implementacje operacji języka C są nazywane funkcjami. Użytkownik może również używać funkcji zewnętrzne, deklarowane i definiowane na zewnątrz.
Turbo Pascal jest jednym z najpopularniejszych języków programowania komputerów. Nie ulega wątpliwości , że język ten jest przyjazny dla początkującego programisty. Pozwoli mi to na przedstawienie mechanizmów zawartych w Pascalu, za pomocą których możemy stworzyć dynamiczne struktury danych. język ten może być również wykorzystywany w procesie tworzenia, analizowania i testowania najróżniejszych programów użytkowych.
W ramach przypomnienia przywołam kilka wiadomości dotyczących Pascal’a i C.
Niektóre identyfikatory zostały zastrzeżone przez twórców języka. Służą one do zapisu konstrukcji jakie są dopuszczalne w danych językach. Dlatego nazywa się je słowami kluczowymi. Słowa kluczowe nie mogą być użyte jako nazwy zmiennych, typów lub funkcji i nie są poprawnymi identyfikatorami .
W języku C występują
następujące słowa kluczowe:
auto double int struct
break else long switch
case enum register typedef
char extern return union
const float short unsigned
continue for signed void
default goto sizeof volatile
do if static while
W języku Pascal występują
and file nil shr
array for not string
asm function object then
begin goto of to
case if or type
const packed unit constructor
in procedure until destructor
inherited program uses div
inline record var do
interface repeat while downto
label set with else
mod shl xor end
Struktury programów :
#include <stdio.h> włączenie informacji o bibliotece standardowej
implementacja funkcji
main() definicja funkcji o nazwie main, która nie
oczekuje żadnych argumentów
{ nawiasy klamrowe otaczają instrukcje funkcji
deklaracje
instrukcje – ciało programu
}
Program nazwa-programu;
User lista-nazwa-modułów;
Definicje-funkcji-i-procedur;
Begin
Instrukcje
End.
Zmienną określany jest pewien obszar w pamięci komputera, w którym mogą być przechowywane dane. Z punktu widzenia osoby piszącej program, zmienna posiada następujące cechy podstawowe:
· nazwa (identyfikator)
· typ
...
klejarka