|
24-маъруза
Маълумотларнинг абстракт структуралари.
Режа:
Рўйхат, Стек, навбат, бинар дарахт.
Хэш-функциялар, Граф, тўпламлар.
Иҳтиёрий программа турли типдаги маълумотларни қайта ишлаш учун мўлжалланган бўлиб, ташкил қилиш усули масала алгоритмига боғлиқ бўлади. турли типдаги масалалар учун маълумотларни турли шаклларда маълумотларни сақлаш талаб қилинади. Шунинг учун маълумотлар структураси алгоритмларга мос келиб, дастурнинг функционаллиги хамда тез ишлашини таъминлаши талаб қилинади. Дастурларда кўпинча массив, рўйхат, стек, навбат, бинар дарахт, хеш-жадвал, граф ва тўплам каби маълумот тузилмаларидан кенг фойдаланилади. Қуйида бу тузилмаларнинг қисқа тавсивларини келтирамиз.
Массив — бу бир ҳил типаги маълумотларнинг чекли тўпламидан иборат. Массивлар хотиранинг узлуксиз қисмини банд қилади хамда ўз элементларига тўғридан – тўғри, индекс номерларини кўрсатиш орқали мурожаат қилишга рухсат беради. Массив учун хотира дастур иш бошлагунча ажратилади ва кейинчалик ўзармайди.
Рўйхатларда хар бир элемент ўзидан кейинги элемент билан боғланган бўлади, айрим холларда ўзидан аввалги элемент билан ҳам боғланган бўлиши мумкин. Биринчи усулда ташкил қилинган рўйхатларни бир томонлама, иккинчисини эса – икки томонлама деб аташ қабул қилинган. Рўйхат элементларининг сони дастурнинг бажарилиши давомида ўзгариши мумкин.
Рўйхатнинг ҳар бир элементи бу элементни таниш учун калитга эга бўлади. Калит одатда ёки сон, ёки сатр, ёки рўйхатнинг ҳб элементида сақланаётган маълумотнинг бир қисми бўлиши мумкин. Калит сифатида иш жараёнида маълумотларнингтурли қисмлари иштирок этиши мумкин. Масалан, фамилия ва исм, туғилган йил, иш стажи каби маъумотлардан ташкил топган рўйхатнри ташкил қилинган бўлса, тартиблаш масаласи учун калит ўрнида бу маълумотларнинг иҳтиёрий биридан фойдаланиш мумкин. Рўйхатнинг турли элементлари учун калитлар устма-уст тушиши ҳам мумкин.
Рўйхатлар устида қўшиш, ўчириш, орасига қўйиш, берилган калитли маълумотларни ўқиш каби амалларни бажариш мумкин. Рўйхатдаги маълумотларга тўғридан – тўғри тушиб бўлмайди, шунинг учун ўқиш, орасига қўйиш ёки ўчириш амалларини бажарганда элементлар кетма-кетлиги то талаб қилинган элемент топилмагунча тўла кўриб чиқилади.
Стек — бир томонлама рўйхатларнинг ҳусусий ҳоли бўлиб, маълумотларни қўшиш ва фойдаланиш стекларнинг бир учидан амалга оширилади. Стеклар билан бажариш учун бошқа амаллар кўзда тутилмаган. Стекдаги элементлар танланганда, одатда уларни стекдан ўчирилади. Стеклар билан ишлаш LIFO (Last In — First Out, охирги келган биринчи кетади) принципи билан ишлайди.
Навбат – бу бир томонлама рўйхатларнинг ҳусусий ҳоли бўлиб, унга элементлар бир томондан қўшилади, фойдаланиш эса иккинчи учидан амалга оширилади. Навбатлар билаб бошқа амаллар назарда тутилмаган. Навбатлар FIFO (First In — First Out, биринчи келган – биринчи кетади) принципи билан ишлайди.
Бинар дарахт — динамик структурали маълумот бўлиб, ҳар бири тугуни бошқа маълумотлардан ташқари турли бинар ост дарахтларга камида иккита ҳаволаларни ўз ичига олади. Ҳар бир тугунда роппа-роса битта ҳавола мавжуд. Бошланғич тугун дарахтнинг илдизи (ўзаги) деб аталади. Бинар дарахта мисол 16.-расмда келтирилган. Ост дарахтларга эга бўлмаган тугунни япроқ деб аталади. Чиқувчи тугунлар – аждодлар, кирувчи тугунлар эса авлодлар дейилади. Дарахтнинг баландлиги унинг шажарасини ташкил қилувчи тугунлари миқдори билан аниқланади.
16.1-расм. Бинар дарахтга намуна.
Ҳар бир тугунлар учун унинг чап ост дарахтларининг барча калитлари шу тугун калитидан кичик, ўнг ост дарахтларнинг барча калитлари тугун калитидан катта бўлса, бундай дарахтларни излаш дарахти деб аталади. Бир хил калитлардан фойдаланишга рухсат этилмайди. Излаш дарахтларида илдиздан чап ва ўнг ост дарахтларга ўитб бориб, калит бўйича элементни топиш мумкин. Бундай излаш рўйхатлан излашга қараганда самаралироқ ҳисобланади, чунки излаш вақти дарахтнинг баландлигина боғлиқ бўлади. У эса тугунлар сонининг иккилимк логарифмига пропорционал.
Хеш-жадвал, ассоциатив массив, ёки луғат — бу массив бўлиб, унинг элементлари билан ишлашга рухсат номери бўйича эмас, балки бирор калит бўйича амалга ошрилади. Айтиш мумкинки, бу жадваллар "калит-қиймат" (16.1-жадвал) жуфтлигидан иборат бўлади. Хеш-жадваллар калит бўйича излаш амалиётини самарали ташкил қилишга имкон беради. Бунда калитлар сонга ( хэш-код ) га айлантирилади ва хеш-жадввалдаги маълумотларни тезкорлик билан топишда фойдаланилади.
Do'stlaringiz bilan baham: |
