PR2ET12: Ahelloend

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.

void PrintNode(list *pNode);

1	void PrintNode(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.

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
ID: 2
Name: Maamees Jaanes
pNext: (nil)

Error! Node not found!

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

ID: 2

Name: Maamees Jaanes

pNext: (nil)

Error! Node not found!

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.

void PrintList(list *pHead);

1	void PrintList(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!

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: 0x7ffe9d745100

ID: 1
Name: Linnud Tõnisted
pNext: 0x7ffe9d7450e0

ID: 2
Name: Maamees Jaanes
pNext: (nil)

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: 0x7ffe9d745100

ID: 1

Name: Linnud Tõnisted

pNext: 0x7ffe9d7450e0

ID: 2

Name: Maamees Jaanes

pNext: (nil)

struct node *CreateNode(char *name);

1	struct node CreateNode(char name);

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!

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: 0x55b81e0f92f0

ID: 1
Name: Linnud Tõnisted
pNext: 0x55b81e0f9330

ID: 2
Name: Maamees Jaanes
pNext: (nil)

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: 0x55b81e0f92f0

ID: 1

Name: Linnud Tõnisted

pNext: 0x55b81e0f9330

ID: 2

Name: Maamees Jaanes

pNext: (nil)

void InsertNode(list **ppHead, struct node *pNode);

1	void InsertNode(list *ppHead, struct node pNode);

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.

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: 0x55b81e0f92f0

ID: 1
Name: Linnud Tõnisted
pNext: 0x55b81e0f9330

ID: 2
Name: Maamees Jaanes
pNext: (nil)

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: 0x55b81e0f92f0

ID: 1

Name: Linnud Tõnisted

pNext: 0x55b81e0f9330

ID: 2

Name: Maamees Jaanes

pNext: (nil)

void Unload(list *pHead);

1	void Unload(list *pHead);

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.

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ valgrind ./ll_basecode
==17208== Memcheck, a memory error detector
==17208== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17208== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==17208== Command: ./ll_basecode
==17208==
==17208==
==17208== HEAP SUMMARY:
==17208==     in use at exit: 0 bytes in 0 blocks
==17208==   total heap usage: 6 allocs, 6 frees, 135 bytes allocated
==17208==
==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)

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ valgrind ./ll_basecode

==17208== Memcheck, a memory error detector

==17208== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info

==17208== Command: ./ll_basecode

==17208==

==17208== HEAP SUMMARY:

==17208== in use at exit: 0 bytes in 0 blocks

==17208== total heap usage: 6 allocs, 6 frees, 135 bytes allocated

==17208==

==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)

struct node *FindNodeByName(list *pHead, char *name);

1	struct node FindNodeByName(list pHead, char *name);

struct node *FindNodeByID(list *pHead, int id);

1	struct node FindNodeByID(list pHead, int id);

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!

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
ID: 1
Name: Linnud Tõnisted
pNext: 0x5627e3069330

Error! Node not passed!

ID: 2
Name: Maamees Jaanes
pNext: (nil)

Error! Node not passed!

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

ID: 1

Name: Linnud Tõnisted

pNext: 0x5627e3069330

Error! Node not passed!

ID: 2

Name: Maamees Jaanes

pNext: (nil)

Error! Node not passed!

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.

Kliki mind, et näha väljundit

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode
de
==17678== Memcheck, a memory error detector
==17678== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17678== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==17678== Command: ./ll_basecode
==17678==

Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 1

List empty

Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 2

Enter a name:
Kivipallur Jürto Nii-Dommzonn

Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 2

Enter a name:
Linnud Tõnisted

Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 2

Enter a name:
Maamees Jaanes

Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 1

ID: 2
Name: Maamees Jaanes
pNext: 0x4a80980

ID: 1
Name: Linnud Tõnisted
pNext: 0x4a808c0

ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: (nil)


Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 3

Enter ID:
66
Entered ID is not in the list!


Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 3

Enter ID:
0
ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: (nil)


Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 4

Enter a name:
miäu!
Entered name is not in the list!


Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 4

Enter a name:
Kivipallur Jürto Nii-Dommzonn
ID: 0
Name: Kivipallur Jürto Nii-Dommzonn
pNext: (nil)


Make your selection. Press the corresponding number and the enter key
1 - Print list
2 - Insert a node
3 - Find a node by ID
4 - Find a node by name
5 - Erase a node by ID
6 - Erase a node by name
0 - Exit
> 0

==17678==
==17678== HEAP SUMMARY:
==17678==     in use at exit: 0 bytes in 0 blocks
==17678==   total heap usage: 8 allocs, 8 frees, 2,183 bytes allocated
==17678==
==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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

risto@risto-tux:~/Nextcloud/ttu/prog2/wk11_linked_list$ ./ll_basecode

==17678== Memcheck, a memory error detector

==17678== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info

==17678== Command: ./ll_basecode

==17678==

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 1

List empty

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 2

Enter a name:

Kivipallur Jürto Nii-Dommzonn

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 2

Enter a name:

Linnud Tõnisted

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 2

Enter a name:

Maamees Jaanes

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 1

ID: 2

Name: Maamees Jaanes

pNext: 0x4a80980

ID: 1

Name: Linnud Tõnisted

pNext: 0x4a808c0

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: (nil)

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 3

Enter ID:

Entered ID is not in the list!

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 3

Enter ID:

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: (nil)

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 4

Enter a name:

miäu!

Entered name is not in the list!

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 4

Enter a name:

Kivipallur Jürto Nii-Dommzonn

ID: 0

Name: Kivipallur Jürto Nii-Dommzonn

pNext: (nil)

Make your selection. Press the corresponding number and the enter key

1 - Print list

2 - Insert a node

3 - Find a node by ID

4 - Find a node by name

5 - Erase a node by ID

6 - Erase a node by name

0 - Exit

> 0

==17678==

==17678== HEAP SUMMARY:

==17678== in use at exit: 0 bytes in 0 blocks

==17678== total heap usage: 8 allocs, 8 frees, 2,183 bytes allocated

==17678==

==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.

Pesa

PR2ET12: Ahelloend

Labori materjal

Laboriülesanded

Laboriülesanne: Ahelloend

Nõuded

Samm-sammuline juhend

Testimine

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

Nõuded

Märkused

Edasijõudnute ülesanne 2: Elementide eemaldamine

Nõuded

Märkused

Pärast seda tundi peaksid

Täiendav materjal