2–mustaqil ishi

O’ZBEKISTON RESPUBLIKASI
AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI
RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI

KI-13-20 (S) GURUH TALABASINING
MA’LUMOTLAR TUZILMASI VA ALGORITMLAR
FANIDAN

^{2–MUSTAQIL ISHI}
Bajardi: Adizov.F


Qabul qildi: Ablaqulov.K
Qarshi 2022
Reja:

1. Yarimstatik ma’lumotlar tuzimasi.

   
   

2. Navbat
   

3. Stek
   

4. Dek
   

Yarimstatik ma’lumotlar tuzilmasi
Yarimstatik ma’lumotlar tuzilmasini quyidagicha tavsiflash mumkin:
- o’zgaruvchan uzunlikka ega va uni o’zgartiruvchi oddiy funksiyalariga ega;
- tuzilmaning uzunligini o’zgartirish ma’lum bir chegarada, ya’ni qandaydir bir maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin;
Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo’lsak, u holda chiziqli ro’yhat munosabati bilan bog’langan ma’lumotlar ketma-ketligi tushuniladi. Xotirada yarimstatik ma’lumotlar tuzilmasini fizik jihatdan tasvirlaydigan bo’lsak, bu xotirada slotlarning oddiy ketma-ketligidir, ya’ni har bir element xotirada navbatdagi slotlarda joylashadi. Yarimstatik MTni fizik tasvirlashning yana bir ko’rinishi bir tomonlama bog’langan ro’yhat (zanjir) ko’rinishida ifodalash mumkin, ya’ni bunda har bir navbatdagi elementning adresi joriy elementda ko’rsatiladi. Bunday tasvirlashda tuzilmaning uzunligiga
cheklanish unchalik qattiq qo’yilmaydi. Bunday tuzilmalarga – navbat, stek, dek va satrlar kiradi.


Navbat
Navbat bu FIFO (First In - First Out - "birinchi kelgan – birinchi ketadi"), shunday o’zgaruvchan uzunlikdagi ketma-ketlik, ro’yhatki, unda tuzilmaga elementlar faqat bir tomondan, ya’ni navbatning oxiridan qo’shiladi va elementlarni tuzilmadan chiqarish boshqa tomondan, ya’ni navbat boshidan amalga oshiriladi. Navbat ustida bajariladigan asosiy amallar
- yangi elementni qo„shish,
- elementni chiqarib tashlash,
- uzunligini aniqlash,
- navbatni tozalash.

Navbatni statik xotirada vektor ko’rinishida ifodalashda 2 ta parametr, ya’ni navbat boshini (navbatning 1-elementini) va oxirini (navbatning oxirgi elementini) ko’rsatuvchi ko’rsatkichlar olinadi (1-rasm).

kirish
chiqish
Navbat boshi
Navbat oxiri
R=9
Navbat tuzilmasi

Navbatga yangi element kiritilayotganda navbat oxiri ko’rsatkichi ko’rsatayotgan adresga yoziladi va shundan keyin navbat oxiri ko’rsatkichi bittaga oshiriladi. Navbatdan elementni o’chirishda navbat boshi ko’rsatkichi ko’rsatayotgan adresdagi element o’chiriladi va shundan keyin bu ko’rsatkichning qiymati bittaga oshiriladi. Navbatga elementlar kiritilganda navbat oxiri ko’rsatkichi shu navbat uchun ajratilgan xotira sohasining oxiriga yetib qoladi. Bunda navbat to’lgan hisoblanadi.

Agar navbatdan elementlar o’chiriladigan bo’lsa, navbat boshida bo’sh joy ajratiladi. Vaholanki, navbat oxiri ko’rsatkichi chegaraga yetib qolganligi sababli, navbatga yangi element kiritib bo’lmaydi. Shu sababli navbatda har safar element o’chirilganda qolgan barcha elementlar bitta oldinga surilishi kerak bo’ladi. Natijada navbat oxirida bo’sh joy ochiladi. Bu holatda navbat boshi ko’rsatkichiga xojat qolmaydi. Lekin shuni aytish kerakki, bu yondashuv bir muncha noqulay hisoblanadi. Shuning uchun har safar elementlarni surib o’tirmaslik uchun navbatni halqasimon shaklda tashkil etamiz. Ya’ni bunda xotirada navbat sohasining oxiriga yetib borilganda navbat boshiga o’tib ketiladi. Ushbu holatda navbat boshi va oxiri ko’rsatkichlari xotiradagi navbat sohasining boshini ko’rsatadi. Bu ikkala ko’rsatkichlarning tengligi navbatning bo’shligini anglatadi. Halqasimon navbatda element qo’shish amali o’chirish amalidan ko’proq bajarilsa, navbat oxiri ko’rsatkichi navbat boshi ko’rsatkichiga “yetib oladi”. Bu holat navbat to’laligini anglatadi. Halqasimon navbatda elementni o’chirish ikkala ko’rsatkich ko’rsatayotgan bitta adresda amalga oshiriladi. Bunday navbatning uzunligi boshi va oxiri ko’rsatkichlari farqi bilan aniqlanadi.
Yarimstatik ma’lumotlar tuzilmasi (stek, navbat).
Stek – massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki chiqarib tashashga imkon beradigan o’zgaruvchan o’lchamning chiziqli tuzilmasidir, ya’ni stekda ma’lumotlar hajmi dasturning bajarilishi vaqtida uyg’un ravishda oshishi va kamayishi mumkin.
Stekli tuzilmaning xususiyati shundan iboratki, elementlardan erkin foydalanish, elementlarni kiritish va chiqarib tashlash faqat tuzilmaning bir tomonidan – stek cho’qqisidan mumkin bo’ladi. Shuning uchun stekka oxirida kiritilgan element birinchi bo’lib o’qiladi yoki tanlanadi. Bunday tuzilmada axborot “oxoroda keldi, birinchi ketdi” tamoyili bo’yicha qayta ishlanadi. Stekning tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu qachonki faqat yuqoridai likobchani olish mumkin bo’lgan likobchalar to’plami misolida yaxshi tushuniladi. Avval yuqoridagi likobchani, so’ngra keyingisini olish mumkin. Likobchalar to’plamning yuqori qismiga bittadan qo’shiladi.
Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi hisoblanadi, chunki faqat stekning cho’qqisida joylashkan elementdan erkin fordalanish mumkin bo’ladi. Bu element joriy element deb ataladi. Joriy elementning joyi to’g’risidagi axborot odatda stekning bosh uyasida joylashadigan stek cho’qqisining ko’rsatkichida(SCHK) saqlanadi.
Steklarni saqlash uchun ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishidan foydalanish mumkin. Ketma-ket taqdim etishdan foydalanganda stekning eng oxirgi o’lchamini bilish zarur. Ko’zda tutiladigan ushbu eng chekka o’lcham uchun moslab zahira xotiraga olinadi, uning ichida stek oshadi va qisqaradi. Blokning birinchi uyasi stek cho’qqisining ko’rsatkichini o’z ichiga oladi. Stek bo’sh bo’lganida ko’rsatkich o’zini-o’zi ko’rsatadi. Har bir yangi element kiritilganda cho’qqi ko’rsatkichi bir birlikka ko’payadi. Yuqoridagi rasmda xotira bloke va unda joylashgan boshlang’ich stek, shuningdek kiritilgan va chiqarib tashlangan elementli steklar tasvirlangan. Stekdan erkin foydalanishni shunday qilib tashkil etish mumkinki, bunda cho’qqi ko’rsatkichining qiymati stek mavjud bo’lgan hamma vaqt davomida o’zgarmas bo’lib qoladi. Bunday holatda erkin foydalanish har doim stek uchun moslab zahiraga olingan xotira blokining bitta uyasiga amalga oshiriladi. Shu uyaga cho’qqi ko’rsatkichi o’rnatiladi, unda stekning joriy (eng yuqori) elementi saqlanadi. Element kiritilganida yoki chiqarib tashlanganida stekning barcha elementlari xotira blokining ichida mos ravishda pastga yoki yuqoriga siljiydi. Bunday holatda kiritish operatsiyasini “itarib kirgizish”, chiqarish operatsiyasini esa “itarib chiqarish” deyiladi.
Dinamik ma’lumotlar tuzilmasi – bu qandaydir bir qonuniyatga asoslanib shakllangan, lekin elementlari soni, o’zaro joylashuvi va o’zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir.
Dinamik ma’lumotlar tuzilmasi – bu qandaydir bir qonuniyatga asoslanib shakllangan, lekin elementlari soni, o’zaro joylashuvi va o’zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir.
1-rasm Dinamik ma’lumotlar tuzilmasi 1-rasmdagidek klassifikatsiyalanadi. Dasturlarda dinamik
Ma’lumotlar tuzilmasidan ko’pincha chiziqli ro’yxatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan Dinamik ma’lumotlat tuzilmasi fayllar matnli toifalashtirilgan toifalashtirilmagan Bog’lanmagan dinamik tuzilmalar Statik MT kabi klassifikasiyalanadi Bog’langan dinamik tuzilmalar chiziqli tuzilmalar Halqasimon tuzilmalar chiziqsiz tuzilmalar Bir bog’lamli navbat stek dek ro’yxat ko’p bog’lamli bir bog’lamli halqasimon ro’yxatlar ko’p bog’lamli halqasimon ro’yxatlar daraxtlar graflar Ikkilik (binar) tarmoqlanuvchi ko’p bog’lamli chiziqli ro’yxatlar 49 informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli maydon. Chiziqli ro’yxatlarda har bir element o’zidan keyingisi yoki oldingisi bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan keyingi element bilan bog’langan bo’lsa, bunday ro’yxatga bir bog‘lamli ro’yxat deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yxatlarga 2 bog‘lamli ro’yxatlar deyiladi. Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yxatga halqasimon ro’yxat deyiladi. Ro’yxatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. Ro’yxatlar ustida quyidagi amallarni bajarish mumkin. - ro’yxatni shakllantirish (birinchi elementini yaratish); - ro’yxat oxiriga yangi element qo’shish; - berilgan kalitga mos elementni o’qish; - ro’yxatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos elementdan oldin yoki keyin) - berilgan kalitga mos elementni o’chirish; - kalit bo’yicha ro’yxat elementlarini tartibga keltirish. Ro’yxatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi ko’rsatkich talab etiladi. Chiziqli bir bog’lamli ro’yxatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko’rib chiqamiz.
Ma’lumotlar tuzilmasidan ko’pincha chiziqli ro’yxatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan Dinamik ma’lumotlat tuzilmasi fayllar matnli toifalashtirilgan toifalashtirilmagan Bog’lanmagan dinamik tuzilmalar Statik MT kabi klassifikasiyalanadi Bog’langan dinamik tuzilmalar chiziqli tuzilmalar Halqasimon tuzilmalar chiziqsiz tuzilmalar Bir bog’lamli navbat stek dek ro’yxat ko’p bog’lamli bir bog’lamli halqasimon ro’yxatlar ko’p bog’lamli halqasimon ro’yxatlar daraxtlar graflar Ikkilik (binar) tarmoqlanuvchi ko’p bog’lamli chiziqli ro’yxatlar 49 informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli maydon. Chiziqli ro’yxatlarda har bir element o’zidan keyingisi yoki oldingisi bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan keyingi element bilan bog’langan bo’lsa, bunday ro’yxatga bir bog‘lamli ro’yxat deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yxatlarga 2 bog‘lamli ro’yxatlar deyiladi. Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yxatga halqasimon ro’yxat deyiladi. Ro’yxatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. Ro’yxatlar ustida quyidagi amallarni bajarish mumkin. - ro’yxatni shakllantirish (birinchi elementini yaratish); - ro’yxat oxiriga yangi element qo’shish; - berilgan kalitga mos elementni o’qish; - ro’yxatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos elementdan oldin yoki keyin) - berilgan kalitga mos elementni o’chirish; - kalit bo’yicha ro’yxat elementlarini tartibga keltirish. Ro’yxatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi ko’rsatkich talab etiladi. Chiziqli bir bog’lamli ro’yxatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko’rib chiqamiz.
Chiziqli bir tomonlama yo’nalgan ro’yxatlar.
Chiziqli bir tomonlama yo’nalgan ro’yxatlar.
Bir bog’lamli ro’yxat deb elementlarning shunday tartiblangan ketmaketligiga aytiladiki, har bir element 2 ta maydonga: informatsion maydon info va ko’rsatkich maydoni ptr ga ega bo’ladi (2-rasm). Mazkur ko’rinishdagi ro’yxat elementi ko’rsatkichining o’ziga xosligi shundan iboratki, u faqatgina ro’yxatning navbatdagi (o’zidan keyin keluvchi) elementi adresini ko’rsatadi. Bir tomonlama yo’naltirilgan ro’yxatda eng so’ngi element ko’rsatkichi bo’sh, ya’ni NULL bo’ladi. Lst – ro’yxat boshi ko’rsatkichi. U ro’yxatni yagona bir butun sifatida ifodalaydi. Ba’zan ro’yxat bo’sh bo’lishi ham mumkin, ya’ni ro’yxatda bitta ham element bo’lmasligi mumkin. Bu holda lst = NULL bo’ladi. Hozir chiziqli bir bog’lamli ro’yxat hosil qilish dasturini ko’rib chiqsak. Buning uchun biz foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak. Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga oshirish mumkin.
Halqasimon bir bog’lamli ro'yxat
Halqasimon bir bog’lamli ro'yxat
halqasimon bir bog’lamli ro'yxat oddiy bir bog’lamli ro'yxatda eng so'ngi element ko'rsatkichiga ro'yxat boshi elementi ko'rsatkichi qiymatini o'zlashtirish orqali xosil qilinadi (chizma).
Ko'pgina masalalarni hal qilishda bir tomonga yo'naltirilgan ro'yxatlardan foydalanish ma'lum bir qiyinchiliklarni keltirib chiharadi. Sababi, bir tomonga yo'naltirilgan ro'yxatda har doim ro'yxatda bosh bo'g’imdan ro'yxatning so'ngi bo'g’imi tomoniga xarakatlanish mumkin xolos. Lekin ko'pgina masalalar hal qilinayotganda ma'lum bir elementni qayta ishlash uchun undan oldin kelgan elementga murojaat qilish zarurati paydo bo'ladi. Ushbu holatda berilgan elementdan oldin kelgan elementga murojaat qilish bir bog’lamli ro'yxatda noqulay va ancha sekin amalga oshiriladi xamda uni amalga oshirish algoritmi murakkablashadi.
Ushbu noqulayliklarni yo'qotish maqsadida ro'yxatning har bir bo'g’imiga yana bitta maydon qo'shiladi. Ushbu maydon qiymati o'zidan oldin kelgan bo'g’imga murojaatdan iborat bo'ladi. Ushbu ko'rinishdagi elementlardan tashkil topgan dinamik tuzilmaga ikkitomonlama yo'naltirilgan yoki ikki bog’lamli ro'yxat deyiladi.

Halqasimon bir bog’lamli ro'yxat

Ikki bog’lamli ro'yxatning har bir elementi ikkita ko'rsatkichga ega. Bittasi oldingi elementga ko'rsatadi (teskari), ikkinchisi navbatdagi elementni ko'rsatadi (to'g’ri) (chizma).
Ikki bog’lamli ro'yxatning har bir elementi ikkita ko'rsatkichga ega. Bittasi oldingi elementga ko'rsatadi (teskari), ikkinchisi navbatdagi elementni ko'rsatadi (to'g’ri) (chizma).
Umuman olganda, ikki bog’lamli ro'yxat bu elementlari soni bir hil faqatgina teskari ketma-ketlikda yozilgan ikkita bir bog’lamli ro'yxatdir.
Halqasimon ikki bog’lamli ro'yxat
Dasturlashda ikki bog’lamli ro'yxatlarni ko'pincha quyidagicha umumlashtiriladi: so'ngi bo'g’in maydoni qiymati Rptr sifatida bosh bo'g’inga murojat olinadi, Lptr maydoni qiymati sifatida so'ngi bo'g’inga murojaat qaraladi.
1.3.4-chizma.Halqasimon ro'yxat.

1.3.4-chizma. Ikki bog’lamli ro'yxat.

Ikki bo'g’imli ro'yxat ustidagi amallar:
ro'yxat elementini yaratish; ro'yxatda elementni qidirish; ro'yxatning ko'rsatilgan joyiga elementni qo'yish; berilgan elementni ro'yxatdan o'chirish.
Steklarni bir bog’lamli ro'yxatlar yordamida amalga oshirish
Ixtiyoriy bir bog’lamli ro'yxatni stek deb qarash mumkin. Lekin, ro'yxat bir o'lchamli massiv ko'rinishida ifodalanganda, stekga nisbatan ustunlikka (afzallikka) ega bo'ladi. Sababi, stekda massiv o'lchami oldindan beriladi, ro'yxatda esa o'lcham oldindan berilmaydi.
Yangi obyekt yoki tushunchalarga aniq izoh kiritishning eng asosiy qoidalaridan biri bu uning ta’rifida sizga avvaldan ma’lum va tushunarli bo’lgan atamalardan foydalanib ta’rif berishdir. Shuning uchun, ta’riflarda asosan o’z doirasidan chetda bo’lgan so’zlarni qo’llash noto’g’ri. Boshqa tomondan, o’zo’zini izohlovchi dasturiy tushunchalar juda ko’p. Bunday ta'riflar rekursiv ta'riflar deb ataladi va asosan cheksiz to'plamlarga ta'rif berilganda foydalaniladi. Bunday to'plamga ta'rif berilganda, barcha elementlar ro'yhatini berish imkonsiz, va juda kata aniq to’plamlar uchun samarasiz. Shuning uchun, eng qulay usul bu obyekt o'sha to'plamga tegishli yoki tegishli emasligini aniqlash. Rekursiv ta'riflar ikki qismdan iborat. Birinchi qismida, to'plamning asos qilib olingan elementlari joylashtiriladi. Ikkinchi qismida, asos qilib olingan yoki avval foydalanilgan elementlardan foydalanilmagan holda yangi obyektlar yaratish uchun qoidalar beriladi. Bu qoidalarga yangi obyektlarni yaratishda qayta-qayta murojaat etiladi.