11 ma`ruza: “RO’yhat” turidagi ma’lumotlarning abstrakt turlari va ro’yhatlarni amalga oshirish (statik va dinamik). Reja

11 - MA`RUZA: “RO’YHAT” TURIDAGI MA’LUMOTLARNING ABSTRAKT TURLARI VA RO’YHATLARNI AMALGA OSHIRISH (STATIK VA DINAMIK).

Reja:
1. Asosiy tushunchalar: ro’yxat.
2. Ma’lumotlarning abstrakt (mavhum) turlari 
3. ADT "List" operatorlari:
4. Mustaqil ishlash uchun savollar
5. Adabiyotlar 
Kalit so’zlar: Ro’yxat, ro’yxat tuzilmasi, statik va dinamik tuzilma, ko’rsatkich. 
1. Asosiy tushunchalar: ro’yxat.
Ro'yxat - bu a1, a2, ..., a n turdagi ma'lum elementlarning ketma -ketligi, bu erda n0. Ro'yxatdagi elementlar soni ro'yxatning uzunligi deb ataladi. Agar n1 bo'lsa, u holda a1
Ro'yxatdagi birinchi element va oxirgi element deb nomlanadi. Ro'yxat elementlari ro'yxatdagi mavqeiga qarab chiziqli tartibda joylashtirilgan. I = 1,2 ,, n-1 uchun ai ai + 1 dan oldin, ai i = 2,3 ,, n uchun ai-1 dan keyin keladi. Ai ro'yxatning har bir elementi i, i = 1,2 ,, n pozitsiyaga ega. Ro'yxatda ro'yxatning oxirini belgilaydigan pozitsiya mavjud - nil. Bu ro'yxatning oxirgi bandiga to'g'ri keladi.
Ko’pincha jiddiy dasturlarni tuzish jarayonida o’lchami va tuzilishini o’zgartirib turuvchi ma’lumotlardan foydalanishga to’g’ri keladi. Bu yerda dinamik massivlar qo’l kelmaydi, chunki, dastur ishlashi vaqtida qancha xotira zarur bo’lishini oldindan aytib bo’lmaydi. Masalan, matnni tahlil qilishda unda qanday so’zlar mavjud va ular matnda necha marta uchraydi, shuningdek, alifbo tartibida tartiblash masalasiga doir dastur tuzishda dinamik massivdan foydalanib bo’lmaydi.
Bunday hollarda alohida elementlari ko’rsatkichlar yordamida bog’langan maxsus ma’lumotlar tuzilmasidan foydalanish kerak. Bunday tuzilmalarning har bir elementi (tuguni) xotiraning ikkita sohasidan tashkil topadi: ma’lumotlar (info) maydoni va ko’rsatkichlar (ptr) maydoni (1-rasm). Ko’rsatkich – bu aynan ushbu turga tegishli bo’lgan boshqa bir element adresi bo’lib, bu element oldingi element bilan mantiqiy bog’langanligini anglatadi.

1-rasm. Ro’yxat tuguni (elementi)ning mantiqiy ifodasi.
C dasturlash tilida ko’rsatkichlarni tashkil etish uchun maxsus o’zgaruvchi qo’llaniladi. Bunday tuzilmalarga yangi element qo’shishda xotiraning yangi bloki belgilab olinadi va ko’rsatkich yordamida mavjud elementga bog’lanish o’rnatiladi. Oxirgi elementni belgilash uchun nol ko’rsatkich – NULL qo’llaniladi.