ページ 11

スタックの実現

Posted: 2009年11月11日(水) 11:20
by 初心者A
大学の課題でスタックを実現せよというものです。
組むには組んだのですが、実行結果が思ったものになりません。
アドバイスをお願いします。
Cの知識は入門書レベル、環境はVine Linuxでgccでコンパイルしています。
欲しい実行結果:
入力
a
b
c
EOF
c
b
a
#include <stdio.h>

typedef struct {
  char box[100];
  int top;
} st;

void create(st *s);
char top(st *s);
void pop(st *s);
void push(char x, st *s);

int main(void)
{
  st *s;
  int x;

  create(s);

  while ((x = getchar()) != EOF){
    push(x, s);
  }

  printf("%c\n", top(s));
  pop(s);
  printf("%c\n", top(s));
  pop(s);
  printf("%c\n", top(s));
  
  return 0;
  
}


void create(st *s)
{
  s->top = 0;
}

char top(st *s)
{
  return (s->box[s->top]);
}

void pop(st *s)
{
  (s->top)--;
}

void push(char x, st *s)
{
  (s->top)++;
  s->box[(s->top)] = x;
}

Re:スタックの実現

Posted: 2009年11月11日(水) 11:32
by たかぎ
pushのインクリメントするタイミングが変です。
s->box[(s->top)] = x;
  (s->top)++;
ではないですか?

Re:スタックの実現

Posted: 2009年11月11日(水) 11:33
by たかぎ
top関数も変ですね。

Re:スタックの実現

Posted: 2009年11月11日(水) 11:42
by 初心者A
インクリメントを後にするとprintfで表示するときに
文字が何も入ってない所を参照してしまわないでしょうか。
後top関数はスタックの現在の一番上の文字を返す関数のつもりで
書いていますが、これがおかしいのでしょうか。

Re:スタックの実現

Posted: 2009年11月11日(水) 11:55
by たかぎ
> インクリメントを後にするとprintfで表示するときに
> 文字が何も入ってない所を参照してしまわないでしょうか。
> 後top関数はスタックの現在の一番上の文字を返す関数のつもりで
> 書いていますが、これがおかしいのでしょうか。

そうですね。
ですので、全体的な整合性を見直す必要があります。
普通、スタックは上位アドレスから下位アドレスに向かって延びるようにします。
具体的には、
void create(st *s)
{
  s->top = sizeof(s->box)/sizeof(s->box[0]);
}

void push(char c, st *s)
{
  --s->top;
  st->box[s->top] = c;
}

char top(st *s)
{
  return s->box[s->top];
}

void pop(st *s)
{
  ++s->top;
}
のようにです。

Re:スタックの実現

Posted: 2009年11月11日(水) 12:40
by non
スタックのメモリ確保がされてないのでは?
それに、入力は
abc[EOF]のように、改行を入れてはいけないのでは?

Re:スタックの実現

Posted: 2009年11月11日(水) 16:18
by 初心者A
>スタックのメモリ確保がされてないのでは?
st *s を宣言するだけでは駄目ということでしょうか?

>abc[EOF]のように、改行を入れてはいけないのでは?
一文字ずつ積むイメージでそういう入力をしているのですが、これもマズいのでしょうか。
1文字入れる→pushで配列の番号が進むをwhileで繰り返しているつもりです。

>たかぎさん
具体的な解答ありがとうございます。
しかし、関数をその形に書き換えて再度実行を試みましたが、結果は変わりませんでした。

Re:スタックの実現

Posted: 2009年11月11日(水) 18:34
by non
>st *s を宣言するだけでは駄目ということでしょうか?
ポインタはアドレスを格納する変数であり、これだけでは実際にスタック(構造体st)の
メモリが確保されたわけではないので、暴走する危険があります。

st stk;
st *s;
s=&stk;
で試してください。
ただ、この問題ではポインタにする必要はないのですが。
私なら
st s;
にしておいて、
pop(&s);
のようにするかも。


>一文字ずつ積むイメージでそういう入力をしているのですが、これもマズいのでしょうか。
>1文字入れる→pushで配列の番号が進むをwhileで繰り返しているつもりです。
改行だって文字です。改行もスタックに積んでしまいます。

たかぎさんのプログラムは間違ってません。
試しに、abc[EOF]と改行を入れずに入力してみてください。

改行も入れたいなら、改行はスタックに積まないようにプログラムします。

Re:スタックの実現

Posted: 2009年11月12日(木) 15:08
by 初心者A
解決しました。
>改行だって文字です。改行もスタックに積んでしまいます。
これが原因でした。今までの出力結果も理解出来ました。
解答ありがとうございました。