CPW - C\C++ :: Artykuły :: Lista dwukierunkowa w C

Programowanie

Programy

Strona główna -> C\C++ -> Artykuły -> Lista dwukierunkowa w C

Lista dwukierunkowa to jedna z najczęściej używanych struktur danych.
W odróżnieniu od tablicy można bardzo łatwo wstawić element w jej środek oraz go usunąć. Nie zapewnia ona jednak szybkiego dostępu do dowolnego elementu - zawsze trzeba przejść przez listę od jednego końca lub od drugiego, aby uzyskać dostęp do rządanego elementu.

Kiedy należy stosować listę ??

Listy najczęściej stosujemy, gdy nie jesteśmy w stanie przewidzieć ilości potrzebnych nam elementów oraz często dodajemy i usuwamy elementy.

Co jest potrzebne do zbudowania listy??

Podstawowa rzecz jaka jest potrzebna to pojedyńcza komórka przechowująca interesujące nas dane. Zadeklarujemy ją w postaci struktury:

struct ListElement
{
struct ListElement *next, *prev;
int wartosc;
};

Jak widać zawiera ona wskaźniki na poprzedni oraz następny element oraz pole danych typu int (przyjmujemy tak dla uproszczenia - w rzeczywistości struktura może być bardzo rozbudowana).

Następną rzeczą potrzebną nam do budowy są metody, które zaalokują potrzebną pamięć oraz odpowiednio powiążą elementy ze sobą:

void addBegin(struct ListElement **head,struct ListElement **tail, int value)
void addEnd(struct ListElement **head,struct ListElement **tail, int value)
void addMiddle(struct ListElement **head, struct ListElement **tail, int value, int pos)

Wszystkie trzy metody w parametrach otrzymują wskaźniki na pierwszy, ostatni element listy oraz dane, które mają być przechowywane.
Trzecia metoda dodatkowo otrzymuje informacje gdzie nowy element ma zostać wstawiony.

Implementacje metod:

// ******* addBegin *******
void addBegin(struct ListElement **head,struct ListElement **tail, int value)
{
struct ListElement *a;
a =(struct ListElement*)malloc(sizeof(struct ListElement));
a->wartosc = value;
if ((*head)==NULL && (*tail)==NULL)
{
*head=a;
*tail=a;
a->next=NULL;
a->prev=NULL;
}
else
{
a->next=*head;
a->prev=NULL;
(*head)->prev=a;
(*head)=a;
}
}
// ******* addEnd *******
void addEnd(struct ListElement **head,struct ListElement **tail, int value)
{
struct ListElement *a;
a =(struct ListElement*)malloc(sizeof(struct ListElement));
a->wartosc = value;
if ((*head)==NULL && (*tail)==NULL)
{
*head=a;
*tail=a;
a->next=NULL;
a->prev=NULL;
}
else
{
a->prev = *tail;
a->next = NULL;
(*tail)->next = a;
(*tail)=a;
}
}
// ******* addMiddle *******
void addMiddle(struct ListElement **head, struct ListElement **tail, int value, int pos)
{
int m;
struct ListElement *a,*b;
a =(struct ListElement*)malloc(sizeof(struct ListElement));
if (pos == 0)
{
addBegin(head,tail,value);
}
else
{
if (ValidatePosition(*head,*tail,&b,pos))
{
if ((b->next)=NULL)
{
addEnd(head,tail,value);
}
else
{
a->prev=b->prev;
a->next=b;
(b->prev)->next=a;
b->prev=a;
a->wartosc=value;
}
}
}
}

W implementacji funkcji addMiddle użyliśmy metody pomocniczej ValidatePosition, która wygląda następująco:

// ******* ValidatePosition *******
int ValidatePosition(struct ListElement *head, struct ListElement *tail, struct ListElement **p1, int pos)
{
int i,k;
struct ListElement *a;
if (pos<0)
{
return 0;
}
else
{
a=head;
i=0;
k=500;
while (k)
{
if (pos==i)
{
*p1=a;
return 1;
}
else
{
if ((a->next)!=NULL)
{
a=a->next;
i++;
}
else
{
return 0;
}
}
}
}
}

Mając wszystko, co potrzebne jest do budowy warto również pomyśleć o usuwaniu elementów i zwolnieniu całej listy (potrzebne np. przy kończeniu działania programu)

A oto metody do tego służące:

void deleteBegin(struct ListElement **head,struct ListElement **tail)
void deleteEnd(struct ListElement **head,struct ListElement **tail)
void deleteMiddle(struct ListElement **head, struct ListElement **tail, int pos)
void ReleaseList(struct ListElement **head, struct ListElement **tail)

Implementacje metod :

// ******* deleteBegin *******
void deleteBegin(struct ListElement **head,struct ListElement **tail)
{
struct ListElement *a;
if ((*head)!=NULL)
{
if ((*tail)==(*head))
{
*tail=NULL;
free(*head);
*head=NULL;
}
else
{
a=(*head)->next;
(*head)->next->prev=NULL;
free(*head);
*head=a;
}
}

}

// ******* deleteEnd *******
void deleteEnd(struct ListElement **head,struct ListElement **tail)
{
struct ListElement *a;
if ((*tail)!=NULL)
{
if ((*tail)==(*head))
{
*tail=NULL;
free(*head);
*head=NULL;
}
else
{
a=(*tail)->prev;
a->next=NULL;
free(*tail);
*tail=a;
};
}
}

// ******* deleteMiddle *******
void deleteMiddle(struct ListElement **head, struct ListElement **tail, int pos)
{
struct ListElement *a;
if (pos==0)
{
deleteBegin(head,tail);
}
else
if (ValidatePosition(*head,*tail,&a,pos))
{
if (a->next==NULL)
{
deleteEnd(head,tail);
}
else
{
a->prev->next=a->next;
a->next->prev=a->prev;
free(a);
}
}

}

Posiadamy już wszystko, co było potrzebne do budowy oraz zwalniania listy, aby jednak móc jej użyć musimy jeszcze posiadać metody, które np. wypiszą liste, wyszukają w niej określony element lub wykonają dowolną inną operacje. Te metody każdy musi już stworzyć sam, aby były dostosowane do konkretnych potrzeb. W metodach przedstawionych wyżej znajduje się wiele informacji przydatnych przy pisaniu takich funkcji (np. jak przechodzić po liście).

Dodatkowa wskazówka : w wielu implementacjach list korzysta się z dodatkowego wskaźnika, który wskazuje na bierzący element listy.

Autorem tekstu jest: Jakub Leśniak

Materiał dodany przez użytkownika: kubal5003

C\C++

C++Builder

Delphi

Pascal

Asembler

Algorytmika

Ogólne

(X)HTML

CSS

PHP

MySQL

ASP

JavaScipt

Ogólne

Źródła

Skrypty

Kursy Off-line

Komponenty

Programy