logi sisse meist KKK

Alates 1.01.2018 pinu.ee lõpetab oma töö. Tänud kõigile osalejatele ja kohtume jälle!

Ma saan aru, et selle põhimõtteks on pinudes ühtivate elementide pealt kokku hoida. Lisades ühe pinu vaatad samal tasandil olevate tippude väärtuseid ja lisad niimoodi uued servad DAG-i. Välja tõmbamiseks on pinud

märgitud.

Põhimõtteliselt tõmbad välja teed pinu operatsiooni ära ja paned tagasi.

Küsimus on, et kas sellel andmestruktuuril on veel mingisuguseid omadusi, mida lisada? Ja kas ma sain õigesti aru tööpõhimõttest.

Wiki link

küsitud Feb 04 '10 at 13:41

blinx's gravatar image

blinx
313

edited Mar 10 '10 at 15:46

Rene%20Saarsoo's gravatar image

Rene Saarsoo ♦♦
1.1k101121


Päris täpselt ei saanud küll küsimusest aru.

Miks ta on kasulik mitte-deterministlikul parsimisel on kiiruse ja mälu võit:

Näiteks algne pinu:
a --- b --- c --- d --- e

ning reeglid
f <-- d e
g <-- d e
h <-- c d e

kui kasutame gss-i, siis pärast 3 redutseerimist:
                 /--- f
                /
a ----- b ---- c ---- g
         \
          \---------- h

kui ei kasutaks, siis peaks pinust koopiaid tegema:
a --- b --- c --- f
a --- b --- c --- g
a --- b --- h

O(1) vs O(n*k) <--- ühe reegli rakendamine
kus n - ühe pinu elementide arv, k pinude arv

Ja siin üks artikkel, mis räägib nendest lähemalt.

link

vastatud Feb 05 '10 at 12:07

egon's gravatar image

egon ♦♦
771239

edited Feb 05 '10 at 12:15

Jah nüüd saan aru, et ühendatud pinud on realiseeritud sõlmpunkidega mis omavad viitasid

madalamal asuvatele sõlmedele. Pop-i ei tehtagi päriselt, pinu top osuti lihtsalt viiakse ühe

võrra madalamale. Pop-i järel saadakse uus hulk Top-e. Bottom-eid on 1. Vaatasin Elkhound

parseri generaatori koodi.

link

vastatud Feb 05 '10 at 14:30

blinx's gravatar image

blinx
313

Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×5
×2

küsitud: Feb 04 '10 at 13:41

nähtud: 1,952 korda

viimati uuendatud: Mar 10 '10 at 15:46

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee