Илгари ААТ ларнинг ишлаш жараёнида ёзувлар ва массивлар
ўзгаради, деб айтиларди. Бунда массивларга янги ёзувлар қўшилади ва керак бўлмай
қолган ёзувлар ўчирилади. Шу муносабат билан массивларда амалга ошириладиган
операциялар ва массивларни ташкил этадиган айрим ёзувларнинг ичидаги маълумотлар
устида бажариладиган операциялар фарқланади.
Ёзувларни
қўшиш (киритиш) ва ўчириш (чиқариб ташлаш) дан иборат бўлган ахборот массивини
долзарб ҳолатда сақлаб туриш жараёни юритиш деб аталади.
Объектларнинг
айрим тавсифлари вақт ўтиши билан ўзгариши мумкин, шунинг учун ёзувларга тегишли
ўзгартиришларни киритиш зарур. Ёзувларга ўзгартиришларни киритиш жараёни
тузатиш ёки
модификация деб
аталади.
ААТ да амалга ошириладиган ҳар қандай операциянинг охирги
мақсади ёзув ҳисобланади. Муайян ёзувга янги ёзувларни қўшиш, эскиларини ўчириш
ёки тузатиш, ундаги ахборотга ишлов бериш учун энг аввало керакли ёзувни ёки
унинг массивдаги жойини топиш зарур. Шунинг учун излаш операциялари ахборотни
сақлаш ва ишлов бериш тизимлари учун анъанавий бўлиб, ААТ да энг кўп
бажариладиган операциялар деб ҳисоблаш мумкин. Ёзувни излаш имкон қадар тез
амалга оширилиши зарур, чунки излаш вақти маълум даражада ахборотга ишлов
беришнинг умумий вақтини белгилайди. Равшанки, ААТ нинг бу хусусиятлари сақлаш
даражаси қандай ташкил этилганлиги ва массивлар ҳамда файлларда ёзувларни излаш
учун қандай қоидалар, алгоритмлар қабул қилинганлигига боғлиқ бўлади.
Ахборот
массивининг «ҳаётийлигини» таъминлаш учун маълумотларни ташкил этувчи тузилмалар
массивни юритиш ва айрим ёзувларни тузатиш, ёзувларни тезкор излаш имконини
бериши, массивлар учун хотиранинг кам сарфланишини таъминлаши керак. Юқорида
санаб ўтилган талаблар қарама-қарши талаблардир, чунки ААТ нинг битта тавсифини
яхшилашга олиб келадиган талабларни кучайтириш унинг бошқа тавсифлари
ёмонлашишига олиб келиши мумкин. Маълумотларнинг тузилмаларини танлашда,
кўпинча, бу масаланинг ҳар томонини ҳисобга оладиган ечимларга
тўхталинади.
Маълумотлар
тузилиши чизиқли ва ночизиқли
тузилмаларга бўлинади. Ночизиқли тузилмаларда чизиқлилардан фарқли ўлароқ
тузилма элементлари (ёзувлар) ўртасидаги алоқа бўйсуниш муносабатлари ёки
қандайдир мантиқий шартлар билан белгиланади.
Маълумотларнинг чизиқли тузилмаларига массив,
стек, навбат, жадвал киради. Ночизиқли тузилмаларга дарахтлар, графлар, кўп
боғланишли рўйхатлар ва рўйхатли тузилмалар киради.
Маълумотларнинг
бир қатор тузилмалари ёзувга бошқа ёзувни қўшиш ёки ўчириш имконини бермайди,
фақат ёзувни тузатишга йўл қўяди. Бу ўлчами қайд
этилган тузилмалардир. Ўлчами
ўзгарувчан тузилмалар
ёзувларга янги ёзувларни киритиш, ўчириш имконини беради ва бу билан
ахборот массивининг динамик равишда ўзгаришига имкон беради. Компьютер
хотирасида тузилмаларнинг қандай усулда (кетма-кет ёки боғлиқ) берилишига боғлиқ
ҳолда ўлчами ўзгарувчан тузилмаларга ёки олдиндан заҳира сифатида сақлаб
турилган хотира блокида, ёки бутунлай бўш бўлган манзил маконида ўсиш ва камайиш
имконияти берилади. Биринчи ҳолда
тузилма элементлари сонини олдиндан билиш ва ахборот массивининг энг катта
ўлчами учун хотира блокини ажратиш зарур.
Агар тузилма элементларининг сони мўлжалдагидан кўп бўлса, ортиқча элементларни
хотирада жойлаштириб бўлмайди. Агар элементлар камроқ бўлса, хотира участкасидан
фойдаланилмай қолади.
Маълумотлар боғлиқ ҳолда берилганда ўзгарувчан ўлчамли тузилмалар бемалол ўсиши
ва камайиши мумкин.
Тузилма элементлари сони илгаридан маълум бўлмаслиги мумкин.
киришнинг
чекланиши керакли ёзувларни излаб топиш вақти ошишига олиб келади.
Маълумотлар тузилиши бир ва бир неча турда бўлиши мумкин.
Бир
турдаги тузилмаларда барча элементлар бир турдаги ёзувлардан иборат
бўлади. Бир турда
бўлмаган тузилмаларда турли типдаги ёзувлар битта тузилманинг элементлари
бўлиши мумкин.
Компьютерларнинг
хотирасида
маълумотлар сақлаш даражасида
кетма-кет ёки ўзаро боғлиқ ҳолда жойлашиши мумкин
Демак, маълумотларни сақлашнинг
уларни тегишлича кетма-кет ва боғлиқ ҳолда тақдим этишдан фойдаланадиган сақлаш
тузилмалари фарқланади.
Кетма-кет
тақдим этишда маълумотлар машина хотирасида кетма-кет жойлашган қўшни уяларда
жойлаштирилади. Бунда ёзувлар жойлашувининг жисмоний тартиби мантиқий тузилма билан белгиланадиган
мантиқий тартибга тўла мос бўлади, яъни мантиқий тузилма маълумотлар
жойлашувининг жисмоний тартиби билан қўллаб-қувватланади. Хотиранинг
кетма-кет уяларида жойлаштирилган ёзувларнинг мажмуи кетма-кет рўйхат деб аталади.
Ахборот массивини кетма-кет рўйхат шаклида сақлаш учун
хотирада массивнинг энг катта ўлчамига мос бўш уялар блоки ажратилади. Қуйидаги:
В ёзув, А ёзув, F ёзув, С ёзув, ..., N ёзув мантиқий тартибига эга
бўлган ёзувлар машина хотирасида
жойлаштирилади. Янгидан
пайдо бўладиган ёзувлар блокнинг охирида хотиранинг бўш участкасида жойлашади.
Агар янги ёзувларнинг миқдори заҳира блокидаги бўш уялар сонидан кўп бўлса, бу
ёзувларни хотирада жойлаштириб бўлмайди. Агар ёзувлар мўлжалланганидан кам
бўлса, хотирада фойдаланилмаган уялар қолади.
Ахборот
массивини юритиш жараёнида ёзувлар қўшилади ва чиқариб ташланади. Янги ёзувлар
рўйхатнинг охирига қўшилади. Масалан, (N
+ 1) -ёзув 100 + (N + 1) манзилли уяда жойлаштирилади. Хотиранинг
бўш уялари бўлган рўйхат зич бўлмайди. Вақт ўтиши билан анча уялар бўшаб қолиши мумкин.
Хотиранинг бу участкалари бўшлигича қолмаслиги учун вақти-вақти билан бутун
маълумотлар массиви қайта ёзилади, бунда барча ёзувлар 5.7,б-расмда
кўрсатилганидек сурилади. Массивни қайта ёзиш қўшимча машина вақтининг
сарфланишини талаб этади. Массивни тузатиш жараёнида янгиланиши зарур бўлган
ёзувлар хотирадан ўқилади ва уларга зарурий тузатишлар киритилади. Тузатилган
ёзувлар хотиранинг бўш уяларига рўйхат охирига ёзилади.
Маълумотларнинг
кетма-кет тақдим этилишидан одатда массивнинг чегаравий ўлчамини олдиндан айтиш
мумкин бўлган ҳолларда чизиқий маълумотлар тузилмасини амалга ошириш учун
фойдаланилади.
ААТ
иловалари кўпинча узлуксиз равишда янгиланадиган, тузатиладиган маълумотлар
билан ишлашига тўғри келади ва маълумотларнинг кетма-кет рўйхат шаклида тақдим
этилиши хотирадан самарасиз фойдаланишга, машина вақтининг массивни қайта ёзишга
сарфланишига олиб келади. Бир қатор топшириқлар учун маълумотларнинг кетма-кет
тақдим этилиши умуман мақсадга номувофиқ. Бундай ҳолларда маълумотлар
тузилмасини ташкил этишда боғланишли тақдим этишдан фойдаланилади.
Маълумотларни
боғланишли тақдим этишда ҳар бир ёзувда қўшимча майдонча кўзда тутилади, унга
кўрсаткич
(ишорат) жойлаштирилади.
Бу ҳолда ёзувлар кетма-кетлигининг жисмоний тартиби мантиқий тартибга мос
келмаслиги мумкин. Машина хотирасида ёзувлар исталган бўш уяга жойлашади ва
ўзаро кўрсаткичлар билан боғланади, улар мантиқан ушбу ёзувдан кейин келадиган
ёзув жойлашган жойни кўрсатиб туради. Кўрсаткичга кўпинча кейинги ёзув
сақланадиган хотира уясининг манзили сифатида ҳам қараш мумкин.
Маълумотларни
ўзаро боғланган ҳолда тақдим этишга асосланган сақлаш тузилмалари боғланган
рўйхатлар деб ҳам аталади. Агар ҳар бир ёзув битта кўрсаткичга эга бўлса, рўйхат
бир
боғланишли, кўрсаткичлар сони кўп бўлса, рўйхат кўп
боғланишли бўлади.
Маълумотлар
тузилмаси ёзувларнинг қуйидаги мантиқий кетма-кетлигини акс эттиради,
дейлик:
А ёзув, В ёзув, С ёзув, F ёзув.
Ёзувлар 01, 03, 05, 10 манзилли хотира уяларида жойлаштирилган. Ҳар бир ёзувнинг
кўрсаткич майдонида алоқа манзили (АМ) жойлашади ва у мантиқан шу ёзувдан
кейинги ёзувнинг уяси манзилини белгилаб беради.
Маълумотларни
боғланган ҳолда тақдим этиш маълумотлар билан турли операцияларни бажариш учун
кенг имкониятлар очиб беради ва сақлаш тузилмаларининг катта мослашувчанлигини
таъминлайди. Боғланган рўйхатни
юритиш жараёнида янги ёзувларни қўшиш ва эскиларини ўчириш массив элементларини
қайта ёзишни талаб этмайди, балки тегишли кўрсаткичларни ёзувларнинг мантиқий
тартибини бузмаган ҳолда ўзгартириш йўли билан амалга оширилади.
Бир
боғланишли рўйхатни юритиш жараёнида
кўрсаткичларни ўзгартириш процедурасини кўриб чиқамиз.
Ўчириш
операциясини бажаришда ўчирилаётган ёзув ўзининг барча майдонлари, шу жумладан
кўрсаткич майдони билан билан бирга массивдан чиқарилади. Бунда кўрсаткичлар
занжири узилади ва рўйхатнинг кейинги ёзувларига кириш мумкин бўлмай
қолади.
Мантиқий жиҳатдан ўчирилаётган ёзувдан кейин келадиган ёзув кўрсаткичи «осилган»
деб аталади, чунки у мавжуд бўлмаган ёзувни кўрсатиб туради ва рўйхатнинг
ёзувлар занжири унда узилади. Ёзувлар эргашишининг мантиқий занжири ўзгармаслиги
учун ёзувни ўчиришдан олдин кўрсаткичларни алмаштириш керак. Бунда ўчирилаётган
ёзув кўрсаткичининг қиймати мантиқан ундан олдинги ёзув кўрсаткичи майдонига
киритилади.
Бир
боғланишли рўйхатга янги ёзув киритиш учун бўш уялар рўйхатидан биринчи уя
олинади, унинг ахборот майдонига янги ёзув жойлаштирилади, кўрсаткич майдонига
эса мантиқий жиҳатдан ундан кейин келадиган ёзув сақланадиган манзил киритилади.
Янги ёзувли уя манзили эса мантиқан ундан олдинги ёзувнинг кўрсаткичи бўлиб
қолади. Янги ёзувларни жойлаштириш учун исталган бўш уядан фойдаланиш мумкинлиги
учун рўйхатни чекланмаган тарзда кўпайтириб бориш мумкин ва бунинг учун олдиндан
хотирани заҳиралаш талаб этилмайди.
Бир
боғланишли рўйхатни ёпиқ ҳалқа шаклида ташкил этиш мумкин. Бу
ҳолда биринчи ёзувнинг манзили охирги ёзувнинг кўрсаткичи бўлади. Бундай рўйхат
яна циклик рўйхат ҳам деб
аталади. Циклик рўйхатни исталган уядан бошлаб кўриб чиқа бошлаш мумкин. Кўриб
чиқилган ёзувлар сони рўйхатдаги ёзувлар умумий сонига ёки кўрсаткичнинг биринчи
ўқилган уя манзили билан тўғри келиши кўриб чиқишнинг тугаганлиги шартидир.
Охирги ҳолатда биринчи ўқилган уя манзили эслаб қолиниши ва ҳар сафар навбатдаги
ёзувни ўқишда унинг кўрсаткичи Маълумотларни боғланган ҳолда тақдим этишдан
маълумотларнинг ночизиқий тузилмаларини сақлаш учун, шунингдек ахборот
массивининг энг чегаравий ўлчами олдиндан номаълум бўлган (демак, хотира
ўлчамига талабларни ҳам олдиндан белгилаб бўлмайди); ахборот массиви тез-тез
ўзгартириб туриладиган, маълумотлар устида кўп сонли қўшиш ва ўчириш
операциялари бажариладиган ҳолларда
чизиқий тузилмаларни амалга ошириш учун фойдаланилади. ЭҲМ хотирасида
маълумотларни қандай тақдим этишни танлаш масаласини ҳал қилишда маълумотларни
боғланган тарзда тақдим этиш кўрсаткичлар учун машина хотирасининг қўшимча
сарфланишига олиб келишини ёдда тутиш зарур.
Бир
қатор вазифаларни бажаришда боғланган рўйхат бўйича ҳар икки йўналишда ҳаракат
қилиш имкониятига эга бўлиш зарур. Бунинг учун рўйхатнинг ҳар бир элементига
қўшимча кўрсаткич киритилади, у рўйхат бўйича тескари йўналишда ҳаракат қилишни
белгилайди. Бундай рўйхат икки
йўналишли деб аталади. Кўрсаткич майдонига мантиқан ушбу ёзувдан олдин
келадиган ёзувли уя манзили киритилади. Бош уя бу ҳолда рўйхатнинг биринчи ва
охирги уяси кўрсаткичларига эга бўлади. Икки йўналишли рўйхатда излаш ишларини
рўйхатнинг ҳам бошидан, ҳам охиридан бошлаш мумкин.
Ёзувларни қўшиш (ўчириш) жараёнида икки боғланишли рўйхатда, тўғри ва тескари
кўрсаткичларнинг ўзгариши юз беради.
Тескари кўрсаткичнинг мавжудлиги кўрсаткичларни ўзгартириш алгоритмини
соддалаштириш имконини беради, чунки ўчирилаётган ёзувнинг тескари кўрсаткичи
мантиқан бу ёзувдан олдинги ёзув уясининг манзилини сақлаб қолади.
Битта боғланишли рўйхатда бу манзилни
қўшимча процедуралар ёрдамида аниқлаш зарур.
Икки йўналишли рўйхатдан фойдаланишда ахборот массивларини излаш ва юритиш
жараёнлари тезлашади, лекин кўрсаткичлар учун хотира сарфи ошади.
Маълумотларни боғлиқ ҳолда тақдим этишни амалга ошириш
учун дастурлаштириш тили муайян воситаларга, хусусан «кўрсаткич» типидаги
маълумотларга эга бўлиши керак. «Кўрсаткич» типидаги маълумотларга эга бўлмаган
дастурлаштириш тиллари билан ишлашда маълумотларни боғлиқ ҳолда тақдим этиш
массив тузилмаси ёрдамида моделлаштирилади.
Маълумотлар
тузилмаси М (I) массив cифатида белгиланган бўлсин. Ёзувлар жойлашишининг
жисмоний тартибига мос келмайдиган массив элементларини ўқиш тартибини белгилаш
учун кўрсаткичларнинг ёрдамчи векторини N(J)
ташкил этиш мумкин, унинг элементлари – яхлит сонлар – асосий массив
ёзувларининг тартиб номерини (индексини) белгилаб беради.
Элементар
маълумотлар (сонлар, символлар, мантиқий маълумотлар, кўрсаткичлар)
машина ичида маълум тарзда жойлашади ва ЭҲМ хотирасининг муайян бирликларини
эгаллайди. Бу ахборот массивларини жойлаштириш учун зарур хотира ҳажмини
ҳисоблаб чиқиш имконини беради.
Сонли
маълумотлар барча дастурлаштириш тилларида бор. Уларга яхлит, моддий ва комплекс
сонлар киради.
Яхлит
сонлар иккилик ва ўнлик шаклларида берилиши мумкин. Яхлит сонларни иккилик
шаклларида сақлашда битта сон учун битта машина сўзи ажратилади. Четки ўнг бит
белги учун ажратилади. Мусбат 0 билан, манфий – 1 билан кодланади. Сонлар учун жойлар ўнгдан чапга қараб
ажратилади, сонлар билан эгалланмай
қолган жойлар ноллар билан тўлдирилади. Манфий сонлар одатда қўшимча код билан берилади.
Сонларни
ўнлик шаклида сақлашда соннинг ҳар бир ўнлик рақами тўрт разрядли иккилик коди
билан кодланади, яъни байтда иккитадан ўнлик рақамлар эслаб
қолинади.
Сонларни сақлашнинг бундай шакли жойланган ўнлик шакл деб аталади. Белги учун
четки ўнг ярим байт ажратилади,
мусбат 1100, манфий –1101 кодига эга бўлади. Масалан, жойланган ўнлик
шаклида тақдим этилган +9613 сони қуйидаги кўринишда ёзилади:
1001 0110 0001 0011 1100.
Моддий сонлар қайдланган ва сузувчи вергулли шаклда тақдим этилиши мумкин.
Қайдланган
вергул (нуқта) ли моддий сонлар яхлит сонлар каби сақланади. Сақлаш тузилмасида
нуқтанинг ҳолати акс эттирилмайди, у транслятор билан қайд этилади.
Катта
разрядлиликка эга сонлар одатда сузувчи нуқтали шаклда тақдим этилади. Улар икки
қисм: мантисса ва тартибдан иборат бўлади.
Ҳар икки қисмни сақлаш учун одатда машина сўзи, баъзи компьютерларда қўш сўз
ажратилади. Тартиб қуйидагича
сақланади – катта чап байтда, бу байтнинг чап битидан мантисса белигсини сақлаш
учун фойдаланилади.
Сон мантиссаси иккилик, саккизлик ёки ўн олтилик шаклида тақдим этилиши
мумкин.
Кўп компьютерлар сузувчи нуқтали сонларни иккиланган аниқлик билан бериш
имкониятига эга.
Улар учун ажратиладиган хотира ҳажми икки марта кўпайтирилади.
Символли маълумотларга лотин ва кирилл алифбосининг ҳарфлари, бош ва кичик
ҳарфлар, рақамлар, операция белгилари ва махсус символлар, бошқарувчи символлар
киради. Лотин ва рус ҳарфлари, рақамлар, операция белгилари ва махсус
символлардан маълумотларга ишлов бериш вазифаларини бажариш, матнни
шакллантириш, дастурларни ёзиш учун фойдаланилади.
Бошқарув
символларидан маълумотларни структуралаш, ахборотларни узатиш, файлларни тузиш
учун фойдаланилади.
Турли
компьютерлар символларнинг турли тўпламлари билан ишлайди ва турли символ
кодларидан фойдаланади. Одатда,
символлар уч разрядли саккизлик код АSСII
билан кодланади. Хотирада сақлаш учун ҳар бир символнинг саккизлик коди иккилик
кодга ўзгартирилади ва унга бир байт ажратилади. Байтнинг четки чап битидан
назорат разрядини сақлаш учун фойдаланилади.
Мантиқий
маълумотлар фақат иккита қиймат: «ҳа» ва «йўқ» ни қабул қилади. Мантиқий
маълумотлар билан Бул алгебрасининг турли операциялари амалга
оширилади:
ОR, АND, N0T - инверсия ва бошқалар.
Мантиқий
катталикларнинг машина хотирасида тақдим этилиши дастурга ишлов берувчи
транслятор ва компьютер турига боғлиқ. Мантиқий маълумотларни сақлаш учун агар
улар «ҳақиқат» бўлса қиймати
Мантиқий
катталикни ифодалан учун 1 байт дан фойдаланиш мумкин.
«Ҳақиқат» қиймати четки ўнг разрядда ноллар ва битта бирдан иборат бўлган
битларнинг кетма-кетлиги билан кодланади. «Ёлғон» қиймати ноллардан иборат
бўлган битларнинг кетма-кетлиги билан кодланади. Бундай тақдим этиш анча
самарали, чунки у тезкор эркин
фойдаланишни таъминлайди ва машина хотирасидан тежаб фойдаланади.
Сонсиз
операцияларни амалга оширувчи дастурларда маълумотларнинг анча фойдали тури
айрим символлар эмас, балки айрим символлардан конкатенация (уланиш) операцияси
билан ҳосил қилинадиган символлар қатори ҳисобланади.
Қаторлар устида конкатенация, кичик қаторни излаб топиш ва алмаштириш,
қаторларнинг ўхшашлигини текшириш, қатор узунлигини белгилаш каби муайян
операцияларни амалга ошириш мумкин.
Қаторни
ҳосил қилувчи символлар хотиранинг кетма-кет жойлашган байтларида эслаб
қолинади.
Символларни АSСII га кодлашда ҳар
бир символ учун 1 байт ажратилади, шунинг учун машина сўзида символларнинг бутун
сони жойлашади. Узунлиги қайдланган қаторни жойлаштириш учун талаб этиладиган
хотира ҳажми дастурда эълон қилинганга мувофиқ транслятор билан заҳира сифатида
сақлаб қўйилади.
Энг катта ўлчами дастурда кўрсатилган узунлиги ўзгарувчан қаторлар учун
қаторнинг энг катта узунлиги бўйича хотира ажратилади.
Битлар
қатори «0» ва «1» символларидан иборат бўлган символлар қаторининг алоҳида тури
ҳисобланади. Бит қаторларини хотирада сақлаб қолиш учун ҳар бир элементга битта
иккилик разряд ажратилади. Машина сўзида,
масалан, узунлиги 32 битдан иборат бўлган бит қатори жойлашиши мумкин.
Бит қаторлари устида символ қаторлари устида бажариладиган операцияларни бажариш
мумкин.
Кўрсаткич
(боғлама, далил) — бу ўлчами қайдланган маълумотларнинг элементидир.
Ундан машина хотирасида маълумотларни боғланган ҳолда тақдим этиш учун
фойдаланилади.
Кўрсаткич маълумотнинг мутлақ ёки нисбий манзили бўлиши мумкин.
Нисбий кўрсаткич шу соҳанинг баъзи базавий манзилига нисбатан хотира соҳасидаги
сурилиш қийматига эга бўлади.
Кўрсаткич манзил бўлганлиги учун у ҳам худди манзил каби сақланади. Аксарият
компьютерларда манзилни сақлаш учун хотирада сўз ёки ярим
сўз
ажратилади.
Саволлар
1.
Маълумотлар тузилиши таснифи
қандай?
2.
Маълумотлар кетма кет
рўйхати?
3.
Элементар
маълумотлар деб нимага
айтилади?