Dastlab, dasturlash jarayoni dasturchiga barcha algoritmlarni to'g'ridan-to'g'ri mashina tilida yozishni ta'minladi. Ushbu yondashuv algoritmlarni ishlab chiqishda allaqachon qiyin bo'lgan vazifani yanada kuchaytirdi va ko'pincha ishni tugatilgan deb hisoblashdan oldin [tuzatish deb nomlanuvchi jarayon] topilishi va tuzatilishi kerak bo'lgan xatolarga olib keldi.
Dasturlashni osonlashtirish uchun birinchi qadam ko'rsatmalar va operandlarni to'g'ridan-to'g'ri mashinada ishlatadigan shaklda yozish uchun raqamlardan foydalanishni bekor qilish edi. Shu maqsadda dasturlarni ishlab chiqishda turli xil buyruqlarning o'n oltinchi vakili o'rniga mnemonik yozuvlardan keng foydalanila boshlandi. Masalan, registrni yuklash buyrug'ining raqamli kodi o'rniga, dasturchi endi LOD yozishi mumkin va registr tarkibini xotiraga nusxalash buyrug'i o'rniga STO mnemonik yozuvidan foydalanishi mumkin. Operandalarni yozish uchun qoidalar ishlab chiqilgan bo'lib, unga ko'ra dasturchi ba'zi bir xotira mintaqalariga tavsiflovchi nomlarni tayinlashi mumkin (ular ko'pincha identifikator deb ataladi) va ularni tegishli xotira kataklari manzillari o'rniga dastur buyruqlarini yozishda foydalanishi mumkin. Bunday identifikatorlar odatda o'zgaruvchan deb nomlanadi. Bu shuni ta'kidlaydiki, xotiraning ma'lum bir qismiga ajratilgan qiymatni o'zgartirib, biz dasturni bajarish paytida ushbu qismga berilgan identifikator bilan bog'liq qiymatni o'zgartiramiz.
Dasturda o'zgaruvchini e'lon qilishda ularning turi odatda bir vaqtning o'zida aniqlanadi. Ma'lumotlar turi aniq ma'lumotlarning talqinini ham, ular ustida bajarilishi mumkin bo'lgan operatsiyalarni ham belgilaydi. Ma'lumot turlariga Integer, Real, Character va Boolean kiradi.
Integer turi butun sonlar bo'lgan raqamli ma'lumotlarni belgilash uchun ishlatiladi. Xotirada ular ko'pincha ikkilikning qo'shimcha kodida ifodalanadi. Integer ma'lumotlari bilan umumiy arifmetik va taqqoslash operatsiyalarini bajarishingiz mumkin.
Haqiqiy turi butun sonli bo'lmagan qiymatlarni o'z ichiga oladigan raqamli ma'lumotlarni ifodalash uchun mo'ljallangan. Ular odatda xotirada ikkilik suzuvchi nuqta raqamlari sifatida saqlanadi. Haqiqiy ma'lumotlarda bajarilishi mumkin bo'lgan operatsiyalar, Integer ma'lumotlarida bajarilgan operatsiyalarga o'xshashdir. Biroq, Real tipidagi ikkita ma'lumotlar elementlarini qo'shish uchun bajarilishi kerak bo'lgan manipulyatsiyalar, Integer tipidagi o'zgaruvchilar bo'yicha amallarni bajarish uchun zarur bo'lgan manipulyatsiyalardan farq qiladi.
Character turi xotirada ASCII yoki UNICODE kodlari sifatida saqlanadigan belgilardan tashkil topgan ma'lumotlar uchun ishlatiladi. Ushbu turdagi ma'lumotlarni bir-biri bilan taqqoslash mumkin [ikkita belgidan qaysi biri alifbo tartibida ikkinchisidan oldinroq ekanligini aniqlang]; bitta belgi satrining boshqasi ekanligini tekshiring va ikkita satrni bitta uzunroq qatorga ulang, ulardan birini ikkinchisidan keyin qo'shib qo'ying [biriktirish amallari].
Mantiqiy ma'lumot faqatgina "True" va "False" qiymatlariga ega bo'lishi mumkin. Bunday ma'lumotlarning misoli ikkita raqamni taqqoslash operatsiyasining natijasidir. Mantiqiy ma'lumotlar operatsiyalari o'zgaruvchining joriy qiymati rost yoki yolg'on ekanligini tekshirishni o'z ichiga oladi.
Mashinaning asosiy xotirasi ketma-ket o'sib boradigan alohida kataklar shaklida tashkil etilgan. Biroq, bu hujayralar ko'pincha ma'lumotlarni joylashtirishning boshqa usullarini amalga oshirish uchun asos sifatida ishlatiladi. Masalan, matn odatda uzun belgilar qatori sifatida qaraladi, savdo ma'lumotlari esa raqamlarning to'rtburchaklar jadvali sifatida ko'rib chiqilishi mumkin, ularning har biri ma'lum bir xodimning ma'lum bir kun ichida qilgan bitimlari sonini aks ettiradi. Muammo shundaki, foydalanuvchiga mashinaning asosiy xotirasidagi ma'lumotlarni haqiqiy tashkil etish tafsilotlarini o'rganish o'rniga, bunday mavhum tuzilmalarni boshqarish uchun vositalar bilan ta'minlash. Kompyuterdan to'g'ri foydalanish uchun ma'lumotlar orasidagi tarkibiy aloqalar, kompyuter tarkibidagi tuzilmalarni aks ettirishning asosiy usullari va ular bilan ishlash usullari to'g'risida yaxshi ma'lumotga ega bo'lish kerak. Kompyuterdagi ma'lumotlar orasidagi bog'lanish uchun quyidagi axborot tuzilmalaridan foydalaniladi: massiv, yozuv, ro'yxat, daraxt, stek, navbat.
Massivlar
Massiv - bu bir xil turdagi bir nechta elementlarni o'z ichiga olgan tuzilish. Indekslar massiv elementlarini buyurtma qilish uchun ishlatiladi. Indekslar qavs ichida massiv nomidan keyin yoziladi. Bitta indeksli massiv bir o'lchovli, ikkitasi bilan ikki o'lchovli va boshqalar deyiladi.
Yozib olish
Yozuv - bu bir xil turdagi bo'lishi shart bo'lmagan tuzilma. Yozuvning alohida elementlari maydonlar deb nomlanadi. Maydon, o'z navbatida, rekord ham bo'lishi mumkin.
rekord talaba (
Ism,
Familiya,
Guruh
)
Ro'yxatlar
Ro'yxat - bu yozuvlar to'plami, ularning har birida maxsus maydon - ko'rsatgich mavjud. Ko'rsatkich yozuvni boshqa yozuvlar bilan bog'laydi yoki Null qiymatlarini o'z ichiga oladi, bu ko'rsatgichning qiymati aniqlanmaganligini ko'rsatadi.
Yagona bog'langan ro'yxatdagi yozuvlarning har biri bitta ko'rsatkichga ega va ular zanjirga bog'langan:
Rasmdagi o'q ko'rsatgich tarkibini bildiradi va Ma'lumot so'zi ma'lumotlarni saqlaydigan maydonlar to'plamlarini bildiradi. Ro'yxatni ikki o'lchovli massiv yordamida tashkil qilish mumkin, bu erda birinchi indeks 0 ga teng bo'lgan barcha elementlar ma'lumotlarni saqlashga mo'ljallangan va birinchi indeks 1 ga teng bo'lgan elementlar ko'rsatkichdir.
Ushbu ro'yxatda ingliz alifbosidagi harflarni o'z ichiga olgan yozuvlar alifbo tartibida joylashtirilgan. Ro'yxatdagi birinchi yozuv "A" belgisini, ikkinchisi "B" va boshqalarni o'z ichiga oladi.
Ro'yxat bilan ishlash uchun siz uchta asosiy operatsiyani bajarishingiz kerak:
Pass () - o'tish yoki ro'yxat bo'ylab harakatlanish;
Qo'shish () - ro'yxatga yangi yozuv kiritish;
Delete () - yozuvni ro'yxatdan o'chiradi.
Ro'yxat bilan ishlash bo'yicha operatsiyalardan tashqari yana ikkita o'zgaruvchi kerak:
o'zgaruvchi Head, bu ro'yxatdagi birinchi yozuv haqidagi ma'lumotlarni saqlaydi
ro'yxatdagi joriy yozuvga ishora qiluvchi Current o'zgaruvchisi
Jadval ro'yxatdagi ba'zi operatsiyalarning tavsiflarini umumlashtiradi, ularning bajarilish misoli yuqorida keltirilgan.
| Operatsion nomi | Psevdokod |
| Ro'yxat bo'yicha bir qadam pastga siljiting |
pass (joriy) funktsiyasi ( |
|
funktsiya qo'shish (joriy, yangi) { |
|
| Ro'yxatga New o'zgaruvchisi ko'rsatgan yozuvni qo'shing |
funktsiyani o'chirish (joriy) ( |
Ikki marta bog'langan ro'yxatdagi yozuvlar zanjir bilan bir-biriga bog'langan, ammo ular ikkita ko'rsatkich maydoniga ega. Ulardan biri ro'yxatdagi avvalgi bandga, ikkinchisi keyingi bandga ishora qiladi. Ushbu tuzilma ro'yxat bo'ylab ikki yo'nalishda harakat qilish imkonini beradi: oldinga va orqaga.
Dairesel ro'yxat - bu ro'yxat, uning oxirgi kiritilishi birinchisiga ishora qiladi. Ushbu ro'yxatlarda bo'sh yozuv yo'q.
Daraxt - bu har bir yozuvida bir nechta ko'rsatgich bo'lishi mumkin bo'lgan tarvaqaylab qo'yilgan ro'yxat. Daraxtdagi yozuvlar tugun deb nomlanadi. Barcha ko'rsatkichlar bo'sh bo'lgan tugunlarga barglar deyiladi. Daraxtning yuqori boshlanadigan tuguniga ildiz tuguni deyiladi. Ko'pgina muammolarda tugunlari ikkitadan ko'p bo'lmagan ko'rsatkichlarga ega bo'lgan binar [binar] daraxtlardan foydalanish kifoya.
Misol. Siz matematik ifodani (3 + 7) * (2 / (3-1)) baholashni xohlaysiz. Keling, ushbu iborani daraxt sifatida namoyish etamiz:
Ushbu daraxtning har bir tuguni quyidagi shaklning yozuvidir:
yozuv tuguni (
Ishlash
Raqam
LePointer
RightPointer
)
Daraxtning barglarida raqamlar, qolgan tugunlar amallarning belgilaridir.
Ta'riflangan daraxtni ikki o'lchovli massivda amalga oshirib, biz quyidagi rasmni olamiz:
Daraxtning qiymatini hisoblash uchun siz o'ng va chap pastki daraxtlarning qiymatlarini hisoblashingiz kerak, so'ngra ular ustida olingan amalni bajarishingiz kerak. Muammoni hal qiladigan algoritmning psevdokodi quyidagicha bo'ladi:
funktsiyani hisoblash (joriy) (
agar (M \u003d Null) bo'lsa
Natija: \u003d M;
boshqa (
R1: \u003d Hisoblang (M);
R2: \u003d Hisoblang (M);
Natija: \u003d R1 (M) R2;
}
qaytish (Natija);
}
Stek - bu birinchi bo'lib birinchi bo'lib tuzilgan ma'lumotlar tuzilishi. Stekda saqlangan ma'lumotlarga yuqori qism orqali kirish mumkin. Ma'lumotlar ketma-ket stakka suriladi, dasta ustiga surilgan element avval pastki qismida paydo bo'ladi va uni stakdan chiqarish uchun avval stakka surilgan barcha ma'lumotlarni keyinroq chiqarib qo'yish kerak.
Stek bilan ishlashda ikkita favqulodda vaziyat yuzaga kelishi mumkin: bo'sh stakadan ma'lumotlarni o'qishga urinish; stekdagi narsalar soni ruxsat etilgan maksimal songa etganida, narsalarni stakka surishga urinish.
Navbat - bu birinchi bo'lib birinchi bo'lib chiqadigan ma'lumotlar tuzilishi. Navbatda o'zgaruvchan hajmdagi ma'lumotlar mavjud. Qachonki, quyruqga ma'lumotlar qo'shiladi, olinayotganda boshdan olinadi.
Hash stol
Hashing - bu qo'shimcha tuzilmalardan foydalanmasdan yozuvlarga to'g'ridan-to'g'ri kirishni ta'minlaydigan usuldir. Jarayonni quyidagicha umumlashtirish mumkin. Ma'lumotlar saqlanadigan joy bir nechta segmentlarga bo'linadi. Yozuvlar ushbu segmentlar bo'yicha asosiy maydon qiymatini segment raqamiga o'zgartiradigan xeshlash algoritmi deb nomlangan ba'zi algoritmlarga muvofiq taqsimlanadi. Har bir yozuv ushbu jarayon bilan belgilangan segmentda saqlanadi. Shuning uchun yozuvni uning asosiy maydonining qiymatini xeshlash va tegishli segment yozuvlarini o'qish orqali olish mumkin. Shu tarzda qurilgan ma'lumotlar tuzilishi xash jadvali deb ataladi.
Masalan, ingliz alifbosidagi katta harflarni saqlash uchun xesh jadvalini tashkil qilish zarur bo'lsa, u holda belgilarning ASCII kodlari kalit sifatida tanlanishi mumkin va xeshlash algoritmi eng kam ahamiyatga ega bo'lgan beshta bitni kesib tashlaydi va ularning asosida belgini saqlash uchun massiv elementlari indeksini hosil qiladi:
Umuman olganda, xeshlash algoritmi kalit qiymatiga asoslanib, massiv chegaralarida indeks qiymatini hosil qilishi va tugmachalarni massiv elementlari bo'yicha teng ravishda taqsimlashi kerak. Oxirgi talabni bajarmaganlik bir nechta yozuvlar bitta segmentga tushadigan holatlarga olib keladi. Ushbu holatlar to'qnashuv deb ataladi.
Kompyuter xotirasida saqlanadigan ma'lumotlar nollar va bitlar (bitlar) to'plamidir. Bitlar ketma-ketlikda birlashtiriladi: baytlar, so'zlar va boshqalar. RAMning bitta bayt yoki so'zni sig'dira oladigan har bir qismiga tartib raqami (manzil) beriladi.
Ma'lumotlarning ma'nosi nimada, ular qanday belgilar bilan ifodalanadi - alifbo yoki raqamli, u yoki bu raqam nimani anglatadi - bularning barchasi ishlov berish dasturi tomonidan belgilanadi. Amaliy muammolarni hal qilish uchun zarur bo'lgan barcha ma'lumotlar bir necha xil turlarga bo'linadi va tushuncha turi ma'lumotlar manzil maydonida aks etishi bilan emas, balki ularni qayta ishlash usuli.
Har qanday ma'lumotlar ikki turdan biri sifatida tasniflanishi mumkin: asosiy (oddiy), uning shakli kompyuter arxitekturasi bilan belgilanadi yoki murakkab, foydalanuvchi tomonidan aniq muammolarni hal qilish uchun ishlab chiqilgan.
Ma'lumotlarning oddiy turlari - bu belgilar, raqamlar va boshqalar. yanada parchalanishi mantiqiy bo'lmagan elementlar. Ma'lumotlar tuzilmalari (kompleks turlari) elementar ma'lumotlardan hosil bo'ladi.
Ba'zi tuzilmalar:
· Array(cheklangan ko'lamli funktsiya) - bir xil turdagi ma'lumotlar elementlarining oddiy to'plami, bir xil turdagi ma'lumotlar guruhi bilan ishlash vositasi. Massivning bitta elementi indeks bilan belgilanadi. Massiv bir o'lchovli, ikki o'lchovli va boshqalar bo'lishi mumkin. O'zgaruvchan uzunlikdagi bir o'lchovli massivlarning turlari bu turdagi tuzilmalardir ring, stack, navbat va dek.
· Yozib olish(Dekart mahsuloti) - har xil turdagi ma'lumotlar elementlari to'plami. Oddiy holatda, yozuv doimiy elementlarning sonini o'z ichiga oladi, ular deyiladi chekkalar... Xuddi shu tuzilishdagi yozuvlar to'plami deyiladi fayl... (Fayl magnit disk kabi tashqi xotirada ma'lumotlar to'plami deb ham ataladi). Fayldan alohida yozuvlarni olish imkoniyatiga ega bo'lish uchun har bir yozuvga uning identifikatori sifatida xizmat qiladigan va alohida maydonda joylashgan o'ziga xos nom yoki raqam beriladi. Ushbu identifikator deyiladi kalit.
Massiv yoki yozuv kabi ma'lumotlar tuzilmalari kompyuter xotirasida doimiy hajmni egallaydi, shuning uchun ular statik tuzilmalar deyiladi. Statik tuzilmalarga shuningdek kiradi bir guruh.
Uzunligini o'zgartirishi mumkin bo'lgan bir qator tuzilmalar mavjud - ular deyiladi dinamik tuzilmalar... Ular orasida daraxt, ro'yxat, havola mavjud.
Lineer bo'lmagan manzil maydonini talab qiladigan narsalarni joylashtirish uchun muhim tuzilish yog'och... Daraxt sifatida ifodalanadigan ko'plab ma'lumotlar tuzilmalari mavjud. Bular, masalan, tasniflash, ierarxik, rekursiv va boshqa tuzilmalar. Daraxtlar haqida qo'shimcha ma'lumotni 1.2.1 bo'limiga qarang.
Shakl: 1.1. Ma'lumot turlarining tasnifi
1.1.2 Umumiy ma'lumotlar tuzilmalari yoki modellari
Yuqorida biz ma'lumotlar elementlari to'plami bo'lgan bir necha turdagi tuzilmalarni ko'rib chiqdik: massiv, daraxt, yozuv. Ma'lumotlarning yanada murakkab turi ushbu tuzilmalarni a'zo sifatida o'z ichiga olishi mumkin. Masalan, yozuv elementlari massiv, stek, daraxt va boshqalar bo'lishi mumkin.
Ma'lumotlarning juda xilma-xil turlari mavjud, ammo katta amaliy material bo'yicha olib borilgan tadqiqotlar shuni ko'rsatdiki, ular orasida eng keng tarqalgan bir nechtasini ajratish mumkin. Umumlashtirilgan tuzilmalar ham deyiladi ma'lumotlar modellariberi ular foydalanuvchining real ma'lumotlar haqidagi tushunchasini aks ettiradi.
Har qanday ma'lumot modeli uchta komponentni o'z ichiga olishi kerak:
1. ma'lumotlar tuzilishi - ma'lumotlar taqdimotida foydalanuvchi nuqtai nazarini tavsiflaydi.
2. ruxsat etilgan operatsiyalar to'plami ma'lumotlar strukturasida bajarilgan. Ma'lumotlar modeli, hech bo'lmaganda, ularni saqlash tuzilishini tavsiflovchi ma'lumotlarni aniqlash tili (DL) va ma'lumotlarni olish va o'zgartirish operatsiyalarini o'z ichiga olgan ma'lumotlar manipulyatsiyasi tili (DL) mavjudligini nazarda tutadi.
3. yaxlitlik cheklovlari - rasmiy tavsiflangan qoidalar asosida ma'lumotlarning predmet sohasiga muvofiqligini saqlash mexanizmi.
Tarixiy rivojlanish jarayonida ma'lumotlar bazasi ma'lumotlar bazasida quyidagi ma'lumotlar modellari ishlatilgan:
· ierarxik,
· tarmoq,
· aloqador.
So'nggi paytlarda ma'lumotlar taqdimotiga ob'ektiv yo'naltirilgan yondashuv tobora muhim ahamiyat kasb etmoqda.
1.2 Ma'lumotlarga kirish usullari
Ma'lumotlarni taqdim etish masalalari ushbu ma'lumotlar qayta ishlanadigan operatsiyalar bilan chambarchas bog'liq. Ushbu operatsiyalar quyidagilarni o'z ichiga oladi: olib kelish, o'zgartirish, yoqish va istisno ma'lumotlar. Yuqoridagi barcha operatsiyalar operatsiyaga asoslangan kirish, uni taqdim etish uslubidan qat'iy nazar ko'rib bo'lmaydi.
Qidiruv muammolarida barcha ma'lumotlar xotirada ma'lum bir identifikator bilan saqlanadi va kirish haqida gapirganda, avvalambor, tegishli ma'lumotlar to'plamlarini noyob ravishda aniqlaydigan ma'lumotlarga kirish (kalitlar deb ataladi) degan ma'noni anglatadi.
Deylik, har biri o'ziga xos kalit maydon qiymatiga ega bo'lgan bir xil yozuvlar to'plamini o'z ichiga olgan faylga kirishni tashkil qilishimiz kerak. Qidirishning eng oson usuli - fayldagi har bir yozuvni kalit qiymati qidiruv mezonlariga mos keladiganini topguncha ketma-ket skanerlash. Shubhasiz, bu usul juda samarasiz, chunki fayldagi yozuvlar kalit maydon qiymati bo'yicha tartiblanmagan. Fayldagi yozuvlarni saralash ham qo'llanilmaydi, chunki bu ko'proq vaqt talab etadi va har bir yozuv qo'shilgandan keyin bajarilishi kerak. Shuning uchun, ular quyidagicha harakat qilishadi - tugmalar, fayldagi tegishli yozuvlarga ko'rsatgichlar bilan birga, saralash va qidirish ishlarini tezda bajarishga imkon beradigan boshqa tuzilishga ko'chiriladi. Ma'lumotlarga kirishda, avval ushbu tuzilishda tegishli kalit qiymati topiladi, so'ngra u bilan saqlangan ko'rsatgichdan fayldan yozuv olinadi.
Ma'lumotlarga asosiy kirishni amalga oshiradigan ikkita usul mavjud:
· daraxtlarni qidirish usullari,
· aralashtirish usullari.
1.2.1 daraxtlarni qidirish usullari
Ta'rif: Daraxt tugunlar deb nomlangan bir yoki bir nechta elementlardan tashkil topgan cheklangan to'plamdir:
1. tugunlar o'rtasida "manba tomonidan yaratilgan" turdagi munosabat mavjud;
2. manba tugunisiz faqat bitta tugun mavjud. U ildiz deb ataladi;
3. ildizdan tashqari barcha tugunlar faqat bitta manbaga ega; har bir tugunda bir nechta bola tugunlari bo'lishi mumkin;
4. "asl hosil qilingan" munosabat faqat bitta yo'nalishda harakat qiladi, ya'ni. hech bir tugunning nasli uning ajdodiga aylana olmaydi.
Urug'langan alohida tugunlar soni (ma'lum bir ildizning kichik daraxtlari soni) uning deyiladi daraja... Nol darajali tugun barg yoki tugun tuguni deb ataladi. Berilgan daraxtning barcha tugunlari darajasining maksimal qiymati deyiladi daraxt darajasi bo'yicha.
Agar umumiy manbaga ega bo'lgan hosil bo'lgan tugunlar orasidagi daraxtda ularning tartibi muhim deb hisoblansa, u holda daraxt deyiladi tartibli... Qidiruv muammolarida deyarli har doim buyurtma qilingan daraxtlar hisobga olinadi.
Darajasi ko'pi bilan 2 ga teng bo'lgan buyurtma qilingan daraxt deyiladi ikkilik daraxt. Ikkilik daraxt, ayniqsa, RAM-da qidirishda ishlatiladi. Qidiruv algoritmi: birinchi navbatda, qidiruv argumenti ildizdagi kalit bilan taqqoslanadi. Agar argument kalitga to'g'ri keladigan bo'lsa, qidiruv tugadi, agar u mos kelmasa, u holda argument kalitdan kichik bo'lsa, qidiruv chap pastki daraxtda davom etadi va agar o'ng pastki daraxtda kalitdan ko'p bo'lsa. Darajani 1 ga oshirib, taqqoslashni takrorlang, joriy tugunni ildiz deb hisoblang.
Misol: O'quvchilarning ismlari va o'rtacha baholarini o'z ichiga olgan ro'yxati berilsin (1.1-jadvalga qarang). Kalit sifatida talabaning ismi ishlatiladi. Barcha yozuvlar belgilangan uzunlikka ega deb hisoblasak, u holda yozuv raqami ko'rsatgich sifatida ishlatilishi mumkin. Bunday holda, fayldagi yozuvning ofseti quyidagicha hisoblanadi ([yozuv_nomiri] -1) * [yozuvning_oyuni] ... Qidiruv argumenti "Petrov" bo'lsin. 1.2-rasmda ushbu ma'lumotlar bazasi uchun mumkin bo'lgan ikkilik qidiruv daraxti va qidirish yo'li ko'rsatilgan.
|
1.1-jadval |
|
|
Vasilev |
|
|
Kuznetsov |
|
|
Tixomirov |
|
Shakl: 1.2. Ikkilik daraxtlarni qidirish
Shuni e'tiborga olingki, bu erda satr o'zgaruvchilarini taqqoslash uchun quyidagi qoida qo'llaniladi: belgining qiymati alifboda uning tartib raqamiga mos keladi. Shuning uchun "I" "K" dan kam, "K" esa "C" dan kam. Agar taqqoslangan qatorlardagi joriy belgilar bir xil bo'lsa, unda quyidagi pozitsiyalardagi belgilar taqqoslanadi.
Ikkilik daraxtlar, ayniqsa, kalitlar to'plami oldindan ma'lum bo'lmaganda yoki ushbu to'plam tez o'zgarganda samarali bo'ladi. Shubhasiz, o'zgaruvchan tugmachalar to'plamiga ega bo'lish yaxshiroqdir muvozanatli daraxt.
Ta'rif: Ikkala daraxt muvozanatli deb ataladi, agar har bir tugunning chap pastki daraxtining balandligi o'ng pastki daraxtning balandligidan 1 dan oshmasa.
Tashqi xotirada ma'lumotlarni qidirishda tashqi xotiradan asosiy xotiraga ma'lumot uzatish sonini kamaytirish juda muhimdir. Shuning uchun, bu holda, ikkilik daraxtlar bilan taqqoslaganda, kuchli dallanadigan daraxtlar ko'proq foyda keltiradi. ularning balandligi kichikroq, keyin qidirish tashqi xotiraga kamroq qo'ng'iroqlarni talab qiladi. Bunday holda, B daraxtlari (B - muvozanatli)
Ta'rif: N tartibli B daraxti bu quyidagi xususiyatlarga ega 2n + 1 darajadagi kuchli dallanadigan daraxtdir:
- Ildizdan tashqari har bir tugun kamida n va ko'pi bilan 2n tugmachalarni o'z ichiga oladi.
- Ildiz kamida bitta va ko'pi bilan 2n tugmachalarni o'z ichiga oladi.
- Barcha barglar bir xil darajada joylashgan.
- Har bir oraliq tugunda ikkita ro'yxat mavjud: ko'tarilgan tugmachalar ro'yxati va mos ko'rsatkichlar ro'yxati (barg tugunlari uchun ko'rsatgichlar ro'yxati yo'q).
Bunday daraxt uchun:
· ketma-ket kirishni tashkil qilish nisbatan oson, chunki barcha barglar bir xil darajada;
· tugmachalarni qo'shganda va o'zgartirganda, barcha o'zgarishlar, qoida tariqasida, bitta tugunga cheklangan.
Shakl: 1.3 Balanslangan daraxt
IN-haqiqiy qiymatlar faqat barglarda (barg tugunlarida) joylashgan daraxt deyiladi IN +- daraxt... Bunday daraxtning ichki tugunlarida kichik daraxtlar uchun kalitlarning o'zgarishi oralig'ini belgilaydigan ajratuvchi tugmalar mavjud.
Balanslangan daraxtlarning har xil turlari, shuningdek ularni amalga oshirish usullari haqida ko'proq ma'lumotni adabiyotda o'qishingiz mumkin, ularning ro'yxati sahifaning oxirida berilgan. Shuni ta'kidlash kerakki B- daraxtlar faqat juda oddiy (bir o'lchovli) ma'lumotlar tuzilmalariga kirishni tashkil qilish uchun eng mos keladi. So'nggi yillarda, masalan, kosmik (ko'p o'lchovli) ma'lumotlar kabi murakkab tuzilmalarga kirish uchun ular tobora ko'proq foydalanmoqdalar R- daraxtlar.
R- daraxt ( R-Tree) - bu A.Guttman (Kaliforniya universiteti, Berkli) tomonidan taklif qilingan fazoviy ma'lumotlarga kirish uchun indeks tuzilmasi. R daraxti vaqti-vaqti bilan reindexlashsiz ma'lumotlarni qo'shish, o'chirish va qidirish operatsiyalarini o'zboshimchalik bilan bajarishga imkon beradi.
Ma'lumotlarni ko'rsatish uchun yozuvlar ishlatiladi, ularning har biri o'ziga xos identifikatorga ega (tuple-identifikator). Daraxtning har bir barg tugunida (bargida) shakl yozuvlari mavjud ( I, tuple-identifikator) qayerda Men - n- fazoviy ma'lumotlarga ko'rsatgichlarni o'z ichiga olgan o'lchov qutisi (shuningdek, minimal chegaralangan to'rtburchak, MBR) va har bir element tuple-identifikator mos keladigan o'lchamdagi parallelepipedning yuqori va pastki chegaralarini o'z ichiga oladi.
Tugunsiz tugmalar shakl yozuvlarini o'z ichiga oladi (I, childnode-pointer) qayerda Men barcha tugunlarning MBR uchun minimal chegarasi. Childnode-ko'rsatgich olingan tugunlarga ko'rsatgich.
Ruxsat bering M va m <= M/2 navbati bilan, tugunga joylashtirilishi mumkin bo'lgan elementlarning maksimal va minimal soni. Keyin R-daraxtining xususiyatlarini quyidagicha ta'riflash mumkin:
· R-Tree - bu juda muvozanatli daraxt, ya'ni. barcha barglar bir xil darajada.
· Ildiz tugunida kamida ikkita bola bor.
· Har bir element uchun (I, childnode-pointer) terminal bo'lmagan tugunda Men bu mumkin bo'lgan eng kichik parallelepiped, ya'ni. barcha tugunlarning parallelepipedlarini o'z ichiga oladi.
· Har bir tugun (varaq) dan quyidagini o'z ichiga oladi m oldin M indeks yozuvlari.
· Har bir indeks uchun (I, tuple-identifikator) tugun tugmachasida Men o'z ichiga olgan parallelepipeddir n- o'lchovli ma'lumotlar ob'ekti ko'rsatildi tuple-identifikator .
1.2.2 hashing
Ushbu usul barcha tugmalar to'plami oldindan ma'lum bo'lganda ishlatiladi va ishlov berish muddati davomida RAMda saqlanishi mumkin. Bunday holda, xash funktsiyasi (inglizcha "to hash" so'zidan - kesish, maydalash) deb nomlangan tugmalar to'plamini ko'rsatgichlar to'plamiga noyob ravishda tushiradigan maxsus funktsiya tuziladi. Bunday funktsiyaga ega bo'lgan holda, qidiruv tugmachasi orqali fayldagi yozuvning manzilini hisoblash mumkin. Umuman olganda, yozuvning manzilini aniqlash uchun ishlatiladigan asosiy ma'lumotlar hash jadvali deb nomlangan jadvalda tartibga solingan.
Agar tugmachalar to'plami oldindan noma'lum bo'lsa yoki juda katta bo'lsa, unda yozuvning manzilini uning kaliti bo'yicha aniq hisoblash g'oyasidan voz kechiladi va xash funktsiyasi shunchaki tugmalar to'plamini manzillar to'plamiga tarqatadigan funktsiya sifatida qaraladi.
Izoh: Ma'lumotlar bilan ishlashni tashkil etuvchi ijrochi sifatida ma'lumotlar strukturasining umumiy tushunchasi berilgan: saqlash, qo'shish va o'chirish, qidirish va hk. Ba'zi tuzilmalarni boshqalarga asoslangan holda amalga oshirish, xususan, massiv asosida amalga oshirish ko'rib chiqiladi. Ma'lumotlarning eng sodda tuzilmalaridan eng muhimi: navbat va stek, shuningdek ularni doimiy ravishda massiv asosida amalga oshirish. Dasturlashda stekdan foydalanishning ko'plab misollari keltirilgan. Formulaning teskari Polsha yozuvi (argumentlardan keyingi operatsiya belgisi) va uni stak mashinasida hisoblash usuli ko'rib chiqilgan. PostScript grafik tili teskari Polsha yozuvlaridan foydalanish misoli sifatida qaraladi. Material C tilida amalga oshirilgan "Stack Calculator" loyihasi bilan tasvirlangan.
Ma'lumotlar tuzilmalari
"Algoritmlar + ma'lumotlar tuzilmalari \u003d dasturlar". Bu shveytsariyalik mashhur dasturlash mutaxassisi, Paskal, Modula-2, Oberon tillari muallifi Niklaus Virtning kitobi sarlavhasi. Dasturlashning tizimli yondashuvini ishlab chiqish Wirt nomi bilan bog'liq. N.Virt shuningdek, ajoyib o'qituvchi va klassik darsliklarning muallifi sifatida tanilgan.
N.Virt ta'kidlagan dasturning ikkala komponenti ham bir xil ahamiyatga ega. Nomukammal algoritmgina emas, balki ma'lumotlar bilan ishlashni muvaffaqiyatsiz tashkil qilish ham dasturni o'nlab, ba'zan esa millionlab marta sekinlashtirishi mumkin. Boshqa tomondan, egalik qilish dasturlash nazariyasi va uni amaliyotda muntazam ravishda qo'llash qobiliyati tezda samarali va shu bilan birga estetik jihatdan chiroyli dasturlarni ishlab chiqishga imkon beradi.
Ma'lumotlar tuzilishi haqida umumiy tushuncha
Ma'lumotlar tarkibi ma'lumotlar bilan ishlashni, shu jumladan saqlash, qo'shish va yo'q qilish, o'zgartirish, qidirish va boshqalarni tashkil etuvchi ijrochi. Ma'lumotlar tarkibi ularga kirishning ma'lum tartibini saqlaydi. Ma'lumotlar tuzilishini omborxona yoki kutubxona turi deb qarash mumkin. Ma'lumotlar tuzilishini tavsiflashda siz buning uchun mumkin bo'lgan harakatlar to'plamini ro'yxatlashingiz va har bir harakat natijasini aniq ta'riflashingiz kerak. Biz bunday harakatlarni chaqiramiz qoidalar... Dasturiy nuqtai nazardan ma'lumotlarning tuzilishini retseptlash tizimi umumiy o'zgaruvchilar ustida ishlaydigan funktsiyalar to'plamiga mos keladi.
Ma'lumotlar tuzilmalari eng qulay tarzda ob'ektga yo'naltirilgan tillarda amalga oshiriladi. Ularda sinf ma'lumotlar tuzilishiga mos keladi, ma'lumotlarning o'zi sinfning a'zo o'zgaruvchilarida saqlanadi (yoki ma'lumotlarga a'zo o'zgaruvchilar orqali kirish mumkin), sinf usullari to'plami retsept tizimiga mos keladi. Qoidaga ko'ra, ob'ektga yo'naltirilgan tillarda ma'lumotlar tuzilmalari standart sinflar kutubxonasi sifatida amalga oshiriladi: bular shunday ataladi konteyner darslari Standart sinf kutubxonasiga kiritilgan C ++ tillari STL, yoki kutubxonadan turli xil ma'lumotlar tuzilmalarini amalga oshiradigan sinflar Java Developer Kit Java tili.
Biroq, ma'lumotlar tuzilmalari Fortran yoki C kabi an'anaviy dasturlash tillarida bir xil darajada muvaffaqiyatli amalga oshirilishi mumkin. Bunday holda, ob'ektga yo'naltirilgan dasturlash uslubiga rioya qilish kerak: ma'lumotlar tuzilishi bilan ishlaydigan funktsiyalar to'plamini aniq ajratib ko'rsatish va ma'lumotlarga kirishni faqat ushbu funktsiyalar to'plami bilan cheklash. Ma'lumotlarning o'zi statik (global emas) o'zgaruvchilar sifatida amalga oshiriladi. C tilida dasturlashda ma'lumotlar tuzilishi ikkita manba faylga mos keladi:
- ma'lumotlar tuzilishi interfeysini tavsiflovchi sarlavha yoki h-fayl, ya'ni. ma'lumotlar tuzilishini retseptlash tizimiga mos keladigan funktsiya prototiplari to'plami;
- dastur fayli yoki ma'lumotlarni saqlaydigan va ularga kiradigan statik o'zgaruvchilarni belgilaydigan, shuningdek ma'lumotlar tuzilishi retsept tizimiga mos keladigan funktsiyalarni bajaradigan C-fayl.
Ma'lumotlar tarkibi odatda oddiyroq asosida amalga oshiriladi asosiy tuzilishilgari amalga oshirilgan yoki massiv va oddiy o'zgaruvchilar to'plamiga asoslangan. Ma'lumotlar strukturasini mantiqiy nuqtai nazardan tavsiflash va uning bajarilishini tavsiflash o'rtasida aniq farq qilish kerak. Turli xil dasturlar bo'lishi mumkin, ammo mantiqiy nuqtai nazardan (ya'ni tashqi foydalanuvchi nuqtai nazaridan) ularning barchasi tengdir va ular faqat retseptni bajarish tezligida farq qiladi.
Tuzilmalar va ma'lumotlar turlari. Massivlar, daraxtlar, ro'yxatlar, grafikalar. Ma'lumotlar bilan ishlash.
Kompyuter xotirasida saqlanadigan ma'lumotlar nollar va bitlar (bitlar) to'plamidir. Bitlar ketma-ketlikda birlashtiriladi: baytlar, so'zlar va boshqalar. RAMning bitta bayt yoki so'zni ushlab turadigan har bir qismiga tartib raqami (manzil) beriladi.
Ma'lumotlarning ma'nosi nima, ular qanday belgilar bilan ifodalanadi - alifbo yoki raqamli, bu yoki boshqa raqam nimani anglatadi - bularning barchasi ishlov berish dasturi tomonidan belgilanadi. Amaliy masalalarni echish uchun zarur bo'lgan barcha ma'lumotlar bir nechta turlarga bo'linadi va tip tushunchasi nafaqat manzillar maydonida ma'lumotlarni taqdim etish bilan, balki ularni qayta ishlash usuli bilan ham bog'liqdir.
Har qanday ma'lumotni ikki turdan biriga kiritish mumkin: asosiy (oddiy), uning shakli kompyuter arxitekturasi bilan belgilanadi yoki murakkab, foydalanuvchi tomonidan muayyan muammolarni hal qilish uchun ishlab chiqilgan.
Ma'lumotlarning oddiy turlari bu belgilar, raqamlar va boshqalar. yanada parchalanishi mantiqiy bo'lmagan elementlar. Ma'lumotlarning strukturalari (murakkab turlari) elementar ma'lumotlardan hosil bo'ladi.
Ba'zi tuzilmalar:
Array (cheklangan ko'lamli funktsiya) - bu bir xil turdagi ma'lumotlar elementlarining oddiy to'plami, bir xil turdagi ma'lumotlar guruhi bilan ishlash vositasi. Massivning bitta elementi indeks bilan belgilanadi. Massiv bir o'lchovli, ikki o'lchovli va boshqalar bo'lishi mumkin. Ring, stack, queue va deque - bu bir o'lchovli o'zgaruvchan uzunlikdagi massivlarning turlari.
Agar massiv doimo xotiraning tutashgan qismini egallasa, u holda ro'yxat dinamik ma'lumotlar strukturasining eng oddiy namunasidir. Ma'lumotlarning dinamik tuzilmalarida ob'ekt har xil xotira sohalarida joylashgan bo'lib, ularning soni va tarkibi ish paytida o'zgarishi mumkin. Bunday ob'ektning birligi uning qismlarini sinf tavsifida birlashtirib saqlanadi.
Eng oddiy chiziqli ro'yxat - bu elementlarning chiziqli ketma-ketligi. Ularning har biri uchun, oxirgisidan tashqari, keyingi element mavjud va har biri uchun, birinchisidan tashqari - oldingi. Ro'yxat an'anaviy ravishda elementlarning ketma-ketligi sifatida tasvirlangan bo'lib, ularning har biri keyingi va / yoki oldingi element bilan bog'lanishni (ko'rsatgichni) o'z ichiga oladi, ammo shuni ta'kidlash kerakki, jismonan ro'yxat elementlarini namoyish qilishda biron bir havola bo'lmasligi mumkin.
Ro'yxatdagi odatdagi operatsiyalar to'plamiga uning elementlarini qo'shish, olib tashlash va qidirish, ro'yxat uzunligini hisoblash va ro'yxatni elementlarni ketma-ket qayta ishlash (takrorlash) kiradi.
Massivlar singari, ko'plab sinf kutubxonalari ro'yxatlarni tavsiflash va boshqarish qobiliyatini o'z ichiga oladi (masalan, MFC sinf kutubxonasining CListi). Shunga qaramay, tez-tez o'zingizning ma'lumotlar tuzilmalaringizni hal etilayotgan muammo uchun qulayroq operatsiyalarni o'z ichiga olgan, standartlardan sodda (va shuning uchun ham samaraliroq) yoki o'ziga xos xususiyatlarga ega bo'lgan ro'yxatlar shaklida tavsiflash zarur bo'ladi (masalan, buyurtma qilingan ro'yxatlar) ).
Odatda, ro'yxatni tavsiflashda ro'yxatning har bir elementining taqdimoti alohida sinf sifatida tavsiflanadi. Ushbu sinf o'zining atributi sifatida keyingi va / yoki oldingi elementga havolaga ega.
Yozuv (dekart mahsuloti) - har xil turdagi ma'lumotlar elementlari to'plami. Oddiy holatda, yozuvlar doimiy sonli elementlarni o'z ichiga oladi, ular maydonlar deb nomlanadi. Xuddi shu tuzilishdagi yozuvlar to'plami fayl deb ataladi. (Fayl magnit disk kabi tashqi xotirada ma'lumotlar to'plami deb ham ataladi). Fayldan alohida yozuvlarni ajratib olish imkoniyatiga ega bo'lish uchun har bir yozuvga uning identifikatori sifatida xizmat qiladigan va alohida maydonda joylashgan o'ziga xos nom yoki raqam beriladi. Ushbu identifikator kalit deb nomlanadi.
Massiv yoki yozuv kabi ma'lumotlar tuzilmalari kompyuter xotirasida doimiy hajmni egallaydi, shuning uchun ular statik tuzilmalar deyiladi. Bundan tashqari, ko'plab statik tuzilmalar mavjud.
Uzunligini o'zgartirishi mumkin bo'lgan bir qator tuzilmalar mavjud - bu dinamik strukturalar. Ular orasida daraxt, ro'yxat, havola mavjud.
Elementlarni joylashtirish uchun chiziqli bo'lmagan manzil maydonini talab qiladigan muhim tuzilish daraxtdir. Daraxt sifatida ifodalanadigan ko'plab ma'lumotlar tuzilmalari mavjud. Bular, masalan, tasniflash, ierarxik, rekursiv va boshqa tuzilmalar.
Umumlashtirilgan tuzilmalar yoki ma'lumotlar modellari.
Yuqorida biz ma'lumotlar elementlari to'plami bo'lgan bir necha turdagi tuzilmalarni ko'rib chiqdik: massiv, daraxt, yozuv. Ma'lumotlarning yanada murakkab turi ushbu tuzilmalarni a'zo sifatida o'z ichiga olishi mumkin. Masalan, yozuv elementlari qator, stek, daraxt va boshqalar bo'lishi mumkin.
Ma'lumotlarning murakkab turlari juda xilma-xildir, ammo katta amaliy material bo'yicha olib borilgan tadqiqotlar shuni ko'rsatdiki, ular orasida eng keng tarqalgan bir nechtasini ajratish mumkin. Umumiy tuzilmalar ma'lumotlar modellari deb ham ataladi, chunki ular foydalanuvchining real ma'lumotlar haqidagi tushunchasini aks ettiradi.
Har qanday ma'lumot modeli uchta komponentni o'z ichiga olishi kerak:
Ma'lumotlar tarkibi - ma'lumotlar taqdimotida foydalanuvchi nuqtai nazarini tavsiflaydi.
Ma'lumotlar tuzilmasida bajarilgan amaldagi operatsiyalar to'plami. Ma'lumotlar modeli, hech bo'lmaganda, ularni saqlash tuzilishini tavsiflovchi ma'lumotlar ta'rifi tili (DLS) va ma'lumotlarni chiqarib olish va o'zgartirish operatsiyalarini o'z ichiga olgan ma'lumotlar manipulyatsiyasi tili (DML) mavjudligini nazarda tutadi.
Butunlikni cheklash - bu rasmiy ravishda tavsiflangan qoidalar asosida domen ma'lumotlariga muvofiqlikni saqlash mexanizmi.
Tarixiy rivojlanish jarayonida ma'lumotlar bazasi ma'lumotlar bazasida quyidagi ma'lumotlar modellari ishlatilgan:
Ierarxik - bu model bitta asosiy ob'ektga, qolganlari - bo'ysunuvchilar - ierarxiyaning turli darajalarida joylashgan ob'ektlarga ega. Ob'ekt munosabatlari bitta ildiz ob'ekti bo'lgan ierarxik daraxtni hosil qiladi.
Tarmoqda - Ma'lumotlarni tartibga solishda tarmoq yondoshuvi bu ierarxikaning kengaytmasi. Ierarxik tuzilmalarda bola yozuvida aynan bitta ajdod bo'lishi kerak; tarmoq ma'lumotlar tuzilmasida nasl istalgan miqdordagi ajdodlarga ega bo'lishi mumkin.
Tarmoq ma'lumotlari modelida har qanday ob'ekt ham asosiy, ham bo'ysunuvchi bo'lishi mumkin va boshqa ob'ektlar bilan istalgan miqdordagi munosabatlarni shakllantirishda ishtirok etishi mumkin.
Relyatsion - relyatsion modelda ma'lumotlar jadval tuzilishini tashkil etuvchi to'plamlarga bo'linadi. Ushbu jadval tuzilishi maydonlar deb nomlangan alohida ma'lumotlar elementlaridan iborat. Maydonlarning bitta to'plami yoki guruhi yozuv sifatida tanilgan.
Ma'lumotlarga kirish usullari.
Ma'lumotlarni taqdim etish masalalari ushbu ma'lumotlar qayta ishlanadigan operatsiyalar bilan chambarchas bog'liq. Ushbu operatsiyalarga ma'lumotlarni olish, o'zgartirish, shu jumladan ma'lumotlarni kiritish kiradi. Yuqoridagi barcha operatsiyalar taqdim etish usulidan qat'i nazar ko'rib chiqilmaydigan kirish operatsiyasiga asoslangan.
Qidiruv muammolarida barcha ma'lumotlar xotirada ma'lum bir identifikatsiyalash bilan saqlanadi va kirish haqida gapirganda, ular, avvalambor, ular bilan bog'liq ma'lumotlar to'plamlarini noyob ravishda aniqlaydigan ma'lumotlarga (kalitlar deb nomlangan) kirishni anglatadi.
Aytaylik, har biri o'ziga xos kalit maydon qiymatiga ega bo'lgan bir xil yozuvlar to'plamini o'z ichiga olgan faylga kirishni tashkil qilishimiz kerak. Qidiruvning eng oson usuli - fayldagi har bir yozuvni kalit qiymati qidiruv mezonlariga mos keladiganini topguncha ketma-ket skanerlash. Shubhasiz, bu usul juda samarasiz, chunki fayldagi yozuvlar kalit maydon qiymati bo'yicha tartiblanmagan. Fayldagi yozuvlarni saralash ham qo'llanilmaydi, chunki bu ko'proq vaqt talab etadi va har bir yozuv qo'shilgandan keyin bajarilishi kerak. Shuning uchun, ular quyidagicha harakat qilishadi - tugmalar, fayldagi tegishli yozuvlarga ko'rsatgichlar bilan birga, boshqa tuzilishga ko'chiriladi, bu esa saralash va qidirish ishlarini tezda bajarishga imkon beradi. Ma'lumotlarga kirishda, avval ushbu tuzilishda tegishli kalit qiymati topiladi, so'ngra u bilan saqlangan ko'rsatgichdan fayldan yozuv olinadi.
Ma'lumotlarning asosiy kirishini amalga oshiradigan ikkita usul mavjud:
Daraxtlarni qidirish usullari,
Hash usullari.
Grafik nazariyasi hisoblash matematikasining muhim qismidir. Ushbu nazariya yordamida turli sohalardagi ko'plab masalalar echiladi. Grafik ko'plab tepaliklardan va tepaliklarni bog'laydigan ko'plab qirralardan iborat. Grafik nazariyasi nuqtai nazaridan, vertikal va qirralarga qanday ma'no qo'yilishi muhim emas. Vertices aholi punktlari bo'lishi mumkin va ularni bog'laydigan yo'lning chekkalari yoki tepaliklari pastki dasturlar bo'lib, vertikallar qirralar bilan bog'langan, pastki dasturlarning o'zaro ta'sirini anglatadi. Ko'pincha grafadagi yoy yo'nalishi muhim ahamiyatga ega. Agar chekka yo'nalishga ega bo'lsa, u yoy, qirralari yo'naltirilgan grafik esa digraf deb ataladi.
Keling, grafik nazariyasining yanada rasmiy ravishda asosiy ta'rifini beraylik. G grafik - tartiblangan juftlik (V, E), bu erda V - tepaliklarning bo'sh bo'lmagan to'plami, E - V to'plam elementlari juftlari to'plami va V dan elementlarning juftligi chekka deb ataladi. V dan tartiblangan juft element yoy deyiladi. Agar E dagi barcha juftliklar tartiblangan bo'lsa, unda grafik yo'naltirilgan deb nomlanadi.
Yo'l - bu digrafdagi vertikallarning har qanday ketma-ketligi, bu ketma-ketlikda b vertex a vertikalidan keyin faqat a dan b gacha keladigan kamon bo'lsa, ergashishi mumkin. Xuddi shunday, siz yoylardan iborat yo'lni belgilashingiz mumkin. Bitta tepadan boshlanib, bitta tepada tugaydigan yo'l tsikl deb ataladi. Tsikllar bo'lmagan grafik asiklik deb nomlanadi.
Grafikning muhim maxsus holati daraxtdir.
Ta'rif: Daraxt tugunlar deb nomlangan bir yoki bir nechta elementlardan tashkil topgan cheklangan to'plamdir:
Tugunlar o'rtasida ota-ona va bola munosabatlari mavjud;
Manbasi bo'lmagan bitta tugun mavjud. U ildiz deb ataladi;
Ildizdan tashqari barcha tugunlar faqat bitta manbaga ega; har bir tugunda bir nechta bola bo'lishi mumkin;
Kelib chiqadigan munosabatlar faqat bitta yo'nalishda ishlaydi, ya'ni. hech bir tugunning nasli uning ajdodiga aylana olmaydi.
Urug'langan alohida tugunlarning soni (ma'lum bir ildizning kichik daraxtlari soni) uning darajasi deb ataladi. Nol darajaga ega bo'lgan tugun barg yoki so'nggi tugun deb ataladi. Berilgan daraxtdagi barcha tugunlar darajasining maksimal qiymati daraxtning darajasi deb ataladi.
Agar umumiy boshlang'ichga ega bo'lgan tugunlar orasidagi daraxtda ularning tartibi muhim deb hisoblansa, u holda daraxt buyurtma qilingan deb nomlanadi. Qidiruv muammolarida deyarli har doim buyurtma qilingan daraxtlar hisobga olinadi.
Darajasi ko'pi bilan 2 ga teng bo'lgan tartiblangan daraxt binar daraxt deyiladi. Ikkilik daraxt, ayniqsa, RAM-da qidirishda ishlatiladi. Qidiruv algoritmi: birinchi navbatda, qidiruv argumenti ildizdagi kalit bilan taqqoslanadi. Agar argument kalitga to'g'ri keladigan bo'lsa, qidiruv tugadi, agar u mos kelmasa, u holda argument kalitdan kichik bo'lsa, qidiruv chap pastki daraxtda davom etadi va agar o'ng pastki daraxtda kalitdan ko'p bo'lsa. Darajani 1 ga oshirib, taqqoslash takrorlanadi, joriy tugunni ildiz deb hisoblaydi.
Ikkilik daraxtlar, ayniqsa, kalitlar to'plami oldindan ma'lum bo'lmaganda yoki ushbu to'plam tez o'zgarganda samarali bo'ladi. Shubhasiz, o'zgaruvchan kalitlar to'plami bilan muvozanatli daraxtga ega bo'lish yaxshiroqdir.
Ta'rif: Ikkilik daraxt muvozanatli deyiladi, agar har bir tugunning chap pastki daraxtining balandligi o'ng pastki daraxtning balandligidan 1 dan oshmasa.
Hashing.
Ushbu usul barcha tugmalar to'plami oldindan ma'lum bo'lganda ishlatiladi va ishlov berish muddati davomida RAMda saqlanishi mumkin. Bunday holda, xash funktsiyasi (inglizcha "to hash" - kesish, maydalash) deb nomlangan tugmachalar to'plamini ko'rsatgichlar to'plamiga noyob ravishda tushiradigan maxsus funktsiya tuziladi. Bunday funktsiyaga ega bo'lgan holda, berilgan qidirish tugmachasi bo'yicha fayldagi yozuvning manzilini hisoblash mumkin. Umuman olganda, yozuvning manzilini aniqlash uchun ishlatiladigan asosiy ma'lumotlar hash jadvali deb nomlangan jadvalda tartibga solingan.
Agar tugmachalar to'plami oldindan noma'lum bo'lsa yoki juda katta bo'lsa, unda yozuvning manzilini uning kaliti bo'yicha aniq hisoblash g'oyasidan voz kechiladi va xash funktsiyasi shunchaki tugmalar to'plamini manzillar to'plamiga tarqatadigan funktsiya sifatida qaraladi.
Ma'lumotlar tarkibi - bu ko'plab o'xshash yoki mantiqiy bog'liq ma'lumotlarni hisoblash qurilmalarida saqlash va qayta ishlashga imkon beruvchi dasturiy ta'minot birligi. Agar siz ma'lumotni qo'shishni, topishni, o'zgartirishni yoki o'chirishni xohlasangiz, ramka uning interfeysini tashkil etadigan ma'lum bir variant to'plamini taqdim etadi.
Ma'lumotlar tarkibi tushunchasi nimani o'z ichiga oladi?
Ushbu atama bir nechta yaqin, ammo baribir o'ziga xos ma'nolarga ega bo'lishi mumkin. Bu:
- mavhum turi;
- ma'lumotlarning mavhum turini amalga oshirish;
- ma'lumotlar turidagi misol, masalan ma'lum bir ro'yxat.
Agar biz funktsional dasturlash kontekstida ma'lumotlar tuzilishi haqida gapiradigan bo'lsak, unda bu o'zgarish paytida saqlanadigan maxsus birlik. Buni norasmiy ravishda bitta tuzilma sifatida aytish mumkin, ammo turli xil versiyalari bo'lishi mumkin.
Tuzilishi nimadan iborat?
U ma'lum bir dasturlash tilidagi havolalar va ulardagi operatsiyalar yordamida tuziladi. Aytish kerakki, har xil turdagi tuzilmalar turli xil dasturlarni amalga oshirish uchun mos keladi, ba'zilari, masalan, juda tor ixtisosga ega va faqat belgilangan vazifalarni ishlab chiqarish uchun mos keladi.
Agar siz B daraxtlarini olsangiz, ular odatda ma'lumotlar bazalarini yaratish uchun mos keladi va faqat ular uchun. Xuddi shu soatda xash jadvallar hanuzgacha amalda turli xil lug'atlarni yaratish, masalan, ma'lumotlar bazalarini shakllantirish uchun emas, balki shaxsiy kompyuterlarning Internet-manzillarida domen nomlarini namoyish qilishda keng qo'llanilmoqda.
U yoki bu dasturiy ta'minotni ishlab chiqish jarayonida dasturlarning amalga oshirilishining murakkabligi va funktsionalligi to'g'ridan-to'g'ri ma'lumotlar tuzilmalaridan to'g'ri foydalanishga bog'liq. Narsalarni bunday tushunishi dastur arxitekturasida etakchi mavqega algoritmlar emas, tuzilmalar joylashtirilgan rasmiy ishlab chiqish usullari va dasturlash tillarini rivojlantirishga turtki berdi.
Shunisi e'tiborga loyiqki, ko'plab dasturlash tillari modullikning belgilangan turiga ega bo'lib, bu ma'lumotlar tuzilmalarini turli xil ilovalarda xavfsiz ishlatishga imkon beradi. Java, C # va C ++ - bu eng yaxshi misollar. Endi ishlatiladigan ma'lumotlarning klassik tuzilishi dasturlash tillarining standart kutubxonalarida taqdim etiladi yoki to'g'ridan-to'g'ri tilning o'zida o'rnatiladi. Masalan, xesh jadvallar Lua, Python, Perl, Ruby, Tcl va boshqalarga o'rnatilgan. C ++ standart andozalari kutubxonasi keng qo'llaniladi.
Funktsional va imperativ dasturlashdagi strukturani taqqoslash
Shuni ta'kidlash kerakki, kamida ikkita sababga ko'ra funktsional tillar uchun tuzilmalarni imperativ tillarga qaraganda qiyinroq tuzish kerak:
- Darhaqiqat, barcha tuzilmalar amalda ko'pincha aniq funktsional uslubda ishlatilmaydigan topshiriqlardan foydalanadilar.
- Funktsional tuzilmalar moslashuvchan tizimlardir. Imperativ dasturlashda eski versiyalar shunchaki yangilari bilan almashtiriladi, ammo funktsional dasturlashda hamma narsa xuddi shunday ishlaydi. Boshqacha qilib aytganda, imperativ dasturlashda tuzilmalar vaqtinchalik, ammo funktsional dasturlashda ular doimiydir.
Tuzilishi nimani o'z ichiga oladi?
Ko'pincha, dasturlar ishlaydigan ma'lumotlar ishlatilgan dasturlash tiliga o'rnatilgan massivlarda, doimiy yoki o'zgaruvchan uzunlikda saqlanadi. Massiv - bu ma'lumotga ega bo'lgan eng sodda tuzilma, ammo ba'zi bir vazifalar ba'zi operatsiyalarning yuqori samaradorligini talab qiladi, shuning uchun boshqa tuzilmalardan foydalaniladi (murakkabroq).
Eng oddiy massiv indekslari va ularning o'zgarishi bo'yicha o'rnatilgan komponentlarga tez-tez kirish uchun mos keladi va elementlarni o'rtadan olib tashlash O (N) O (N) dir. Muayyan muammolarni hal qilish uchun narsalarni olib tashlashingiz kerak bo'lsa, boshqa tuzilmani ishlatishingiz kerak bo'ladi. Masalan, ikkilik daraxt (std :: set) buni O (logN) O (log\u2061N) da bajarishga imkon beradi, lekin u indekslar bilan ishlashni qo'llab-quvvatlamaydi, faqat elementlar orqali takrorlanadi va ularni qiymat bo'yicha qidiradi. Shunday qilib, biz aytishimiz mumkinki, struktura bajarilishi mumkin bo'lgan operatsiyalar bilan, shuningdek ularni bajarish tezligi bilan ajralib turadi. Masalan, samaradorlikni oshirishni ta'minlamaydigan, lekin aniq belgilangan qo'llab-quvvatlanadigan operatsiyalar to'plamiga ega bo'lgan eng oddiy tuzilmalarni ko'rib chiqing.
Yig'ma
Bu cheklangan, oddiy massiv shaklida taqdim etilgan ma'lumotlar tuzilmalarining turlaridan biridir. Klassik stek faqat uchta variantni qo'llab-quvvatlaydi:
- Biror narsani stakka suring (Murakkablik: O (1) O (1)).
- Stekdan elementni oching (Murakkablik: O (1) O (1)).
- Yig'inning bo'sh yoki yo'qligini tekshirish (Murakkablik: O (1) O (1)).
Stekning qanday ishlashini aniqlash uchun siz cookie-fayllar o'xshashligini ishlatishingiz mumkin. Idishning pastki qismida bir nechta pechene borligini tasavvur qiling. Siz yana ikkita qismni ustiga qo'yishingiz mumkin, yoki aksincha, ustiga bitta pechene olishingiz mumkin. Qolgan pechene ustki pishiriqlar bilan yopiladi va ular haqida hech narsa bilmaysiz. Bu stack bilan bog'liq. Kontseptsiyani tavsiflash uchun LIFO (Last In, First Out) qisqartmasi ishlatiladi, bu stekka oxirgi kirgan komponent birinchi bo'lishini va undan olib tashlanishini ta'kidlaydi.
Navbat
Bu stek bilan bir xil variantlar to'plamini qo'llab-quvvatlaydigan, ammo qarama-qarshi semantikaga ega bo'lgan ma'lumotlar tuzilishining yana bir turi. Navbatni tavsiflash uchun FIFO (First In, First Out) qisqartmasi ishlatiladi, chunki avval qo'shilgan element avval olinadi. Strukturaning nomi o'z-o'zidan gapiradi - ishlash printsipi do'konlarda, supermarketda ko'rish mumkin bo'lgan navbatlarga to'liq mos keladi.
Dekabr
Bu ma'lumotlar tuzilishining yana bir turi, uni ikki tomonlama navbat deb ham atashadi. Variant quyidagi operatsiyalar to'plamini qo'llab-quvvatlaydi:
- Elementni boshiga joylashtiring (Murakkablik: O (1) O (1)).
- Komponentni boshidan ajratib oling (Murakkablik: O (1) O (1)).
- Oxiriga element qo'shish (Murakkablik: O (1) O (1)).
- Ob'ektni oxiridan olish (Murakkablik: O (1) O (1)).
- Kemaning bo'shligini tekshiring (Qiyinchilik: O (1) O (1)).
Ro'yxatlar
Ushbu ma'lumotlar tuzilishi chiziqli bog'langan komponentlar ketma-ketligini belgilaydi, buning uchun ro'yxatdagi istalgan joyga komponentalarni qo'shish va uni o'chirish operatsiyalariga ruxsat beriladi. Chiziqli ro'yxat ko'rsatgich tomonidan ro'yxatning boshiga ko'rsatiladi. Odatda ro'yxat operatsiyalari shpal, ma'lum bir komponentni topish, element qo'shish, komponentni yo'q qilish, ikkita ro'yxatni bitta butunga birlashtirish, ro'yxatni juftlikka ajratish va boshqalarni o'z ichiga oladi. Shuni ta'kidlash kerakki, chiziqli ro'yxatda, birinchisidan tashqari, har bir element uchun avvalgi komponent mavjud bo'lib, oxirgisi qo'shilmaydi. Bu shuni anglatadiki, ro'yxatning tarkibiy qismlari tartiblangan holatda. Ha, bunday ro'yxatni qayta ishlash har doim ham qulay emas, chunki teskari yo'nalishda harakat qilish imkoniyati yo'q - ro'yxat oxiridan boshigacha. Biroq, chiziqli ro'yxatda siz barcha komponentlar bo'yicha bosqichma-bosqich harakat qilishingiz mumkin.
Shuningdek, qo'ng'iroq ro'yxatlari mavjud. Bu chiziqli ro'yxat bilan bir xil tuzilishga ega, ammo u birinchi va oxirgi komponentlar o'rtasida qo'shimcha aloqaga ega. Boshqacha qilib aytganda, birinchi komponent oxirgi elementning yonida joylashgan.
Ushbu ro'yxatda elementlar tengdir. Birinchisini va oxirini ajratish - bu konventsiya.
Daraxtlar
Bu tugunlar deb ataladigan tarkibiy qismlar to'plamidir, unda ildiz shaklida asosiy (bitta) komponent mavjud bo'lib, qolganlari bir-birlari bilan kesishmaydigan elementlarga bo'linadi. Har bir to'plam daraxt bo'lib, har bir daraxtning ildizi daraxt ildizining avlodidir. Boshqacha qilib aytganda, barcha tarkibiy qismlar ota-ona va bola munosabatlari bilan o'zaro bog'liqdir. Natijada tugunlarning ierarxik tuzilishi kuzatilishi mumkin. Agar tugunlarda bola bo'lmasa, unda ular barglar deb nomlanadi. Daraxt ustida bunday operatsiyalar quyidagicha tavsiflanadi: komponentni qo'shish va uni olib tashlash, o'tish, komponentni qidirish. Ikkilik daraxtlar kompyuter fanida alohida o'rin tutadi. Bu nima? Bu daraxtning alohida holati, u erda har bir tugunda chap va o'ng pastki daraxtning ildizi bo'lgan ko'pi bilan bir nechta bola bo'lishi mumkin. Agar qo'shimcha ravishda daraxt tugunlari uchun chap subtree tarkibiy qismlarining barcha qiymatlari ildizning qiymatlaridan kichik va o'ng pastki daraxt tarkibiy qismlarining qiymatlari ildizdan kattaroq bo'lishi sharti qondirilsa, u holda bunday daraxt ikkilik qidiruv daraxti deb ataladi va u elementlarni tezda topish uchun mo'ljallangan. Bunday holda qidiruv algoritmi qanday ishlaydi? Qidiruv qiymati ildiz qiymati bilan taqqoslanadi va natijaga qarab qidirish tugaydi yoki davom etadi, lekin faqat chap yoki o'ng pastki daraxtda. Taqqoslash operatsiyalarining umumiy soni daraxt balandligidan oshmaydi (bu ildizdan barglardan biriga o'tish yo'lidagi eng katta tarkibiy qism).
Graflar
Graflar - bu tepalar deb ataladigan komponentlar to'plami va shu uchlar orasidagi qirralar deb ataladigan munosabatlar majmuasi. Ushbu strukturaning grafik talqini tepaliklarga mos keladigan nuqtalar to'plami ko'rinishida taqdim etilgan va ba'zi juftlar qirralarga to'g'ri keladigan chiziqlar yoki o'qlar bilan bog'langan. Oxirgi holat grafikani yo'naltirilgan deb atashni taklif qiladi.
Grafikalar har qanday strukturadagi ob'ektlarni tavsiflashi mumkin, ular murakkab tuzilmalarni va barcha tizimlarning ishlashini tavsiflovchi asosiy vositadir.
Mavhum tuzilish haqida ko'proq bilib oling
Algoritmni tuzish uchun ma'lumotlarni rasmiylashtirish talab qilinadi, yoki boshqacha qilib aytganda, ma'lumotlarni allaqachon o'rganilgan va yozilgan ma'lum bir ma'lumot modeliga etkazish kerak. Model topilgandan so'ng, mavhum tuzilish o'rnatildi, deb bahslashish mumkin.
Bu ob'ektning xususiyatlarini, fazilatlarini, ob'ekt tarkibiy qismlari va unda bajarilishi mumkin bo'lgan operatsiyalar o'rtasidagi munosabatni namoyish etadigan asosiy ma'lumotlar tuzilishi. Asosiy vazifa - kompyuterni tuzatish uchun qulay bo'lgan axborot taqdimot shakllarini izlash va namoyish qilish. Darhol ta'kidlash kerakki, informatika aniq fan sifatida rasmiy ob'ektlar bilan ishlaydi.
Ma'lumotlar strukturasini tahlil qilish quyidagi ob'ektlar tomonidan amalga oshiriladi:
- Butun sonlar va haqiqiy sonlar.
- Mantiqiy qiymatlar.
- Belgilar.
Barcha elementlarni kompyuterda qayta ishlash uchun tegishli algoritmlar va ma'lumotlar tuzilmalari mavjud. Odatda ob'ektlar murakkab tuzilmalarga birlashtirilishi mumkin. Ushbu tuzilmaning ayrim qismlariga ularga operatsiyalar, qoidalar qo'shishingiz mumkin.
Ma'lumotlarni tashkil qilish tarkibiga quyidagilar kiradi:
- Vektorlar.
- Dinamik tuzilmalar.
- Jadvallar.
- Ko'p o'lchovli massivlar.
- Graflar.
Agar barcha elementlar muvaffaqiyatli tanlangan bo'lsa, unda bu samarali algoritmlar va ma'lumotlar tuzilmalarini shakllantirish uchun kalit bo'ladi. Agar biz tuzilmalar va haqiqiy ob'ektlarning o'xshashligini amalda qo'llasak, u holda mavjud muammolarni samarali hal qilishimiz mumkin.
Shuni ta'kidlash kerakki, barcha ma'lumotlarni tashkil qilish tuzilmalari dasturlashda alohida-alohida mavjud. Ular o'n sakkizinchi va o'n to'qqizinchi asrlarda, hali ham kompyuterdan asar ham qolmagan paytda ular ustida juda ko'p ishladilar.
Algoritmni mavhum tuzilish nuqtai nazaridan ishlab chiqish mumkin, ammo algoritmni ma'lum bir dasturlash tilida amalga oshirish uchun uni ma'lum bir dasturlash tili tomonidan qo'llab-quvvatlanadigan ma'lumotlar turlarida, operatorlarda namoyish qilish texnikasini topish kerak bo'ladi. Vektor, plastinka, qator, ketma-ketlik kabi tuzilmalarni yaratish uchun ko'plab dasturlash tillarida ma'lumotlarning klassik turlari mavjud: bir o'lchovli yoki ikki o'lchovli massiv, satr, fayl.
Biz ma'lumotlar tuzilmalarining xususiyatlarini aniqladik, endi strukturaning kontseptsiyasini tushunishga ko'proq e'tibor qaratish lozim. Mutlaqo har qanday muammoni hal qilishda siz ma'lumotlar bilan ishlashni amalga oshirish uchun qandaydir ma'lumotlar bilan ishlashingiz kerak. Har bir topshiriq o'ziga xos operatsiyalar to'plamiga ega, ammo ma'lum bir to'plam amalda turli vazifalarni hal qilishda tez-tez ishlatiladi. Bunday holda, ushbu operatsiyalarni iloji boricha samarali bajarishga imkon beradigan ma'lumotni tashkil qilishning ma'lum bir usulini o'ylab topish foydalidir. Bunday usul paydo bo'lishi bilanoq, sizda "qora quti" mavjud bo'lib, unda ma'lum bir turdagi ma'lumotlar saqlanadi va ular ma'lumotlar bilan ba'zi operatsiyalarni bajaradi. Bu sizning fikringizni tafsilotlardan olib tashlashga va muammoning o'ziga xos xususiyatlariga to'liq e'tibor berishga imkon beradi. Ushbu "qora quti" har qanday usulda amalga oshirilishi mumkin, shu bilan birga eng samarali amalga oshirishga intilish kerak.
Buni kim bilishi kerak?
Ushbu sohada o'z o'rnini topmoqchi bo'lgan, ammo qaerga borishni bilmagan yangi boshlagan dasturchilar uchun ma'lumot bilan tanishish kerak. Bular har bir dasturlash tilidagi asoslardir, shuning uchun ma'lumotlar tuzilmalari to'g'risida darhol ma'lumot olish, so'ngra ular bilan aniq misollar yordamida va ma'lum bir til bilan ishlash ortiqcha bo'lmaydi. Shuni esdan chiqarmaslik kerakki, har bir tuzilmani mantiqiy va fizikaviy tasvirlar, shuningdek, ushbu tasvirlar bo'yicha operatsiyalar to'plami bilan tavsiflash mumkin.
Unutmang: agar siz ma'lum bir tuzilish haqida gapiradigan bo'lsangiz, unda uning mantiqiy ko'rinishini yodda tuting, chunki jismoniy tasvir "tashqi kuzatuvchi" dan butunlay yashiringan.
Shuni ham yodda tutingki, mantiqiy tasvir dasturlash tili va kompyuterdan mutlaqo mustaqildir, jismoniy, aksincha, tarjimonlar va kompyuterlarga bog'liq. Masalan, Fortran va Paskaldagi ikki o'lchovli massiv bir xil tarzda ifodalanishi mumkin, ammo bitta kompyuterda ushbu tillarda fizikaviy ko'rinishi boshqacha bo'ladi.
Muayyan tuzilmalarni o'rganishni boshlashga shoshilmang, ularning tasnifini tushunish, har bir narsa bilan nazariy va tercihen amalda tanishish yaxshiroqdir. Shuni esda tutish kerakki, o'zgaruvchanlik strukturaning muhim xususiyati bo'lib, statik, dinamik yoki yarim statik holatni bildiradi. Dunyo miqyosidagi narsalarni o'rganishdan oldin asoslarni o'rganing, bu sizga yanada rivojlanishingizga yordam beradi.
