ALG7
5.2. Tablicowa implementacja list 127
5.2.3.Listy innych typów
Listy jednokierunkowe są bardzo wygodne w stosowaniu i zajmują stosunkowo mało pamięci. Tym niemniej operacje na nich niekiedy zajmują dużo czasu. Zauważyło ten fakt sporo ludzi i tym sposobem zostały wymyślone inne typy list, np.:
lista dwukierunkowa - komórka robocza zawiera wskaźniki do elementów: poprzedniego i następnego:
Rys. S -13. Lista dwukierunkowa.
• pierwsza komórka znajdująca się w liście nie posiada swojego poprzednika; zaznaczamy to wpisując wartość NULL do pola poprzedni;
• ostatnia komórka znajdująca się w liście nie posiada swojego następnika; zaznaczamy to wpisując wartość NULL do pola następny. Lista dwukierunkowa jest dość „kosztowna”, jeśli chodzi o zajętość pamięci, tym niemniej czasami ważniejsza jest szybkość działania od ewentualnych strat pamięci.
Struktura wewnętrzna listy dwukierunkowej jest oczywista:
typedef struct rob
{
Iint wartość;
struct rob 'następny; struct rob 'poprzedni;
(ELEMENT;
Załóżmy teraz, że podczas przeglądania elementów listy zapamiętaliśmy wskaźnik pozycji bieżącej p. (Przykładowo szukaliśmy elementu spełniającego pewien warunek i na wskaźniku p nasze poszukiwania zakończyły się sukcesem).
I Jak usunąć elementp z listy'? Jak pamiętamy z paragrafów poprzednich, do pra
widłowego wykonania tej operacji niezbędna była znajomość wskaźników przed i po, wskazujących odpowiednio na komórki poprzednią i następną. W przypadku listy dwukierunkowej w' komórce wskazywanej przez p tc dwie informacje już się znajdują i wystarczy tylko po nie sięgnąć:
void usunżkier(ELEMENT *p)
(
if(p->poprzedni!-NULL) II nie jest to element pierwszy
p->poprzećni->nastepny=p->nastepny; if(p->nastcpny!-NULL) II nic jest to element ostatni
p->nastepr.y->poprzedni=p->poprzedni;
)
Wyszukiwarka
Podobne podstrony:
ALG3 5.2. Tablicowa implementacja list 123 tego konieczne będzie wybranie jakiejś zmiennej do zapam
ALG5 5.2. Tablicowa implementacja lisi 125 5-11, gdzie można zobaczyć przykładową implementację lis
ALG 4 94 Rozdział 5. Struktury danych5.1. Listy jednokierunkowe Lista jednokierunkowa jest oszczędną
ALG8 108__Rozdział 5. Struktury danych5.1.3.Listy jednokierunkowe - teoria i rzeczywistość Oprócz p
ALG 7 5.1. Listy jednokierunkowe 97 public: int pusta() // czy lista jest pusta? {
ALG7 5.1. Listy jednokierunkowe 107 cout « "L2 = for (i=0; i<n; 12.dorzuc2(tab2[i++])) ; 12
ALG7 5.1. Listy jednokierunkowe 117 Mając już komplet funkcji pusta, zestaw funkcji decyzyjnych i u
str7 Tablica IKlotoida jednostkowa l a-i. r T. , « h X y i,68o 2,822 400 89,83 98 80 51
page0219 TABLICA XXVI. Takiż podług listy
12582 str 7 Tablica i ,93° 3,93 0,932 0,933 o,934 0,864 900 1 861 ,866 761 1 863 ,86
17 Tablica 13 Orientacyjne ceny nici; to ryci? gatunków stali — ii a podstawie cennika .nr 32-Z/70
Programowanie równoległeMinimalny element tablicy // Plik: elminimalny.alg // Dane: Tablica n elemen
Programowanie równoległeSuma elementów tablicy; n procesorów // Plik: suma.alg // Dane: Tablica licz
Programowanie równoległeSuma elementów tablicy; p procesorów // Plik: suma-p.alg // Dane: Tablica li
60832 str7 Tablica IKlotoida jednostkowa l 2=1 r T° * " h X , : 1,230 x ,512 900 48,15 71
lab7 Tablica V. Kwantyle rozkładu £2 ?(%2 (t)< wartość tablicowa)= p 239
28806 str7 Tablica IKlotoida jednostkowa l 1 T 0 r° * " h f* ==“ r X y o,i8c 0,032 40C 1,°3
więcej podobnych podstron