Eli viitsisikö joku laittaa tänne yksinkertaista linkitetyn listan toteutusta. Oon yrittänyt saada toimivaa kyhättyä mutta ei vain onnistu.
Eli mahd. yksinkertainen jossa olis esim.
struct Alkio
{
int data;
Alkio* next;
}
ja sitte se jatkuu miten?
Eli mahd. yksinkertainen jossa olis esim.
struct Alkio
{
int data;
Alkio* next;
}
ja sitte se jatkuu miten?
Vastaukset 5
Vanhimmat
funktio joka tallentaa uusia alkioita listaan, esim:
void TallennaListaan(i)
struct Alkio *i;
{
static struct Alkio *viimeinen = NULL;/* aloitetaan tyhjällä listalla*/
if(!viimeinen) viimeinen=i; /* ensimmäinen */
else viimeinen->next=i;
i->next=NULL;
viimeinen=i;
}
Tässä käytetään staattista muuttujaa "viimeinen" funktion alussa. Koska static muuttuja alustetaan ainoastaan kerran sitä voidaan käyttää listarakenteen alustamiseen. (toinen vaihtoehto on että viimeinen on globaali muuttuja ja sitä initialisoidaan main():ssä.
Näin siis jos teet tuon C:llä käyttäen struct ja erillisia funktioita listan rakentamiseen, lajitteluun, alkioiden poistoon jne. Siistimpää koodia kuitenkin saisit käyttämällä C .
Kirjoitin tuon koodipätkän suoraan tähän viestiin joten se ei ole testattu. Periaate on kai oikein mutta jotain kirjoitusvirheitä voi aina sattua (kääntäjä kertoo niistä). Saattaa myös viestissä ilmetä virheellisiä rivinvaihtoja.
Aamulla vähän kireistä, ellet ole saannut toimimaan (huomasin että oli pähkäillyt asiaa aika myyöhään):
Pääohjelmaan(tai johonkin globaali muuttujaan) sinun luonnollisesti on luotava muuttujaa joka vastaa listan ensimmäistä struct:uuria (ja itse listaa):
struct Alkio MinunLista;
ja tälle annettava tarvittava data. Jokaista seuraavaa uutta alkiota varten on ensin hankittava tilaa (esim temp = malloc(sizeof(Alkio))) annettava sille data ja sen jälkeen kutsuttava TallennaListaan(temp);
Kun lähdet käsittelemään tätä listaa huomaat todennäköisesti pian että tuplalinkitetty(double-linked list) (previous-next eikä vaan next) on monessa suhteessa helpompi (ja nopeampi) käsitellä (muistinmenetyksestä ei tarvitse välittää, koodimäärä vähenee ja nopeutuu).
Myös tallennusstruktuuri Binary Tree (jossa ei ole previous-next vaan left-right) voi myös olla varteenotettava vaihtoehto jos pitkästä listasta joudut etsimään jotain. Tällainen puurakenne (varsinkin jos se tasapainotetaan) nopeutuu mitä enemmän data siihen tulee, verrattuna muihin lista rakenteisiin (tietokoneen tiedostojärjestelmä perustuu tällaiseen). Mutta nyt ehkä puhun asioista mitä et oikeastaan kysynnyt!
Mutta, kuten aikaisemmin sanoin, jos teet tätä itseesi vuoksi etkä mihenkään koulutehtävään, harkitse C . Kirjoitin tämän vastauksen ainoastaan koska minua nauratti, osaanko vielä tehdä tämän Kernigham&Ritchie:n neuvojen mukaan?
En kiitosta kaipaa, olisi vain hauskaa kuulla jos neuvoistani on jotain hyötyä?
Emmä oikein, srry, pitäs löytää jostain kokonainen yksinkertanen lista niinku yhdessä kirjassa oli.
"Tällainen puurakenne (varsinkin jos se tasapainotetaan) nopeutuu mitä enemmän data siihen tulee"
Tuo saattaa kuullostaa hieman harhaanjohtavalta, sikäli että eihän tuo tietorakenne nopeudu siitä, että sinne ladataan lisää dataa. Toiseksi, kyllähän ideaalinen hash-taulu (O(1))on silti nopeampi kuin yksikään puurakenne (O(log2(n))), edellyttäen että taulukon laajennuksia ei tarvi kovin usein tehdä.