C-ohjelmointi Kurssikokeen 12.5.2005 arvostelusta Tehtävä 2 (Liisa Marttinen) =========================== Esitetty hyvin erilaisia ratkaisutapoja: 1. Käydään annetun listan alkiot läpi järjestyksessä ja laitetaan kukin alkio omalle paikalleen uuteen listaan. Tämä on ehkä suoraviivaisin ja lyhyin ratkaisu: Annettu lista käydään kerran läpi while-silmukassa ("niin pitkään kuin listan alkioita riittää") ja kunkin alkion paikka uudessa listassa löytyy sekin while-silmukassa ("kunnes uuden listan alkiossa on pienempi arvo"). Ja sitten vain sijoitetaan alkio listaan ennen tätä pienempää arvoa. 2.Kopioidaan annettu lista uudeksi listaksi, joka sitten järjestetään laskevaan järjestykseen. Tässä kopiointi on yksinkertaista. Uuden listan järjestäminen on tuottanut joillekin ongelmia. Jotkut ovat käyttäneet apuna taulukkoa, johon annetun lista alkioiden arvot kopioidaan ja joka järjestetään nousevaan järjestykseen. Tämän jälkeen on helppo muodostaa taulukon alkioista laskevassa järjestyksessä oleva uusi lista: otetaan vain alkiot järjestyksessä ja lisätään listan alkuun. Taulukkoa käytettäessä taulukon koko voi olla rajoittava tekijä! Jotkut ovat vielä laskeneet listan alkioiden lukumäärän ennen taulukon varaamista. 3.Otetaan alkiot annetusta listasta suuruusjärjestyksessä (ja mieluummin pienin ensin) ja muodostetaan niistä uusi lista. Tässä ratkaisussa vaikeutena on se, ettei annettua listaa saa muuttaa. Jotenkin täytyy tietää, mitkä listan alkiot on jo käsitelty ja mitkä vielä käsitttelemättä. Tähän on kehitetty erilaisia ratkaisuja: * Otetaan joka läpikäyntikierroksella aina suurin (tai pienin) ja muistetaan, mikä on suurin (pienin) jo käytetty arvo. Tässä täytyy varautua myös siihen, että listassa on samoja arvoja. * Pidetään erillistä taulukkoa jo käsitellyistä solmuista. * Etsitään listan pienin ja suurin arvo ja käydään läpi kaikki arvot tästä välillä. Jos annetusta listasta löytyy ko. arvoja, niin ne viedään uuteen listaan. Tämä on turhan työläs ratkaisu! Vaikka listassa olisi vain kaksi solmua: MAXint ja MINint, niin läpikäyntejä on melkoinen määrä! Arvostelussa ei ole kovin vahvasti otettu huomioon käytetyn ratkaisun järkevyyttä ja ekonomisuutta. Hankalampi ratkaisu on yleensä muutenkin aiheuttanut ongelmia: enemmän koodin kirjoittamista ja virheitä toiminnassa. Kuitenkin täydet 14 p on saanut vain oikein ja järkevästi toimivasta ratkaisusta; ei hyvin kömpelöstä ja lukemattomia kertoja listaa läpikäyvästä ratkaisusta. Erillistä lista-rakennetta ei ole vaadittu; listan alkioiden rakenne oikein käytettynä on riittänyt. Jos sellaisen on tehnyt, niin 'huonossa ratkaisussa' siitä on saattanut saada lisäpisteen. Miinuspisteitä ratkaisuista --------------------------- Yleisesti: pienet virheet, lähinnä huolimattomuusvirheet -1 p struktin jäsenten käytössä väärä syntaksi ja määrittelyssä väärä tyyppi suurempi virhe, C-kielen pieni vääränkäytös tai pienehkö virhe toiminnassa -2p suurempi toimintavirhe tai C-kielen väärinkäyttö -3 -5 p Jos järjestämisosuus puuttuu kokonaan -5 p. uudelle listalle ja sen solmuille ei varata mitään tilaa mallocilla -4 p listan järjestäminen qsort-funktion kutsulla -4 p (paitsi, jos on todella oikein osannut käyttää tätä funktiota) ensimmäisen alkion käsittely ei toimi -3 p toimii väärin, jos samoja alkioita -3 p linkkien päivitykset eivät täysin toimi -2 joissakin tapauksissa ei järjesty oikein -2 turhan monimutkainen linkkien pyöritys, vaikka lopputulos olisikin oikea -1 Pluspisteitä, jos on sentään jotain osannut: ------------------------------------------ osannut tehdä struct-rakenteen, typedef:n ja osannut käyttää niitä 2-3 p ratkaisuissa on jotain ideaa ja yritystä 1-2 p