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.
Lähdetiedosto solmulle on seuraava:// 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
// Solmu.cpp: implementation of the Solmu class.
Työntekijälle yksinkertainen luokka:
// ////////////////////////////////////////////////////////////////////// #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; } // Tyontekija.h: interface for the CTyontekija
class.
Tyontekijäluokka, joka liittyy linkitettyyn listaan on esitetty
seuraavassa:
// #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 // Tyontekija.cpp: implementation of the
CTyontekija class.
Linkitetylle listalle on seuraavassa esitetty pääohjelma:
// ////////////////////////////////////////////////////////////////////// #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; }
/************************************************************
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"); } |
C++-kieli >