Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
28
1.Podstawowezasadyanalizyalgorytmów
Rys.1.1.Różnewariantyimplementacjidowiązaniowejlist
Następująceoperacjenalistachmająstałązłożonośćczasową:
•wimplementacjipojedynczejliniowej:operacjestosu,wstawianiejednegoelementuza
drugi,usuwanienastępnegoelementu;
•wimplementacjipojedynczejcyklicznej:teoperacjecowyżejpluszłożenieorazope-
racjereariinject;
•wimplementacjipodwójnejcyklicznej:teoperacjecowyżejpluseject,wstawianie
jednegoelementuprzeddrugim,usuwaniedanegoelementu,odwracanielisty.
Każdazatemoperacjadotyczącakolejkipodwójnejmapesymistycznązłożonośćczasową
O(1)wimplementacjipodwójnejcyklicznej.WadątejimplementacjijestużycieO(n)komó-
rekpomocniczejpamięcinapamiętaniedowiązań(njestrozmiaremlisty).
Jeślijestznanamaksymalnadługośćmkolejkipodwójnej,tobardziejoszczędnapamię-
ciowojestimplementacjalistyzapomocątablicycyklicznejQ[0..m-1],wktórejnastęp-
nikiempozycji0≤i≤m-1jestpozycja(i+1)modm.Wówczasjeśliq=[x
1,x
2,...,x
n],to
Q[(k+i)modm]=x
idla1≤i≤nipewnejpozycji0≤k≤m-1.Przykładowooperacja
pop(q)maimplementację:
pop(k,n)::ifn=0
thenerror
3)
else
begin
k:=(k+1)modm;
n:=n-1
end;
3)Instrukcjaerroroznaczaprzerwanieobliczeń.
