Ma'lumotlar tuzilmalari
O'tgan hafta pointerlarni o'rgandik. Endi ulardan foydalanib, ma'lumotni aqlli tarzda tashkil qilamiz. struct bilan bog'liq ma'lumotni guruhlash, bog'langan ro'yxat, stek va navbat: bularning hammasini jonli diagrammalarda ko'ramiz. Aynan shu yerda pointerlar nima uchun shunchalik muhimligi ochiladi.
Bu darsda nimani o'rganasiz
7.1 Tuzilma nima?
Ma'lumotlar tuzilmasi (data structure) deganda ma'lumotni qulay tartibda saqlash va boshqarish usuli tushuniladi. Biz allaqachon bittasini bilamiz: massiv. Lekin massiv hamma vazifaga mos kelmaydi.
Masalan, massivga o'rtaga element qo'shmoqchi bo'lsangiz, qolgan hammasini surishingiz kerak. Yoki massiv hajmi oldindan belgilanadi, keyin oson o'sib bo'lmaydi. Turli vazifalar uchun turli tuzilma yaxshiroq ishlaydi.
Bu darsda bir nechtasini ko'ramiz: struct (bog'liq ma'lumotni guruhlash), bog'langan ro'yxat (oson o'sadigan ro'yxat), stek va navbat (maxsus tartibli ro'yxatlar). Ularning ko'pi o'tgan haftadagi pointerlar ustiga qurilgan.
7.2 struct: ma'lumotni guruhlash
Bitta o'quvchining ismi, yoshi va bahosi bor. Ularni uchta alohida o'zgaruvchida saqlash mumkin, lekin ular bir-biriga bog'liq. struct aynan shu bog'liq maydonlarni bitta yangi turga birlashtiradi.
Maydonlarga nuqta orqali murojaat qilamiz: student.yosh. Pastda qiymatlarni kiriting va struct qanday to'lishini ko'ring:
7.3 struct massivi
struct ham oddiy tur kabi, undan massiv yasash mumkin. struct Student sinf[3]; degani: uchta o'quvchining to'liq ma'lumoti bitta massivda. Endi har bir o'quvchiga indeks bilan, har bir maydonga nuqta bilan murojaat qilamiz: sinf[1].baho.
Pastdagi jadval uchta o'quvchi struct'i. Qatorni bosib, unga qanday murojaat qilinishini ko'ring:
| # | ism | yosh | baho |
|---|
7.4 Bog'langan ro'yxat
Endi pointerlar yordamga keladi. Bog'langan ro'yxat (linked list) tugunlardan (node) tashkil topadi. Har bir tugun ikki narsani saqlaydi: o'z qiymati va keyingi tugunga pointer. Shu tarzda tugunlar zanjir kabi bog'lanadi, oxirgisi esa NULL ga ko'rsatadi (ro'yxat tugadi).
Pastdagi diagrammada har bir quticha bitta tugun: chap tomonda qiymat, o'ng tomonda keyingiga strelka. Yashil bosh birinchi tugunni ko'rsatadi:
7.5 Qo'shish va o'chirish
Bog'langan ro'yxatning kuchi shu: tugun qo'shish yoki o'chirish uchun butun massivni surish shart emas, faqat bir nechta pointerni qayta ulaymiz. Boshiga qo'shish ayniqsa tez: yangi tugun eski boshga ko'rsatadi, bosh esa yangi tugunga.
Pastda qiymat kiriting va ro'yxat bilan ishlang. Yangi tugun yashil chaqnaydi:
7.6 Massiv vs bog'langan ro'yxat
Ikkalasi ham ketma-ket ma'lumot saqlaydi, lekin har birining kuchli va kuchsiz tomoni bor. Tanlov vazifaga bog'liq:
| Xususiyat | Massiv | Bog'langan ro'yxat |
|---|---|---|
| Indeks bilan murojaat | tez (O(1)) | sekin (boshdan yurish) |
| Boshiga qo'shish | sekin (surish kerak) | tez (O(1)) |
| O'lcham | oldindan belgilangan | dinamik o'sadi |
| Xotira | ixcham | har tugun pointer uchun qo'shimcha |
Qisqacha: tez-tez indeks bilan murojaat qilsangiz, massiv yaxshi. Tez-tez boshiga qo'shib-o'chirsangiz va o'lcham noma'lum bo'lsa, bog'langan ro'yxat yaxshi.
7.7 Stek (LIFO)
Stek (stack) maxsus ro'yxat bo'lib, faqat bitta uchidan ishlaydi. Element qo'shish push, olib tashlash pop deyiladi, va ikkalasi ham tepadan bo'ladi. Qoidasi: LIFO, ya'ni oxirgi kirgan birinchi chiqadi. Bir-birining ustiga taxlangan tarelkalar kabi.
Pastda sinab ko'ring. Diqqat: pop doim eng tepadagini oladi:
Bashorat qiling
Bo'sh stekka 1, keyin 2, keyin 3 push qildik. So'ng bitta pop qilsak, nima chiqadi?
7.8 Navbat (FIFO)
Navbat (queue) stekka o'xshaydi, lekin teskari qoida bilan. Element bir uchidan qo'shiladi (enqueue), boshqa uchidan olinadi (dequeue). Qoidasi: FIFO, ya'ni birinchi kirgan birinchi chiqadi. Xuddi do'kondagi haqiqiy navbat kabi.
Pastda sinab ko'ring. Diqqat: dequeue doim oldindagini (birinchi kirganni) oladi:
7.9 Amaliy: qaysi tuzilmani tanlash?
Tuzilma tanlash vazifaning tabiatiga bog'liq. Mana kundalik misollar:
- Indeks bilan tez murojaat kerak (masalan jadval): massiv
- O'lcham noma'lum, tez-tez qo'shib-o'chirasiz: bog'langan ro'yxat
- Oxirgi amalni bekor qilish (orqaga tugmasi): stek (LIFO)
- Navbat bilan xizmat ko'rsatish (printer, xabarlar): navbat (FIFO)
- Bir nechta bog'liq maydonni birga saqlash: struct
7.10 Chuqurroq advanced
Yana ikkita kuchli tuzilma bilan qisqacha tanishamiz. Ularni chuqur o'rganish keyingi bosqichlar uchun, hozir esa umumiy tasavvur olamiz.
Hash jadval
Hash jadval (hash table) eng tez qidiruv tuzilmalaridan biri. U kalitni (masalan ism) maxsus funksiya bilan to'g'ridan-to'g'ri xotiradagi joyga aylantiradi. Shuning uchun element qidirish deyarli bir qadamda (O(1)) bo'ladi. Lug'at yoki telefon kitobchasi uchun ideal.
Daraxt
Daraxt (tree) shoxlanuvchi ierarxik tuzilma. Har bir tugun bir nechta "bola" tugunga ega bo'lishi mumkin. Fayl tizimidagi papkalar, oilaviy shajara yoki tezkor qidiruv (binary tree) uchun ishlatiladi. Bu ham, asosan, tugunlar va pointerlar ustiga qurilgan.
Atamalar lug'ati
7.11 Bilim testi
16 ta savol. Haftani yakunlash uchun kamida 11 tasiga to'g'ri javob bering.
Tabriklaymiz! 7-hafta yakunlandi
Endi siz ma'lumotni aqlli tashkil qila olasiz: struct, bog'langan ro'yxat, stek va navbat bilan tanishdingiz. Bu tuzilmalar deyarli har bir jiddiy dasturning yuragida turadi.
Keyingi hafta: Rekursiya va fayllar (o'zini chaqiruvchi funksiyalar, chaqiruv steki va fayl bilan ishlash).
Keyingi modulga o'tish