struktura programu pascal.doc

Struktura programu

Wiemy już, w jakiej formie będziemy przechowywać informację; kolejnym krokiem jest ustalenie sposobu jej przetwarzania odpowiedniego do używanych w programie struktur danych. Przede wszystkim musimy zatem ustalić, jakie operacje na danych program powinien wykonywać, a następnie zaprojektować odpowiadające im procedury lub funkcje (jako że programujemy porządnie, czyli strukturalnie - wykorzystując procedury i funkcje). Po skonsultowaniu się z listą życzeń (zobacz strona 75) stwierdzamy, że nasz program powinien umożliwiać:

wprowadzenie zawartości wybranego rekordu z klawiatury;

wyprowadzenie zawartości wybranego rekordu na ekran;

zbadanie i zmianę zawartości pola Wypozyczajacy wybranego rekordu;

wyszukanie rekordu zawierającego zadany ciąg znaków w polu Tytul;

posortowanie tablicy rekordów według zadanego kryterium (tytuł lub nazwisko autora);

wyszukanie rekordu o najmniejszej i największej zawartości pola Licznik.

Powyższa lista może zostać bezpośrednio przetłumaczona na zestaw podstawowych procedur tworzących program (rzecz jasna, trzeba będzie jeszcze dorzucić kilka procedur pomocniczych, no i oczywiście część operacyjną). Z formalnego punktu widzenia wymagany jest jeszcze schemat blokowy lub przynajmniej słowny zapis algorytmu, aby jednak uniknąć przerostu formy nad treścią, ograniczymy się do ogólnego schematu działania programu:

wyświetl menu dostępnych operacji

w zależności od wybranej opcji:

wprowadź nowy rekord (dodanie książki do katalogu), lub

zmień zawartość pola Wypozyczajacy (wypożyczenie książki), lub

wyszukaj rekord zawierający dany tytuł (wyszukiwanie książki), lub

wyświetl wszystkie rekordy uporządkowane według tytułów lub nazwisk autorów, lub

zakończ pracę programu

wróć do punktu (1)

Jak widać, część operacyjna sprowadza się w zasadzie do wywoływania odpowiednich procedur stosownie do wybranej przez użytkownika funkcji (doskonałe miejsce dla instrukcji case). Ponieważ przedstawianie schematów poszczególnych procedur zajęłoby zbyt dużo miejsca, poprzestaniemy na zaprezentowaniu ich zapisu w Pascalu. Metoda, którą wykorzystamy do tworzenia naszego programu, jest typowym przykładem projektowania wstępującego: najpierw utworzymy zestaw odpowiednich procedur (realizujących poszczególne zadania podrzędne), a następnie powiążemy je w całość, czyli działający program.

Zanim jednak do tego dojdzie, zastanówmy się przez chwilę nad przekazywaniem danych do i z odpowiednich procedur i funkcji. W myśl dobrej praktyki nie będziemy do tego celu wykorzystywać efektów ubocznych, lecz stosownie zaprojektowane listy parametrów. Rozważmy jako przykład procedurę wprowadzania zawartości rekordu z klawiatury. Powinna ona przyjmować jako argument "pusty" rekord i zwracać tenże rekord wypełniony wpisanymi przez użytkownika danymi. Musimy więc wykorzystać mechanizm przekazywania parametru przez nazwę. Ale jak zadeklarować sam parametr? Nagłówek w postaci:

              procedure Wprowadz(var r : record             

                            Tytul : string[30];             

                            Autor : string[25];             

                            Wypozyczajacy : string[25];             

                            Licznik : word);             

wygląda co najmniej podejrzanie. Istotnie: próba skompilowania podobnej konstrukcji skończy się wyświetleniem komunikatu Type identifier expected (spodziewany identyfikator typu).

Rozwiązaniem tego problemu zajmiemy się w następnym rozdziale. Znajdzie się w nim również kilka słów o tak zwanych stałych symbolicznych

Struktura programu pascalowego

Oto przykład prawidłowej struktury programu napisanego w TP:

PROGRAM Nazwa_Programu; {Naglowek programu nie może mieć polskich liter i spacji}

USES {Deklaracja modulow}

{Tu, po przecinku, podaje sie moduly }

LABEL {Deklaracja etykiet}

{Tu podaje się etykiety uzywane w programie}

CONST {Deklaracja stalych}

{Tu podaje sie stale}

TYPE {Deklaracja danych typu 'type'}

{Tu podaje sie dane typu 'type'}

VAR {Deklaracja zmiennych}

{Tu podaje sie zmienne}

PROCEDURE {Deklaracja procedur}

{Tu podaje sie kody zrodlowe procedur}

FUNCTION {Deklaracja funkcji}

{Tu podaje sie kody zrodlowe funkcji}

BEGIN {Poczatek programu}

{Kod zrodlowy programu}

END.

Stos, kolejka i lista nie są niestety predefiniowanymi strukturami danych w Pascalu, ale to nie znaczy, że nie możemy ich sobie stworzyć. W tym celu musimy wykorzystać wskaźniki.

Stos to jedna z najprostrzych struktur. Wyobraźmy sobie stos leżących książek jedna na drugiej. Możemy kłaść tylko na wierzch stosu i tylko z wierzchu zdejmować (jeżeli wyciągniemy ze środka, to się nam zawali stos). Tak samo jest ze stosem w programowaniu. Żeby dostać się do następnego elementu musimy najpierw ściągnąć coś z góry.

Zadeklarujmy więc sobie jeden element takiego stosu:

type PStos = ^TStos;

  TStos = record

    Liczba: Byte;

    Nastepny: PStos;

  end;

Możemy oczywiście dodać też inne pola. Dla nas najważniejsze jest pole "Nastepny", które wskazuje na następny element w stosie (leżący "pod" naszym elementem). Pierwsza książka, leży na stole, więc wskazuje na nil (brak książek). Utwórzmy więc pierszy element:

  Pocz := nil;

  WriteLn('Podaj liczbę');

  Read(Liczba);

  if Liczba <> 0 then

    if Pocz = nil then

    begin

      New(Pocz);

      Pocz^.Liczba := Liczba;

      Pocz^.Nastepny := nil;

    end;

Więc teraz czas napisać procedurkę, która będzie wrzucać elementy na stos:

  procedure DodajS(var Pocz: PStos; Liczba: Byte);

  var

    Nowy: PStos;

  begin

    New(Nowy);

    Nowy^.Liczba := Liczba;

    Nowy^.Nastepny := Pocz;

    Pocz := Nowy;

  end;

Nowy element wskazuje na ostatni, który jest na górze, a Pocz wskazuje na początek stosu, czyli nowo utworzony element.

Jeżeli dodajemy kolejne elementy do stosu, to wkładamy elementy na górę

nil <= 1;

1 <= 2;

1, 2 <= 3;

1, 2, 3

A jeżeli zdejmujemy ze stosu, to zdejmujemy z góry:

1, 2 => 3;

1 => 2;

nil => 1;

Jak widać wkładaliśmy w kolejności 1, 2, 3, a zdejmujemy odwrotnie 3, 2, 1. Taką strukturę oznacza się jako FILO (First In Last Out). Element, który pierwszy wrzuciliśmy zdejmujemy jako ostatni.

Jest to często bardzo przydatne. Np. naturalną dla człowieka kolejością podawania współczynników wielomianu jest podawanie ich od największej potęgi. Jednak żeby obliczyć np. sumę wielomianu znacznie wygodniej jest dysponować wielomianami uporządkowanymi od najmniejszej potęgi. W takim wypadku stosujemy stos.

Co jednak zrobić, jeżeli potrzebujemy odczytywać także w normalnej kolejności? Wówczas musimy zastosować kolejkę.

Kolejka to taka struktura, w której dodajemy elementy na koniec, a zabieramy z początku. Tak jak kolejka w sklepie (za PRL-u :) ). Pierwszy klient, który przyszedł, zostanie obsłużony jako pierwszy.

Element kolejki może wyglądać tak samo jak element stosu:

  PKolejka = PStos;

Tak samo możemy też utworzyć pierwszy element. Jednak już dodawanie elementów różni się od stosu. Jeżeli mamy początek kolejki, to musimy przejść do końca kolejki i tam dodać element:

  procedure DodajK(var Pocz: PKolejka; Liczba: Byte);

  var

    Nowy, Pom: PKolejka;

  begin

    Pom := Pocz;

    while Pom^.Nastepny <> nil do

      Pom := Pom^.Nastepny;

    New(Nowy);

    Nowy^.Liczba := Liczba;

    Nowy^.Nastepny := nil;

    Pom^.Nastepny := Nowy;

  end;

W ten sposób dodajemy elementy na koniec (w praktyce zwykle stosuje sie jeszcze drugi wskaźnik na koniec kolejki, żeby wyeliminować pętlę).

Tutaj, jeżeli będziemy dodawać elementy w kolejności:

nil <= 1

1 <= 2

1, 2 <= 3

1, 2, 3

to też w takiej będziemy ściągać:

1 <= 2, 3

2 <= 3

3 <= nil

Taką strukturę nazywa się FIFO (First In First Out). Pierwszy element który pojawił się w kolejce, jako pierwszy z niej wyjdzie.

Całkiem fajnie. Ale co zrobić, gdy potrzebujemy wstawić coś do środka kolejki? Wówczas trzeba użyć listy jednokierunkowej. Lista jednokierunkowa to taka kolejka czy stos tylko z dodatkową opcją wrzucania elementów gdzieś w środku (ktoś się wpycha w środek kolejki >:[ ).

PLista = PStos;

Więc by wepchnąć coś w środek, tak by znalazło się na pozycji Poz wykonajmy taką procedurę:

  procedure DodajL(var Pocz: PLista; Liczba: Byte; Poz: Integer);

  var

    Nowy, Pom: PLista;

    i: Integer;

  begin

    if Poz = 1 then

    begin

      New(Nowy);

      Nowy^.Liczba := Liczba;

      Nowy^.Nastepny := Pocz;

      Pocz := Nowy;

    end

    else

    begin

      Pom := Pocz;

      for i := 3 to Poz do

        Pom := Pom^.Nastepny;

      New(Nowy);

      Nowy^.Liczba := Liczba;

      Nowy^.Nastepny := Pom^.Nastepny;

      Pom^.Nastepny := Nowy;

    end;

  end;

I już podstawowe struktury mamy za sobą.

Aha... A jak to jeszcze odczytać? Od początku do końca :)

  procedure Wypisz(Pocz: PStos);

  begin

    while Pocz <> nil do

    begin

      WriteLn(Pocz^.Liczba);

      Pocz := Pocz^.Nastepny;

    end;

  end;

Dobrze by było, gdybyśmy posprzątali po sobie usuwajac te struktury (żeby nam nie zabrakło pamięci):

  procedure Usun(var Pocz: PStos);

  var

    Pom: PStos;

  begin

    while Pocz <> nil do

    begin

      Pom := Pocz^.Nastepny;

      Dispose(Pocz);

      Pocz := Pom;

    end;

  end;

Przykładową implementację można znaleźć tutaj