|
O'zbekiston respublikasi oliy va o'rta maxsus ta'lim vazirligi buxoro davlat universiteti
|
| bet | 8/16 | | Sana | 12.12.2023 | | Hajmi | 2,02 Mb. | | #117545 |
Bog'liq Buxoro davlat universiteti I va K uzaro tasiri amaliy shablon-2 compressed, Kompyuter injineringi ” fakulteti 4 – bosqich di-13-19 guruh tal, Ishdan maqsad Dasturiy ta’minot tizimlarini loyihalashda spetsi-fayllar.org1.2.3.4-chizma. Ma’lumotlarnig ierarxik tuzilmasini aks ettiruvchi turli turdagi daraxt
Har bir bo’g’imi bir xil sondagi shoxlarga ega daraxt muvozanatlashgan daraxt hisoblanadi. Muvozanatlashgan n-darajali daraxtda (n-l)-daraja to’liq to’ldirilgan bo’lsa, u simmetrik daraxt deb ataladi. Muvozanatlashgan daraxtda har bir yaratuvchi ikkitadan ko’p bo’lmagan yaratilganga ega bo’lsa, u ikkilik yoki binar daraxt deb ataladi. Ikkilik daraxtda yaratuvchidan yaratilganlarga yo’nalish o’ngga va chapga bo’lishi mumkin. Ushbu chapga bog’lanish vositasi bilan bog’langan barcha bo’g’imlar chap kichik daraxt (chap shox)ni tashkil qiladi, ushbu o’ngga bog’lanish vositasi bilan bog’langan bo’g’imlar o’ng kichik daraxt (o’ng shox)ni tashkil qiladi.
1.2.3.5-chizma. Ixtiyoriy daraxtni ikkilik daraxt ko’rinishida taqdim etish
Ikkilik daraxtlari kompyuterda qayta ishlash va saqlash uchun eng qulaydir. Biroq predmet sohasining juda kam munosabatlari bevosita ikkilik daraxt ko’rinishida taqdim etilishi mumkin. Shuning uchun ko’pchilik hollarda ma’lumotlarning mantiqiy tuzilmasini taqdim etadigan daraxtning tuzilmasi aniqlanganidan so’ng olingan ixtiyoriy daraxt binar daraxtga keltiriladi. Bunda quyidagi tarzda ish ko’riladi. Har bir yaratuvchi bo’g’im uchun undan chiquvchi eng chapdagisidan tashqari barcha qirralar yo’qotiladi. O’sha darajaning barcha «ajralib chiqqan» yaratilganlari «...ga o’xshash» ko’rsatkichlar bilan chapdagi yaratilganga bog’lanadi. 5.8-chizma ixtiyoriy daraxtsimon tuzilmani ko’rsatkichlar yordamida tuzilmaning yaratilgan va o’xshash elementlarida ikkilik daraxt ko’rinishida taqdim etishni namoyish etadi.
1.2.3.6-chizma. Ixtiyoriy ikkilik daraxti
Ikkilik daraxtda yo’nalishlarga ma’lum mantiqiy ma’nosi qarshi qo’yilishi mumkin. Masalan, ko’pincha chap yo’nalish yaratuvchi bo’g’imdagi yozuvga qaraganda kichikroq qiymatdagi kalitli yozuv joylashgan bo’g’imga olib boradi deb, o’ng yo’nalish esa kattaroq kalitga ega yozuvli bo’g’imga olib boradi deb qabul qilinadi. Faqat yozuvlarni kalit polyalarining qiymatini ko’rsatgan holda shunday daraxtni quramiz. Yozuvlar qayta ishlashga quyidagi ketma-ketlikda berilsin: 21, 7, 33, 38, 19, 100, 36, 63, 180, 51, 290, 260, 286. Birinchi yozuv daraxt ildiziga joylashtiriladi, qolganlari qabul qilingan yo’nalishlar mantiqiga muvofiq joylashadi. Saflanish natijasida 5.9-chizmada ifodalangan daraxt hosil bo’ladi. Bunday daraxtda zarur qiymatdagi kalitli yozuvni izlash quyidagi qoida bo’yicha amalga oshiriladi: agar izlanayotgan kalit ushbu bo’g’im kalitidan kichik bo’lsa, bu bo’g’imdan chapga qarab harakat qilish lozim bo’ladi, agar izlanayotgan kalit katta bo’lsa, harakatni o’ng yo’nalishda davom ettirish lozim bo’ladi.
Ma’lumotlarni qayta ishlashning turli protseduralarini bajarish uchun simmetrik daraxtlar eng qulay hisoblanadi. 5.9-chizmada olingan daraxt simmetrik emasligi ko’rinib turibdi. Simmetrik daraxtni qurish uchun ikki bosqichda bajariladigan boshlang’ich ketma-ketlikni dastlabki qayta ishlash zarur bo’ladi. Birinchi bosqichda yozuvlarning boshlang’ich ketma-ketligi kalit polyalar qiymatlarining o’sib borishi yoki kamayib borishi bo’yicha tartibga solinadi. Ikkinchi bosqichda daraxtni turli darajalarining bo’g’imlarida joylashtiriladigan kalitlar aniqlanadi. Ildiz bo’g’imda tartibga solingan ketma-ketlikning markazida joylashgan va uning ikkiga bo’ladigan kalit joylashtiriladi. Ketma-ketlikning chap va o’ng yarimlarini ikkiga bo’ladigan kalitlar mos ravishda chap va o’ng kichik daraxtlarni ikkinchi darajasining bo’g’imlarida joylashtiriladi. Ketma-ketlikning yangitdan olinayotgan bo’laklarini bo’lish va tegishli darajalarning kalitlarini topish protsedurasi daraxt to’liq qurib bo’linmagunicha davom etadi.
Yuqorida ko’rib chiqilgan yozuvlar ketma-ketligini simmetrik ikkilik daraxt ko’rinishida taqdim etamiz, buning uchun esa uni kalit qiymatlarining o’sib borishi bo’yicha tartibga solamiz: 7, 19, 21, 33, 36, 38, 51, 63, 100, 180, 260, 286, 290. 51 qiymatiga ega kalit daraxt ildiziga joylashtiriladi. 21 yoki 33 kalitlar chap kichik daraxtdagi, 180 yoki 260 kalitlar esa o’ng kichik daraxtdagi ikkinchi daraja bo’g’imi bo’lishi mumkin. Bizning misolda 33 va 180 kalitlari tanlab olingan. Boshqa darajalarning bo’g’imlari ham xuddi shu tarzda aniqlanadi. Qurish natijasida olingan daraxt simmetrik hisoblanadi.
Simmetrik daraxt ajoyib xususiyatga ega: daraxtdagi ildizdan ixtiyoriy joygacha bo’lgan yo’llar bir xil uzunlikka ega. Bu uzunlik minimaldir, sababi daraxtning balandligi minimaldir, shuning uchun bunday daraxt bo’yicha zarur yozuvlarni izlashda ixtiyoriy boshqa daraxtga qaraganda kamroq o’qish va taqqoslash operatsiyalari talab etiladi.
1.3 Ro’yxatlar
Ro'yxat bu shunday ma'lumotlar majmuasiki, uning elementlari bog’langan bo'lib, ular turli turlarga tegishli bo'lishi mumkin.
Ro'yxatga misol:
E1, E2, ........, En,... n > 1 bo'lib n fiksirlanmagan.
Ro'yxat elementlari soni dastur bajarilishi davomida o'zgarib turishi mumkin. Ro'yxatning 2 turi mavjud:
Bog’lanmagan
Bog’langan
Ro'yxatning bog’lanmagan turida uning elementlari orasidagi bog’liqlik oshkormas (noaniq) ko'rinishda bo'ladi. Bog’langan turida esa ma'lumot elementlariga ro'yxatda o'zidan oldingi yoki keyingi keluvchi element bilan aloqasini bildiruvchi ko'rsatich kiritiladi.
Dastur bajarilayotganda vujudga keladigan yoki o'lchamlari dastur bajarilishi mobaynida aniqlanadigan obyektlar dinamik obyektlar deyiladi. Dinamik a'lumotlar tuzilmasi 2 ta xususiyatga ega:
Tuzilmada elementlar soni oldindan aniqlanmagan.
Dinamik tuzilma elementlari qat'iy chiziqli tartiblanmagan.
Ular xotirada tartibsiz joylashgan bo'lishi mumkin. Dinamik tuzilma elementlarini o'zaro bog’lash uchun tuzilma elementlari tarkibiga informatsion maydondan tashqari ko'rsatkichlar maydoni xam kiradi (qarang, chizma) (tuzilmani boshqa elementlari bilan bog’liqlik).
|
| |
