C言語のK&Rで簡易スタックを実装するサンプルコードが載っていたのですが、これの使い方を教えてください。

https://gist.github.com/DQNEO/5413292

afreeにアドレスを渡してメモリ解放してもらう仕組みになっているのですが、これだと使う側がスタックに積んだ各要素の先頭アドレスを記憶・管理しなきゃいけないので、allocとafreeだけではスタックを実現できないのではないかと思ったのです。

スタックに積んだ要素のアドレスを配列に入れておけばできそうな気がしますが、やはりそうするしかないのでしょうか・・・。(配列でスタックを作ったら意味がないよなーという気がしました)

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2013/04/18 23:59:42
  • 終了:2013/04/26 00:00:07

回答(3件)

id:Bookmarker No.1

しおり回答回数191ベストアンサー獲得回数342013/04/19 00:57:11

ポイント34pt
void afree(char *p)
{
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
        allocp = p;
    }
}

の写し間違いだと思いますが、要するにalloc()した順とは逆にafree()しなければならないという所が「簡易」なのでしょう。

id:DQNEO

不等号間違っていました。ご指摘ありがとうございます。

1回alloc()して1回afree()するなら簡単なのですが、N回alloc()してN回afree()しようとすると極度に難易度が高くなり、どうやって実装するのかと質問を立てた次第です。

2013/04/19 19:20:27
id:quintia No.2

quintia回答回数561ベストアンサー獲得回数702013/04/19 10:22:24

ポイント33pt

K&Rが手元にないので確認できないですが、このソースだけを見る限りでは、これは「スタック」の簡易な実装ではなくて、「スタックを使ったメモリ割り当て」の簡易な実装なんじゃないでしょうか?

alloc,afreeは、スタックへの操作であるpush,popとして使うものじゃなくて、malloc,freeの代替として使うものではないかと。
もちろん実験的/簡易的な実装であってかわりに使えるようなものではないので、つまりこれは「(malloc,free がヒープによるメモリ割り当てであるのに対して)スタックによるメモリ割り当てはこんな感じになりますよ」という説明なんだと思います。

id:DQNEO

> 「スタック」の簡易な実装ではなくて、「スタックを使ったメモリ割り当て」の簡易な実装なんじゃないでしょうか?

なるほどそうかもしれません。

ただ、K&Rにはあの関数でlast-in first-outのstackが実現できると書いてあるので、どうやってやるのだろう?と思ったのです。

2013/04/19 19:22:27
id:DQNEO

質問者から

DQNEO2013/04/20 11:45:25

一応補足ですが、質問は「使い方を教えてください。」です。

id:fhtdd No.3

fhtdd回答回数174ベストアンサー獲得回数42013/04/25 23:52:56

ポイント33pt

http://homepage3.nifty.com/mmgames/c_guide/c_kandr.html
こちらを参考にしてみては?

  • id:Mook
    K&R を確認してみましたが、この章は「ポインタと配列」の「アドレス計算」の実装例として、alloc と afree を掲載しています。
    ただ、取得順序と開放順序に制限(先に確保したものを後で開放する)があるため「スタック的な構造になっている」という意味です。
    この制限がないメモリ管理としての malloc および free については別の章(第2版では8.7)で言及されています。

    これをスタックの実装と捕らえるのは、誤解でしょう。
  • id:DQNEO
    あくまで「スタック的」ということであって「スタック」ではないと解釈すればよろしいのでしょうか?
    しかし本文にはlast-in first-outのstackが実現できると書いてある気がします。

    それ以前に、allocとafreeの使い方が(2回afreeする方法とか)がわからなかったのですが、このサンプルコードに実用性を求めること自体が間違っているのですかね・・。
  • id:Mook
    上にも書いたようにこれは実用性というよりは、C でのポインタと配列を理解するための実例です。

    書籍には「afreeへの呼び出しをallocへの呼び出しと逆の順序で実行しなければならないという意味で、原始的である。allocとafreeにより管理される記憶はスタック,
    すなわちlast-in,first-outのリストである。」とあるはずです。

    これは使う際には下記のように取得した順序と逆の順序で開放しなければなりません。

    char *mp[10];
    int i;
    for( i=0 ; i<10 ; i++ ) mp[i] = alloc(100);

    for( i=9 ; i>=0 ; i-- ) afree(mp[i]);

    この制約による性質を指してスタックであると書いています。
    スタックとはリスト管理のアルゴリズムの名称であって、その性質を備えてあれば何でもスタックと呼ぶことはできます。

    しかし、リスト管理としてスタックを実装する場合は、スタックポインタを用い、push と pop の I/O 関数(メソッド)を実装するのが一般的だと思います。
  • id:DQNEO
    おお!
    このような回答を待っておりました。

    たしかに固定長の配列でポインタを管理すればいけそうですね。

    そこに思い至りませんでした。

    この方法でやってみます。
    どうもありがとうございました。
  • id:DQNEO
    Mookさんをベストアンサーにしたいのですが、どうすればいいんでしょうか・・・
  • id:quintia
    > この方法でやってみます。
    その使い方をするならmallocとfreeでいいんじゃ……?
  • id:DQNEO
    できました!!

    http://dqn.sakusakutto.jp/2013/04/c_kr_stack.html

    >quitiaさん

    コメントありがとうございます。
    まだ勉強中なので、mallocとfreeを知らないのです。
  • id:Mook
    ポイントは回答された方に差し上げてください。
    質問の意図が良くわからずに、コメントしただけなので。

    C を修得中のようですが、あわせてアルゴリズム(アルゴリズム事典のような本もあります。)について学ぶとよいかと思います。
    Stack だけでなく、FIFO や 2分木、ソート(シェルやクイック)など基本的なところを知っておくと、K&Rを読んでも理解の幅が広がるかと思います。

    提示されたコードを見ましたが、そのようにまずは自分で考えて実装してみるとよいかと思います。


    懐かしくなって調べてみたら、翻訳された石田先生はもうお亡くなりになっていたんですね。K&Rの翻訳は素晴らしいお仕事でした。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません