Microsoft Word malumotlar tuzilmasi va algoritimlash mustaqil ishi docx
Download 0.72 Mb. Pdf ko'rish
|
Zehniddin
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI “KOMPYUTER INJINIRINGI” FAKULTETI “AXBOROT TEXNOLOGIYALARI” KAFEDRASI KI 21-02 GURUH TALABASI XASANOV ZEHNIDDINNING MALUMOTLAR TUZILMASI VA ALGORITIMLAR FANIDAN 1-MUSTQAIL ISHI MAVZU: Bir bog‘lamli ro‘yxatlar ustida amllar va ularning algoritmlari Tekshirdi; Isroilov.SH SAMARQAND — 2022 Mavzu : Bir bog‘lamli ro‘yxatlar ustida amallar va ularning algoritmlari Bog’lamli ro'yxat - bu chiziqli ma'lumotlar strukturasi bo'lib, uning elementlari qo'shni joyda saqlanmaydi. Bu shuni anglatadiki, bog’lamli ro'yxatda "tugunlar" deb nomlanuvchi alohida va kuolalar mavjud bo'lib, ular yaratilgan ma'lumotlarni va ro'yxatdagi boshqa tugunga havolani o'z ichiga oladi. Bir bog’lamli ro'yxat. Bir bog’lamli ro'yxat bir nechta tugunlardan iborat bo'lib, ularning har biri a) ma'lumotlar va b) keyingi tugunga havolani o'z ichiga oladi. 1-rasm. Bir bog’lamli ro'yxat. Yuqoridagi rasmda biz bog’lamli ro'yxatning tartibini ko'rishimiz mumkin. Chapdan boshlab va o'ngga qarab, biz ro'yxatning sarlavhasida ma'lumotlar va keyingi tugunga ko'rsatgich borligini ko'ramiz. Ushbu naqsh ro'yxatning oxirigacha davom etadi, bu erda u tugun emas. NULL qiymati ro'yxat tugaganligini bildiradi. Bir bog’lamli ro'yxat yaratish uchun quyidagi kodni ko'rib chiqing. class tugun: #tugun obyekti def init(self,data): self.data=data self.next=None class royxat: #bog\'langan royxat def init(self): self.head=None def printList(self): temp =self.head while temp: print(temp.data) temp =temp.next def push(self,new_data): #list boshiga tugun qo'shish new_tugun =tugun(new_data) #birinchidagi elementni 2-ga o'tgazamiz new_tugun.next=self.head #yangi tugunni list boshiga qo\'yamiz self.head =new_tugun def insert_after(self,prev_node,new_data): #biror tugundan keyin tugun qo'shish if prev_tugun is None: print('Tugun mavjud emas') #yangi tugun qoshamiz new_tugun =tugun(new_data) #yangi tugunni keyingi tugunga bog'laymiz new_tugun.next=prev_tugun.next Bir bog’lamli ro’yhat boshidan elementni o’chirish Ro‗yhatda birinchi element info informatsion maydonidagi ma‘lumotni esda saqlab qolib uni ro‗yhatdan o‗chiramiz (2-rasm). 2-rasm. Ro‗yhat boshidagi elementni o‗chirish Yuqorida aytilganlarni amalga oshirish uchun quyidagi ishlarni bajarish lozim: a. o‗chirilayotgan elementni ko‗rsatuvchi p ko‗rsatkich kiritish: p=lst; b. p ko‗rsatkich ko‗rsatayotgan element info maydonini qandaydir x o‗zgaruvchida saqlash: x=p->info; c. lst ko‗rsatkichni yangi ro‗yhat boshiga ko‗chirish: lst=p->ptr; d. p ko‗rsatkich ko‗rsatayotgan elementni o‗chirish: delete(p); Natijada 3- rasmdagi ko‗rinishga ega bo‗lamiz. 3-rasm. Ro’yhatning natijaviy ko‗rinishi Endi shu algoritmni C++ tilidagi realizatsiyasini ko„rib chiqsak. Node* p = new Node; if (lst == NULL){ cout<<"ro'yhat bo'sh"; system("pause"); system("CLS"); } else { p = lst; lst = p->next ; delete(p); } 3. Elementni ro‗yhatga qo‗shish Berilgan ro’yhatda p ko‗rsatkich ko‗rsatayotgan elementdan keyin informatsion maydoni x bo‗lgan elementni qo‗yamiz (4-rasm). 4-rasm. Ro‗yhatga yangi element qo‗shish Aytilganlarni amalga oshirish uchun quyidagi amallarni bajarish lozim: a. q ko‗rsatkich ko‗rsatuvchi bo‗sh elementni yaratish: Node *q=new Node; b. Yaratilgan element informatsion maydoniga x ni kiritish: q->info=x; c. q elementni p elementdan keyingi element bilan bog‗lash. q->ptr=p->ptr – yaratilgan element ko‗rsatkichiga p element ko‗rsatkichini o‗zlashtirish. p element bilan q elementni bog‗lash . p->ptr=q – bu amal p elementdan keyingi element q ko‗ rsatkich murojaat qilgan element bo‗lishini anglatadi. Natijada quyidagi rasmdagidek ko‗rinishga ega bo‗lamiz. 5-rasm. Natijaviy ro‗yhat ko‗rinishi Endi shu algoritmni C++ tilidagi realizatsiyasini ko‗rib chiqsak. Node * p = lst; Node * q = new Node; int numb = -1; cout<<"son kiriting: "; cin>>numb; q->number = numb; int k; cout<<"nechta elementdan keyin kiritasiz k="; cin; >>k; for(int i=0;inext; q->next = p->next; p->next = q; 4. Bir bog’lamli ro’yhatdan elementni o’chirish Ro‗yhatda p ko‗rsatkich ko‗rsatayotgan elementdan keyingi elementni o‗chiramiz (6-rasm). 6-rasm. Ro‗yhat o‗rtasidan element o‗chirish Buni ro‗yobga chiqarish uchun quyidagi ishlarni amalga oshirish lozim: a) O‗chirilayotgan elementni ko‗rsatuvchi q ko‗rsatkichni kiritish. b. q=p->ptr; p elementni q elementdan keyingi element bilan bog‗lash. p->ptr=q->ptr; b. O‗chirilayotgan element info maydonidagi informatsiyani yodda saqlash (agar zarur bo‗lsa) k=q->info; b. q ko‗rsatkich ko‗rsatayotgan elementni o‗chirish. c. delete(q) d. Natijada ro‗yhat quyidagi ko‗rinishga ega bo‗ladi: 6-rasm. Natijaviy ro‗yhat ko‗rinishi Shu algoritm dasturi: Node* p = lst; Node* q = new Node; int k; cout<<"k="; cin>>k; for(int i=0;i<="" p=""> p=p->next; q = p->next; p->next = q->next; delete(q); Xulosa Bu mustaqil ishining asosiy maqsadi dinamik ma’lumotlar tuzilmasi haqida ma’lumot berish.Men bu mustaqil ishda yuqorida ularni yoritishga qay tartibda ishlatilishi,ularning tarkibiga nimalar kiritilishi haqida ma’lumot berdim.Qisqacha b u tuzulma haqida ma’lumot beradiga bo’lsam biz biror ma’lumotlar olsak uni joylashtirganda xotirada qay tartibda joylashishi va albatta hajmi o’zgarish o’zgarmasligiga qarab xar-xil tuzulmalar mavjud.Dinamik ma’lumotlar tuzulmasini joylashtirganimizda static tuzulmasidan farqli ravishda uning hajmini o’zgartirishimiz mumkin(kamaytirishimiz yoki qo’shishimiz yoki batamom o’chirvorishimiz mumkin).Uning albatta tur xil avzallilari va kamchiliklari mavjud. Foydalanilgan adabiyotlar ro’yxati: 1. Adam Drozdek. Data structures and algorithms in C++. Fourth edition. 2013. 2. Н.А.Литвиненко. Технология программирования. ―БХВ Петербург‖ Санкт-Петербург. 2012 г. 3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Анализ, Структуры данных, Сортировка, Поиск//К.: Изд. «ДиаСофт», 2007 4. Ma‘ruza matnlari. Carnegie Mellon University – CORTINA. 2010. 15- 121 Introduction to Data Structures, (http://www.cs.cmu.edu/~tcortina/15- 121sp10/lectures.html) Download 0.72 Mb. Do'stlaringiz bilan baham: 
|