|
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 PA.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:
tuzilmaning har bir elementi ixtiyoriy sondagi ko‘rsatkichlarga ega bo‘lishi mumkin (ya‘ni, keyingi element sifatida ixtiyoriy sondagi elementlar ko‘rsatilishi mumkin);
bir element ixtiyoriy sondagi (bir yoki bir necha) elementlar tomonidan keyingi element sifatida ko‘rsatilishi mumkin;
ko‘rsatkich “vazni” (“mavqei”) tushunchasi kiritilishi va natijada, elementdagi ko‘rsatkichlar bir-biridan o‘z “vazni” bilan farqlanib, ko‘rsatkichlar ierarxiyasini tashkil etishi mumkin.
Nazariy savollari
Qanday dinamik tuzilmalarni bilasiz?
Dinamik tuzilmalarning asosiy farqlanuvchi tomonlari nima?
Dinamik ob‘ektlar bilan ishlash uchun qanday turlar mavjud?
Dinamik tuzilmalarda elementlar qanday bog‘lanadi?
Bir bog‘lamli ro‘yxatlarning asosiy xarakteristikasini aytib bering?
CHiziqli ro‘yxatlar xalqasimon ro‘yxatlardan qanday farq qiladi?
7.Ikki bog‘lamli ro‘yxat tushunchasining paydo bo‘lishiga nima sabab bo‘lgan deb hisoblaysiz?
Birbog‘lamli va ikkibog‘lamli ro‘yxatlar ustida bajariladigan amallarning qanday farqlari mavjud?
Ko‘ rsatkich nima?
Stek ustida bajariladigan qaysi amallarni navbatga ham qo‘llash mumkin?
Navbat ustida bajarish mumkin bo‘lgan qaysi amalni ro‘yxatlar uchun qo‘llash mumkin?
Ro‘yxat sarlavhasi elementlarini sanab o‘ting.
Bir bog‘lamli ro‘yxatga yangi element kiritish amalini bajarishga ketadigan vaqt ro‘yxatdagi elementlar soniga bog‘liqmi?
Yangi element kiritish amali qaysi holda samaraliroq bajariladi: ro‘yxatdami yoki massivda?
Bir bog‘lamli ro‘yxatni ko‘rib chiqish qanday amalga oshiriladi?
Bir bog‘lamli ro‘yxatning massivga nisbatan qanday kamchiligi bor?
Qanday tuzilmalar chiziqlimas hisoblanadi?
CHiziqlimas tuzilmalarning o‘ziga xos xususiyatlarini ayting
Do'stlaringiz bilan baham: |
