Algoritmusok 3


  1. Eljárás: PUSH(STACK, TOP, MAXSTK, ITEM). Az eljárás ráhelyezi a veremre az ITEM adatelemet.
    1. [A verem már tele van?]
      If TOP=MAXSTK, then PRINT: TÚLCSORDULÁS,
      Return.
    2. TOP:=TOP+1.
      [A TOP értékének megnövelése 1-gyel.]
    3. STACK[TOP]:=ITEM. [Az ITEM ráhelyezése a veremre.]
    4. Return.


  2. Eljárás: POP(STACK, TOP, ITEM). Az eljárás leemeli a STACK verem legfelső elemét, és hozzárendeli azt az ITEM változóhoz.
    1. [Nem üres a verem?]
      If TOP=0, then Print: ALULCSORDULÁS.
      Return.
    2. ITEM:=STACK[TOP].
      [A verem legfelső elemének hozzárendelése az ITEM változóhoz.]
    3. TOP:=TOP-1.
      [A TOP értékének csökkentése 1-gyel.]
    4. Return.


  3. Eljárás: QUICK(A, N, BEG, END, LOC). Az A tömb N elemű. A BEG és az END az A tömb részlistájának határoló értékeit tartalmazza, Az eljárásban a LOC követi nyomon a részlista első elemének - A[BEG] - pozícióját. A LEFT és a RIGHT lokális változó tartalmazza majd a még felderítetlen elemek listájának határoló értékeit.
    1. [Inicializálás.] LEFT:=BEG, RIGHT:=END, LOC:=BEG.
    2. [Felderítés jobbról balra.]
      1. Repeat while A[LOC]<=A[RIGHT] and LOC . RIGHT:
        RIGHT:=RIGHT-1.
        [A ciklus vége.]
      2. If LOC=RIGHT, then: Return.
      3. If A[LOC]>A[RIGHT], then:
        1. [Az A[LOC] és az A[RIGHT] felcserélése.]
          TEMP:=A[LOC], A[LOC]:=A[RIGHT],
          A[RIGHT]:=TEMP.
        2. LOC:=RIGHT.
        3. Goto 3. lépés.
          [Az If szerkezet vége.]
    1. [Felderítés balról jobbra.]
      1. Repeat while A[LEFT]<=A[LOC] and LEFT . LOC:
        LEFT:=LEFT+1.
        [A ciklus vége.]
      2. If LOC=LEFT, then Return.
      3. If A[LEFT]>A[LOC], then:
        1. [Az A[LEFT] és az A[LOC] felcserélése.]
          TEMP:=A[LOC], A[LOC]:=A[LEFT],
          A[LEFT]:=TEMP.
        2. LOC:=LEFT.
        3. Goto 2. lépés.
          [Az If szerkezet vége.]


  4. Algoritmus: gyorsrendezés. Az N elemet tartalmazó A tömb rendezése.
    1. [Inicializálás.] TOP:=NULL.
    2. [Az A határoló értékeinek vermekre helyezése, ha az A két vagy több elemet
      tartalmaz.]
      If N>1, then: TOP:=TOP+1, LOWER[1]:=1, UPPER[1]:=N.
    3. Repeat 4-7. lépés while TOP . NULL.
    4. [A részlista leemelése a vermekről.]
      BEG:=LOWER[TOP], END:=UPPER[TOP],
      TOP:=TOP-1.
    5. Call QUICK(A, N, BEG, END, LOC). [III: Eljárás.]
    6. [A bal oldali részlista vermekre helyezése, ha a lista két vagy több elemet
      tartalmaz.]
      If BEGTOP:=TOP+1, LOWER[TOP]:=BEG,
      UPPER[TOP]:=LOC-1.
      [Az If szerkezet vége.]
    7. [A jobb oldali részlista vermekre helyezése, ha a lista két vagy több elemet
      tartalmaz.]
      IF LOC+1TOP:=TOP+1, LOWER[TOP]:=LOC+1,
      UPPER[TOP]:=END.
      [Az IF szerkezet vége.]
      [A 3. lépésben elkezdődött ciklus vége.]
    8. Exit.


  5. Eljárás: TOWER(N, BEG, AUX, END). A Hanoi tornyai feladat rekurzív megoldása
    N darab korong esetére.
    1. If N=1, then:
      1. Write: BEG › END.
      2. Return.
        [Az If szerkezet vége.]
    2. [N-1 darab korong áthelyezése a BEG rúdról az AUX rúdra.]
      Call TOWER (N-1, BEG, END, AUX).
    3. Write: BEG › END.
    4. [N-1 darab korong áthelyezése a AUX rúdról az END rúdra.]
      Call TOWER (N-1, BEG, END, AUX).
    5. Return


  6. Eljárás: TOWER(N, BEG, AUX, END). Az eljárás - a rekurzív megoldás átdolgozásával - megadja a Hanoi tornyai feladat megoldását N darab korong esetére. Az STN, az STBEG, az STAUX, az STEND és az STADD verem az N, a BEG, az AUX, az END és az ADD változóra vonatkozik.
    1. TOP:=NULL.
    2. If N=1, then:
      1. Write: BEG › END.
      2. Go to 5. lépés.
        [Az If szerkezet vége.]
    3. [A "Call TOWER(N-1, BEG, END, AUX)" hívás átalakítása.]
      1. [Az aktuális értékek és az új visszatérési cím ráhelyezése a vermekre.]
        1. TOP:=TOP+1
        2. STN[TOP]:=N, STBEG[TOP]:=BEG,
          STAUX[TOP]:=AUX, STEND[TOP]:=END,
          STADD[TOP]:=3.
      2. [A paraméterek értékének beállítása.]
        N:=N-1, BEG:=BEG, AUX:=END, END:=AUX.
      3. Go to 1. lépés.
    4. Write: BEG › END.
    5. [A "Call TOWER(N-1, AUX, BEG, END)" hívás átalakítása.]
      1. [Az aktuális értékek és az új visszatérési cím ráhelyezése a vermekre.]
        1. TOP:=TOP+1
        2. STN[TOP]:=N, STBEG[TOP]:=BEG,
          STAUX[TOP]:=AUX, STEND[TOP]:=END,
          STADD[TOP]:=5.
      2. [A paraméterek értékének beállítása.]
        N:=N-1, BEG:=AUX, AUX:=BEG, END:=END.
      3. Go to 1. lépés.
    6. [A "Return" végrehajtása.]
      1. If TOP=NULL, then: Return.
      2. [A legfelső értékek leemelése a vermekről.]
        1. N:=STN[TOP], BEG:=STBEG[TOP],
          AUX:=STAUX[TOP], END:=STEND[TOP],
          ADD[TOP]:=STADD[TOP].
        2. TOP:=TOP-1.
      3. Go to ADD. Lépés


  7. Eljárás: QUINSERT(QUEUE, N, FRONT, REAR, ITEM). Az ITEM adattétel beszúrása a sorba.
    1. [A sor már tele van?]
      If FRONT=1 and REAR=N, or if FRONT=REAR+1, then:
      Write: TÚLCSORDULÁS.
      Return.
    2. [A REAR új értékének megkeresése.]
      If FRONT=NULL, then: [A sor a kiinduláskor már üres.]
      FRONT:=1, REAR:=1.
      Else if REAR=N, then:
      REAR:=1.
      Else:
      REAR:=REAR+1.
      [Az If szerkezet vége.]
    3. QUEUE[REAR]:=ITEM. [Az új elem beszúrása.]
    4. Return.


  8. Eljárás: QDELETE(QUEUE, N, FRONT, REAR, ITEM). Az eljárás törli a sorból az ITEM adattételt, és hozzárendeli azt az ITEM változóhoz.
    1. [A sor már üres?]
      If FRONT=NULL, then: Write: ALULCSORDULÁS.
      Return.
    2. ITEM:=QUEUE(FRONT).
    3. [A FRONT új értékének megkeresése.]
      If FRONT=REAR, then: [A sorban csupán egyetlen elem szerepel.]
      FRONT:=NULL, REAR:=NULL.
      Else if FRONT=N, then:
      FRONT:=1.
      Else:
      FRONT:=FRONT+1.
      [Az If szerkezet vége.]
    4. Return.


    Egy szintet vissza, vagy vissza a főmenübe.