Ma’lumotlar tuzilmasi va algoritmlar 9-ma’ruza: Chiziqli konteynerlar va ularni qo’llash Ma’ruza rejasi Plan lecture

Bir bog’lamli ro’yxatlar

• Bir bog’lamli ro’yxatda ko’rsatkichni o’ziga xosligi shundan iboratki, bunda faqatgina o’zidan keyin keluvchi ro’yxat elementi manzilini ko’rsatadi.
• Ro’yxatning eng so’ngi elementining ko’rsatkich maydoni bo’sh bo’ladi (NULL).
• Lst – ro’yxat boshiga ko’rsatkich.
• Umuman olganda, ro’yxat bo’sh ham bo’lishi mumkin, bu holda Lst bilan Null ustma-ust tushadi, ya’ni teng bo’ladi.
• Ro’yxat elementiga murojat faqatgina ro’yxat boshidan boshlab amalga oshiriladi, ya’ni bu ro’yxatda teskari aloqa mavjud emas.

Bir bog’lamli ro’yxatlar

• Bir bog’lamli ro’yxat tuzilmasi quyidagicha e’lon qilinadi:

struct Tnode {

int value;

Tnode *pnext;

Tnode (int val): pnext(0), value(val) {}

};

Ikki bog’lamli ro’yxatlar

• Ikki bog’lamli ro’yxatning har bir elementida ko’rsatkich maydoni ikki qismdan iborat bo’ladi. Birinchisi o’zidan oldingi elementni (teskari), ikkinchisi navbatdagi elementni ko’rsatadi (to’g’ri).
• Odatda, ikki bog’lamli ro’yxatlarni, elementlari soni bir xil bo’lgan, faqat o’zaro teskari ketma-ketlikda yozilgan ikkita bir bog’lamli ro’yxat sifatida qarash mumkin.

Ikki bog’lamli ro’yxatlar

• Ikki bog’lamli ro’yxatning tavsiflanishi:

struct Tnode {

T value;

Tnode* pnext;

Tnode* pprev;

Tnode (T val): pnext(0), pprev(0),value(val) {}

};

Bog’langan ro’yxatlar ustida bajariladigan amallar

• Ro’yxatga yangi element qo’shish;
• Ro’yxatdan elementni o’chirish;
• Ro’yxatdan elementni qidirish;
• Ro’yxat elementlarini chop etish.
• Eslatma: Ro’yxatning ixtiyoriy elementini o’chirish, ixtiyoriy joyiga yangi element qo’shish mumkin (dinamik tuzilma).
• Bog’langan ro’yxat elementlari mantiqiy tasvirlanishda yozuv kabi ifodalanadi.