Labori materjal

• Slaidid: SQL
• Näidisandmebaas (slaididel olevad päringud): cars.db
• Andmebaasiga liidestamise näited: [sql1.c]   [sql2.c]  [sql3.c]

Laboriülesanded

Selle labori käigus liidestame me enda C-keelse programmi SQLite3 andmebaasiga kasutades libsqlite3-dev  teeki. Esimese ülesande käigus alustad andmete lisamisest olemasolevasse andmebaasi, millele järgneb andmete pärimine teise ülesande raames.

Laboril on kaks edasijõudnute ülesannet, millest esimeses muudame andmete lisamist paremaks. Teises ülesandes tuleb uuendad juba andmebaasis olevaid andmeid.

Lae alla tunnitööks kasutatav andmebaas: study_information.db

Andmemudel

Ülesanne 1: Lisa iseennast andmebaasi

NB! Ülesanne võib osutuda mitte tehtavaks kui andmebaasi fail asetseb P kettal tänu Windows SMBle. Andmebaas jääb lukustatuks ning muudatuste lisamine ei tööta! Lahenduseks on töö ajaks andmebaasifail hoiustada  väljaspool P ketast, nt töölaual ning hiljem sinna kopeerida.

Selle ülesande raames harjutad INSERT päringuid andmete lisamiseks. Baasülesanne ei ole vajalik realiseerida C koodis. Kirjuta oma päringud ja jooksuta neid kasutades “Execute SQL” funktsiooni SQLite browser rakenduses.

Nõuded

• Kirjuta üleskõik SQL päringud mida sa jooksutad (nt tavalise tekstidokumendina)! Näita jooksutatud päringuid ning näita oma andmebaasi pärast päringute tegemist. Kokku peab olema 5 päringut!
• Tabeli primaarvõtmeks olevaid ID väärtusi (students.id , subjects.id , declarations.id ) ei tohi lisamispäringutesse sisse kirjutada! Need teeb andmebaas ise (id atribuut on andmebaasi disainis omadusega auto increment ning kõigi kolme tabeli id atribuudid omavad vastavat generaatorit)
• Teosta järgmised andmete lisamise päringud
  • Lisa andmebaasi enda kui tudengi andmed
  • Lisa andmebaasi õppeaine, mille oled sooritanud
  • Lisa endale 3 aine deklaratsiooni. Üks nendest peab olema ainele, mille just lõid, lisaks 2 tk olemasolevatele.
• Märkus: hinded ja isikukood ei pea olema reaalsed.

Kui andmed lisatud, näita enda tehtud päringud ning näita oma andmebaasi SQLite Browser rakenduse kaudu.

Ülesanne 2: Andmete pärimine

Selle ülesande raames tuleb sul kirjutada päringuid millega andmebaasis eksisteerivaid andmeid pärida. Kõik päringud peavad olema kirjutatud C-keelse programmi sisse. Sulle on antud 3 koodinäidet selle lehe alguses materjalide all. Vali milline neist on sulle kõige arusadavam ning kasuta seda mallina enda päringute kirjutamisel.

Ülesanne on jaotatud kolmeks eraldi hinnatavaks osaks.

Nõuded

• Kõik päringud vastavas ülesande osas peavad olema sooritatud. Iga osa hinnatakse eraldi.
• Andmed peavad olema täielikult ette valmistatud andmebaasihalduri poolel – st kõik arvutused (nt summa, keskmine, max jne) peavad olema kirjutatud SQL päringu sisse. Arvutusi C koodis ei tohi teha!
• Kõik olulised andmeväljad tuleb väljastada. Ära väljasta identifikaatori väärtusi (nt subjects.id, declarations.id)
• Päringuid võid jooksutada läbi menüü valikuliselt või ühes rakenduses üksteise järel. Sinu otsustada.
• Kõik ressursid peavad olema programmi lõpuks vabastatud – kontrolli lekete puudumist valgrindiga.

Ülesanne 2 hinnatav osa 1

Esimeses osas teeme lihtsaid SELECT päringuid

Päring 1: Leia kõik õppeained, mis on vähem kui 6 EAPd

Päring 2: Leia kõik õppeaineid, milles on eksam. Järjesta tulemused EAPde arvu alusel vähimast suurimani.

Ülesanne 2 hinnatav osa 2

Teises osas harjutame veidi keerukamaid SELECT päringuid, kus tuleb kasutada JOIN märksõna ühe- või kahekordselt, et liita mitme tabeli vahelisi andmeid kasutades nende PK-FK võtmepaare.

Päring 1: Leia õppuri ‘Marko’ kõik hinded

Päring 2: Leia kõik õppeaineid mis sa oled sooritanud. Näita neid koos hinnetega, alustades kõrgeimast hindest.

Ülesanne 2 hinnatav osa 3

Kolmandas osas harjutame andmete koondamist tunnuste alusel ja tulemuste arvutamist oma SELECT päringutes. Meil on vaja nii JOIN kui GROUP BY märksõnu ning mõningaid arvutamise funktsioone.

Päring: Leia iga tudengi poolt teenitud EAPde arv ning keskmine hinne.

Edasijõudnute ülesanne 1: Enda andmebaasi lisamine (usaldusväärsemalt)

Esimese baasülesande raames ei olnud sul otseselt piiranguid kuidas ennast andmebaasi lisama peaks. Võisid vaadata mis ID väärtused tulid ning neid siis jooksvalt kasutada. Reaalses elus kasutatava andmebaasi puhul päris nii mõistlik teha ei oleks.

Taustinfot

Paremaks lahenduseks pakun välja 2 võimalust. Kummagi puhul pole tegu ideaalse lahendusega, kuid saame sammu võrra paremuse poole.

Võimalus 1a: SQL toetab alampäringuid – me saame ühe päringu sisse peita teise päringu ja selle tulemust siis kasutada esimeses päringus. Näiteks me saame INSERT päringu sisse kirjutada SELECT päringu.

Oletame, et tahame oma näidisandmebaasi lisada isikule Marko Mets veel ühte autot. Selleks saaksime jooksutada järgmise päringu.

Antud näide pole veatu – näiteks kui meil oleks 2 isikut kelle nimi on Marko Mets, siis läheks see katki. Sellest parem versioon on 1b, mille võid esitada laboriülesandena.

Võimalus 1b: Sarnaselt eelmise võimalusega saad teha sarnase päringu eesti isikukoodi põhjal. Tegu ei ole garanteeritult eksisteeriva väärtuse ega ei pruugi ka unikaalsust garanteerida kui välisriigi isikukoodid sekka tuua aga on parem kui eelmine.

Võimalus 2: Parem viis sellele läheneda oleks teha mitu päringut. Esiteks lisaksime end tudengina andmebaasi. Seejärel päriksime andmebaasilt mis meie ID väärtuseks sai kasutades  SELECT last_insert_rowid();  päringut. See annab meile tagasi automaatselt genereeritud ID väärtuse. Seejärel saaksime juba kasutada seda ID väärtust järgnevate andmete lisamiseks

Ka see pole veatu ega ideaalne. Näiteks kui meie kahe päringu vahel lisatakse mõne teise klientrakenduse poolt uus õppur, siis saaksime tagasi vale koodi (race condition). Seda lahendatakse tegelikus maailmas mehhanismiga TRANSACTION, mis paneb baasi lukku päringute ajaks teistele – ehk siis kõik või mitte midagi meetod. Küll aga kuna meil on kohalik failipõhine andmebaas, siis me saame sellest täna mööda vaadata.

Nõuded

• Kirjuta enda andmebaasi lisamise päringud C keelse rakenduse sisse.
• Kui lisamise koodi jooksutatakse mitu korda siis tuleb veenduda, et duplikaate ei tekiks (kontrolli kasutades mõnda teadatuntud unikaalset väärtust – nt kas sinu eID juba eksisteerib).
• Pead kasutama automaatselt genereeritud ID väärtusi. Ühtegi ID väärtust ei tohi koodi jäigalt sisse kodeerida.
  • Kasuta ühte eelnevalt välja pakutud meetoditest.

Edasijõudnute ülesanne 2 : Olemasolevate andmete muutmine

Andmete muutmiseks andmebaasis saame kasutada UPDATE päringuid. Selliste päringute jaoks peame esmalt tuvastama millist rida me uuendada soovime ja seejärel saame kirjutada sisse uuendatud väärtused. Oluline on, et tuvastaksime ainult selle või need read, mida me peameuuendama. Ülesande raames pead genereerima kõigile tudengitele Uni-ID tunnused.

Nõuded

• Genereeri kõigile tudengitele Uni-ID tunnused
• Uni-IDd tuleb lisada andmebaasi kasutades UPDATE lauset. Täita tuleb uni_id atribuut.
• Kood peab töötama ükskõik kui paljude tudengite puhul
• Kui genereeritav Uni-ID juba eksisteerib, pead tegema konfliktilahendust. Selle jaoks peaksid kirjutama vastava koodi C keeles.

Pärast seda tundi peaksid

Täiendav materjal

• SQL reference
  https://www.w3schools.com/sql/
• SQL tutorial
  https://www.tutorialspoint.com/sql/index.htm
• SQLite documentation
  https://www.sqlite.org/docs.html
• SQLite C library documentation
  https://www.sqlite.org/c3ref/intro.html
• SQLite C tutorial
  https://zetcode.com/db/sqlitec/
• SQLite in C/C++
  https://www.tutorialspoint.com/sqlite/sqlite_c_cpp.htm

Labori materjal

• Slaidid: Puud

Laboriülesanded

Selle labori baasülesande käigus pead looma kaks programmi ning võrdlema nende jõudlust. Edasijõudnute ülesande raames tuleb luua kolmas programm ning võrrelda selle jõudlust eelneva kahega.

Laboriülesanne: lineaarotsing vs kahendotsingpuu

Labori baasülesande raames on sul tarvis luua kaks programmi. Mõlemad täidavad täpselt sama ülesannet, leides mitu korda iga nimi kordub ette antud andmefailis. Esimese programmi raames pead kasutame lineaarset otsingut koos dünaamilise massiiviga unikaalsete kirjete hoidmiseks. Teises programmis täidab sama rolli meile kahendotsingpuu.

• Lae alla näidisrakendused mille põhjal laboritööd teha: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/13_trees_samples.zip
• Lae alla laboriülesande andmefail: https://blue.pri.ee/ttu/files/iax0584/andmefailid/13_trees_random_people_city_data.zip

Läbi labor jälgides samm-sammulist juhendit.

Nõuded

• Leia kõik failis olevad nimekombinatsioonid (ees + perenimi).
• Loenda mitu korda iga nimekombinatsioon esines.
• Väljasta tulemused väljundfaili
  • NB! Kuna ülesande eesmärk on saavutada paremat jõudlust, võid puu lahenduse juures kasutada globaalset failiviita. Ära ava korduvalt oma väljundfaili!
  • Kasuta järgnevat väljundi struktuuri:
    <eesnimi> <perenimi> <korduste arv>
• Loo kaks lahendust samale ülesandele
  • Esimeses lahenduses kasuta dünaamilist massiivi, mida laiendad jooksvalt realloc() funktsiooniga.
  • Teises lahenduses kasuta binaarotsingpuud.
• Arvuta kui kaua kulus sinu programmil andmete töötlemiseks aega
  • Pead arvestama vähemalt faili lugemise ja andmestruktuuri loomise ajakuluga
  • Võid arvesse võtta ka faili kirjutamise ja vabastamise
  • Tulemused peavad olema võrreldavad! St kui üks programmidest arvestas aja sisse vabastamise, siis peab ka teine seda tegema.
• Kuva rakenduses mitu unikaalset kombinatsiooni rakendus leidis
  • NB! Kuna rakendus peab olema
• Print the number of unique combinations your program found
  • NB! Kuna ülesande eesmärk on saavutada paremat jõudlust, võid puu lahenduse juures kasutada globaalset loendurit.
• Juhindu ülesande lahendamisel ajakulu optimeerimisele. Jäta struktuuri liikmeks olevad sõned staatiliseks – nt char combinedName[64]

Programm 1:Lineaarotsing

Alustuseks ava näiteprogramm  example_linear.c  ning tutvu selle ülesehituse ja sisuga. Proovi seda käivitada ja vaata väljundit.  See saab olema su aluskood.

Märka, et programm kasutab käsurea argumente – st käivita seda järgnevalt:  ./program_name input_file_name

Tutvus tehtud, alustame koodi muutmist enda ülesandele sobivaks.

1. Muuda lugemisfunktsioon sobilikuks ülesandele
   • Praegune versioon faili lugemisest eeldab ühte nime (ühesõnaline). Tunnitöö andmefailis on 4 välja rea kohta – eID, first name, last name and city.
   • Muuda fscanf()  funktsiooni, et see saaks hakkama täiendavate väljadega. eID ja linna salvestada vaja pole, ülesanne neid ei vaja.
   • Kleebi nimi kokku kujule  "Eesnimi Perenimi" . Kasuta kleebitud kuju nii otsingufunktsioonis veendumaks kas tegu on uue nimega või mitte ning uue nime puhul lisa see oma andmestruktuuri.
     Vihje: sprintf() on kõige lihtsam viis nime kokku kleepida.
2. Loenda mitu korda nimi esinenud on
   1. Lisa oma struktuuri kirjeldusse loendur – kasuta kas  int või  unsigned andmetüüpi.
   2. Enne kui hakkad oma loendamise osa kirjutama, vaata kuidas näitekoodis olev unikaalsuse kontroll ja laiendamine on ehitatud.
      Vihje: Vaata mida tagastab  CheckNameUnique()  funktsioon. Funktsiooni tagastus on võimekam kui selle praegune kasutusjuht näitekoodis.
   3. Lisa oma loendurile algväärtustamine olukorras kus said teada, et nägid nime esmakordselt (nimi ei ole massiivis).
   4. Lisa oma loenduri väärtuse uuendamine (suurendamine) olukorras, kui nimi oli korduv (juba lisatud andmebaasi).
3. Muuda oma väljastuse funktsiooni
   1. Muuda väljastust sedasi, et tulemus kirjutataks faili
   2. Väljasta nii nimi kui korduste arv
4. Väljasta mitu unikaalset nime kokku failist leiti
5. Lisa andmete vabastamine
6. Lisa aja mõõtmine
   1. Lisa 2 clock  tüüpi muutujat
   2. Pane paika 2 ajavõtupunkti – koht kust alustad aja mõõtmist (enne faili lugemist) ja koht kus lõpetad (nt enne väljastuse alustamist või pärast  mälu vabastamist)
   3. Arvuta palju aega kulus. Väljasta ajakulu.
7. Jooksuta koodi läbi valgrindi ja veendu selle korrektsuses. Nt. valgrind ./example_linear random_people_city_data.txt

Programm 2: Kahendotsingpuu

Alustuseks ava näiteprogramm  example_bin_search_tree c  ning tutvu selle ülesehituse ja sisuga. Proovi seda käivitada ja vaata väljundit.  See saab olema su aluskood.

Märka, et programm kasutab käsurea argumente – st käivita seda järgnevalt:  ./program_name input_file_name

Tutvus tehtud, alustame koodi muutmist enda ülesandele sobivaks.

1. Uuenda struktuuri kirjeldust. Sul on vaja hoida seal nii sõne kui loendurit, täpselt nagu lineaarse otsingu puhul.
2. Muuda lugemisfunktsiooni sarnaselt nagu tegid lineaarse otsinguga.
   1. Muuda fscanf() funktsiooni toetamaks failis olevat nelja parameetrit.
   2. Kleebi ees- ja perenimi kokku.
3. Uuenda lisamise funktsiooni InsertNode()
   1. Muuda selle parameetrit, et see toetaks lisamisel sõnet (meie puhul siis nimi)
   2. Muuda võrdlemise operatsiooni. Pane tähele, et erinevalt näitekoodist peame me tuvastama ka olukorda, kui puus täpselt sama sõne juba eksisteerib. Sellisel juhul peame loendurit uuendama.
4. Uuenda uue tipu loomise funktsiooni CreateNode()
   1. Muuda parameetrit, et sinna saaks edastada nime
   2. Lisa loenduri algväärtustamine
5. Uuenda puu väljastamise funktsiooni PrintTree()
   • Vii sisse uuendused lähtuvalt muudetud andmestruktuurist
   • NB! Kuna meie eesmärgiks on kiire programm, siis võid  sel korral failiviida luua globaalse muutujana. Muidugi kohustust pole, võid vabalt ka selle parameetrina edastada.
   • Muuda puu läbikäiku. Näites on puu läbikäiguks valitud eesjärjestus. Leia selline läbikäigu meetod, mille puhul oleks vastus sorteeritud tähestikulises järjekorras. Läbikäigu muutmiseks pead vahetama rekursiivsete kutsete ja praeguse liikme väljastamise järjekorda.
6. Realiseeri vabastamise funktsioon
   • Nii nagu kõik puu funktsioonid, peab ka vabastamine olema rekursiivne. Võta inspiratsiooni puu väljastamise funktsioonist. NB! Oluline on valida õige puu läbikäigu meetod (ees, järe või keskjärjestus). Vale meetodi puhul ei ole võimalik puud vabastada.
7. Lisa aja mõõtmine
8. Jooksuta koodi läbi valgrindi ja veendu selle korrektsuses. Nt. valgrind ./example_bin_search_tree random_people_city_data.txt

Programmi tööaja võrdlemine

Nüüd võrdle mõlema programmi ajakulu. Kumb on aeglasem, miks?

Mõtle ka kuidas võiks ajakulu muutuda kui

• Muudaksid realloc()  mälu laiendamise strateegia (n + 1) pealt  (n * 2) peale lineaarotsingul.
• Unikaalsete nimede arv suureneks märkimisväärselt. Kuidas kumbki rakendus sellele reageeriks – ürita väljendada end Big O  notatsiooni kasutades (https://www.bigocheatsheet.com)
• Failis oleks märkimisväärselt rohkem nimesid, kuid unikaalsete nimede arv jääks samaks (tõuseks korduste arv)
• Kui lahendasid ka edasijõudnute ülesande, siis kaasa samasse võrdlusse ka trie andmestruktuur. Kas sellel on ka mõni märkimisväärne eelis tavalise kahendotsingpuu ees?

Testimine

Järgnevad näited sisaldavad väljundit kõigi kolme versiooni tulemustefaili algusest. Võrdle enda loenduse tulemusi allolevatega.

Kokku peab olema  11440 unikaalset nimekombinatsiooni.

NB! Näidetes on ainult rakenduste arvutustulemused, et saaksid neid enda omadega võrrelda. Tegu ei ole programmi väljundiga – programm peab väljastama palju unikaalseid nimekombinatsioone esines ning kui kaua rakenduse töö kestis.

Edasijõudnute ülesanne: Trie puu

Loo kolmas programm ning võrdle selle efektiivsust eelneva kahe programmiga. Kasuta kolmandas rakenduses trie andmestruktuuri.

Kõik teised nõuded jäävad samaks.

Soovituslik andmestruktuur

Kasutame muudetud versiooni slaididel olnud näidisest. Asendame struktuuris oleva tõeväärtuse ( isLeaf ), mis näitas sõne lõppu, hoopis täisarvulise väärtusega. Kui väärtus on 0, siis selles asukohas nime lõppu ei ole. Kui väärtus on nullist suurem, siis on tegu lehega, mis tähistab nime. Number ütleb mitu korda nimi failis eksisteeris.

Vihje 1: Lisaks tähestikule arvesta ka tühiku ja miinuse sümboliga. Mõlemad neist on olemas andmefailis. Täiendavaid erisümboleid failis ei ole.

Vihje 2: Andmestruktuuri väljade algväärtustamine CreateNode()  funktsioonis on äärmiselt tähtis. Algväärtusta nii loendur kui kogu viitade massiiv..

Pärast seda tundi peaksid

Täiendav materjal

• Binary search tree
  https://www.geeksforgeeks.org/binary-search-tree-data-structure/
• Binary search tree visualization
  https://www.cs.usfca.edu/~galles/visualization/BST.html
• Trashing
  https://en.wikipedia.org/wiki/Thrashing_(computer_science)
• Algoritmid ja andmestruktuurid (Tartu Ülikool)
  https://dspace.ut.ee/bitstream/handle/10062/16872/9985567676.pdf

Labori materjal

• Slaidid: Ahelloendid

Laboriülesanded

Selles laboris on üks laboriülesanne, mida laiendab 2 edasijõudnute ülesannet

Laboriülesanne: Ahelloend

Baasülesandes tuleb sul luua rakendus, mis koostab ahelloendi, väljastab selle ning võimaldab loendist otsinguid teostada.

Lae alla aluskood: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/12_ll_basecode.zip

Nõuded

• Loo menüüprogramm, mis kasutab ühesuunalist ahelloendit
• Lisatavad elemendid tuleb paigutada loendi algusesse.
• Iga elemendi sees on täisarv (id) ja sõne (nimi)
  • id on automaatselt genereeritud, unikaalne, järjestikuline täisarv, mis algab nullist.
  • Nimi on sõne, mille sisestab kasutaja uue elemendi loomise käigus
  • Nime jaoks rakenda dünaamilist mälujaotust vastavalt nime sisestatava pikkusele.
• Ülesande lahendamise käigus tuleb sul luua minimaalselt järgnevad funktsioonid: PrintNode() , CreateNode() , InsertNode() , FindNodeByID() , FindNodeByName()  ja Unload()  .
• Lahendus tuleb luua etteantud aluskoodi peale.
• Lahendust luues järgi samm-sammult järgnevat juhendit. Loo funktsioonid vastavalt seal kirjeldatud nõuetele.

Samm-sammuline juhend

NB! Märka, et struktuuri deklareerides on loodud andmetüübile kaks erinevat nime –  struct node  ja list . Mõlemad tähendavad sama asja – st on aliased (nimekaimud) tänu tüübidefinitsioonile. Kasutuse poole pealt on funktsioonid koostatud sedasi, et struct node  viitab ühele elemendile, samal ajal kui list  viitab loendile kui tervikule.

---

Esimene funktsioon, mis tuleb luua, on ühe ahelloendi elemendi kõigi liikmete väljastamiseks (st id, nimi ja viit järgnevale elemendile). Funktsiooni prototüüp on juba päisefailis olemas. Sinul tuleb luua funktsiooni keha ja paigutada see koodifaili.

PrintNode()  funktsiooni peaksid kasutama iga kord, kui tuleb väljastada ühe elemendi sisu. Sedasi kui loendis olevad liikmed peaksid muutuma tuleb muudatus väljastuseks teha vaid ühes kohas. Ülesande lõpupoole on sul seda funktsiooni vaja ka nt otsingufunktsioonide tulemuste väljastamiseks.

Kontrolli, et funktsiooni poleks edastatud NULL-viita. NULL-viida puhul väljasta veateade, kehtiva viida puhul väljasta elemendi sisu.

Kommenteeri sisse testimise esimene osa (stage 1) ja jooksuta oma programmi!

NB! Testjuhtudes on sõned kirjutatud UTF-8 vormingus, mis töötab väga kenasti Linuxis, kuid võib tekitada veidi lahkhelisid Windowsi keskkonnas. Probleemide korral muuda sõnesid.

---

NB! See funktsioon on juba sinu eest valmis tehtud. Pööra tähelepanu funktsioonis oleva tsükli ülesehitusele! Sul on seda vaja loendi läbikäiguks  järgnevate funktsioonide lahendamisel.

Selle funktsiooni eesmärgiks on väljastada kõigi ahelloendis olevate elementide sisu. Funktsioonile PrintList()  edastatakse ahelloendi esimese liikme mäluaadress ning tsükli käigus liigutakse läbi ahelloendi kuni jõutakse loendi lõppu, mida tähistab NULL -viit.

Funktsioonile võib edastada ka   NULL -viida. See juhtub tavaliselt siis, kui loend mida väljastatakse osutub tühjaks.

Funktsioon ise väljastust ei teosta, vaid kasutab selle jaoks eelmises etapis loodud  PrintNode()  funktsiooni.

Kommenteeri sisse testimise teine osa (stage 2) ja jooksuta oma programmi!

---

Seda funktsiooni kasutame uue elemendi loomiseks ja väärtustamiseks. Funktsioon tagastab vastloodud uue elemendi aadressi. Väärtused elemendile antakse kaasa parameetritena.

1. Loo ja anna mälu uuele elemendile
2. Määra ära ID väärtus (järjestikuline suurenev täisarv, kasuta  static  märksõna)
3. Küsi mälu ja kopeeri struktuuri nimi
4. Väärtusta  pNext  viit
5. Tagasta struktuur

NB! Siin funktsioonis on kahel korral vaja mälu anda. Mõlemat tagastust tuleb kontrollida! Vea korral tagasta NULL-viit! Programm peab vea korral jätkama töötamist.

Kommenteeri sisse testimise kolmas osa (stage 3) ja jooksuta oma programmi! Ainukesed visuaalselt nähtavad erinevused on aadressiruumi muutus elementidel (läksime funktsioonide pinust kuhja). Valgrindiga käivitades näed mälu küsimiste arvu suurenemist!

---

Selle funktsiooni eesmärgiks on lisada eelmise funktsiooni poolt loodud uus element  pNode  ahelloendisse, millele viitab ppHead . Topeltviit on vajalik, et lisada uus element loendi algusesse.

Baasülesandes lisame uue elemendi loendi algusesse. Selleks on vaja ainult 2 omistuslauset kirjutada!

NB! Enne lisamist kontrolli, et  pNode  poleks NULL -viit!

Kommenteeri sisse testimise neljas osa (stage 4) ja jooksuta oma programmi! Visuaalselt väljundis midagi ei muutu võrreldes eelmise korraga.

---

Seda funktsiooni kutsutakse hävitajaks (destructor), mille eesmärk on andmestruktuur mälust vabastada. Vabastamise käigus vabastatakse ka struktuuri liikmed, mis on dünaamiliselt loodud – meie puhul on selleks nimi.

Ahelloendi vabastamiseks on vaja tsüklis käia läbi kogu loend.  Läbikäigu ideega tutvu  PrintList()  funktsiooniss.

Loendi vabastamise juures on oluline pöörata tähelepanu praeguse elemendi vabastamisele. Nimelt pärast praeguse elemendi vabastamist ei ole meil enam ligipääsu selle pNext  viidale. Sellest tingitult on meil vaja vabastamiseks täiendavat abiviita praegusele elemendile, mis teeb selle protseduuri natuke keerukamaks.

Tsüklis on 3 olulist sammu. Kõige elegantsema tsükli saad kasutades while()  tüüpi tsüklit!

1. Praeguse elemendi aadressist koopia tegemine (seda koopiat kasutame vabastamiseks)
2. Järgmise elemendi juurde liikumine ( pCurrent = pCurrent->pNext )
3. Praeguse elemendi ja selle liikmete vabastamine.

Kommenteeri sisse testimise viies osa (stage 5).  Jooksuta programmi kasutades valgrindi! Peaksid nägema, et rakendus on 6 korda mälu küsinud ning vabastanud.

---

Selles osas loome kaks otsingufunktsiooni, millest üks otsib nime ja teine ID väärtuse järgi. Kui otsing annab tulemust (st loendis on selline element), tagastatakse viit leitud elemendile. Kui elementi loendis ei ole, tagastatakse NULL-viit.

Kasuta  PrintNode()  funktsiooni leitud elemendi väljastamiseks.

Kommenteeri sisse testimise viiesosa (kuues 6) ja jooksuta oma programmi! Märka, et näidisväljundis on veateade väljastatud PrintNode() poolt ja ei ole seotud otsinguga!

---

Palju õnne! Kõik baasfunktsionaalsuseks vajaminevad funktsioonid on nüüd valmis! Nüüd lisa abifunktsioonid ja koodilaused, et rakendus oleks kasutatav läbi menüü. Testimiseks mõeldud koodi võid soovi korral oma rakendusest kustutada.

Lisada tuleks näiteks nime küsimine uue kirje loomisel või otsitava sisestused otsingufunktsioonide kasutamiseks ning vajadusel tagastuste töötlemiseks. Kui valmis, anna märku tunnitöö esitamiseks!

Testimine

Siin on näha täielikult valmis programmi väljund.

Edasijõudnute ülesanne 1: Tähestikulises järjestikus sorteeritud loend

Selle ülesandega muudame oma elementide lisamise funktsiooni selliseks, et loend oleks alati sorteeritud tähestikulises järjekorras

Nõuded

• Uuenda InsertNode()  funktsiooni sedasi, et uus element paigutataks olemasolevate vahele sedasi, et loend oleks tähestikulises järjekorras
  • Selleks pead toetama elemendi lisamist loendi algusesse, lõppu või keskele
• Uuenda   FindNodeByName()  funktsiooni, et see lõikaks kasu tähestikulisest järjekorrast.
• Kui oled varasemalt lahendanud edasijõudnute ülesande 2, siis uuenda ka eemaldamise funktsiooni, et ka see lõikaks kasu tähestikulisest järjekorrast.

Märkused

• Vastavalt loendi asukohale kuhu element lisatakse viitasid käidelda erinevalt.
• Veendu asukohas enne lisamise alustamist!

Edasijõudnute ülesanne 2: Elementide eemaldamine

Loo kaks funktsiooni elementide eemaldamiseks loendist vastavalt nime või ID alusel.

Nõuded

• Realiseeri  RemoveNodeByName()  funktisoon, mis eemaldab elemendi nimelise vaste korral.
• Realiseeri RemoveNodeByID()  funktsioon, mis eemaldab elemendi ID vaste korra.
• Võimalusel kasuta ära omadust, et loend on juba sorteeritud tähestikulises järjekorras (edasijõudnute ülesanne 1)
• Veendu loendi terviklikkuses pärast elemendi eemaldamist. Testi loendi keskelt, algusest ja lõpust!

Märkused

• Esmalt leia kas element üldsegi eksisteerib mida peaksid eemaldama
• Eemaldamisel ühesuunalisest loendist on sul vaja meeles pidada eelmise elemendi asukohta! Seetõttu ei saa sa korduvkasutada  FindNodeBy()  funktsioone! (Saaksid, kui see oleks kahesuunaline ahelloend).
• Algusest, keskelt ja lõpust eemaldamine on erinev! Kontrolli positsiooni enne eemaldamise alustamist, seejärel vali sobilik eemaldamise meetod.
• Ära unusta mälu vabastada!
• Topeltviit on vajalik loendi algusest eemaldamiseks.

Pärast seda tundi peaksid

Täiendav materjal

Labori materjal

• Slaidid: Rekursioon
• Slaidid: Pinu (magasin)
• Tunnis läbi tehtavad näited
  • Rekursiivne faktoriaal: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial.c
  • Sabarekursiivne faktoriaal: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial_tail.c
  • Pinu: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_base.c
• Alternatiivne näide: Pinu, mis kasutab pinuviita (SP) viidana: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_sp_as_pointer.c

Laboriülesanded

Selles laboris on kaks baasülesannet, üks iseseisev edasijõudnute ülesanne rekursioonile ning üks edasijõudnute laiendusülesanne pinule.

Ülesanne 1: Rekursiooni ülesannete komplekt

Esimese ülesande raames tuleb sul luua kolm rekursiivset programmi (osa 1, 2 ja 3). Ülesanne saab esitada ainult siis, kui kõik kolm on valmis!

NB! Tegu on äärmiselt lihtsate ülesannetega, väldi internetist lahenduste otsimist!

Tunni alguses luuakse näidislahendus faktoriaali rekursiivsest lahendamisest!

Nõuded

• Võid laheduse luua ühe failina kus on kolm rekursiooni korraga või kolme erineva programmina. Näited on tehtud kolme erineva rakendusena.
• Kõigil juhtudel on kohustuslik toetada sisendina positiivset täisarvu. Negatiivse sisendi korral on kas lahenduses märgitud eraldi vastus (baasjuht) või tuleb kuvada viga.
• Sisendi võid küsida rakenduse sees või lugeda käsurea argumendina.
• Iteratiivseid lahendusi kasutada ei tohi, kõik kolm osa peavad olema lahendatud rekursiivselt.
• Esitada saab ülesannet vaid siis, kui kõik kolm osa on valmis.

Osa 1: summa

Loo rakendus, mis leiab kõigi positiivsete täisarvude summa kuni kasutaja sisestatud arvuni. Negatiivse argumendi korral rekursiivsele summa funktsioonile on summa 0 (positiivsed arvud puuduvad, baasjuht).

Osa 2: astendamine

Loo rakendus, mis lubab astendada x^y. math.h teegi ja sisse ehitatud astmefunktsioonide kasutamine ei ole lubatud.

NB! Kuigi nõue on vaid rakendus luua positiivsetele täisarvudele, siis võid proovida ka laiendada lahendust näiteks negatiivsetele arvudele.

Osa 3: Fibonacci arvud.

Loo rakendus, mis leiab soovitud Fibonacci arvu. n-indaks fibonacci arvuks on selle kahe eelneva Fibonacci arvu summa ehk siis fib_x = fib_{x – 1} + fib_{x – 2}. Erinevalt eelnevatest rekursioonidest on Fibonacci jadal kaks seetõttu ka 2 baasjuhtu.

Fibonacci arvud on  0, 1, 1, 2, 3, 5, 8, 13, 21, …,

Märkasid kui kaua aega läks viimase leidmiseks? See on ootuspärane laboriülesande lahendamisel ning parandada vaja ei ole, kuid mõtle kindlasti miks nii juhtus!

Kõik 3 valmis, näita nüüd ülesanne ette!

Programmi ajakulu saad mõõta kasutades time  programmi. Siin on võrdluseks kaks erinevat rekursiivset lahendust samast programmist. Teisel juhul on kasutatud lähenemist mida kutsutakse tail-recursion’iks ehk sabarekursiooniks. Selle kohta võid vajadusel uurida omal käel.

Ülesanne 2: pinu

Selles ülesandes loome menüüprogrammi, mille sisuks on demonstreerida pinu funktsioone. Tunnis lahendatav ülesanne on demonstratiivne ning toetab varasemalt õpitud dünaamilist mälu – selline lahendus ei too oma keerukuse tõttu välja pinu eeliseid kiiruses!

Tunni alguses luuakse osaline näidis, kus lahendame ära Push() funktsiooni!

Nõuded

• Loo oma rakendusele menüü struktuur – kasutaja peab saama valida millist operatsiooni teostada
• Loo Pop() ja Peek() funktsioonid
  • Pop() eemaldab pealmise elemendi pinust ja tagastab selle väärtuse.
  • Peek() tagastab pealmise elemendi, kuid ei eemalda seda
• Loodavad funktsioonid ise elementide väärtusi kuvada ei tohi! Ekraanile kuvatakse väärtused pärast menüüsse tagastamist!
• NB! Baasversioonis on lubatud reserveerida üks väärtust tähistamaks pinu alatäitumist, et väljastuses illegaalset väärtust ei kuvataks. Edasijõudnute versioonis see lubatud ei ole.
• Vastavalt funktsioonile veendu, peavad olema realiseeritud kas ala- või ületäitumise kontrollid.
• Pööra tähelepanu olukorrale kus pinust eemaldatakse kõik elemendid – reallociga 0 baiti küsida on ohtlik, tuleks kasutada free funktsiooni!

Pinu silumisfunktsioon

Selleks, et saaksid paremat aimu pinu sisust pakun sulle ka silumisfunktsiooni. Tegelikus olukorras sellist funktsiooni sageli rakendada ei saaks kuna see võib olla vastuolus pinu piirangute ning ka konkreetse pinu realisatsiooniga!.

Testimine

Testimisel pööra tähelepanu järgnevale:

• pinu ületäitumine
• pinu alatäitumine
• pinu andmete vabastamine pärast viimase elemendi kustutamist (valgrind!)
• Mälulekke ohule kui programm suletakse kui pinus on veel andmeid (valgrind!)

Edasijõudnute ülesanne 1: rekursiooni praktiline kasutusjuht

See edasijõudnute ülesanne on sulle antud ingliskeelse algoritmi kirjeldusena. Tegu on täiesti eraldiseisva ülesandega, mis ei ole seotud eelnevalt tehtud tunnitöö lahendusega!

NB! Olulised muutujad on antud matemaatikutele omases kirjapildis ehk üksikute tähtedena – soovitus oma programmis kasuta pikemaid ja selgitavamaid nimesid nagu on programmeerimises omane.

Given search key K  and an array A  of n  integers A₀, A₁, … , A_{n – 1} sorted such that A₀ ≤ A₁≤ … ≤ A_{n – 1} use the following algorithm to find if K ∈ A

1. Set lowIndex L  to   and highIndex H  to n − 1 .
2. Call the recursive function using 4 arguments – A, L, H, K .
   • If L > H , the search terminates as unsuccessful – return 0
   • Set m  (the position of the middle element) to the floor of (L + H)  /  2
   • If A_m < K, set L  to m + 1 , call recursion again
   • If A_m > K, set H  to m − 1 , call recursion again
   • If A_m = K, the search was successful – return 1

Ülesanne valmis, valmista enne esitamist ette vastused järgmistele küsimustele. Kui vastused olemas, anna märku!

• Ajalike keerukus – võrdle antud algoritmi ja tavalist lineaarset otsingut. Mitu võrdlust läheks vaja, et võrrelda massiivi kus on
  • 16 liiget
  • 256 liiget
  • 100 000 liiget
• Anna hinnang algoritmi keerukusele  – nt konstantne, logaritmiline, lineaarne, eksponentsiaalne (https://www.bigocheatsheet.com)
• Kui massiiv poleks sorteeritud, kas see algoritm töötaks?

Edasijõudnute ülesanne 2: pinu laiendus

Selles ülesandes loome paar lisavõimalust oma pinule ning teeme seda veidi universaalsemaks.

Nõuded

• Lisa oma pinule järgmised funktsioonid
  • Duplicate()
  • Swap()
• Need funktsioonid tohivad kasutada ainult Push() ja Pop() funktsioonide väljakutseid!
• Muuda oma Pop() ja Peek() funktsioonide kujusid sedasi, et kehtiksid järgmised nõuded
  • Pinu peab toetama kõiki arve (ei tohi olla reserveeritud mitmetähenduslike väärtusi).
  • Juhul kui tekib pinu alatäitumine, siis kuvatakse vaid veateade, väärtust ennast ei kuvata
• Märkus: Lisafunktsioonide jaoks pead suure tõenäousega muutma ka Push() funktsiooni!

Testimine

Olulised kitsaskohad mida testida (lisaks tavaolukordadele)

• Pop(), kui pinu on tühi (ei tohi numbrit väljastada

• Duplicate(), kui andmeid pinus pole
• Duplicate(), kui pinu on täis

• Swap(), kui pinus andmeid pole
• Swap(), kui pinus on vaid 1 liige

Pärast seda tundi peaksid

• Teadma mida tähendab rekursioon, sh rekursiivne funktsioon ja rekursiivne andmetüüp.
• Oskama kirjutada lihtsaid rekursioone
• Teadma, et eksisteerib ka sabaga rekursioon
• Teadma rekursioonide headest omadustest ja probleemidest
• Teadma rekursioonide kasutusvaldkondi
• Teadma mida tähendab abstraktne andmestruktuur
• Teadma mis on pinu ning millised on selle omadused
• Teadma pinu kasutusvaldkondi
• Oskama luua pinu ning sellele kohustuslike funktsioone

Täiendav materjal

• Introduction to Recursion – Data Structure and Algorithm Tutorials
  https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/
• Merge sort (recursion)
  https://www.geeksforgeeks.org/merge-sort/
• Quick sort (recursion)
  https://www.geeksforgeeks.org/quick-sort/
• Stack data structure
  https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Labori materjal

• Slaidid: Dünaamiline mälujaotus 2
• Täiendav näide: ümbris-struktuur (wrapper struct) dünaamilisele massiivile

Laboriülesanded

Selles laboris on üks ülesanne, mida laiendab 2 edasijõudnute ülesannet

Ülesanne: Faili lugemine kasutades dünaamilist mälu

Selle ülesande eesmärgiks on tutvuda kuidas lugeda teadmata pikkusega faile sedasi, et me kasutame täpselt nii palju mälu kui failis olevate andmete hoiustamiseks vaja on.

Andmefail

Andmefaili struktuur on järgnev:  <indeks> <perenimi> <eesnimi> <õppekava kood> <punktide arv>

• Indeks (täisarv)
• Ees- ja perenimi – erineva pikkusega sõned
• Õppekava kood – 4-tähemärgi pikkune sõne
• Punktide arv – kümnendmurd vahemikus 10,0 kuni 30,0,. Täpsuse 0,1.

Võid kasutada andmefailide loomiseks oma eelmise nädala laboriülesande lahendust. Testimiseks on antud siiski kindlad failid, et saaksid oma väljundit võrrelda.

Andmefailid mille väljundi näited on ka testimine osas: https://blue.pri.ee/ttu/files/iax0584/andmefailid/8_scholarship_data.zip

Nõuded

• Loe teadmata pikkusega andmefaili sisu mällu
  • Lugemiseks kasuta realloc() funktsiooni, laiendades mäluala suurust jooksvalt lugemise käigus.
  • Andmed salvesta dünaamiliselt loodud struktuurimassiivi
  • Lugemise lõpuks peab küsitud mälumaht olema täpselt nii suur kui on vaja failis olevate andmete hoiustamiseks.
  • Faili tohib vaid ühel korral lugeda (korduv lugemine keelatud! Ka lihtsalt reavahetuste arvu lugemine ei ole lubatud!)
  • Arvesta, et faili pikkus võib muutuda! St faili pikkus selgub lugemise käigus!
• Kõik muutuva pikkusega sõned tuleb mälus hoida täpse pikkusega.
  • Lugemise ajal kasuta staatilist puhvrit, struktuuris hoidmiseks kasuta dünaamilist mälu!
• Failis on stipendiumile kandideerivate tudengite loetelu. Stipendiumi saavad:
  • Igast järgnevast erialast kuni 7 kõige kõrgema punktisummaga tudengit: IACB, EARB ja MVEB.
• Kuva stipendiumi saajate nimekiri ning näita mitu tudengit igalt erialalt stipendiumi sai.
• Veendu, et programm ei tekita mälulekkeid!

Andmestruktuur ülesandele

Selles ülesandes läheme üle dünaamilisele mälule struktuuri liikmete hulgas mille pikkus on muutuv (sõned ja teised massiivid) – see säästab meil mälu ja suurendab paindlikkust. Struktuur võtab järgneva kuju:

Märkused:

• Soovi korral võid nimetusi endale sobilikumaks muuta
• fName ja lName on nüüd viidad, mis vajavad dünaamilist mälu enne kui nendesse midagi salvestada saab – seda kuna nime pikkus on muutuv inimeselt inimesele.
• Õppekava koodi massiiv on staatiline sest see on alati täpselt sama pikk – dünaamiline mälu siin oleks raiskav.
• Üksikud täisarvud, murdarvud jne jäävad samuti staatiliseks – jällegi, dünaamiline mälu siin teeks programmi põhjendamatult aeglasemaks ja keerukamaks.

Soovituslik loetelu funktsioonidest

NB! Funktsioonide tegelik kuju sõltub kuidas otsustad ülesannet lahendada ja struktureerida.

Minimaalselt on sul vaja kolme funktsiooni:

• Andmete lugemise funktsioon failist (vali välja järgmisest peatükist).
• Vastuste väljastamise funktsiooni.
  
  void PrintScholarships(person *pStudents, int n); // Good for base task void PrintScholarships(student_wrapper stdWrapper); // Good for advanced task 2

  1 2	void PrintScholarships(person *pStudents, int n); // Good for base task void PrintScholarships(student_wrapper stdWrapper); // Good for advanced task 2

• Andmete vabastamise funktsiooni
  
  void FreeStudentData(person *pStudents, int n); // Good for base task void FreeStudentData(person **ppStudents, int n); // Good for base task with defensive programming void FreeStudentData(student_wrapper stdWrapper); // Good for advanced task 2

  1 2 3

  void FreeStudentData(person *pStudents, int n); // Good for base task void FreeStudentData(person **ppStudents, int n); // Good for base task with defensive programming void FreeStudentData(student_wrapper stdWrapper); // Good for advanced task 2

Soovituslikud funktsioonid enda elu lihtsamaks tegemiseks

• qsordi võrdlusfunktsioon
  
  int ComparPersonByPoints(const void *a, const void *b);

  1	int ComparPersonByPoints(const void *a, const void *b);

• Ühe tudengi andmete printimise funktsioon (kasulik kui prindid tudengi andmeid, kes stipendiumi saab.
  
  void PrintStudent(student *s);

  1	void PrintStudent(student *s);

• Kaitsva programmeerimisstiili jaoks kulub ära ka slaididel näidatud vabastamisfunktsioon
  
  void FreeMemory(void **p);

  1	void FreeMemory(void **p);

Lugemise kontrollimiseks võib olla mõistlik luua ka funktsioon, mis trükib kõigi tudengite andmed välja mis failist kätte saadi. See aga pole ülesande osa.

Funktsioon andmete lugemiseks

Sel korral võtab andmete lugemise funktsioon veidi teistsuguse kuju.  Funktsioonist on meil vaja saada kätte 2 uut väärtust – mälu asukoht ja ridade arv. Pakun välja kolm võimalikku lahendust – vali endale meelepärane!

Esimene variant tagastab ridade arvu ning edastab mälu asukoha kasutades topeltviita :

Teine variant tagastab mälu asukoha ning edastab ridade arvu kasutades viita:

Pakun välja ka kolmanda võimaluse. Selle eelis on võimalus funktsioonist tagastada kood, mida saab tõlgendada kas eduka või ebaõnnestunud lugemisega. Koode võib olla enam kui soovid erinevate vigade detaile edastada.

Testimine

Esimeses näites kasutame pikemat andmefaili, kus kõik loetelud said täis.

Teises näites on andmefail lühem.

Edasijõudnute ülesanne 1: Optimaalne mäluhõive

Selles ülesandes muudame oma dünaamilise mälu hõivamise mõistlikumaks kasutades optimaalsemat mälu laiendamise strateegiat.

Nõuded

• Muuda oma faili lugemist sedasi, et lugemisek kasutaksid (n * 2) strateegiat
  • St iga kord kui küsitud mälumaht saab otsa, laiendatakse mäluala 2x võrreldes olemasolevaga
• Alustamiseks vali n mis on suurem kui 1 (vali siiski vähemalt 3x väiksem kui pikima faili pikkus

Edasijõudnute ülesanne 2: ümbris-struktuur

Selles ülesandes muudame oma koodi veelgi loetavamaks ja seotumaks, pannes oma andmestruktuuri ja selle omadused ühte ümbritsevasse struktuuri.

Nõuded

• Pane oma struktuurimassiiv teise struktuuri ehk ümbrise sisse (wrapper struct),
• Ümbrises peaks olema 3 muutujat – viide struktuurile, struktuuri suurus ja struktuuri kasutatud liikmete arv.
• Muuda oma funktsioonide parameetreid nii, et nüüd need kasutaksid uut vastloodud ümbrisstruktuuri.
• NB! Mõtle läbi mis funktsiooni on mõistlik viit ümbrisele anda, millisesse pole seda mõtet teha!

Vihje: Kuna nüüd on iga välja poole pöördumisel vaja ümbrisstrukuturist valida välja õige liige, siis võib loetavuse huvides olla see mõistlik “lahti pakkida” eraldi muutujasse vastava funktsiooni või tsükli sees. Näiteks

Pärast seda tundi peaksid

• teadma erinevaid võimalusi kuidas struktureerida ja lugeda faile mille pikkus võib erineda
• oskama dünaamiliselt oma massiivide suurust muuta
• oskama lugeda faile dünaamilist mälu kasutades jooksvalt ja täpselt
• teadma kõiki võimalike realloci tagastuste võimalus
• teadma kahte laiendamise strateegiat (n + 1) ja (n * 2) ning oskama neid kahte võrrelda
• oskama struktuuri liikmetele mälu küsida
• teadma ja oskama rakendada ohutu programmeerimise tehnikat mälu vabastamisel.
• teadma kõiki samme mida strdup() funktsioon taustal teeb

Täiendav materjal

Labori materjal

• Slaidid: Dünaamiline mälu 1

Laboriülesanded

Sellel nädalal on üks ülesanne, mida laiendab kaks edasijõudnute ülesannet.

Ülesanne: Juhuandmete generaator

Selle nädala ülesandeks on koostada juhuandmetega andmefaili generaator. Selliseid generaatoreid kasutatakse sageli rakenduste testimiseks enne kui on ligipääs reaalsetele andmetele.

Lae alla aluskood: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/7_generator_starter.zip

Nõuded

• Ehita oma rakendus ette antud aluskoodi põhjale
• Küsi kasutajalt mitu kirjet ta soovib genereerida. Piirangut olla ei tohi!
• Kõik kirjed salvestatakse genereerimise käigus struktuurimassiivi, mis luuakse kasutades dünaamilist mälu.
• Vali juhuslikult etteantud valimitest välja eesnimi, perenimi ja  õppekava kood.
• Genereeri juhuslikult sisseastumispunktid.
  • Punktid on vahemikus 10 – 30 punkti. Otspunktid on kaasatud. Täpsus on 0,1 punkti (nt 24.7)
• Sorteeri genereeritud andmed perenime järgi. Kui perenimed ühtivad, sorteeri eesnime järgi.
• Väljund kirjuta faili järgnevas vormingus:
  <indeks> <perenimi> <eesnimi> <õppekava kood> <sisseastumispunktid>
  • Indeks on unikaalne täisarv. Esimesel kirjel on indeksis 0, igal järgneval suureneb see 1 võrra.
• Veendu, et kogu mälu on programmi lõppedes vabastatud kasutades valgrind’i.

Qsordi võrdlusfunktsioon

Pakun välja kaks erinevat võrdlusfunktsiooni võimalust. Esimesel puhul tehakse tüübiteindused jooksvalt, likvideerides lisamuutujate loomise vajaduse.

Teisel juhul loome lisaviidad, mis võtavad täiendavalt mälu, kuid lihtsustavad koodi loetavust.

Töövoog

• Loo vajalik struktuuri kirjeldus
• Küsi kasutajalt palju kirjeid vaja
• Küsi mälu vajalike kirjete hoidmiseks, kontrolli!
• Genereeri vajalikud kirjed
  • Iga isiku jaoks pead genereerima kõik väljad juhuslikult.
  • Iga  struktuuri liikme valimiseks eesnimede, perenimede ja õppekava koodide valimist pead genereerima juhusliku numbri.
    Vihje: Sa võid nime kas kopeerida enda struktuuri või hoiustada vaid viita nimele
  • Lisaks genereeri ja salvesta ka punktid.
    Vihje: Mõtle matemaatiliselt – nt mis vahe on 30 ja 300!?! rand() funktsioon väljastab sulle täisarvu olenemata mida sa teha üritad sellega.
• Sorteeri struktuurid
• Kirjuta andmed väljundfaili
• Vabasta mälu

Kontrolli oma rakendust kasutades valgrindi! Seda mitte ainult lõpus, vaid ka siis kui rakendus käitub imelikult või jookseb kokku!

Testimine

Rakenduse väljund on võrdlemisi lihtne ja lühike

Vaadates väljundfaili näeme, et tulemused on kenasti sorteeritud (näites vaid esimesed 15 rida)

Edasijõudnute ülesanne 1: väljundfaili formaat

Selle ülesande käigus lisame oma lahendusele CSV formaadi toe väljundis ning lubame kasutajal valida sobivlikku väljundformaati.

Nõuded

• Lisa oma programmile võimekus genereerida andmeid CSV formaadis.
  • Esimene rida CSV failis peab olema päis väljade nimetustega
  • Sellele järgnevad genereeritud andmeread, komadega eraldatud. NB! CSV puhul koma järele tühik ei käi.
• Küsi kasutajalt kummas formaadis ta soovib faili genereerida (tühikutega eraldatud või CSV) ning genereeri sobilik väljundfail.
• Tühikutega eraldatud faili laiendiks peab olema .txt , komadega eraldatud faili laiendiks peab olema .csv .
• Veendu, et CSV fail on korrektselt genereeritud – proovi avada või importida seda kasutades Libreoffice Calc’i või Microsoft Office’it ja vaata kas nad tuvastavad väljad korrektselt.

Edasijõudnute ülesanne 2: seadistused

Selles lisaülesandes muudame oma generaatori paindlikumaks ja lisame seadistuste võimekuse.

Nõuded

• Kõik seadistused tuleb hoida struktuuris – loo eraldi struktuuri kirjeldus ja struktuur selleks.
• Kõigil seadistustel peavad olema vaikeväärtused
• Programm peab kasutama vaikeväärtusi kui kasutaja ei soovi seadeid muuta. Kuidas kasutaja muutmissoovist teada peab anda võid ise otsustada.
  Näiteks võib programm seda esimese asjana käivitudes küsida või saab kasutaja käivitada programmi kindla käsureaargumendiga, mis seadistuse avab.
• Kasutajal peab soovi korral olema võimalik järgnevaid seadistusi muuta programmis sees olles
  • Millised andmeväljad genereeritakse (igaühte peab olema eraldi võimalik sisse-välja lülitada)
  • Väljundfaili nimi (ainult nimeosa, laiend valitakse automaatselt lähtuvalt valitud väljundformaadist!)
  • Väljundformaadi seadistus (edasijõudnute ülesande 1 osa, tõsta struktuuri sisse)
  • Genereeritavate kirjete arv (baasülesande osa, tõsta struktuuri sisse)
  • Alam- ja ülempiir sisseastumispunktidele
• NB! Genereeritavate kirjete arvu tuleb küsida hoolimata sellest kas kasutaja soovis seadeid muuta või mitte. Eesmärk on lihtsalt hoida seadistusi koos.
• Kasutajale tuleb kuvada genereerimisseaded olenemata sellest kas ta soovis neid muuta või mitte.

Märkus: Soovi korral võid seadistusi hoida eraldi failis, kuid see pole vajalik. Kasutaja tehtud muudatusi seadetesse ei ole vaja meeles pidada järgmisel programmi käivitamisel. Küll aga kui sa soovid seadefaili kasutada, siis veendu, et kasutaja saab seadistusi muuta läbi programmi (ilma, et ta peaks seadefaili käsitsi muutma).

Vihje: Siin saab kolmikoperaatorit hõlpsasti ära kasutada
printf("First name: %10s\n", settings.genFirstName ? "Yes": "No");

Pärast seda tundi peaksid

• Oskama kasutada dünaamilist mälu
• Oskama kontrollida kas programmis on mälulekkeid
• Teadma mis olukorras on dünaamilist mälu mõistlik kasutada ja millal mitte
• Teadma dünaamilise mälu võludest ja valudest
• Tegema vahet pinumälul ja kuhjal ning mis muutujad kuhu lähevad.

Täiendav materjal

Labori materjal

• Slaidid: Silumine
• Slaidid: Makefile ja logimine
• Täiendav näide: Korduvkasutatava koodi (teegi) loomine
• Lisalugemist: Fun with valgrind (inglise keeles)
• Testfailid valgrindi proovimiseks: https://blue.pri.ee/ttu/files/iax0584/demokood/valgrind.zip

Laboriülesanded

Selles laboris on üks ülesanne, mis on jagatud kahte ossa. Ülesannet laiendab kaks edasijõudnute ülesannet.

NB! Kuigi arendada saad oma lahendused ükskõik mis platvormil, siis üks osa tõestusest vajab Valgrind tööriista kasutamist. Valgrind töötab kontrollitult vaid Linuxil (rakendus olemas ka MacOSil) – vajadusel saad rakenduse tõestuseks üles laadida kooliarvutisse.

Lae alla andmefailid: https://blue.pri.ee/ttu/files/iax0584/andmefailid/6_make_data.zip

Arhiiv sisaldab andmefaile nii baasülesandeks kui edasijõudnute ülesandeks!

Ülesande osa 1 / 2: Andmete lugemine, töötlemine

Esimeses osas on meie eesmärgiks saada programmi andmed sisse ning demonstreerida oma oskusi Makefile’i koostamiseks ja kasutamiseks ning mälus vigade puudumiseks.

Nõuded

• Loe andmed sisendfailist
  • Andmefaili struktuur
    <õppeaine nimi> <hinnete arv> <hinded>
  • Loetud andmed salvesta struktuurimassiivi. Hinnete jaoks võid teha mõistliku pikkusega massiivi – näiteks max 20 hinnet aine kohta (lähtuvalt näitefaili struktuurist).
• Kuva ekraanil
  • Õppeaine nimi
  • Õppeaines antud hinded
  • Õppeaine keskmine hinne
• Hoia andmete lugemine, keskmise leidmine ja väljastus eraldi funktsioonides!
• Kood peab olema tükeldatud vähemalt kahte koodifaili, millest mõlemal on oma päisefail. Tükeldus peab olema mõistlik, kuid on jäetud sinu otsustada.
• Kood kompileeri programmiks kasutades Makefile’i
  • Makefile’is peab olema minimaalselt kirjeldatud retsept all , muutuja CFLAGS  ja lipud -Wall -Wextra -Wconversion -g
  • Ülejäänud Makefile’i keerukuse ja ülesehituse võid ise otsustada
•  Kaitsmisel
  • Näita projekti kompileerimist kasutades Makefile’i
  • Näita programmi väljundit läbi Valgrindi tõestamaks, et puuduvad mäluvead.

Vihje

Hinnete arv aine kohta varieerub – st iga failis olev andmerida võib olla erineva pikkusega. Seetõttu andmefaili võimalik lugeda ühe ühte fscanf()  funktsiooni väljakutsega!

Lugemine on vaja teha pesastatud tsüklitega, kus

• Välimine tsükkel loeb õppeaine nime ning hinnete arvu
• Vastavalt välimisest tsüklist saadud hinnete arvule määratakse ära sisemise tsükli korduste arv, lugemaks sisse õppeaines antud hinded. Ära unusta sisemise tsükli fscanf()  funktsiooni tagastust kontrollida!

Testimine

Näide võimalikust koodi struktuurist.

NB! Failide nimed ei ole ette määratud, tegu on lihtsalt näidisega. Samuti piisab vaid ühest andmefailist ning see ei pea olema eraldi kaustas.

NB! Järgnevas näites ei ole kajastatud valgrindi väljundit! Ära unusta testida oma programmi korrektsust valgrindiga!

Ülesande osa 2 / 2: Logimine

Selle osa raames tuleb sul lisada oma programmi logimine.

Nõuded

• Lisa oma programmi logimine
  • Üks logi rea kohta. Logi ei tohi olla kaherealine!
  • Iga logi rida algab ajatempliga. Ajatempel peab sisaldama kuupäeva (päev, kuu, aasta) ja kellaaega (tunnid, minutid, sekundid)
• Programmi järgmine käivitus ei tohi kustutada eelneva käivituse logi
• Logitavad sündmused
  • Programmi käivitamine ja sulgemine
  • Sisendfaili avamise seisund (edukas / ebaõnnestunud)
  • Faili lugemine lõpetatud. Logis kuva loetud ridade arv!
  • Faili lugemine katkestatud kuna massiivi maksimaalne piir on ületatud (maksimaalne piir kuvatakse logis).  NB! Sul on struktuuride massiiv ja struktuuri liikmena hinnete massiiv!
  • Viga aine keskmise hinde arvutamisel.
• Logi terviklikkus peab olema garanteeritud ka programmi kokkujooksu korral
  • Võimalus 1: Väljundpuhvrist on võimalik sunniga andmed faili kirjutada kasutades funktsiooni fflush()
  • Võimalus 2: Sulge logifail pärast kirjutamist – faili sulgemise järel kirjutatakse puhvris olevad andmed faili.
• Logifaili avamise ebaõnnestumisel peab programm jätkama tööd, mitte väljuma! Teavita kasutajat logimise ebaõnnestumisest.

Vihjeid

• Valmista ette logitav sõne enne logimise funktsiooni väljakutsumist! Ära koorma logimise funktsiooni üle parameetritega. Sõne ettevalmistamiseks on hea funktsioon snprintf()
• Logifunktsiooni lihtsustamiseks on soovitatav mitte failiviita ega nime sellele kaasa anda. Võimalike lahendusi:
  • Ava ja sulge fail logifunktsioonis järjest
  • See on üks võimalikest eranditest globaalmuutujale – soovi korral võid teha failiviida logifailile globaalmuutujana. (See ei ole hea lahendus, kuid aktsepteeritav – parem võimalus on kirjutatud lahti edasijõudnute ülesandena).
• Näiteks võiks logimise väljakutsumine välja näha nii:
  Logger("Program started");

Edasijõudnute ülesanne 1: Logimise teek

Selle ülesande raames lood sa endale logimise teegi. Vihje: seda saad ära kasutada kodutöö 2 juures!

Nõuded

• Lisa programmile eraldi .c ja .h fail ja tõsta sinna logimine
• Lisa 4 logimise taset – OFF, ERROR, WARNING ja INFO – need on loendi tüüpi (enum).
  • Iga logifaili rea juures on kirjeldatud selle logi tase.
  • Logi kirjutatakse faili vaid siis, kui määratud tase seda lubab. Näiteks:
    INFO taseme korral kirjutatakse kõigi tasemete logid;
    WARNING taseme korral kirjutatakse ainult WARNING ja ERROR tasemega logid;
    ERROR taseme korral kirjutatakse ainult ERROR tasemega logid;
    OFF korral logisid ei kirjutata;
• Iga kutse logi kirjutamiseks peab nüüd sisaldama selle logi olulisuse taset (ERROR, WARNING või INFO)
  Näiteks: Logger(LOG_INFO, "Program started");
• Teek peab toetama logi väljundfaili nime andmist
  Näiteks: LoggerSetOutputName("log.txt");
• Teek peab toetama programmi logitaseme sättimist
  Näiteks: LoggerSetLoggingLevel(LOG_INFO);
• Logimise seadistused tuleb hoida logimise teegi sisemiselt. Selleks on logifaili nimi ja logi tase (võid ka lisada täiendavaid). Need hoiusta logi koodifailis globaalmuutujatena.
• Logifaili seadistustel peavad olema vaikeväärtused – näiteks kui kasutaja unustab või ei soovi neid seadistada, siis programm ei läheks katki.
• Iga logi peab sisaldama kellaaega nii nagu oli kirjeldatud ülesande teises osas.

Edasijõudnute ülesanne 2: Lihtsustatud CSV failist lugemine

Selle edasijõudnute ülesande eesmärgiks on võimaldada mitmest sõnast koosnevaid õppeainete nimesid.

Nõuded

• Kasuta sisendfailina CSV versiooni sisendfailist
• Andmeväljad on üksteisest eraldatud komaga. Andmeväljad ise komasid ei sisalda.

Lahenduskäik

NB! Kasutame lihtsustatud metoodikat CSV lugemiseks. Sellega ei ole võimalik lugeda ükskõik missugust CSV faili! St kui andmeväli võib sisaldada ka komasid, siis seda metoodikat kasutada ei saa!

Kui vajad täielikku CSV tuge, kasuta kas vastavat teeki (nt libcsv) või kirjuta näiteks olekumasina-põhine töötlemine (loed tähemärk-haaval ja otsustad mida teha lähtuvalt loetud tähemärgist ja hetkeolekust olekumasinas)

---

scanf() funktsioonide perekond võimaldab lisaks andmeformaadi kirjeldamisele ka kirjeldada oodatavat sisendit ning lihtsamaid regulaaravaldisi.

Näiteks lugemaks kasutajalt kellaaega, saame kasutada formaati scanf("%d:%d", &hours, &minutes);  – sellisel juhul saab kasutaja sisestada kellaaja formaadiga 14:35 . Muutuja hours  saab väärtuseks 14 ja minutes  väärtuseks 35 . Kui aga kasutaja sisestab 14 35 , siis hours  saab ikka väärtuseks 14 , kuid kuna tühik polnud oodatud formaat, siis sealt edasi ei loeta ning minutes  jääb väärtustamata.

Lähtuvalt sellest teadmisest saame koostada faili lugemiseks formaadi fscanf(fp, "%[^,],%d", ...)  . Asenda failiviida nimi enda kasutatud viidaga ning kolme punkti asemele pane oma muutujad kuhu andmeid salvestad.

• Esimene väli loetakse tekstina kuniks komani (koma ei loeta). See salvestatakse tekstimassiivi (õppeaine nimi)
• Seejärel loetakse puhvrist välja koma (ja visatakse ära)
• Siis loetakse sisse üks täisarv (hinnete arv aines)

Sedasi saad loetud esimesed 2 välja. Edasi pead juba formaadi koostama hinnete lugemiseks (ära komasid unusta!).

Pärast seda tundi peaksid

• Teadma erinevate ehitussüsteemide kohta
• Oskama koostada lihtsat Makefile’i
  • Teadma kuidas deklareerida muutujaid ja neid kasutada
  • Teadma kuidas koostada retsepti, sh mitut retsepti ühes failis
  • Teadma mis retsepti sees käib
  • Teadma varjatud reeglitest ja oskama neid vajadusel kasutada
• Oskama kasutada Makefile’i programmi kompileerimiseks
• Oskama kasutada valgrindi programmist vigade leidmiseks ja korrektsuse kontrollimiseks
• Oskama programmi siseselt hetke kellaaega leida ning seda kujundada
• Teadma logimise põhitõdesid ja olulisust

Täiendav materjal

• Make manual
  https://www.gnu.org/software/make/manual/make.html
• What is a Makefile and how does it work?
  https://opensource.com/article/18/8/what-how-makefile
• Compiling Programs with Make
  https://web.stanford.edu/class/archive/cs/cs107/cs107.1194/resources/make
• Makefile tutor project (näidisprojektid koos Makefile’iga)
  https://github.com/clemedon/Makefile_tutor
• Makefile tutorial
  https://makefiletutorial.com
• VMWare VSphere Logging options (levels)
  https://docs.vmware.com/en/VMware-vSphere/8.0/vsphere-vcenter-configuration/GUID-0439D577-66F7-4584-AF05-5EB41A761873.html
• Logimise teegi näidis (keerukam kui meil vaja)
  https://github.com/rxi/log.c
• strftime() funktsioon
  https://www.cplusplus.com/reference/ctime/strftime/
• Valgrind dokumentatsioon
  https://valgrind.org/docs/manual/index.html
• Teegi tegemise juhend
  http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html
  
• Address Sanitizer dokumentatsioon
  https://github.com/google/sanitizers/wiki/AddressSanitizer

 

Labori materjal

• Slaidid: Qsort
• Slaidid: Koodi tükeldamine
• Näidisprojekt koodi tükeldamisest: https://blue.pri.ee/ttu/files/iax0584/demokood/division_to_files.zip

Laboriülesanded

Selles laboris on kaks ülesannet.

• Esimene ülesanne koosneb kahest baasosast ja edasijõudnute lisast.
• Teine ülesanne koosneb baasülesandest ja edasijõudnute lisast.

Ülesanne 1: Quicksort

Selle ülesande eesmärk on harjutada qsort()  funktsiooni kasutamist ning koodi tükeldamist erinevate koodifailide vahel, sealjuures alustad oma esimese kergesti lisatava teegifaili loomist. Aluskoodis on juba koodi tükeldus failidesse sinu eest juba tehtud.

Lae alla aluskood: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/5_1_qsort_task_basecode.zip

NB! Aluskood sisaldab tükke mõlema baasosa ja edasijõudnute osa jaoks!

Nõuded

• Realiseeri vajalikud funktsioonid mis on ette antud sulle erinevates päisefailides prototüüpidena. Funktsiooni realisatsioon peab olema päisefailiga samanimelises .c koodifailis
• Kutsu välja vajalikud funktsioonid andmete sorteerimiseks ja ekraanile kuvamiseks main funktsiooni switch lausest.
• Kompileeri programm kokku mitmest koodifailist – vastavalt struktuurile mis oli antud aluskoodis. Kasuta kompileerimiseks käsurida (võid kasutada ka Makefile’i kui oskad).

Ülesande hinnatavad alamosad

Esimese hinnatava osa jaoks peavad töötama menüüst valikud 1 ja 2. Selle sooritamiseks pead sa

• Realiseerima qsort võrdlusfunktsioonid täisarvudest ja murdarvudest koosneva massiivi jaoks
• Kutsuma välja qsort funktsiooni mõlema eelnimetatud massiivi sorteerimiseks ning väljatrükiks menüüs

Teise hinnatava osa jaoks peavad töötama menüüst valikud 3 ja 4. Selle sooritamiseks pead sa

• Realiseerima qsort võrdlusfunktsioonid struktuurimassiivi sorteerimiseks eesnime ja töösuhte pikkuse järgi
• Realiseerima struktuurimassiivi väljatrüki funktsiooni.
• Kutsuma välja qsort funktsiooni struktuurimassiivi sorteerimiseks vastavalt menüü valikule ning seejärel massiivi väljatrüki funktsiooni

Edasijõudnute ülesande hinnatava osa jaoks peab töötama menüüst valikud 5. Selle sooritamiseks pead sa

• Realiseerima qsort võrdlusfunktsioonid struktuurimassiivi sorteerimiseks perenime järgi. Kui perenimed on samad, tuleb teha täiendav otsus sorteerimiseks eesnime alusel.
• Kutsuma välja qsort funktsiooni struktuurimassiivi sorteerimiseks vastavalt menüü valikule ning seejärel massiivi väljatrüki funktsiooni
• Kutsuma välja qsort funktsiooni struktuurimassiivi sorteerimiseks vastavalt menüü valikule ning seejärel massiivi väljatrüki funktsiooni

Testimine

Järgnev näide sisaldab kõiki kolme hinnatavat osa (1 ja 2 baasosa ning edasijõudnute osa)

Ülesanne 2: Teekide kasutamine (covid-data)

Selles ülesandes tutvume esimest välise teegi (libcurl) lisamisest oma programmi, mille abil on võimalik näiteks kasutada internetis olevaid APIsid ja faile internetist alla laadida. Kasutame neid Eesti riigi avaandmete alla laadimiseks. Jätkame programmi tükeldamise harjutamisega.

NB! Ülesande lahendamine on kordades lihtsam UNIX põhistel süsteemidel (Nt Linux). Windowsil ülesande lahendamiseks on vaja teha täiendav seadistus ning muuta osa ette antud lähtekoodist!

Lae alla aluskood: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/5_2_covid_starter.zip

Nõuded

• Kasuta põhjana sulle antud aluskoodi
• Lae alla Eesti Covid-19 avaandmed (ette antud aluskoodis)
  NB! Avaandmeid uuendatakse korra nädalas! 
• Avaandmete spetsifikatsioon
  • Eesti keeles: https://opendata.digilugu.ee/docs/#/et/opendata/covid19/test/opendata_covid19_tests_total
  • Inglise keeles: https://opendata.digilugu.ee/docs/#/en/opendata/covid19/test/opendata_covid19_tests_total
• Kuva viimase 14 päeva kinnitatud nakatumised (päev ja nakatumiste arv)
• Kuva top10 kõige suurema nakatumiste arvuga päeva (päev ja nakatunute arv)
• Minimaalselt peab olema kood tükeldatud kolme koodi ja päisefaili
  • file_helper.c  ja file_helper.h  on faili allalaadimiseks ja ettevalmistuseks  (ette antud, muudatusi pole vaja teha)
  • data_processor.c  ja data_processor.h  on failist andmete lugemiseks ja töötlemiseks
  • main.c  ja main.h  on programmi töövoo juhtimiseks ja üldisteks makroteks
  • Soovi korral võid näiteks faili lugemise lüüa lahku andmete töötlemisest
• Kompileeri kõik koodifailid kokku kas käsurealt või kasutades Makefile’i

Soovituslik töövoog

1. Tutvu etteantud koodifaiide struktuuri ja sisuga
2. Kommenteeri sisse enda eelistatud andmefaili formaat (kas tühikute või komadega eraldatud andmed)
3. Kompileeri ja proovi kas allalaadimine töötab. Kompileerimiseks on vajalik lipp -lcurl
4. Lisa main.h  faili struktuuri kirjeldus andmete mälus hoidmiseks ning teised vajalikud makrod suurustele
   Vihje: sul ei ole vaja kõike failist loetut mälus hoida! Vali välja vaid olulised väljad!
5. Kodeeri data_process.c  faili andmefailist andmete lugemise funktsioon. Lisa selle funktsiooni prototüüp data_process.h  päisefaili ning väljakutse main funktsiooni.
   NB! Kas märkasid, et CSV failil oli esimene rida päis!?
   Vihje: konkreetse andmevälja ignoreerimiseks saad scanf  funktsioonis kasutada formaati %*s  – tärn tähistab,  andmeid sellele formaadile vastavale osale ei salvestata. St ignoreeritakse kõike kuni järgmise tühiku või reavahetuseni. Kui kasutad tärni formaadis ei tohi selle kohta muutujat scanf  parameetrina anda.
   Kompileeri ja testi kas andmed loetakse edukalt sisse
6. Loo funktsioon andmete väljatrükiks, et kuvada viimase 14 päeva statistika.
   Vihje: Kasuta ära oma teadmist massiividest ja viida-aritmeetikast mida rakendasime esimesel nädalal viitade tunnis (ülesanne 1, osa 2)! Nii jääb väljatrüki funktsioon lihtsaks ja korduvkasutatavaks järgmise punkti jaoks.
7. Loo qsort  jaoks võrdlusfunktsioon ning kutsu qsort  välja andmete sorteerimiseks. Kuva top 10 kõrgeima nakatunute arvuga päeva.
   Vihje: Kui kasutasid eelmise punkti juures viida-aritmeetika ja jätsid väljatrüki funktsiooni lihtsaks, siis nüüd saad seda sama funktsiooni ka siin ära kasutada!

Testimine

NB! Väljundis on koos baasülesande ja edasijõudnute ülesande lahendused!

Edasijõudnute ülesanne

• Leia nakatumiste arv viimase 7 päeva jooksu
• Leia nakatumiste arv sellele eelneva 7 päeva jooksul
• Väljasta perioodi vahemikud ja nakatunute koguarv neil perioodidel
• Leia ja kuva kas nakatumine kahe võrreldava perioodi vahel on vähenenud, kasvanud või jäänud samaks. Näita protsenti kahe komakohaga.

Vihje: Baasülesande raames sorteerimise andmemassiivi terviklikult ära ja neid andmeid me kasutada ei saa ilma uuesti sorteerimata. Küll aga saame enne sorteerimist teha osalise koopia andmetest. Koopia saad teha (enne kui qsort välja kutsutakse) kasutades funktsiooni memcpy() . Uuri parameetreid ja meenuta viida-aritmeetikat alguspunkti määramiseks!

MS Windows

Antud ülesannet on võimalik lahendada ka Windowsil, kuid selleks tuleb teha mõned täiendavad liigutused. Sammud on testitud ja töötasid kevadel 2022 kasutades chocolatey kaudu installeeritud 64 bitist MinGW-d (see oli osa lihtsast tarkvara paigaldamise juhendist Windowsil kasutades käsurida). Väljavõte eelmise aasta vestlusest, kus sammud kirja said (inglise keeles)

Pärast seda tundi peaksid

• Oskama tükeldada oma programmi mitme koodifaili vahel mitmest koodifailist koosnevat programmi kompileerida
• Oskama kasutada qsort funktsiooni
• Mõistma qsort funktsiooni võrdlusfunktsiooni nõudeid ning suutma kirjutada võrdlusfunktsiooni lihtsatele massiividele ning ka struktuurimassiividele
• Teadma viitade eksisteerimisest funktsioonidele ning oskama funktsiooni edastada viita teisele funktsioonile
• Teadma üldistatult samme mis on vajalikud kolmandate osapoolte teekide kasutamiseks ning oskama neid oma programmi kompileerida

Täiendav materjal

• Sorting algorithms visualized
  https://www.toptal.com/developers/sorting-algorithms
• Big-O cheat sheet
  https://www.bigocheatsheet.com
• Quicksort algorithm
  https://en.wikipedia.org/wiki/Quicksort
• Example structure
  https://github.com/JackWetherell/c-project-structure
• List of common C libraries
  https://github.com/oz123/awesome-c

Labori materjal

• Slaidid: Struktuurid 2 + lihtne päisefail
• Täiendav näide: struktuurimassiiv viitadega (Seotud laboriülesandega)
• Täiendav näide: struktuuri tagastamine
• Täiendav näide: struktuur struktuuris
• Täiendav näide: Struktuuriviit kui struktuuri liige

Laboriülesanded

Selleks laboriks on ülesanne mis on jaotatud kahte ossa.

Laboriülesande 1. osa: Seostatud andmete väljastamine

Selles osas trükime välja failidest loetud andmed. Selleks on oluline õigel hetkel teha vajalikud seostamised kahe struktuuri vahel.

Andmefailid

Andmed on sulle antud kahes eraldi failis, mille kirjeldamiseks kasutame olemi-suhte diagrammi (ERD ehk entity-relationship diagram).

NB! Selliseid suhteid näidatakse sageli ka UMLi klassidiagrammina. Vaata all viidet selle kohta!

Olemi-suhte diagrammi kardinaalsus

• Ühel isikul võib olla 0 või enam sõidukit
• Iga sõiduk peab kuuluma täpselt ühele isikule

Andmed kahes failis on seostatud Eesti isikukoodi (person_id) abil.

Lae andmefailid alla siit: https://blue.pri.ee/ttu/files/iax0584/andmefailid/4_data.zip

Nõuded

• Kasuta programmi programmis päisefaili. Paiguta sinna struktuuride deklaratsioonid, makrod ja funktsioonide prototüübid, vajadusel ka loendid.
• Loe kahest antud failist andmed eraldiseisvatesse struktuurimassiividesse.
  • Väldi keerukaid lahendusi (pesastatud struktuurid või struktuuriviidad) selle laboriülesande lahendamisel.
  • Isikukoodi pead hoiustama 64-bitise täisarvuna. Sedasi vähendad protsessoritsüklite arvu mis kulub väljade võrdlemiseks!
    Use inttypes.h !
• Harjuta viidaaritmeetikat
  • Kasuta nooleoperaatorit (->) struktuuri liikmete poole pöördumiseks
  • Väldi nurksulgude [] kasutamist massiivide indekseerimisel.
• Sorteeri isikute andmed eesnime alusel tähestikulises järjekorras kasvavalt.
• Trüki välja isikuandmed, millele järgnevad kõik nendega seotud sõidukid.
  • Omaniku andmed tohid trükkida ühekordselt.
  • Omaniku info järel loetle kõik nendega seotud sõidukid
  • Kui isikul puuduvad sõidukid, anna sellekohane teavitus.

Soovituslikud funktsioonid

NB! Tegu on soovitusliku loeteluga. Sinu loodavad funktsioonid ning nende parameetrid võivad sellest erineda.

Testimine

Järgnev on ülesande esimese osa oodatav väljund

Laboriülesande 2. osa: Maksude arvutamine

Teises osas kirjutame laienduse esimesele osale. Kõik esimeses osas olnud nõuded kehtivad ka siin.

Nõuded

• Leia ja kuva palju iga omanik makse maksma peab
  • Kuvada tuleb nii summa kui protsendina sissetulekust
  • Lisa hoiatus kui maksud ületavad 10% isiku aastasest sissetulekust.
  • Väljasta veateade kui inimesel puuduvad sissetuleku kohta andmed.
  • NB! Meenuta, et funktsioonid peaksid vaid ühte asja tegema. Ära pane arvutamist samase funktsiooni kus andmeid väljastad või faile loed! Tee eraldi funktsioon maksude leidmiseks.
• Vihje: Lisa struktuuri täiendav liige või liikmed, et saaksid hoiustada ja kuvada maksuandmeid. Struktuuri liikmed ei pea olema 1:1 vastavuses sellega mis on hoiustatud failis, täiendavate väljade lisamine või isegi andmete töötlemine ja teises formaadis hoidmine mälus on OK.

Soovituslikud funktsioonid

NB! Tegu on soovitusliku loeteluga. Sinu loodavad funktsioonid ning nende parameetrid võivad sellest erineda.

Testimine

Järgnev on ülesande teise osa oodatav väljund

Pärast seda tundi peaksid

• Oskama luua ja seostada päisefaili oma koodifailiga
• Teadma mida pannakse ja mida ei panda päisefaili sisse
• Teadma tüüpilisi kasutusjuhte päisefailidesse
• Teadma erinevaid mis vahet on noolsulgudel ja ümarsulgudel päisefaili lisamisel ning kust siis neid faile otsima hakatakse
• Teadma kuidas makrotena luua tingimuslauseid eelprotsessori jaoks
• Teadma miks on vajalikud ning oskama kasutada kaitseid päisefailidel
• Oskama silumislauseid koodi põimida erinevatel viisidel
• Oskama algväärtustada struktuure
• Oskama struktuure pesastada (st ühe struktuuri liikmeks on teine struktuur või struktuuri viit)
• Oskama struktuure tagastada
• Oskama kasutada struktuuri ligipääsuoperaatorina noolt ning teadma millal seda teha tuleb
• Oskama viidaaritmeetikat kasutada struktuurimassiivide peal
• Oskama lugeda lihtsamaid ERD diagramme ja teadma, et neid kasutatakse andmemudelite modelleerimiseks.
• Teadma, et UMLis on ka olemas klassidiagrammid ning klassidiagramme kasutatakse andmemudelite modelleerimiseks.

Täiendav materjal

• C Header Files
  https://www.tutorialspoint.com/cprogramming/c_header_files.htm
• ERD – Entity Relationship Diagram
  https://www.visual-paradigm.com/guide/data-modeling/what-is-entity-relationship-diagram/
• Data models using UML class diagrams (alternative to ERD)
  https://sparxsystems.com/resources/tutorials/uml/datamodel.html
• Cardinality rules in data modelling
  https://en.wikipedia.org/wiki/Cardinality_(data_modeling)

Labori materjal

• Slaidid: struktuurid
• Täiendav koodinäidis: Struktuurimassiivi näide

Laboris lahendatakse kommenteeritult koos läbi failist struktuuridesse lugemise näide. Neile kes ei osale laboris on see avaldatud koodinäitena: Failist struktuurimassiivi lugemise näide

Laboriülesanded

Selles laboris on üks ülesanne, millele lisandub 4 edasijõudnute ülesannet.

Ülesanne: töötajate otsing

Selles programmis matkime töötajate andmebaasi, kust on võimalik filtreerida välja töötajate andmeid vastavalt etteantud otsinguparameetrile.

Andmefail

Lae alla testandmed järgnevalt lingilt: https://blue.pri.ee/ttu/files/iax0584/andmefailid/3_data_short.zip

Andmefail koosneb juhugeneraatoriga loodud andmetest.

Nõuded

• Loe failist ettevõtte töötajate andmed
  • Failis on iga rea kohta üks kirje
  • Iga andmeväli on eraldatud tühikuga. Andmeväljad on ühesõnalised.
  • Andmete struktuur failis
    <eID> <first_name> <last_name> <city>
• Programmis tuleb andmeid hoida struktuuridest koosnevas massiivis.
• Programm peab töötama olukorras kus andmete täpne arv pole teada ning see võib ajas muutuda (näiteks mõni rida lisatakse või kustutatakse).
  • Loo programmile mõistlik limiit ning veendu, et sellest üle ei mindaks!
• Luba programmi kasutajal teostada otsingut linna nime järgi
  • Programm väljastab kõik töötajad, kes sisestatud linnas elavad
  • Näita mitu vastet mitmest leiti (nt [0 / 91])
  • Otsingut peab saama sooritada korduvalt ilma programmist väljumata
  • Baasülesandes väljasta kõik andmed – isikukood, perenimi, eesnimi, linn
• Kasutajal peab olema võimalus programm sulgeda, loo selle jaoks eraldi võimekus (näiteks sisestades kindel käsk)
• Korduv faili lugemine programmi sees ei ole lubatud.
• Struktuuri sisu ei pea olema üks-ühele faili sisuga! Väljade lisamine on kasulik eelkõige lisaülesannete lahendamisel.

Programmi näidisväljund

NB! Programmi väljund on näide lahendusest pärast kõigi nelja edasijõudnute ülesande lahendamist!

Edasijõudnute ülesanne 1: struktuuride sorteerimine

Nõuded:

• Leitud töötajate loetelu peab olema sorteeritud perekonnanime järgi tähestikulises järjekorras kasvavalt.
• Väljastuse nime formaat peab olema perenimi, eesnimi

Edasijõudnute ülesanne 2: linnade nimistu

Nõuded:

• Kuva kasutajale kõik failis olevad linnad
• Linnade nimekiri koostatakse programmi poolt töö ajal, vastavalt sisendfailis esinevatele linna nimedele
• Kasutaja peab saama linnade nimekirja kuvada sisestades selleks vastava käsu. Käsk tuleb lisada menüüsse
• Linnade nimekirja peab saama kuvada korduvalt
• Linnade nimekirja tohib koostada programmi töö vältel vaid ühe korra.

Edasijõudnute ülesanne 3:  Mugavam otsing

Nõuded

• Otsing ei tohi olla tõstutundlik. Näiteks otsides otsides linna TALLINN  või tallinn , tuleb kuvada kõik töötajad, kes elavad Tallinnas.
• Otsing peab toetama osalist vastet. Näiteks otsides all  leitakse nii need, kes elavad Kallastel, kui ka need, kes elavad Tallinnas.
• Mõlemad peavad töötama ka korraga. St eelnev tulemus peab olema leitav ka otsides ALL  või aLL

Edasijõudnute ülesanne 4: Töödeldud isikukood

Nõuded

• Ära kuva vastuste hulgas enam isikukoodi
• Kuva töötaja sünniaeg formaadiga d. MMMM yyyy

Isikukoodi formaadi kohta saad lugeda: https://www.riigiteataja.ee/akt/114022017005

Pärast seda tundi peaksid

• Teadma kuidas deklareerida uusi struktuure – st uus andmetüüp, milleks on struktuur
• Oskama valida struktuuri liikmeid
• Teadma mis on struktuuri polsterdamine ja joondamine ning kuidas see mõjutab struktuuri suurust mälus
• Teadma mis mõjutab struktuuri suurust
• Teadma millised operaatorid on kasutusel struktuuri liikmete poole pöördumiseks ja oskama kasutama punkt-operaatorit
• Teadma kuidas luua struktuuridest koosnevat massiivi ja lugeda andmeid failist struktuurimassiivi
• Teadma kuidas omistada terviklikku struktuuri
• Teadma kuidas defineerida andmetüüpe ümber, andes neile uue nime (typedef)

Täiendav materjal

• Structures in C
  https://www.geeksforgeeks.org/structures-c/
• Structure Member Alignment, Padding and Data Packing
  https://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/
• Typedef in C
  https://www.geeksforgeeks.org/typedef-in-c/
• Why to avoid typedefs with structs (by Linus Torvalds, author of Linux Kernel and Git)
  https://yarchive.net/comp/linux/typedefs.html
• Structure padding in C
  https://www.scaler.com/topics/structure-padding-in-c/
• C structures
  https://www.tutorialspoint.com/cprogramming/c_structures.htm
• Comprehensive list of date and time formats used in .Net.
  https://learn.microsoft.com/en-us/dotnet/standard/base-types/custom-date-and-time-format-strings