1

我有一个以这些值为例的链表：4 5 3 2 7，现在我想将每个节点与前一个节点交换，如下所示：

4 5 3 2 7 // this beginning of list
5 4 3 2 7
5 3 4 2 7
5 3 2 4 7
5 3 2 7 4 // the list should now become like this

但不幸的是，当我解析输出时，我陷入了无限循环：

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    int p;
    struct _node *next;
} node;

main(int argc, char **argv)
{
    int i, n;
    node *nod = NULL;
    node *nod_tmp = NULL;
    node *nod2 = NULL;
    printf("Enter n: ");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        nod_tmp = (node *)malloc(sizeof(node));
        scanf("%d", &nod_tmp->p);
        nod_tmp->next = nod;
        nod = nod_tmp;
    }

    i = 0;
    while(i < n)
    {   
        nod_tmp = nod;
        nod = nod->next;
        nod->next = nod_tmp;
        ++i;
    }

    while(nod != NULL)
    {   

        printf("%d\n", nod->p);
        nod = nod->next;
    }
    return 0;
}
4

6 回答 6

2

这看起来很奇怪：

while(i < n)
{   
    nod_tmp = nod;
    nod = nod->next;
    nod->next = nod_tmp;
    ++i;
}

基本上，您正在循环 2 个项目，将它们相互分配。你需要审查这一点。

编辑

好的，为你写的，似乎有效。（我通过实际成对交换列表元素来做到这一点）。

/// reading and stuff...

node *prev = NULL, *start = nod->next;
for(int i = 0; i < n - 1; ++i)
{
    // look at this part, it makes everything obvious
    node *a = nod, *b = nod->next, *c = nod->next->next;

    b->next = a;
    a->next = c;

    nod = a; // changing the current node to next

    if(i == 0)
            {
        start = prev = b; // saving an actual start
            }
    else
    {
        prev->next = b;
        prev = prev->next;
    }

    // printing state to be sure
    for(node *tmp_start = start; tmp_start != NULL; tmp_start = tmp_start->next)
        printf("%d ", tmp_start->p);
    printf("\n");
}

printf("Final answer:\n");
while(start != NULL)
{   
    printf("%d ", start->p);
    start = start->next;
}

您需要以相反的顺序输入数据（或稍微更改读取功能）

使用示例：

Enter n: 5 7 2 3 5 4
5 4 3 2 7
5 3 4 2 7
5 3 2 4 7
5 3 2 7 4
Final answer:
5 3 2 7 4
于 2013-01-08T00:14:48.400 回答
1

您的交换代码错误。应该是这样的：

i = 1;
nod2 = nod;
while(i < n)
{   
    nod_tmp = nod2->next;
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    ++i;
}

或者，由于交换每一对基本上将第一个元素推到最后，您可以这样做：

nod_tmp = nod;
while (nod_tmp->next != NULL)
{
    nod_tmp = nod_tmp->next;
}
// nod_tmp now points to the last element
nod_tmp->next = nod;          // loop from the last element back to the first
nod = nod->next;              // move the list pointer to the second element
nod_tmp->next->next = NULL;   // break the loop at the new last element

此外，您可能想查看您的输入代码。如所写，它将使用与输入的相反顺序的值构建列表，因为它总是将下一个值添加到列表的头部。

更新

为了避免潜在的 seg_faults，上面的第一个循环可以在没有计数器的情况下重写，如下所示：

nod2 = nod;
nod_tmp = nod2->next;
while(nod_tmp != NULL)
{   
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    nod_tmp = nod2->next;
}

更新 2

这是执行您想要的完整代码。它只是将第一个节点推到列表的末尾，而不是交换每对节点。我还修复了输入循环，以便以正确的顺序构建列表。

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    int p;
    struct _node *next;
} node;

main(int argc, char **argv)
{
    int i, n;
    node *nod = NULL;
    node *nod_tmp = NULL;
    node *nod2 = NULL;
    printf("Enter n: ");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        nod_tmp = (node *)malloc(sizeof(node));
        scanf("%d", &nod_tmp->p);
        if (i == 0)
        {
            nod = nod2 = nod_tmp;
        }
        nod2->next = nod_tmp;
        nod2 = nod_tmp;
    }

    nod_tmp = nod;
    while (nod_tmp->next != NULL)
    {
        nod_tmp = nod_tmp->next;
    }
    // nod_tmp now points to the last element
    nod_tmp->next = nod;          // loop from the last element back to the first
    nod = nod->next;              // move the list pointer to the second element
    nod_tmp->next->next = NULL;   // break the loop at the new last element

    while(nod != NULL)
    {   

        printf("%d\n", nod->p);
        nod = nod->next;
    }
    return 0;
}
于 2013-01-08T00:21:11.930 回答
1

让我们按照这个循环：

while(i < n)
{   
    nod_tmp = nod;         // 1
    nod = nod->next;       // 2
    nod->next = nod_tmp;   // 3
    ++i;
}
  1. nod_tmp现在nod指向同一个节点。
  2. nod现在指向nod->next(so nod == nod_temp->next)
  3. nod->next现在指向的not_temp是 的旧地址nod。

现在它指向（也指向）nod->next的旧地址，你有一个链表，它的尾部指向它的头部。nodnod_temp

这个 while 循环可能更适合您：

nod2 = nod;
nod_tmp = nod->next;
while(nod_tmp != NULL)
{   
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    nod_tmp = nod2->next;
}
于 2013-01-08T00:21:25.750 回答
0 
    i = 0;
    while(i < n)
    {
        printf("%d\n", nod->p);
        nod = nod->next;
        i++;
    }
于 2013-01-08T00:15:13.000 回答
0

在完成交换之后和打印结果之前，您需要清除列表中最后一个条目的 nod->next。

于 2013-01-08T00:15:13.893 回答
0

c++11方式..

编译：g++ --std=c++11 -Wall -Wextra mylist.cpp

#include <iostream>
#include <list>

template <class List>
void print(const List& list) {
    for (auto i : list)
        std::cout << i << ' ';
    std::cout << std::endl;
}

template <class List>
void swap(List& list) {
    auto i(list.begin());
    auto next(i);
    auto end(list.end());
    while (++next != end) {
        auto tmp = *i;
        *i++ = *next;
        *i = tmp;
        print(list);
    }
}

int main(int, char**) {
    std::list<int> list {4, 5, 3, 2, 7};
    print(list);
    swap(list);
}
于 2013-01-08T00:52:26.923 回答