【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.22600

Re:リストとハッシュ
投稿者---あきき(2005/08/12 14:31:13)


>p->prev->next = p->next
> 俺(p)の前にいる奴(p->prev)の後(p->prev->next)は
> 俺の後にいる奴(p->next)だ、と。 つまり俺が列から外れます。
>
>p->next->prev = p->prev;
> 逆方向のリンクから、俺を外してます。
>
p->next->prevについてなんですが、
1上記のポインタ先は前のノードに移動して、そこを基準にその後ろのノ ードを指すのでしょうか
2現在のポインタ先からの相対的指定なんでしょうか


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:リストとハッシュ 22601 とおり 2005/08/12 14:39:37


No.22601

Re:リストとハッシュ
投稿者---とおり(2005/08/12 14:39:37)


>1上記のポインタ先は前のノードに移動して、そこを基準にその後ろのノ ードを指すのでしょうか
>2現在のポインタ先からの相対的指定なんでしょうか

そういう風に固定的に理解しては駄目。
構造体のメンバの参照を繰り返しているだけなのだから、その参照を1つずつ紐解いていけばいい。
 p->prev->next = p->next
は、一時的なポインタ変数temp_pでも導入すれば、
 temp_p = p->prev;
 temp_p->next = p->next;
と同じこと。
あとは、実際にpやtemp_pがリスト中のどれを指しているかを考えるだけ。


この投稿にコメントする

削除パスワード

No.22608

Re:リストとハッシュ
投稿者---あきき(2005/08/12 22:43:58)


> p->prev->next = p->next
>は、一時的なポインタ変数temp_pでも導入すれば、
> temp_p = p->prev;
> temp_p->next = p->next;
>と同じこと。
>あとは、実際にpやtemp_pがリスト中のどれを指しているかを考えるだけ。

そういう風に考えるとシンプルですね。考え方としては、ポインタ変数を用いると容易に理解できます。

以下のような処理手順でも、やっぱり固定的な考えでしょうか?
1現データのポインタをもとに前データのポインタを求める
2前データのポインタをもとに後の(現データ)のポインタを求める
3 1と2の繰り返しでデータを追加する


この投稿にコメントする

削除パスワード

No.22609

Re:リストとハッシュ(訂正)
投稿者---あきき(2005/08/12 23:16:07)


>そういう風に考えるとシンプルですね。考え方としては、ポインタ変数を用いると容易に理解できます。
>
>以下のような処理手順でも、やっぱり固定的な考えでしょうか?
>1現データのポインタをもとに前データのポインタを求める
>2前データのポインタをもとに後の(現データ)のポインタを求める
>3 1と2の繰り返しでデータを追加する

2の手順で
現データで求めた前データのポインタをもとに後の(現データ)のポインタを求める

と訂正します。


この投稿にコメントする

削除パスワード

No.22610

Re:リストとハッシュ
投稿者---επιστημη(2005/08/12 23:39:59)


>以下のような処理手順でも、やっぱり固定的な考えでしょうか?
> ...

そのくらいにしておけば?
スレッドの横取りは感心しないな。



この投稿にコメントする

削除パスワード

No.22615

数珠つなぎの図
投稿者---CENTER(2005/08/13 14:12:42)


数珠つなぎの図

CENERです。
数珠つなぎの図をいろいろ検索してみながら考えてみました。
削除の場合の動作がわかりました。
しかし、挿入の場合だろ上手くいきません。
考え方は、同じでよいですよね?
なんか、また、怒られそうですね・・・

一方向リスト
http://cai.cs.shinshu-u.ac.jp/sugsi/Lecture/c/e_07-02-02.html

双方向リスト
http://cai.cs.shinshu-u.ac.jp/sugsi/Lecture/c/e_07-03-03.html

[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c


              後(p->prev->next)              俺の後にいる奴(p->next)
               ↓                              ↓
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
       ↑      ------------------  ------------------
       |             ↑          ↑
       |           p            c
俺(p)の前にいる奴(p->prev)


俺(p)の前にいる奴(p->prev)の後(p->prev->next)は
俺の後にいる奴(p->next)だ、と。 つまり俺が列から外れます。
(p->prev->next = p->next)


        p->prev           俺(p)の後にいる奴(p->next)
        ↓              ↓
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑       ↑  ↑
               p        |  c
                                            p->next->prev

p->next->prev = p->prev;
逆方向のリンクから、俺を外してます。

上記のは、なんとか理解できました。

次のがちょっと図があるのですが、理解ができません。

*pが挿入する要素 *cは挿入する場所

[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c
p->next = c;
c->prev = p;
cとpを入れていますが、これって要素のどの部分でもなくて
変数の名前じゃないですか?これを入れて意味があるのです
かね?

p->prev = c->prev;
c->prev->next = p;
挿入の場合だとない部分だからさっきと違いますね。
さっきの考えとうまくいかないなぁ

/* 両隣へポインターをつなぐ */
p->prev = c->prev;
p->next = c;
俺の前は貴様の前の奴、俺の後は貴様。
なので俺の後に貴様が並ぶ。

/* 両隣のポインターをつなぎ換える */
c->prev->next = p;
c->prev = p;
貴様の前の後を俺に、貴様の前は俺。
逆方向のリンクです。



この投稿にコメントする

削除パスワード

No.22616

Re:数珠つなぎの図
投稿者---まきじ(2005/08/13 15:56:53)


>*pが挿入する要素 *cは挿入する場所

p は挿入する、ノードを指しています。
c は挿入したい後ろのノード。

>[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
>           ------------------  ------------------
>               ↑          ↑
>               p           c
>p->next = c;
>c->prev = p;

>cとpを入れていますが、これって要素のどの部分でもなくて
>変数の名前じゃないですか?

p は、malloc() で struct list 型のサイズ分確保した領域への
ポインタが格納されいます。

p が指し示す先は、prev data next というメンバを持った構造体です。
そのメンバの next と prev も p と同様に、
prev data next というメンバを持った構造体へのポインタです。

prev next に格納されているポインタを変更する事によって、
リストを作っています。

例えば、最初に確保された領域へのポインタが head に格納されいるとします。
prev next は仮に NULL とします。

次に、新たに、struct list* 型 の変数 p を用意して、malloc() で領域を
確保し、その領域へのポインタを p に格納します。

head と p を繋ぐには、head が指し示す構造体のメンバの next に p を
格納するだけです。

next も p と同様に struct list* 型ですから、新たに確保された領域のポインタ
が格納されている p を代入してやることで、head の後ろに繋がります。


この投稿にコメントする

削除パスワード

No.22617

Re:数珠つなぎの図
投稿者---NykR(2005/08/13 18:13:01)


一つだけやってみますね。

p->next = c;

pが指してる構造体(*p)の、メンバー((*p).next)に
cが指してる構造体(*c)を指させます。
# p-> は(*p). に置き換えることができます

つまり、

p---->[[prev][data][next]]
c---->[[prev][data][next]]

が、
                     +--------+
                     |        |
p---->[[prev][data][next]]    |
c---->[[prev][data][next]]<---+


となります。


続きは自分でどうぞ

p->prev = c->prev;
c->prev->next = p;
c->prev = p;

# c->prevが指している構造体も書き加えなければいけませんが


この投稿にコメントする

削除パスワード

No.22622

cとpは自動的に決まるのですね
投稿者---CENTER(2005/08/14 09:51:41)


NykR 様 まきじ 様

お忙しい中、お答えいただきありがとうございます。

>一つだけやってみますね。
>
>p->next = c;
>
>pが指してる構造体(*p)の、メンバー((*p).next)に
>cが指してる構造体(*c)を指させます。
># p-> は(*p). に置き換えることができます
>
>つまり、
>
>p---->[[prev][data][next]]
>c---->[[prev][data][next]]
>
>が、<pre>
>                     +--------+
>                     |        |
>p---->[[prev][data][next]]    |
>c---->[[prev][data][next]]<---+</pre>
>
>となります。

p->next = c;の場合は、cは、自動的にpとcの
next同士を指すということですね。
p->nextのnextの部分で判断すればいいんですね。

c->prev = p;の場合は、prev同士を指し示す
ということですね。
これも同じですね。
どの部分ということは、自動的に決まるのですね。
やっとわかりました。

ちょっとだけ確認
それぞれの指している部分について。

>p->prev = c->prev;

            p->prev               c->prev
       ↓                    ↓
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c

>c->prev->next = p;

                                  c->prev->next
                                   ↓
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c

>c->prev = p;

                                  c->prev
                                   ↓
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c

それぞれ指している部分は、上記の通りですよね。
でも、一部p->prev = c->prev;などは、考えると
おかしな部分が出てくるのですが。



この投稿にコメントする

削除パスワード

No.22624

Re:cとpは自動的に決まるのですね
投稿者---まきじ(2005/08/14 13:35:30)


>p->next = c;の場合は、cは、自動的にpとcの
>next同士を指すということですね。

仰ってる意味がわかりません。
p -> next が指し示す所を c が指し示す所にする。

>p->nextのnextの部分で判断すればいいんですね。

何を?

>c->prev = p;の場合は、prev同士を指し示す

仰ってる意味がわかりません。
c -> prev が指し示す所を p が指し示す所にする。

>p->prev = c->prev;

   p->prev       c->prev
    ↓          ↓
------------------  ------------------
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c

next の部分だけではなく全体です。


>c->prev->next = p;


[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p        c (c->prev->next)

この図からいくと c -> prev -> next は c と同様です。

>c->prev = p;

              c->prev
               ↓
           ------------------
[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
           ------------------  ------------------
               ↑          ↑
               p           c

>でも、一部p->prev = c->prev;などは、考えると
>おかしな部分が出てくるのですが。

どこがですが?


この投稿にコメントする

削除パスワード

No.22625

理解していたはずなんですが^_^;
投稿者---CENTER(2005/08/14 19:48:33)


まきじ 様

お忙しい中、お答えいただきありがとうございます。

要素の削除の部分では理解していたと思ったんです
が、やはり間違っているようですね。

>>p->next = c;の場合は、cは、自動的にpとcの
>>next同士を指すということですね。
>仰ってる意味がわかりません。
>p -> next が指し示す所を c が指し示す所にする。
>>p->nextのnextの部分で判断すればいいんですね。
>何を?
>>c->prev = p;の場合は、prev同士を指し示す
>仰ってる意味がわかりません。

そうですね、pとcは、それぞれ、prevとnextの要素が
入っているので、それが、c->prev = pの時に、pは、
prevに変わる思ったのです。だって、pとcってあいま
いですよね。そこを指しているかわかりませんよね。

それとも、pとcは、char str[20];のstrが配列の先頭
アドレスを指しているのと同じで決まったところをさし
ているのですかね。

>c -> prev が指し示す所を p が指し示す所にする。
>
>>p->prev = c->prev;
>
>   p->prev       c->prev
>    ↓          ↓
>------------------  ------------------
>[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
>           ------------------  ------------------
>               ↑          ↑
>               p           c
>
>next の部分だけではなく全体です。

全体ですか?おかしいですねp->prev = c->prev;これは
全体を指しているのですね・・・
でも、全体というと、そこにどのような情報が入ってい
るかが疑問ですね。prevとnextの部分だと前の要素や後
ろの要素のアドレスが入っていると考えると自然に考え
られるのですが、全体となるとわからないですね。
でも、リストって要素のおのおののprevとnextの部分を
つなぎ換えて要素を削除したり付け加えたりするのです
よね。全体を指し示すと考えるとどう繋ぐとかイメージ
できなくなりますね。

削除のときそういう考え方でやったらなっとくがいったん
でうすがね。部分を指すと考えて・・・

>c->prev->next = p;
> >
>[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
>           ------------------  ------------------
>               ↑          ↑
>               p        c (c->prev->next)
>
>この図からいくと c -> prev -> next は c と同様です。

c->prev->next、これはpのnextの部分かと思いましたね。
削除の時の考えだとうまくいったのですが、おかしくなり
ましたね。

>>c->prev = p;
>
>              c->prev
>               ↓
>           ------------------
>[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
>           ------------------  ------------------
>               ↑          ↑
>               p           c

すいませんでした、考えてるいるのと全然違いましたね。
もう少し頭をしぼってきます。


この投稿にコメントする

削除パスワード

No.22626

Re:理解していたはずなんですが^_^;
投稿者---nop(2005/08/14 20:26:53)


>そうですね、pとcは、それぞれ、prevとnextの要素が
>入っているので、それが、c->prev = pの時に、pは、
>prevに変わる思ったのです。

「c->prev = p;」で「p」が「prev」に変わるのなら、
「a = 1;」は「1」が「a」に変わる、
と言う解釈ですか?


この投稿にコメントする

削除パスワード

No.22627

Re:理解していたはずなんですが^_^;
投稿者---まきじ(2005/08/14 20:43:45)


>全体ですか?おかしいですねp->prev = c->prev;これは
>全体を指しているのですね・・・
>でも、全体というと、そこにどのような情報が入ってい
>るかが疑問ですね。

構造体の情報が入ってる。

>>c->prev->next = p;
>> >
>>[prev][data][next]<-->[prev][data][next]<-->[prev][data][next]
>>           ------------------  ------------------
>>               ↑          ↑
>>               p        c (c->prev->next)
>>
>>この図からいくと c -> prev -> next は c と同様です。

>c->prev->next、これはpのnextの部分かと思いましたね。
>削除の時の考えだとうまくいったのですが、おかしくなり
>ましたね。

c -> prev ->next が指すオブジェクトなのか?
next 自体がどの next のなんか?
で違って来ます。
他の 2 つは、前者だったので、同様に前者で説明しました。
後者なら、他の 2 つが間違ってる事になります。

前者の場合、「c -> prev ->next が指すオブジェクトは c と同じ」という意味。
後者の場合、c -> prev が指すオブジェクトの next は、p -> next です」という意味

if(c -> prev -> next == c)、if(c -> prev == p) の様に
if 文確認してみてください。


この投稿にコメントする

削除パスワード

No.22633

Re:理解していたはずなんですが^_^;
投稿者---とおり(2005/08/14 21:24:02)


リスト構造うんぬんの前に、単純に構造体やそれを指すポインタ、
さらにC言語基礎の理解が不足しているのは間違いありません。
現状の理解度では、リスト構造を扱うのはとても無理だと思います。
基本を差し置いて、先を急いでも時間を浪費するだけです。

まきじさんが懇切丁寧に応答されていますが、横からやり取りを
見ていても、全く埒があかないと感じました。
↑の方で一度書きましたが、もう一度引用しておきます。
本ホームページの解説を(最初から)一通り読むことをお勧めします。

>そもそもこの掲示板は、「初心者のためのポイント学習C言語」という、まさにあなたの
>ような方のためにあるC言語解説ページ内の一掲示板だということに気づいていますか?
>そちらのページには、構造体やリスト構造についてもきっちり絵入りで解説されています。
>そこを一読した上で理解できない点があれば、ポイントを絞って再度質問すると良いでしょう。


この投稿にコメントする

削除パスワード

No.22714

これでどうでしょうかね・・・
投稿者---CENTER(2005/08/18 12:01:31)


すいません、名前は、省略させていただきますが、お忙しい
中、私の質問にお答えいただいたみなさん、ありがとうございます。

いろいろと調べてみました・・・

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

                
             +----+
        |    |
        |    |   
             ↓   |                  c
+--------------+  |                  +--------------+
|    |    |    |  |                  |    |    |    | 
|prev|data|next|  |           +------|prev|data|next|
|    |    |    |  |           |      |    |    |    |
+--------------+  |         |      +--------------+   
             |    |           |      ↑
             |    |           |      |                     
             |    |           |      |
           |   p|          ↓      |
             |   +--------------+    |
             |   |    |    |    |  |
             +-→|prev|data|next|----+ 
                 |    |    |    |
                 +--------------+

手順・・・
p->prev = c->prev;
p->next = c;
c->prev->next = p;
c->prev = p;

調べていてわかったのですが、p->prev = c->prev;で
p->prevは、pのprevの部分を指してc->prevは、cの
prev部分でなくcの前の要素のprev部分を指すのですね
ここらへんがこんがらがっていました。

やはりpとcとすることによって前または、後ろの要素と
繋げているのですね。
ということは、cというのは、cのprevの部分と等価という
ことですね。
pというのも、pのprevの部分と等価ですね。
でも、待てよc->prev = p;で考えるとpは、pのnextの
部分とも等価と考えられますね。

ここらへんが、まだ、納得がいきませんが・・・

でも、なんとか半分は理解できた気がします。

何かあればご指導ください。









この投稿にコメントする

削除パスワード

No.22720

Re:これでどうでしょうかね・・・
投稿者---まきじ(2005/08/18 14:35:41)


>p->prevは、pのprevの部分を指して

p の前の要素です。

>c->prevは、cのprev部分でなくcの前の要素のprev部分を指すのですね

c の前の要素です。
構造体、全体です。

>cというのは、cのprevの部分と等価ということですね。

完成したリストの、ある要素を c が指している場合、等価しない。

>pというのも、pのprevの部分と等価ですね。

等価しない。

# どなたかが、仰ってましたが、構造体、ポインタ、
# 構造体へのポインタを勉強し直してください。


この投稿にコメントする

削除パスワード

No.22730

Re:これでどうでしょうかね・・・
投稿者---NykR(2005/08/18 17:57:51)


>               p->prev = c->prev;で
> p->prevは、pのprevの部分を指してc->prevは、cの
> prev部分でなくcの前の要素のprev部分を指すのですね

pには「prevの部分」なんてものは存在しません。
pが指している構造体にprevというメンバーが存在します。
同様にcにも「prev部分」なんてものはありません。
また、cには前の要素もありません。
cが指している要素に前の要素があるのです。図を描くなら

           
             +----+
        |    |
        |    |   
             ↓   |                  c
+--------------+  |                  +--------------+
|    |    |    |  |                  |    |    |    | 
|prev|data|next|  |           +------|prev|data|next|
|    |    |    |  |           |      |    |    |    |
+--------------+  |         |      +--------------+   
             |    |           |      ↑
             |    |           |      |                     
             |    |           |      |
           |   p|          ↓      |
             |   +--------------+    |
             |   |    |    |    |  |
             +-→|prev|data|next|----+ 
                 |    |    |    |
                 +--------------+


ではなく
                                            +--------------+
                             p            |              |
              +----+           |            |              |
        |    |           |            |              +----c
        |    |        |            |
             ↓    |     +-----+           ↓
+--------------+   |     |           +--------------+
|    |    |    |   |     |           |    |    |    | 
|prev|data|next|   |     |    +-------prev|data|next|
|    |    |  | |   |     |    |      |    |    |    |
+------------|-+   |     |  |      +--------------+   
             |     |     |    |      ↑
             |     |     |    |      |                     
             |     |     |    |      |
           |     |    ↓   ↓      |
             |   +-|------------+    |
             |   | |  |    |    |  |
             +-→|prev|data|next-----+ 
                 |    |    |    |
                 +--------------+


の様にすべきでしょう。


この投稿にコメントする

削除パスワード

No.22885

ありがとうございました
投稿者---CENTER(2005/08/29 20:39:20)


みなさん返事が遅れて申し訳ありませんが
解決しました。

本当にありがとうございましたm(__)m


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧