|
Algoritmlar va berilganlar strukturalari
|
| bet | 1/14 | | Sana | 23.11.2023 | | Hajmi | 0,65 Mb. | | #104360 |
Bog'liq Algoritmlar va berilganlar strukturalari Algoritmlar va berilganlar strukturalari.
Fanidan yakuniyaga javoblari
Algoritmlar va berilganlar strukturasining asosiy tushuncha va ta’riflar.
Algoritm bu oldimizga qo‘yilgan masalani yechish zarur bo‘lgan amallar ketma-ketligidir.Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan. Algoritmning asosiy xossalari.Algoritmning 5-ta asosiy xossasi bor:Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi.
Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan ishlayotgan elektron soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik va mexanik qurilmalarni kuzatamiz. Aniqlik. Ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi zarur. Chunki ko‘rsatmadagi noaniqliklar mo‘ljaldagi maqsadga erishishga olib kelmaydi. Ommaviylik. Har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi kerak. Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kera
Berilganlarni tasvirlash bosqichlari.
3.Berilganlar tuzilmasini klassifikatsiya qilish.
Berilganlarni abstrakt toifalari.
Ma’ lumotlarni abstrakt toifalari Umuman olganda toifalar o‘zgaruvchi yoki ifoda qabul qilishi mumkin bo‘lgan qiymatlar to‘plami orqali tavsiflanadi. Ko‘plab dasturlash tillarida ma’lumotlar standart va foydalanuvchi tomonidan beriladigan toifalarga ajratiladi. Ma’lumotlarni standart toifalariga quyidagi 5 ta tur o‘zgaruvchilari kiradi: a) butun (INT); b) haqiqiy (FLOAT) ; c) mantiqiy (BOOL); d) belgili (simvol) (CHAR);
ko‘rsatkichli (*). Foydalanuvchi tomonidan aniqlanadigan toifalar esa: a) sanaladigan; b) diapazonli (oraliqli)
Yarimstatik berilganlar tuzilmalari.
Yarimstatik ma‟lumotlar tuzilmasi
Yarimstatik ma‟lumotlar tuzilmasini quyidagicha tavsiflash mumkin:
|
„zgaruvchan
|
uzunlikka
|
ega
|
va
|
uni
|
o„zgartiruvchi
|
oddiy
|
funksiyalariga
|
-
o ega;
-
tuzilmaning uzunligini o„zgartirish ma‟lum bir chegarada, ya‟ni qandaydir
bir maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin;
Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo„lsak, u holda chiziqli ro„yhat munosabati bilan bog„langan ma‟lumotlar ketma-ketligi tushuniladi. Xotirada yarimstatik ma‟lumotlar tuzilmasini fizik jihatdan tasvirlaydigan bo„lsak, bu xotirada slotlarning oddiy ketma-
ketligidir, ya‟ni har bir
element xotirada navbatdagi slotlarda joylashadi. Yarimstatik MTni fizik tasvirlashning yana bir ko„rinishi bir tomonlama bog„langan ro„yhat (zanji r)
ko„rinishida ifodalash mumkin, ya‟ni bunda har bir navbatdagi elementning adr esi
7.
34
cheklanish unchalik qattiq qo„yilmaydi. Bunday tuzilmalarga – navbat, stek, dek va satrlar kiradi.
joriy elementda ko„rsatiladi. Bunday tasvirlashda tuzilmaning uzunligiga
5. Yarimstatik berilganlar tuzilmalari
Yarimstatik ma'lumotlar tuzilmasi. Dek, xossalari.1.Yarimstatik ma’lumotlar tuzilmasiYarimstatik ma’lumotlar tuzilmasini quyidagicha tavsiflash mumkin:-o‘zgaruvchan uzunlikka ega va uni o‘zgartiruvchi oddiy funksiyalariga ega;-tuzilmaning uzunligini o‘zgartirish ma’lum bir chegarada, ya’ni qandaydirbir maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin;Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo‘lsak, u holdachiziqli ro‘yhat munosabati bilan bog‘langan ma’lumotlar ketma-ketligitushuniladi. Xotirada yarimstatik ma’lumotlar tuzilmasini fizik jihatdantasvirlaydigan bo‘lsak, bu xotirada slotlarning oddiy ketma-ketligidir, ya’ni har birelement xotirada navbatdagi slotlarda joylashadi. Yarimstatik MTni fiziktasvirlashning yana bir ko‘rinishi bir tomonlama bog‘langan ro‘yhat (zanjir)ko‘rinishida ifodalash mumkin, ya’ni bunda har bir navbatdagi elementning adresijoriy elementda ko‘rsatiladi. Bunday tasvirlashda tuzilmaning uzunligigacheklanish unchalik qattiq qo‘yilmaydi. Bunday tuzilmalarga –navbat,stek, dekvasatrlarkiradi.Bunday tuzilma uzunliklari oldindan beriladi (statiklik sharti), lekintuzilmani tashkil etuvchi elementlar soni dastur bajarilishi mobaynida vaqtga varo‘yxat uzunligiga bog‘liq ravishdao‘zgarib turishi mumkin
Stek tuzilmasi va uni dasturda amalga oshirish, ustida amal bajarish\
Stek Stek deb shunday strukturaga aytiladiki, stekka kelib tushgan oxirgi elementga birinchi bo’lib xizmat ko’rsatiladi va stekdan chiqariladi. Mazkur ko’rinishdagi xizmat ko’rsatishni LIFO (Last input-First output, ya’ni oxirgi kelgan – birinchi ketadi) nomlash qabul qilingan. Stek bir tomondan ochiq bo’ladi Masalan, Korobkaga taxlangan disklar, tagma-tag qo'yilgan tarelkalar va hokazo. Steklar asosan arifmetik ifodali masalalarni tahlil qilishda, perebor (ajratish) li masalalarda hamda graflardagi algoritmlarda ishlatiladi. Stek (misol) Misol.
Stek 4 ta sondan tashkil topgan bo’lsin. Ular o’z navbatida 0, 1, 2 va 3 bilan raqamlangan. h = 4 ga teng, ya’ni stekda 4 ta son bor va keyingi qo’shilayotgan sonni o’rni stek massivida 4
bo’ladi. Stekni massiv orqali quyidagicha tasvirlash mumkin: Stek (misol) Stek boshiga
element qo’shish uchun qiymatni yozamiz va h ko’rsatkichni oshiramiz: a[h ++] = k; Stekga qiymati k=9 sonini qo’shish jarayonini quyidagicha grafik ko’rinishda tasvirlash mumkin: Stek (misol) k = a[ -- h]; Stek boshidan elementni chiqarish uchun teskari amaldan foydalanish lozim: Bo’sh stekning boshidagi ko’rsatkichi h = 0 ga teng. Massivga element qo’shish va o’chirish davomida stek boshi massiv bo’ylab ko’chib turadi. Stek Universal
stek har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir Stek tuguni ro’yxat tugunidan farqi shundaki, o’zidan oldingi tugun adresini saqlovchi ko’rsatkich ishlatilgan. struct slist_node { void* info; struct slist_node* pred; }; Stek Stek o’zi
alohida struktura sifatida kiritilgan stackda end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni. struct stack { struct slist_node* end; int size; int width; }; Stek (asosiy funksiyalar) void pop(struct stack*p) – stek oxiridagi elementni o’chirish. void push(struct stack*p, void* val) –stek oxiriga element qo’shish. Bu yerda val
kiritilayotgan ma’lumotga ko’rsatkich. char* top(struct stack p) – stek oxiridagi tugun axborot qismiga ko’rsatkich qaytarish. int empty(struct stack p) – stek bo’shligini tekshirish.
int size (struct stack p) – stek elementlari soni. Bundan tashqari stekni inisiallash uchun quyidagi sarlavhali funksiya kiritilgan void ini_stack (struct stack* p, int n) - n kiritilayotgan ma’lumotlar hajmi. Stek (misol) Misol. 0156 Uzunligi N ga teng, aylanali, kvadratli va figurali qavslardan tashkil topgan ketma-ketlik berilgan. Shu berilgan ketma-ketlikka sonlar va arifmetik amallar qo’shish yordamida to’g’ri ifoda hosil qilish mumkinmi yo’qligii aniqlovchi dastur tuzing. (1 <= N <= 100 000). Kiruvchi ma'lumotlar: Birinchi qatorda qavslar soni N berilgan. Ikkinchi qatorda esa- (, ), [, ], {, } to’plamdan olingan N ta simvollar ketma-ketligi
berilgan. Chiquvchi ma'lumotlar: Agar to’g’ri ifoda hosil qilib bo’lsa "Yes", aks holda "No" so’zini chiqaring.
Navbat tuzilmasi va dasturda ifodalanishi, ustida amal bajarilishi
Navbat Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi. Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi. Navbat bizga nima uchun kerak! ! Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur. Navbat qanday ishlaydi! ! Navbat Biz hammamiz magazinda navbatga turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat. Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori). Klassik navbatni ko’rib chiqamiz: birinchi kelgan birinchi ketadi (FIFO – first input, first output) Navbat har ikkala tomondan ochiq bo’ladi. Navbat Universal navbat har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir: struct slist_node { void* info; struct slist_node* next; }; struct que { struct slist_node* beg; struct slist_node* end; int size; int width; }; Bu yerda beg birinchi tugunga ko’rsatkich, end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni Navbat (asosiy funksiyalar) void pop(struct que*p) – navbat oxiridagi elementni o’chirish. void push(struct que*p, void* val) –navbat boshiga element qo’shish. Bu yerda val kiritilayotgan ma’lumotga ko’rsatkich. char* top(struct que p) – navbat boshidagi tugun axborot qismiga ko’rsatkich qaytarish. int empty(struct que p) – navbat bo’shligini tekshirish. int size (struct que p) – navbat elementlari soni.
Bundan tashqari navbatni inisiallash uchun quyidagi sarlavhali funksiya kiritilgan. void ini_que(struct que* p,int n) – Bu yerda n kiritilayotgan ma’lumotlar hajmi.
Deklar. Ustida amal bajarish.
|
| |
