ヒープ領域とスタック領域の違いについて教えてください

投稿者: user4410 ヒープ領域とスタック領域の違いについて教えてください ひとまず以下の疑問があります。 いつ確保されるのか どちらが早いのか サイズはいつ決定されているのか スタックに確保されているAuto変数とはなにか ヒープ領域はなぜ、双方向リストによって構成されているのか スタック領域のデータ構造はどのようなものなのか 追記 なぜ、データ構造に違いを与えたのか 解決 スタックとヒープの違いを、使い方とデータ構造から説明します。 スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。 従って、スタックを実装するデータ構造としては、先入れ後出し(FILO)のデータ構造である「スタック(同じ名前なのでややこしいかもしれませんが)」がスタックを実装するのに利用されます。 これに対して、ヒープに確保されるメモリ領域は、確保と解放にこのような一定の順序がありません。先に確保したメモリ領域が先に解放されることもあります。そのため、メモリ領域を確保した順序に関係なく解放できる必要があります。 従って、ヒープを実装するデータ構造としては、途中の要素をいつでも削除できるデータ構造であるリストなどが利用されます。 回答者: Anonymous

プログラムの実行時間をできるだけ短くしたい

投稿者: Anonymous プログラムの実行時間をできるだけ短くしたいです。 最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです 入力の条件は、 The first line contains the integer N. The second line contains N integers, a0,a1,…,aN−1. The integers are separated by a single space character. The third line contains N integers, b0,b1,…,bN−1. The integers are separated by a single space character. となっています。 タイムリミットは1s,入力数は<1000000です。 現時点では、 scanf(“%d”, &N) //入力される要素数 for(i=0;i<N;i++) scanf(“%d”,&a[i]); for(i=0;i<N;i++){ scanf(“%d”,&b[i]); //aiの範囲を指定する数bi…(Continue Reading)

C言語でのスタックを実装する際、何故グローバル領域でスタックの先頭のポインタを宣言しなければいけないのでしょうか。

投稿者: Anonymous 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("ERRORn"); exit(-1); } // NULLポインタならエラー(-1)を返す if(stack_root == NULL){ return -1; } n = stack_root->data; next = stack_root->next; fr =…(Continue Reading)

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

投稿者: Anonymous 中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。 では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? 「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか? (乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね) 解決 中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? ご質問中にあるように、3 4 + 5 +でも構いませんし、3 4 5 + +でも構いません。 「3 4 5 +」のように書くことはできないのでしょうか? +がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、3 4 5 +だと、最後の4 5だけが加算されて、3 9と書いたのと同じ状態になってしまいます。 もし「スタック上から3つの数を取り出して全部を足し合わせる演算」、なんてものが定義できれば、3 4 5 add3なんて書き方もありになります。 逆ポーランド記法を基礎に置いた言語(と言うよりスタック操作を基礎、と言った方が良いかもしれませんが)Forthだとこんな感じ。(以降は行コメントです。) : add3 +…(Continue Reading)

メモリ管理、スタックのmutabilityについて

投稿者: Anonymous スタック領域に積んだ値は、関数がネストしてもFrame Pointerから遡って参照することができると理解しているのですが、 その場合、より深い場所にある値の上書きはできないのでしょうか? また、できないとすればそれはなぜなのでしょう。 セキュリティでしょうか? ただし、代入する値のサイズがもとの値以下であり、Growableでないことを前提とします。 無駄に手書きですが、こういうイメージです ーーーーーーー | | | 関数 | | | | ローカル変数 <-| ———– | | | | | 上書きしたい | ネストした — | 関数 | | | ーーーーーーー 解決 質問するに至った動機と合致する答えになるのかどうか微妙な気がしますが void func1(int* p) { ++p[4]; } void func2(void) { int array[10]={0}; func1(array); } 上記コードはたいていの CPU (x86 も含む)…(Continue Reading)