2 つのノードを交換しようとしています。たとえば、ノードがであり、基本的にノードであるポインタ およびaをb渡している場合。
(a-1)->next(b-1)->nextab
void swap(struct stack **a,struct stack **b)
{
struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b;
*a = *b;
(*b)->next = (temp1)->next;
temp2 = temp1;
(temp2)->next = temp3->next;
}
私は何を間違っていますか？関数を呼び出した後にノードを出力しようとすると、無限ループになります。助けてください。
無限ループは、関数を呼び出した後のリスト内の自己ループが原因です。swap()次swap()のコードでは、ステートメントにバグがあります。
(*b)->next = (temp1)->next;
なんで？swap(): functionの nextの代入文の後にnodetemp1を指し始めるためです。bAndnode[b]の次のポイントはループ内にあります。そして、自己ループは無限ループの理由であり、リンクリストをトラバースするコードのどこかにあります。
swap()以下に、段階的にどのように機能するかを示すために描きました。エラーを理解するのにこれが役立つかもしれません：
aあなたは言及しませんでしたが、私はリンクされたリストが と の間に次の関係を持っていると仮定していますb:(赤いコメントを読んでください)
（ステップ1）：
+----+----+----+ +---+----+----+
| one |----->| two |
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| *a | *b
| |
temp1 temp2, temp3 "after assignment to temp variables"
(step-2): ^
|
*a = *b | *a "<--- next step"
(step-3): バグのあるステートメント
(*b)->next = (temp1)->next; "Change link: (temp1)->next; is `two` node"
" *b is `two`, So Self loop"
+----+----+----+ +---+----+----+ <---|
| one | | two |-----|
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp1 temp2, temp3 " after assignment to temp"
(temp1)->next;実際に参照してください。実行しbて割り当て(*b)->next = (*b)ている(*b)->next = (temp1)->next;ため、自己ループを追加しています。
(ステップ 4):図を使用すると、コード
の最後の 2 行が何を行っているかを簡単に理解できると思います。swap()
temp2 = temp1;
(temp2)->next = temp3->next;
以下は、この 2 行の図です。
temp2 = temp1;
+----+----+----+ +---+----+----+ <---|
| one | | two |-----| "<--- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
(step-5): 関数の最後の行でさえswap() 、以下のようにループを残しました:
(temp2)->next = temp3->next; " last line of your code"
+----+----+----+ +---+----+----+ <---|
| one |----->| two |-----| "<-- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
したがって、ループはまだtwoノードにあるため、無限ループです。
1つの方法は、ノードの位置をリンクリスト内でスワップするのではなく、ノードのデータをスワップすることです（質問にコメントしたように）。しかし、リスト内のノードの位置を入れ替えたいとします。
まあこれでいい！ノードのデータ サイズが大きい場合は、ノードのデータをスワップするよりもノードの位置をスワップする方が適切です (データのスワップは悪い選択です) 。
単一のリンクされたリストがあるため、リスト内の任意の 2 つのノードを交換するには、以前のノード アドレスも必要です。（これは、スワッピングロジックで考慮しないポイントです）
なぜ以前のポインターが必要なのですか? :
いくつかの挿入 (プッシュ) 操作が成功した後、リストが次のようになったとします。
0 <--------TOP - "head"
9 <--p
2
6 <--q
5
水平ダイアグラム - たとえば、 2 つのノード とを交換するとします。(q)(p)
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (q) (p)
(head)
先ほど言ったように、スワップするには以前のポインターが必要です。次のことを考える必要があります(
理論的には、説明を簡単にするために特定のノードについて書いています。しかし、私の実装は非常に一般的です(p)(q))。
リストの前のポインター:
node[0] points to node[9] that is (q), and
node[2] points to node[6] that is (p)
と
node[9] points to node[2]
node[6] points to node[5]
注意: 2 つのノードを交換したい場合は、これら 2 つのノードの前のノードのポインターを使用する必要がありますnode[ 9 ] 。
例: 2 つの swapとの場合、上の図の next pointer ofと next pointer of も変更する必要があります。node[ 6 ]node[ 9 ][ 6 ]node[ 0 ]node[ 2 ]
この 2 つのノードを交換した後のリストはどうなりますか?
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (p) (q)
(head)
以前のノード[o]とには何があり[2]ますか?
スワップ後、以前のポインタのリストに
node[0] points to node[6] that is (q), and
node[2] points to node[9] that is (p)
と
node[9] points to node[5]
node[6] points to node[2]
したがって、2 つのノードを交換する場合は、次のようになります。直前のノードも影響し、リストは単一のリンクリストであるため、以前のポインターも必要です。
前のノード ポインタを見つける方法は?
任意の 2 つのノードを交換し、前のノードを見つけるために 使用できるnode[p]とします。node[q]head pointer
したがって、スワップ関数の構文（私の実装では）は次のようになります。
void swap(struct stack **head, // head node
struct stack **a, // first candidate node to swap
struct stack **b); // first candidate node to swap
そして、次のような関数を呼び出します:
swap(&head, &p, &q);
定義: (コードを理解するには、ほぼ各行に追加したコメントをお読みください)
void swap(struct stack **head,
struct stack **a,
struct stack **b){
// first check if a agrgument is null
if( (*head) == NULL || // Empty list
(*a) == NULL || (*b) == NULL){ // one node is null
// Nothing to swap, just return
printf("\n Nothing to swap, just return \n");
return;
}
// find previos nodes
struct stack* pre_a = get_prevnd(*head, *a);
struct stack* pre_b = get_prevnd(*head, *b);
//Now swap previous node's next
if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and
if(pre_b) pre_b->next = (*a); // b's previous become a's previous
//Now swap next fiels of candidate nodes
struct stack* temp = NULL;
temp = (*a)->next;
(*a)->next = (*b)->next;
(*b)->next = temp;
//change head: if any node was a head
if((*head)==(*a))
*head = *b;
else
if((*head)==(*b))
*head = *a;
}
functionではswap()、ヘルパー関数を呼び出していることがわかりますget_prevnd(, );。この関数は、リスト内の前のノードのアドレスを返します。functionget_prevnd(, );では、最初の引数はリスト ヘッドで、2 番目の引数は探しているノードです。
// find previous node function()
struct stack* get_prevnd(
struct stack* head,
struct stack* a
){
if(head == a){
// node[a] is first node
return NULL;
}
struct stack* temp = head; // temp is current node
struct stack* pre_a = NULL;
while(temp && temp!=a){ //search while not reach to end or the node
pre_a = temp; // find previous node
temp = temp->next;
}
if(temp!=a){// node[a] not present in list
fprintf(stderr, "\n error: node not found!\n");
exit(EXIT_FAILURE); // bad technique to exit()
}
return pre_a;
}
幸いなことに、コードは機能しています:)。以下は、このコードのオンライン テストへのリンクです。さまざまな種類の入力をテストしました。
CodePad:単一のリンクされたリストでノードを交換します。出力を確認してください。
そして下手な英語でごめんなさい
カットアンドペーストのコードを期待していましたが、見つかりませんでした。誰かがまだ興味を持っているなら、これが答えです。3つのケースすべてのブルートフォース分析を行いました。
// swaps nodes at locations *sp and *tp
struct stack *s = *sp; // store locations to prevent overwritten bugs
struct stack *t = *tp;
if(&t->next == sp) { // order u (tp)-> t (sp)-> s -> ...
t->next = s->next;
s->next = t;
*tp = s;
} else if(&s->next == tp) { // order u (sp)-> s (tp)-> t -> ...
s->next = t->next;
t->next = s;
*sp = t;
} else { // disconnected u (sp)->s -> ..., v (tp)->t -> ...
struct stack *next = s->next;
s->next = t->next;
t->next = next;
*sp = t;
*tp = s;
}
// If you track the end of your list, it be the one pointing to NULL.
if(s->next == NULL) {
end = &s->next;
} else if(t->next == NULL) {
end = &t->next;
}
注: このコードは sp == tp の場合に機能しますが、&s->next == tp && &t->next == sp (サイクルで開始) の両方が発生するような病的なケースがないことを前提としています。