1. Projektowanie programu w języku C

1.1. Projektowanie zstępujące

Struktury danych to narzędzia do reprezentowania informacji, która ma być przetwarzana przez program komputerowy, a algorytmy to przepisy wykonania czynności niezbędnych do jej przetworzenia. Wybór algorytmu do rozwiązania konkretnego problemu programistycznego pomaga w ustaleniu, jakiej struktury danych należałoby użyć, ale i odwrotnie - wybrana struktura danych ma ogromny wpływ na szczegóły realizacji i efektywność algorytmu. Rozpoznanie, jaki rodzaj struktury danych jest najwłaściwszy w danej sytuacji, to połowa sukcesu.
Przy rozwiązywaniu prostych zadań podejście ad hoc może dawać szybsze rezultaty, jednak gdy mamy do czynienia z bardziej złożonymi problemami i chcemy tworzyć kod łatwy do zrozumienia, uruchomienia i pielęgnacji, efektywniejsze jest podejście systematyczne, chociaż początkowo bywa ono bardziej czasochłonne. Użyteczną metodą rozwiązywania problemów programistycznych jest projektowanie zstępujące ( ang. top-down design). Rozpoczyna się ono od zdefiniowania problemu, który należy rozwiązać. Problem dzieli się na główne kroki - podproblemy. Podproblemy są z kolei dzielone na drobniejsze kroki tak długo, aż rozwiązania drobnych problemów stają się łatwe do zapisania albo można wykorzystać bądź zaadaptować znane rozwiązania. Proces dzielenia kroków na mniejsze fragmenty nazywa się stopniowym uszczegółowianiem. W idealnym przypadku podproblemy powinny być rozwiązywane niezależnie, a ich rozwiązania łączone w celu otrzymania rozwiązania całego problemu. W odniesieniu do tworzenia kodu oznacza to, że poszczególne kroki powinny być kodowane niezależnie, przy czym dane wyjściowe jednego kroku są używane jako wejściowe dla innego. Niestety, w realnych problemach współzależność między poszczególnymi krokami jest zazwyczaj bardziej skomplikowana. Celem projektowania zstępującego jest zminimalizowanie tej współzależności.
Oto niektóre z zalet projektowania zstępującego:
=> Projektowanie zstępujące stanowi systematyczną metodę rozwiązywania problemów.
#18
=> Otrzymane rozwiązanie jest modularne. Poszczególne kroki mogą być kodowane, uruchamiane, modyfikowane i ulepszane niezależnie od pozostałych.
=> Otrzymane rozwiązanie jest łatwiejsze do zrozumienia, bo można je przyswajać fragmentami, bez konieczności ogarnięcia od razu całości.
=> Dobrze zaprojektowane fragmenty mogą być ponownie zastosowane w innych zadaniach.
=> Dzięki rozpoczynaniu projektowania "od góry" można rozpoznać wspólne podproblemy na samym początku i uniknąć w ten sposób wielokrotnego ich rozwiązywania za każdym razem, gdy się pojawiają.
Jako prosty przykład projektowania zstępującego rozważmy problem uporządkowania talii kart. Większość ludzi wydzieli tu następujące kroki:
1. Podziel talię na kolory.
2. W ramach każdego koloru ułóż karty według wartości.
3. Połącz uporządkowane kolory.
Kroki pierwszy i trzeci są proste. Sortowanie jednego koloru odbywa się tak samo, jak każdego innego, więc krok drugi może być zapisany jako pętla. Wszystko, co trzeba zrobić, to opisać, jak sortować jeden kolor. Krok drugi można dalej podzielić tak:
=> Rozłóż karty w wachlarz.
=> Dla każdej karty w wachlarzu, zaczynając od drugiej karty z lewej strony, a kończąc na ostatniej z prawej strony, umieść kartę we właściwym miejscu między kartami leżącymi na lewo od niej. (Kartę, którą się właśnie zajmujemy, nazywamy kartą bieżącą).
To rozwiązanie jest poprawne, ponieważ karty położone na lewo od karty bieżącej są już uporządkowane. Umieszczenie karty bieżącej we właściwym miejscu pośród kart leżących na lewo od niej odbywa się w następujących krokach:
=> Zaczynając od karty znajdującej się bezpośrednio na lewo od karty bieżącej i przemieszczając się w lewo, przekładaj karty o wartości większej niż wartość karty bieżącej o jedno miejsce w prawo. Zatrzymaj się, jeśli kolejna karta ma wartość mniejszą niż wartość karty bieżącej lub też jeśli nie ma więcej kart do przełożenia.
=> Wstaw kartę bieżącą w to miejsce.
Zapisanie tego rozwiązania w postaci programu komputerowego jest zadaniem nietrudnym (chociaż niektóre kroki, jak na przykład rozkładanie kart w wachlarz, nie nadają się do zakodowania). Częścią tego zadania jest ustalenie typu danych do reprezentowania wartości kart i struktury przechowującej karty. Zazwyczaj wybór struktury danych idzie w parze z projektem algorytmu. Dla tego prostego problemu opracowaliśmy schemat algorytmu przed wyborem struktury danych, zwykle jednak wybór struktury danych ma wpływ na projekt algorytmu. W książce tej mówimy, jak wybrać właściwą strukturę danych.
#19

1.2. Projektowanie wstępujące: maszyny wirtualne

Projektowanie zstępujące nie jest jedyną systematyczną metodą budowania programów. Inne podejście polega na wyjściu od samego języka i wzbogacaniu go nowymi operacjami, dopóki nie będzie można wyrazić rozwiązania problemu w rozszerzonym języku. Podejście to nazywa się projektowaniem wstępującym (ang. bottom-up de-sigri). Każde oprogramowanie działające na maszynie cyfrowej rozszerza jej możliwości o nowe funkcje. W efekcie uruchomienie programu na komputerze tworzy nową maszynę, która nie wykonuje swoich operacji bezpośrednio, ale zamienia je na prostsze, wykonywalne przez sprzęt. Tę nową maszynę nazywamy maszyną wirtualną, ponieważ istnieje w świecie abstrakcyjnym, a nie fizycznym. To samo dotyczy sytuacji, gdy dodajemy nową operację do języka programowania, pisząc funkcję. Zwiększa ona jego funkcjonalność, tworząc nowy, silniejszy język. O zbiorze nowych funkcji można myśleć jako o wirtualnej maszynie zbudowanej na bazie starego języka.
Aby to podejście przynosiło efekty, rozwijanie języka musi być inspirowane rozwiązywanym problemem. Przy projektowaniu wstępującym nie dzieli się problemu na kroki, które za pomocą tego języka można zrealizować. Zamiast tego rozbudowuje się język, dodając nowe, coraz silniejsze konstrukcje tak długo, aż problem da się w języku rozwiązać bezpośrednio.
Jako przykład rozważmy napisanie programu, który wczytuje, oblicza i wypisuje wyrażenia zbudowane z ułamków. Jeżeli na przykład na wejściu mamy wyrażenie

(3/28 + 2/7) * 4/3 - 1

to program powinien wypisać wynik 61/84. Napisanie takiego programu w języku C jest łatwe przy użyciu rekursji (zob. rozdz. 7), tyle że C nie jest wyposażony w możliwość bezpośredniego reprezentowania i manipulowania ułamkami. Dlatego należałoby zacząć od rozszerzenia języka C przez dodanie funkcji implementujących działania + ,-, * i / na ułamkach oraz wczytywania i wypisywania ułamków. Ten pakiet funkcji mógłby też zawierać funkcję skracającą ułamki, chociaż nasz program nie musiałby z niej korzystać. Pakiet do obliczeń na ułamkach może się przecież przydać w wielu innych programach, nie tylko w tym jednym.
Zazwyczaj programy projektuje się, łącząc metodę zstępującą i wstępującą. Programista zaczyna od podzielenia problemu na podzadania i przekonuje się, że przydatny byłby określony pakiet funkcji. Następnym krokiem jest rozstrzygnięcie, jakie funkcje wejdą w skład pakietu, i użycie ich do rozszerzenia języka. Programista może teraz zaimplementować pakiet lub użyć nowych funkcji do rozwiązania niektórych podproblemów. Podproblemy można dalej dzielić na prostsze, a język wzbogacać dopóty, dopóki rozwiązania wszystkich problemów składowych nie dadzą się zapisać bezpośrednio w rozszerzonym języku. Wtedy problem będzie rozwiązany, a program - ukończony.
Jednym z celów przy pisaniu programu metodą systematyczną jest to, aby kod programu odzwierciedlał rozbicie na podproblemy. Każdy krok projektu zstępującego
#20
mógłby być na przykład zaimplementowany jako wywołanie funkcji. Taka metoda pisania programów jest użyteczna, nie tyle z powodu efektywności (ponieważ każdy krok jest zapewne wykonywany raz, każda funkcja będzie wywoływana tylko raz, co według niektórych nie jest efektywne), co z powodu tego, że czyniąc każdy krok funkcją, programista może przypisywać znaczące nazwy spójnym fragmentom kodu, a funkcja może być wywoływana również w innych programach. Kod staje się czytelniejszy i łatwiejszy do uruchomienia i ulepszania.
Język C dostarcza narzędzi przydatnych do reprezentowania rozbicia problemu w tekście programu. Jeden ze sposobów implementacji pakietu funkcji, takiego jak pakiet operacji na ułamkach, omawiamy w następnym podrozdziale.

1.3. Projektowanie do wielokrotnego użytku: oddzielna kompilacja

Kiedy projektujemy program w sposób modularny, czy to metodą zstępującą czy wstępującą, zawiera on zbiór użytecznych, powiązanych ze sobą funkcji. Pakiet funkcji do manipulacji ułamkami na przykład może mieć zastosowanie w innych programach, powinien więc być zaimplementowany tak, żeby zawarte w nim operacje były zrozumiałe i żeby łatwo było włączać pakiet do innych programów.
W języku C pakiet zawiera się w dwóch plikach: nagłówkowym i źródłowym, dzięki czemu jego funkcje mogą być z łatwością użyte w dowolnym programie. Taką parę plików nazywa się modułem (ang. unit). Plik nagłówkowy (z rozszerzeniem .h) zawiera deklaracje funkcji pakietu, przewidzianych do wykorzystania w innych programach, wraz z wszelkimi potrzebnymi używanymi przez nie deklaracjami. Może on także zawierać dyrektywy włączania innych plików oraz makrodefinicje wyrażające ograniczenia implementacyjne albo kodujące operacje na tyle proste, że narzut wynikający z realizacji ich jako funkcji byłby marnotrawstwem. Plik źródłowy (z rozszerzeniem . c) zawiera definicje funkcji. Oprócz funkcji udostępnianych na zewnątrz plik źródłowy może też zawierać niezbędne funkcje pomocnicze i zmienne do wewnętrznego użytku.
Na rysunku 1.1 widać plik nagłówkowy dla pakietu operacji na ułamkach. Plik nagłówkowy włącza plik stdio.h, potrzebny w funkcji writeRat (). Test #ifndef ma na celu zapewnienie, że deklaracje zawarte w tym pliku będą przetwarzane tylko raz, chociaż plik może być włączany do programu wielokrotnie: na przykład gdy program główny włącza ten nagłówek, a inny plik także używa ułamków.
Plik źródłowy rational.c zawiera kod implementujący te funkcje. Dodatkowo trzeba będzie zapewne zdefiniować funkcję obliczającą największy wspólny dzielnik dwóch liczb całkowitych i inną, skracającą ułamek.
Aby można było wywołać funkcję modułu, plik nagłówkowy musi być włączony do programu. Plik źródłowy modułu musi także włączać swój plik nagłówkowy, ponieważ ten zawiera wymagane dla funkcji deklaracje. Oba pliki mogą być teraz kompilowane
#21
niezależnie, a otrzymane pliki pośrednie - połączone, co tworzy gotowy program.
Proces ten nazywa się oddzielną kompilacją. Oto jej zalety:
=> Jeśli potrzebna jest zmiana, to tylko pliki, których ona dotyczy, muszą być powtórnie
kompilowane.
Po ponownej kompilacji wszystkie pliki muszą być znowu łączone, ale zajmuje to zwykle
znacznie mniej czasu niż kompilacja całości.
=> Moduł może być zastosowany w różnych programach bez żadnych zmian w jego kodzie.
=> Plik nagłówkowy zawiera całość informacji potrzebnej do wykorzystania pakietu.

#ifndef RATIONALS
#def ine RATIONALS

#include

typedef struct {
int num, denom;
} Rational;

int readRat(Rational *);
int writeRat(Rational);
Rational addRat(Rational, Rational);
Rational subRat(Rational, Rational);
Rational multRat(Rational, Rational);
Rational divRat(Rational, Rational);
#endif RATIONALS

Rys. 1.1. Plik rational.h

Użytkownik musi jedynie wiedzieć, jak wywoływać funkcje, a nie jak są zaimplementowane. Wystarczy przejrzeć plik nagłówkowy, aby dowiedzieć się, jak używać pakietu.
Do tej metody projektowania programów można wprowadzić jedno istotne ulepszenie. Często operacje z pakietu nie zależą od konkretnego typu danych, którym posługuje się program główny. Niech na przykład wspólną operacją będzie zapisywanie i odczytywanie danych według kluczy. Konkretny typ danych i klucza jest bez znaczenia dla funkcji zapisującej i odczytującej, ale nie dla programu głównego. Dobrze jest implementować pakiet w taki sposób, żeby kod nie zależał od poszczególnych typów danych. Typ danych, dla którego operacje nie zależą od jego szczególnych własności, nazywamy abstrakcyjnym typem danych (ATD).
#22

1.4. Abstrakcyjne typy danych

Aby przekonać się, dlaczego abstrakcyjne typy danych są przydatne, rozważmy następujące dwa zadania programistyczne:
Zadanie 1. Program tworzenia skorowidza. Program będzie wczytywał tekst ze standardowego wejścia, a następnie wypisywał każde słowo występujące na wejściu wraz z informacją, ile razy się ono pojawiło.
Zadanie 2. Program bankowy. Program będzie wczytywał listę transakcji. Każda transakcja składa się z numeru konta, daty i kwoty. Następnie dla każdego konta zostanie utworzony wydruk zawierający jego stan oraz listę transakcji związanych z tym kontem w kolejności, w jakiej zostały wczytane przez program. Dla uproszczenia założymy, że z każdym kontem jest związanych co najwyżej dziesięć transakcji, stany wszystkich kont są początkowo zerowe, a numery kont, daty i kwoty są liczbami całkowitymi.
Na pierwszy rzut oka wydaje się, że programy te nie mają ze sobą nic wspólnego, ale przyjrzyjmy się im dokładniej. Na rysunku 1.2 jest przedstawiony podział obu zadań na kroki.

Program tworzenia skorowidza:
Dopóki nie koniec danych wejściowych
Wczytaj słowo.
Poszukaj tego słowa (i związanego z nim licznika) w pewnej strukturze danych.
Jeśli słowo zostało znalezione, to zwiększ jego licznik i umieść nową wartość z powrotem w strukturze danych.
Jeśli słowo nie zostało znalezione, to dodaj je do struktury danych wraz z licznikiem o wartości 1.
Dla każdego słowa w strukturze danych wypisz słowo i jego licznik.

Program bankowy:
Dopóki nie koniec danych wejściowych
Wczytaj transakcję.
Poszukaj numeru konta (i związanego z nim stanu konta oraz listy transakcji) w pewnej
strukturze danych.
Jeśli numer konta został znaleziony, to dodaj kwotę do stanu konta i dołącz transakcję
do listy transakcji, a następnie umieść tę nową informację z powrotem w strukturze danych.
Jeśli numer konta nie został znaleziony, to dodaj go do struktury danych wraz z kwotą transakcji jako stanem konta i listą transakcji zawierającą tę jedyną transakcję.
Dla wszystkich kont w strukturze danych wypisz numer konta, jego stan i listę transakcji.

Rys. 1.2. Podział programów na kroki
#23

Teraz można już zauważyć, że te dwa odmienne programy są bardzo podobne. Rzeczywiście, procedury wyszukiwania danych według klucza, zastępowania danych nową informacją i tworzenia nowej porcji danych z nowym kluczem mogą być wykorzystane w obu programach. Procedury te nie powinny zależeć od typu przechowywanych danych ani od typu klucza, ale od tego, w jaki sposób dane są zapamiętywane i jakie algorytmy stosuje się do wyszukiwania i odczytywania danych.
Oddzielenie operacji wykonywanych na danych i sposobów ich przechowywania od konkretnego typu danych jest podstawą abstrakcyjnego typu danych. Jak wspomnieliśmy wcześniej, abstrakcyjny typ danych można zdefiniować za pomocą operacji, które są wykonywane na danych, niezależnie od ich typu. W obu powyższych przykładach wykonuje się następujące operacje:

1. Wyszukiwanie danych związanych z konkretnym kluczem. Rozróżnienie, czy dane zostały znalezione czy nie. Zakładamy, że wszystkie klucze są różne i dwie różne porcje danych nie mogą mieć tego samego klucza.
2. Zastępowanie danych związanych z pewnym kluczem nowymi danymi.
3. Dodanie nowego klucza wraz z danymi.
4. Wykonanie jakiejś operacji na każdym kluczu i związanych z nim danych. W naszych programach operacją tą jest wypisanie klucza i danych.

Ten zbiór operacji definiuje ATD zwany prostą bazą danych. Zastosowanie abstrakcyjnego typu danych umożliwia podzielenie zadania programistycznego na dwie części. Pierwsza polega na zaimplementowaniu ATD: wyborze struktury danych reprezentującej ATD i napisaniu funkcji implementujących operacje. Druga część to napisanie programu głównego, który będzie wywoływać funkcje ATD. Program ma dostęp do danych ATD wyłącznie przez wywoływanie funkcji; nie może bezpośrednio odczytywać ani modyfikować wartości przechowywanych w wewnętrznych strukturach ATD.
To ograniczenie wydaje się utrudniać programowanie, ale w rzeczywistości decyduje o użyteczności ATD. Przez odseparowanie implementacji ATD od jego użycia dzielimy problem programistyczny na dwa niezależne zadania. Ponieważ program główny nie może sięgać do struktur danych ATD bezpośrednio, a jedynie przez wywołanie funkcji z interfejsu, będziemy mogli w przyszłości zmienić implementację ATD, pozostawiając program główny nietknięty. Jeśli więc znajdziemy efektywniejszy sposób przechowywania danych albo szybsze algorytmy operacji ATD, to jedynie ATD musi się zmienić. Z drugiej strony, implementacja ATD jest oderwana od jego użycia, zatem ten sam ATD można włączać do wielu różnych programów bez żadnych zmian. Jednym z celów programisty powinno być utworzenie zestawu efektywnych, bezbłędnych ATD, które będzie włączał do pisanych przez siebie programów.
Prosta baza danych jest chyba najczęściej stosowanym ATD. Zawsze gdy potrzebujemy dostępu do danych według kluczy oraz możliwości dodawania nowych kluczy i danych, możemy wykorzystać ten ATD. Definiujemy go za pośrednictwem funkcji dających dostęp do danych. Ponieważ ATD prócz swojej modularnej budowy musi być efektywny, zaopatrzymy funkcje w dodatkowy parametr idx (od ang. index), wskazujący gdzie szukać bieżącego zapisu. Typ tego wskaźnika zależy od
#24
rodzaju struktury danych użytej do implementacji ATD, zatem tylko funkcje ATD będą mogły go używać. Program główny otrzymuje jego wartość przy wywołaniu funkcji findRec (), a potem przekazuje ją innym funkcjom ATD, takim jak createRec (), deleteRec () czy setRec (). Na rysunku 1.3 jest podana specyfikacja ATD-prostej bazy danych.

int findRec(dbkeytype key, dbdatatype *data, indextype *idx);
/*Działanie: Szuka klucza key w prostej bazie danych. Jeśli rekord z takim kluczem istnieje, to findRec zwraca wartość 1, data to dane z tego rekordu, a idx wskazuje miejsce jego przechowywania. Jeśli rekord nie został znaleziony, to findRec zwraca 0, idx wskazuje, gdzie taki rekord należałoby umieścić, a data ma wartość nieokreśloną. */

int createRec(dbkeytype key, dbdatatype data, indextype idx);
/* Założenie: idx powinien wskazywać, gdzie ma się znaleźć nowy rekord. Działanie: Dodaje nowy rekord z kluczem key i danymi data do prostej bazy danych. Zwraca wartość 1 w przypadku sukcesu, 0 w razie niepowodzenia (przepełnienie bazy). */

void setRec (indextype idx, dbdatatype data);
/* Założenie: idx powinien wskazywać, gdzie ma się znaleźć nowy rekord. Działanie: Zmienia dane w rekordzie wskazywanym przez idx na data. */

void eachRec(void (*fn)(dbkeytype key, dbdatatype data));
/* Działanie: Wywołuje funkcję fn dla każdego rekordu, (przekazując jego klucz i dane jako parametry) w prostej bazie danych. */

Rys. 1.3. ATD-prosta baza danych

Zauważmy, że typy dbkeytype i dbdatatype zależą tylko od tego, co jest przechowywane w bazie danych. W programie tworzenia skorowidza klucz to słowo, reprezentowane w języku C jako char[21], a dana to liczba typu int. W programie bankowym kluczem jest numer konta typu int, a dane to struktura zawierająca stan (typu int) i listę transakcji. Można napisać ATD-prostą bazę danych w taki sposób, że wszelkie operacje zależne od typu klucza lub danych (jak porównanie dwóch kluczy czy kopiowanie rekordu) są oddzielone od reszty ATD i mogą być łatwo zmieniane. Typ indextype z kolei zależy od sposobu implementacji ATD, a nie od typu przechowywanych danych. Jeśli będziemy zmieniać implementację ATD, to indextype prawdopodobnie też się zmieni.
Prosta baza danych jest najczęściej używanym ATD i można ją zaimplementować na wiele sposobów. Można użyć list (zob. rozdz. 5) lub tablic do przechowywania kluczy i danych. Rekordy mogą być uporządkowane według kluczy albo nie uporządkowane, a nowe rekordy dodawane na początku lub na końcu.
Przy danym opisie ATD-prostej bazy danych implementacja programu tworzenia skorowidza wygląda jak na rysunku 1.4.
#25

#include
#include "database.h"

void printCount ( char *word, int n)
{
printf ("%20s %5d\n", word, n);
}

main()
{
char word[21] ;
int count;
indextype idx;

while (scanf ("%20s", word)==1) {
if (findRec(word, &count, &idx))
setRec(idx, count+1);
else if (!createRec(word, 1, idx))
printf ("Błąd: Nie można dodać słowa %s. Brak miejsca \ w bazie danych.", word);
}
eachRec(&printCount);
}

Rys. 1.4. Plik concordance.c

Zauważmy, że program główny sięga do danych przechowywanych w bazie tylko przez wywoływanie odpowiednich funkcji. Nigdzie nie korzysta z tego, że baza danych mieści się, przykładowo, w posortowanej tablicy. Sam ATD jest zaimplementowany w dwóch plikach: database.h - pliku nagłówkowym obejmującym prototypy funkcji implementujących operacje ATD i wszystkie potrzebne dla nich deklaracje, oraz database.c - pliku zawierającym kod tych funkcji. Plik database.h musi być włączony do programu głównego za pomocą dyrektywy #include, a kod pośredni otrzymany po kompilacji database . c połączony z kodem pośrednim programu głównego. Typy dbkeytype i dbdatatype nie są częścią ATD, gdyż zależą od programu głównego. Dlatego muszą one być zadeklarowane w osobnym pliku, włączonym do database.h. Plik ten zawiera też kilka makrodefinicji, które zależą od określonych typów danych. Aby wykorzystać ten ATD w innym programie, należy zmienić wiersz #include "words.h" na włączający odpowiedni plik. Rysunek 1.5 zawiera treść pliku database.h, a rysunek 1.6 - pliku words.h.
Aby ukończyć pierwsze zadanie, trzeba jeszcze zaimplementować operacje bazy danych. Niezbędne zmienne i funkcje są zdefiniowane w pliku database.c, co widać na rysunkach 1.7 i 1.8.
Podsumowując, ATD-baza danych składa się z dwóch plików: database.h i database.c. Kod nie zależy od typu danych ani kluczy przechowywanych w bazie. Ta konkretna implementacja przechowuje rekordy w posortowanej tablicy.
#26

#ifndef DATABASE
#def ine DATABASE
#include
#include "words.h"

typedef struct dbrec {
dbkeytype key;
dbdatatype data;
} Dbrec;

typedef Dbrec *indextype;

int findRec(dbkeytype, dbdatatype *, indextype *);
int createRec(dbkeytype, dbdatatype, indextype);
void setRec(indextype, dbdatatype);
void eachRec(void (*fn)(dbkeytype, dbdatatype));
#endif

Rys. 1.5. Plik database.h dla implementacji tablicowej

Program tworzenia skorowidza składa się z dwóch plików: concordance .c - zawierającego program główny i pomocniczą funkcję do wypisywania danych, oraz words . h - opisującego jakie dane i klucze będą przechowywane w bazie.

#ifndef WORDS
#define WORDS
#include
#include

typedef char dbkeytype[21];
typedef int dbdatatype;

#define comparedbkey (s1, s2) ((int)(strcmp((s1),(s2))))
#define copydbkey (s1, s2) (strcpy((s1),(s2)))
#define copydbdata (d1, d2) ((d2)=(d1))
#endif

Rys. 1.6. Plik words.h

Powróćmy teraz do drugiego zadania, programu bankowego. Z każdym kontem może być związanych do dziesięciu transakcji, a każda z nich ma być wypisana po wczytaniu całej informacji o danym koncie, zatem do każdego konta trzeba dowiązać listę transakcji. Oprócz ATD-prostej bazy danych będziemy potrzebować innego abstrakcyjnego typu danych, a mianowicie ATD-listy, składającej się z niezbędnych operacji listowych. Między tymi dwoma ATD występuje istotna różnica. Ponieważ obydwa programy potrzebują tylko jednej bazy danych do przechowywania słów lub kont, ATD-prosta baza danych powinna używać pojedynczej zmiennej globalnej do przechowywania bazy danych i nadawać jej odpowiednią wartość początkową. Natomiast każde konto w programie bankowym ma własną listę. Dlatego listy muszą być tworzone dynamicznie, co wymusza istnienie dodatkowej funkcji tworzącej i inicjującej nową listę. ATD-lista jest zdefiniowana przez następujące operacje:
1. Utworzenie nowej listy.
2. Dodanie elementu do listy.
3. Wykonanie pewnej operacji na każdym elemencie listy. W naszym przykładzie - wypisanie daty i kwoty każdej transakcji.
#27

#include "database.h"

#define maxRec 1000

Dbrec db[maxRec]; /* tablica rekordów */
int numRecs=0 ; /* bieżąca liczba rekordów */

int findRec(dbkeytype key, dbdatatype *data, indextype *idx)
/* Założenia: Klucze rekordów są uporządkowane. numRecs>=0.
Działanie: Szuka klucza key na liście rekordów. Zwraca informację, czy został on znaleziony, dane - o ile rekord był znaleziony, oraz wskaźnik do rekordu, jeśli był znaleziony, lub do rekordu o kluczu bezpośrednio większym od key, jeśli rekord z kluczem key nie został znaleziony. */
{
int low=0, high=numRecs-1, found=0, mid, cmp;

while (!found && low<=high) {
/*NP: (1) Wszystkie klucze od db[0].key do db[low-1].key są mniejsze niż key.
(2) Wszystkie klucze od db[high+1].key do db[numRecs-1].key są większe niż key.
(3) Jeśli found!=0, to db[mid].key==key.
(4) low<=high+1. */
mid = (low+high)/2;
cmp = comparedbkey(key,db[mid].key);
if (cmp<0)
high = mid-1;
else if (cmp>0)
low = mid+1;
else /* cmp==0 */
found = 1 ;
}
if (found) {
/* Z NP(3) wynika, że mid jest numerem rekordu o kluczu key. */
*idx = db+mid;
copydbdata((*idx)->data, *data);
}
else
/* Jeśli !found, to low>high, a więc low==high+1 z NP(4), NP(1) i NP(2) implikują, że low jest numerem rekordu o kluczu następującym bezpośrednio po key. */
*idx = db+low;
return found;
}

Rys. 1.7. Plik database.c dla implementacji tablicowej
#28

int createRec (dbkeytype key, dbdatatype data, indextype idx) /* Założenie: idx jest miejscem, gdzie powinien się znaleźć nowy rekord. Działanie: Jeśli baza danych nie jest całkowicie wypełniona, dodaje rekord z kluczem key i danymi data, zwracając 1. W przeciwnym razie zwraca 0. */
{
Dbrec *rec;

if (numRecs==maxRec)
return 0;
for (rec=db+numRecs; rec>idx; rec--)
*rec = *(rec-1);
copydbkey(key, idx->key);
copydbdata(data, idx->data) ;
numRecs++;
}

void setRec (indextype idx, dbdatatype data)
/* Założenie: idx wskazuje na rekord w bazie danych.
Działanie: Umieszcza data jako dane w rekordzie wskazywanym przez idx. */
{
copydbdata (data, idx->data) ;
}

void eachRec(void (*fn) (dbkeytype key, dbdatatype data))
/* Działanie: Wywołuje funkcję kolejno dla wszystkich kluczy i danych przechowywanych w bazie danych. */
{
Dbrec *rec;
for (rec = db; rec(*fn) (rec->key, rec->data);
}
Rys. 1.8. Plik database.c dla implementacji tablicowej (cd.)
#29

Powyższy zbiór operacji można rozszerzać na wiele sposobów, czyniąc ATD ogólniejszym i zwiększając możliwości jego stosowania w innych programach, nam jednak na razie wystarczy ten zestaw. Na rysunku 1.9 widać opis ATD-listy. Zwróćmy uwagę, że funkcje mają dodatkowy parametr, list, wskazujący, która lista będzie przetwarzana. Nie było to potrzebne dla ATD-prostej bazy danych, ponieważ zawsze mieliśmy do czynienia tylko z jedną bazą danych.

void initList(List *list);
/* Działanie: Tworzy pustą listę. */

int addList(List *list, listdatatype data);
/* Działanie: Dodaje dane data do listy. Zwraca 1 w przypadku powodzenia, 0 w przeciwnym razie (lista jest pełna). */

void eachElement (List list, void (*fn) (listdatatype));
/* Działanie: Wywołuje funkcję fn dla każdego elementu listy. */

Rys. 1.9. ATD-lista

Teraz możemy już zaimplementować program bankowy. Będzie on korzystał z ATD-bazy danych i listy oraz opisów transakcji. Na rysunku 1.10 jest przedstawiony program bankowy.
ATD-prosta baza danych jest dokładnie ta sama co w poprzednim programie. Jedyna różnica polega na tym, że poprzednio klucze były napisami, a dane - liczbami całkowitymi, natomiast teraz klucze to numery kont typu int, a daną jest rekord opisujący konto. Ponieważ oddzieliliśmy opis przechowywanych danych od ATD, to jedyną zmianą, jaką musimy zrobić, jest włączenie do database.h pliku accounts.h zamiast words.h. Na rysunku 1.11 widać zawartość pliku accounts.h.
Widzimy, że konta są umieszczane w bazie według numerów i że pojedyncza dana jest strukturą składającą się z dwóch części: stanu konta i ciągu transakcji. Ten ostatni jest listą, nowym ATD.
ATD-listę można zaimplementować na wiele sposobów. Ponieważ mamy (bardzo arbitralne) ograniczenie, że na jedno konto przypada co najwyżej dziesięć transakcji, do przechowywania transakcji wybierzemy 10-elementową tablicę wraz z licznikiem wskazującym, ile transakcji już w niej umieszczono. Tak jak dla prostej bazy danych, ATD definiują dwa pliki: list .h, zawierający prototypy funkcji implementujących operacje i wszelkie niezbędne deklaracje, i list.c, zawierający kod tych funkcji. Pliki te są zamieszczone na rysunkach 1.12 i 1.13.
Ostatnia część programu bankowego składa się z opisu transakcji i funkcji wypisującej pojedynczą transakcję. Fragment ten zawiera tylko jedną prostą funkcję, został więc umieszczony w pliku nagłówkowym, zamiast w oddzielnym pliku źródłowym. Na rysunku 1.14 widać zawartość pliku trans .h - opis transakcji i funkcję wypisującą transakcję.
#30

#include
#include "trans.h"
#include "database.h"
#include "list.h"

void printstatement(int acctNo, AcctData acctRec)
{
Transaction trans;

printf ("Numer konta : %8d, Stan = %d.\n", acctNo, acctRec.balance);
eachElement(acctRec.transactions, &printTransaction);
}

void printError(int acctNo, Transaction trans)
{
printf ("Błąd: nie przetworzona transakcja: %d%d%d.\n", acctNo, trans.date, trans.amount);
}

main()
{
int acctNo;
Transaction trans;
AcctData acctRec;
indextype idx;

while (scanf ("%d%d%d", &acctNo, &trans.date, &trans.amount) == 3) {
if (findRec(acctNo, &acctRec, &idx)) {
acctRec.balance += trans.amount;
if (addList(&acctRec.transactions, trans))
setRec(idx, acctRec);
else
printError(acctNo, trans);
}
else {
acctRec.balance = trans.amount;
initList(&acctRec.transactions);
if (!addList(&acctRec.transactions,trans) ||
!createRec(acctNo, acctRec, idx) )
printError(acctNo, trans);
}
}
eachRec(&printStatement)
}
Rys. 1.10. Plik banking.c
#31

#ifndef ACCOUNTS
#def ine ACCOUNTS
#include "list.h"

typedef struct {
int balance;
List transactions;
} AcctData;

typedef int dbkeytype;
typedef AcctData dbdatatype;

#def ine comparedbkey(k1, k2) ((k1)-(k2))
#define copydbkey(k1, k2) ((k2)=(k1))
#define copydbdata(d1, d2) ((d2)=(d1))
#endif

Rys. 1.11. Plik accounts.h

#ifndef LIST
#def ine LIST

#include "trans.h"
#define MAXLIST 10
typedef struct {
listdatatype elements[MAXLIST];
int counter;
} List;

int addList(List *, listdatatype);
void initList (List * ) ;
void eachElement(List, void (*fn)(listdatatype));

#endif

Rys. 1.12. Plik list.h

Struktura całego programu bankowego może początkowo wydawać się skomplikowana, ponieważ program został podzielony na siedem plików: banking. c, database.h, database.c, accounts.h, list.h, list.c i trans.h. Jeśli jednak uszeregujemy różne koncepcyjnie dane w naszym problemie, to okaże się, że są ich cztery rodzaje: baza danych przechowująca konta, same konta, listy transakcji i same transakcje. Ponieważ w języku C zazwyczaj reprezentujemy każdy typ danych w dwóch plikach (nagłówkowym i źródłowym, zawierającym kod), plików będzie sporo. (Konta i transakcje nie mają pliku z kodem, ale jest jeszcze program główny, co razem czyni siedem plików).
#32

#include "list.h"

int addList(List *list, listdatatype data)
{
if (list->countercopylistdata (data, list->elements[list->counter++]) ;
return 1;
}
return 0;
}

void initList(List *list)
{
list->counter = 0;
}
void eachElement(List list, void (*fn)(listdatatype))
{
listdatatype *1;
for (1 = list.elements; l < list.elements+list.counter; 1++) (*fn) (*1) ;
}

Rys. 1.13. Plik list.c

#ifndef TRANS
#define TRANS

typedef struct {
int date;
int amount;
} Transaction;

typedef Transaction listdatatype;

#def ine copylistdata (d1, d2) ((d2) = (d1))
void printTransaction(Transaction trans)
{
printf("Data: %8d, Kwota: %8d\n" , trans.datę, trans.amount)
}
#endif

Rys. 1.14. Plik trans.h
#33

W tym konkretnym ATD zakładaliśmy, że program będzie używał tylko jednej prostej bazy danych. Gdyby program miał używać wielu baz, należałoby uzupełnić każdą funkcję ATD parametrem specyfikującym, do której bazy trzeba sięgnąć. Oprócz tego w obecnej wersji ATD jedyna używana baza jest przechowywana w zmiennej lokalnej pliku implementującego ATD i jest tam automatycznie inicjowana. Gdyby mogło istnieć wiele baz danych, program główny musiałby zadeklarować wszystkie zmienne potrzebne do ich przechowania i samodzielnie je zainicjować. Aby zrobić to w stylu zachowującym niezależność ATD, powinniśmy zdefiniować nową funkcję, initDb(), którą wywołuje się (przekazując jej stosowny argument) w celu zainicjowania bazy danych.

1.5. Ćwiczenia

1. Podaj projekt zstępujący algorytmu, innego niż opisany w podrozdziale 1.1, sortowania talii kart.
2. Podaj projekt zstępujący dotyczący spożywania posiłku w restauracji. Jakie kroki można wydzielić? Rozbij chociaż jeden z kroków na drobniejsze.
3. Załóżmy, że program często operuje na zbiorach liczb całkowitych. Które ze znanych operacji mógłbyś zaimplementować, rozszerzając język C tak, by mógł obsługiwać zbiory? Czy Twoja implementacja narzuca ograniczenia na zbiory? Jeśli tak, to jakie?
4. Jak zaimplementowałbyś w języku C liczby zespolone?
5. Pojęcie ukrywania informacji odnosi się do zasady ograniczania informacji (takiej jak nazwy zmiennych czy dowiązania) jedynie do tych funkcji, które powinny mieć do niej dostęp. Chodzi o uproszczenie programowania dzięki uniknięciu przypadkowych lub zbędnych odwołań do wewnętrznych obiektów. W jaki sposób oddzielna kompilacja pozwala programiście stosować ukrywanie informacji?
6. Wymień główne wady oddzielnej kompilacji.
7. Czym się różni abstrakcyjny typ danych od maszyny wirtualnej?
8. Rozważmy abstrakcyjny typ danych - statyczny słownik, który umożliwia jedynie odczytywanie danych według kluczy, ale nie pozwala na modyfikację ani usuwanie danych. Czy można zaimplementować ten ATD efektywniej niż ogólniejszy ATD-prostą bazę danych?
9. Rozważmy następujące zadanie programistyczne: należy wczytać ciąg par miast - napisów składających się co najwyżej z 20 znaków - gdzie każda para jest połączona autostradą, a następnie wypisać listę tych miast, które są bezpośrednio połączone z trzema lub więcej innymi miastami. Opisz, jak zaimplementować ten program z użyciem ATD-prostej bazy danych.
#34

Bibliografia

[1] Abelson H., Sussman G.J.: Structure and Interpretation of Computer Programs. Cambridge, MA, MIT Press 1985.
[2] Dahl O.-J., Dijkstra E.W., Hoare C.A.R.: Structured Programming. London, Academic Press 1972.
[3] Dijkstra E.W.: Umiejętność programowania. Warszawa, WNT 1985.
[4] Wirth N.: Programming Development by Stepwise Refinement. Communications of the ACM, 1971, 14, s. 221-227.
[5] Wirth N.: Wstęp do programowania systematycznego. Warszawa, WNT 1978.