“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

Алгоритм 
Топилган элементни рўйхат бошига қўйиш орқали қайта тартиблаш
Топилган элемент бирданига рўйхат бошига жойлаштирилади.
Бошида q кўрсаткчи бўш, p эса рўйхат бошини кўрсатади; p иккинчи элементни кўрсатганда, q 
биринчини кўрсатади. Рўйхат боши кўрсаткичи (table) иккинчи элементга жойлаштирилганда, иккинчи элемент 
кўрсаткичи эса учинчига. Шундай қилиб, иккинчи элемент биринчи ўринга жойлаштирилади.
алгоритм 
q:=nil; 
p:=table; 
while (p <> nil) do 
begin 
if key = p^.k then 
begin 
if q = nil 
then 'ўринлаштириш шарт эмас' 
search := p; 
exit; 
end; 
q^.nxt := p^.nxt; 
p^.nxt := table; 
table := p; 

---

32
exit; 
end; 
q := p; 
p := p^.nxt; 
end; 
search := nil; 
exit; 
Транспозиция усули 
Ушбу усулда топилган элемент рўхатда битта олдинги элемент билан ўрин алмаштирилади. Агарда 
мазкур элементга кўп мурожаат қилинса, биттадан олдинга сурилиб бориб натижада рўйхат бошида бўлади.
Ушбу усулнинг қулайлиги у нафақат рўйхатда, балки тартибланмаган массивда хам самарали ишлайди 
(сабаби фақатгина иккита ёнма-ён турган элемент ўрин алмаштирилади).
Бу усулда учта кўрсаткичдан фойдаланамиз:
р – ишчи кўрсаткич 
q – ёрдамчи кўрсаткич, р дан битта қадам орқада бўлади 
s - ёрдамчи кўрсаткич, q дан иккита қадам орқада бўлади
Биз томонимиздан топилган учинчи элемент рўйхат бошига бир қадам сурилади (яъни иккинчи бўлиб 
қолади). Биринчи элемент кўрсаткичи учинчи элементга жойлаштирилади, иккинчи элемент кўрсаткичи 
тўртинчи, шундай қилиб учинчи элемент иккинчи жойга жойлашиб қолади. Агар мазкур элементга яна бир бор 
мурожаат қилинса, у ҳолда у рўйхат бошида бўлиб қолади. 
алгоритм 
s:=nil; 
q:=nil; 
p:=table; 
while (p <> nil) do 
begin 
if key = p^.k then 
‘транспонерлаймиз 
begin
if q = nil then 
begin 
‘ўринлаштириш шарт эмас
search:=p; 
exit; 
end; 
q^.nxt:=p^.nxt; 
p^.nxt:=q; 
if s = nil then 
table := p; 
else
begin 
s^.nxt := p; 
end; 
search:=p; 
exit; 
end;
end; 
search:=nil;
exit; 
Ушбу усул нафақат рўйхатда, балки массивда хам қулай (сабаби фақатгина иккита ёнма-ён турган 
элемент ўрин алмаштирилади). 

---

33