• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Lista



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Lista z przeskokami (ang. skip list) – w informatyce struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL, czy czerwono-czarne.
    Przykład listy jednokierunkowej

    Listastruktura danych służąca do reprezentacji zbiorów dynamicznych, w której elementy ułożone są w liniowym porządku. Rozróżniane są dwa podstawowe rodzaje list: lista jednokierunkowa w której z każdego elementu możliwe jest przejście do jego następnika oraz lista dwukierunkowa w której z każdego elementu możliwe jest przejście do jego poprzednika i następnika.

    Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

    Implementacja listy[ | edytuj kod]

    Każdy element listy składa się z co najmniej dwóch pól: klucza oraz pola wskazującego na następny element listy. W przypadku list dwukierunkowych każdy element listy zawiera także pole wskazujące na poprzedni element listy. Pole wskazujące poprzedni i następny element listy są najczęściej wskaźnikami.

    Tablica w informatyce to kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy, które najczęściej przyjmują wartości numeryczne. Rozmiar tablicy jest albo ustalony z góry (tablice statyczne), albo może się zmieniać w trakcie wykonywania programu (tablice dynamiczne).Kolejka (ang. queue) – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).

    Dopisanie elementu (dla prostej listy jednostronnej):

  • jeśli ma ono nastąpić na końcu listy, to wskaźnik wiążący w obiekcie ostatnim ustawia się na nowy obiekt danego typu;
  • jeśli ma ono nastąpić wewnątrz listy, to najpierw tworzy się nowy obiekt danego typu i jego wskaźnik wiążący ustawia się na następnik elementu, za którym ma być wstawiany. Później wskaźnik poprzednika przestawia się na ten nowy obiekt. W tym przypadku bardzo ważna jest kolejność, której zachwianie jest częstą przyczyną błędów. Np. można najpierw przestawić wskaźnik poprzednika na nowy obiekt, co spowoduje bezpowrotną utratę dostępu do dalszych elementów listy, na które już nie będzie pokazywał żaden wskaźnik. Ustawienie wskaźnika nowego elementu na następnik nie będzie możliwe, bo nie będzie znany jego adres.
  • Usunięcie elementu jest odwrotne do wstawiania: w pewnym miejscu zapisuje się wskaźnik do usuwanego elementu (aby nie „zgubić” jego adresu), następnie wskaźnik wiążący poprzednika przestawia się na następnik. Dopiero w tym momencie zwalnia się pamięć po obiekcie usuwanym (do tego potrzebny jest ten wskaźnik tymczasowy).

    Tablica asocjacyjna (tablica skojarzeniowa, mapa, słownik, ang. associative array, map, dictionary) – nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.Krotka (ang. tuple) - struktura danych będąca odzwierciedleniem matematycznej n-ki, tj. uporządkowanego ciągu wartości. Krotki przechowują stałe wartości o różnych typach danych - nie można zmodyfikować żadnego elementu, odczyt natomiast wymaga podania indeksu liczbowego żądanego elementu.

    Zalety i wady listy są komplementarne w stosunku do tablicy (patrz porównanie niżej).

    Wgłębiając się w szczegóły implementacji listy można wyróżnić następujące rodzaje list:

  • lista jednokierunkowa – w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika).
    Singly-linked-list.svg
  • lista dwukierunkowa – w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika, jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony.
    Doubly-linked-list.svg
  • lista cykliczna – następnikiem ostatniego elementu jest pierwszy element. Po liście można więc przemieszczać się cyklicznie. Nie ma w takiej liście charakterystycznego ogona (ani głowy), często rozpoznawanego po tym, że jego następnik jest pusty (NULL).
    Circularly-linked-list.svg
  • lista z wartownikiem – lista z wyróżnionym elementem zwanym wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.
  • Powyższe cechy można prawie dowolnie łączyć, co daje możliwość stworzenia wielu różnych implementacji listy, zależnie od potrzeb.

    Programowanie funkcyjne (lub programowanie funkcjonalne) – filozofia i metodyka programowania będąca odmianą programowania deklaratywnego, w której funkcje należą do wartości podstawowych, a nacisk kładzie się na wartościowanie (często rekurencyjnych) funkcji, a nie na wykonywanie poleceń.Skośny system dwójkowy, binarne liczby skośne, (skew binary numbers), to system liczbowy, w którym liczby są reprezentowane w podobny lecz nie identyczny sposób do liczb dwójkowych.

    Jednokierunkowe listy są bardzo popularną podstawową strukturą danych w funkcyjnych językach programowania.

    Lista dwukierunkowa z jednym wskaźnikiem[ | edytuj kod]

    Istnieje możliwość realizacji takiej listy, wtedy gdy:

    1. Wskaźnik można utożsamiać z liczbą i wykonywać na nim działania bitowe.
    2. Wskaźnik pusty ma wartość liczbową 0.

    Wówczas pojedynczy wskaźnik zawiera różnicę symetryczną (xor) wartości liczbowej wskaźników na poprzedni i następny element listy. Podczas przechodzenia listy pamiętany jest rzeczywisty wskaźnik uprzednio odwiedzonego elementu i dzięki własności można z zakodowanej liczby odtworzyć albo poprzedni albo następny element, w zależności od kierunku przeglądania listy. Warunek 2. gwarantuje, że wskaźniki na pierwszej i ostatniej pozycji można odkodować natychmiast.

    Zaletą takiej reprezentacji jest oszczędność pamięci (jeden wskaźnik, zamiast dwóch), wadą natomiast utrudnione przeglądanie – jeśli nie rozpoczyna się od pierwszego lub ostatniego elementu, potrzeba znać co najmniej dwa wskaźniki w celu odkodowania rzeczywistych wartości.

    Podstrony: 1 [2] [3]




    Reklama

    Czas generowania strony: 0.013 sek.