交換鏈接列表中的節點

我想交換鏈接列表中的兩個相鄰節點，我想我理解如何使用臨時節點來實現它的想法。交換鏈接列表中的節點

這裏是我的結構交換功能

struct part { 
    char* name; 
    float price; 
    int quantity; 
    struct part *next; 
}; 
typedef struct part partType; 

partType *swap_node(partType **item) { 

    partType *temp; 
    temp = *item; 
    *item = (*item)->next; 
    temp->next = (*item)->next; 
    (*item)->next = temp; 
    return *item; 
}

我想不出如何使一個節點列表指向新的交換節點。我是否需要另一個臨時變量？另外，如何解釋交換的兩個節點是列表中的前兩個。

來源

2012-04-02 Tristan Pearce

請用標準的英語，包括首都。如果這是一個家庭作業問題，看起來它可能是，那麼請標記它。 – thb 2012-04-02 03:29:57

您的列表是雙向鏈接的（即什麼是partType）？什麼是'物品'？一個指向你想成爲「對中第二個」的物品的指針？ – John3136 2012-04-02 03:31:36

單鏈接列表，item是指向列表中頭節點的指針。 – 2012-04-02 03:33:14

從代碼中，它看起來像要交換item和item-> next。

如果你沒有雙向鏈表，那麼你需要設置linkPtr頭部，然後迭代，直到linkPtr-> next == *項目。從那裏，你可以開始在linkPtr，linkPtr-> next和linkPtr-> next-> next之間切換。

你還需要一個單獨的條件比較linkPtr頭，如果是的話，那麼你需要設置頭到新的頭。

來源

2012-04-02 03:35:26 steve8918

爲了闡明我的功能什麼是head和linkptr？我雖然*項目被認爲是頭指針。 – 2012-04-02 03:47:26

四個簡單的選擇：

第一種選擇：跟蹤指針到上一個（可能是分配預計需要的方向）。

第二個選項：實現一個雙向鏈表，以便始終可以找到前一個節點。

第三種選擇：實現一個單獨鏈接列表（因爲你的任務可能需要），但給每個節點兩個指針：一個指向'下一個'，一個指向數據有效載荷（可能幾乎任何東西;一個結構體，一個數組或一個普通的舊數據類型）。然後，您只需交換有效負載指針指向的位置，而不用擔心「next」和「prev」。

第四個選項：交換數據本身（可能需要分配的方向）。

上面每個都有用例。

來源

2012-04-02 03:38:38 DavidO

第五種選擇：使用指針而不是指針。然後你可以改變它，而不需要明確的指向prev。（雖然你當然仍然需要一個指向prev-> next的指針）。我可能不會使用這個選項，但是如果數據不是這樣的話，編寫一個基於swap的通用指針（a，b）會很有用一個指針。 – Corbin 2012-04-02 03:40:47

「有多種方法可以做到這一點」（一個衆所周知的Perl口頭禪） – DavidO 2012-04-02 03:41:39

呃，我認爲除了那五個之外，沒有任何合理的方法。剛剛計算清單可能也完成:) – Corbin 2012-04-02 03:44:28

忽略關於雙向鏈表的答案。要回答您的問題，您需要考慮如何調用您的功能。

現在，你有一個函數需要一個指針指針。它當前指向一個節點（節點A），節點又指向另一個節點（節點B）。想象一下這樣的場景：

partType a, b, c, d; 
a->next = &b; 
b->next = &c; 
c->next = &d; 
d->next = NULL;

現在，你想換B和C的順序使用功能有A-> C-> B-> d。那麼，你會這樣做：

swap_node(&a->next);

A指向B;現在它指向C.正如你所看到的，如你所期望的那樣，「前一個」節點已經指向C.換句話說，你已經完成了你的目標。乾杯!

備註：交換功能究竟發生了什麼？讓我們分解它。首先，你給它的參數是指向的指針。由於措辭的原因，這些都是拙劣的想法 - 不要讓措辭欺騙你。就像「變化率的變化率」是一個婊子想的，但「加速」更容易。你想通過記住這個參數來解析它，首先是一個指向某些數據的指針，而你的函數將修改它指向的數據。

所以你的函數得到一個指向這個'p'的指針，它指向鏈表中的一個點（你假設，見PS）指向兩個節點（稱它們爲X和Y）。圖：

[p] --> X[next] --> Y[next] --> Z[next]

你的算法確實：

讓[P]指向Y：*項目=（*項目） - >下一步

製作X [下一頁]指向Z：溫度 - >未來=（*項目） - >下一步

使Y [下一頁]指向X：（*項目） - >未來=臨時

所以，如果你現在考慮我的A，B，C ，D例子，鏈表是：

A[next] --> B[next] --> C[next] --> D[next] --> NULL

你可以更清楚地看到我傳遞的是什麼指針。它是內存中的位置（讀：指針），其中A [next]存儲在哪裏，您的函數需要進行交換。

順便說一句，另一種方式來編寫這是做：

a->next = swap_node(&a->next);

，但不這樣做。這是多餘的。

PS你有沒有想過當你要求交換系列中的最後一個節點時會發生什麼？眼下，事情發生爆炸：P

來源

2012-04-02 03:58:10

當我想交換a和b時，情況如何？ – 2012-04-02 04:11:12

要交換a和b，您需要有一個概念，該列表的第一個或「頭」是什麼。大多數人自己保留一個指針，比如'partType * list_head'，它指向列表的頭部。最初，'list_head =＆a;'。然後，交換A和B，你想調用'swap_node（＆list_head）;'。現在'list_head'將指向B. – 2012-04-02 04:13:31

隨着數據這個小，你還不如干脆換一切，但next指針：

partType tmp = *item; 
memcpy(item, item->next, offsetof(item, next)); 
memcpy(item->next, &tmp, offsetof(item, next));

如果您的數據變得太大時要做到這一點，你需要一個指向節點之前你想要的兩個。好的部分是，你修復prev的next指針作爲一個臨時變量，讓你不需要一個。

prev->next = item->next; 
item->next = item->next->next; 
prev->next->next = item;

來源

2012-04-02 05:41:38 Dave

簡單的方法來交換到節點... 我不寫實際的代碼。我只是給你一個提示交換節點。

[1]->[2]->[3]->[4]

假設這是你的鏈表，要交換[2]和[3]。

使用循環來達到[2]。因此您的temp位於[2]。因此temp1在[3]。
temp->next = temp1->next;

temp1->next = temp;

所以現在temp->next = [4]和temp1->next = [2]

來源

2012-04-02 05:54:14 Parag

交換鏈接列表中的節點

回答

相關問題