Ma’lumotlar tuzilmasi va algoritimlar
Download 370.35 Kb.
|
Ma\'lumotlar tuzilmasi 3
- Bu sahifa navigatsiya:
- Infiks oʻtish
- Foydanilgan adabiyotlar.
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI Ma’lumotlar tuzilmasi va algoritimlar Mustaqil ish Bajardi:Jumayev O. Qabul qildi:Ablaqulov K. Mavzu:Binar daraxtlar bilan ishlash Reja:
Binar daraxti ikkilik ifodalarni ifodalash uchun ishlatiladigan dastur tili hisoblanadi. Binar daraxti ifodalashi mumkin boʻlgan ikkita keng tarqalgan ikkilik ifoda turi algebraik[1] va mantiqiy ifoda turlari hisoblanadi. Binar daraxti birlik va ikkilik operatorlarni oʻz ichiga olgan ifodalarni ifodalashi mumkin. Binar ifoda daraxtining har bir tugunida nol, bitta yoki ikkita son mavjud. Ushbu cheklangan struktura ifoda daraxtlarini qayta ishlashni soddalashtiradi. (a+b)*c+7 ifodaning ifodalar daraxti Ikkilik ifoda daraxtining barglari operandlar, masalan, doimiylar yoki oʻzgaruvchilar nomlari va boshqa tugunlarda operatorlar mavjud. Bu alohida daraxtlar ikkilik boʻladi, chunki barcha operatsiyalar ikkilikdir va bu eng oddiy holat boʻlsa-da, tugunlarda ikkitadan ortiq son boʻlishi mumkin. Bundan tashqari, birlik minus operatorida boʻlgani kabi, tugunning har biri faqat bitta songa ega boʻlishi mumkin. Ifodalar daraxti T ni chap va oʻng pastki daraxtlarni rekursiv baholash natijasida olingan qiymatlarga ildizdagi operatorni qoʻllash orqali baholash mumkin. Oʻtish Algebraik ifoda ikkilik ifoda daraxtidan qavs ichiga olingan chap ifodani rekursiv ishlab chiqarish, soʻngra operatorni ildizga chiqarish va nihoyat, qavs ichiga olingan oʻng ifodani rekursiv ishlab chiqarish orqali ishlab chiqarilishi mumkin. Ushbu umumiy strategiya (chap, tugun, oʻng) tartibli o'tish sifatida tanilgan. Muqobil oʻtish strategiyasi chap pastki daraxtni, oʻng pastki daraxtni va keyin operatorni rekursiv ravishda chop etishdir. Ushbu oʻtish strategiyasi odatda buyruqdan keyingi o'tish sifatida tanilgan. Uchinchi strategiya — avval operatorni chop etish, soʻngra oldindan tartibli oʻtkazish deb nomlanuvchi chap va oʻng pastki daraxtni rekursiv ravishda chop etish. Ushbu uchta standartdan birinchi oʻtish uch xil ifoda formatlarining ifodasidir: infiks, postfiks va prefiks. Infiks ifodasi tartibni kesib oʻtish orqali, postfiks ifodasi buyruqdan keyingi oʻtish orqali va prefiks ifodasi oldindan tartibli oʻtish orqali hosil boʻladi. Infiks oʻtish Infiks ifodasi chop etilganda, har bir ifodaning boshiga va oxiriga ochilish va yopish qavslari qoʻshilishi kerak. Har bir pastki daraxt pastki ifodani ifodalaganligi sababli, uning boshida ochilish qavslari va barcha sonlarni qayta ishlagandan soʻng, yopish qavslari chop etiladi. Psevdokod: Algoritm infix ( daraxt ) Algorithm infix (tree) /*Print the infix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the infix expression has been printed*/ if (tree not empty) if (tree token is operator) print (open parenthesis) end if infix (tree left subtree) print (tree token) infix (tree right subtree) if (tree token is operator) print (close parenthesis) end if end if end infix Algebraik ifoda daraxtlari raqamlar, oʻzgaruvchilar va birlik va ikkilik operatorlarni oʻz ichiga olgan ifodalarni ifodalaydi. Baʼzi umumiy operatorlar × (koʻpaytirish), ÷ (boʻlish), + (qoʻshish), — (ayirish), ^ (koʻrsatkich) va — (inkor). Operatorlar daraxtning ichki tugunlarida, raqamlar va oʻzgaruvchilar barg tugunlarida joylashgan boʻladi[3]. Ikkilik operatorlar tugunlarida ikkita tugun, birlik operatorlarda esa bitta tugun mavjud. Ikkilik mantiqiy ifoda daraxtiga ekvivalent ((rost {\displaystyle \lor } yolgʻon) {\displaystyle \land }{\displaystyle \neg } yolgʻon) {\displaystyle \lor } (rost {\displaystyle \lor } yolgʻon)) Foydanilgan adabiyotlar. 1. Bruno R. Preiss. „Expression Trees“ (1998). 19-yanvar 2017-yilda asl nusxadan arxivlandi. Qaraldi: 20-dekabr 2010-yil.2. Mark Allen Weiss,Data Structures and Algorithm Analysis in C,2nd edition, Addison Wesley publications 3. Bruno R. Preiss. „Expression Trees“ (1998). 19-yanvar 2017-yilda asl nusxadan arxivlandi. Qaraldi: 20-dekabr 2010-yil. Bruno R. Preiss (1998). „Expression Trees“. Archived from the original on January 19, 2017. Retrieved December 20, 2010. Download 370.35 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling