Informacje zawarte w pliku to: dwukierunkowa lista liniowa, implementacja listy dwukierunkowej jako dynamicznej struktury danych.
Podstawy Programowania semestr drugiWykład czwarty1. Dwukierunkowa lista liniowa
Dwukierunkowa lista liniowa różni się w niewielkim stopniu od jednokierunkowej listy liniowej. Zasadnicza różnica w funkcjonalności polega
na tym, że elementy listy dwukierunkowej możemy przeglądać zarówno od początku do ko c
ń a, jak i od końca do początku. W przypadku listy
jednokierunkowej, jak sama nazwa wskazuje, przeglądanie możliwe jest tylko od początku do końca.
2. Implementacja listy dwukierunkowej jako dynamicznej struktury danych
Lista dwukierunkowa, podobnie jak jej poprzedniczka zostanie opisana na przykładzie programu, który wstawia do niej kolejne elementy, tak
aby warto c
ś i, które one przechowują znajdowały się w porządku niemalej c
ą ym. Definicja typu pojedynczego elementu listy dwukierunkowej
zawiera dwa pola wskaźnikowe (wiersze 5-9). Pole „next” przeznaczone jest na zapamiętanie adresu następnego elementu w li c
ś ie, pole „prev”
będzie słu y
ż ło do przechowywania adresu poprzedniego elementu. Wartość tego pola dla pierwszego elementu na li c
ś ie będzie wynosiła
„NIL”, podobnie jak wartość pola „next” ostatniego elementu listy. Tak jak w przypadku jednokierunkowej listy potrzebujemy tylko jednej
globalnej zmiennej wskaźnikowej, która będzie przechowywa a
ł adres pierwszego elementu listy1 (wiersz 11). Pierwszy element listy jest
tworzony przy pomocy procedury „create”. Mo e
ż ona również służyć do wstawiania nowych elementów do listy, gdyż wywołuje procedurę
„insert_node”, realizującą tę operację. Ta ostatnia różni się od swojej odpowiedniczki dla listy jednokierunkowej, tym że w jej kodzie zawarte
są operacje zwi z
ą ane z manipulacją zawarto c
ś ią pola „prev” elementu i że nie potrzebuje dodatkowej zmiennej lokalnej, która pamiętałaby
wskaźnik na poprzedni element. Procedura ta ma dwa parametry. Przez pierwszy pobiera wskaźnik pierwszego elementu listy, natomiast
poprzez drugi pobiera wartość, którą należy umie c
ś ić w elemencie. Posiada ona również dwie lokalne zmienne wska n
ź ikowe. W wierszach (18
21) tworzony jest i inicjalizowany nowy element listy, z uwzględnieniem pola „prev”, któremu należy nadać wartość początkową „NIL”.
Jeśli warunek zawarty w wierszu 22, w instrukcji warunkowej jest prawdziwy, to oznacza to, e
ż nowy element należy umie c
ś ić na początku
listy. Wymaga to następujących operacji: zapamiętania
wskaźnika na element listy, który dotychczas był pierwszym
1 program double_linked_list;
... zobacz całą notatkę
Komentarze użytkowników (0)