Politechnika Świętokrzyska w Kielcach
Projekt z języka C/C++
Temat: Dokumentacja techniczna programu „Księgarnia”.	Grupa: Belka Radosław Fulara Radosław Jaguścik Janusz
Data oddania projektu: 09-06-99r.	Ocena:

1. Wstęp

Program Księgarnia służy do obsługi księgarni przy przyjmowaniu książek na skład, ich sprzedaży oraz wyszukiwania pozycji ze względu na autora lub tytuł. Program napisany został przy pomocy kompilatora Borland C++ Builder 3.0. Do przechowywania i wyszukiwania pozycji w pamięci wykorzystywana jest dynamiczna struktura drzewa. Wszystkie najważniejsze funkcje programu zgrupowane zostały w module Modul.cpp

2. Idea działania programu

Jak już wspomniano we wstępie program oparty jest na idei działania drzewa binarnego. Najprostszym sposobem przechowywania danych jednego typu jest umieszczenie ich w jednowymiarowej tablicy. Przeszukiwanie i modyfikacja takiej struktury w przypadku znacznego jej rozmiaru jest jednak czasochłonne. O wiele efektywniej (choć jest to bardziej skomplikowane programowo)jest zapisywać elementarną daną, którą w naszym przypadku jest rekord zawierający dane o książce do struktury drzewa. Ogólną zasadę tworzenia drzewa podano w już w poprzednim sprawozdaniu. Mówiąc w skrócie, drzewo składa się z węzłów, z którego każdy zawiera jedną elementarną daną. Każdy węzeł, może prowadzić do dwóch nowych węzłów ( zakładamy, że są to tzw. węzeł prawy i lewy), przy czym istnieje pewne kryterium logiczne przydzielania kierunku do kolejnych węzłów. Każdy węzeł leży na odpowiednim poziomie. Na pierwszym poziomie znajduje się tylko jeden węzeł, na drugim znajdować się mogą dwa, na trzecim 4, a na i - tym poziomie znajdować się może do 2^i-1 węzłów. W przypadku, gdy istnieje tendencja do maksymalizowania ilości węzłów na każdym poziomie, drzewo takie możemy uznać za zrównoważone. Jest to optymalny przypadek zapisu danych. W przeciwnym przypadku drzewo nie jest zrównoważone; w granicznym przypadku drzewo może mieć charakter listy.

W przypadku listy zawierającej N danych czas jej przeszukiwania jest proporcjonalny do N. Natomiast w przypadku binarnego drzewa zrównoważonego czas ten jest proporcjonalny do logarytmu o podstawie 2 z N. Dla N ok. tysiąca czas w tym drugim przypadku jest więc ok. 100 razy krótszy. Jest to więc główna zaleta stosowania struktury drzewa.

W naszym przypadku kryterium tworzenia drzewa jest alfabetyczna kolejność tytułów książek. Drzewo niekoniecznie musi być zrównoważone. Zależy to od przypadkowej kolejności wprowadzanych tytułów.

3. 3. Opis struktur danych używanych w programie

typedef struct {

char tytul[50];

char autor[50];

int licz_egz;

double cena;

} Ksiegarnia;

Struktura przechowująca dane o pojedynczej książce.

typedef struct TREE{ Ksiegarnia ksiegarnia; int indeks; struct TREE *left; struct TREE *right; } tree;

Struktura pojedynczego węzła w drzewie. Pole ksiegarnia zawiera strukturę typu Ksiegarnia, natomiast pola left i right wskazują odpowiednie na gałąź lewą i prawą. Pole indeks jest polem pomocniczym zawierającym indeks danej pozycji na liście Siatka (patrz opis zmienych).

4. Opis zmiennych używanych w programie

static TREE *root; - zmienna przechowująca adres początku drzewa.

static FILE *Outfile; - zmienna plikowa służąca do operacji na pliku zawierającym dane z drzewa.

static int indeksy[1000]; - statyczna tablica zawierająca indeksy znalezionych książek (według autora).

static Ksiegarnia ksiazka;- pomocnicza zmienna typu Ksiegarnia przechowująca dane o jednej książce.

static TREE *node;static TREE *tr;static TREE *poz; - zmienne pomocnicze wykorzystywane przy operacjach na drzewie.

TStringGrid *Siatka; - kontrolka typu StringGrid na głównym formularzu programu, która zawiera spis wszystkich książek jako jedną listę.

5. Opis ważniejszych funkcji modułu Modul.cpp

TREE * utw_drz(Ksiegarnia ksiazka); - Funkcja tworząca jeden węzeł w drzewie. Zwraca ona adres tego węzła.

Rel(Ksiegarnia a,Ksiegarnia r); - Zwraca wartość ujemną, gdy pozycja a jest „mniejsza” ze względu na tytuł od pozycji b, wartość dodatnią gdy a jest „większa” niż b a zero gdy tytuły tych pozycji są identyczne.

void dod_lisc(Ksiegarnia ksiazka,TREE **tr); - Wstawia rekord ksiazka do drzewa począwszy od liścia tr. Jest to procedura rekurencyjna przeszukująca drzewo tak długo, aż znajdzie właściwe miejsce do wstawienia rekordu.

void usun_drz(TREE *tr); - Rekurencyjna funkcja usuwająca całe drzewo począwszy od węzła tr.

int znaj(char *klucz,TREE **node); - Funkcja zwracająca zero, jeżeli nie ma książki o tytule klucz, w przeciwnym przypadku funkcja zwraca wartość różną od zera.

void usun_lisc(TREE **node); - Funckja usuwająca węzeł o adresie node. W przypadku, gdy węzeł ten będzie w środku drzewa, zostanie ono poprawnie przekształcone tak, aby wypełnić puste miejsce po usuniętej pozycji.

void czyta(TREE *node); - Zapisuje całą strukturę do pliku.

void del(TREE **root,char *nam,int i)- Najbardziej skomplikowana funkcja w programie. Obsługuje ona kompletne usunięcie książki ze spisu. Parametr i oznacza liczbę usuwanych egzemplarzy. W przypadku gdy będzie ona mniejsza niż liczba egzemplarzy na stanie jest on automatycznie zmiejszany o wartość i. Gdy wartość ta jest równa lub większa od wartości liczby egzemplarzy danej książki, usuwany jest cały węzeł. W każdym przypadku program wywołuje okna dialogowe z informacją lub zapytaniem o dalsze podejmowanie działania.

tree znajd(char *klucz,TREE **node); - Funkcja wyszukująca książkę według tytułu. W odróżnieniu od funkcji znaj zwraca ona adres znalezionej pozycji lub NUL, gdy takowej nie ma. Funkcja ustawia również zmienną pomocniczą found.

void znajd_a(char *klucz,TREE *node); - Znajduje pozycję w spisie według autora. Ponieważ może być dużo książek jednego autora, więc funkcja ta zapisuje indeksy wszystkich znalezionych pozycji do tablicy indeksy. Tablica ta następnie służy do wyświetlenia listy znalezionych książek w oknie dialogowym wyszukiwania.

void Initialization(); - Funkcja inicjalizująca zmienne root,tr,poz i found.

void Odswierz(TREE* x); - Funkcja przeglądająca rekurencyjnie drzewo i wpisująca wszystkie pozycje do listy Siatka.

void Wczytaj(); - Wczytuje strukturę drzewa z pliku.

void Zapisz(); - „Obudowana” funkcja czyta: zapisuje cała strukturę drzewa do pliku.

void AddBook(); - Funkcja odpowiedzialna za wyświetlenie okna dialogowego służącego do dodawania pozycji do spisu, oraz umieszczająca pozycję w drzewie.

void SellBook(); - Wyświetla okno dialogowe służące do obsługi sprzedaży książki oraz dokonuje usunięcia pozycji ze spisu.

void SearchTitle(); - Wyświetla okno dialogowe do wyszukiwania pozycji. Możliwe są dwie możliwości wyszukiwania: według tytułu i według autora. Tytuł może być tylko jeden w całym składzie, więc po znalezieniu odpowiedniej pozycji w spisie książek na głównym oknie (kontrolka Siatka) podświetlony zostaje odpowiedni wiersz. W przypadku wyszukiwania według autora może być kilka znalezionych pozycji, więc okno dialogowe powiększa się o listę tychże pozycji. Po kliknięciu na wybraną książkę w oknie głównym automatycznie wybrana zostaje ta pozycja. Okno dialogowe so wyszukiwania jest oknem niemodalnym pozostającym cały czas ponad wszystkimi innymi oknami.

void PickBook(int i); - Funkcja pomocnicza służąca do wybrania na głównej formie pozycji, której indeks przechowywany jest w tablicy indeksy na miejscu o numerze i. Wykorzystywana jest ona podczas wyszukiwania według autora.

void ChangePrice(); - Wyświetla okno z tytułem i autorem książki pozwalając na zmianę jej ceny.

void Refreshing(); - „Obudowana” funkcja Odswież.

Język C/C++ - „Dokumentacja techniczna programu „Księgarnia”. - 2 -

Drzewo zrównoważone

Drzewo niezrównoważone

---