在C中反向雙鏈接Deque

我很難在C中反轉我的雙鏈接deque list（只有後哨兵），我正在通過切換指針來接近它，這裏是我迄今爲止的代碼：在C中反向雙鏈接Deque

/* Reverse the deque 

param: q pointer to the deque 
pre: q is not null and q is not empty 
post: the deque is reversed 
*/ 
/* reverseCirListDeque */ 
void reverseCirListDeque(struct cirListDeque *q) 
{ 
struct DLink *back = q->backSentinel; 
struct DLink *second = q->backSentinel->prev; 
struct DLink *third = q->backSentinel->next; 

while (second != q->backSentinel->next){ 
    back->next = second; 
    third = back->prev; 
    back->next->prev = back; 
    back = second; 
    second = third; 
} 
}

但它似乎沒有工作，我一直在用雙端隊列，看起來像這樣測試它：1，2，3 輸出爲：3這個過程似乎搞亂實際值的數字。即。 2變爲2.90085e-309 ...我認爲指針切換已經搞亂了，但我找不到問題。即使這並不意味着我的代碼是正確的，它編譯得很好。

來源

2010-07-20 Dacto

如果這是一項家庭作業，您應該爲您的問題添加_homework_標籤。 – zneak 2010-07-20 03:26:15

如果是雙向鏈表，則根本不需要更改任何指針。只是交換了有效載荷：

pointer1 = first 
pointer2 = last 
while pointer1 != pointer2 and pointer2->next != pointer1: 
    temp = pointer1->payload 
    pointer1->payload = pointer2->payload 
    pointer2->payload = temp 
    pointer1 = pointer1->next 
    pointer2 = pointer2->prev

如果回定點你的意思是last指針（在沒有出現第一指針可用），那麼你就需要倒退拋雙端隊列找到它。然而，很難相信這會是一個相當低效的deque（這應該是一個雙端隊列）。

來源

2010-07-20 03:31:03 paxdiablo

您的意思是交換數值？ – Dacto 2010-07-20 03:34:09

@Dacto，是的。因爲列表的_結構沒有改變，所以在改變指針方面沒有意義（原諒我可憐的雙關語嘗試）。 – paxdiablo 2010-07-20 03:46:06

@paxdiablo您可以更改列表的結構（通過更改指針）*或*您可以更改結構中的值，就像您一樣;兩種方式都有效。改變指針會稍微快一點，因爲那時你只需要一次跟蹤一個節點（'q'），而你必須跟蹤兩個（'pointer1'和'pointer2'）需要更多的操作和堆棧空間。 – kerkeslager 2010-07-20 04:01:46

像deques這樣的鏈接結構很容易遞歸，所以我傾向於在處理鏈接結構時使用遞歸樣式。這也使我們可以逐步編寫它，以便我們可以輕鬆測試每個功能。循環隨着你的功能確實有很多缺點：你可以很容易地引入fencepost errors，它往往會導致混亂的大功能。

首先，你已經決定通過交換指針來做到這一點，對吧？所以寫一個函數來交換指針：

void swapCirListDequePointers(
    struct cirListDeque** left, 
    struct cirListDeque** right) 
{ 
    struct cirListDeque* temp = *left; 
    *left = *right; 
    *right = temp; 
}

現在，寫反轉指針中的單個節點的功能：

void swapPointersInCirListDeque(struct cirListDeque* q) 
{ 
    swapCirListDequePointers(&(q->prev),&(q->next)); 
}

現在，把它一起遞歸：

void reverseCirListDeque(struct cirListDeque* q) 
{ 
    if(q == q->backSentinel) 
     return; 

    swapPointersInCirListDeque(q); 

    // Leave this call in tail position so that compiler can optimize it 
    reverseCirListDeque(q->prev); // Tricky; this used to be q->next 
}

我不確定你的結構是如何設計的;我的函數假定你的deque是循環的，並且你會在哨兵上調用它。

編輯：如果你的deque不是圓形的，你還需要在哨兵上打電話swapPointersInCirListDeque(q)，所以在if聲明前移動swapPointersInCirListDeque(q)。

如果你打算在此之後使用backSentinel，你應該改變它，因爲它現在是列表的前面。如果你有一個frontSentinel，你可以添加swapCirListDequePointers(&(q->frontSentinel),&(q->backSentinel));到swapPointersInCirListDeque。否則，您必須將第一個節點與q一起傳遞，並將q->backSentinel設置爲該節點。

來源

2010-07-20 03:54:12 kerkeslager

您已收到幾條建議;這裏的另一種可能性：

// Assumes a node something like: 
typedef struct node { 
    struct node *next, *prev; 
    int data; 
} node;

，並假設一對夫婦分別命名爲head和tail指向雙端隊列的頭部和尾部，變量（暫時全局）。

void reverse() { 
    node *pos = head; 
    node *temp = pos->next; 

    head = tail; 
    tail = pos; 

    while (pos != NULL) { 
     node *t = pos->prev; 
     pos->prev = pos->next; 
     pos->next = t; 
     pos = temp; 
     if (temp) 
      temp = temp->next; 
    } 
}

至少就目前而言，這並沒有承擔任何哨兵 - 只是空指針信號列表的末端。

如果你只是在012ques存儲在德克，Paxdiablo的建議是一個很好的（除了創建一個雙鏈接節點只容納一個int是一個巨大的浪費）。假設實際上你已經存儲了足夠大的雙向鏈接節點，那麼你也應該避免移動數據，至少在一般情況下是這樣。

來源

2010-07-20 04:05:07

在C中反向雙鏈接Deque

回答

相關問題