一方向リストプログラムの問題がわかりません

Question

指定されたキーを削除するというコードです。

scanf("%d",&data); //指定するキーをdataに入れる
a = &listhead; //listheadのアドレスをaに入れる
while(a -> next != NULL){ //listheadの中の変数nextがNULLでない間
if( a -> next -> key == data) //listheadの変数nextに入っているkeyがdataと同じだったら
break;
a = a -> next; //aをaの変数nextのアドレスに変える
}

if( a -> next == NULL) //aの変数nextがNULLだったら
prtinf("キーがありません");
else {
ptr = a -> next; //①
a -> next = ptr -> next (またはa -> next -> next);②
free( ptr ); //ptrを削除(解放)
}

このように解釈しているのですが、特に①と②で何をしているのかがわかりません。
ptrが宣言されていないので、ptrが何なのか、aとの違いはなんなのか....

ご教授いただけたらと思います。
よろしくお願いいたします。

Answer 1

変数の宣言文が全くありませんから、サンプルプログラムではないですよね。
課題か演習問題でしょうか。構造体のポインタの使い方に関する問題ですね。
だとすると、解答を書いてしまうより考え方をサポートするほうがよいと思いますので
以下を参考に自分で考えてみてください。

1行ずつ見ていって解ること・解らないことを並べてみましょう。
1行目
%d で読み込んでいるので、data は int型であることが解ります。
2行目
a は listhead と同じ型のポインタ
listhead の型は解らない
3行目
a->next とあるので、a は構造体のポインタ → listhead は構造体
4行目 ☆ここがポイント
data と比較しているので、a->next->key は data と同じ int型
では a->next はなんでしょう？

と、順に追ってみてください。

Answer 2

ptrは、listheadのポインタ変数。
a や a->next も同じくlistheadのポインタ変数ですね。

削除するキーが見つかったのが、a->nextなんで、
ptrにa->nextを保持させておいて、a->nextにa->next->nextを代入(繋げる)。
で、いらなくなったptr(保持しておいたa->next)のメモリを解放。

Answer 3

すでに回答は出ているので分かりやすく言いますと、この問題（後半）は、
並んでいる列から誰か抜けて、前に詰め直す作業をしています。

そして、その列というのは一方向（単方向）リストで、
ポインタで前につながっているわけですから、
ポインタを前につなぎ直すことが削除と等しくなるわけです。

番号札を持っていないとダメなタイプの窓口で、
番号札を前の者に渡してしまうと、
たとえそこに並んでいても順番が飛ばされるようなイメージです。

理解できればいくらでも問題は解けるようになるので、
何をしているのかのイメージを描くようにしましょう。

Answer 4

一方向連結リストを自体をよくわかってないのではないでしょうか。

一方向連結リストはノード(構造体として定義)の集まりです。
ノードの保持する情報は、

• 記憶したい値
• 次のノードのアドレス

です。
「俺は3という数を覚えておくように言われた、次の数は2000番地にいる奴が知っているぞ」
みたいな感じです。

a:削除対象の手前のノード
foo->next:ノードfooの次のノード(のアドレス)
ptr:削除対象のノード
と脳内変換すれば意味がわかると思います。
（というわけでこのコード、変数の名前があまりよろしくないです。）

A--->B--->C--->Dという風に連結されたリストがあって、Cを消したいとなれば
Cの手前であるBの接続先を
Cの次であるDに変えますよね？

Answer 5

結論から言うと
ptrはリスト中でaの次の要素です。
(同じリストの別要素なので、各要素が示す値が異なるだけで構成は同じ)

実際に値を当てはめてみればわかりやすいと思います。

たとえば1->2->3となっているリストで
keyが2の場合、
whileはa->next->key == 2
つまりa->key==1で抜けます。

このとき
a->key == 1
a->next->key == ptr->key == 2
a->next->next->key == ptr->next->key == 3
です。

ここで、a->next = ptr->nextにする(aの次をaの次の次にする)ので、
1->2->3で1から2を指しているポインタを3を指すようにします。
これで1->3となってリストから2が消えます。

Answer 6

指定されたキーのデータを削除するために、その前後のデータのリンクをつなげなおしています。

a,b,c,d,eとデータが並んでいます。
aはbへのリンクを持っています。
bはcへのリンクを持っています。
cも
dも

次のデータへの参照（リンク）を持つことによって次のデータにアクセスできるのがリストなのですが、例えばbがただ削除されてしまっては参照が途切れてしまうので、bが削除される場合はaが保持する次の参照をcに変更してやります。

それを行っているのが①、②です。

Comments

[ababab]

回答ありがとうございます。
データのリンクをつなげなおすというのがよくわかりませんでした..すみません。
ptr = a -> nextは、ptrの中にaの中にある変数nextの値を入れるということでよろしいでしょうか？

[omochi]

そうなります。
ptrはポインタなのでアドレスが代入されます。