Struktury danych/Dla twórców podręcznika

Spis treści
Wstęp

Wstęp - Konwencje

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

edytuj

Niniejsza 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.

Podrę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:

  1. Wstęp ilustrujący problem, który mamy do rozwiązania (np. wady jakiejś innej struktury)
  2. Krótki opis obrazowy streszczający ideę kryjącą się za daną strukturą
  3. Bardziej naukowa definicja struktury danych
  4. Operacje, jakie można wykonywać na danej strukturze
  5. Sposoby implementacji
  6. Ć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

edytuj

We 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:

  1. Nazwy operacji wykonywanych na strukturze danych - dużymi literami, np. INSERT, DELETE
  2. Angielskie nazwy struktur danych jako typy, np. Set, List
  3. Typ Data do reprezentowania jakichś abstrakcyjnych danych umieszczanych w strukturze.
  4. Reszta małymi literami.

Przyjmujemy, że funkcja write potrafi wyświetlić wszystko.

Jeśli chodzi o dział Implementacje, stosujemy następujące reguły:

  1. Styl docelowy.
  2. Wcięcia czteroznakowe (spacja).
  3. W nazewnictwie posługujemy się underscore (tj. zmienne, funkcje itd. nazywamy jako nazwa_funkcji, a nie nazwaFunkcji albo nazwafunkcji).
  4. Poszczególne części algorytmu staramy się separować linijką przerwy.
  5. Kod musi być skomentowany, najlepiej komentarzami jednolinijkowymi.
  6. Implementacja musi być zapisana z użyciem programowania strukturalnego wraz z abstrakcją danych.
  7. Kod piszemy w języku angielskim.
  8. Komentarze piszemy w języku polskim.
  9. 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ć.
  10. Używamy C++11 oraz C++14.

Pascal

edytuj
  1. Wcięcia trójznakowe
  2. "begin" w nowej linijce
  3. W nazewnictwie posługujemy się camelStyle (tj. zmienne, funkcje itd. nazywamy jako nazwaFunkcji, a nie nazwa_funkcji albo nazwafunkcji).
  4. Poszczególne części algorytmu staramy się separować linijką przerwy.

Formatowanie

edytuj

W opisie stosujemy następującą konwencję:

  1. kursywa - nazwy zmiennych, funkcji przy nawiązaniach do kodu algorytmu
  2. pogrubienie - nazwy struktur kontrolnych, np. for, if oraz predefiniowanych wartości, np. null
  3. Akapitów używamy zgodnie z przeznaczeniem, tj. do zmiany wątku, a nie do separacji zdań, jak czasem się niektórym zdarza robić.
  4. Kolorujemy składnię! Szczegóły: Pomoc:Podświetlanie_składni

Szablony

edytuj

Oto 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
  • do wstawiania w sekcji
  • stosować tylko w rozdziałach, w których większość tekstu jest napisana
{{RDoZrobienia}}
  Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.
Artykuł do poprawy {{dopracować|powód}}

Nawigacja

edytuj

Wykaz szablonów nawigacyjnych:

Opis Kod Efekt
Główna nawigacja {{Struktury danych/SpisTreści}}
Spis treści
Wstęp

Wstęp - Konwencje

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

Menu implementacji: C++ {{Struktury danych/ImplC++}}
Implementacje w C++

Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Tablice haszujące - Grafy

Menu implementacji: Pascal {{Struktury danych/ImplPascal}}
Implementacje w Pascalu

Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Tablice haszujące - Grafy