9-mavzu: Chiziqsiz ma’lumotlar tuzilmasi


Download 1.36 Mb.
Sana29.11.2020
Hajmi1.36 Mb.

9-mavzu: Chiziqsiz ma’lumotlar tuzilmasi

  • Reja:
  • Chiziqsiz ma’lumotlar tuzilmasi haqida tushuncha.
  • Chiziqsiz ma’lumotlar tuzilmasi klassifikatsiyasi.
  • Chiziqsiz ma’lumotlar tuzilmasini mantiqiy tasvirlash.

Chiziqsiz ma’lumotlar tuzilmasi

  • Def.1.
  • Agar tuzilmani tashkil etuvchi elementlar qat’iy tartiblanmagan bo’lsa, u holda bunday tuzilmaga chiziqsiz ma’lumotlar tuzilmasi deyiladi.
  • Izoh
  • Chiziqsiz maʼlumotlar tuzilmasida elementlar orasidagi munosabatlar ixtiyoriy boʼlishi mumkin.
  • Chiziqsiz tuzilmani 3 ta farqli belgisini ajratish mumkin :
  • Tuzilmani xar bir elementi boshqa ixtiyoriy elementga murojaat qilish mumkin;
  • Tuzilmani berilgan elementiga mazkur tuzilmaning ixtiyoriy sondagi elementi murojaat qilishi mumkin;
  • Murojaatlar ogʼirlikga, hamda ierarxik koʼrinishga ega boʼlishi mumkin.
  • Chiziqsiz maʼlumotlar tuzilmasi klassifikatsiyasi
  • Izoh
  • Umuman olganda daraxt xam yoʼnaltirilgan graf boʼladi.
  • Roʼyxatlar:
  • chiziqsiz ikki bogʼlamli;
  • koʼp bogʼlamli;
  • Daraxtlar:
  • binar daraxtlar;
  • koʼpoʼlchamli daraxtlar;
  • Graflar:
  • yoʼnaltirilgan graf (orgraf);
  • yoʼnaltirilmagan graf (graf);
  • gipergraf

Misollar

  • Orgraf
  • D1
  • D2
  • D3
  • Chiziqsiz roʼyxat
  • Daraxt

Chiziqsiz bogʼlangan roʼyxatlar

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

Koʼp bogʼlamli roʼyxatlar (KBR)ning afzalligi: xotiraning tejalishidadir. Yaʼni bunda bir xil informatsion maydondan iborat bir necha roʼyxatlarni ifodalash mumkin va roʼyxatning bironta elementida oʼzgartirish qilinsa. Barcha roʼyxatlarga taalluqli xisoblanadi. KBR da bironta masala oʼziga tegishli qismroʼyxat bilan xuddi chiziqli roʼyxat kabi amalga oshiriladi va bunda muayyan koʼrsatkich maydoni bilan bajariladi

  • Koʼp bogʼlamli roʼyxatlar (KBR)ning afzalligi: xotiraning tejalishidadir. Yaʼni bunda bir xil informatsion maydondan iborat bir necha roʼyxatlarni ifodalash mumkin va roʼyxatning bironta elementida oʼzgartirish qilinsa. Barcha roʼyxatlarga taalluqli xisoblanadi. KBR da bironta masala oʼziga tegishli qismroʼyxat bilan xuddi chiziqli roʼyxat kabi amalga oshiriladi va bunda muayyan koʼrsatkich maydoni bilan bajariladi

Koʼp bogʼlamli roʼyxatdan keraksiz elementlarni oʼchirish

  • KBR dan elementni oʼchirish uni xotiradan butunlay oʼchirish degani emas. U boshqa qismroʼyxatlarda ishtirok etishi mumkin. Element xech qaysi qismroʼyxatga kirmagandagina uni xotiradan oʼchirish kerak. Elementlarni oʼchirishni soddalashtirish uchun odatda KBRda asosiy boʼlgan, barcha elementlarni oʼzida saqlovchi qismroʼyxat mavjud boʼladi. Boshqa qismroʼyxatlardan elementni oʼchirishda faqat unga tegishli koʼrsatkichlar qayta ishlanadi xolos. Аsosiy qismroʼyxatdan element oʼchirishda esa barcha roʼyxatlarda koʼrsatkichlar oʼzgartirilishi va xotira tozalanishi talab etiladi.
  • Keraksiz elementlarni utilizatsiya qilish yoʼllari
  • Hisoblagichlar (schyotchiklar) usuli
  • Markerlar usuli
  • Izoh
  • Koʼp bogʼlamli roʼyxatning har bir elementiga mazkur elementga murojatni hisoblovchi xisoblagich maydoni qoʼyiladi. Аgar element hisoblagich koʼrsatkichi nol va element koʼrsatkich maydoni nil boʼlsa, u holda ushbu element oʼchiriladi.
  • Izoh
  • Аloqa oʼrnatilgan element bir bitli maydoniga (marker) “1”, aks holda “0” yoziladi. Roʼyxat toʼlganligi toʼgʼrisida signal kelganda, markeri nol boʼlgan elementlar qidiriladi, yaʼni keraksiz elementlarni yigʼish dasturi ishga tushiriladi.
  • Граф тушунчаси
  • Def.2.
  • G=(V,E) juftlikka yoʼnaltirilgan graf (orgraf) deyiladi, bunda V - uchlari toʼplami (tugun), E - esa yoylar (yoʼnaltirilgan yoqlar).
  • v
  • w
  • Izoh
  • Graf yoyi tartiblangan (v,w) juftlik koʼrinishida aniqlangan boʼlib, v - yoy boshi, w - esa yoy oxiri boʼladi.
  • Eslatma !
  • Baʼzan vw yoyda v uchidan w uchigacha olib boradi deyiladi, w ga esa v uchiga qoʼshma deyiladi
  • 1
  • 2
  • 3
  • 4
  • Def.3.
  • Orgrafda yoʼl deb shunday v1, v2,…, vn tugunlar ketma-ketligi aytiladiki, bunda v1 v2, v2v3, … , vn-1vn yoylar mavjud boʼlishi shart.
  • Эслатма
  • Yo’l v1 dan boshlanadi va v2,…, vn-1 tugunlardan o’tib vn da yakunlanadi.
  • Def.4.
  • Yoʼl uzunligi deb yoʼlni tashkil etuvchi yoylar soniga aytiladi.
  • Def.5.
  • Yoʼl oddiy deyiladi, agar birinchi va soʼngi tugundan tashqari barcha tugunlar turli hil boʼlsa.
  • Chiziqsiz maʼlumotlar tuzilmasini mantiqiy tasvirlash
  • Koʼrsatkichli bogʼlangan roʼyxat
  • Masalan, qoʼshma matritsa orqali ifodalab olish
  • 1
  • 2
  • 3
  • 4
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0

Koʼrsatkichli bogʼlangan roʼyxatlar koʼrinishida ifodalash

Koʼrsatkichli bogʼlangan roʼyxat koʼrinishida ifodalash

  • Chiziqsiz bogʼlangan roʼyxat koʼrinishida ifodalash

Mavzu boʼyicha nazorat savollari

  • Chiziqsiz maʼlumotlar tuzilmasining oʼziga xosligi nimalardan iborat?
  • Chiziqsiz maʼlumotlar tuzilmasining klassifikatsiyasi.
  • Graf turlari: Orgraf, graf, gipergraf.
  • Chiziqsiz maʼlumotlar tuzilmalarini mantiqiy tasvirlash yoʼllari.

Download 1.36 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling