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

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

 詳しくはこちら


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

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


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

No.22566

リストとハッシュ
投稿者---CENTER(2005/08/10 22:23:53)


リストについての記述があったのですがやはりわかりません
やはりこれは、入門ではないですね。
もうひと山越えれば大丈夫そうですが・・・ここまで来るのに
苦労しています。
質問
リストについてですが、char line[256];は、データの部分で
すか?p->prev->next = p->next;これは、かなり複雑ですね
こんな参照の方法ありましたっけ?
p->next->prev = p->prev;これも同じです誰かやさしくわかる
かたいませんか?
/* 両隣へポインターをつなぐ */
p->prev = c->prev;
p->next = c;
/* 両隣のポインターをつなぎ換える */
c->prev->next = p;
c->prev = p;
上記も複雑ですね・・・
解説お願いします・・・
free(p);はメモリの解放ですか?

リスト

*prevは前の要素へのポインター
*nextは後ろの要素へのポインター

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

delete_line(LIST *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}

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

ハッシュ
質問
u = ((u << 8) + *s) % HASHSIZE;がハッシュ関数というものですか?
どういう計算ですかね?
これを計算してデータを探すということですね・・・

ハッシュを使うと、データ構造の中からあるデータを検索するのに、
データの比較などせずに基本的には計算するだけで検索することが
できる。

int hash(char *s)
{
    unsigned int u;
    
    for (u = 0; *s != '\0'; s++)
        u = ((u << 8) + *s) % HASHSIZE;
    return ((int)u);
}

HASHSIZEの値は素数が最適

出典 作ってわかるCプログラミング
日下部陽一 



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:リストとハッシュ 22567 まきじ 2005/08/10 23:10:27
<子記事> Re:リストとハッシュ 22569 επιστημη 2005/08/10 23:41:12


No.22567

Re:リストとハッシュ
投稿者---まきじ(2005/08/10 23:10:27)


>リストについてですが、char line[256];は、データの部分で
すか?

そうです。

>p->prev->next = p->next;これは、かなり複雑ですね
こんな参照の方法ありましたっけ?

可能です。
prev は 現在のノードの 1 つ前のノードで、そのノードの next
ですから、現在のノードですね。

>p->next->prev = p->prev;これも同じです誰かやさしくわかる
かたいませんか?

上記と同様です。

>/* 両隣へポインターをつなぐ */
>p->prev = c->prev;
>p->next = c;

c が指しているノードの前に p が指してるノードを追加。

c の前ですから、 p の前にくるのは、c の前にあるノード
よって、p->prev = c->prev となる。
c の前ですから、p の次は c よって p->next = c となる。

>/* 両隣のポインターをつなぎ換える */
>c->prev->next = p;
>c->prev = p;

c の前にあるノードの次は p になるので c->prev->next = p となる。
c の前に、p を追加したので、c の前は p よって c->prev = p となる。

>free(p);はメモリの解放ですか?

そうです。

>*prevは前の要素へのポインター
>*nextは後ろの要素へのポインター

これが解っていたら解りそうですが・・・

>u = ((u << 8) + *s) % HASHSIZE;がハッシュ関数というものですか?
>どういう計算ですかね?

ハッシュ値の求め方は決まってません。
別になんでもよかったはずです。

>これを計算してデータを探すということですね・・・

そうです。


この投稿にコメントする

削除パスワード

No.22570

Re:リストとハッシュ
投稿者---あきき(2005/08/11 00:06:12)


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

>>p->prev->next = p->next;これは、かなり複雑ですね
>
>>/* 両隣へポインターをつなぐ */
>>p->prev = c->prev;
>>p->next = c;
>
>>/* 両隣のポインターをつなぎ換える */
>>c->prev->next = p;
>>c->prev = p;
>
となると、構造体変数のメンバーへの参照の時、メンバーがアドレスであれば、アロー演算子でつなぐというわけですか(メンバーが自己参照構造体ですから)。


この投稿にコメントする

削除パスワード

No.22571

Re:リストとハッシュ
投稿者---まきじ(2005/08/11 00:09:46)


>構造体変数のメンバーへの参照の時、メンバーがアドレスであれば、アロー演算子でつなぐというわけですか(メンバーが自己参照構造体ですから)。

構造体のメンバーがポインタの時ではなく、
構造体の変数がポインタの時に、アロー演算子で参照する。


この投稿にコメントする

削除パスワード

No.22572

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


よくわかりました。ありがとうございます。


この投稿にコメントする

削除パスワード

No.22569

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


> p->prev->next = p->next;これは、かなり複雑ですね
> こんな参照の方法ありましたっけ?
> p->next->prev = p->prev;これも同じです誰かやさしくわかる
> かたいませんか?

絵を描きましょう。

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

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

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

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

u = ((u << 8) + *s) % HASHSIZE;がハッシュ関数というものですか?
どういう計算ですかね?
これを計算してデータを探すということですね・・・

たくさんの箱を用意し、データを格納する箱の番号をコレで求めます。
検索時にこの値が示す箱を覗けばイッパツで見つかる。
ただし、異なるデータが同じ数を返すことがある(ハッシュの衝突)ので、
適宜衝突回避策が必要。



この投稿にコメントする

削除パスワード

No.22582

絵を書きたいのですが・・・もう少し質問
投稿者---CENTER(2005/08/11 20:43:11)


επιστημη 様、まきじ 様

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

>絵を描きましょう。

とりあえず、絵を書きたいのですが、ちょっと構造体が
実際問題どのようにメモリに展開されているか想像がつ
きません。

ちょっと整理したいのですが、根本から・・・・・・・

>p->prev->next = p->next
> 俺(p)の前にいる奴(p->prev)の後(p->prev->next)は
> 俺の後にいる奴(p->next)だ、と。 つまり俺が列から外れます。
>
>p->next->prev = p->prev;
> 逆方向のリンクから、俺を外してます。
>
>/* 両隣へポインターをつなぐ */
>p->prev = c->prev;
>p->next = c;
> 俺の前は貴様の前の奴、俺の後は貴様。
> なので俺の後に貴様が並ぶ。
>
>/* 両隣のポインターをつなぎ換える */
>c->prev->next = p;
>c->prev = p;
> 貴様の前の後を俺に、貴様の前は俺。
> 逆方向のリンクです。

整理・・・
まず、下記ですね・・・
*prevは前の要素へのポインター
*nextは後ろの要素へのポインター

ということは、
[][][][][][][][][][][][]
     ↑  
←後 ここだとして 前→

char line[256]; ← これがデータの内容・・・

pとcは、何を表しているのですか?
pとcを宣言してはじめて使えるようになるのですか?

すいませんご指導ください。

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

delete_line(LIST *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}

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



この投稿にコメントする

削除パスワード

No.22584

Re:絵を書きたいのですが・・・もう少し質問
投稿者---まきじ(2005/08/11 20:51:57)


> [][][][][][][][][][][][]
>    ↑  
>←後 ここだとして 前→
>pとcは、何を表しているのですか?

[][][p][c][][][][][][][][]
←(prev)後   前(next)→

>pとcを宣言してはじめて使えるようになるのですか?

変数ですから、宣言しないと使えないです。

# わざわざ、名前変えなくても・・・


この投稿にコメントする

削除パスワード

No.22585

Re:絵を書きたいのですが・・・もう少し質問
投稿者---επιστημη(2005/08/11 20:57:48)


> pとcは、何を表しているのですか?
> pとcを宣言してはじめて使えるようになるのですか?

ちょ、ちょい待ち。
あなたはここに示された関数群を使って実際にリストへの要素の
追加/削除をするお試しコードを書いていないのですか?

それじゃ疑問だらけでわかんないのも当然なんだが。




この投稿にコメントする

削除パスワード

No.22594

はい、そうなんです。すいませんm(__)m
投稿者---CENTER(2005/08/12 00:27:47)


επιστημη 様

とりあえず出典は、作ってわかるCプログラミングです。
入門書だそうですが、手にとってみるとかなり難解です。

それで、途中にデータ構造についての説明が載っていま
した。でも、私は初心者ですから、そこでつまづいてし
まって止まっています。

他の入門書ではないやりかたですね・・・・

選択を間違えたと思っています。

でも、最後まで読みたいのでなんとか無理やり
理解しようとしています。

>ちょ、ちょい待ち。
>あなたはここに示された関数群を使って実際にリストへの要素の
>追加/削除をするお試しコードを書いていないのですか?
>
>それじゃ疑問だらけでわかんないのも当然なんだが。

載ってるコードは、下記だけだったんですよ・・・・
でも、理由になりませんね、自分でこれを完成させて
実行してみるというのが本来の学習ですね。

でも、今、私にはその能力はありませんね。

図々しいですが、助けていただければうれしいです。

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

delete_line(LIST *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}

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







この投稿にコメントする

削除パスワード

No.22596

Re:はい、そうなんです。すいませんm(__)m
投稿者---επιστημη(2005/08/12 01:56:02)


> それで、途中にデータ構造についての説明が載っていま
> した。でも、私は初心者ですから、そこでつまづいてし
> まって止まっています。

> 他の入門書ではないやりかたですね・・・・

そんなことはないんじゃないかな。
少なくとも僕は「データ構造を説明しない入門書」はお薦めしない。

> 載ってるコードは、下記だけだったんですよ・・・・
> でも、理由になりませんね、自分でこれを完成させて
> 実行してみるというのが本来の学習ですね。

> でも、今、私にはその能力はありませんね。
> 図々しいですが、助けていただければうれしいです。

複数の struct list_t が数珠繋ぎになってる絵が
書けない限り完成コードが提示されても理解できませんよ。




この投稿にコメントする

削除パスワード

No.22597

こんな感じですかね・・・・
投稿者---CENTER(2005/08/12 07:33:58)


επιστημη 様

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

>そんなことはないんじゃないかな。
>少なくとも僕は「データ構造を説明しない入門書」はお薦めしない。

そうですか・・・

>複数の struct list_t が数珠繋ぎになってる絵が
>書けない限り完成コードが提示されても理解できませんよ。

なるほど・・・

[p][data][c] ← 1つの要素はこんな感じですかね・・・

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

こういう参照の仕方はじめてみます・・・

p->x この参照の仕方は見るのですがね・・・
意味は多分ですが、pが指すあるメモリ上にある
構造体のxメンバーですよね・・・

間違ってたりして・・・

とにかく複雑になりましたね・・・

なんとか頭しぼってみます・・・


この投稿にコメントする

削除パスワード

No.22598

Re:こんな感じですかね・・・・
投稿者---とおり(2005/08/12 07:54:04)


>間違ってたりして・・・

・・・ばかりで、自分で調べようというニュアンスには、私には見えません。
リスト構造などのデータ構造は、ネット上でいくらでも解説が見つかります。
本にないなら、ネット上で検索するなどの努力はしたのでしょうか?
というか、επιστημηさんがほとんど解説済みなので、あなたの応答を見ている限り、
C言語に対する基礎的な理解が不足しているのではと思います。

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


この投稿にコメントする

削除パスワード

No.22599

Re:こんな感じですかね・・・・
投稿者---まきじ(2005/08/12 08:31:25)


>[p][data][c] ← 1つの要素はこんな感じですかね・・・

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

ですね


この投稿にコメントする

削除パスワード

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現在のポインタ先からの相対的指定なんでしょうか


この投稿にコメントする

削除パスワード

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-----+ 
                 |    |    |    |
                 +--------------+


の様にすべきでしょう。


この投稿にコメントする

削除パスワード

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