Kompyuter injenering kafedrasi Kompyuter injenering fakulteti Sirtqi “Ma'lumotlar tuzilmasi va algoritmlar” fanidan

“Ma'lumotlar tuzilmasi va algoritmlar” fanidan

1-Mustaqil ish

Reja:

1. 
   Ikki bog’lamli ro’yhatlar va ular ustida amal bayarish algoritmlari
   
2. 
   Stek, navbat va deklarni bog’langan ro’yhat ko’rinishida ifodalash
   
3. 
   Halqasimon bog’langan ro’yhatlar.
   

Ikki bog'lamli ro'yhat

Ko’pgina masalalarni hal qilishda bir tomonga yo’naltirilgan ro’yhatlardan foydalanish ma'lum bir qiyinchiliklarni keltirib chiqaradi. Sababi, bir tomonga yo’naltirilgan ro’yhatda har doim bironta elementdan ro’yhatning so’ngi elementi tomoniga harakatlanish mumkin. Lekin ko’pgina masalalar hal qilinayotganda ma'lum bir elementni qayta ishlash uchun undan oldin kelgan elementga muroyaat qilish zarurati paydo bo’ladi. Ushbuholatda berilgan elementdan oldin kelgan elementga muroyaat qilish bir bog’lamli ro’yhatda noqulay va ancha sekin amalga oshiriladihamda uni amalga oshirish algoritmi murakkablashadi.

Ushba noqulayliklarni yo’qotish maqsadida ro’yhatning har bo’g’imiga yana bitta maydonqo’shiladi. Ushbu maydon qiymati o’zidan oldin kelgan bo’g’imga muroyaatdan iborat bo’ladi. Ushba ko’rinishdagi elementlardan tashkil topgan dinamik tuzilmaga ikkitomonlama yo’naltirilgan yokiikki bog’lamli ro’yhat deyiladi.

Ikki bog’lamli ro’yhatning har bir elementi ikkita ko’rsatkichga ega. Bittasi o’zidan oldingi elementga ko’rsatadi (teskari), ikkinchisi navbatdagi elementni ko’rsatadi (to’g’ri) (chizma).

Ikki bo’g’lamli ro’yhat ustidagi amallar:

• 
  Ro’yhat elementini yaratish;
  

• 
  ro’yhatda elementniqidirish;
  

• 
  Ro’yhatning ko’rsatilgan yoyiga elemental qo’yish;
  

• 
  berilgan elementni ro’yhatdan o’chirish.
  

Ikki bog’lamli ro’yhat oxiridan elementni o’chirish algoritmi

• 
  
  O’chirilayotgan elementni prev maydonidagi adres bilan oldingi turgan element olinadi;
  

• 
  O’chirilayotgan elementni xotiradan tozalash mumkin.