C言語とC++言語コミュの教えてください(双方向リスト)

双方向リストについてわからない部分があるのでご指導ください。
基本的すぎて怒られるかもしれませんが、ご指導ください。
以下のコードに関してです
*prevは前の要素へのポインター
*nextは後ろの要素へのポインター

typedef struct list_t {
　　char line[256];
　　struct list_t *prev;
　　struct list_t *next;
} LIST;

insertt_line(LIST *c, LIST *p)
{
　　/* 両隣へポインターをつなぐ */
　　p->prev = c->prev;
　　p->next = c;
　　/* 両隣のポインターをつなぎ換える */
　　c->prev->next = p;
　　c->prev = p;
}
/*insert_line は、 c の前に p を挿入する操作です。*/

だいたいの操作は、わかってきましたが、少し疑問に残る
場所があります。

まず、p は新しく挿入されるデータなので、prev には何も
入っていません。
そこで、p->prev に何か入る。

c の前に入れるのだから、それまで c->prev が示していた
「前」は、今度は p の前になる。これを入れる。

p->prev = c->prev;

ここまでの操作はわかるのです・・・

以下の操作が疑問の部分です。

p->next = c;

c->prev->next = p;

c->prev = p;

上記の操作でcとpが代入されていますよね・・・

cとpというのは、どこの部分を指しているのでしょうか？

リストの要素の構造は
[prev][data][next]という形で繋がっているとおもうの
ですが・・・

cとpが持っている情報が何なのか知りたいです。

ご指導ください。

コメント(27)

最初
全て
最新の40件

[1] mixiユーザー 08月25日 20:34

図かいたらわかりやすいよ。

[2] mixiユーザー 08月25日 20:38

これって、単体試験でうまく動かないのを、ポインタを理解できていないテスターが直したんでは？

insertt_line(LIST *c, LIST *p)
{
　　/* 両隣へポインターをつなぐ */
　　c->prev = p;
　　p->next = c;
}

でおしまいだと思うのですが。
#ビール500ml+発砲酒500mlあけているので、あまり自信がありません(^^;

[3] mixiユーザー 08月25日 20:41

＞cとpというのは、どこの部分を指しているのでしょうか？

構造体変数の先頭アドレスです。
構造体変数全体を指し示していると考えればいいでしょう。

[4] mixiユーザー 08月25日 20:43

＞Yebisuさん
それだと、p->prevが不定のままですし、
もともとcに対して繋いでいたポインタの値がpに繋がらないままになります。

[6] mixiユーザー 08月25日 20:47

このLIST構造体は
・自身の前のリストのアドレス
・後ろのリストのアドレス
そして
・要素数256のchar配列
を持っています。

pやcはLIST構造体そのものではなく、LIST構造体のアドレスを
指し示すポインタです。

さて、仮に呼び出し前のリストが
a→c→b
だったとしますね。その時点でのリストの中身は

・c->prev = aのアドレス
・c->next = bのアドレス
・c->line = 要素が256のchar配列（例えば3,5,7…）
・p->prev = 不定
・p->next = 不定
・p->line = 要素が256のchar配列（例えば1,2,4…）

これが呼出し後は並びが
a→p→c→b
となり、リストの中身も

・c->prev = pのアドレス
・c->next = bのアドレス
・c->line = 要素が256のchar配列（例えば3,5,7…）
・p->prev = aのアドレス
・p->next = cのアドレス
・p->line = 要素が256のchar配列（例えば1,2,4…）

となります。前後でc->lineとp->lineはなんら
変化しないことに注意してください。

＞リストの要素の構造は
＞[prev][data][next]という形で繋がっていると
＞おもうのですが・・・
恐縮ながらこの認識は根本的に間違ってるような…。　（＾＾；

[8] mixiユーザー 08月25日 20:53

＞よーたんさん

＞＞リストの要素の構造は
＞＞[prev][data][next]という形で繋がっていると
＞＞おもうのですが・・・
＞恐縮ながらこの認識は根本的に間違ってるような…。　（＾＾；

そもそも、[prev][data][next]という表現が何を意味しているのか解釈できないので、”根本的に間違っているか”を語るのは筋違いではないでしょうか？

[9] mixiユーザー 08月25日 21:06

をー、わかりました。
addではなく、insertってことですね。
#解説は、シラフな方々にお任せしますよ。(^^)

メチャンコ、オフトピで申し訳ないですが。。。
>5: rep
普段は、YEBISUなんですが、昨日「KIRIN 秋味」がドドーンと並んでまして、「秋だけの限定醸造」って言葉に惹かれ、浮気中です。(^^;

[10] mixiユーザー 08月25日 21:55

一旦ローカル変数に代入して、ポインタの二重参照をなくしたバージョンのコードを見たら理解できませんかね？

LIST *thiselement, *nextelement, *prevelement;
thiselement=p;
prevelement=c->prev;
nextelement=c;

prevelement -> next = thiselement;
//prevelement -> prev = ...触る必要なし

thiselement -> next = nextelement;
thiselement -> prev = prevelement;

nextelement -> prev= thiselement;
//nextelement -> next = ...触る必要なし

[12] mixiユーザー 08月25日 22:17

とにかく自分で絵を描いてみれば理解できます。
代入1つ毎に、全部絵を描いてみれば。。。
最初と最後はこんな感じ。

[13] mixiユーザー 08月25日 22:37

人が、手をつないで一列に並んでいるような物だと思えば・・・

aさんの右(next)はbさん、bさんの右(next)はcさん、cさんの右(next)はdさん、bさんの左(prev)はaさん、aさんの左(prev)は誰もいない・・・という感じです。
そこへ「わたしも入れてください」とαさんがやってきました。αさんはaさんとbさんの間に入るとします。

・・・という筋書きの続きを考えてみるのはどうでしょう？

[14] mixiユーザー 08月25日 23:07

面倒な僕はSTLで一発解決(ﾏﾃｺﾗ

# ちょっと前まではこういう風に
# ゴリゴリ書いていたんだけどなぁ…

[17] mixiユーザー 08月26日 01:24

13で述べた内容を図にしてみました。超絵心ないですが、イメージとしてはこんな感じです。

[18] mixiユーザー 08月26日 02:13

c->prev->next
このままだと先頭に挿入すると落ちね？
c->prevがNULLの時の判定が・・・
まぁ、リングならいらないけど・・・

[19] mixiユーザー 08月26日 02:48

　プログラムでどう書くかは皆さん言い尽くしてらっしゃいますので、別の観点で１レスだけ・・・。

　insert 対象の状態と、insert する場所の組み合わせは、この課題の場合、有限個だと思います。

・insert 対象の状態
　(1) リストが１つも無い
　(2) リストが１つだけある
　(3) リストが２つ以上つながっている

・insert する場所
　(a) リストの先頭
　(b) リストの途中
　(c) リストの最後
　(d) 場所無し（リストが無い）

　これらの組み合わせを考えると、次のような場合が有り得ます。

・(1) の時は、(d)→insert したものがリスト全体となる
・(2) の時は、(a) と (c) は可能
・(3) の時は、(a)～(c) いずれも可能

　よって、このプログラムは、上記の場合について考えれば良い事になります。
　逆に、上記以外の場合で動作する事は考えられないので、そのような「例外」は「動作しないように」コードを組むべきでしょう。
　有限個の組み合わせのみでプログラムを作る限り、有限の資源で検証が可能である、と考えられるからです。

　「有限の立場」に依らない設計や実装は、バグやセキュリティホールを生むでしょう・・・。

　もちろん、上記の状態を「まとめて」、より少ない状態数にした上で実装するのは問題ないと思います。その「まとめ方」が正しい限りは・・・。

[21] mixiユーザー 08月26日 05:56

/*insert_line は、 c の前に p を挿入する操作です。*/

という記述から、リストにはすでに何らかの要素が入っていることが前提で、挿入する箇所はcで指し示された要素の直前であると考えられるのではないでしょうか？

[22] mixiユーザー 08月28日 17:11

いろいろご指導いただきありがとうございます。

ちょっと、混乱しています、リスト構造についていろいろ
調べてみるといろいろな図が出てきますね。

私が、最初に見た図は、prevとnextの部分同士が指し合っ
ている図です。

saitohさんがアップした図は、データ部分を指しています
よね。その部分で混乱しています。

リスト構造というのは、実現する方法というのは、たくさ
んあるということなのでしょうか？

私が示した図で考えるとpとcというのは、何を意味してい
るのかわからなくなってしまします。

http://cai.cs.shinshu-u.ac.jp/sugsi/Lecture/c/e_07-03-03.html

[23] mixiユーザー 08月28日 17:44

　はじめまして。m(_ _)m

>>22: nip_tuckさん
　12番記事でsaitohさんがアップしてくださった図でも、このリンク先にある図も、どちらも意図するところは同じです。
　リンク先の図では矢印の先っぽが枠の内に入っているので、そのせいでちょっと混乱されているのかと思いますが、矢印(ポインタ)は、太線で示される枠全体(つまり構造体struct list_t)を指すものと考えてください。
＃>>3: 顕斗さんのご指摘どおりです。

　prev, nextの型である「struct list_t *」の意図するところは、「struct list_tへのポインタ」であり、prevやnextといった構造体の一要素(メンバ)ではありません。
　つまり、prevとnextが指すのは、それぞれリストの中で直前・直後にある要素「を含んでいるstruct list構造体」ということになります。

　実際メモリ上のレイアウトがどうなっているかは、考える必要が(少なくともこの場合は)ありません。あくまで構造体を一かたまりとして捉えられるとよろしいかと思います。

[24] mixiユーザー 08月28日 18:54

＞23: へっぽこメイドさん
＞prev, nextの型である「struct list_t *」の意図するところは、「struct list_tへのポインタ」であり、prevやnextといった構造体の一要素(メンバ)ではありません。

すいませんおっしゃりたい事は非常によく解るのですが、敢えて文句をば。
「struct list_tへのポインタ」って言い方は控えた方がいいように思うのですがどうでしょう？
いや、わたしがまだガキの頃「intへのポインタ」って聞いてこの世で唯一絶対の「int様」ってあるんだろうなあ！？とか思ったりしたので・・・
fopenとかで返るのは「FILE様」だからぞんざいに扱ってはいけないとか・・・
過去のアホ話失礼しました～。

[25] mixiユーザー 08月28日 19:34

>>24: ああひよひよさん

>「intへのポインタ」って聞いてこの世で唯一絶対の「int様」ってあるんだろうなあ！？とか思ったりした

　なるほど、そういう可能性もありますか。。。
　ここで出ているintは、"int"という名前の「値」(変数の実体)ではなくて、"int"という名前の「型」(値の集合)である、という点ですよね。

…とはいえ、それを正確に説明するような書き方っていうのは、ちょっと考えた限りではだーらだら書く以外に思いつきません。(^_^;
「××型(の値)?へのポインタ」というのが一番簡潔で、そこそこ正確なような気がしますので、「型」と「値」は同じものではないよ、というところを理解していただいた上で、その旨読み替えてください。m(_ _)m

P.S.
　Type Checkerの中ではどーなんだ、とか言われるとちょっと困りますが。(笑

[26] mixiユーザー 08月28日 20:37

うーん。データ部分じゃなくて、struct全体をさしているつもりの図なんだけどな。ま、先頭フィールドだから、結局同じだけど。

[27] mixiユーザー 08月28日 23:52

＞23～26
変数という実体あっての参照だとおもうので、ああひよひよさんの意見に賛成です。

あと、構造体型変数（全体）へのポインタを注釈なしに図で説明することは難しいですからね…
もちろん双方向リストの概要を説明するには図を描くのがいいと思いますが、
「上記の操作でcとpが代入されていますよね・・・
cとpというのは、どこの部分を指しているのでしょうか？」
という質問者の意図から、俺はc、pの参照先について日本語で説明すべきだと思い、3を書きました。

ログインすると、残り6件のコメントが見れるよ