このコードを図で解説していただけませんか。

Question

このコードを図で解説していただけませんか。図を書いて見たのですが、
どこか解釈が間違っているのかうまくいきません。
workがどこか、ｐが指している（A)リンクとの関係がよくわかりません。
図はgHead,p,work,tempを書いて、リンクは
A->B->C->Dとしました。workをどこにするかが、分かっていないのかもしれません。
よろしくおねがいいたします。

コード
/*
	リストを逆順にする。
*/
void reverse_list(void)
{
	struct LinkedList_tag* p = gHead.next;
	struct LinkedList_tag* work = NULL;
	struct LinkedList_tag* tmp;

	while( p != NULL ){

		/* この後、p->next を書き換えるので退避しておく */
		tmp = p->next;

		/* １つ前の要素を p->next に設定 */
		/* "１つ前の要素" とは先頭から末尾へ向かう流れの中でのことを言っており、
		   逆順になった後のことを考えると、"次の要素" のことを言っている。
		   初回は何もないので NULL になっている */
		p->next = work;

		/* 現在の注目要素を保存 */
		/* これは、次のループにおいては "１つ前の要素" になる */
		work = p;

		/* 最初に退避させておいた p->next を次の注目要素として復帰させる */
		p = tmp;
	}

	/* 最終的な work は、逆順になった後の先頭要素であるから、
	   ダミーの先頭要素の nextポインタとして設定する */
	gHead.next = work;
}

Comments

[episteme]

循環双方向リストは投げ出したのか?

[退会済みユーザー]

いいえ、投げ出していません。もう一度リストを復習していて、分からないところが出てきたのでしつもんしています。図を見ているんですがよくわからないのですが。今日は時間がないので、明日見ますのでよろしくお願いいたします。

[退会済みユーザー]

解決しました

Answer 1

[0:start]

       P
     +----+     +----+
前   |next+---->|next|
 ^   +----+     +----+
 |
 |
 +---work        tmp

[1:tmp = p->next]

      P
     +----+     +----+
前   |next+---->|next|
 ^   +----+     +----+
 |                ^
 |                |
 +---work        tmp

[2:p->next = work] ※ここで回れ右

      P
     +----+     +----+
前<--+next+     |next|
 ^   +----+     +----+
 |                ^
 |                |
 +---work        tmp

[3:work = p] work は tmp のひとつ前

      P
     +----+     +----+
前<--+next+     |next|
     +----+     +----+
       ^          ^
       |          |
     work        tmp

[2:p = tmp] work は p のひとつ前

                  P
     +----+     +----+
前<--+next+     |next|
     +----+     +----+
       ^          ^
       |          |
     work        tmp

※ 「図が描けない」が理解できん。コードのとおりに線を引くだけじゃないのか?

Comments

[退会済みユーザー]

仕事に行きます。あした図をよく見ます。

Answer 2

ちょっと見ですが、最後（ループ脱出時）から考えると p = tmp;の時はtmp=p=NULLですねd＾＾　その場合、workには最後の有効なポインタが入っています。・・・それを、gHead.nextに入れてるv＾＾・・・で、分かりますか？　追記：要はnextを入れ替えながらリストを最後までたどって、最後の要素をさすポインタをリストの先頭にしているだけです。

Comments

[退会済みユーザー]

それはわかるんですが、ポインタの付け替えが、図にできないのです。A->BからB->Aに付け替えているところが、すっきりしません。

Answer 3

リストの状態(初期)
gHead(next: A)
A(next: B)
B(next: C)
C(next: D)
D(next: NULL)

処理の流れ

初期値

p = gHead.next(A)
work = NULL
tmp = NULL

while 1回目

tmp = A(p)->next(B)
A(p)->next = NULL(work)
work = A(p)
p = B(tmp)

while 2回目

tmp = B(p)->next(C)
B(p)->next = A(work)
work = B(p)
p = C(tmp)

while 3回目

tmp = C(p)->next(D)
C(p)->next = B(work)
work = C(p)
p = D(tmp)

while 4回目

tmp = D(p)->next(NULL)
D(p)->next = C(work)
work = D(p)
p = NULL(tmp)

while終了

gHead.next = D(work);

リストの状態(完了)
gHead(next: D)
D(next: C)
C(next: B)
B(next: A)
A(next: NULL)

付け替え順序

初期値
gHead->A->B->C->D->NULL

while 1回目
gHead->A->NULL
B->C->D->NULL

while 2回目
gHead->A->NULL
B->A->NULL
C->D->NULL

while 3回目
gHead->A->NULL
C->B->A->NULL
D->NULL

while 4回目
gHead->A->NULL
D->C->B->A->NULL

while終了
gHead->D->C->B->A->NULL

Comments

[退会済みユーザー]

sh_akiraさん,epistemeさん、ありがとうございます。図を書くことが出来ました。助かりました。