|
Ma'lumotlar tuzilmasi va algoritmlar” fanidan
|
| bet | 1/2 | | Sana | 16.01.2024 | | Hajmi | 41,22 Kb. | | #138643 |
Bog'liq 1696313451, maxmudov doston 5-6-amaliy ish, 5-MAVZU, 4-Deformatsiyaning birgalik tenglamalari., физиканинг долзарб муаммолари маъруза матн, 2020 INFORMATIKA TESTLAR KITOBI 5-11 sinf, 1. Davlatning milliy iqtisodiyotini tartibga solishdagi ro’li ha-fayllar.org, Organik va noorganik Anarqulov, 9-sinf Informatika BSB-1 (1v) umum origin, BO\'SHLIQ, 9-sinf-ona-tili-va-adabiyot-olimpiyada-savollari(1), 10-mavzu testlar, 6-mavzu, zo\'r
O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI
"Kompyuter injiniring" fakulteti
"Axborot texnologiyalari" kafedrasi
" Ma'lumotlar tuzilmasi va algoritmlar”
fanidan
Mustaqil ish №1
Bajardi: KI-S21-04-guruh talabasi
Qodirov Z.
Qabul qildi: ABDUVAITOV A. A
SAMARQAND – 2023
Mavzu: Chiziqli konteynerlar va ularni qo‘llash. “Ro‘yxat” turdagi ma’lumotlarning abstrakt turlari va ro‘yxatlarni amalga oshirish (statik va dinamik). Ro‘yxatlar ustida amallar bajarish
Reja:
Ro'yxatlar (Lists)
Abstrakt turlar va ro'yxatlar
Ro'yxatlarni amalga oshirish (Statik va dinamik)
Chiziqli konteynerlar, ma'lumotlarni ketma-ket chiziqli tartibda saqlaydigan ma'lumot tuzilmalardir. Bu konteynerlar o'z ichiga bir nechta element olishi mumkin bo'lgan dinamik tuzilmalardir. Chiziqli konteynerlar va ularni qo'llashning umumiy tartibi quyidagicha bo'lishi mumkin:
Yagona bog'langan ro'yxat kontseptsiyasidan foydalangan holda stekni amalga oshirish uchun barcha yakka bog'langan ro'yxat operatsiyalari LIFO (oxirgidan birinchi chiqadi) stack operatsiyalari asosida bajarilishi kerak va bu bilimlar yordamida biz yakka bog'langan ro'yxat yordamida stekni amalga oshirmoqchimiz. ro'yxati.
Shunday qilib, biz birinchi bo'lib oxirgi bo'lgan stekni amalga oshirishda oddiy qoidaga amal qilishimiz kerak va barcha operatsiyalar yuqori o'zgaruvchi yordamida bajarilishi mumkin. Keling, quyidagi maqoladan Pop, Push, Peek va Display amallarini qanday bajarishni bilib olaylik :
Stack Implementation-da stek yuqori ko'rsatkichni o'z ichiga oladi. bu stekning "boshi" bo'lib, unda elementlarni surish va ochish ro'yxatning boshida sodir bo'ladi. Birinchi tugun havola maydonida nullga ega va ikkinchi tugun havolasi havola maydonida birinchi tugun manziliga ega va hokazo va oxirgi tugun manzili "yuqori" ko'rsatgichda.
Bog'langan ro'yxatni massivlardan foydalanishning asosiy afzalligi shundaki, kerak bo'lganda qisqarishi yoki o'sishi mumkin bo'lgan stekni amalga oshirish mumkin. Massivdan foydalanish massivning maksimal sig'imiga cheklov qo'yadi, bu esa stekning to'lib ketishiga olib kelishi mumkin. Bu erda har bir yangi tugun dinamik ravishda taqsimlanadi. shuning uchun toshib ketish mumkin emas.
Stack operatsiyalari:
push() : stekga yangi element qo'shing, ya'ni bog'langan ro'yxatning boshiga yangi element qo'shing.
pop() : Stackning yuqori elementini qaytaring, ya'ni bog'langan ro'yxatdan birinchi elementni o'chirib tashlang.
peek() : Yuqori elementni qaytaradi.
display(): Stackdagi barcha elementlarni chop eting.
Bosish operatsiyasi:
Tugunni ishga tushiring
Ushbu tugunning qiymatini ma'lumotlar bo'yicha yangilang, ya'ni tugun->ma'lumotlar = ma'lumotlar
Endi ushbu tugunni bog'langan ro'yxatning yuqori qismiga bog'lang
Va yuqori ko'rsatgichni joriy tugunga yangilang
Pop operatsiyasi:
Avval bog'langan ro'yxatda tugun bor yoki yo'qligini tekshiring, agar bo'lmasa, qayting
Aks holda , yuqori tugunga temp deyish uchun ko'rsatgichni qo'ying va yuqori tugunni 1 qadam oldinga siljiting
Endi bu vaqtinchalik tugunni bo'shating
Peek operatsiyasi:
Tugun bor yoki yo'qligini tekshiring, agar bo'lmasa, qayting.
Aks holda, bog'langan ro'yxatning yuqori tugunining qiymatini qaytaring
Displey ishlashi:
Vaqtinchalik tugunni oling va uni yuqori ko'rsatkich bilan ishga tushiring
Endi temp NULLga duch kelguncha o'tishni boshlang
Bir vaqtning o'zida vaqtinchalik tugunning qiymatini chop eting
Quyida yuqoridagi operatsiyalarni amalga oshirish ko'rsatilgan
// C++ program to Implement a stack
// using singly linked list
#include
using namespace std;
// creating a linked list;
class Node {
public:
int data;
Node* link;
// Constructor
Node(int n)
{
this->data = n;
this->link = NULL;
}
};
class Stack {
Node* top;
public:
Stack() { top = NULL; }
void push(int data)
{
// Create new node temp and allocate memory in heap
Node* temp = new Node(data);
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp) {
cout << "\nStack Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
bool isEmpty()
{
// If top is NULL it means that
// there are no elements are in stack
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// If stack is not empty , return the top element
if (!isEmpty())
return top->data;
else
exit(1);
}
// Function to remove
// a key from given queue q
void pop()
{
Node* temp;
// Check for stack underflow
if (top == NULL) {
cout << "\nStack Underflow" << endl;
exit(1);
}
else {
// Assign top to temp
temp = top;
// Assign second node to top
top = top->link;
// This will automatically destroy
// the link between first node and second node
// Release memory of top node
// i.e delete the node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;
// Check for stack underflow
if (top == NULL) {
cout << "\nStack Underflow";
exit(1);
}
else {
temp = top;
while (temp != NULL) {
// Print node data
cout << temp->data;
// Assign temp link to temp
temp = temp->link;
if (temp != NULL)
cout << " -> ";
}
}
}
};
// Driven Program
int main()
{
// Creating a stack
Stack s;
// Push the elements of stack
s.push(11);
s.push(22);
s.push(33);
s.push(44);
// Display stack elements
s.display();
// Print top element of stack
cout << "\nTop element is " << s.peek() << endl;
// Delete top elements of stack
s.pop();
s.pop();
// Display stack elements
s.display();
// Print top element of stack
cout << "\nTop element is " << s.peek() << endl;
return 0;
}
Chiqish
44 -> 33 -> 22 -> 11
Yuqori element 44
22 -> 11
Yuqori element 22
Vaqtning murakkabligi: O(1), barcha push(), pop() va peek() uchun, chunki biz roʻyxat boʻyicha hech qanday oʻtishni amalga oshirmayapmiz. Biz barcha operatsiyalarni faqat joriy ko'rsatgich orqali bajaramiz.
Yordamchi bo'shliq: O(N), bu erda N - stekning o'lchami
Ushbu amalga oshirishda biz bog'langan ro'yxatdagi tugunni ifodalovchi Node sinfini va stekni amalga oshirish uchun ushbu tugun sinfidan foydalanadigan Stack sinfini aniqlaymiz. Stack sinfining head atributi stekning yuqori qismiga ishora qiladi (ya'ni, bog'langan ro'yxatdagi birinchi tugun).
Ob'ektni stekga surish uchun biz berilgan element bilan yangi tugun yaratamiz va uning keyingi ko'rsatkichini stekning joriy boshiga o'rnatamiz. Keyin biz stekning boshini yangi tugunga o'rnatamiz va uni samarali ravishda stekning yangi tepasiga aylantiramiz.
Stekdan elementni chiqarish uchun biz stek boshini ro'yxatdagi keyingi tugunga (ya'ni joriy boshning keyingi ko'rsatkichi ko'rsatgan tugun) o'rnatish orqali bog'langan ro'yxatdan birinchi tugunni olib tashlaymiz. Biz asl bosh tugunida saqlangan ma'lumotlarni qaytaramiz, bu stackning yuqori qismidan olib tashlangan element.
Yagona bog'langan ro'yxat yordamida stekni amalga oshirishning afzalliklari quyidagilardan iborat:
Dinamik xotira taqsimoti : stek uchun oldindan belgilangan xotira miqdorini ajratmasdan, bog'langan ro'yxatga tugunlarni qo'shish yoki olib tashlash orqali stek hajmini dinamik ravishda oshirish yoki kamaytirish mumkin.
Xotiradan samarali foydalanish: Yakka bog'langan ro'yxatdagi tugunlar oldingi ko'rsatgichga emas, faqat keyingi ko'rsatkichga ega bo'lgani uchun ular ikki marta bog'langan ro'yxatdagi tugunlarga qaraganda kamroq xotiradan foydalanadilar.
Oson amalga oshirish : Yagona bog'langan ro'yxat yordamida stekni amalga oshirish juda oddiy va bir necha qator kod yordamida amalga oshirilishi mumkin.
Ko'p qirrali : bitta bog'langan ro'yxatlar navbatlar, bog'langan ro'yxatlar va daraxtlar kabi boshqa ma'lumotlar tuzilmalarini amalga oshirish uchun ishlatilishi mumkin.
Xulosa qilib aytganda, yakka bog'langan ro'yxat yordamida stekni amalga oshirish Python-da dinamik stek ma'lumotlar strukturasini yaratishning oddiy va samarali usuli hisoblanadi.
Haqiqiy vaqtda stack misollari:
Stacklar har xil real stsenariylarda qo'llaniladi, bunda oxirgi kiruvchi, birinchi chiquvchi (LIFO) ma'lumotlar strukturasi talab qilinadi. Bu erda steklarning real vaqtda qo'llanilishiga misollar keltirilgan:
Funksiya chaqiruvi stacki : Funktsiya dasturda chaqirilganda, qaytariladigan manzil va barcha funksiya parametrlari funksiya chaqiruvi stekiga suriladi. Stack funksiyaga qo'ng'iroq qiluvchi funksiyasini ular chaqirilgan teskari tartibda bajarishga va unga qaytishga imkon beradi.
Bekor qilish/Qayta tiklash operatsiyalari: matn muharrirlari, tasvir muharrirlari yoki veb-brauzerlar kabi ko‘plab ilovalarda bekor qilish va qayta tiklash funksiyalari stek yordamida amalga oshiriladi. Har bir harakat bajarilganda, u stekga suriladi. Foydalanuvchi oxirgi amalni bekor qilmoqchi bo'lganda, stekning yuqori elementi ochiladi va harakat teskari bo'ladi.
Brauzer tarixi: Veb-brauzerlar foydalanuvchi tashrif buyurgan sahifalarni kuzatib borish uchun steklardan foydalanadi. Har safar yangi sahifaga tashrif buyurilganda uning URL manzili stekga suriladi. Foydalanuvchi "Orqaga" tugmasini bosganida, oxirgi tashrif buyurilgan URL stackdan chiqariladi va foydalanuvchi oldingi sahifaga yo'naltiriladi.
Ifodalarni baholash : steklar ifodalarni baholash uchun kompilyatorlar va tarjimonlarda qo'llaniladi. Ifoda tahlil qilinganda, u postfiks belgisiga aylantiriladi va stekga suriladi. Keyin postfiks ifodasi stek yordamida baholanadi.
Rekursiyadagi qo'ng'iroqlar to'plami: Rekursiv funktsiya chaqirilganda, uning chaqiruvi stekga suriladi. Funktsiya o'zini bajaradi va chaqiradi va har bir keyingi qo'ng'iroq stekga suriladi. Rekursiya tugagach, stek ochiladi va dastur avvalgi funksiya chaqiruviga qaytadi.
Xulosa qilib aytganda, steklar funksiya chaqiruvlari, bekor qilish/qayta tiklash operatsiyalari, brauzer tarixi, ifodani baholash va rekursiv funksiya chaqiruvlari kabi LIFO funksiyasi talab qilinadigan ko‘plab ilovalarda keng qo‘llaniladi.
Xulosa
Dasturlashda ma'lumotlar tuzilmasi va algoritmni tuzish, bir dasturchi uchun muhim asosiy qadamlardir. Ma'lumotlar tuzilmasi, ma'lumotlarni saqlash va ularga operatsiyalar bajarishning tuzilgan usullarini taqdim etadi. Algoritm esa, bir vazifani bajarish uchun boshlang'ich nuqtadan, qanday qadam qilish, shartlar va harakatlar qanday bajarilishi lozimligini aniqlaydi.
Ma'lumotlar tuzilmasi kerakli ma'lumotlarni qanday saqlash va ularga qanday operatsiyalar bajarishni aniqlaydi. Misol uchun, ma'lumotlar tuzilmasida sonlar, matnlar, va ro'yxatlar turlarida ma'lumotlar saqlanishi mumkin. Bu ma'lumotlar ustida o'zgarishlar amalga oshirish, qo'shish, va boshqa amallarni bajarish uchun tuzilmalar taqdim etilishi mumkin.
Algoritm esa, maqsadga mos ravishda bajarilishi kerak bo'lgan amallarni tartibga solishning qanday yo'lini ko'rsatadi. Bunday qadam-qadamda yuritilayotgan algoritm, aniqlik va samarali bajarishni ta'minlaydi. Algoritmni tuzishda shartlar, sikllar, va boshqa dasturlash vositalaridan foydalanish, qanday qilib vazifani eng yaxshi bajarishni ta'minlaydi.
Barcha dasturchilar uchun muhim bo'lgan birinchi qadam, ma'lumotlar tuzilmasi va algoritmni aniq tuzish, ularga e'tibor berish va yaxshi tushuntirishdir. Bu asosiy printsip, dasturchi uchun qanday dastur yozishda ham katta yordam bera oladi.
|
| |
