O'zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali "Dasturiy injiniring" kafedrasi

O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI "Dasturiy injiniring" kafedrasi

“KOMPYUTER INJINIRINGI” FAKULTETI
Guruh : KIS 20-01
“Algaritmlarni loyihalash” fanidan
Bajardi: Qarabayev M
Qabul qildi: Mahmudov R.Z
Mavzu: Ketma-ketliklar, to‟plamlar, daraxtlar, graflarni ifodalash usullari.
Ketma-ketliklar:
Ketma-ketliklar massivlar yoki bog'langan ro'yxatlar yordamida ifodalanishi mumkin. Masalan, [1, 2, 3, 4, 5] butun sonlar massivi beshta butun sonlar ketma-ketligini ifodalaydi.

2. To'plamlar:

To'plamlar massivlar, bog'langan ro'yxatlar yoki xesh-jadvallar yordamida ifodalanishi mumkin. Misol uchun, noyob elementlarni ifodalovchi kalitlari va ularning chastotalarini ifodalovchi qiymatlari bo'lgan xesh-jadval elementlar to'plamini ifodalashi mumkin.

3. Daraxtlar:

Daraxtlar massivlar, bog'langan ro'yxatlar yoki ko'rsatkichlar bilan tugunlar yordamida ifodalanishi mumkin. Misol uchun, ikkilik qidiruv daraxti ularning chap va o'ng bolalariga ko'rsatgichlari bo'lgan tugunlar yordamida ifodalanishi mumkin.

4. Grafiklar:

Grafiklar qo'shni matritsalar yoki qo'shni ro'yxatlar yordamida ifodalanishi mumkin. Masalan, uchlari kalit sifatida va ularning qo'shni uchlari qiymat sifatida ifodalangan qo'shnilik ro'yxati grafikni ifodalashi mumkin.

Umuman olganda, vakillikni tanlash muayyan muammoga va ma'lumotlar strukturasida bajarilishi kerak bo'lgan operatsiyalarga bog'liq.

Rekursiv algoritm f dasturlash tilida yozilgan. Rekursiya va rekursiv algoritmlar. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Rekursiya - bu subroutin o'zini o'zi chaqiradigan vaziyat. Bunday algoritmik qurilishga birinchi marta duch kelganda, ko'pchilik muayyan qiyinchiliklarga duch keladi, ammo ozgina amaliyot va rekursiya sizning dasturiy arsenalingizda tushunarli va juda foydali vositaga aylanadi. 1. Rekursiya mohiyati Protsedura yoki funktsiya boshqa protseduralar yoki funktsiyalarni chaqirishni o'z ichiga olishi mumkin. Protsedurani o'z ichiga olishi mumkin. Bu erda hech qanday paradoks yo'q - kompyuter faqat dasturda uchragan buyruqlarni ketma-ket bajaradi va agar u protsedura qo'ng'irog'iga duch kelsa, shunchaki ushbu protsedurani bajarishni boshlaydi. Buni qanday buyruq berganligi muhim emas. Rekursiv protseduraga misol: Rec (a: butun) protsedurasi; agar boshlang\u003e a Agar asosiy dasturda, masalan, Rec (3) shaklida qo'ng'iroq qilinsa nima bo'lishini ko'rib chiqing. Quyida bayonlarning ketma-ketligini ko'rsatuvchi jadval. Anjir. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a \u003d 3. parametri bilan chaqiriladi, unda a \u003d 2 parametrli Rec protsedurasiga qo'ng'iroq bor. Oldingi qo'ng'iroq hali tugallanmagan, shuning uchun siz boshqa protsedura yaratilayotganligini tasavvur qilishingiz mumkin va uning ishi oxiriga qadar u o'zining birinchi ishini tugatmaydi. A \u003d 0 parametridan so'ng qo'ng'iroq jarayoni tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida bajariladi. Bir vaqtning o'zida bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi. (Rec (0)) deb nomlangan to'rtinchi protsedura 0 raqamini bosib chiqaradi va o'z ishini yakunlaydi. Shundan so'ng, boshqaruv uni (Rec (1)) deb nomlangan protseduraga qaytadi va 1-raqam bosiladi va hokazo, barcha protseduralar tugaguncha. Dastlabki qo'ng'iroq natijasi to'rtta raqamni chop etadi: 0, 1, 2, 3. Nima bo'layotganining yana bir vizual tasviri sek. 2. Anjir. 2. Rec protsedurasini 3-parametr bilan bajarish, 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni bosib chiqarish, o'z navbatida, 2-parametr bilan Rec protsedurasini bajarish, 1-parametr bilan Rec protsedurasini bajarish va 2-raqamni bosib chiqarish va boshqalarni o'z ichiga oladi. Mustaqil mashq sifatida Rec (4) ni chaqirganda nima bo'lishini o'ylang. Shuningdek, quyida tasvirlangan Rec2 (4) protsedurasini chaqirganda nima yuz berishi haqida o'ylang, bu erda operatorlar almashadi. Rec2 protsedurasi (a: butun); writeln (a) boshlash; agar a\u003e 0 bo'lsa, Rec2 (a-1); oxiri; Yuqoridagi misollarda rekursiv chaqiruv shartli gapning ichida ekanligini unutmang. Bu rekursiyani to oxirigacha davom ettirish uchun zarur shartdir. Shuni ham yodda tutingki, protseduraning o'zi boshqa parametr bilan chaqiriladi, lekin u chaqirilgandek emas. Agar protsedura global o'zgaruvchilardan foydalanmasa, unda rekursiya cheksiz davom etmasligi kerak. Bir oz murakkabroq sxema mumkin: A funktsiyasi B funktsiyasini chaqiradi va o'z navbatida A ni chaqiradi murakkab rekursiya. Bunday holda, birinchi bo'lib tasvirlangan protsedura hali tavsiflanmagan bo'lishi kerak. Buni amalga oshirish uchun foydalanish kerak. Jarayon A (n: butun son); (Birinchi protseduraning avans tavsifi (nomi)) B protsedurasi (n: butun son); (Ikkinchi protseduraning avans tavsifi) A (n: butun son) protsedurasi; (Protseduraning to'liq tavsifi A) writeln (n) boshlanadi; B (n-1); oxiri; protsedura B (n: butun son); (B protseduraning to'liq tavsifi) boshlanadi wr (n); agar n B protsedurasining batafsil tavsifi sizga uni A protsedurasidan chaqirishga imkon beradi. Ushbu misolda A protsedurasining batafsil tavsifi talab qilinmaydi va estetik sabablarga ko'ra qo'shiladi. Agar oddiy rekursiyani bizning oboborosga o'xshatish mumkin bo'lsa (3-rasm), unda murakkab recursion tasvirini “Qo'rquvdan bo'rilar bir-birini eb yuborgan” mashhur bolalar she'ridan yig'ish mumkin. Ikki bo'rining bir-birini eyishini tasavvur qiling, shunda siz murakkab rekursiyani tushunasiz. Anjir. 3. Ouroboros - dumini yutib yuboradigan ilon. Teodor Pelekanosning (1478) "Sinosius" kimyoviy traktatidan olingan rasm. Anjir. 4. Murakkab rekursiya. 3. Rekursion yordamida ko'chadan simulyatsiya qilish Agar protsedura o'zini o'zi chaqirsa, demak, mohiyatan, bu tsiklning ishlashiga o'xshash tarkibiy ko'rsatmalarning takroriy bajarilishiga olib keladi. Ba'zi dasturlash tillarida umuman tsiklli konstruktsiyalar mavjud emas, bu esa dasturchilarni takrorlash yordamida takrorlashni tashkil qilish uchun qoldiradi (masalan, Prolog, bu erda rekursiya asosiy dasturlash uslubidir). Masalan, for loopning ishini taqlid qiling. Buning uchun, masalan, protsedura parametri sifatida bajarilishi mumkin bo'lgan o'zgaruvchan qadam hisoblagichiga ehtiyoj bor. 1-misol LoopImitatsiya protsedurasi (i, n: butun son); (Birinchi parametr - qadam hisoblagichi, ikkinchi parametr - bu qadamlarning umumiy soni) writeln boshlanadi ("Salom N", i); // Mana, agar i takrorlansa, ko'rsatmalar mavjud LoopImitatsiya turini (1, 10) chaqirish natijasida, hisoblagichlar 1 dan 10 gacha o'zgargan holda ko'rsatmalarning o'n barobar bajarilishi bo'ladi, bu holda u bosadi: Salom N 1 Salom N 2 … Salom N 10 Umuman olganda, protsedura parametrlari hisoblagich qiymatlarining o'zgarishi chegarasi ekanligini ko'rish qiyin emas. Quyidagi misolda bo'lgani kabi, siz takrorlanadigan qo'ng'iroqni va takrorlanadigan ko'rsatmalarni almashtirishingiz mumkin. 2-misol LoopImitation2 protsedurasi (i, n: butun son); agar i Bunday holda, ko'rsatmalar bajarilishidan oldin, protseduraga rekursiv qo'ng'iroq paydo bo'ladi. Hisoblagichning maksimal qiymatiga erishmagunimizcha protseduraning yangi namunasi, avvalambor, boshqa misolni chaqiradi va hokazo. Shundan keyingina, chaqirilgan protseduralarning oxirgisi uning ko'rsatmalarini bajaradi, so'ngra oxirgi, ammo bitta ko'rsatmani bajaradi va hokazo. LoopImitatsiya2 (1, 10) ni chaqirish natijasi tabriklarni teskari tartibda chop etadi: Salom N 10 … Salom N 1 Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, unda 1-misolda biz bundan oldin chaqirilgan protseduralardan keyingilariga o'tamiz. 2-misolda buning teskarisi keyinroq oldingisiga. Va nihoyat, ikkita ko'rsatma bloklari orasiga rekursiv qo'ng'iroqni qo'yish mumkin. Misol uchun: LoopImitation3 protsedurasi (i, n: butun son); begin writeln ("Salom N", i); (Birinchi ko'rsatmalar bloki bu erda joylashgan bo'lishi mumkin), agar i Bu erda birinchi navbatda birinchi blokdagi ko'rsatmalar ketma-ket, so'ngra teskari tartibda, ikkinchi blokning ko'rsatmalari bajariladi. LoopImitation3 (1, 10) ni chaqirganda biz quyidagilarga ega bo'lamiz: Salom N 1 … Salom N 10 Salom N 10 … Salom N 1 Buni takrorlashsiz bir xil qilish uchun birdaniga ikki tsikl kerak bo'ladi. Xuddi shu protsedura qismlarining bajarilishi vaqt ichida ajratilganligini ishlatish mumkin. Misol uchun: 3-misol: raqamni ikkilik tizimga tarjima qilish. Ikkilik raqamlarning raqamlarini olish, ma'lum bo'lganingizdek, qolgan son bilan 2-son tizimining bazasida bo'lish orqali sodir bo'ladi. Agarda raqam mavjud bo'lsa, uning ikkilik ko'rinishida uning oxirgi raqami bo'ladi. 2 ga bo'linishdan butun sonni olish: biz bir xil ikkilik tasvirga ega bo'lgan sonni olamiz, ammo oxirgi raqamsiz. Shunday qilib, keyingi bo'linish maydoni 0 ga teng butun sonni olguncha yuqoridagi ikkita operatsiyani takrorlash kifoya qiladi. Repsursiz, u quyidagicha bo'ladi: X\u003e 0 boshlanganda c: \u003d x mod 2; x: \u003d x div 2; yozish (c); oxiri; Bu erda muammo shundaki, ikkilik vakillik raqamlari teskari tartibda (birinchi oxiri) hisoblab chiqiladi. Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha raqamlarni eslab, ularni alohida tsiklda ko'rsatishingiz kerak. Rekursiondan foydalanib, natijani ketma-ket va ikkinchi bosqichsiz to'g'ri tartibda olish oson. Aynan: BinaryRepresentation protsedurasi (x: butun); var c, x: butun; begin (Birinchi blok. Bu protsedurani chaqirish tartibida bajariladi) c: \u003d x mod 2; x: \u003d x div 2; (Rekursiv qo'ng'iroq) agar x\u003e 0 bo'lsa, BinaryRepresentation (x); (Ikkinchi blok. Bu teskari tartibda bajariladi) yozish (c); oxiri; Umuman olganda, biz hech qanday foyda olmadik. Ikkilik vakillik raqamlari mahalliy o'zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlaydigan holati uchun farq qiladi. Ya'ni, xotirani saqlab qolishning iloji bo'lmadi. Aksincha, biz ko'plab mahalliy o'zgaruvchilarni saqlash uchun qo'shimcha xotira sarflaymiz. Shunga qaramay, bunday echim menga juda chiroyli ko'rinadi. 4. Takroriy nisbatlar. Rekursiya va takrorlash Agar boshlang'ich vektor va keyingi vektorning oldingi holatga funktsional bog'liqligi bo'lsa, vektorlar ketma-ketligi takrorlanish munosabati bilan beriladi, deyiladi. Takrorlanish munosabatlari yordamida hisoblangan miqdorning oddiy namunasi - bu faktorial Keyingi omilni avvalgisidan hisoblash mumkin: Notation bilan tanishtirib, biz nisbatni olamiz: Formuladan (1) vektorlarni o'zgaruvchan qiymatlar to'plami sifatida talqin qilish mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini takroriy yangilashdan iborat bo'ladi. Xususan, faktorial uchun: X: \u003d 1; for i: \u003d 2 to n do x: \u003d x * i; writeln (x); Har bir bunday yangilanish (x: \u003d x * i) chaqiriladi iteratsiya, va takrorlashni takrorlash jarayoni iteratsiya. Ammo shuni ta'kidlaymizki, munosabatlar (1) - bu ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash f funktsiyani o'zidan ko'p marta olishdir: Xususan, faktorial uchun siz quyidagilarni yozishingiz mumkin: Factorial funktsiyasi (n: butun son): butun; agar n\u003e 1 bo'lsa, undan keyin boshlang'ich: \u003d n * Fakultativ (n-1) else Faktor: \u003d 1; oxiri; Shuni tushunish kerakki, chaqirish funktsiyalari qo'shimcha qo'shimcha xarajatlarni talab qiladi, shuning uchun omilni hisoblashning birinchi varianti biroz tezroq bo'ladi. Umuman olganda, iterativ echimlar rekursiv echimlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo'lgan holatlarga o'tishdan oldin, keling, uni ishlatmaslik kerak bo'lgan yana bir misolga e'tibor qarataylik. Takroriy munosabatlarning alohida holatini ko'rib chiqing, agar ketma-ketlikning keyingi qiymati bir biriga emas, balki darhol bir necha oldingi qiymatlarga bog'liq bo'lsa. Bunga misol sifatida taniqli Fibonachchi ketma-ketligini keltirish mumkin, bunda har bir keyingi element oldingi ikki elementning yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Fib (n: integer): butun son; agar n\u003e 1 bo'lsa, keyin Fib: \u003d Fib (n-1) + Fib (n-2), boshqa tolalar: \u003d 1; oxiri; Har bir Fib qo'ng'irog'i birdaniga ikkita nusxani yaratadi, ularning har biri yana ikkita nusxani yaratadi va hokazo. Operatsiyalar soni soniga qarab o'sib bormoqda n eksponent sifatida, garchi iterativ eritma etarlicha chiziqli bo'lsa ham n operatsiyalar soni. Aslida, bu misol bizga o'rgatmaydi QACHON rekursiya ishlatilmasligi kerak, lekin AS ishlatilmasligi kerak. Oxir-oqibat, agar tez iterativ (ko'chadan asoslangan) echim bo'lsa, xuddi shu pastadir rezursiv protsedura yoki funktsiyadan foydalanib amalga oshirilishi mumkin. Misol uchun: // x1, x2 - boshlang'ich shartlar (1, 1) // n - Fibonachchi funktsiyasining zarur bo'lgan soni Fib (x1, x2, n: integer): butun son; var x3: butun son; agar n\u003e 1 bo'lsa, keyin x3 ni boshlang: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; Fib: \u003d tolasi (x1, x2, n-1); else end Fib: \u003d x2; oxiri; Hali ham iterativ echimlar afzal ko'riladi. Savol shuki, qachon rekursiondan foydalanish kerak? Faqatgina bitta rekursiv chaqiruvni o'z ichiga olgan har qanday rekursiv protseduralar va funktsiyalar osongina iterativ tsikllar bilan almashtiriladi. Oddiy rekursiv bo'lmagan analogga ega bo'lmagan narsani olish uchun siz o'zlarini ikki yoki undan ko'p marta chaqiradigan protseduralar va funktsiyalarga murojaat qilishingiz kerak. Bunday holda, chaqirilgan protseduralar to'plami endi shaklda bo'lgani kabi zanjir hosil qilmaydi. 1 va butun daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo'lgan muammolarning keng sinflari mavjud. Faqat ular uchun rekursiya uni hal qilishning eng oson va tabiiy usuli bo'ladi. 5. Daraxtlar O'zlarini bir necha bor chaqiradigan rekursiv funktsiyalarning nazariy asosi daraxtlarni o'rganadigan diskret matematika bo'limi. 5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Ta'rif: biz cheklangan to'plamni chaqiramiz Tbir yoki bir nechta tugunlardan iborat, masalan: a) Ushbu daraxtning ildizi deb nomlangan bitta maxsus tugun mavjud. b) qolgan tugunlar (ildizni hisobga olmaganda) ikkitadan ajratilgan pastki qatorlarda joylashgan bo'lib, ularning har biri o'z navbatida daraxtdir. Daraxtlar deyiladi pastki daraxtlar bu daraxt. Ushbu ta'rif rekursivdir. Qisqacha aytganda, daraxt - bu ildiz va unga bog'langan kichik daraxtlardan iborat to'plam, ular ham daraxtlardir. Daraxt o'zi orqali aniqlanadi. Ammo, bu ta'rif ma'noga ega, chunki rekursiya cheklangan. Har bir pastki darcha o'z ichiga olgan daraxtga qaraganda kamroq tugunlarga ega. Oxir-oqibat, biz faqat bitta tugunni o'z ichiga olgan pastki daraxtlarga kelamiz va u nima ekanligi aniq bo'ldi. Anjir. 3. Daraxt. Shaklda 3da etti tugunli daraxt ko'rsatilgan. Oddiy daraxtlar pastdan yuqoriga o'ssa-da, ularni chizish aksincha. Diagrammani qo'l bilan chizishda ushbu usul aniqroq qulayroqdir. Ushbu nomuvofiqlik tufayli, ba'zida ular tugunlardan biri ikkinchisidan yuqorida yoki pastda joylashganligini aytganda chalkashlik paydo bo'ladi. Shu sababli, oilaviy daraxtlarni tavsiflashda ishlatiladigan atamalarni, ildiz otalariga yaqinroq tugunlarni va uzoqroq avlodlarni chaqirish qulayroqdir. Grafik jihatdan daraxt boshqa bir necha usullar bilan ifodalanishi mumkin. Ulardan ba'zilari anjir shaklida keltirilgan. 4. Ta'rifga ko'ra, daraxt - bu bir-biri bilan kesishmaydigan yoki to'liq bir-biriga joylashtirilgan ichki o'rnatilgan to'plamlar tizimidir. Bunday to'plamlarni samolyotda mintaqalar sifatida ko'rsatish mumkin (4 a-rasm). Shaklda 4b, ichki to'plamlar samolyotda emas, balki bitta chiziqda cho'zilgan. Anjir. 4b-ni, shuningdek, ichiga o'rnatilgan qavslarni o'z ichiga olgan ba'zi algebraik formulaning diagrammasi sifatida ko'rib chiqish mumkin. Anjir. 4c daraxt tuzilishini ro'yxat sifatida namoyish etishning yana bir mashhur usulini taqdim etadi. Anjir. 4. Daraxt konstruktsiyalarini tasvirlashning boshqa usullari: (a) joylashtirilgan to'plamlar; (b) ichki qavslar; (c) topshiriqlar ro'yxati. Belgilangan ro'yxat kodni formatlash usuliga aniq o'xshashliklarga ega. Darhaqiqat, tizimli dasturlash paradigmasi doirasida yozilgan dasturni inshootlardan tashkil topgan daraxt sifatida ko'rsatish mumkin. Shuningdek, siz topshiriq ro'yxati va kitoblar tarkibidagi jadvalning ko'rinishi o'rtasida taqqoslashingiz mumkin, unda bo'limlar kichik bo'limlarga ega, o'z navbatida ular pastki bo'limlar va boshqalar. Bunday qismlarni raqamlashning an'anaviy usuli (1-bo'lim, 1.1 va 1.2-bo'limlar, 1.1.2-kichik bo'lim va boshqalar) Dewey o'nlik tizimi deb ataladi. Anjir daraxtiga qo'llanilgandek. 3 va 4, ushbu tizim quyidagilarni beradi: 1. A; 1,1 B; 1,2 S; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G; 5.2. Daraxtlarning o'tishi Daraxt konstruktsiyalari bilan bog'liq bo'lgan barcha algoritmlarda bir xil fikr mutlaqo uchraydi, ya'ni g'oya o'tgan yoki daraxt shpallari. Bu daraxtning tugunlariga tashrif buyurishning shunday usuli, unda har bir tugun aniq bir marta o'tadi. Natijada daraxt tugunlari chiziqli joylashadi. Xususan, uchta usul mavjud: siz tugunlarni oldinga, orqaga va tugash tartibiga o'tishingiz mumkin. To'g'ridan-to'g'ri tartibda shpal algoritmi: Ildizga o'ting To'g'ri tartibda chapdan o'ngga barcha pastki qismlardan o'ting. Ushbu algoritm rekursivdir, chunki daraxtni kesib o'tishda pastki kesishgan daraxtlar mavjud va ular, o'z navbatida, xuddi shu algoritm orqali o'tadi. Xususan, sek. 3 va 4-chi to'g'ridan-to'g'ri chorrahalar tugunlarning ketma-ketligini beradi: A, B, C, D, E, F, G. Olingan ketma-ketlik chapdan o'ngga yo'naltirilgan tugunlarning ketma-ket joylashtirilgan ro'yxatiga, Dewey o'nli tizimida joylashtirilgan qavslardan foydalangan holda daraxtni ifodalashda, shuningdek, topshiriqlar ro'yxati shaklida taqdim etilganda yuqoridan pastga qarab. Ushbu algoritmni dasturlash tilida amalga oshirayotganda, ildizga o'tish ba'zi bir amallar yoki funktsiyalarning bajarilishiga va subursiyalarning o'zlarining rekursiv chaqiruvlariga o'tishga to'g'ri keladi. Xususan, ikkilik daraxt uchun (har bir tugundan ikkitadan kam bo'lmagan daraxtlar) tegishli protsedura quyidagicha bo'ladi: // Old buyurtma Traversal - to'g'ridan-to'g'ri buyurtma protsedurasining inglizcha nomi PreorderTraversal ((Argumentlar)); start // DoSomething ((Dalillar)) ildizini o'tkazing; // Chap pastki satrni o'tkazing, agar (chap satr mavjud bo'lsa) va keyin PreorderTransversal ((Argumentlar 2)); // To'g'ri pastki satrni o'tkazing, agar (To'g'ri pastki satr mavjud bo'lsa) va keyin PreorderTransversal ((Argumentlar 3)); oxiri; Ya'ni, dastlab protsedura barcha harakatlarni bajaradi va shundan keyingina barcha rekursiv qo'ng'iroqlar sodir bo'ladi. Algoritmni teskari tartibda aylantiring: Chap pastki qismdan o'ting Ildizga o'ting Chap pastki qismga o'ting. Ildizga o'ting va hokazo eng to'g'ri pastki qator o'tguncha. Ya'ni, barcha pastki daraxtlar chapdan o'ngga o'tkaziladi va ildizga qaytish ushbu o'tish joylari orasida joylashgan. Anjir daraxt uchun. 3 va 4 bu tugunlarning ketma-ketligini beradi: B, A, D, C, E, G, F. Tegishli rekursiv protsedurada harakatlar rekursiv qo'ng'iroqlar orasida joylashgan bo'ladi.
Hulosa
Xulosa qilib aytganda, ketma-ketliklar, to'plamlar, daraxtlar va grafiklar kabi umumiy ma'lumotlar tuzilmalarini ifodalashning turli usullari mavjud. Vakillikni tanlash muayyan muammoga va ma'lumotlar strukturasida bajarilishi kerak bo'lgan operatsiyalarga bog'liq. Masalan, massivlar elementlarga tasodifiy kirishni talab qiladigan ketma-ketliklar uchun ko'proq mos bo'lishi mumkin, bog'langan ro'yxatlar esa tez-tez kiritish yoki o'chirishni talab qiladigan ketma-ketliklar uchun ko'proq mos kelishi mumkin. Xuddi shunday, xesh-jadvallar tez-tez a'zolik sinovlarini talab qiladigan to'plamlar uchun samaraliroq bo'lishi mumkin, ikkilik qidiruv daraxtlari esa tartibli o'tishni talab qiladigan to'plamlar uchun ko'proq mos kelishi mumkin. Umuman olganda, ma'lumotlar tuzilmalarini ifodalashning turli usullarini tushunish samarali va samarali algoritm dizayni uchun juda muhimdir.