8-Mavzu: Ma’lumotlarning dinamik tuzilmalari Reja

Bir bog'lamli ro‘yxat mustaqil ma'lumotlar tuzilmasi sifatida. Bir bog'lamli ro‘yxat elementlariga murojaat faqat ro‘yxatning boshidan boshlab ketma-ket ravishda bajarilishi mumkin. Agar joriy elementdan oldingisini

ko‘rish (qayta ishlash) talab qilinsa, u holda yana ro‘yxat boshiga qaytish kerak

bo'ladi. Bu - bir boglamli ro'yxatlarning massiv turidagi statik ma'lumotlar tuzilmasiga nisbatan kamchiligi hisoblanadi. Ularning afzalliklari ham mavjud. Elementlar soni juda katta bo‘lib, element qo‘shish va o‘chirish amallari faqat ro‘yxat ichida bajarilsa, uning samaradorligi namoyon bo‘ladi.

Misol:
Mavjud massivning 5 va 6 elementlari o‘rtasiga X elementni qo‘yish kerak bo‘lsin.
Ro’yxatga element qo’shish
Bu amalni bajarish uchun massivda X6-elementdan boshlab keyingi
elementlarni surib, joy ochish kerak. bo‘shatilgan joyga yangi X elementni kiritsak quyidagi massiv hosil bo‘ladi (3.8-rasm):
Massivda bu protseduraning bajarilishi juda ko‘p vaqtni olishi mumkin. Bir bog‘lamli ro‘yxatda esa yangi element qo‘shish amali ko‘p vaqt talab qilmaydi va sarflangan vaqt o‘zgarmas hamda ro‘yxat elementlari sonidan bog‘liq emas. Yangi element qo‘shish uchun 2 ta ko‘rsatkich qiymatini o‘zgartirish kifoya.


Ro’yxatdan elementlarni chiqarib olish va ro’yxatga element qo’shish.
Ro‘yxatda ushbu amallar bajariladigan joyni aniqlaymiz. Qo‘yish InsAfter(Q,X) protsedurasi, o‘chirish esa DelAfter(Q, X) protsedurasi yordamida amalga oshiriladi.
Oraliq ma‘lumot sifatida ishlatiladigan P yangi ko‘rsatkich qo‘yiladigan yoki o‘chiriladigan elementning joyini ko‘rsatadi.
1-misol (element qo‘shish):

Ishchi ko‘rsatkich P ko‘rsatib turgan elementdan keyingi joyga axborot maydoni X bo‘lgan yangi elementni kiritish talab qilingan bo‘lsin.

Buning uchun:

1. yangi element hosil qilinadi:

   
   

Q = GetNode;

2. hosil qilingan elementning axborot maydoniga X qiymat ta‘minlanadi: Info(Q) = X;

   
   

3. olingan element qo‘shiladi:

   
   

Ptr(Q) = Ptr(P);

Ptr(P) = Q;
Bu amallar InsAfter(Q, X) protsedurasini tashkil qiladi.