Linkitetty lista

Linkitetty lista (Linked list)

Linkitetty lista on yksi perustietorakenteista. Se koostuu joukosta solmuja, joista jokainen koostuu linkitettävästä tiedosta ja viitteistä seuraavaan (ja mahdollisesti edelliseen) solmuun listassa. Yhden viitteen listaa kutsutaan yksisuuntaiseksi ja jälkimmäistä kaksisuuntaiseksi. Haluttaessa löytää tietty solmu, tulee aloittaa listan alusta, juurisolmusta (root node), ja käydä listaa läpi, kunnes haluttu solmu on löytynyt. Linkitetyn listan etuna on rajoittamaton kasvu (ei staattisesti määriteltyä maksimikokoa) ja O(1)-tason lisäys ja poisto-operaatiot (kun käytetään kaksisuuntaista linkitettyä listaa). Indeksointi on O(n).

Esimerkki 1. Solmun koodirunko.

class CSolmu

{

public:

CSolmu* Seuraava();

void AsetaSeuraava();

protected:

CSolmu* m_Seuraava; // Osoitin seuraavaan solmuun.

CSolmu* m_Edellinen; // Osoitin edelliseen solmuun.

CData* m_Data; // Osoitin listan 'dataan' eli siihen mitä listaan tallennetaan.

};

Varoitus: Koodit toimivat vain Windows-ympäristössä!

// Solmu.h: interface for the Solmu class.

// Solmu-luokka huolehtii tiedon järjestyksestä

// sekä tiedon hausta tiedostosta ja talletuksesta tiedostoon

//////////////////////////////////////////////////////////////////////

#include "Tyontekija.h"

#ifndef h_Solmu

#define h_Solmu

class CSolmu

{

public:

int HaeTiedostosta();

void Talleta(); // tiedon talletus levylle

void Tulosta(); // tulostus ruudulle

void Lisaa(CSolmu*); // solmun lisäys oikeaan kohtaan

void Poista(char Nimi[]);

CTyontekija* AnnaTyontekija() const;

CSolmu* AnnaSeuraava() const;

void AsetaSeuraava(CSolmu*);

CSolmu(CTyontekija*);

~CSolmu();

private:

CSolmu* m_pSeuraava;

CTyontekija* m_pTyontekija;

};

#endif

Lähdetiedosto solmulle on seuraava:

// Solmu.cpp: implementation of the Solmu class.

//

//////////////////////////////////////////////////////////////////////

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include "Tyontekija.h"

#include "Solmu.h"

void Menu(void);

int Debug=1;

// CSolmun muodostin

CSolmu::CSolmu(CTyontekija* Tt)

{

m_pTyontekija=Tt;

m_pSeuraava=NULL;

}

// CSolmun tuhoajafunktio

CSolmu::~CSolmu()

{

printf("\nPoistetaan tyontekija");

getch();

delete m_pTyontekija;

m_pTyontekija=0;

printf("\nAion poistaa solmun");

//delete m_pSeuraava;

//m_pSeuraava=0;

}

// Laitetaan seuraavaksi solmuksi listaan

void CSolmu::AsetaSeuraava(CSolmu* solmu)

{

m_pSeuraava=solmu;

}

CSolmu* CSolmu::AnnaSeuraava() const

{

return m_pSeuraava;

}

CTyontekija* CSolmu::AnnaTyontekija() const

{

return m_pTyontekija;

}

// Uuden solmun lisäys listaan

void CSolmu::Lisaa(CSolmu* UusiSolmu)

{

char UusiNimi[100];

char* pUusiNimi;

char TamanNimi[100];

char* pTamanNimi;

char SeuraavanNimi[100];

char* pSeuraavanNimi;

char Nimi[100];

if (!m_pSeuraava) {

m_pSeuraava=UusiSolmu;

if (Debug==1) {

printf("\nLaitan viimeideksi %s", m_pSeuraava->AnnaTyontekija()->KysyNimi(Nimi));

}

} else {

pSeuraavanNimi=m_pSeuraava->AnnaTyontekija()->KysyNimi(SeuraavanNimi);

pUusiNimi=UusiSolmu->AnnaTyontekija()->KysyNimi(UusiNimi);

pTamanNimi=m_pTyontekija->KysyNimi(TamanNimi);

// Tarkistetaanko, sopiiko solmu nykyisen ja seuraavan väliin

if (strcmp(pUusiNimi,pTamanNimi)>0 && strcmp(pSeuraavanNimi,pUusiNimi)>0) {

UusiSolmu->AsetaSeuraava(m_pSeuraava);

m_pSeuraava=UusiSolmu;

if (Debug==1) {

printf("\nTama %s Uusi %s Seuraava %s",

pTamanNimi,pUusiNimi,pSeuraavanNimi);

}

} else {

m_pSeuraava->Lisaa(UusiSolmu); //rekursiivinen kutsu

}

}

}

void CSolmu::Poista(char Nimi[])

{

char seNimi[100];

CSolmu* pTemp;

CSolmu* pTemp2;

if (m_pSeuraava) {

if (strcmp(Nimi,m_pSeuraava->AnnaTyontekija()->KysyNimi(seNimi))==0) {

printf("Loytyi");

getch();

pTemp=m_pSeuraava;

pTemp2=m_pSeuraava->m_pSeuraava;

if (Debug==1) {

printf("\n%s",pTemp->AnnaTyontekija()->KysyNimi(seNimi));

// Tarkistetaan onko poistettavaa seuraava olemassa

if (pTemp2)

printf("\n%s",pTemp2->AnnaTyontekija()->KysyNimi(seNimi));

}

delete m_pSeuraava;

if (pTemp2) {

m_pSeuraava=pTemp2; //hypätään yli

} else {

m_pSeuraava=0;

}

return;

}

if (m_pSeuraava) {

m_pSeuraava->Poista(Nimi);

}

} else {

printf("\nNimea ei loydy tietokannasta Paina enter");

getch();

}

}

// Solmun tulostus näytölle

void CSolmu::Tulosta()

{

char Nimi[100];

if (m_pTyontekija->KysyNimi(Nimi) > 0) {

printf("\nTyontekija %s", m_pTyontekija->KysyNimi(Nimi));

}

if (m_pSeuraava) {

m_pSeuraava->Tulosta(); // Rekursiivinen kutsu

}

}

/***********************************************************

Tietokannan talletus tiedostoon

************************************************************/

void CSolmu::Talleta()

{

FILE* pTiedosto;

int iLukum;

CSolmu *pTemp=0;

char SeuraavanNimi[100];

char* pSeuraavanNimi;

pTemp=this;

pTiedosto=fopen("Tiedot.oma","wb");

if (pTiedosto==NULL) {

printf("\nTiedosto ei aukea");

getch();

}

do {

if (pTemp->m_pSeuraava) {

iLukum=fwrite(pTemp->m_pSeuraava->m_pTyontekija, sizeof(CTyontekija),1,pTiedosto);

if(Debug) {

pSeuraavanNimi=pTemp->m_pSeuraava->AnnaTyontekija()->KysyNimi(SeuraavanNimi);

printf("\nTalletettava %s",pSeuraavanNimi);

}

}

// Siirrytään tietokannassa seuraavaan kohtaan

pTemp=pTemp->m_pSeuraava;

} while(pTemp);

fclose(pTiedosto);

}

/********************************************************

Tietokannan haku tiedostosta

**********************************************************/

int CSolmu::HaeTiedostosta()

{

FILE* pTiedosto; // Esitellään osoitin tiedostoon

CSolmu* pSolmu=0;

int iLukum;

CTyontekija* pTemp; // pointteri tilavaraukselle

CTyontekija Temp; // tilapäisvarasto tiedostohaulle

// Avataan tiedosto

pTiedosto=fopen("Tiedot.oma","rb");

if (pTiedosto==NULL) {

printf("\nTiedosto ei aukea");

getch();

return 0;

}

do { // luetaan tiedostoa yksi työntekijä kerrallaan muuttujaan Temp

iLukum=fread(&Temp, sizeof(CTyontekija),1,pTiedosto);

if (iLukum) { // onnistuiko luku tiedostosta

// varataan työntekijälle tila keosta

pTemp=new CTyontekija();

// *:llä haetaan osoitteessa pTemp oleva muuttuja

// ja talletetaan siihen tiedostosta haettu tieto

*pTemp=Temp;

// Varataan solmulle tilaa

pSolmu=new CSolmu (pTemp);

// lisätään solmu tietokantaan

this->Lisaa(pSolmu);

}

} while(iLukum); // luetaan niin kauan, kun löytyy

fclose(pTiedosto);

return 1;

}

Työntekijälle yksinkertainen luokka:

// Tyontekija.h: interface for the CTyontekija class.

//

#ifndef h_Tyontekija

#define h_Tyontekija

class CTyontekija

{

public:

void AsetaNimi();

void AsetaNimi(char Nimi[]);

char* KysyNimi(char Nimi[]);

CTyontekija();

~CTyontekija();

CTyontekija operator=(CTyontekija T);

private:

char m_Nimi[100];

};

#endif

Tyontekijäluokka, joka liittyy linkitettyyn listaan on esitetty seuraavassa:

// Tyontekija.cpp: implementation of the CTyontekija class.

//

//////////////////////////////////////////////////////////////////////

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include "Tyontekija.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

CTyontekija::CTyontekija()

{

//printf("\nAnna nimi: ");

//gets(m_Nimi);

}

CTyontekija::~CTyontekija()

{

}

void CTyontekija::AsetaNimi(char Nimi[])

{

strcpy(m_Nimi,Nimi);

}

char* CTyontekija::KysyNimi(char Nimi[])

{

strcpy(Nimi,m_Nimi);

return Nimi;

}

void CTyontekija::AsetaNimi()

{

printf("Anna nimi ");

gets(m_Nimi);

}

CTyontekija CTyontekija::operator=(CTyontekija T)

{

strcpy(m_Nimi,T.m_Nimi);

//strcpy(m_Osasto,T.m_Osasto);

return *this;

}

Linkitetylle listalle on seuraavassa esitetty pääohjelma:

/************************************************************

Työntekijätietokanta

Tietokanta on toteutettu linkitettynä listana

Tietokanta muodostuu solmuista, jotka on likitetty osoittimilla toisiinsa

*************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include "Tyontekija.h"

#include "Solmu.h"

void Menu();

int main()

{

int Valitsin;

char Nimi[100];

CSolmu* pSolmu=0;

int Tiedosto=0;

// Varataan tietokannalle alkukohta

CTyontekija* pTyontekija = new CTyontekija();

pTyontekija->AsetaNimi("aaa");

CSolmu* pJuuri = new CSolmu(pTyontekija);

// Haetaan tiedostosta alkukohtaa seuraavat tiedot

Tiedosto = pJuuri->HaeTiedostosta();

while(1) {

Menu();

Valitsin=getch();

switch (Valitsin) {

case '0':

exit(1);

// lisäys

case '1':

pTyontekija=new CTyontekija();

pTyontekija->AsetaNimi();

pSolmu=new CSolmu(pTyontekija);

pJuuri->Lisaa(pSolmu); // lisätään duunari listaan

pJuuri->Talleta();

break;

// Tulostus

case '2':

pJuuri->Tulosta();

break;

// Poisto

case '3':

printf("Anna nimi: ");

gets(Nimi);

pJuuri->Poista(Nimi);

pJuuri->Talleta();

break;

default:

break;

}

}

}

void Menu()

{

printf("\n\n0=ohjelman lopetus");

printf("\n1=Duunarin lisays tietokantaan");

printf("\n2=Kaikkien duunarien tulostus");

printf("\n3=Duunarin poisto tietokannasta\n\n");

}