Tworzenie dynamicznie połączonego stosu w C: implementacja i pułapki

Większość początkujących zakłada, że struktury danych są statyczne. To jest błędne. Powiązany stos jest jednostką dynamiczną. Rośnie i kurczy się w trakcie lotu. Nie przydzielasz pamięci z góry. Dostajesz to, kiedy tego potrzebujesz. Zwolnisz, kiedy skończysz.

W tym przykładzie użyto liczb całkowitych. Zmień typedef int stack_data na float lub char, jeśli chcesz. Logika pozostanie taka sama.

Interfejs

Spójrz na plik nagłówkowy. To jest umowa.

stack_init konfiguruje strukturę. stack_clear czyści to. stack_empty informuje, czy coś tam zostało. push wypycha dane do środka. pop je odzyskuje.

Tylko. Czysto.

Silnik

Plik źródłowy ukrywa wewnętrzne wypełnienie.

„top” oznacza najnowszy element. NULL oznacza pusty.

stack_init po prostu resetuje top do NULL. Gotowy.

stack_clear usuwa elementy, aż stos będzie pusty. To cykl. To jest tanie.

stack_empty sprawdza, czy top ma wartość NULL. Zwraca 1, jeśli jest prawdą. 0 jeśli fałszywe.

Większość pracy wykonuje stack_push.

Przydziela pamięć. Ustawia dane. Łączy je ze starym blatem. Aktualizacje „na górze”.

stack_pop uruchamia proces w odwrotnej kolejności.

Bierze dane. Przesuwa „górę” w dół. Zwalnia stary węzeł. Zwraca wartość.

A co jeśli stos jest pusty? Zwróci śmieci. Nie pobieraj danych z pustego stosu.

Ukrywanie informacji

To jest kluczowy punkt.

Widzisz tylko plik nagłówkowy. Nie widzisz kodu implementacyjnego.

Stos może używać tablic. Wskaźniki. Akta. Połączona lista. Nie ma znaczenia.

Dopóki interfejs działa, nie obchodzi Cię, jak jest zaprojektowany.

To ukrywanie informacji. To nie tylko modne hasło. W ten sposób tworzy się oprogramowanie, które nie psuje się przy zmianie wewnętrznej implementacji.

Funkcje C

C jest bezlitosny.

1. Nawiasy mają znaczenie. (*p).i to nie to samo co *p.i. W pierwszym przypadku najpierw następuje dereferencja wskaźnika. W drugim przypadku najpierw uzyskaj dostęp do elementu członkowskiego, a następnie wyłuskuj. Jeśli popełnisz błąd, spotka cię porażka.
2. Wycieki pamięci. Nigdy nie przypisuj po prostu top = NULL. Stracisz wszystkie węzły na liście. Stracisz dane. Stracisz pamięć. Użyj „bezpłatnego”. Zawsze.
3. Dołącz pliki nagłówkowe. NULL znajduje się w stdio.h. Jeśli zapomnisz go dołączyć, Twój kod może się nie skompilować w niektórych kompilatorach. Ale nie na innych. Lub w dziwny sposób zdefiniuje „NULL” jako zero. Dołącz , jeśli używasz wskaźników.

Co dalej?

Podstawowy stos jest prosty. Prawdziwe stosy wymagają więcej.

Dodaj „dup”. Powiel górny element. Dodaj „liczbę”. Zwróć liczbę elementów. Dodaj „dodaj”. Wyjmij dwa górne elementy, złóż je i odłóż wynik.

Napisz program sterownika. Napisz plik Makefile. Skompilować. Uruchom to.

Jeśli się zawiesi, przegapiłeś opcję „bezpłatny”. Lub uzyskałeś dostęp do wolnej pamięci. Odpluskwić.

Prawdziwa ocena

Dynamiczna alokacja pamięci jest szybka. Dopóki nie stanie się inaczej.

malloc i free mają narzut. W ciasnych cyklach to się kumuluje.

Ale do ogólnego użytku? Jest elastyczny. To jest standardowe. To właśnie zobaczysz w większości baz kodu C.

Powiązany stos jest elementem konstrukcyjnym.

Będziesz go używać do wykonywania wywołań funkcji. Aby ocenić wyrażenia. Dla przycisków „Anuluj”.

On jest wszędzie.

Pamiętaj tylko: jeśli alokujesz pamięć, musisz ją zwolnić. W przeciwnym razie.

„Kod jest jak humor”