7-ma’ruza: Graflar va daraxtlar Reja: Chiziqli ro’yxatlar Chiziqsiz ro’yxatlar

Chiziqli bir bog’lamli ro’yhatlar va ular ustida amal bajarish algoritmlari
Endi shu belgilashlar orqali ro‘yhat hosil qilamiz.
Node * p = new Node;
int numb = -1;
cout<<"son kiriting: ";
cin>>numb;
p->info = numb;
p->next = NULL;
if (lst == NULL) { lst = p; last = p; }
else{ last->next = p; last = p; }
Bir bog‘lamli ro‘yhatlar ustida amallar bajarish algoritmlari
1. Bir bog‘lamli ro‘yhat boshiga element qo‘yish
1-rasm. Bir bog‘lamli chiziqli ro‘yhat tuzilishi
1-rasmdagi ro‘yhat boshiga informatsion maydoni D o‘zgaruvchi bo‘lgan element qo‘yamiz. Ushbu ishni amalga oshirish uchun quyidagi amallarni bajarish lozim bo‘ladi:
a) p ko‘rsatkich murojaat qiladigan, bo‘sh element yaratish (2-rasm).
2-rasm. Yangi element hosil qilish
Bir bog‘lamli ro‘yhatlar ustida amallar bajarish algoritmlari
b) Yaratilgan element informatsion maydoniga D o‘zgaruvchi qiymatini o‘zlashtirish (3-rasm).
3-rasm. Yangi element info maydoniga qiymat kiritish
c) Yangi elementni ro‘yhat bilan bog‘lash: p->ptr=lst;
(shu holatda yangi element va lst – ro‘yhat boshini ko‘rsatyapti)
d) lst ko‘rsatkichni ro‘yhat boshiga ko‘chirish (4-rasm). lst=p; va nihoyat:
4-rasm. Ro‘yhat boshiga element qo‘shish
Bir bog‘lamli ro‘yhatlar ustida amallar bajarish algoritmlari
Endi shu algoritmni C++ tilidagi realizatsiyasini ko‘rib chiqamiz.
Node * p = new Node;
int numb = -1;
cout<<"son kiriting: ";
cin>>numb; p->info = numb;
if (lst ==NULL){ p->next = NULL; lst = p; }
else { p->next = lst; lst = p;}
Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi
Agar tuzilmani tashkil etuvchi elementlar bog’liqligi qatiy tartiblanmagan bo’lsa, u holda bunday tuzilmaga chiziqsiz malumotlar tuzilmasi deb ataladi. Chiziqsiz malumotlar tuzilmasida elementlar orasidagi munosabatlar ixtiyoriy bo’lishi mumkin. Chiziqsiz tuzilmani 3 ta farqli belgisi mavjud:

• 
  tuzilmani xar bir elementi boshqa ixtiyorij elementga murojaat qilish mumkin;
  
• 
  tuzilmani berilgan elementiga mazkur tuzilmaning ixtiyoriy sondagi elementi murojaat qilishi mumkin;
  
• 
  murojaatlar og’irlikga, yani murojaatlar ierarxik ko’rinishga ega bo’lishi mumkin.
  

Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi

Chiziqsiz malumotlar tuzilmasi klassifikatsiyasi:

• 
  ro’yxatlar: chiziqsiz ikki bog’lamli; ko’p bog’lamli;
  
• 
  daraxtlar: binar daraxtlar; ko’po’lchamli daraxtlar;
  
• 
  graflar: yo’naltirilgan graf(orgraf);yo’naltirilmagan graf(graf); gipergraf.
  Umuman olganda daraxtni xam jo’naltirilgan graf deyish mumkin.
  Misollar.
  

1-rasm. Chiziqsiz ro’yxat va daraxt tuzilmalari
Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi
Daraxt – bu chiziqsiz bog’langan ma’lumotlar tuzilmasidir
Daraxt o’zining quyidagi belgilari bilan tasniflanadi:

• 
  daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo’q. Mazkur elementga daraxt ildizi deyiladi;
  
• 
  daraxtda ixtiyoriy elementga chekli sondagi ko’rsatkichlar yordamida murojaat qilish mumkin;
  
• 
  daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni oraliq yoki terminal (barg) bo’lishi mumkin. Yuqoridagi rasmda M1, M2 - oraliq, A, B, C, D, E - barglardir. Terminal tugunning o’ziga xos tasnifi uning shoxlari yo’qligidir.
  

Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi

Daraxt – bu chiziqsiz bog’langan ma’lumotlar tuzilmasidir
Daraxt o’zining quyidagi belgilari bilan tasniflanadi:

• 
  daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo’q. Mazkur elementga daraxt ildizi deyiladi;
  
• 
  daraxtda ixtiyoriy elementga chekli sondagi ko’rsatkichlar yordamida murojaat qilish mumkin;
  
• 
  daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni oraliq yoki terminal (barg) bo’lishi mumkin. Yuqoridagi rasmda M1, M2 - oraliq, A, B, C, D, E - barglardir. Terminal tugunning o’ziga xos tasnifi uning shoxlari yo’qligidir.