1

課題で困っています。いっぱいになるとサイズが 2 倍になり、1/4 いっぱいになると半分になる、動的に成長するスタックを実装することになっています。私は完全な C の初心者であり、ポインターに慣れていないため、いくつかの例を調べました。これが私が思いついたコードです。

実際には警告なしで gcc でコンパイルされますが、実行しようとすると「セグメンテーション違反」が発生します。これはおそらく壊れたポインターに関係していることがわかりましたが、間違いは見られないので、誰かが私に指摘してくれるとうれしいです.

乾杯

# ifndef STACK_H
# define STACK_H
# include "stdlib.h"

typedef struct stack {
  int *stack;
  int used;
  int size;
} stack;

stack* stck_construct() {
    stack *stck;
    stck->stack = (int *)malloc(10 * sizeof(int));
    stck->used = 0;
    stck->size = 10;
    return stck;
}

void   stck_destruct(stack *stck) {
    stck->stack = 0;
    stck->used = stck->size = 0;
    free(stck);
}

int    stck_push(stack *stck, int val) {
  if (stck->used == stck->size) {
    stck->size *= 2;
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }
  stck->stack[stck->used] = val;
  stck->used++;
  return 1;
}

int    stck_pop(stack *stck, int *val) {
  *val = stck->stack[stck->used];
  free(stck->stack);
  stck->used--;
  if (stck->used <= (stck->size)/4) {
    if (stck->size <=40) stck->size = 10;
    else stck->size /= 2;
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }

  return 1;
}

int main(){

    stack* test;

    test=stck_construct();

    int i; int out;
    for (i =1; i<=10; i++)
        stck_push(test, i);

    for (i =1; i<=10; i++)  {
        stck_pop(test,&out);
        printf("%i\n", out);
    }
    stck_destruct(test);
    return 0;
}

# endif
4

2 に答える 2

5

最初に作成せずに使用stack* stck_construct()している場合。そのままでは、どこも参照していないポインターにすぎません。これにより、確実にセグメンテーション違反が発生します。あなたは aを実際のstck->stckstack*stackmalloc

注意: 他にもいくつかのバグがあり、それらについては触れていません。興味があれば、David と Alexey のコメントを参照してください。

于 2013-01-22T15:29:19.303 に答える
2

注釈付きのバグ:

stack* stck_construct() {
    // stck is a pointer, you never initialize it to point to an existing object:
    stack *stck;
    // you dereference the invalid pointer with stck->stack:
    stck->stack = (int *)malloc(10 * sizeof(int));
    stck->used = 0;
    stck->size = 10;
    return stck;
}

void   stck_destruct(stack *stck) {
    stck->stack = 0;
    stck->used = stck->size = 0;
    // I thought you were assigning the pointer to the allocated memory to stck->stack,
    // and by now that pointer is 0 as you just did stck->stack = 0;
    free(stck);
}

  if (stck->used == stck->size) {
    stck->size *= 2;
    // if realloc() fails you end up with twice as big stck->size and
    // with stck->stack = NULL
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }

  // You first store the new element and then advance the index
  stck->stack[stck->used] = val;
  stck->used++;

  // But when you remove it you don't do the two operations in the reverse order:
  *val = stck->stack[stck->used];
  // and for some reason you additionally destroy all data
  free(stck->stack);
  stck->used--;

    // and then you realloc() using the invalid pointer (you just free()'d it!)
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
于 2013-01-22T15:41:03.733 に答える