Ахборот т е хнол огиялари

Хотирада маълумотларни кетма-кет ва боғлиқ тақдим этиш
Компьютерларнинг хотирасида маълумотлар сақлаш даражасида кетма-кет ѐки ўзаро боғлиқ ҳолда жойлашиши мумкин Демак, маълумотларни сақлашнинг уларни тегишлича кетма-кет ва боғлиқ ҳолда тақдим этишдан фойдаланадиган сақлаш тузилмалари фарқланади.
Кетма-кет тақдим этишда маълумотлар машина хотирасида кетма-кет
жойлашган қўшни уяларда жойлаштирилади. Бунда ѐзувлар жойлашувининг
жисмоний тартиби мантиқий тузилма билан белгиланадиган мантиқий
тартибга тўла мос бўлади, яъни мантиқий тузилма маълумотлар жойлашувининг жисмоний тартиби билан қўллаб-қувватланади. Хотиранинг кетма-кет уяларида жойлаштирилган ѐзувларнинг мажмуи кетма-кет рўйхат деб аталади.
Ахборот массивини кетма-кет рўйхат шаклида сақлаш учун хотирада массивнинг энг катта ўлчамига мос бўш уялар блоки ажратилади. Қуйидаги: В ѐзув, А ѐзув, F ѐзув, С ѐзув, ..., N ѐзув мантиқий тартибига эга бўлган ѐзувлар машина хотирасида жойлаштирилади. Янгидан пайдо бўладиган ѐзувлар блокнинг охирида хотиранинг бўш участкасида жойлашади. Агар янги
102
ѐзувларнинг миқдори заҳира блокидаги бўш уялар сонидан кўп бўлса, бу ѐзувларни хотирада жойлаштириб бўлмайди. Агар ѐзувлар мўлжалланганидан кам бўлса, хотирада фойдаланилмаган уялар қолади.
Ахборот массивини юритиш жараѐнида ѐзувлар қўшилади ва чиқариб ташланади. Янги ѐзувлар рўйхатнинг охирига қўшилади. Масалан, (N + 1) -ѐзув 100 + (N + 1) манзилли уяда жойлаштирилади. Хотиранинг бўш уялари бўлган рўйхат зич бўлмайди. Вақт ўтиши билан анча уялар бўшаб қолиши мумкин. Хотиранинг бу участкалари бўшлигича қолмаслиги учун вақти-вақти билан бутун маълумотлар массиви қайта ѐзилади, бунда барча ѐзувлар 5.7,б-расмда кўрсатилганидек сурилади. Массивни қайта ѐзиш қўшимча машина вақтининг сарфланишини талаб этади. Массивни тузатиш жараѐнида янгиланиши зарур бўлган ѐзувлар хотирадан ўқилади ва уларга зарурий тузатишлар киритилади. Тузатилган ѐзувлар хотиранинг бўш уяларига рўйхат охирига ѐзилади.
Маълумотларнинг кетма-кет тақдим этилишидан одатда массивнинг чегаравий ўлчамини олдиндан айтиш мумкин бўлган ҳолларда чизиқий маълумотлар тузилмасини амалга ошириш учун фойдаланилади.
ААТ иловалари кўпинча узлуксиз равишда янгиланадиган, тузатиладиган маълумотлар билан ишлашига тўғри келади ва маълумотларнинг кетма-кет рўйхат шаклида тақдим этилиши хотирадан самарасиз фойдаланишга, машина вақтининг массивни қайта ѐзишга сарфланишига олиб келади. Бир қатор топшириқлар учун маълумотларнинг кетма-кет тақдим этилиши умуман мақсадга номувофиқ. Бундай ҳолларда маълумотлар тузилмасини ташкил этишда боғланишли тақдим этишдан фойдаланилади.
Маълумотларни боғланишли тақдим этишда ҳар бир ѐзувда қўшимча майдонча кўзда тутилади, унга кўрсаткич (ишорат) жойлаштирилади. Бу ҳолда ѐзувлар кетма-кетлигининг жисмоний тартиби мантиқий тартибга мос келмаслиги мумкин. Машина хотирасида ѐзувлар исталган бўш уяга жойлашади ва ўзаро кўрсаткичлар билан боғланади, улар мантиқан ушбу ѐзувдан кейин келадиган ѐзув жойлашган жойни кўрсатиб туради. Кўрсаткичга кўпинча кейинги ѐзув сақланадиган хотира уясининг манзили сифатида ҳам қараш мумкин.
Маълумотларни ўзаро боғланган ҳолда тақдим этишга асосланган сақлаш тузилмалари боғланган рўйхатлар деб ҳам аталади. Агар ҳар бир ѐзув битта кўрсаткичга эга бўлса, рўйхат бир боғланишли, кўрсаткичлар сони кўп бўлса, рўйхат кўп боғланишли бўлади.
Маълумотлар тузилмаси ѐзувларнинг қуйидаги мантиқий кетма-кетлигини акс эттиради, дейлик: А ѐзув, В ѐзув, С ѐзув, F ѐзув. Ёзувлар 01, 03, 05, 10 манзилли хотира уяларида жойлаштирилган. Ҳар бир ѐзувнинг кўрсаткич майдонида алоқа манзили (АМ) жойлашади ва у мантиқан шу ѐзувдан кейинги ѐзувнинг уяси манзилини белгилаб беради.
Маълумотларни боғланган ҳолда тақдим этиш маълумотлар билан турли операцияларни бажариш учун кенг имкониятлар очиб беради ва сақлаш тузилмаларининг катта мослашувчанлигини таъминлайди. Боғланган рўйхатни юритиш жараѐнида янги ѐзувларни қўшиш ва эскиларини ўчириш массив элементларини қайта ѐзишни талаб этмайди, балки тегишли кўрсаткичларни
103
ѐзувларнинг мантиқий тартибини бузмаган ҳолда ўзгартириш йўли билан амалга оширилади.
Бир боғланишли рўйхатни юритиш жараѐнида кўрсаткичларни
ўзгартириш процедурасини кўриб чиқамиз.
Ўчириш операциясини бажаришда ўчирилаѐтган ѐзув ўзининг барча майдонлари, шу жумладан кўрсаткич майдони билан билан бирга массивдан чиқарилади. Бунда кўрсаткичлар занжири узилади ва рўйхатнинг кейинги ѐзувларига кириш мумкин бўлмай қолади. Мантиқий жиҳатдан ўчирилаѐтган ѐзувдан кейин келадиган ѐзув кўрсаткичи «осилган» деб аталади, чунки у мавжуд бўлмаган ѐзувни кўрсатиб туради ва рўйхатнинг ѐзувлар занжири унда узилади. Ёзувлар эргашишининг мантиқий занжири ўзгармаслиги учун ѐзувни ўчиришдан олдин кўрсаткичларни алмаштириш керак. Бунда ўчирилаѐтган ѐзув кўрсаткичининг қиймати мантиқан ундан олдинги ѐзув кўрсаткичи майдонига киритилади.
Бир боғланишли рўйхатга янги ѐзув киритиш учун бўш уялар рўйхатидан биринчи уя олинади, унинг ахборот майдонига янги ѐзув жойлаштирилади, кўрсаткич майдонига эса мантиқий жиҳатдан ундан кейин келадиган ѐзув сақланадиган манзил киритилади. Янги ѐзувли уя манзили эса мантиқан ундан олдинги ѐзувнинг кўрсаткичи бўлиб қолади. Янги ѐзувларни жойлаштириш учун исталган бўш уядан фойдаланиш мумкинлиги учун рўйхатни чекланмаган тарзда кўпайтириб бориш мумкин ва бунинг учун олдиндан хотирани заҳиралаш талаб этилмайди.
Бир боғланишли рўйхатни ѐпиқ ҳалқа шаклида ташкил этиш мумкин. Бу ҳолда биринчи ѐзувнинг манзили охирги ѐзувнинг кўрсаткичи бўлади. Бундай рўйхат яна циклик рўйхат ҳам деб аталади. Циклик рўйхатни исталган уядан бошлаб кўриб чиқа бошлаш мумкин. Кўриб чиқилган ѐзувлар сони рўйхатдаги ѐзувлар умумий сонига ѐки кўрсаткичнинг биринчи ўқилган уя манзили билан тўғри келиши кўриб чиқишнинг тугаганлиги шартидир. Охирги ҳолатда биринчи ўқилган уя манзили эслаб қолиниши ва ҳар сафар навбатдаги ѐзувни ўқишда унинг кўрсаткичи Маълумотларни боғланган ҳолда тақдим этишдан маълумотларнинг ночизиқий тузилмаларини сақлаш учун, шунингдек ахборот массивининг энг чегаравий ўлчами олдиндан номаълум бўлган (демак, хотира ўлчамига талабларни ҳам олдиндан белгилаб бўлмайди); ахборот массиви тез-тез ўзгартириб туриладиган, маълумотлар устида кўп сонли қўшиш ва ўчириш операциялари бажариладиган ҳолларда чизиқий тузилмаларни амалга ошириш учун фойдаланилади. ЭҲМ хотирасида маълумотларни қандай тақдим этишни танлаш масаласини ҳал қилишда маълумотларни боғланган тарзда тақдим этиш кўрсаткичлар учун машина хотирасининг қўшимча сарфланишига олиб келишини ѐдда тутиш зарур.
Бир қатор вазифаларни бажаришда боғланган рўйхат бўйича ҳар икки йўналишда ҳаракат қилиш имкониятига эга бўлиш зарур. Бунинг учун рўйхатнинг ҳар бир элементига қўшимча кўрсаткич киритилади, у рўйхат бўйича тескари йўналишда ҳаракат қилишни белгилайди. Бундай рўйхат икки йўналишли деб аталади. Кўрсаткич майдонига мантиқан ушбу ѐзувдан олдин келадиган ѐзувли уя манзили киритилади. Бош уя бу ҳолда
104
рўйхатнинг биринчи ва охирги уяси кўрсаткичларига эга бўлади. Икки йўналишли рўйхатда излаш ишларини рўйхатнинг ҳам бошидан, ҳам охиридан бошлаш мумкин. Ёзувларни қўшиш (ўчириш) жараѐнида икки боғланишли рўйхатда, тўғри ва тескари кўрсаткичларнинг ўзгариши юз беради. Тескари кўрсаткичнинг мавжудлиги кўрсаткичларни ўзгартириш алгоритмини соддалаштириш имконини беради, чунки ўчирилаѐтган ѐзувнинг тескари кўрсаткичи мантиқан бу ѐзувдан олдинги ѐзув уясининг манзилини сақлаб қолади.
Битта боғланишли рўйхатда бу манзилни қўшимча процедуралар ѐрдамида аниқлаш зарур. Икки йўналишли рўйхатдан фойдаланишда ахборот массивларини излаш ва юритиш жараѐнлари тезлашади, лекин кўрсаткичлар учун хотира сарфи ошади.
Маълумотларни боғлиқ ҳолда тақдим этишни амалга ошириш учун дастурлаштириш тили муайян воситаларга, хусусан «кўрсаткич» типидаги маълумотларга эга бўлиши керак. «Кўрсаткич» типидаги маълумотларга эга бўлмаган дастурлаштириш тиллари билан ишлашда маълумотларни боғлиқ ҳолда тақдим этиш массив тузилмаси ѐрдамида моделлаштирилади.
Маълумотлар тузилмаси М (I) массив cифатида белгиланган бўлсин. Ёзувлар жойлашишининг жисмоний тартибига мос келмайдиган массив элементларини ўқиш тартибини белгилаш учун кўрсаткичларнинг ѐрдамчи векторини N(J) ташкил этиш мумкин, унинг элементлари – яхлит сонлар – асосий массив ѐзувларининг тартиб номерини (индексини) белгилаб беради.