Q&A
ありがとうございます。
「l_ と l_->next の間に x_ が挿入されます。」というご指摘でコードはわかったのですが、ご説明の[0:start]のなかがよくわからないのですが、
どういうことなんでしょうか。教えてください。
"llist.h"の中身がよく理解できません。図を書いて見るんですがうまく
表現できないので、どなたか説明してもらえませんか。一つわかれば後は分かると思います。
コード //"llist.h" #ifndef INCLUDED_LLIST_H #define INCLUDED_LLIST_H #define llist_init(l_) ((l_)->next = (l_)->prev = (l_)) #define llist_next(l_) ((l_)->next) #define llist_prev(l_) ((l_)->prev) #define llist_ins_next(l_, x_) (\ (x_)->next = (l_)->next ,\ (x_)->prev = (l_) ,\ (l_)->next->prev = (x_) ,\ (l_)->next = (x_) ) #define llist_ins_prev(l_, x_) (\ (x_)->prev = (l_)->prev ,\ (x_)->next = (l_) ,\ (l_)->prev->next = (x_) ,\ (l_)->prev = (x_) ) #define llist_del_next(l_) (\ (l_)->next->next->prev = (l_) ,\ (l_)->next = (l_)->next->next ) #define llist_del_prev(l_) (\ (l_)->prev->prev->next = (l_) ,\ (l_)->prev = (l_)->prev->prev ) #define llist_del(l_) (\ (l_)->prev->next = (l_)->next ,\ (l_)->next->prev = (l_)->prev ) #endif /* !INCLUDED_LLIST_H */
回答3件
0
遅くなりすぎてしまった...
双方向循環リストの操作をマクロで実装した機能群です。
おそらく
cpp
1struct linked_list { 2 linked_list *prev; 3 linked_list *next; 4 int value; 5};
のような構造体に対して使うのでしょう。
やっていることは、通常の双方向循環リストを知っていればそれと同じです。
まず、引数はすべてポインタで渡す想定のようです。これはアロー演算子が使われていることから分かります。
cpp
1#define llist_init(l_) ((l_)->next = (l_)->prev = (l_))
リストを初期化します。最初にリストを構築するときに使います。
これは引数で渡されたノードの next と prev を自分自身に設定していますね。だから要素数 1 の循環リストになります。
cpp
1#define llist_next(l_) ((l_)->next) 2#define llist_prev(l_) ((l_)->prev)
これらは説明不要かと思います。そのまま next と prev を返しているだけです。
cpp
1#define llist_ins_next(l_, x_) (\ 2 (x_)->next = (l_)->next ,\ 3 (x_)->prev = (l_) ,\ 4 (l_)->next->prev = (x_) ,\ 5 (l_)->next = (x_) )
ノード l_ の次にノード x_ を追加する処理です。 l_ の次のノードを N とします。 l_ と N の間に x_ を挿入する操作です。
これだけ参考までに図を書いてみました。
cpp
1#define llist_ins_prev(l_, x_) (\ 2 (x_)->prev = (l_)->prev ,\ 3 (x_)->next = (l_) ,\ 4 (l_)->prev->next = (x_) ,\ 5 (l_)->prev = (x_) )
これはノード l_ の前にノード x_ を追加する処理です。 llist_ins_next 同様なので省略します。
cpp
1#define llist_del_next(l_) (\ 2 (l_)->next->next->prev = (l_) ,\ 3 (l_)->next = (l_)->next->next ) 4
【「l_ の次の次のノード」から見た「一つ前のノード」】を 「l_」 に、【「l_」から見た「次のノード」】を 「l_ の次の次のノード」 にしています。結果、リストからは「l_ の次のノード」が切れています。
cpp
1#define llist_del_prev(l_) (\ 2 (l_)->prev->prev->next = (l_) ,\ 3 (l_)->prev = (l_)->prev->prev ) 4 5#define llist_del(l_) (\ 6 (l_)->prev->next = (l_)->next ,\ 7 (l_)->next->prev = (l_)->prev )
これらも同様に考えることができます。省略します。
質問とは関係ありませんが、マクロで実装されていると
cpp
1// 毎回 `new linked_list` が展開されてダメ 2llist_ins_next(l, new linked_list);
のように書けず、
cpp
1linked_list *new_node = new linked_list; 2llist_ins_next(l, new_node);
のようにしなければならないなど、マクロ特有のいろいろと配慮するべきこともでてきます。
投稿2018/02/24 13:42
総合スコア429
0
ベストアンサー
循環双方向リストの基本操作やね。
nextとprevを持つ任意の構造体:
C
1struct node { 2 struct node* next; 3 struct node* prev; 4 ... 5};
に対する操作をマクロで実装してます。
#define llist_ins_next(l_, x_) (\ (x_)->next = (l_)->next ,\ (x_)->prev = (l_) ,\ (l_)->next->prev = (x_) ,\ (l_)->next = (x_) )
これ↑を図説
[0:start]
l_ +----+ +----+ |next+------->|next| +----+ +----+ |prev|<-------+prev| +----+ +----+ +----+ |next| +----+ |prev| +----+ x_
[1:(x_)->next = (l_)->next]
l_ +----+ +----+ |next+------->|next| +----+ +----+ |prev|<-------+prev| +----+ +----+ ^ +----+ | |next+----+ +----+ |prev| +----+ x_
[2:(x_)->prev = (l_)]
l_ +----+ +----+ |next+------->|next| +----+ +----+ |prev|<-------+prev| +----+ +----+ ^ ^ | +----+ | | |next+----+ | +----+ +----+prev| +----+ x_
[3:(l_)->next->prev = (x_)]
l_ +----+ +----+ |next+------->|next| +----+ +----+ |prev| +--+prev| +----+ | +----+ ^ V ^ | +----+ | | |next+----+ | +----+ +----+prev| +----+ x_
[4:(l_)->next = (x_)]
l_ +----+ +----+ |next+--+ |next| +----+ | +----+ |prev| | +--+prev| +----+ | | +----+ ^ V V ^ | +----+ | | |next+----+ | +----+ +----+prev| +----+ x_
ってなわけで、l_ と l_->next の間に x_ が挿入されます。
投稿2018/02/24 13:05
編集2018/02/24 13:13
総合スコア16614
「よくわからない」を説明してください。
[start]は処理を行う(マクロを適用する)前の状態です。
図 l_
+----+ +----+
|next+------->|next|
+----+ +----+
|prev| +--+prev|
+----+ | +----+
^ V ^
| +----+ |
| |next+----+
| +----+
+----+prev|
+----+
x_
がどんな意味かわかりません。すみません。ポインタの付け替えは理解できました。
読めん。何番だ? それ[start]じゃないだろ。
すみません。ekiさんに詳しい説明をもらいました。
たすかりました。またよくよみなおします。
分からないところがありましたら、またお願いします。
3番ぽいですね。
(l_)->next->prev = (x_) の式によって、今まで l_ を指していた
「l_ の next の prev」 が、 x_ を指すようになったことを意味しています。
ふぉろーありがとです。
# 1-stepずつ丁寧に図を描けばわかるハズなんだがなー...
少しずつ進歩しています。list.hを使うコードは後からと思っていたのですが、リストを勉強していて、
単方向リスト、単方向循環リスト、双方向リスト、双方向循環リストが出てきて、双方向循環リストのコードが載ってなくて、単方向循環リスト、双方向リストから作ろうとして、ここに迷い込みました。
大分リストのポインタの付け替えが見えてきました。がんばります。少し仕事が入りましたので数日おやすみします。ありがとうございました。
ありがとうございます。いろんな双方向リストを探して勉強していますが、まだよくりかいできていなようです。その途中で、「list.h」が出てきたのでそれをみていたのですが、よくわかりません。電話帳のプログラムで、間口を広げすぎて、自分でも何をしようとしているのか分からない状態でもがいています。
よろしくおねがいいたします。ご指摘のURLで勉強しなさいということですよね。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2018/02/24 13:50