6

C言語でスタックを実装をしようと思い、いくつかのwebページを参考にして、以下のように実装しました(このコードは正常に動作します)。

#include <stdio.h>
#include <stdlib.h>

typedef struct{
  int data;
  struct stack *next;
} stack;

stack *stack_root = NULL;


// stackの先頭の要素をとり出す
int pop(void){
  int n;
  stack *next, *fr;

  next = calloc(1, sizeof(stack));
  if(next == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  // NULLポインタならエラー(-1)を返す
  if(stack_root == NULL){
    return -1;
  }

  n = stack_root->data;
  next = stack_root->next;
  fr = stack_root;
  stack_root = next;
  free(fr);

  return n;
}


// stackの先頭に要素を追加
void push(int n){
  stack *new_stack;

  new_stack = calloc(1, sizeof(stack));
  if(new_stack == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  new_stack->data = n;
  new_stack->next = stack_root;
  stack_root = new_stack;
}


int main(){
  int i;

  push(3);
  push(2);

  i = pop();
  printf("%d \n", i);

  i = pop();
  printf("%d \n", i);

  i = pop();
  printf("%d \n", i);

  push(2);
  
  i = pop();
  printf("%d \n", i);
}

/*実行結果
2 
3 
-1 
2
*/ 

しかしながらこのコードだと、スタックを複数使用する場合、その個数分stack_root(スタックの先頭)をグローバル領域で定義しなければいけません。
そこで、stack_rootの宣言をメイン関数内に移動し、以下のようなコードを書きました(このコードは正常に動作しません)。

#include <stdio.h>
#include <stdlib.h>

typedef struct{
  int data;
  struct stack *next;
} stack;


// stackの先頭の要素をとり出す
int pop(stack *stack_root){
  int n;
  stack *next, *fr;

  next = calloc(1, sizeof(stack));
  if(next == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  // NULLポインタならエラー(-1)を返す
  if(stack_root == NULL){
    return -1;
  }

  n = stack_root->data;
  next = stack_root->next;
  fr = stack_root;
  stack_root = next;
  free(fr);

  return n;
}


// stackの先頭に要素を追加
void push(stack *stack_root, int n){
  stack *new_stack;

  new_stack = calloc(1, sizeof(stack));
  if(new_stack == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  new_stack->data = n;
  new_stack->next = stack_root;
  stack_root = new_stack;
}


int main(){
  int i;
  stack *stack_root = NULL;

  push(stack_root, 3);
  push(stack_root, 2);

  i = pop(stack_root);
  printf("%d \n", i);

  i = pop(stack_root);
  printf("%d \n", i);

  i = pop(stack_root);
  printf("%d \n", i);

  push(stack_root, 2);
  
  i = pop(stack_root);
  printf("%d \n", i);
}

/*実行結果

-1 
-1 
-1 
-1 

*/

pop関数やpush関数で関数の先頭のポインタを渡せば良いと思ったのですが、何故このコードは正常に動作しないのでしょうか。教えてください。


追記

774RRさん、ありがとうございます。
ポインタ変数の場合も、通常の変数と同様、関数に参照渡ししたい場合はその変数のポインタを渡さなければならない

#include <stdio.h>

// 通常の変数を参照渡し
void addone(int *n){
  (*n)++;
}

int main(void){
  int i=1;

  addone(&i);

  printf("%d\n", i);
  return 0;
}

// 実行結果
// 2

,

// ポインタ変数を参照渡し
void addone(int **n){
  (**n)++;
}

int main(void){
  int *i;

  *i = 1;
  addone(&i);

  printf("%d\n", *i);
  return 0;
}

// 実行結果
// 2

ということですね。
したがって、

#include <stdio.h>
#include <stdlib.h>

typedef struct{
  int data;
  struct stack *next;
} stack;


// stackの先頭の要素をとり出す
int pop(stack **stack_root){
  int n;
  stack *next, *fr;

  next = calloc(1, sizeof(stack));
  if(next == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  // NULLポインタならエラー(-1)を返す
  if(*stack_root == NULL){
    return -1;
  }

  n = (*stack_root) -> data;
  next = (*stack_root) -> next;
  fr = *stack_root;
  *stack_root = next;
  free(fr);

  return n;
}


// stackの先頭に要素を追加
void push(stack **stack_root, int n){
  stack *new_stack;

  new_stack = calloc(1, sizeof(stack));
  if(new_stack == NULL){
    printf("ERROR\n");
    exit(-1);
  }

  new_stack->data = n;
  new_stack->next = *stack_root;
  *stack_root = new_stack;

}


int main(){
  int i;
  stack *stack_root = NULL;

  push(&stack_root, 3);
  push(&stack_root, 2);

  i = pop(&stack_root);
  printf("%d \n", i);

  i = pop(&stack_root);
  printf("%d \n", i);

  i = pop(&stack_root);
  printf("%d \n", i);

  push(&stack_root, 1);
  
  i = pop(&stack_root);
  printf("%d \n", i);
  
  return 0;
}

/*実行結果

2 
3 
-1 
1 

*/

というようにして、ポインタ変数のポインタをpop()やpush()に渡すことで解決しました。
ありがとうございました。

1 件の回答 1

10

で関数の引数は値渡し(複写渡し)であるため、です。
提示コード main 側は

push(stack_root, 3);

stack_root が変更されて帰ってくることを期待している構造になっています。
の文法規則上、この呼び出しでは stack_root は変更されないのです。

push で行っている

stack_root = new_stack;

mainstack_root とは異なる局所変数 stack_root を書き換えるだけです。
結果的に mainstack_root は変化しないままです。

大域変数だったら両者が同一なのでうまくいくわけです。

ではどうするか・・・なんですが、やりかたはいくつもあります。

策1 push pop には &stack_root を渡す。
push pop*stack_root を操作する。

ってとこでしょうか。他の方策も考えてみてください。

1
  • 2
    回答ありがとうございます。 つまり、通常の変数を関数に参照渡しする場合に、その変数のアドレスを渡さなければならないのと同様、ポインタ変数の場合も、参照渡ししたい場合は「そのポインタ変数のポインタ」を渡さなければならないということですね。
    – myuuuuun
    Commented 2015年7月30日 9:03

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。