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

2. Ma’lumotlarning abstrakt (mavhum) turlari 
Ma’lumotlarning abstrakt (mavhum) turlari – bu matematik model va shu model doirasida aniqlangan turli xil operatorlardir. Abstrakt ma’lumotlar turi bilan algoritmlarni ishlab chiqish mumkin, lekin ma’lum bir dasturlash tilida algoritmlarni qo’llash uchun ma’lumotlarning abstrakt turlarini ushbu dasturlash tiliga mos ma’lumotlar turi va operatorlar yordamida ishlab chiqiladi.
Ma’lumotlarning abstrakt turlarini tavsiflash uchun o’zida o’zgaruvchilarning aniq to’plamini, mumkin bo’lgan ma’lumotlar turini mujassamlashtirgan ma’lumotlar tuzilmasidan foydalaniladi.
Algoritmlarda qo’llaniladigan ma’lumotlar tuzilmasi juda murakkab bo’lishi mumkin. Ma’lumotlarni to’g’ri taqdim etish natijasi muvaffaqiyatli dasturlash kaliti sifatida xizmat qiladi. Ma’lumotlar tuzilmasining qurilish materiali tayanch yoki tarkibli ma’lumotlar turini saqlashga mo’ljallangan yacheykalar hisoblanadi. Ma’lumotlar tuzilmasi yacheykalar majmuasiga boshqa yacheykalar vakili (ya’ni ko’rsatkichlar) sifatida nom berish orqali ishlab chiqiladi.
3. ADT "List" operatorlari:
1. INSERT (x, p, L). Bu operator x ob'ektini L ro'yxatidagi p holatiga qo'yadi, elementlarni p pozitsiyadan keyingi yuqori holatga o'tkazadi. Shunday qilib, agar L ro'yxat a1, a2, ..., an elementlaridan iborat bo'lsa, u holda bu operatorni bajargandan so'ng u a1, a2, ..., ap-1, x, ap, ..., shaklga ega bo'ladi. a .. Agar p n qiymatini oladigan bo'lsa, unda bizda a1, a2 ,, ..., an ,, x bo'ladi. Agar L ro'yxatda p pozitsiya bo'lmasa, bu operatorning bajarilish natijasi aniqlanmagan.
2. LOCATE (x, L). Bu funktsiya x ob'ektining L ro'yxatidagi o'rnini qaytaradi. Agar x ob'ekt ro'yxatda bir necha marta sodir bo'lsa, u holda ro'yxatning boshidan birinchi x ob'ektining o'rni qaytariladi. Agar x obyekti L ro'yxatda bo'lmasa, nil qaytariladi.
3. RETRIEVE (p, L). Bu funktsiya L ro'yxatidagi p holatidagi elementni qaytaradi, agar p = nil bo'lsa yoki L ro'yxatda p pozitsiya bo'lmasa, natija aniqlanmaydi.
4. DELETE (p, L). Bu operator L ro'yxatning p pozitsiyasidagi elementni olib tashlaydi. Shunday qilib, agar L ro'yxat a1, a2, ..., an elementlardan iborat bo'lsa, u holda bu operatorni bajargandan so'ng u a1, a2, ... kabi ko'rinadi. , ap-i, ap + i, ..., va. L yoki p = nil ro'yxatida p element bo'lmasa, natija aniqlanmaydi.
5. NEXT (p, L) и PREVIOUS (p, L). Bu funktsiyalar navbati bilan L ro'yxatidagi p pozitsiyasidan keyingi va oldingi pozitsiyalarni qaytaradi. Agar p L ro'yxatidagi oxirgi o'rin bo'lsa, NEXT (p, L) = nil. P = nil bo'lganda NEXT funktsiyasi aniqlanmagan. PREVIOUS funktsiyasi aniqlanmagan, agar p = 1. L ro'yxatda p bo'lmasa, ikkala funktsiya ham aniqlanmagan.
6. MAKENULL (L). Bu funktsiya L ro'yxatini bo'sh qiladi va nol pozitsiyasini qaytaradi.
7. FIRST (L). Bu funktsiya L ro'yxatidagi birinchi pozitsiyani qaytaradi. Agar ro'yxat bo'sh bo'lsa, nil pozitsiyasi qaytariladi.
8. PRINTLIST (L). L ro'yxatining elementlarini ro'yxatda paydo bo'ladigan tartibda chop etadi.
Massiv yordamida ro'yxat ko'rinishi:
Bitta bog'langan ro'yxat yordamida ro'yxat ko'rinishi:

Belgilanishi:

- ro'yxat boshiga ko'rsatgich;