Икки боғламли рўйхат

O’zbekiston Respyblikasi Axborot Texnologiylari va Kommunikatsiyalarini Rivojlantirish Vazirligi
Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Ma'lumotlar tuzulmasi va Algoritmlar

Mavzu; Ikki bog'lamli ro'yxat

Guruh;811-19

Bajardi;Omonov Kamoliddin


Икки боғламли рўйхат
Кўпгина масалаларни ҳал қилишда бир томонга йўналтирилган
рўйхатлардан фойдаланиш маълум бир қийинчиликларни келтириб чиқаради.
Сабаби, бир томонга йўналтирилган рўйхатда ҳар доим рўйхатда бош
бўғимдан рўйхатнинг сўнги бўғими томонига харакатланиш мумкин холос.
Лекин кўпгина масалалар ҳал қилинаѐтганда маълум бир элементни қайта
ишлаш учун ундан олдин келган элементга мурожаат қилиш зарурати пайдо
бўлади. Ушбу ҳолатда берилган элементдан олдин келган элементга
мурожаат қилиш бир боғламли рўйхатда ноқулай ва анча секин амалга
оширилади хамда уни амалга ошириш алгоритми мураккаблашади.
Ушбу ноқулайликларни йўқотиш мақсадида рўйхатнинг ҳар бир бугимига яна битта майдон кушилади. Ушбу майдон киймати узидан олдин келган бўғимга мурожаатдан иборат бўлади. Ушбу кўринишдаги
элементлардан ташкил топган динамик тузилмага иккитомонлама
йўналтирилган ѐки икки боғламли рўйхат дейилади.
Икки боғламли рўйхатнинг ҳар бир элементи иккита кўрсаткичга эга.
Биттаси олдинги элементга кўрсатади (тескари), иккинчиси навбатдаги
элементни кўрсатади (тўғри) (чизма)

Умуман олганда, икки боғламли рўйхат бу элементлари сони бир ҳил

фақатгина тескари кетма-кетликда ѐзилган иккита бир боғламли рўйхатдир


Ҳалқасимон икки боғламли рўйхат
Дастурлашда иккибоғламли рўйхатларни кўпинча қуйидагича
умумлаштирилади: сўнги бўғин майдони қиймати Rptr сифатида бош бўғинга
мурожат олинади, Lptr майдони қиймати сифатида сўнги бўғинга мурожаат қаралади

Икки бўғимли рўйхат устидаги амаллар:

- рўйхат элементини яратиш;
- рўйхатда элементни қидириш;
- рўйхатнинг кўрсатилган жойига элементни қўйиш;
- берилган элементни рўйхатдан ўчириш.

Фараз қилайлик рўйхатни текшириб, унда информацион майдони 4 га

тенг бўлган элементларини ўчириш талаб қилинган бўлсин.
Р орқали ишчи кўрсаткични белгилаб оламиз, процедура бошида P =
Lst. Шундай Q кўрсаткич киритамизки, у Р дан бир элемент орқада юрсин. Р
кўрсаткич керакли элементни топганда ушбу элемент Q га нисбатан
навбатдаги элемент сифатида ўчирилади.
Q = Nil
P = Lst
While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile