8-Mavzu: Ma’lumotlarning dinamik tuzilmalari Reja

misol. O‘sish tartibida tartiblangan info maydonli ro‘yxat berilgan. Bu ro‘yxatga X qiymatli elementni shunday qo‘shish kerakki, ro‘yxatdagi tartib buzilmasin.


X=16 bo‘lsin. Boshlang'ich shartlar: Q = Nil, P = Lst. Yangi element 3 va 4- elementlar orasiga qo‘shilishi kerak (3.10-rasm).

Algoritm quyidagicha yoziladi:

Q =Nil

P = Lst
While (P <> Nil) and (X > Info(P)) do

Q = P
P = Ptr(P)

EndWhile if Q = Nil then

Push(Lst, X)
EndIf
InsAfter(Q, X)

Quyida 1 va 2-misollarni yechish dasturi keltirilgan:

1-misol:
Q:=nil;

P:=Lst;
While P <> nil do

If P^A.Info = 4 then begin
If Q = nil then begin
Pop(Lst);
P:=Lst;

end
Else Delafter(Q,X);

End;
Else

begin
Q:=P;

P:=PA.Next;
end;

end;

2-misol:
Q:=nil;

P:=Lst;
While (P <> nil) and (X > PA.Info) do begin

Q:=P;
P:=PA.Next;

end;
{Bu yerda qo‘yish amali bajariladi}

If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;

Ro‘yxat sarlavhasi elementlari. Sarlavhali ro‘yxatlarni hosil qilish uchun

ro‘yxat boshiga qo‘shimcha element kiritilib, bu element ro‘yxat haqidagi ma'lumotlarni o‘zida saqlab turadi (3.11-rasm).

Odatda, sarlavhada ro‘yxat elmenetlari sonini saqlovchi (sarlavhaning o‘zi hisobga olinmaydi) dinamik o‘zgaruvchi joylashadi. Agar ro‘yxat bo‘sh bo‘lsa, u faqat sarlavhadan iborat bo‘ladi (3.12-rasm).

Sarlavhaning ma'lumot maydonida ro‘yxat oxirini ko‘rsatuvchi qiymatni saqlash ham mumkin. Bundan tashqari, sarlavhaning ma'lumotlar maydonini ishchi ko‘rsatkich qiymatini saqlash uchun ishlatish ham mumkin. Ro‘yxat elementlarini ketma-ket ko‘rib chiqishda ishchi ko‘rsatkichdan foydalanish juda qulay hisoblanadi.

Ma'lumotlar tuzilmasining sarlavhasi uning deskriptorini tashkil qiladi.
CHiziqli bo‘lmagan bog'langan tuzilmalar. Agar ikki bog'lamli ro‘yxatda ikkinchi ko‘rsatkich elementlar joylashuvining erkin tartibini ko‘rsatsa, bu ro‘yxatni chiziqli bo‘lmagan ma'lumotlar tuzilmasi deb qarash mumkin (3.13- rasm).

Yuqorida ikki xil ro‘yxatni ko‘rish mumkin. Ulardan biri PTR1 ko‘rsatkichlar bilan berilgan, 5 ta elementdan iborat va chiziqli. PTR2 ko‘rsatkich bilan berilgan ikkinchi ro‘yxat ham aynan shu elementlardan iborat, lekin elementlar ketma-ketligi chiziqli emas, elementlar 1-ro‘yxatdagidek birin-ketin emas, balki 3-, 5-, 4-, 1-, 2-element tartibida joylashgan.

Umumiy holda, ro‘yxat elementiga xohlagancha sondagi ko‘rsatkichlar kiritilib, har bir ko‘rsatkich orqali elementlar ketma-ketligining alohida bir tartibi berilishi mumkin.
CHiziqli bo‘lmagan tuzilmalarning 3 ta asosiy belgisini ko‘rsatish mumkin:

1. tuzilmaning har bir elementi ixtiyoriy sondagi ko‘rsatkichlarga ega bo‘lishi mumkin (ya‘ni, keyingi element sifatida ixtiyoriy sondagi elementlar ko‘rsatilishi mumkin);

   
   

2. bir element ixtiyoriy sondagi (bir yoki bir necha) elementlar tomonidan keyingi element sifatida ko‘rsatilishi mumkin;

   
   

3. ko‘rsatkich “vazni” (“mavqei”) tushunchasi kiritilishi va natijada, elementdagi ko‘rsatkichlar bir-biridan o‘z “vazni” bilan farqlanib, ko‘rsatkichlar ierarxiyasini tashkil etishi mumkin.