Kurssiaiheen 8 tehtävät¶
Puut¶
Tarkastele alla olevaa puuta, ja vastaa seuraaviin kysymyksiin tämän puun perusteella. (Lisää tietoa puista löytyy esimerkiksi kurssiaiheen 8 luentomateriaaleista):
Huomaa. Kirjoita vastaukset pienillä kirjaimilla, aakkosjärjestyksessä ja käytä pilkkua kohteiden erottelussa.
C++ structeja yllä olevalle puun solmulle¶
Seuraavissa kahdessa tehtävässä sinun tulee valita esitetyistä C++ structeista ne, joita voidaan käyttää yllä esitetyn puun solmuina.
Huomaathan, että tehtävissä tulee olettaa, että annetun structin lisäksi muu koodi ei sisällä structeja tai luokkia. Ja lisäksi huomioi, että solmussa täytyy tallettaa solmun sisältämä tieto oikealla tietotyypillä.
Struct A
1 2 3 4 5 | struct Node {
Node* parent = nullptr;
char value;
std::unordered_set<Node*> children = {};
};
|
Struct B
1 2 3 4 | struct {
char value;
std::vector<Node*> children
};
|
Struct C
1 2 3 4 5 | struct TreeNode {
char data;
Node* leftChild = nullptr;
Node* rightChild = nullptr;
};
|
Struct D
1 2 3 4 5 | struct Node {
Node* parent = nullptr;
char value;
std::vector<Node*> children = {};
};
|
Struct E
1 2 3 4 5 | struct TreeNode {
char data;
TreeNode* leftChild = nullptr;
TreeNode* rightChild = nullptr;
};
|
Struct F
1 2 3 4 5 | struct Node {
char data;
Node* leftChild = nullptr;
Node* rightChild = nullptr;
};
|
Struct G
1 2 3 4 5 | struct Node {
Node* parent;
Node* data;
std::pair<Node*,Node*> children;
};
|
Struct H
1 2 3 4 5 | struct Node {
Node* parent;
double data;
std::pair<Node*,Node*> children;
};
|
Struct I
1 2 3 4 5 | struct Node {
Node* parent;
char data;
std::pair<Node*,Node*> children;
};
|
Struct J
1 2 3 4 5 | struct Node {
Node* parent;
bool data;
std::pair<Node*,Node*> children;
};
|
Esijärjetys¶
Välijärjestys¶
Jälkijärjestys¶
Iteraattoreiden mitätöityminen¶
Kaikki kolme alla olevaa (rikkinäistä) funktiota löytyvät päivitetystä reposta hakemistosta wk04_trees/iterator_invalidation.
Funktioita ja graderien ajamia testejä voi ajaa myös paikallisesti, se onnistuu Qt Creatorin kanssa vaihtamalla komentojonoparametrit ja
komentojonoa käyttäen antamalla parametrit ohjelmaa ajettaessa. Jos jätät parametrit antamatta, ajetaan tällöin kaikki testit.
Jos haluat testata ensimmäistä funktiota siihen liitetyllä testillä 2, vaihda komentojonoparametreiksi 1 2.
Jos taas haluat testata toista funktiota siihen liitetyllä testillä 3 (satunnaiset arvot) kahdenkymmenen alkion sisääntulovektorilla
vaihda komentojonoparametreiksi 2 3 20.
Koon määrittelevä (eli kolmas numero) komentojonoparametri ei ole pakollinen eikä vaikuta kaikkiin testeihin, oletuksena koko on 10. Kaksi ensimmäistä parametria ovat pakollisia, jos yrität ajaa jollekin funktiolle testiä, jota ei ole olemassa, ohjelma tulostaa tästä virheen.
Komentojonoparametrien vaihto Qt Creatorissa¶
Komentojonoparametrit voi vaihtaa Qt Creatorissa valitsemalla ensin vasemmasta laidasta jakoavaimen kuvan projects, sen alta Build & Run alta run.
Nyt auki olevasta listasta löytyy Command line arguments. Voit kopioida komentojonoparametrit (esimerkiksi 1 2) tuohon tekstikenttään.
Iteraattoreiden mitätöityminen 1, ascendingVector (suom.) kasvavaVektori¶
Funktio ascendingVector luo vektorin jossa on kasvavassa järjestyksessä luvut 0 - (n-1).
Korjaa se, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk04_trees/iterator_invalidation/invalidation1.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
Iteraattoreiden mitätöityminen 2, eraseEverySecond (suom.) poistaJokaToinen¶
Funktio eraseEverySecond poistaa viitteenä annetusta vektorista joka toisen alkion.
Esimerkki: {1, 2, 3, 4} -> {1, 3}
Korjaa se, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk04_trees/iterator_invalidation/invalidation2.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
Iteraattoreiden mitätöityminen 3, duplicateEvenRemoveUneven (suom.) toistaParillinenPoistaPariton¶
Funktio duplicateEvenRemoveUneven nimensä mukaisesti poistaa parittomat luvut ja duplikoi/toistaa/kopioi parilliset luvut viitteenä annetussa vektorissa.
Esimerkki: {1, 2, 3, 4} -> {2, 2, 4, 4}
Korjaa se, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk04_trees/iterator_invalidation/invalidation3.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.