Ahelloendi tunniülesanne

[Lae alla baaskood]

[slaidid]

Struktuuri kirjeldus:

struktuuri ühe lüli sees on ühe inimese nimi, temaga seotud kood (ei pea olema unikaalne) ning viit järgmisele sama tüüpi struktuurile.

Juure ehk alguspunkti jaoks võid kasutada deklaratsiooni

Tunnitöö: Realiseerida järgmised funktsioonid

NB! Järgmiste funktsioonide prototüübid on soovituslikud. Soovi korral võid neid muuta veidi, kuid funktsioonid oma eesmärgiga peavad säiluma. Näiteks võid kokku kirjutada createNode() ja insertNode() funktsioonid või valides lihtsama ülesande kasutada topeltviida asemel ühekordset viita.

Kõige mõistlikum on järgnevaid funktsioone realiseerida samas järjekorras nagu nad on antud dokumendis kirja pandud.


 

See funktsioon on tehtud sinu eest. Kuna aga see sõltub funktsioonist PrintNode(), siis on see baaskoodis välja kommenteeritud. 

Trükib välja kõik ahelloendi elemendid. Soovitavalt kasuta PrintNode() funktsiooni konkreetse elemendi kuvamiseks, et tagada modulaarsem lähenemine.

Kindlasti kontrollida ega pHead pole NULL-viit. Sedasi väldid olukorda, kus tühja loendit üritatakse välja trükkida.


 

Parameetrina antakse kaasa ühe lüli aadress. Soovituslik kasutada funktsioonide InsertNode(), FindNode(), PrintList() ja RemoveNode() koosseisus. Sedasi säästad ka aega kui on vaja lisada struktuuri andmeid – muudatusi pead tegema ainult ühes kohas väljatrüki korrektsuse tagamiseks.

Soovitav kontrollida, ega parameetrina kaasa antav lüli pole NULL-viit, et vältida kokkujooksu juhul, kui mõnes väljakutsuvas funktsioonis peaks viga olema.


 

 

Funktsioon loob uue lüli (node’i). Tagastuseks on uue loodud lüli aadress.  Loomise käigus küsitakse kasutajalt sisestust, eraldatakse mälu vajalikus koguses ning tehakse veakontrollid.

Kui see ebaõnnestub (nt pole piisavalt mälu), tagastatakse NULL-pointer.


 

 

NB! Järgnevast funktsioonist on baasversiooni ja edasijõudnute versiooni prototüüp.

Funktsioon lisab loodava lüli loendisse. Lüli loomiseks kutsutakse esmalt välja funktsioon CreateNode(), mis tagastab loodava lüli aadressi. Seejärel paigutatakse loodav lüli loendisse (seatakse paika viidad). Enne loendisse lisamist kontrolli, et CreateNode() ei tagastanud NULL-viita (st uue lüli loomine õnnestus).

NB! Kui CreateNode() poolt tagastatav väärtus oli NULL, siis ära välja programmist, vaid jätka tööd.

Asukoha loendis määrab ära valitud raskusaste (vt kergem ja raskem variant). Kergemat varianti lahendades võid kasutada ka antud funktsioonil järgnevat kuju:


 

 

Funktsioon kustutab kõik ahelloendis olevad elemendid mälust. Eemaldada tuleb ka kõik alamväljadele antud mälu. Veendu tulemuses valgrindi abil.


 

 

Otsingufunktsioonid vastavalt kas võtme või ID numbri järgi. Funktsioonid tagastavad viida leitud lülile. NULL-viit tagastatakse juhul, kui viita ei leita.

Soovitus: kasuta tagastatud viita PrintNode() funktsioonis, et leitud tulemus välja trükkida.

Edasijõudnutele:

Realiseerida järgmised funktsioonid:

void RemoveNodeByKey(list **pHead, char *key);

Loendist otsitakse võtme (nime) järgi lüli, mida eemaldada. Lüli leidmisel eemaldatakse mälust kõik antud lüli alamväljad ning seejärel lüli ise. Eemaldamise protsessi käigus tuleb jälgida listi terviklikkuse säilimist – st nt listi keskelt eemaldades tuleb otsad omavahel siduda viitadega ning ei tohi lõppu ära kaotada. Samuti tuleb arvestada erijuhte, kui lüli peaks olema loendi esimene või viimane element.

Sama nagu eelmine aga otsing toimub id alusel.

 

 

Kergem variant (1.5p)

Kergema variandi puhul luuakse loend sorteerimata kujul.

Funktsioon InsertNode() lisab uusi lülisid ainult loendi algusesse ja seega on võimalik prototüüpi ning elemendi lisamist oluliselt lihtsamalt teostada.

 

 Keerukam variant (2.5p)

Keerulisemas variandis saavutatakse nimekiri, mis on alati tähestikulises järjekorras sorteeritud.

Funktsioon InsertNode() otsib esmalt kuhu kohta olemasolevas loendis tuleb uus lüli lisada ning seejärel lähtuvalt kas tegu on esimese, keskmise või viimase elemendiga, seab viidad paika.

Funktsioonides InsertNode(), RemoveNode() ja FindNode() puhul arvesta sellega, et loend on sorteeritud tähestiku järjekorras ning tee vastavad optimeeringud.