Struktury danych/Dla twórców podręcznika
Spis treści | |
Wstęp | |
Struktury danych |
Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy |
Dodatki |
Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika |
Dla twórców podręcznika
edytujNiniejsza strona zbiera zalecenia dla autorów i standardy, w jakich pisany będzie podręcznik. Aktualnie znajduje się on w BARDZO początkowej fazie tworzenia, dlatego możliwe są zmiany. Wszelkie nowe propozycje prosimy zgłaszać na stronie dyskusji.
Styl
edytujPodręcznik adresowany jest przede wszystkim do osób rozpoczynających swą przygodę z algorytmami, a także pragnących uporządkować swą wiedzę na ten temat. Staramy się pisać tak, aby nie przypominał on pracy zaliczeniowej jakiegoś znużonego studenta - najważniejsza jest przystępność oraz staranność opisów. Nie mamy nic przeciwko opisom obrazowym, ponieważ jest to świetne uzupełnienie naukowych i technicznych definicji.
Przy omawianiu każdej struktury danych trzymamy się następującego schematu:
- Wstęp ilustrujący problem, który mamy do rozwiązania (np. wady jakiejś innej struktury)
- Krótki opis obrazowy streszczający ideę kryjącą się za daną strukturą
- Bardziej naukowa definicja struktury danych
- Operacje, jakie można wykonywać na danej strukturze
- Sposoby implementacji
- Ćwiczenia (podział na część Podstawową oraz Zaawansowaną)
Podręcznik dodatkowo zawiera dwa rozdziały zatytułowane odpowiednio: Implementacje w C++ oraz Implementacje w Pascalu pokazujące działające przykładowe implementacje w dwóch językach programowania C++ oraz Pascal wraz z przykładami użycia. Mają one charakter zapoznawczy.
Podręcznik zakłada, że czytelnik ma jakieś pojęcie nt tego, czym jest złożoność obliczeniowa. W razie czego, jest ona dokładniej wyjaśniona w jednym z dodatków, zatem można śmiało stosować w opisach notację dużego O oraz dużej Ω.
Przykłady
edytujWe właściwej części podręcznika do prezentacji algorytmów stosujemy pseudokod ze składnią Pascalową. Uproszczenia polegają na tym, że niektóre fragmenty zastępujemy krótkim opisem słownym - przeważnie dotyczy to miejsc, gdzie implementacja tego, co napisaliśmy, okropnie zagmatwałaby kod. Ponadto korzystamy z operacji zdefiniowanych na początku rozdziału (np. INSERT) jak funkcji, również, aby uprościć kod. Przyjmujemy, że nazwy operacji zapisane są dużymi literami. Opis słowny umieszczamy między znakami mniejszości i większości. Oto przykład:
procedure ABC(V: Data); var S: Set; P: Data; begin for <każdy element P w zbiorze S> do begin write(P); end; end;
Stosujemy nazewnictwo:
- Nazwy operacji wykonywanych na strukturze danych - dużymi literami, np. INSERT, DELETE
- Angielskie nazwy struktur danych jako typy, np. Set, List
- Typ Data do reprezentowania jakichś abstrakcyjnych danych umieszczanych w strukturze.
- Reszta małymi literami.
Przyjmujemy, że funkcja write potrafi wyświetlić wszystko.
Jeśli chodzi o dział Implementacje, stosujemy następujące reguły:
C++
edytuj- Styl docelowy.
- Wcięcia czteroznakowe (spacja).
- W nazewnictwie posługujemy się underscore (tj. zmienne, funkcje itd. nazywamy jako nazwa_funkcji, a nie nazwaFunkcji albo nazwafunkcji).
- Poszczególne części algorytmu staramy się separować linijką przerwy.
- Kod musi być skomentowany, najlepiej komentarzami jednolinijkowymi.
- Implementacja musi być zapisana z użyciem programowania strukturalnego wraz z abstrakcją danych.
- Kod piszemy w języku angielskim.
- Komentarze piszemy w języku polskim.
- W implementacji NIE korzystamy ze struktur danych dostępnych w STL - w końcu po to jest ten dział, by czytelnik sam nauczył się dane struktury pisać.
- Używamy C++11 oraz C++14.
Pascal
edytuj- Wcięcia trójznakowe
- "begin" w nowej linijce
- W nazewnictwie posługujemy się camelStyle (tj. zmienne, funkcje itd. nazywamy jako nazwaFunkcji, a nie nazwa_funkcji albo nazwafunkcji).
- Poszczególne części algorytmu staramy się separować linijką przerwy.
Formatowanie
edytujW opisie stosujemy następującą konwencję:
- kursywa - nazwy zmiennych, funkcji przy nawiązaniach do kodu algorytmu
- pogrubienie - nazwy struktur kontrolnych, np. for, if oraz predefiniowanych wartości, np. null
- Akapitów używamy zgodnie z przeznaczeniem, tj. do zmiany wątku, a nie do separacji zdań, jak czasem się niektórym zdarza robić.
- Kolorujemy składnię! Szczegóły: Pomoc:Podświetlanie_składni
Szablony
edytujOto wykaz szablonów używanych w podręczniku:
Opis | Kod | Efekt | ||
---|---|---|---|---|
Ostrzeżenie czytelnika | {{Uwaga|Tekst ostrzeżenia}} |
| ||
Porada | {{Porada|Tekst porady}} |
| ||
Informacja | {{Infobox|Tekst informacji}} |
| ||
Definicja | {{Definicja|Tekst definicji}} |
| ||
Do zrobienia | {{TODO|co zrobić}} |
| ||
Do zrobienia
|
{{RDoZrobienia}} |
| ||
Artykuł do poprawy | {{dopracować|powód}} |
|
Nawigacja
edytujWykaz szablonów nawigacyjnych:
Opis | Kod | Efekt | |||||||
---|---|---|---|---|---|---|---|---|---|
Główna nawigacja | {{Struktury danych/SpisTreści}} |
| |||||||
Menu implementacji: C++ | {{Struktury danych/ImplC++}} |
| |||||||
Menu implementacji: Pascal | {{Struktury danych/ImplPascal}} |
|