O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
SWD013-guruh talabasi
Xoltoʻrayeva Yulduzning
“ Malumotlar tuzilmasi va algoritmlar” fanidan tayyorlagan
MUSTAQIL ISHI
O’qituvchi;Abarova M.
Mavzu:Bir bog’lamli ro’yxatlar ustida amallar va ularning algoritmlari
Reja:
1.Bog’langan ro’yxatlar.
2.Chiziqli bog’langan ro’yxatlar.
3. Bir bog’lamli va ikki bog’lamli ro’yxatlar.
Bog'langan ro'yxat - ketma-ketlikdagi tugunlar guruhidan iborat bo'lgan juda tez-tez ishlatiladigan chiziqli ma'lumotlar tuzilmasi. Har bir tugun o'z ma'lumotlariga va keyingi tugunning manziliga ega, shuning uchun zanjirga o'xshash tuzilma hosil qiladi. Bog'langan ro'yxatlar daraxtlar va grafiklarni yaratish uchun ishlatiladi.
Bog'langan ro'yxatlarning afzalliklari:
-Ular dinamik xarakterga ega bo'lib, kerak bo'lganda xotirani ajratadi.
-Qo'shish va o'chirish operatsiyalari osongina amalga oshirilishi mumkin.
-Stacks va navbatlar osongina bajarilishi mumkin.
-Bog'langan ro'yxat kirish vaqtini qisqartiradi.
Bog'langan ro'yxatlarning kamchiliklari:
-Ko'rsatkichlar saqlash uchun qo'shimcha xotira talab qilganligi sababli xotira behuda ketadi.
-Hech qanday elementga tasodifiy kirish mumkin emas; u har bir tugunga ketmaket kirishi kerak.
-Bog'langan ro'yxatda teskari o'tish qiyin.
Bog'langan ro'yxatlarning ilovalari:
Bog'langan ro'yxatlar steklarni, navbatlarni, grafiklarni va boshqalarni amalga oshirish uchun ishlatiladi.
Bog'langan ro'yxatlar ro'yxatning boshiga va oxiriga elementlarni kiritish imkonini beradi.
Bog'langan ro'yxatlarda biz o'lchamni oldindan bilishimiz shart emas.
Bog'langan ro'yxatlar turlari:
Bog'langan ro'yxatning 3 xil ilovalari mavjud ular:
1.Yagona bog'langan ro'yxat
2.Ikki marta bog'langan ro'yxat
3.Doiraviy bog'langan ro'yxat
Chiziqli ro’yxatlarda elementlar orasidagi bog’liklik qatiy tartiblangan bo’lib,element ko’tsatgichi o’zidan navbatdagi yoki oldingi element adresini o’z ichiga oladi.
Chiziqli ro’yxatga misol
Boglangan ro’yxatlar ustida quydagi amallarni bajarish mumkin;
-ro’yxarga element qo’shish,
-ro’yxardan element o’chirish,
-ro’yxarda element qidirish,
-ro’yxar elementlarini chop etish mumkin.
Ro’yxatning istalgan elementini o’chirish,ixtiyoriy joyiga element qo’shish mumkin.
Agar ro’yhat elementlari (tuguni) faqatgina bitta ko’rsatkichlar maydoniga ega bo’lsa, u holda bunday tuzilmaga bir bog’lamli yoki bir tomonlama yo’naltirilgan ro’yhat deyiladi.
-Ro’yhat elementlari garchi ketma-ket tuzilmani tashkil etsada, ular xotirada tartibsiz joylashgan bo’lishi mumkin.
-Ro’yhat elementlariga murojaat faqat ro’yhat boshidan amalga oshiriladi. Teskari aloqa yo’q.
Umuman olganda, ikki bog’lamli ro’yhat bu elementlari soni bir xil, faqatgina o’zaro teskari ketma-ketlikda yozilgan ikkita bir bog’lamli ro’yhatdir.
Bir va ikki bog’lamli ro’yhatlarni e’lon qilish
Bir bogʼlamli roʼyxat tuzilmasi:
struct Node {
BT inf;
Node* ptr;
};
Ikki bogʼlamli roʼyxat tuzilmasi:
struct Node {
BT inf;
Node* next;
Node* prev;
};
*Ro'yhat oxiriga element qo'shish
Node* p = new Node;
cin>>numb;
p->info = numb;
p->next = NULL;
if (Lst == NULL)
{ Lst = p;
lastPtr = p;
}
else { lastPtr->next = p;
lastPtr = p;
}
*Ro'yhat boshidan element o‘chirish
Node* p = new Node;
if (lst == NULL)
cout<<"ro'yhat bo'sh";
else {
p = lst;
lst = p->next ;
delete(p);
}
*Ro'yhatdan elementni qidirish
Node* Find(Node *Lst, int x)
{
Node *P=Lst;
while(P)
if (P->inf==x) return P;
else P = P->ptr;
return 0;
}
*Ro'yhat elementlarini ekranga chiqarish
void print(Node *Lst)
{
Node* P = Lst;
while(P) {
cout <<" "<< P->inf<<"-> ";
P = P->ptr;
}
cout << endl;
}
Yangi ro’yxat hosil qilish va unga n ta element kiritish amalini bajaramiz. Buning uchun List sinfi
ichida push_back(x) – elementlarni ro’yxat oxiriga qo’shish funksiyasini yaratamiz. Buning uchun yangi element p uchun hotiradan joy ajratamiz.
Node *p=new Node()
va uning info maydiniga x ni kiritamiz. Yangi element ro’yxat oxiriga kiritilayotgani sababli uning ko’rsatkichli maydoniga NULL yoziladi.
p->info=x;
p->ptr=NULL;
Agar ro’yxat bo’sh bo’lsa, ya’ni lst=NULL bo’lsa, p yangi element ro’yxat
boshiga joylashtiriladi va oxirgi element sifatida ham aynan yangi element ro’yxat element belgilab qo’yiladi.
lst=p;
last=p;
Aks holda, ya’ni ro’yxat bo’sh bo’lmasa, p elementni oxirgi element lastdan keyin joylanadi va p ni oxirgi kelib tushgan element sifatida belgilab
qo’yiladi.
int puch_back(int x){
Node *p=new Node();
p->info=x;
p->ptr=NULL;
if(lst==NULL){
lst=p;
last=p;
}
last->ptr=p;
last=p;
}
Agar ro’yxat bo’sh bo’lsa, ya’ni lst=NULL bo’lsa, p yangi element ro’yxat
boshiga joylashtiriladi va oxirgi element sifatida ham aynan yangi element ro’yxat element belgilab qo’yiladi.
lst=p;
last=p;
Aks holda, ya’ni ro’yxat bo’sh bo’lmasa, p elementni oxirgi element lastdan keyin joylanadi va p ni oxirgi kelib tushgan element sifatida belgilab
qo’yiladi.
int puch_back(int x){
Node *p=new Node();
p->info=x;
p->ptr=NULL;
if(lst==NULL){
lst=p;
last=p;
}
last->ptr=p;
last=p;
}
Ushbu funksiyalardan foydalanib, yangi ro’yxat hosil qilish va ekranga chiqarish asosiy dastur tanasi kodini keltiramiz.
int main(){
List L1;
int n; cin>>n;
int i=0, k;
while(icin>>k;
L1.push_back(k);
i++;
}
cout<<"1-roy'xat elementlari: ";
L1.print();
return 0;
}
Ro’yxatga yangi elementni kiritsg algoritmlari.
Yangi elementni yaratib ro’yhatga quyidagi qadamlar bilan ro’yhat oxiriga qo’shiladi:
- Yangi element yaratiladi, uning 3 ta maydoni e’lon qilinadi.
- info maydoniga el sonini kiritamiz;
- next maydoniga NULL qiymat kiritamiz;
- prev maydoniga tail ni qiymatini yozib qo’yamiz, chunki bu element oxirgi turgan elementdan keyinga qo’shiladi va prev maydoni bilan o’zidan oldingi elementni ko’rsatib turishi kerak.
Undan oldin keladigan element (xozircha oxirgi element tail da ko’rsatilyapti) adresi tail da saqlanyapti.
- Yangi element kiritilgach, tail ko’rsatkichni ushbu yangi elementga
o’rnatamiz. Chunki endi oxirgi element bo’lib, yangi element hisoblanadi.
- Qachonki, yana yangi element kiritiladigan bo’lsa, boya kiritilgan elementning next maydonidagi NULL ni o’rniga yangi kiritilayotgan elementning adresi yoziladi.
Bog’lamli ro’yxat dasturini tuzish uchun quyidagi kodlarni foydalanishingiz mumkin:
# Bog'lamli ro'yxat dasturi
class BoglamliRoyxat:
def __init__(self):
self.boglamli_royxat = []
def qo'shish(self, element):
self.boglamli_royxat.append(element)
def o'chirish(self, element):
if element in self.boglamli_royxat:
self.boglamli_royxat.remove(element)
else:
print(f"{element} ro'yxatda mavjud emas!")
def ko'rish(self):
if len(self.boglamli_royxat) == 0:
print("Ro'yxat bo'sh!")
else:
for element in self.boglamli_royxat:
print(element)
```
Ushbu kod bir bog'lamli ro'yxat dasturini yaratadi. Bog'lamli ro'yxatning asosiy tuzilishi `__init__` metodi orqali amalga oshiriladi.
Ro'yxatga element qo'shish uchun `qo'shish` metodi ishlatiladi. Ushbu metot parameter sifatida yangi elementni olib, uni ro'yxatga qo'shadi.
Ro'yxatdan element o'chirish uchun `o'chirish` metodi foydalaniladi. Metotga o'chirish kerak bo'lgan element ni beriladi va agar element ro'yxatda bo'lsa uni o'chirib, aks holda "Element ro'yxatda mavjud emas!" xabarni chiqaradi.
Ro'yxatni ko'rish uchun `ko'rish` metodi ishlatiladi. Metod ro'yxat bo'sh bo'lsa "Ro'yxat bo'sh!" xabarni chiqaradi, aks holda ro'yxatdagi har bir elementni bitta bitta chiqaradi.
Bog'lamli ro'yxat obyekti yaratish uchun quyidagi kodni ishga tushiring:
royxat = BoglamliRoyxat()
Ro'yxatga element qo'shish uchun quyidagi kodlarni ishga tushiring:
royxat.qo'shish("Element 1")
royxat.qo'shish("Element 2")
Ro'yxatdan element o'chirish uchun quyidagi kodlarni ishga tushiring:
royxat.o'chirish("Element 2")
Ro'yxatni ko'rish uchun quyidagi kodlarni ishga tushiring:
royxat.ko'rish().
Amaliy qism: Bir bog’lamli ro’yxatlarga misol.
Ro‘yhat yaratamiz, Ro‘yhatga N ta haqiqiy son kiritamiz.Ro‘yhatning barcha musbat elementlarini yig’indisini ro‘yhat oxiriga qo’shish dasturini tuzimiz.
|
