Tietorakenteet ja algoritmit 13.11.2003 Harjoitus 9 Näissä tehtävissä tehdään sama pakan toteutus kahdella tavalla. Koska pakan operaatioiden otsikoiden pitäisi olla samanlaisia kaikissa toteutuksissa, on melko iso osa kirjoitettavasta koodista toistuvaa. Editorin kopiointi ja etsi-korvaa toiminnot kannattaa siis opiskella viimeistään nyt. Näissä tehtävissä ei käytetä tietorakennekirjastoa, vaan tavallista Pascalia tai C:tä. Rakennetaan kumpikin pakkatoteutus moduuliksi ja otetaan moduuli pääohjelmaan import/#include:lla (vastaavan tra:n sijaan). Mallia moduulirakenteeseen www-sivulla. Käytetään alkioina ELEMENT-tyyppiä, jonka toteutus löytyy www-sivulta tiedostoista tra03.h9.element.?. Harjoitukset on tehtävä cs/cc:llä käännettäväksi (josta ne myös edelleen esitetään), käännös esimerkiksi: gpc --automake ohjelma.p tai gcc ohjelma.c tra03.h9_50-51.c tra03.h9.element.c. 49) Kirjoita pääohjelma joka testaa pakan toimintaa kaikissa tilanteissa. Siis pakkaan viemistä/poistamista kummastakin päästä, pakan kiertämistä ympäri (vuorotellen lisäys, poisto, pitkään jatkaen), pakan tyhjenemistä, jne. Kiinnitä erityistä huomiota erilaisten erikoistapausten toimintaan ja dokumentoi piirtäen kaikki erikoistapaukset. Jollet pysty testaamaan tämän toimintaa seuraavilla pakkatoteutuksilla, testaa TRA-kirjaston pakkatyypillä. 50) Toteuta abstrakti tietotyyppi pakka taulukkoa käyttäen. Pakka on siis tietue (tai osoitin tietueeseen) joka sisältää alkioiden talletukseen käytetyn taulukon ja tietoa käytössäolevien alkioiden sijainneista (pakka voi ryömiä molempiin suuntiin taulukossa ja kiertää ympäri). Määrittele siis toteutuksen tietorakenne ja toteuta operaatiot CREATE, EMPTY, FRONT ja REAR. Muista määritellä vakiot/lueteltu tyyppi bottom ja top. Mitkä ovat operaatioiden aikavaativuudet? 51) Jatka edellistä tehtävää toteuttamalla operaatiot ENQUEUE, DEQUEUE ja PRINT. Mitkä ovat operaatioiden aikavaativuudet? Testaa pakkaasi tehtävän 49 pääohjelmalla. Testaa myös pakan täyttyminen. 52) Toteuta abstrakti tietotyyppi pakka dynaamisesti kaksisuuntaisella linkitetyllä rakenteella (listalla) erillisen tunnisterakenteen kanssa. Pakka on siis rakenne, joka sisältää osoittimet alkuun ja loppuun. Solmut sisältävät osoittimen edeltäjään ja seuraajaan. Määrittele siis toteutuksen tietorakenne ja toteuta operaatiot CREATE, EMPTY, FRONT ja REAR. Muista määritellä vakiot/lueteltu tyyppi bottom ja top. Mitkä ovat operaatioiden aikavaativuudet? 53) Jatka edellistä tehtävää toteuttamalla operaatiot ENQUEUE ja PRINT. Mitkä ovat operaatioiden aikavaativuudet? Testaa pakkaasi tehtävän 49 pääohjelmalla. 54) Jatka edellistä tehtävää toteuttamalla operaatio DEQUEUE. Mitkä ovat operaatioiden aikavaativuudet? Testaa pakkaasi tehtävän 49 pääohjelmalla. Sisällytä testiohjelmaasi myös pakkojen lomituslajittelu (www-sivulta).