8-Mavzu: Ma’lumotlarning dinamik tuzilmalari Reja


Xalqasimon ikki bog'lamli ro‘yxatlar



Download 216,45 Kb.
bet4/7
Sana17.06.2021
Hajmi216,45 Kb.
#69178
1   2   3   4   5   6   7
Xalqasimon ikki bog'lamli ro‘yxatlar. Ikki bog'lamli ro‘yxatda oxirgi elementning Rptr maydonining qiymati sifatida boshlang'ich elementga murojaat ko‘rsatkichi, birinchi elementning Lptr maydoni qiymati sifatida esa oxirgi elementga murojaat ko‘rsatkichi qabul qilinadi. Bu ko‘rinishdagi

ro‘yxatlar xalqasimon shaklni hosil qilib, ko‘rsatkichlar bo‘yicha

harakatlanganda oxirgi elementdan birinchi elementga va aksincha murojaat

amalga oshirilishi mumkin .

Ro’yxatlar ustida bajariladigan amallar



Bir bog’lamli ro’yxatlar ustida bajariladigan oddiy amallar:

  1. Bir bog’lamli ro’yxat boshiga element qo’shish. Bir bog‘lamli ro‘yxat boshiga ma‘lumotlar maydoni D bo‘lgan elementni qo‘yish kerak bo‘lsin. Buning uchun bo‘sh element (P=GetNode) olib, uning ma‘lumotlar maydoniga D qiymatni (INFO(P)=D) ko‘rsatkich maydoniga esa ro‘yxat boshining ko‘rsatkich qiymatini (Ptr(P) = Lst) va ro‘yxat boshi ko‘rsatkichiga P ko‘rsatkich qiymtini (Lst = P) ta‘minlash kerak.

Paskal tilida yozilishi: type

PNode = ATNode;

TNode = record

Info: Integer; {ro‘yxat elementlari turi ixtiyoriy bo‘lishi mumkin}

Next: PNode;

end;


var

Lst: PNode; {ro‘yxat boshiga ko‘rsatkich}

P: PNode;

{ro‘yxat boshiga yangi element qo‘shish}

New(P); {yangi elementni yaratish}

PA.Info:=D;

PANext:=Lst; {P ro‘yxat boshiga ko‘rsatkich}

Lst:=P; {Lst ro‘yxatning yangi boshiga ko‘rsatkich}



  1. Bir bog’lamli ro’yxat boshidan elementni o’chirish. Ro‘yxatning birinchi elementini o‘chirish kerak, lekin bu elementning Info maydonidagi ma‘lumotni eslab qolish kerak. Buning uchun o‘chiriladigan (P=Lst) elementga ko‘rsatkich bo‘ladigan R ko‘rsatkichni kiritamiz. X o‘zgaruvchiga (X=Info(P)) o‘chirilayotgan elementning Info ma‘lumotlar maydoni qiymatini kiritamiz. Ro‘yxat boshiga ko‘rsatkich qiymatiga o‘chirilgan elementdan (Lst = Ptr(P)) keyingi element ko‘rsatkichi qiymatni ta‘minlaymiz. Elementni o‘chiramiz (FreeNode(P)).

Paskalda yozilishi:

{Ro‘yxat boshidan o‘chirish}

P:=Lst;

X:=PA.Info;

Lst:=PA.Next;

Dispose(P); {elementni dinamik xotiradan o‘ chiradi}



Ikki bog’lamli ro‘yxatlar ustida bajariladigan amallar:

  • ro‘yxat elementini yaratish;

  • ro‘yxatdan elementni qidirish;

  • ro‘yxatning ko‘rsatilgan joyiga yangi elementni qo‘yish;

  • tanlangan elementni ro‘yxatdan o‘chirish.

Steklarni bir bog'lamli ro‘yxatlar yordamida tashkillashtirish. Ixtiyoriy bir bog'lamli ro‘yxatni stek deb qarash mumkin. Stekni ro‘yxat shaklida berish uni bir o‘lchamli massiv sifatida tashkillashtirishga nisbatan birmuncha qulayliklarga ega. Xususan, ro‘yxatning o‘lchovini ilgaridan aniq berish talab etilmaydi.

  1. Stekka elementni qo‘shish (Push(S, X) amali) uchun, algoritmda Lst ko‘rsatkichni Stack ko‘rsatkichi bilan almashtirish kerak.

P = GetNode

Info(P) = X

Ptr(P) = Stack

Stack = P



  1. Stekning bo‘shligini tekshirish (Empty(S))

If Stack = Nil then Print —Stek bo‘sh”

Stop


  1. Stekdan elementni tanlash (POP(S))

P = Stack

X = Info(P)

Stack = Ptr(P)

FreeNode(P)



Paskal dasturlash tilida yozilishi:

  1. Lst ko‘rsatkichi o‘rniga Stack ko‘rsatkichi qo‘llaniladi.

Push (S, X) protsedurasi

procedure Push(var Stack: PNode; X: Integer); var

P: PNode; begin

New(P);


PA.Info:=X;

PA.Next:=Stack;

Stack:=P;

end;


  1. Stekning bo‘shligini tekshirish (Empty) function Empty(Stack: PNode): Boolean; begin

If Stack = nil then Empty:=True Else Empty:=False; end;

  1. Pop protsedurasi

procedure Pop(var X: Integer; var Stack: PNode); var

P: PNode; begin

P:=Stack;

X:=PA.Info;

Stack:=PA.Next;

Dispose(P);

end;

Navbat ustida bajariladigan amallarni ro’yxatga qo’llash. Ro‘yxat boshi ko‘rsatkichini navbat boshi ko‘rsatkichi F sifatida, ro‘yxatning oxirigi elementini ko‘rsatuvchi R ko‘rsatkichni esa navbat oxiri ko‘rsatkichi sifatida qaraymiz.


  1. Navbatdan elementni o‘chirish amali (Remove(Q, X)).

Navbatdan elementni o‘chirish amali uning boshidan boshlab qo‘llaniladi

P = F


F = Ptr(P)

X = Info(P)

FreeNode(P)


  1. Navbatni bo‘shlikka tekshirish amali (Empty(Q))

If F = Nil then Print —Navbat bo‘sh”

Stop


  1. Navbatga elementni qo‘shish amali (Insert(Q, X))

Navbatga elementni qo‘shish amali uning oxiridan boshlab qo‘llaniladi.

P = GetNode

Info(P) = X

Ptr(P) = Nil

Ptr(R)= P

R = P


Paskal dasturlash tilida yozilishi: procedure Remove(var X: Integer; Fr: PNode);

var


P: PNode; begin

New(P);


P:=Fr;

X:=PA.Info;

Fr:=PA.Next;

Dispose(P);

end;

function Empty(Fr: PNode): Boolean; begin



If Fr = nil then Empty:=True Else Empty:=False; end;

procedure Insert(X: Insert; var Re: PNode); var

P: PNode; begin

New(P);


PA.Info:=X;

PA.Next:=nil;

ReA.Next:=P;

end;


Ro‘yxatlar bilan ishlash jarayonida kompyuter xotirasidan samaraliroq foydalanish uchun formatlangan maydonlarga ega bo‘lgan erkin ro‘yxatlar, ya‘ni funktsional ro‘yxatlarni tashkil qilish ahamiyatga ega.

Agar funktsional ro‘yxatlar turli formatda bo‘lsa, u holda har bir funktsional ro‘yxat uchun erkin ro‘yxat tashkil etish zarur.

Dastur qayta ishlayotgan masalada erkin ro‘yxatning elementlari soni aniqlangan bo‘lishi shart. CHunki erkin ro‘yxat kompyuter xotirasida stek kabi tashkil etiladi. SHuning uchun ham yangi elementni hosil qilish bo‘sh stekdan elementni tanlash bilan ekvivalent, bo‘sh stekka bo‘shatiladigan elementni qo‘shish bilan ekvivalent.

Faraz qilaylik, bizga stek tipidagi bo‘sh ro‘yxatni (ro‘yxat boshi ko‘rsatkichi- AVAIL) tashkil etish masalasi qo‘yilgan (3.6-rasm) bo‘lsin. Ro‘yxatning bo‘sh elementini hosil qilish va ro‘yxatdan elementni chiqarib tashlash protseduralarini yaratamiz.





Ko‘pbog'lamli ro‘yxatdan o‘chiriladigan elementni chiqarib tashlash. Agar chiziqli bo‘lmagan ko‘pbog'lamli ro‘yxat qo‘llanigan bo‘lsa, ro‘yxatga bo‘shatilgan elementni qaytarishning standart amalini erkin element yordamida bajarish hamma vaqt ham samara bermaydi.

CHiqarib tashlashning birinchi usuli - bu hisoblagich (schetchik) usuli hisoblanadi. Ko‘pbog‘lamli ro‘yxatning har bir elementiga ushbu elementga murojaatlar sonini hisoblab boruvchi hisoblagich maydoni qo‘yiladi. Qachonki, element hisoblagichi nol holatida bo‘lsa, element ko‘rsatkich maydoni esa nil holatida bo‘lsa, bu element erkin element qo‘llash orqali qo‘yilgan bo‘ladi.

Ikkinchi usul - bu «chiqindi» (musor)ni yig‘ish metodi (marker metodi). Agar qaysidir elementga bog‘lanish o‘rnatilgan bo‘lsa, u holda elementning bir bitlik maydoni (marker)ga «1» o‘rnatilgan bo‘ladi, aks holda «0» bo‘ladi.


Download 216,45 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




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