Listy jednokierunkowe, dwukierunkowe, cykliczne
Dynamiczne struktury
Stworzenie dynamicznej struktury danych sprowadza się do stworzenia:
- struktury zawierającej wskaźnik(i) na samą siebie, oraz zmienne wskazywane
- funkcje narzędziowe zapewniające możliwość tworzenia i przetwarzania dynamicznych struktur
Stosy i kolejki są to implementacje zbiorów dynamicznych, w których dostęp mamy do jednoznacznie określonych elementów (pierwszy i,lub ostatni).
Listą nazywamy liniowo uporządkowany zbiór składników, z którego w dowolnym miejscu można usunąć składnik, jak również dołączyć nowy. W zależności od typu wiązań między składnikami wyróżniamy listy: jednokierunkowe, dwukierunkowe, cykliczne.
Listy jednokierunkowe:
Organizacja listy jednokierunkowej podobna jest do stosu, tzn. dla każdego składnika (poza ostatnim) jest określony składnik następny lub dla każdego składnika (poza pierwszym) jest określony składnik poprzedni.
Struktura:
typedef struct Element_listy{
typ_danych dane;
struct Element_listy *wskaznik;
} T_lista;
Dane są dowolnego typu, natomiast zmienna HEAD jest wskaźnikiem na składnik listy i przechowuje adres pierwszego elementu (gdy lista jest pusta przechowuje NULL).
Funkcje:
T_lista Znajdź(T_lista *HEAD, typ_danych x)
/*funkcja szuka elementu x w liście na którą wskazuje HEAD, zwraca jego adres
albo null gdy lista nie zawiera elementu x.*/
{
T_lista *temp;
temp=HEAD;
while ( temp!=NULL && temp->dane!=x)
temp=temp->wskaznik;
return temp;
}
Pesymistyczny czas działania tej funkcji na liście n-elementowej wynosi teta(n), ponieważ niekiedy konieczne jest przejście całej listy.
void Wstaw(T_lista *BIEZACY,typ_danych x)
/*funkcja wstawia element x do listy za elementem na który wskazuje
wskaźnik BIEZACY*/
{
T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));
nowy->dane=x; //1
nowy->wskaznik=BIEZACY->wskaznik; //2
BIEZACY->wskaznik=nowy; //3
}
W podobny sposób można napisać funkcję wstawiającą element na pozycji przed pierwszym składnikiem listy:
void Wstaw(T_lista **HEAD, typ_danych x)
/*funkcja wstawia element x do listy na pozycji przed pierwszym składnikiem*/
{
T_lista nowy=(T_lista *)malloc(sizeof(T_lista));
nowy->dane=x;
nowy->wskaznik=*HEAD;
*HEAD=nowy;
}
Obydwie funkcje wstawiania działają w czasie O(1)
void Usuń(T_lista **HEAD, typ_danych x)
/*funkcja usuwa składnik x z listy na którą wskazuje wskaźnik HEAD*/
{
T_lista *temp;
T_lista *poprzedni;
temp=*HEAD;
while(temp!=NULL && temp-> dane!=x)
poprzedni=temp;
temp=temp->wskaznik;
if(temp==*HEAD) *HEAD=*HEAD->wskaznik;
else poprzedni->wskaznik=temp->wskaznik;
if (temp!=NULL) free(temp);
}
Listy dwukierunkowe:
Listą dwukierunkową nazywamy liniowo uporządkowany zbiór składników, w którym dla każdego składnika, poza pierwszym i ostatnim, określony jest składnik poprzedni i następny.
Struktura:
typedef struct Element_listy{
typ_danych dane;
struct Element_listy *wskaznik1;
struct Element_listy *wskaznik2;
} T_lista;
Funkcje:
Wyszukiwanie elementu x w listach dwu- i jednokierunkowych odbywa się w ten sam sposób, natomiast wstawianie i usuwanie elementów jest łatwiejsze.
void Wstaw(T_lista *BIEZACY, typ_danych x)
/*funkcja wstawia element x do listy za elementem na
który wskazuje wskaźnik BIEZACY*/
{
T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));
nowy->dane=x;
nowy->wskaznik1=BIEZACY->wskaznik1; //2
nowy->wskaznik2=BIEZACY; //3
BIEZACY->wskaznik1=nowy; //4
nowy->wskaznik1->wskaznik2=nowy; //5
}
W podobny sposób można napisać funkcję wstawiającą element na pozycji przed pierwszym składnikiem listy:
void Wstaw(T_lista **HEAD,typ_danych x)
/*funkcja wstawia element x do listy na pozycji przed pierwszym składnikiem*/
{
T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));
nowy->dane=x;
nowy->wskaznik1=*HEAD;
nowy->wskaznik2=NULL;
*HEAD=nowy;
}
void Usuń(T_lista **HEAD,typ_danych x)
/*funkcja usuwa składnik x z listy na którą wskazuje wskaźnik HEAD*/
{
T_lista *temp;
temp=HEAD;
while(temp!=NULL && temp->dane!=x)
temp=temp->wskaznik1;
if(temp==HEAD)
{
HEAD=HEAD->wskaznik1;
temp->wskaznk1->wskaznik2=NULL;
}
else if (temp!=NULL)
{
temp->wskaznik2->wskaznik1=temp->wskaznik1; //6
temp->wskaznik1->wskaznik2=temp->wskaznik2; //7
free(temp);
}
}
Listy cykliczne:
Gdyby można było pominąć warunki brzegowe dotyczące głowy i ogona listy, funkcje obsługujące listę znacznie by się uprościły. Tę rolę odgrywa wartownik, sztuczny element który pozwala uprościć warunki brzegowe. Wartownik zastępuje stałą NULL w listach jednokierunkowych i dwukierunkowych (wszędzie gdzie w listach występowała stała NULL wstawiamy wskaźnik na wartownika). W listach dwukierunkowych wartownik zawiera wskaźniki na głowę i ogon listy.
Struktura:
typedef struct Element_listy{
typ_danych dane;
struct Element_listy *next;
struct Element_listy *prev;
} T_lista;
/*Listę inicjalizuje się następująco:*/
T_lista *WARTOWNIK=(T_lista *)malloc(sizeof(T_lista));
WARTOWNIK->next=WARTOWNIK;
WARTOWNIK->prev=WARTOWNIK;
Pusta lista wygląda tak:
gdzie WARTOWNIK to wskaźnik do wartownika. Zaś lista z dwoma elementami tak:
Funkcje:
T_lista *Znajdź(T_lista *WARTOWNIK, typ_danych x)
/*funkcja szuka elementu x w liście na którą wskazuje HEAD,
zwraca jego adres albo null gdy lista nie zawiera elementu x.*/
{
T_lista *temp;
temp=WARTOWNIK->next;
while (temp!=WARTOWNIK && temp->dane!=x)
temp=temp->next;
return temp;
}
void Wstaw(T_lista *BIEZACY, typ_danych x)
/*funkcja wstawia element x za elementem BIEZACY,
gdy chcemy dodać element na początku listy to BIEZACY=WARTOWNIK*/
{
T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));
nowy->next=BIEZACY->next;
nowy->prev=BIEZACY;
nowy->next->prev=nowy;
BIEZACY->next=nowy;
}
void Usuń(T_lista *WARTOWNIK, T_lista *BIEZACY)
{
If (BIEZACY!=WARTOWNIK)
{
BIEZACY->prev->next=BIEZACY->next;
BIEZACY->next->prev=BIEZACY->prev;
}
}
Użycie wartownika nie poprawia złożoności operacji na strukturze danych, ale często prowadzi do zmniejszenia stałych współczynników. Korzyść wynikająca z zastosowania wartowników w pętlach programu polega często na poprawie czytelności programu, a nie szybkości jego działania.
Bibliografia
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Clifford Stein -
- "Wprowadzenie do algorytmów", WNT Warszawa 2004, wyd. szóste
- A. Marciniak – „Turbo Pascal 7.0 z elementami programowania” cz. 1, BUM Poznań 1990-1994
Aby dodawać komentarze musisz być zalogowany!