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 つのアイテムを互いに割り当ててループしています。これを見直す必要があります。

編集

OKはあなたのためにそれを書きました、うまくいっているようです。(リスト要素をペアで実際に交換することでこれを行います)。

/// 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. nodnod->nextは現在(so nod == nod_temp->next)を指しています
  3. nod->nextnot_tempは現在、 の古いアドレスである を指していますnod。

nod->nextの古いアドレスを指しているnod（これnod_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

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 に答える
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 に答える