0

これが、リンクリストを使用したスタックの実装です

STACK using linked list 

STACK-EMPTY:
if L.head == NIL
    return True
else return False

PUSH(x):
x.next = L.head 
if L.head != NIL
    L.head.prev = x
L.head = x
x.prev = NIL

POP():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

これを検証しますか？改善方法 ？

ありがとう

4

2 に答える 2

1

データ構造の一貫性を向上させることができます:

  1. リストヘッドのprevは常にNIL
  2. リストにない要素がNILnextに設定されていますprev

1. POP に矛盾があり、エラーの原因となる可能性があります。要素をポップするprevと、ヘッドはヘッド自体になり、要素をプッシュするprevと、ヘッドは NIL になります。

于 2013-03-27T13:26:18.377 に答える
0

これを試して...

定義:

  • S.topXスタックの一番上にあるタイプのノードへのポインタです
  • Xは 2 つのポインターを持つノードでtopあり、base
  • X.topスタックの一番上にある次のノードを指します。
  • X.baseスタックのベース (下) に向かって次のノードを指します

まず、スタック トップ ポインターを初期化します。

STACK-INITIAL:
S.top = NIL
return true  // Never fails

空のスタックをテストします。

STACK-EMPTY:
return (S.top == NIL)

xノードをスタックにプッシュします。

PUSH(x):
x.top = NIL     // Top of stack, therfore top is NIL
x.base = S.top  // base is previous top
S.top = x       // x is now top of stack  
return true

スタックの先頭をポップして返します (これは唯一の「興味深い」部分です)。

POP():
x = S.top          // Top node on stack (could be NIL)
if S.top != NIL    // Check in case stack was empty
  S.top = x.base   // New top = next node toward base
  x.base = NIL     // Disconnect x from stack
  if S.top != NIL  // Is stack now empty?
    S.top.top = NIL // No, set top node's top pointer to NIL
return x            // x could be NIL if stack was empty

考えるべきこと...あなたが使用していたもののように見えたので、上記の二重リンクリストを使用しました。ただし、リンクがスタックのベースを指す単一のリンク リストのみが必要です。x.top上記のアルゴリズムのポインターはほとんど役に立たないことに注意してください(設定されていますが、参照されていません)。スタックトップ (S.top) を追跡している限り、必要なことは POP 操作中にスタックをトレースバックすることだけです。

コメントへの対応

要素がスタックからポップされると、関連するすべてのポインターが NIL に設定されます。これは、もはやスタックの一部ではないため、スタック要素を指すべきではありません。元の回答にそのビットを追加しました（上記を参照）。

同様に、スタック要素の新しいトップ (スタックが空にならない限り) は、その上の要素へのポインタを NIL に設定する必要があります (その上の要素が削除されたため)。私の例では、それS.top.top = NIL がすべてでした（S.topは一番上のスタック要素を指しているのでS.top.top、その要素の一番上のポインタです）。がPOPした要素であり、NIL自体ではないとx.next.prev = NIL仮定すると、 で同じことを行うと思います。あなたの疑似コードでは、スタック要素の先頭の prev ポインタがそれ自体を指しているままになるxように見えます(その直前のスタックの新しい先頭)。x.next.prev = L.headL.headx.next

最後に、二重連結リストを使用してスタックを実装する理由を疑問に思います。その下の次の要素へのポインタを持つ単一の連結リストのみが必要です

于 2013-03-27T14:40:28.603 に答える