C++-kieli‎ > ‎

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");
}


Comments