Мавзу: Чизиқсиз маълумотлар тузилмаси Режа

Мавзу: Чизиқсиз маълумотлар тузилмаси

Режа:

• Chiziqsiz ma’lumotlar tuzilmasi. Daraxtsimon maʻlumotlar tuzilmalari
• Binar va ko‘ptarmoqli daraxtlar. Taʻriflar va xususiyatlar. Daraxtlarni binar ko‘rinishga keltirish algoritmi. Rekursiya va ularni dasturlashda ishlatish.

Чизиқсиз маълумотлар тузилмаси

Def.1.
Агар тузилмани ташкил этувчи элементлар боғлиқлиги қатъий тартибланмаган бўлса, у ҳолда бундай тузилмага чизиқсиз маълумотлар тузилмаси деб аталади.
Изоҳ
Чизиқсиз маълумотлар тузилмасида элементлар орасидаги муносабатлар ихтиёрий бўлиши мумкин.
Чизиқсиз тузилмани 3 та фарқли белгиси мавжуд:

• Тузилмани хар бир элементи бошқа ихтиёрий элементга мурожаат қилиш мумкин;
• Тузилмани берилган элементига мазкур тузилманинг ихтиёрий сондаги элементи мурожаат қилиши мумкин;
• Мурожаатлар оғирликга, яъни мурожаатлар иерархик кўринишга эга бўлиши мумкин.

Чизиқсиз маълумотлар тузилмаси классификацияси

• Рўйхатлар:
• чизиқсиз икки боғламли;
• кўп боғламли;
• Дарахтлар:
• бинар дарахтлар;
• кўпўлчамли дарахтлар;
• Графлар:
• йўналтирилган граф (орграф);
• йўналтирилмаган граф (граф);
• гиперграф.

Изоҳ
Умуман олганда дарахт хам йўналтирилган граф бўлади.

Мисоллар

Орграф
D1
D2
D3
Чизиқсиз боғланган рўйхат
Дарахт

Чизиқсиз боғланган рўйхатлар

Чизиқсиз боғланган рўйхат

Рекурсия ҳақида тушунча

Изоҳ
Рекурсия (умуман)– бу объектни мазкур объектга мурожаат қилиш орқали аниқлашдир.
Изоҳ
Рекурсив алгоритм – бу алгоритмни аниқлашда ўзига бевосита ёки билвосита мурожаат қилишдир.
Эслатма: Алгоритм ва дастурларни тузишда рекурсиядан фойдаланиш вақтни тежайди, хажми кичик бўлади, лекин итерацион усулга нисбатан дастур секинроқ ишлайди ҳамда кўпроқ хотира талаб этади.
Def.1.
Агар маълумотлар тузилмаси элементлари ҳам мазкур тузилмага ўхшаш тузилма бўлса, у ҳолда бундай тузилмага рекурсив маълумотлар тузилмаси дейилади.

Рекурсив объектларга мисоллар

Серпинский учбурчаги

Дарахт тушунчаси

Дарахт – бу чизиқсиз боғланган маълумотлар тузилмасидир.

Дарахт ўзининг қуйидаги белгилари билан таснифланади:

• дарахтда шундай битта элемент борки, унга бошқа элементлардан мурожаат йўқ. Мазкур элементга дарахт илдизи дейилади;
• дарахтда ихтиёрий элементга чекли сондаги кўрсаткичлар ёрдамида мурожаат қилиш мумкин;
• дарахтнинг ҳар бир элементи фақатгина ўзидан олдинги келган битта элемент билан боғланган. Дарахтнинг ҳар бир тугуни оралиқ ёки терминал (барг) бўлиши мумкин.

Def.2.
Дарахт босқичлари сонига дарахт баландлиги дейилади.
Def.3.
Тугунлардан чиқаётган шоҳлар сони тугундан чиқиш даражаси дейилади.
0-чи босқич
1-чи босқич
2-чи босқич
Чиқиш даражалари
3
1
2

Дарахтлар классификацияси

1) агар максимал чиқиш даражаси m бўлса, у ҳолда бундай дарахт m-чи тартибли дарахт дейилади;
2) агар чиқиш даражаси 0 ёки m бўлса, у ҳолда тўлиқ m-чи тартибли дарахт дейилади;
3) агар максимал чиқиш даражаси 2 бўлса, у ҳолда бундай дарахт бинар дарахт дейилади;
4) агар чиқиш даражаси 0 ёки 2 бўлса, у ҳолда тўлиқ бинар дарахт дейилади.
Тугунлар орасидаги боғлиқликни тавсифлаш учун яна қуйидагича атамадан фойдаланилади: отаўғил.
Эслатма
Дарахтлар чиқиш даражаси бўйича классификация қилинади.

Дарахтларни тасвирлаш

Мантиқий тасвирланишда дарахтлар боғланган рўйхатлар кўринишида ифодаланади. Бунда рўйхат элементи тугун қиймати ва чиқиш даражасини ўз ичига олувчи информацион майдонга хамда чиқиш даражасига тенг бўлган кўрсаткичлар майдонига эга бўлади.

Дарахтни график ва чизиқсиз рўйхат шаклидаги тасвирланиши

Мавзу бўйича назорат саволлари

• Чизиқсиз маълумотлар тузилмаси
• Рекурсия нима?
• Рекурсив объект, алгоритм, функция тушунчаси.
• Рекурсив триада.
• Рексурсив алгоритм самарадорлигини аниқлаш ва ошириш йўллари.
• Дарахт тушунчаси: баландлиги, чиқиш даражаси.
• Дарахтлар классификацияси.
• Дарахтларни мантиқий тасвирлаш.