Nada

LÖSNING TILL DATALOGIÖVNING 11

Uppgift 1: Kö, stack. prioritetskö (Weiss: Ex 6.1)

KÖ:4816, STACK:6184, PRIORITETSKÖ: 1486 (om lägst tal har högst prioritet). Att datastrukturerna är abstrakta betyder att vi bara kan manipulera dom med vissa givna anrop, av typen q.put(x) och x=q.get() i dessa fall.

Uppgift 2: Heap (trappa)

Trappan är en vektor med index från 0 till maxantalelement. Den tolkas som ett binärträd med index 1 överst, index 2 och 3 på nivån under, index 4,5,6,7 på nivån därunder etc. Barnen till index i har indexen 2i och 2i+1. Trappvillkoret är att ett större tal aldrig får ligga på ett mindre. Så här ser trappan ut steg för steg. (Index 0 skrivs inte ut.) 4 48 Trappvillkoret är uppfyllt. 481 -> 184 Den nyinsatta ettan trappas upp. 1846 -> 1648 Den nyinsatta sexan trappas upp. *648 -> 864 Sista elementet upp i topp, -> 468 trappas ner genom att bytas med minsta barnet. *68 -> 86 Sista elementet upp i topp, -> 68 trappas ner genom att bytas med minsta barnet. *8 -> 8 Sista elementet upp i topp.

Uppgift 3: Störst i trappan

Största talet kan inte ha något under sej och finns därför antingen på den understa nivån eller på den högraste delen av den näst understa nivån (om inte understa nivån är helt utfylld).

Uppgift 4: Programdatabas

Binärsökning är obegripligt i detta fall. En ordnad länkad lista där nya tablåer sorteras in då och då fungerar men linjärsökning för att sortera in på rätt ställe är litet långsamt. Binärträd blir snart helt obalanserat eftersom alla nytillkommande program hamnar till höger. Hashtabell används inte vid sortering, inte heller stack. Men en heap (trappa) är perfekt! Man ser till att tidigaste starttiden hamnar överst i trappan. Man tar ut program från trappan till skärmen och när man vill kan man lägga in nya program i trappan utan att något störs.

Uppgift 5: Från fan till gud på olika sätt.

Om man ritar upp ett släktträd med FAN överst, fans söner därunder etc, ser man att det gäller att hitta den översta förekomsten av ordet GUD. Med en kö kommer man att söka nivå för nivå. Med en stack går man på djupet via en son innan man behandlar övriga söner. Med stacken måste man ta bort dumsöner, annars är trädet oändligt djupt: FAN-FIN-FAN-FIN... Om man bryter så snart man funnit GUD är man inte säker på att det är den kortaste lösningen. En prioritetskö är troligen smartare än en vanlig kö. Man ska försöka prioritera som söner som verkar mest lovande, och det enklaste är att prioritera dom som överensstämmer med GUD i vissa positioner. Till exempel FAN=3 (tre fel) DUM=2 (två fel, alltså mer prioriterat)