PP2 Wykład 5

Nasza ocena:

3
Wyświetleń: 1260
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
PP2 Wykład 5 - strona 1

Fragment notatki:

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)

Zaloguj się, aby dodać komentarz