交换链接列表中的节点

我想交换链接列表中的两个相邻节点，我想我理解如何使用临时节点来实现它的想法。交换链接列表中的节点

这里是我的结构交换功能

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

交换链接列表中的节点

回答

相关问题