Mavzu: Ma’lumotlarning nochiziqiy tuzilmasi kirish 2 I. Ma’lumotlar tuzilmalari va algoritmlari

Jadval bu har bir elementi kalitning ma’lum qiymati bilan tavsiflanadigan va elementlaridan erkin foydalanish kalit bo’yicha amalga oshiriladigan ma’lumotlarning chiziqli tuzilmasidir. Oldin ko’rib chiqilgan barcha ma’lumotlar tuzilmalarida tuzilma elementlaridan erkin foydalanish chegaralangan, chunki faqat saqlash tuzilmasi indeks yoki ko’rsatkich vositasida erkin foydalanishni ta’minlayotgan element o’qilishi mumkin, bunda erkin foydalanish jarayonida yozuvlar maydonlarining qiymati hech qanday tahlil qilinmaydi.

Axborotni avtomatlashtirilgan qayta ishlashning ko’pgina vazifalarida muayyan alomatlarga ega obyektlar to’g’risidagi yozuvlarga murojaat qilinishi kerak. Bu holatda erkin foydalanish jarayonida yozuv (odatda, kalit) maydonining qandaydir qiymatini tahlil qilish zarur bo’ladi, buning asosida ushbu yozuvni o’qish va uni qayta ishlashga uzatishning zarurligi to’g’risidagi masala hal qilinadi. Kalit bo’yicha erkin foydalanish deyiladigan bunday erkin foydalanish ma’lumotlarning jadval tuzilmasida amalga oshiriladi.

Ketma-ket taqdim etishda jadval ketma-ket ro’yxat ko’rinishida saqlanadi. Jadvalning yozuvlari oldindan zahiraga olingan xotira blokida birin-ketin joylashadi. Bunday jadvallarni tuzish va to’ldirish oson, yangi yozuvlarni jadvalning oxiriga minimal vaqt ichida qo’shish oson. Biroq bunday jadvallarda izlash uzoq davom etadi, chunki ketma-ket ravishda jadvalning birinchisidan boshlab barcha yozuvlari ko’rib chiqiladi va ularni kalit maydonlarining qiymati tahlil qilinadi. Ko’rib chiqish kerakli yozuv topilmagunicha yoki butun jadvalni ko’rib chiqishdan so’ng kerakli yozuvning yo’qligi signali ishlab chiqilmagunicha amalga oshiriladi.

Odatda, jadval yozuvlari qandaydir tamoyil bo’yicha (masalan, kalit qiymatining oshib borishi bo’yicha yoki yozuvlar murojaatlarning soni bo’yicha) tartibga solinadi va tartibga solingan ketma-ket ro’yxat ko’rinishida saqlanadi. Bu holatda izlash maxsus usullarni ishlatish hisobiga sezilarli ravishda tezlashtirilishi mumkin. Biroq tartibga solingan ketma-ket ro’yxatni yuritish qiyinlashadi va u bilan bir qator qo’shimcha protseduralar birga keladi. Sh unday qilib, masalan, ketma-ket tartibga solingan ro’yxatga yangi jadval yozuvini kiritish uchun yangi yozuv o’z kalitining qiymatiga muvofiq ro’yxatda egallashi kerak bo’lgan o’rinni aniqlash zarur. Xotiraning tegishli uyasi bo’shatilishi kerak, buning uchun barcha yozuvlar bir uyaga ko’chiriladi, ya’ni massivning bir qismi qayta yoziladi. Tartibga solingan jadval o’zaro bog’langan ro’yxat shaklida saqlanishi mumkin.

Bunda dinamik ravishda o’zgartirilib boriladigan jadvalni yuritish qayta yozish protseduralarini bajarishni talab etmaydi. Lekin bunday jadvalda yozuvlarni ko’rsatkich tomonidan belgilangan tartibda ketma-ket ko’rib chiqibgina izlash mumkin.

Jadvallarni saqlash uchun ko’pincha ma’lumotlarni taqdim etishning aralash usulidan foydalaniladi. Bunda axborot massivini yaratishning dastlabki bosqichida har bir jadvalning yozuvlari zahiralangan xotira bloklarida ketma-ket joylashtiriladi. Jadvallar o’sib borgani sayin bloklar ham to’lib boradi. U yoki bu blok butunlay to’lib bo’lganda bu jadval uchun yangi xotira bloki ajratiladi, u ko’rsatkich orqali oldingi to’lgan blok bilan bog’lanadi. A jadvalning xotira bloki to’lganidan so’ng xotiraning bo’sh joyida A jadval uchun birinchi blok bilan ko’rsatkich orqali bog’langan yangi blok ajratiladi. V jadval ham o’sib borgani sayin u uchun ham yangi xotira bloki ajratiladi. Saqlashning bunday tuzilmasi elementlari soni oldindan noma’lum bo’lgan jadval tuzilmalarini xotirada joylashtirish uchun qulaydir.

1.2.2 Yarim statik ma’lumotlar tuzilmalari.

Stek - massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki chiqarib tashlashga 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 «oxirida keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Stekning tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu qachonki faqat yuqoridagi 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.

1.2.1 chizma. Stekni ketma-ket taqdim etganda uning oshishi va kamayishi

Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi hisoblanadi, chunki faqat stekning cho’qqisida joylashgan elementdan erkin foydalanish 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’rsatkichi (SCHK)da 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 xotira zahiraga olinadi va 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 elementning kiritilganida cho’qqi ko’rsatkichi bir birlikka ko’payadi. 1.2chizmada xotira bloki 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», chiqarib tashlash operatsiyasini esa - «itarib chiqarish» deyiladi.Shuning uchun tuzilmaning buzilishi uning xususiyatlari yo’qolishiga va oqibatda obyektning nomuvofiq ta’riflanishiga olib keladi.

SChK

An+

SChK

An+1 An

SChK

An-1		An		An-1
…..		…..		…..
A1		A1		A1
Bo’sh makon		Bo’sh makon		Bo’sh makon

vaziyatlarda stekning tuzilmasi juda qulay keladi. Asosiy ro’yxatdan o’chirilgan ixtiyoriy uya bo’sh xotira stekining cho’qqisiga qo’shiladi. Bo’sh xotira stekiga kiritilgan so’nggi uya asosiy ro’yxatning yangi yozuvini joylashtirish uchun birinchi bo’lib ishlatiladi. Bo’shagan uyalarni bo’sh xotira stekiga kiritilishini boshqaradigan algoritm ko’pincha «axlat yig’uvchi» deb ataladi.

Stekli tuzilmalar ichiga qo’yilgan kichik dasturlar va ko’p pog’onali uzilishlarni amalga oshirishda translyatorlarda, shuningdek algoritmlari rekursiv usul bilan eng yaxshi ta’riflanadigan vazifalarni echishda keng qo’llaniladi.

Navbat bu o’zgaruvchan o’lchamdagi chiziqli tuzilmadir. Elementlarni navbatdan chiqarib tashlashga bir tomondan - navbatning boshidan ruxsat beriladi. Elementlarni kiritish faqat teskari tomonga - navbatning oxiriga bo’lishi mumkin.

Bunday tuzilmadagi ma’lumotlar ular kelib tushishiga qarab «birinchi keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Adabiyotda navbat tuzilmasini FIFO (inglizcha First In, First Out) tipidagi tuzilma deyiladi. Svetoforning ochilishini kutayotgan avtomobillar navbati an’anviy misol hisoblanadi. Svetoforga birinchi bo’lib kelgan avtomobil chorrahadan birinchi bo’lib o’tib ketadi, ya’ni navbatdan chiqariladi. Oxirida kelgan va navbatning oxirida o’tib ketishni kutayotgan avtomobilb chorrahadan oxirgi bo’lib o’tadi.

Navbat elementlaridan erkin foydalanish boshlanish va tugash ko’rsatkichi bo’yicha amalga oshiriladi. Boshlanish ko’rsatkichi birinchi bo’lib chiqarib tashlanadigan yoki o’qiladigan navbat elementini ko’rsatadi. Tugash ko’rsatkichi navbatdagi so’nggi yozuvdan keyin keladigan xotiraning bo’sh uyasiga o’rnatiladi.

Yangi kelgan yozuv, ya’ni navbatning yangi elementi aynan shu uyaga joylashadi. Navbat tuzilmasini amalga oshirish uchun KOMPYUTER xotirasida ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishdan foydalaniladi.

1.2.3-chizma. Navbat

Navbatga ketma-ket taqdim etishda stekdagi kabi xotira bloki z ahiraga olinadi, uning ichida navbat oshishi va kamayishi mumkin. Har bir yangi element kiritilishi bilan tugash ko’rsatkichi birlikka o’zgaradi. Yangi elementlarni kiritish natijasida navbat tugashi ko’rsatkichi zahiraga olingan xotira blokining oxiriga etsa, u blokning boshiga ko’chiriladi. Agar tugash ko’rsatkichi boshlanish ko’rsatkichiga etib olsa, bu xotira bloki to’lganligini anglatadi.

Elementni chiqarib tashlashda boshlanish ko’rsatkichi birlikka o’zgaradi.

Agar boshlanish ko’rsatkichi tugash ko’rsatkichi bilan mos tushsa, navbat bo’sh bo’ladi. Ma’lumotlarni ketma-ket taqdim etishda zahiraga olingan xotira bloki ichidagi navbatni joylashtirish sxemasi 1.2.3-chizmada tasvirlangan. Shu yerning o’zida navbat elementlarini kiritish va chiqarib tashlashda ko’rsatkichlar qanday o’zgarishi ham ko’rsatilgan.

Navbatni bog’langan taqdim etishda xotirani oldindan zahiraga olish talab etilmaydi. Navbatni shakllantiruvchi yozuvlar ixtiyoriy bo’sh xotira uyalarida joylashadi va o’zaro ko’rsatkichlar bilan bog’lanadi. Bunday navbat cheksiz oshishi mumkin. Elementlarni kiritish va chiqarib tashlashda faqat boshlanish va tugash ko’rsatkichlarining qiymati va aloqa ko’rsatkichlarining qiymati (AS) o’zgaradi, xolos.

Navbat tuzilmasi ma’lumotlarni qayta ishlashning turli vazifalarini echishda ishlatiladi. Masalan, vaqtni taqsimlash bilan hisoblash tizimini modellash navbat tuzilmasi ishlatiladigan an’anviy vazifalardan biri hisoblanadi. Bunday tizimda ko’pchilik foydalanuvchilar bir vaqtning o’zida bitta asosiy xotiradan foydalanib yagona markaziy protsessor bilan ishlaydi. Bajarilishni kutayotgan foydalanuvchilarning dasturlari navbatni tashkil etadi. Navbatni tashkil etish va unga xizmat ko’rsatishning ishlab chiqilgan tamoyili ko’p jihatdan bunday tizim ishlashining samaradorligini belgilab beradi.

Ko’rsatkichlar ishtirok etadigan dasturlarga misollar.

Stekka element qo’shish, olib tashlash procedure udals; begin top:=top^{^}.next

end.

Stek elementlarini qo’shish procedure rasps;

{elementlarni teskari tartiblab chiqarish} begin kop:=top; while kop

<>NIL do begin writeln (kop^{^}.INF); kop:=kop^{^}.next

end;

Stekni ishlatganda quyidagi xolatlar yuzaga kelishi mumkin:

1. 
   stekning tulib ketishi, ya’ni stek xotirasida joy kolmaslik.
   
2. 
   Tulmaslik xolati stekdan u bush bulganda ukishga xarakat kilish. Navbat-ma’lumotlarning shunday tuzilmasiki, uning bir tomonida
   

element qo’shib borilsa, ikkinchi tomonidan olib tashlanadi.

Bunday tuzilmani tashkil kilish uchun LEFT va RIGHTo’zgaruvchilari ishlatiladi. Navbatga element kushilayotganda, elementlar RIGHT o’zgaruvchisining qiymatiga mos xotiraga joylashadi. SHunday kilib, RIGHT xotiraning bush joyini kursatadi. Navbatdan elementlarni tanlash navbatning keyingi elementini kursatuvchi qiymat orqali amalga oshadi. Agar LEFT qiymati

RIGHT qiymatiga teng bo’lsa, u xolda navbat bush xisoblanadi. Navbat ustida xam quyidagi amallarni bajarish mumkin:

navbatni tashkil kilish; navbatga kushish; navbatdan olib tashlash; navbatga elementlarini kurish.

Shunday qilib, navbat aylana shaklidagi ro’yxatdan iboratdir.

1.2.3 Ma’lumotlarning nochiziqiy tuzilmasi.

Ma’lumotlari AATda qayta ishlanadigan obyektlar o’rtasidagi munosabatlar ko’pincha nochiziqiy xarakterga ega bo’ladi. Bular mantiqiy shartlar bilan aniqlanadigan munosabatlar, «birning ko’pga» tipidagi munosabatlar yoki «ko’pning ko’pga» tipidagi munosabatlar bo’lishi mumkin.

«Birning ko’pga» tipidagi munosabatlar ierarik xarakterga ega va daraxtsimon tuzilma bilan aks ettiriladi. Masalan, oliy o’quv yurti o’quv bo’linmalarining tuzilmasi, shuningdek kutubxonalarda qabul qilingan Universal o’nlik tasniflash (UO’T) ierarxiya ko’rinishida berilishi mumkin. Kitob mundarijasi daraxtsimon tuzilma ko’rinishida taqdim etilishi mumkin. Daraxtsimon tuzilma algebraik ifodalarni echish algoritmlarini qurish uchun, ma’lumotlardan erkin foydalanishni tezlashtiradigan ma’lumotnomalarni yaratish uchun, saralash va izlash uchun qo’llaniladi.

«Ko’pning ko’pga» mungosabatlari ancha universal xarakterga ega va graflar tuzilmasi bilan aks ettiriladi. «Ko’pning ko’pga» munosabatlariga misol keltirib o’tamiz. Har bir oliy o’quv yurti o’z bitiruvchilarini turli korxonalarga taqsimlaydi. Bir vaqtning o’zida har bir korxona turli oliy o’quv yurtlaridan mutaxassislarni oladi. Buning natijasida tuzilgan sxema (5.1-chizma) ko’pchilik oliy o’quv yurtlarining ko’pchilik korxonalar bilan aloqasini aks ettiradi.

Umumiy ko’rinishdagi graf bir qator cho’qqi (bo’g’im)lar va cho’qqilar juftligini bog’lovchi qirralardan iborat. Agar «qirra» va «cho’qqi» tushunchalariga ma’lum bir ma’noviy mazmun kiritilsa, graflarni ma’lumotlarni taqdim etish uchun ishlatish mumkin. SHunday qilib, grafning cho’qqilariga ma’lum bir obyektlarni qarshi qo’yish mumkin, bunda qirralar obyektlar o’rtasidagi munosabatlarga mos keladi.

Ma’lumotlar bazalarining tuzilmasi bo’yicha adabiyotlarda yo’naltirilgan graf ko’rinishiga ega ma’lumotlar modeli tarmoq deb ataladi. Ixtiyoriy cho’qqilar juftligida bittadan ko’p bo’lmagan qirraga ega bo’lgan yo’naltirilgan graf ko’rinishida ifodalanadigan tarmoq oddiy tarmoq hisoblanadi. Parallelb qirralarga ega yo’naltirilgan graf ko’rinishida ifodalanadigan tarmoq murakkab tarmoq deyiladi.

Daraxt ba’zi cheklovlarga ega grafdan iborat, ya’ni bu tsikllarga ega bo’lmagan yo’naltirilgan grafdir. Daraxtning cho’qqi (bo’g’im)lari darajalar bo’yicha tashkil qilingan, ya’ni ma’lum ierarxiyaga bo’ysungan. Daraxtning ixtiyoriy bo’g’imi yuqoriroq darajadagi yagona bo’g’im - yaratuvchi bilan hamda quyi darajadagi m bo’g’imlar - yaratilgan bilan bog’langan. Eng yuqori darajada daraxtning boshida ildiz deb ataluvchi yagona bo’g’im mavjud.

Daraxt har bir shoxining oxirida joylashgan va yaratilganlarga ega bo’lmagan bo’g’imlar barglar deb ataladi. O’zaro bog’lanmagan daraxtlarning majmui o’rmon hosil qiladi.

Daraxtlarda yo’nalish albatta yaratuvchidan yaratilganga qarab bo’ladi, shuning uchun qirralarda strelkalarni ko’rsatmasa ham bo’ladi. Ildizdan qandaydir bo’g’imgacha bo’lgan yo’l uzunligi ushbu bo’g’imning darajasiga teng. Bo’g’im joylashgan daraja shu bo’g’imning qiymatini belgilaydi. Daraxt darajalarining miqdori daraxt balandligini belgilaydi.