Mustaqil ish Mavzu: Bir bog‘lamli ro‘yxatlar ustida amllar va ularning algoritmlari Bajardi: Farmonov U. Guruh: tt2M21-01

Halqasimon ikki bog‘lamli ro‘yxatga element kiritish algoritmi

Yangi element yaratamiz:

Node *r= new Node;
2. Bu element informatsion maydoniga ma’lumot kiritamiz:
p->data = x ;
3. Bu elementni quyidagi rasmdagi 2-elementdan keyin qo‘shish uchun 2-element, ya’ni oxirgi element adresi kerak bo‘ladi.
Uni List ko‘rsatayotgan 1-elementning prev maydonidan olsa bo‘ladi. ya’ni
Node *LastPtr=List->prev;
Demak, oxirgi elementning adresi LastPtr da saqlanayapti.

Halqasimon ikki bog‘lamli ro‘yxatga element kiritish algoritmi

4. Oxirgi elementning next maydoniga yangi element r ni adresini o‘zlashtiramiz:

LastPtr ->next = p;

Yangi elementning prev maydoniga esa shu oxirgi elementning adresini o‘zlashtiramiz, ya’ni:

p ->prev= LastPtr;

Hozircha ro‘yxatimiz quyidagicha ko‘rinishga ega bo‘ldi:

Halqasimon ikki bog‘lamli ro‘yxatga element kiritish algoritmi

• 5. Navbatdagi qilinadigan ishimiz ro‘yxat boshi va oxirgi elementlarni o‘zaro bog‘lab qo‘yish bo‘ladi, ya’ni;

  
  
• 
  
  p->next = List;
  
• 
  
  List->prev = p;
  

• Ushbu amallardan keyin yangi elementimiz ro‘yxatga qo‘shiladi:

  
  

Algoritm dasturi

void AddList(int value){

Node *p=new Node; //создание нового элемента

p->data=value; //присвоение элементу значения

if (List==NULL) {

p->next=p; //установка указателя next

p->prev=p; //установка указателя prev

List =p; //определяется голова списка

}

else {

Node *LastPtr= List ->prev;

LastPtr->next=p;

p->prev=LastPtr;

p->next= List;

List ->prev=p;} }

Halqasimon ikki bog‘lamli ro‘yxatdan element o‘chirish algoritmi

• O‘chirilishi kerak bo‘lgan joriy element r dan oldin turgan element adresini prev ko‘rsatkichga o‘zlashtirib olamiz

  
  
• 
  
  Node *Prev=p->prev;
  

• oldin turgan elementning next maydoniga r dan keyin turgan element adresini yozamiz:

  
  
• 
  
  Prev->next=p->next;
  

• joriy elementdan keyin turgan elementni Next deb belgilab olib, uning prev maydoniga joriy elementdan oldin kelgan elementni adresini o‘zlashtiramiz:

  
  
• 
  
  Node *Next=p->nextI;
  
• 
  
  Next->prev=Prev;
  
• 
  
  delete(p);
  

• Natijada joriy r element o‘chiriladi.

  
  
• 
  
  void delete(Node *p){
  
• 
  
  Node *Prev=p->prev;
  
• 
  
  Prev->next=p->next;
  
• 
  
  Node * Next=p->next;
  
• 
  
  Next->prev=Prev;
  
• 
  
  delete(p);
  
• 
  
  }