Lista powiązana w C++

Co to jest lista powiązana?

Jest to dynamiczna struktura danych. Składa się z elementów tego samego typu, które oprócz swoich danych posiadają wskaźnik do następnego elementu listy. W ten sposób mozemy przebiegać całą listę od początku do końca.

Czemu lista, a nie tablica?

Ktoś pewnie zapyta. Odpowiedź jest prosta. Tablica to w dużej ilości przypadków marnotrawienie pamięci. Powiedzmy, że piszemy bazę danych książek (przechowywaną w pamięci RAM). Jeśli mielibyśmy korzystać z tablicy, to już na początku musimy zadeklarować odpowiedni rozmiar tablicy, tak aby mógła pomieścić wszytskie możliwe książki. Lista daje nam tę wygode, że początkowo nie zajmuje prawie żadnej pamięci. Gdy dodajemy nową książkę to tworzymy po prostu nowy element listy i tylko dla niego alokujemy pamięć.

Dzięki temu lista może nie zawierać żadnych elementów, może zawierać zarówno 10 jak i 10 tysięcy elementów, a zajmowana pamięć jest wprost proporcjonalna do ilości przechowywanych elementów.

Różne typy list powiązanych

Prosta lista w C++

Teraz spróbujemy napisać implementację prostej listy jednokierunkowej w C++. Lista taka może być podstawą dla bardziej użytecznych dynamicznych struktur danych, jak np. kolejka, stos, czy dynamiczna tablica.

Załóżmy, że elementy naszej listy maja przechowywać wartość typu int. (Jest to dość abstrakcyjny przypadek, gdyż listy zazwyczaj przechowują elementy składające się z bardziej rozbudowanych typów).

Najpierw zdefiniujemy element listy:

struct SElement
{
 int Value;
 SElement* Next;
};

Następnie będzie nam potrzebna zmienna - wskaźnik do pierwszego elementu listy:

SElement* First;

i do ostatniego elementu (dla wygody - nie jest niezbędna):

SElement* Last;

Nastpnie zmienna - rozmiar listy:

int Size = 0;    // liczba elemntów na liscie

Następnie należy zdefiniować podstawowe funkcje do obsługi listy:

void Put (int NValue, int Pos);    //Dokłada element do listy
void Get (int Pos);        //Zabiera i zwraca element z listy

Najlepiej jest zebrać wszystkie zmienne i funkcje w jedną klasę np. o nazwie CList.

Jeśli ktoś ma pytania co do szczegółowej implementacji listy to proszę o e-maile.(adres na końcu)

Wzorzec - Dynamiczna tablica TArray

Poniżej mozna sobie ściągnąć dobra implementację (kod źródłowy) wzorca dynamicznej tablicy z wykorzytsaniem listy jednokierunkowej.

Jest to tablica dowolnego (jednego) typu, którą deklaruje się następująco:

#include<tarray.cpp>
...
TArray<float> Tablica;

A interfejs klast TArray wygląda tak:

template<class T>
class TArray
{
...
public:
 TArray();
 ~TArray();

void Add(T NItem);
void Insert(T NItem, unsigned Pos);
T Remove(unsigned Pos);
void Clear();
unsigned GetSize();

T& operator[](unsigned Pos);

class EOutOfMemory {};
class EOutOfRange {};
};

Z doświadczenia wiem, że taka klasa może przydać się w praktycznym pisaniu programów.

Autor

Autor: Mr Bin
Data: 26.12.2000
E-mail: delfisajt@poczta.onet.pl
WWW : www.delfisajt.republika.pl