1

tacop 2.2.2 シーケンシャル アロケーションの作業中に、247 ページのメモリ セクションを再パックしているときに、いくつかの問題に遭遇しました。

主題は、共通領域の場所 L0 < L < LX を共有する n 個のスタックがあることです。最初に、1 <= j <= n に対して BASE[j] = TOP[j] = L0 を設定します。

目標は、スタック i に関して要素を挿入または削除しているときにオーバーフローが発生した場合、メモリを再パックする方法です。(まだいっぱいになっていないテーブルから一部を取り除いて、スタック i のためのスペースを作ります)。

a)。i < k < n かつ TOP[k] < BASE[k+1] となる最小の k を見つけます (そのような k が存在する場合)。1 ノッチ上に移動、設定 CONTENTS(L+1) -> CONTENTS(L)、 for TOP[k] >= L > BASE[i+1] 最後に、設定 BASE[j] -> BASE[j] + 1 、TOP[j] -> TOP[j] + 1、i < j < k の場合

ここに私の質問があります：

まだ埋まっていないスタックをどのように見つけるのでしょうか? スタックk? そして、なぜ最小のkを選んだのですか?

4

1 に答える 1

2

まだ満たされていないスタックを見つけるために使用される基本的な考え方は、次の事実です。

スタックkがいっぱいではありません <==>TOP[k] < BASE[k+1]

アルゴリズムの最初のステップのループは、この条件を満たす最初のものを見つけるために to から実行kされます。i+1nk

また、最初はすべてのスペースがとのn設定によって最後の th スタックに与えられることに注意してください。したがって、すべての「より高い」スタックが満たされていない限り、そのような.BASE[n] = TOP[n] = L0BASE[n+1]=LInftyk

あなたの 2 番目の質問 (なぜ最小のものを選ぶのですか?) は、より簡単kに答えられます。アルゴリズムのテキストのすぐ上の段落でクヌースが言及しているように：

再梱包を行う方法はいくつかあります。... 最も単純な方法を示すことから始め、次にいくつかの代替方法を検討します。

その後、Knuth は、以前の再パックを考慮に入れた再パックのアプローチについて説明し、プロセスをある程度適応させます。

于 2009-07-21T11:20:56.647 に答える