İki bağlantılı liste için nasıl bir takas işlevi yaratırsınız?

Question

İki bağlantılı bir liste için bir takas işlevi oluşturma sorunları yaşıyorum. Ben sadece listeyi değiştirmek için "rewire" yapmak istiyorum (Bu kolay olacağını biliyorum). Bu geçici öğeyi back<-p->front tutmaya çalıştım, böylece q = bu cepheye ve arkaya ayarlayabilirdim, ancak geçici öğe p ile birlikte değişir. Bu öğeleri geçici bir öğe olmadan nasıl değiştirebilirim veya geçici öğeyi nasıl davranacağımı nasıl anlarım?

void DLinkedList::swap(Item *p, Item *q) 
{ 
    Item* temp = p; 
    p->next = q->next; 
    p->pre = q->pre; 
    if (p->next != NULL) 
     p->next->pre = p; 
    if (q->next != NULL) 
     q->next->pre = q; 
    q->next = temp->next; 
    q->pre = temp->pre; 
    if (p->pre != NULL) 
     p->pre->next = p; 
    if (!q->pre == NULL) { 
     q->pre->next = q; 
    } 
    cout << "- The items " << p->val << " & " << q->val << " were swapped -" << endl; 
} 

Answer 1

Burada resimsel formda durum:

+----------+  +----------+  +----------+ 
| before_p | <-> |  p | <-> | after_p | 
+----------+  +----------+  +----------+ 

+----------+  +----------+  +----------+ 
| before_q | <-> |  q | <-> | after_q | 
+----------+  +----------+  +----------+ 

sahip problemi p bir temp işaretçi tasarrufu aslında p içindeki işaretçileri kopyalamak olmamasıdır. Yani onların üzerine yazdığınızda, başın belada.

Şimdi, resimdeki "önce" ve "sonra" öğeleri gerçekten istediğiniz şeydir. Sadece bunları kopyalamak ve sonra mantığı yapmak çok daha kolay. Aşağıdaki kod ne kadar net bak: Eğer şey yapmadan önce

Item * before_p = p->pre; 
Item * before_q = q->pre; 
Item * after_p = p->next; 
Item * after_q = q->next; 

// Relink before and after nodes 
if(before_p) before_p->next = q; 
if(before_q) before_q->next = p; 
if(after_p) after_p->pre = q; 
if(after_q) after_q->pre = p; 

// Relink nodes themselves 
p->pre = before_q; 
q->pre = before_p; 
p->next = after_q; 
q->next = after_p; 

Ayrıca aklı testi isteyebilir:

if(p == q || !p || !q) return; 

Ve son olarak, kafasına bir işaretçi sürdürmek durumunda Listenizde bir yer değişiyor ve bu değiştirilen öğelerden biri oluyor, sonra güncellemeyi unutmayın *. Aynı

if(head == p) head = q; 
else if(head == q) head = p; 

(*) tail gibi diğer işaretçiler için de geçerli.