1

次の擬似コードをスタックではなく配列に変換するにはどうすればよいですか。このアルゴリズムは、特定の入力が与えられた場合に有向グラフを作成することを目的としています。

  1. 2つの連続するノードシンボルが上に表示されるまで、スタック上の呼び出しシンボルを右から左にスキャンします。
  2. これらの2つのノードシンボルと、スタック上のそれらのすぐ下にある「*」をポップオフします。最初のシンボルから2番目のシンボルにエッジを描画します。
  3. スタックの最初のシンボルをプッシュします。
  4. 数式が処理されるまで、手順1〜3を続けます。

入力と出力の例を次に示します。

入力：

***ABCD

出力：

*AB, *AC, *AD

「*」はエッジを表します

すべての入力はスキャナーを使用して行われます。

4

2 に答える 2

2

限られたサイズのスタックは、「スタックインデックス」の配列とインデックスを使用してモデル化できます。

でスタックインデックスを開始します-1。プッシュ操作では、スタックインデックスをインクリメントし、配列の対応するインデックスに値を格納します。ポップ操作では、スタックインデックスの値を使用し、値をフェッチした後にインデックスをデクリメントします。スタックの最上位にアクセスするには、スタックインデックスの項目を読み取ります。

于 2012-11-08T16:27:37.300 に答える
1

基本的に、FIFOプロパティを使用してアレイに対して操作を実行する必要があります。

public ArrayStack( )
{
    theArray = new String[InitialSize];
    topOfStack = -1;
}

配列に要素を追加する（push）たびに、その要素を配列の位置にtopOfStack++;挿入します。"topOfStack"そうtopOfStack++することで、スタックの新しいトップになったアレイの位置を追跡します。

実行するときはpop、配列が空でないかどうかを確認し、要素をオンにして実行する必要がarray[topOfStack]ありますtopOfStack--;。これは、一番上が配列の前の位置になっているためです。

スタックがいっぱいであるために配列にさらに多くのスペースが必要な場合は、(topOfStack == InitialSize)次のように、より多くのスペースを持つ別の配列を作成する必要があります。

private void doubleArray( )
{
        String [] newArray = new String[ theArray.length * 2 ];
        for( int i = 0; i < theArray.length; i++ )
            newArray[ i ] = theArray[ i ];
        theArray = newArray;
 }

言うまでもなく、これは大まかにあなたが探す必要があるものです、当然、調べるべきより多くの詳細があります。それでも、自分で試してみてください。疑問がある場合は、このようなリソースを探してください。

于 2012-11-08T16:34:52.527 に答える