Your task is to create a program that analyzes written text (i.e. books in public domain) and compares it to a dictionary containing correctly written words.
Generic requirements
Program must be written in either C90, C99, C11 or C17 standard. On agreement, you can also use C23. When electing for a newer version of the standard than C99, you should also be using the features of the newer standard.
You are permitted to use GCC extensions, C POSIX and GNU C. You are free to make your case for additional libraries, but they must be agreed upon before use.
The program must compile under either
Ubuntu 24.04 with GCC-13 (based on the recommended software)
OpenSUSE Linux 15 SP5 with GCC-12 (lab configuration)
Solution must be divided into source and header files as appropriate
You are expected to provide a Makefile to compile the solution with a
make all recipe, that compiles the entire solution from scratch
The code is expected to conform to practices widely accepted for C programs, including style, code division, commenting etc.
You are allowed to minimally use global variables where appropriate, but they must be limited to file scope and not harm code reuse practices (e.g. keeping a global struct of settings for logging). This does NOT include a pointer to your data structure to skip on passing data to functions.
The user experience for the program must be clear.
Any errors that occur must be described to the user in a clear manner. The program is not allowed to “just close” without informing the user what happened.
Successful operations must also be confirmed (E.g. successfully read dictionary containing 120 391 words)
The length of the dictionary file must not cause significant impacts on the performance of the application
Ideally the size of the dictionary should not affect searching at all and can only minimally affect loading and unloading the application.
Thus, You are recommended to implement a Trie data structure, however you can also look for alternative faster data structures and algorithms. There are faster alternatives out there.
Program must manage its memory dynamically
Do not implement any arbitrary length for word length or number of words
The program must not excessively over-allocate memory. Memory usage should be either exactly as needed or close to what’s needed.
Memory must be deallocated before exit. Deallocation will be checked using
valgrind . 0 bytes in use is expected at exit.
You are expected to create and use a custom
enum type. If You are not able to find a suitable use case for creating a new type within the specified task requirements, you will need to add a feature to the task of your own choosing. Some ideas for that might work:
Logging that uses logging levels (info, warning, error)
…
Task requirements
The program must offer a basic interactive experience to perform tasks (e.g. a menu or step-by-step input prompts).
The program can also offer command line options, if the author so chooses, but it’s not a requirement. If command line arguments are used, the entered arguments should skip the relevant prompts and be documented in the readme.
Program must provide the following features
Read a dictionary (reference list of correctly written words)
Analyze a plain text document (book, short story, paragraph of text)
Provide analysis reports of the text document
User must be able to choose both the names of the dictionary and (/or) the text document to analyze
The user must be able to get the following reports (depending on their selection)
The list of words in the document in alphabetical order. Output must include both the word and number of occurrences in the text.
The list of unrecognized words (not present in the dictionary), ordered by the number of times they were used in the document.
The result will be written into a text file that is formatted as a CSV file with a header row. The name of the results file must contain a timestamp when the result file was created and must be stored in an appropriate subdirectory of the program
Data
Your programs are expected to work with ASCII-encoded text files, however you are free to test and play around with other encodings, such as UTF-8 or UTF-16.
Dictionary files are plain-text files where each word is on a separate line.
Documents are plain-text files that contain written sentences that can formulate a longer story. They may include double empty lines, punctuation marks, upper and lower case words. Words containing numbers can be ignore (e.g. 1st, 6th). Words written using different capitalization must be identified as the same word (e.g. “HELLO!!!!”, “Hello!” and “hello” all contain the same word).
Useful links
Note: The Estonian dictionary and many texts in Gutenberg are provided with UTF-8 encoding. Your program will be tested only using ASCII strings, but they are a good source of realistic data.
The preferred method of submitting is by providing a Private Git repository that contains all the source files, Makefile and data files to test the solution (at least 2 dictionary files and 2 written text files, one of which should be a simpler case to test correctness and one containing large files to test for performance). A README file should describe the project and how to build it, including any other necessary details.
You are also expected to provide some examples (screenshots) with supporting text explanations of your program running in a format of your choosing – e.g. It can be written into the Wiki section, provided as a part of the README.md or a secondary markdown file or included as a pdf in the repository.
It’s preferred to use our department GitLab instance https://gitlab.pld.ttu.ee, accessible using your Uni-ID. Create a private project and add your instructor to the project (handle:
risto.heinsar ).
Once the task is completed, notify your instructor in Mattermost.
NB! If you are not comfortable using Git, you can also provide the solution as a .zip file through Mattermost.
Task extension to homework 3
Note, that this task is also extendable to Homework 3. All the features included in the extension are additive to this task and agreed upon separately, including with a separate agreed upon deadline. This will include adding additional features, as well as implementing a local SQLite database. To extend the task, ask the instructor separately about the requirements.
Selles laboris on kokku kolm ülesannet. Kõigil ülesannetel on antud koodipõhi, mis määrab ära ülesande üldise struktuuri ja annab sulle ettemääratud töövoo. Töövoog on antud samm-sammuliste juhenditena, alguses täpsemalt, lõpupoole üldisemalt.
Ülesandeid 2 ja 3 on võimalik laiendada lisaülesannetega.
Ülesanne 1: Elektri hinna kalkulaator
Antud ülesandes on sinu eest juba kogu programmi loogika valmis tehtud. St kogu
main() funktsiooni sisu on juba valmis ja seda muuta ei ole põhjust.
Tegemata on jäetud aga enda loodavate (user-defined) funktsioonide sisud ning need on vastavalt asendatud kõik tagastama 0 väärtust (selleks, et programm kompileeruks). Sinu ülesandeks täita kõigi funktsioonide deklaratiivne osa (keha) vastavalt funktsioonile eelnevale kommentaarile.
Ülesande lahendamist alusta baaskoodiga tutvumisest. Sinu lahendus peab olema ehitatud ette antud baaskoodile.
Sinu ülesandeks on kirjutada funktsioonide kehad seitsmele funktsioonile. Funktsiooni eesmärk on kirjeldatud selle ees kommentaarina.
main() funktsiooni sisu ja koodi struktuuri muuta ei tohi. Soovitav on vältida ka funktsioonide ja muutujate ümbernimetamist.
Vihjeid ja soovitusi
Alusta tutvumist koodi ülesehitusest. Vaata kus on makrod, kus prototüübid, kus main() ja kus funktsioonid. Vaata kuidas main() funktsioonist teisi funktsioone välja kutsutakse, mis kaasa antakse jne. Ära muuda midagi alguses!
Üldine pilt selge, hakka järjest funktsioonide sisusid täitma. Lahenda 1 funktsioon korraga, kompileeri ja testi enne kui järgmise juurde lähed!
Sisestuse funktsioonides on soovitatav struktuur do while tsükkel, mille sees on if lause veateate väljastamiseks.
Kõik ülejäänud funktsioonid on lahendatavad ühe reaga, asendades olemasoleva
return 0 asemel õige valemi
Ettevaatust ühikutega. Erinevates kohtades on kord kasutusel vatt-tunnid, kord kilovatt-tunnid, kord megavatt-tunnid! Juhindu funktsiooni kommentaaridest.
VAT – value added taxtähendab käibemaksu (Eestis 20%)
Enter the market price for electricity in MWh: 412.65
Market cost of electricity is 412.65 EUR / MWh.
This is 0.4126 EUR per kWh before taxes.
The government takes 0.0825 EUR in taxes.
With taxes, the cost for you is 0.4952 EUR / kWh
Lets do a rough savings estimate when switching from incandescent bulbs to LEDs
Number of E27 lightbulbs in use: 9
Average hours per day the bulbs are turned on for: 6
Results are calculated for a 30-day month.
Using 60 W incandescent bulbs consumes 97200 W, costing 48.13 EUR
Using 9 W LED bulbs consumes 14580 W, costing 7.22 EUR
That's a saving of 40.91 EUR.
At the price of 0.69, you could buy 59 packs of instant noodles with that money!
Test 2: vigadega sisend
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Enter the market price for electricity in MWh: -5
Retry! Must be > 0
> 125
Market cost of electricity is 125.00 EUR / MWh.
This is 0.1250 EUR per kWh before taxes.
The government takes 0.0250 EUR in taxes.
With taxes, the cost for you is 0.1500 EUR / kWh
Lets do a rough savings estimate when switching from incandescent bulbs to LEDs
Number of E27 lightbulbs in use: -1
Retry! Must be > 0
> -3
Retry! Must be > 0
> -5
Retry! Must be > 0
> 8
Average hours per day the bulbs are turned on for: 7
Results are calculated for a 30-day month.
Using 60 W incandescent bulbs consumes 100800 W, costing 15.12 EUR
Using 9 W LED bulbs consumes 15120 W, costing 2.27 EUR
That's a saving of 12.85 EUR.
At the price of 0.69, you could buy 18 packs of instant noodles with that money!
Ülesanne 2: Arvujadade generaator
Selle ülesande raames tuleb koostada programm, mis sisaldab endas kahte arvujada generaatorit, aritmeetilise ja geomeetrilise jada genereerimiseks. Ülesannet laiendab lisaülesanne, mille raames lisatakse algarvude generaator ja muudetakse programmi väljundit kenamaks.
Funktsioonide lahendamisel juhindu funktsiooni kommentaarist ja siin lehel olevast samm-sammulisest juhendist.
Programm peab suutma genereerida aritmeetilist ja geomeetrilist jada vastavalt etteantud sisenditele.
Kasutaja peab saama valida kumba generaatorit kasutada ning sisestada sellele parameetrid (algväärtus, vahe või tegur ja sammude arv).
Jada algväärtus, geomeetrilise jada tegur ja aritmeetilise jada tegur sisestatakse kümnendmurruna.
Jada liikmed kuva kahe komakohaga.
Samm-sammuline juhend
Kompileeri aluskood. Proovi seda, vaata mis ta teeb. Loe kood läbi.
Lisa
main() funktsiooni väljakutse funktsioonile
PrintMenu() . Väljakutse asukoht on märgistatud TODO kommentaarina. Kirjuta väljakutse kommentaarist järgmisele reale. Proovi – kui töötab, kustuta TODO kommentaar ära. KOMPILEERI JA TESTI, ET TEHTU TÖÖTAB ENNE EDASI LIIKUMIST!
Kirjuta funktsiooni
PrintSeparator() sisu. Selleks pead kirjutama tsükli, mis trükib
# sümbolit täpselt nii mitu korda kui oli ette antud funktsiooni parameetriga. KOMPILEERI JA TESTI, ET TEHTU TÖÖTAB ENNE EDASI LIIKUMIST!
Lõpeta funktsioon
PrintAsciiWelcomeMsg() , pannes see väljastama endale meelpärast ASCII kunsti (pilt, tekst, …). Võid näiteks kasutada ka pildi teisendajaid ASCII kunstiks või kasutada mõnda teost internetis olevatest galeriidest. KOMPILEERI JA TESTI, ET TEHTU TÖÖTAB ENNE EDASI LIIKUMIST! Vihje: Internetis on mitmeid ASCII galeriisid ja teisendajaid. Üks nest on kättesaadav siit: https://www.asciiart.eu NB!Osad tähemärgid omavad erilist tähendust ja neid ei saa niisama lihtsalt ekraanile manada. Sellisteks on näiteks
\ (escape sequence) ja
% (formaat ehk format specifiers). Nende väljastamiseks peame
\ asemel kirjutama
\\ ja
% asemel
%%. Kõige lihtsam viis (kui selliseid sümboleid on palju) on teha Geanys uus fail, panna oma kunstiteos sinna ja kasutada kogu dokumendi ulatuses asendust (kiirklahv ctrl+h avab menüü, valik replace all in document).
Nüüd mine
ArithmeticSequence() funktsiooni juurde.
Deklareeri puuduvad muutujad (3 tk kokku, ettevaatust andmetüüpidega!)
Lisa kasutajale päringud ja loe väärtused loodud muutujatesse.
Lisa funktsiooni
ArithmeticSequenceGenerator() väljakutse koos vajaminevate parameetritega. NB! Märka, et funktsioon
ArithmeticSequenceGenerator() on koodist välja kommenteeritud! Seda tegime selleks, et vähendada liigseid kompilaatori hoiatusi mis võivad summutada muud olulised hoiatused ja veateated sinu jaoks. Kuniks sa seda funktsiooni sisse ei kommenteeri, annab kompilaator sulle “undefined reference” veateate ja programm ei kompileeru. Kommenteeri see funktsioon sisse, et saaksid testimise läbi viia (hetkel veel tulemusteta)! KOMPILEERI JA TESTI, ET TEHTU TÖÖTAB ENNE EDASI LIIKUMIST!
Liigu edasi funktsiooni
ArithmeticSequenceGenerator() juurde ja lõpeta see. Sul on vaja kirjutada üks tsükkel, mille sisse tuleb paigutada 2 lauset
Väljasta praeguse jada liikme väärtus.
Arvuta järgmise jada liikme väärtus.
NB! Järjekord on oluline!
Vihje 1:
järgmine_väärtus = praegune_väärtus + vahe
Vihje 2: Sul ei ole tegelikult vaja siin funktsioonis ühtegi uut muutujat deklareerida peale tsükliloenduri. . Kindlast väldi massiivide kasutamist (teema järgnevateks nädalateks). KOMPILEERI JA TESTI, ET TEHTU TÖÖTAB ENNE EDASI LIIKUMIST!
Menüüs, mis on realiseeritud
switch () lausena, on valmis kirjutatud vaid üks
case . Lisa veel 2 puuduolevat menüü valikut ja nendele vajaminevad laused. Vajaminevad käsud on kirjeldatud menüüs (
PrintMenu() funktsioonis)
Samal viisil nagu lahendasid aritmeetilise jada genereerimise funktsioonid tuleb nüüd lahendada ka geomeetrilise jada genereerimiseks vajaminevad funktsioonid.
Nüüd peaks ülesanne lahendatud olema. võrdle oma väljundit etteantud testjuhtudega!
Testimine
Testi kindlasti kõiki kolme menüü valikut ning ka tundmatut sisendit!
Soovitus: Enne ülesande lahendamist loe läbi ja mõtesta enda jaoks lahti etteantud algoritm (pärast nõudeid)! Kui tekib segadus, soovitan piiluda sisse lähenemise peatükki.
Nõuded
Tööpäeva algus on määratud makrona
Kasutaja sisestab klientide arvu ning ühe kliendikohtumise kestvuse
Programm genereerib kliendikohtumiste kellaajad. Ajad on järjestikused.
Minimaalselt peavad olema realiseeritud ja kasutatud aluskoodis antud funktsioonid. Funktsioone võid juurde luua.
Genereeritud ajad peavad olema reaalsed
Väljund peab olema visuaalselt joondus
Aluskoodis on kõigi funktsioonide kohta on antud vaid nende nimed. Sa pead määrama nende tagastatava andmetüübi ja parameetrid. Kui parameetrid puuduvad, siis tuleb sulgudesse kirjutada
void .
Algoritm
Lähenemine
Sel korral on lähtekood juba üsna õhuke, kuid sisaldab siiski struktuuri kuidas oleks mõistlik see programm funktsioonideks tükeldada.
Iga funktsiooni puhul mida lahendad, alusta selle tagastuse andmetüübi ja parameetrite loetelu määramisest. Need on sulle ette antud funktsiooni kommentaarina. Kui see on tehtud, lisa funktsiooni prototüüp enne main() funktsiooni. Seejärel kirjuta funktsiooni kena ning lisa funktsiooni väljakutse sobilikku kohta.
Ava mind vihjete nägemiseks
Esmalt alusta asjadest, mis on juba koodis kasutusel ja/või poolikult realiseeritud. Sellisteks funktsioonideks on
PrintTime() ja
PrintTimeInterval() . Need peaksid olema üsna lihtsad realiseerida ja saad mõned häirivad hoiatused eest ära.
Nüüd realiseeri
GetPositiveInt() funktsioon. Selle funktsiooni oled juba eelnevate tunnitööde raames teinud. Määra tagastuse tüüp ja funktsiooni parameetrid ning kopeeri eelnevast ülesandest kood sisse. Seejärel saad funktsiooni kasutada nii klientide arvu kui kliendikohtumise kestvuse lugemiseks.
Järgmisena tuleks alustada tööd funktsiooni
PrintTimetable() kallal. Kutsu see funktsioon
main() -ist välja. Funktsiooni sisse loo tsükkel klientide ja nende kellaaegade väljastamiseks. Ära kellaaegade peale veel mõtle, veendu lihtsalt, et kliendide loetelu kuvataks korrektselt.
Kellaaegade saamiseks tuleb lahendada funktsioonid
CalcNextHour() ja
CalcNextMin() . Mõlemad funktsioonid on lahendatavad ühe reaga, pead vaid vaid piisavalt täpse matemaatilise tehte välja mõtlema ja tulemuse tagastama.
Vihje: Sa saad nende funktsioonide töötamist testida ka eraldiseisvalt ülejäänud koodist. Näiteks kutsudes funktsioon välja CalcNextHour(8, 0, 50) peab tagastatavaks väärtuseks olema 8 ning
CalcNextHour(8, 0, 70) puhul 9. Sarnaselt peab teise funktsiooni korral
CalcNextmin(8, 0, 50) tagastama 50 ja
CalcNextmin(8, 0, 70) korral 10.
Nüüd mine tagasi funktsiooni
PrintTimetable() ja hakka sinna kirjutatud tsüklit sisustama. Vaata kindlasti algoritmi võrdluseks.
NB! Funktsiooni korrektseks tööks on sul vaja teada nii kohtumise alguskellaaega (märgitud kui hetkeaeg – current time) kui lõpukellaaega. Kui need 4 väärtust on teada, kasuta neid funktsiooni
PrintTimeInterval() väljakutses.
Nüüd on aeg testimiseks ja vajadusel silumiseks. Kõik jupid koodist on valmis. Veendu, et need töötavad ootuspäraselt.
Testimine
Testime vaid minuti ületäitumisega
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>Workday starts at 8:00
Enter num of clients
10
Enter client session length
45
Client 1: 8:00 - 8:45
Client 2: 8:45 - 9:30
Client 3: 9:30 - 10:15
Client 4: 10:15 - 11:00
Client 5: 11:00 - 11:45
Client 6: 11:45 - 12:30
Client 7: 12:30 - 13:15
Client 8: 13:15 - 14:00
Client 9: 14:00 - 14:45
Client 10: 14:45 - 15:30
Testime tundide ületäitumist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Workday starts at 8:00
Enter num of clients
25
Enter client session length
45
Client 1: 8:00 - 8:45
Client 2: 8:45 - 9:30
Client 3: 9:30 - 10:15
Client 4: 10:15 - 11:00
Client 5: 11:00 - 11:45
Client 6: 11:45 - 12:30
Client 7: 12:30 - 13:15
Client 8: 13:15 - 14:00
Client 9: 14:00 - 14:45
Client 10: 14:45 - 15:30
Client 11: 15:30 - 16:15
Client 12: 16:15 - 17:00
Client 13: 17:00 - 17:45
Client 14: 17:45 - 18:30
Client 15: 18:30 - 19:15
Client 16: 19:15 - 20:00
Client 17: 20:00 - 20:45
Client 18: 20:45 - 21:30
Client 19: 21:30 - 22:15
Client 20: 22:15 - 23:00
Client 21: 23:00 - 23:45
Client 22: 23:45 - 0:30
Client 23: 0:30 - 1:15
Client 24: 1:15 - 2:00
Client 25: 2:00 - 2:45
Testime kõiki ületäitumisi korraga ja mitmekordselt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Using basic version of the task
Workday starts at 8:00
Enter num of clients
8
Enter client session length
145
Client 1: 8:00 - 10:25
Client 2: 10:25 - 12:50
Client 3: 12:50 - 15:15
Client 4: 15:15 - 17:40
Client 5: 17:40 - 20:05
Client 6: 20:05 - 22:30
Client 7: 22:30 - 0:55
Client 8: 0:55 - 3:20
Lisaülesanded
Selles laboris on kaks lisaülesannet, vastavalt teisele ja kolmandale baasülesandele.
Lisaülesanne 1: Algarvude generaator ja rea pikkuse piiramine
Tegu on laiendusega baasülesandele.
Nõuded
Kasuta lahendatud laboriülesannet selle töö põhjaks
Lisa algarvude generaator. Kasuta järgmises punktis etteantud funktsiooni enda lahenduse koostamisel.
Lisa limiit mitu tulemust ühe rea kohta generaatorid kuvavad. Leia enda programmile sobilik limiit. Alternatiivina võid teha programmi kenamaks, piirates hoopiski väljastatavat tähemärkide arvu. Selleks tuleb loendada väljastatavaid tähemärke. Üks võimalikest abistatavatest funktsioonidest võiks olla
snprintf() .
Funktsioon algarvude tuvastamiseks
Kasuta järgnevat funktsiooni testimaks kas tegu on algarvuga või mitte. NB! Märka, et pead lisama enda koodi ka IS_PRIME makro!
* Description: Checks if a number is a prime or not.
*
* Parameters: num - number to test for
*
* Return: IS_PRIME (defined 1) when num is a prime, !IS_PRIME (0)
* if it was not.
*/
intIsPrime(intnum)
{
/* Sanity check to avoid misuse of this function */
if(num<=0)
{
return!IS_PRIME;
}
/* Check divisibility from 2 until 1 below the test value itself */
for(inti=2;i<num;i++)
{
/* If it's divisible, it's not a prime */
if(num%i==0)
{
return!IS_PRIME;
}
}
/* Number is only divisible by itself and 1, so it's a prime */
returnIS_PRIME;
}
Testimine
NB! Märka, et sel korral on näidatud kahte erinevat lahendust. Mõlemad on korrektsed ja aktsepteeritavad lahendused sellele ülesandele. Sa pead näitama neist vaid ühe.
Teine ülesanne on antud inspiratsiooniks kui soovid väheke rohkem pead murda ja teha väljund veelgi kenamaks.
Lisaülesanne 2: Lisa puhkepausid ja mitmele päevale ulatuv planeerimine
Tegu on laiendusega baasülesandele.
Nõuded
Kasuta lahendatud laboriülesannet selle töö põhjaks
Lisa kasutaja poolt seadistatav paus iga kliendikohtumise vahele (nt 10 minutit).
Lisa tööpäeva lõpu kellaaeg. Kui kliendikohtumine ületaks seda aega, siis planeeri kohtumine hoopis järgmisse päeva. Kui kohtumiste plaan osutub mitmepäevaseks, näita iga päeva ees ka päeva numbrit.
Testimine
Näide oodatavast väljundist kui broneering läheb mitmepäevaseks koos pausidega.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Using advanced version of the task
Workday starts at 8:00
Workday ends at 16:00
Enter num of clients
25
Enter client session length
35
Enter break length
10
Day 1
Client 1: 8:00 - 8:35
Client 2: 8:45 - 9:20
Client 3: 9:30 - 10:05
Client 4: 10:15 - 10:50
Client 5: 11:00 - 11:35
Client 6: 11:45 - 12:20
Client 7: 12:30 - 13:05
Client 8: 13:15 - 13:50
Client 9: 14:00 - 14:35
Client 10: 14:45 - 15:20
Day 2
Client 11: 8:00 - 8:35
Client 12: 8:45 - 9:20
Client 13: 9:30 - 10:05
Client 14: 10:15 - 10:50
Client 15: 11:00 - 11:35
Client 16: 11:45 - 12:20
Client 17: 12:30 - 13:05
Client 18: 13:15 - 13:50
Client 19: 14:00 - 14:35
Client 20: 14:45 - 15:20
Day 3
Client 21: 8:00 - 8:35
Client 22: 8:45 - 9:20
Client 23: 9:30 - 10:05
Client 24: 10:15 - 10:50
Client 25: 11:00 - 11:35
Pärased tundi peaksid
Teadma lihtsamaid polsterdamise ja joondamise võimalusi
Täisarvude polsterdamine nullide või tühikutega
Kümnendmurdude polsterdamine
Sõnede polsterdamine ja joondamine
Liigpikkade sõnelõppude ära lõikamine
Teadma mis erinevus on lokaal- ja globaalmuutujal
Teadma mis on funktsioon ja mis on nende olulisus programmeerimisel
Saama aru, et tegelikult kasutasime juba esimesest nädalast peale funktsioone.
Mõistma järgmisi mõisteid
Funktsiooni prototüüp
Funktsiooni tagastuse tüüp
Funktsiooni argumendid
Funktsiooni parameetrid
Funktsiooni päis
Funktsiooni keha
Oskama ise koostada funktsioone (kasutaja-defineeritud funktsioonid)
Omama väikest kogust universaalseid funktsioone, mida saad kasutada tulevikus järgnevate programmide koostamisel! See loetelu hakkab iga nädalaga laienema.
Your task is to generate a F1 racing event results. The results will be displayed on the screen with an option to store them to a file.
Generic requirements
Program must be written in either C90, C99 or C11 standard. GNU extensions are permitted. The necessary C standard version must be specified in the header of the code file.
You can only use standard libraries and the GNU extensions.
The program must compile under either
Ubuntu 22.04 with GCC-12 (based on the recommended software)
OpenSUSE Linux 15 SP4 with GCC-11 (lab comfiguration)
All arrays must be created with static sizes
Arrays must be large enough that the program can operate within the specified limitations. Specification is listed under task specifications
Program does not need to work with larger inputs, but also must not crash when those are entered. The decision on how to handle improper input is left to the developer.
If the program uses dynamic memory allocation, all of the best practices regarding it must be followed. All dynamically allocated memory must be freed before exit. Note that dynamic memory is not a part of Programming 1, so it is not necessary to use it.
Program must be divided into functions.
Use of global variables is forbidden
Use of GOTO statements is forbidden
The user experience for the program must be clear. Any errors that occur must be described to the user in a clear manner. The program is not allowed to “just close” without informing the user what happened.
Program flow general description
The program will read the names of the pilots from an input file and pick the participating pilots.
The number of laps will be specified by the user inside of the program by inputting the number..
All lap times are generated as random numbers.
Total time is calculated for each pilot who participated.
Pilots, their lap times and the total time is shown on the screen as a table.
If an output file name was specified as a command line argument, all results are also written to the output file with that name as a CSV file.
Task specific requirements
The program will take either 1 or 2 arguments from the command line
First argument is the number of pilots participating. This argument is mandatory.
Second argument is the name of the output file. This argument is optional. If this argument is given, an output file that name with the name will be created. Results will be stored into that file.
The program must support up to 10 participating pilots. The maximum length for the name name of a participant is 32 characters. The number of laps can range from 5 – 15.
The first n pilots will be chosen to participate in the race, based on the order that they are given in the input file. n is the number of pilots, given from the command line. You must validate that you have enough pilots given in the data file.
Each lap time will be a randomly generated number between 70 and 125 seconds.
Each pilot will have a 3% probability that they have to abandon the race during any lap. If a pilot needs to abandon, they will no longer drive the following laps. The decision (dice roll) will be redone on each lap.
For pilots who abandon the race, a
- symbol will be used for the lap that they stopped on and all the following laps. Previous lap times must be present. The total time for that pilot will be presented as DNF (did not finish).
Data file requirements
Input file
The names of pilots will be read by the program from a file called
pilots.dat. The data file must be in the same directory as the binary fine. Name of the file will be hardcoded into the program.
The data file is formatted as an ASCII text file, containing all pilots with the format
initial.last_name. Names are separated by a space. The number of names can range from 5 – 10.
The program will generate a CSV file. File must contain a header with the column names. As data, you need to include the name, all lap times and total time. The output file will be created in the same directory as the binary file.
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.
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
SELECTlast_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.
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.
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.
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.
Loenda mitu korda nimi esinenud on
Lisa oma struktuuri kirjeldusse loendur – kasuta kas
int või
unsigned andmetüüpi.
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.
Lisa oma loendurile algväärtustamine olukorras kus said teada, et nägid nime esmakordselt (nimi ei ole massiivis).
Lisa oma loenduri väärtuse uuendamine (suurendamine) olukorras, kui nimi oli korduv (juba lisatud andmebaasi).
Muuda oma väljastuse funktsiooni
Muuda väljastust sedasi, et tulemus kirjutataks faili
Väljasta nii nimi kui korduste arv
Väljasta mitu unikaalset nime kokku failist leiti
Lisa andmete vabastamine
Lisa aja mõõtmine
Lisa 2
clock tüüpi muutujat
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)
Arvuta palju aega kulus. Väljasta ajakulu.
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_treec 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.
Uuenda struktuuri kirjeldust. Sul on vaja hoida seal nii sõne kui loendurit, täpselt nagu lineaarse otsingu puhul.
Muuda lugemisfunktsiooni sarnaselt nagu tegid lineaarse otsinguga.
Muuda fscanf() funktsiooni toetamaks failis olevat nelja parameetrit.
Kleebi ees- ja perenimi kokku.
Uuenda lisamise funktsiooni
InsertNode()
Muuda selle parameetrit, et see toetaks lisamisel sõnet (meie puhul siis nimi)
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.
Uuenda uue tipu loomise funktsiooni
CreateNode()
Muuda parameetrit, et sinna saaks edastada nime
Lisa loenduri algväärtustamine
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.
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.
Lisa aja mõõtmine
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.
Lineaarne otsing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Ingrid Purga 14
Angela Leppik 13
Hendri Meier 21
Mihhail Saal 18
Aivar Tiidus 14
Julia Leppik 15
Ingrid Kaasik 18
Marko Lepik 14
Ants Ratas 26
Heimar Tomson 12
Yana Kuningas 10
Aivar Kurg 17
Edgar Johanson 14
Eliise Saks 14
Kristi Saar 18
...
Kahendotsingpuu ja Trie
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Ain Aas 15
Ain Aasa 19
Ain Allik 11
Ain Anvelt 18
Ain Hein 17
Ain Heinsoo 20
Ain Helme 16
Ain Herkel 17
Ain Hunt 13
Ain Ilves 15
Ain Ivanov 12
Ain Jakobson 13
Ain Johanson 16
Ain Kaasik 20
Ain Kalda 9
...
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.
1
2
3
4
5
6
typedefstructnode
{
charch;
intcount;
structnode *chars[ALPHA_LEN];
}trie_t;
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..
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.
1
voidPrintNode(list*pNode);
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.
1
voidPrintList(list*pHead);
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.
Loo ja anna mälu uuele elemendile
Määra ära ID väärtus (järjestikuline suurenev täisarv, kasuta
static märksõna)
Küsi mälu ja kopeeri struktuuri nimi
Väärtusta
pNext viit
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!
Praeguse elemendi aadressist koopia tegemine (seda koopiat kasutame vabastamiseks)
Järgmise elemendi juurde liikumine (
pCurrent = pCurrent->pNext )
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.
==17208== All heap blocks were freed -- no leaks are possible
==17208==
==17208== For lists of detected and suppressed errors, rerun with: -s
==17208== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
1
structnode*FindNodeByName(list*pHead,char*name);
1
structnode*FindNodeByID(list*pHead,intid);
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!
==17678== All heap blocks were freed -- no leaks are possible
==17678==
==17678== For lists of detected and suppressed errors, rerun with: -s
==17678== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
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.
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).
Loo rakendus, mis leiab soovitud Fibonacci arvu. n-indaks fibonacci arvuks on selle kahe eelneva Fibonacci arvu summa ehk siis fibx = fibx – 1 + fibx – 2. Erinevalt eelnevatest rekursioonidest on Fibonacci jadal kaks seetõttu ka 2 baasjuhtu.
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.
1
2
3
4
5
6
7
8
9
10
11
12
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ time ./fib 45
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!.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
voiddebug_stack(stack st)
{
printf("DEBUG\n");
printf("\tStack size: %d\n",st.size);
printf("\tData pointer: %p\n",st.data);
if(st.size!=0&&st.data==NULL)
{
printf("Sanity check failed!\n");
printf("Stack is NULL, but size is not 0\n");
return;
}
if(st.size==0&&st.data!=NULL)
{
printf("Sanity check failed!\n");
printf("Stack data is not NULL, but size is 0\n");
return;
}
printf("\tValues: ");
for(inti=st.size-1;i>=0;i--)
{
printf("%d ",st.data[i]);
}
printf("\n\n");
}
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 A0, A1, … , An – 1 sorted such that A0 ≤ A1≤ … ≤ An – 1 use the following algorithm to find if
K ∈ A
Set lowIndexL to
and highIndex H to
n − 1 .
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 Am < K, set
L to
m + 1 , call recursion again
If Am > K, set
H to
m − 1 , call recursion again
If Am = 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
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.
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:
1
2
3
4
5
6
7
8
typedefstruct
{
intindex;
char*fName;
char*lName;
charcurriculum[LEN_CURRICULUM+1];
floatpoints;
}person;
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.
1
2
voidPrintScholarships(person*pStudents,intn);// Good for base task
voidPrintScholarships(student_wrapper stdWrapper);// Good for advanced task 2
Andmete vabastamise funktsiooni
1
2
3
voidFreeStudentData(person*pStudents,intn);// Good for base task
voidFreeStudentData(person**ppStudents,intn);// Good for base task with defensive programming
voidFreeStudentData(student_wrapper stdWrapper);// Good for advanced task 2
Soovituslikud funktsioonid enda elu lihtsamaks tegemiseks
qsordi võrdlusfunktsioon
1
intComparPersonByPoints(constvoid*a,constvoid*b);
Ühe tudengi andmete printimise funktsioon (kasulik kui prindid tudengi andmeid, kes stipendiumi saab.
1
voidPrintStudent(student*s);
Kaitsva programmeerimisstiili jaoks kulub ära ka slaididel näidatud vabastamisfunktsioon
1
voidFreeMemory(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 :
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Description: Reads data from a file. During reading, a dynamic
* struct array will be created and expanded using realloc()
* Parameters: ppStudentData - Stores the location of the allocated array
* fileName - name of the input file to read
* Return: Number of lines read from the file
*/
intReadData(person**ppStudentData,char*fileName)
{
// Current line counter
intcount=0;
// Main pointer for the allocated array
person*pData=NULL;
// Temporary pointer used for reallocating the array
person*pTemp=NULL;
// TODO: Temporary buffers for reading (all variables you intend to read!)
// Read a record at a time in a loop into buffer(s)
while()
{
// rellocate memory to fit the latest line
// Check allocation was successful
// Make both pointers point at the memory location
// Allocate memory for the struct members fName and lName, check allocation!
// Copy data in from the buffers into the struct array
// Increment number of records successfully read
count++;
}
// Store the allocated array trough the double pointer
*ppStudentData=pData;
// Return the number of lines read
returncount;
}
Teine variant tagastab mälu asukoha ning edastab ridade arvu kasutades viita:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Description: Reads data from a file. During this, a dynamic
* struct array will be created and expanded using realloc()
* Parameters: pLineCount - pointer to store the read line count
* fileName - name of the input file to read
* Return: Pointer to the allocated data array
*/
person*ReadData(int*pLineCount,char*fileName)
{
// Current line counter
intcount=0;
// Main pointer for the allocated array
person*pData=NULL;
// Temporary pointer used for reallocating the array
person*pTemp=NULL;
// TODO: Temporary buffers for reading (all variables you intend to read!)
// Read a record at a time in a loop into buffer(s)
while()
{
// rellocate memory to fit the latest line
// Check allocation was successful
// Make both pointers point at the memory location
// Allocate memory for the struct members fName and lName, check allocation!
// Copy data in from the buffers into the struct array
// Increment number of records successfully read
count++;
}
// Store the number of lines trough the pointer
*pLineCount=count;
// Return the pointer to the data
returnpData;
}
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.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Description: Read data from a file. During this, a dynamic
* struct array will be created and expanded using realloc()
* Parameters: ppStudentData - Stores the location of the allocated array
* pLineCount - pointer to store the read line count
==14397== All heap blocks were freed -- no leaks are possible
==14397==
==14397== For lists of detected and suppressed errors, rerun with: -s
==14397== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
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
1
2
3
4
5
6
7
8
9
10
voidPrintData(student_wrapper stdWrap)
{
intlen=stdWrap.used;
for(inti=0;i<len;i++)
{
student*s=&stdWrap.studentDB[i];
}
}
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
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.
Teisel juhul loome lisaviidad, mis võtavad täiendavalt mälu, kuid lihtsustavad koodi loetavust.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
intComparCandidate(constvoid*a,constvoid*b)
{
// Temporary cast pointers for readability
candidate*pA=(candidate*)a;
candidate*pB=(candidate*)b;
// Get comparison for last names
intret=strcmp(a->lName,b->lName);
// When last names match, return difference by first name
if(ret==0)
returnstrcmp(a->fName,b->fName);
// return difference by last name
returnret;
}
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!
==12389== All heap blocks were freed -- no leaks are possible
==12389==
==12389== For lists of detected and suppressed errors, rerun with: -s
==12389== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Vaadates väljundfaili näeme, et tulemused on kenasti sorteeritud (näites vaid esimesed 15 rida)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 Aas Heidy IACB 27.9
1 Aas Juhan IACB 29.6
2 Aas Reet IACB 18.2
3 Aasa Anne EARB 10.1
4 Aasa Julia MVEB 13.8
5 Aasa Sven EARB 14.5
6 Aasa Taavi MVEB 16.1
7 Aasa Urve EARB 29.4
8 Aasa Valdo IACB 21.2
9 Allik Ivari IACB 21.3
10 Allik Kerttu MVEB 29.8
11 Allik Kerttu MVEB 21.4
12 Allik Laivi MVEB 24.2
13 Allik Peeter IACB 22.3
14 Allik Rainer IACB 17.5
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.
Selles laboris on üks ülesanne, mis on jagatud kahte ossa. Ülesannet laiendab kaks lisaü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.
Arhiiv sisaldab andmefaile nii baasülesandeks kui lisaülesandeks!
Ülesande osa 1 / 2 [W06-1]: 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.
1
2
3
4
5
6
7
8
9
.
├── data
│ ├── data_grades.csv
│ └── data_grades.txt
├── analyzer.c
├── analyzer.h
├── Makefile
├── subjects_processor.c
├── subjects_processor.h
NB! Järgnevas näites ei ole kajastatud valgrindi väljundit! Ära unusta testida oma programmi korrektsust valgrindiga!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Subject: Programming
Grades: 4 5 5 4 2 5 1 4 2 5
Average: 3.70
Subject: Databases
Grades: 5 3 3 4 4 3
Average: 3.67
Subject: Mechatronics
Grades: 3 3 4 4 5 0
Average: 3.17
Subject: Physics
Grades: 5 5 3 3 2 3 4 5 1 1 2 4
Average: 3.17
Subject: Ethics
Grades: 5 5 5 4 5 3
Average: 4.50
Subject: Scientology
Grades: N/A
Average: N/A
Subject: Chemistry
Grades: 4 4 3 4 5 4 5
Average: 4.14
Ülesande osa 2 / 2 [W06-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
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 lisaülesandena).
Näiteks võiks logimise väljakutsumine välja näha nii: Logger("Program started");
Lisaülesanne 1 [W06-3]: 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.
Käesoleva lisaülesande eesmärgiks on toetada mitmest sõnast koosnevaid õppeainete nimesid. Selleks on vaja toetada välja sees paikevat tühikut.
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
