Stos

Stos (1) Przykładowy stos i operacja dodawania elementu (na pomarańczowo oznaczono wskaźniki po dodaniu)
REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 1. Projektowanie stron internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−14%39,95 zł
Algorytmy. Ćwiczenia
34,90 zł

Stos (ang. Stack) – struktura danych, w której bezpośredni dostęp jest tylko do ostatnio dodanego elementu. Stos bywa określany także jako kolejka LIFO (z ang. Last In, First Out, czyli: ostatni na wejściu, pierwszy na wyjściu). Stos można sobie wyobrazić jako kilka rzeczy ułożonych „jedna na drugiej” – łatwo można wziąć tylko rzecz leżącą na samym wierzchu, gdyż pozostałe są przykryte.

Implementacja

W tej sekcji przedstawiona jest przykładowa implementacja w języku C++ stosu przechowującego liczby typu int. Opis ten jest adresowany przede wszystkim do osób, które dopiero chcą zrozumieć ideę dynamicznych struktur danych, zatem jest on dość opisowy.

Elementem leżącym na stosie będzie nie sama liczba, ale struktura (nazwijmy ją sobie ElementStosu) zawierająca:

  • Przechowywany element (w naszym przypadku będzie to liczba typu int),
  • Wskaźnik do kolejnego elementu.

W kodzie programu tworzymy zmienną typu ElementStosu*, która jest wskaźnikiem na element znajdujący się na wierzchu stosu. Początkowo nasz stos jest pusty, więc wskaźnik ten ma przypisaną zerową wartość. Potrzebne nam są teraz funkcje umożliwiające dodanie elementu na stos oraz pobranie elementu ze stosu. Dodanie nowego elementu powinno przebiegać następująco:

  1. Tworzymy nowy element typu ElementStosu.
  2. Jako element danej struktury przypisujemy liczbę, którą chcemy dodać na stos.
  3. Jako wskaźnik do następnego elementu ustawiamy wskaźnik do elementu, który aktualnie jest na wierzchu stosu.
  4. Ustawiamy nasz nowy element jako wierzch stosu.

Ponieważ zmienna przechowująca początek stosu jest modyfikowana, musimy przekazać ją do funkcji przez referencję (ewentualnie przez wskaźnik). Poniższy kod źródłowy zawiera implementację struktury ElementStosu, funkcji dodającej element na stos i przykładowe wykorzystanie tej funkcji w funkcji main.

struct ElementStosu
{
	int liczba;
	ElementStosu* nastepny;
};

void dodajDoStosu(ElementStosu* &stos, int liczba)
{
	ElementStosu* nowy = new ElementStosu();
	nowy->liczba = liczba;
	nowy->nastepny = stos;
	stos = nowy;
};

int main()
{
	ElementStosu* stos = 0;
	dodajDoStosu(stos, 2);
	dodajDoStosu(stos, 5);
	return 0;
}

Zwróćmy uwagę, że po dodaniu liczby 5 tracimy bezpośredni dostęp do liczby 2 – aby się do niej dostać, musielibyśmy przejść przez kolejne wskaźniki: stos->nastepny->liczba. Zastanówmy się teraz, jak pobrać liczbę z wierzchu stosu. Tym razem musimy przestawić wskaźnik wierzchu stosu na drugi element, a pierwszy element przeczytać i usunąć. Wygląda to następująco:

  1. Odczytujemy liczbę z dawnego pierwszego elementu stosu, zapisujemy ją do tymczasowej zmiennej,
  2. Tworzymy tymczasowy wskaźnik do pierwszego elementu stosu,
  3. Ustawiamy drugi element stosu jako jego wierzch,
  4. Usuwamy z pamięci element, na który wskazuje tymczasowy wskaźnik,
  5. Zwracamy liczbę odczytaną w punkcie 1.

Kod źródłowy takiej funkcji jest następujący:

int pobierzZeStosu(ElementStosu* &stos)
{
	int liczba = stos->liczba;
	ElementStosu* doUsuniecia = stos;
	stos = stos->nastepny;
	delete doUsuniecia;
	return liczba;
};

Warto zauważyć, że wywołanie tej funkcji jest możliwe tylko wtedy, gdy stos nie jest pusty – w przeciwnym razie program zakończy się błędem. Podstawowe funkcje stosu mamy już zaimplementowane. Żeby móc wygodnie przetestować ich działanie napiszmy jeszcze funkcję, która wypisze nam całą zawartość stosu. Jak wspominaliśmy, bezpośredni dostęp mamy tylko do wierzchu stosu. Żeby dostać się głębiej, musimy „przewijać” stos przechodząc po kolejnych wskaźnikach. Algorytm ten jest następujący:

  1. Utwórz tymczasowy wskaźnik, początkowo niech pokazuje on na wierzch stosu,
  2. Jeśli wskaźnik ma wartość 0 (jesteśmy na końcu stosu), zakończ wypisywanie. W przeciwnym razie:
  3. Wypisz wartość aktualnego elementu,
  4. Ustaw tymczasowy wskaźnik na kolejny element stosu,
  5. Wróć do punktu 2.

Pełny przykład programu, zawierający wszystkie opisane w tym artykule funkcje, jest zamieszczony poniżej.

#include<iostream>

using namespace std;

struct ElementStosu
{
	int liczba;
	ElementStosu* nastepny;
};

void dodajDoStosu(ElementStosu* &stos, int liczba)
{
	ElementStosu* nowy = new ElementStosu();
	nowy->liczba = liczba;
	nowy->nastepny = stos;
	stos = nowy;
};

int pobierzZeStosu(ElementStosu* &stos)
{
	int liczba = stos->liczba;
	ElementStosu* doUsuniecia = stos;
	stos = stos->nastepny;
	delete doUsuniecia;
	return liczba;
};

void wypiszStos(ElementStosu* &stos)
{
	ElementStosu* aktualny = stos;
	while (aktualny != 0)
	{
		cout << aktualny->liczba << " ";
		aktualny = aktualny->nastepny;
	}
	cout << "\n";
};

int main()
{
	ElementStosu* stos = 0;
	dodajDoStosu(stos, 2);
	dodajDoStosu(stos, 5);
	dodajDoStosu(stos, 7);

	wypiszStos(stos);

	int pobrane = pobierzZeStosu(stos);
	cout << "Pobrano: " << pobrane << "\n";
	wypiszStos(stos);

	dodajDoStosu(stos, 6);
	wypiszStos(stos);

	system("pause");

	// Czyszczenie pamięci
	while (stos != 0)
	{
		pobierzZeStosu(stos);
	}

	return 0;
}

Zobacz też

Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 13 kwietnia 2018 21:26, ostatnia edycja: 10 listopada 2018 11:12.

REKLAMA

Zobacz też

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Polityka prywatnościKontakt