Chiziqsiz malumotlar tuzilmasi



Download 0,87 Mb.
bet3/3
Sana23.06.2022
Hajmi0,87 Mb.
#696294
1   2   3
Bog'liq
Chiziqsiz malumotlar tuzilmasi

4-rasm. Chiziqsiz bog’langan tarmoqlanuvchi ro’yhatlar
Qayta ishlashda chiziqsiz ro’yhat atomlar va qismro’hatlardan iborat ihtiyoriy ketma-ketlik bo’ladi. Bu holda atom sifatida shunday ob’ekt olinadiki, u qayta ishlash jarayonida tuzilmaviy jihatdan bo’linmasligi kerak.
U holda chiziqsiz tarmoqlanuvchi ro’yhatni, qavs ichiga yozilgan va vergul bilan ajratilgan elementlar shaklida quyidagicha ifodalash mumkin:
(a,(b,c,d),e,(f,g))
( )
((a))
Birinchi ro’yhat 4 ta elementga ega: a-atom, (b,c,d)-qism ro’yhat (o’z navbatida b,c,d atomlarga ega), e-atom va (f,g)-qism ro’yhat. Ikkinchi ro’yhat elementlarga ega emas – bo’sh ro’yhat. Uchinchi ro’yhat 1 ta elementga ega, bu atom - а. 1
Bunday ro’yhatlarni dasturda ifodalash uchun xotirada quyidagicha tuzilishda ifodalash kerak.

info maydon

down – qismro’yhatga
ko’rsatkich

next – keying elementga ko’rsatkich

C++ dasturlash tilida e’lon qilinishi:

class Sublist{ //qismro’yhat elementlari
toifasi int info; Sublist *next;
}
class Node{ //asosiy ro’yhat
elementlari toifasi int info;
Sublist *down;
Node *next; }

Chiziqsiz bog’langan tarmoqlanuvchi ro’yhat ustida asosiy amal bajarish algoritmlari:

  • asosiy ro’yhatga element kiritish;

  • elementga tegishli qismro’yhatga element kiritish;

  • asosiy ro’yhatdan element o’chirish;

  • qismro’yhatdan element o’chirish;

  • asosiy va qismro’yhatni bo’shlikka tekshirish;

  • element qidirish;
2. Chiziqsiz ro’yhatlarni mantiqiy tasvirlash

Ro’yhatlarning kamchiligi bor: elementlarni qidirishda qat’iy ketma-ketlik mavjud. Qidirish davom ettiriladi toki element topilguncha yoki ro’yhat oxiriga yetguncha, agar element topilmasa. Shu masalani hal qilish uchun yuqorida aytilgan skip listlardan foydalaniladi. Bunda elementni qidirishda yoki unga murojaat qilishda ungacha bo’lgan xar bir element ko’rib chiqilmaydi.
n ta elementdan iborat skip list berilgan bo’lsin. Unda xar bir 1 ≤ k ≤ ⎣lg n⎦ va 1 ≤ i ≤ ⎣n/2k–1⎦ – 1 shartni qanoatlantiruvchi k va i uchun 2k-1*i o’rinda turgan tugun 2k-1*(i+1) o’rinda turgan tugunni ko’rsatadi. Bu degani, xar bir 2tugun 2 tugun keyin turgan elementga murojaat qiladi va xar bir 4-element o’zidan 4 ta keyin turgan elementga murojaat qiladi va x.k. ( 5-quyidagi rasm)

5 rasm. Skip list tuzilmasi.
Ushbu rasmdagi kabi skip listdan elementni qidirish algoritmi quyidagicha: (bizga ma’lumki, skip list tartiblangan) qidiruv eng yuqori ko’rsatkich bilan boshlanadi

  • Agar oldinda el elementdan qiymat jixatidan kichik elementlar chiqsa, qidiruv davom ettiriladi, toki el dan katta element chiqqunga qadar.

  • Agar oldinda el dan katta element chiqadigan bo’lsa, bitta oldingi elementga qaytiladi va qidiruv bitta past darajadagi ko’rsdatkich bilan davom ettiriladi.

  • Qidiruv element topilguncha davom ettiriladi yoki eng pastki darajadagi ko’rsatkich bilan oraliqdagi elementlarning xammasi tekshirilib chiqqanda to’xtatiladi.

el elementni qidirish psevdokodi quyidagicha:

search(element el)
p=the nonnull list on the highest level i;
while el not found and i≥0 if p->key>el
p=a sublist that begins in the predecessor of p
on level --i; else if p->key< el
if p is the last node on level i p=a nonnull sublist that begins in p on the
highest level < i; i=the number of the new level; else p = p->next;

Masalan, agar bu ro’yhatda (5b-rasm) 16 ni qidiradigan bo’lsak, 4darajadan qidirishni boshlaymiz. Uning 1-elementi 28 ga olib boradi va bu darajada element topilmaydi, shu sababli bitta past darajadagi ko’rsatkich bo’yicha qidiramiz. Unda 1-element 8, demak kyingi elementni tekshiramiz, 2element 17, o’tib ketildi. Biz qidirayotgan element shu ikki element orasida bo’lishi mumkinligi sababli yana bitta past darajadagi ko’rsatkich bilan davom etamiz va bunda n8 va 17 orasidagi elementlar tekshiriladi. Bunda navbatdagi element 10 chiqadi va undan keyin yana 17. Shu sababli eng quyi darajaga tushib 10 va 17 orasi qidiriladi. Unda 10, 12, 17 sonlari kelib chiqadi. Boshqa quyi darajadagi ko’rsatkich yuq va element shu paytgacha topilmagani uchun tuzilmada bu element yuq deb aytiladi.
Nazorat savollar

  1. Chiziqsiz malumotlar tuzilmasining o’ziga xosligi nimalardan iborat?

  2. Chiziqsiz malumotlar tuzilmasining klassifikasiyasi?

  3. Daraxt va graf - chiziqsiz malumotlar tuzilmasi nima?.

  4. Chiziqsiz tarmoqlanuvchi ro’yhat nima?

  5. Skip list nima?

  6. Skip listlarni dasturda ifodalanishi qanday?

  7. Skip list samaradorligi qanaqa?
Adabiyotlar

  1. AdamDrozdek. Data structure and algorithms in C++. Fourth edition. 2013. Chapter 3.4. 96-106 betlar.

В.Д.Далека, А.С.Деревянко, О.Г.Кравец, Л.Е.Тимановская. Модели и cтруктуры данных. учебное пособие. Харьков:ХГПУ, 2000. - 241с. http://khpi-iip.mipk.kharkiv.edu/library/datastr/book/prt05.html#lb54

1 В.Д.Далека, А.С.Деревянко, О.Г.Кравец, Л.Е.Тимановская. Модели и cтруктуры данных.
учебное пособие. Харьков:ХГПУ, 2000. - 241с. http://khpiiip.mipk.kharkiv.edu/library/datastr/book/prt05.html#lb54

Download 0,87 Mb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish