8-Mavzu: Ma’lumotlarning dinamik tuzilmalari Reja

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}
P^A.Info:=D;
P^ANext:=Lst; {P ro‘yxat boshiga ko‘rsatkich}
Lst:=P; {Lst ro‘yxatning yangi boshiga ko‘rsatkich}

2. 
   
   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

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

   
   

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

Stop

3. 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;

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

   
   

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

3. Pop protsedurasi

   
   

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

P: PNode; begin
P:=Stack;
X:=P^A.Info;
Stack:=P^A.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)

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

   
   

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

Stop

3. 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.